Search for: All records

The issue of internal fragmentation in data structures is a fundamental challenge in database design. A seminal result of Yao in this field shows that evenly splitting the leaves of a B-tree against a workload of uniformly random insertions achieves space utilization of around 69%. However, many database applications perform batched insertions, where a small run of consecutive keys is inserted at a single position. We develop a generalization of Yao's analysis to provide rigorous treatment of such batched workloads. Our approach revisits and reformulates the analytical structure underlying Yao's result in a way that enables generalization and is used to argue that even splitting works well for many workloads in our extended class. For the remaining workloads, we develop simple alternative strategies that provably maintain good space utilization. 

In recent decades, cloud computing as a service has emerged as a major computing paradigm. These services (e.g., Amazon EC2, Google Compute Engine, Azure Virtual Machines) all offer variations of the following basic model for how storage works: a compute instance can choose between placing data on something that resembles a local disk (e.g., Amazon EBS, Google Block Store, Azure Managed Disks) versus what we will refer to as a global disk (e.g., Amazon S3, Google GCS, Azure Blob Storage). The disks are distinguished by two features:(1) Bandwidth: Whereas the local disk has a fixed limited bandwidth, the global disk offers essentially unlimited bandwidth.(2) Cost: The local disk supports I/Os for free, while the global disk charges money each time an object is read or written.This storage model suggests a natural algorithmic problem: How should a system manage its storage across local and global disk in order to simultaneously optimize cost and performance?In this paper, we formalize this local/global disk problem as follows. A scheduler running many (potentially parallel) processes must serve I/O requests to local/global disks and can move objects between the disks over time. The local disk performs I/Os for free, but can only perform one I/O per timestep, while the global disk charges a fee for each I/O, but has unlimited bandwidth. The scheduler wishes to optimize both the stretch of each process that it runs (the running-time blowup compared to if that process used only global disk) and the overall cost savings (the amount of money saved compared to a world in which we use only the global disk).We show, for any ε ∈ (0, 1] that it is possible to support an expected stretch of 1 + O(ε) while saving a total of εE[T] expected dollars, where T is the number of distinct timesteps in which I/Os are performed. We also offer a second tradeoff curve that, for any δ \v{s} (0, 1), supports expected stretch 1 + O(δ−1) with expected cost savings (1 − δ)E[T]. Finally, we prove that both of these tradeoff curves are asymptotically optimal. 

Recent work has investigated adaptive filters, which are filters that change their internal representation in response to queries that yield false positives. These include: (1) strongly adaptive filters, which guarantee a false-positive probability of at most ϵ for any query regardless of the history of prior queries, i.e., against adaptive adversaries, (2) support-optimal filters, which guarantee an average false-positive probability of at most ϵ over sufficiently large query sequences, when the adversary is oblivious, (3) other adaptive filters that change their representation and empirically perform better, but do not come with any specific provable guarantees beyond static filters. In this paper, we investigate the performance advantages that strongly adaptive filters offer on (non-adversarial) skewed query distributions, which are common in database applications. In our theoretical and experimental results, we model query distribution skewness with the Zipfian distribution with parameterz. We consider two strongly adaptive filters: the broom filter and the telescoping adaptive filter (TAF). We also consider two adaptive (but not strongly adaptive) filters: the adaptive cuckoo filter (ACF), and a non-adaptive rank-and-select quotient filter augmented with a cache of recent false positives, which we call the cache-augmented filter (CAF). We prove upper bounds on the false-positive rates of the broom filter, the TAF, and the CAF as a function of the Zipfian parameterzas the length of the query sequence tends to infinity. We provide an implementation of the broom filter, based on the (non-adaptive) rank-and-select quotient filter. We validate the above bounds experimentally on synthetic Zipfian query sequences on the broom filter, the TAF, and the CAF. Finally, we measure the observed false-positive rate of the broom filter, the TAF, the CAF, and the ACF on highly skewed real-world network trace data. We find that all adaptive filters achieved 1-2 orders of magnitude lower false-positive rates than non-adaptive filters. We further find that the broom filter and the TAF outperform the CAF only when the ratio of distinct negative queries to positive set size is high; otherwise, the CAF and the strongly adaptive filters yield similar false-positive rates.