FIELD OF THE INVENTION

The field of the invention relates, generally, to key-value stores and, more particularly, to the key-value stores involving log-structured merge-trees (“LSM-trees”).

BACKGROUND

Very large data stores, such as those that support business intelligence and “big data” applications, are often organized as key-value stores. Unlike the more common “transactional” databases used for routine business applications, key-value stores are designed to quickly retrieve indexed data items. Because of their size, key-value stores may utilize a hierarchy of storage options reflecting the trade-off between access speed and cost per bit of storage. Given a large dataset that receives frequent additions (“writes”) and the need to index that dataset to support queries, it can be challenging to organize the tiers of available storage for optimum efficiency and performance.

LSM tree is a data structure with performance characteristics that make it attractive for providing indexed access to files with high insert volume. LSM trees, like other search trees, maintain key-value pairs, i.e., sets of two linked data items: a key, which is a unique identifier for some item of data, and the value, which is either the data that is identified or a pointer to the location of that data. LSM trees maintain data in two or more separate structures, each of which is optimized for its respective underlying storage medium; data is synchronized between the two structures efficiently, in batches. More specifically, LSM trees cascade data over time from smaller, higher performing (but more expensive) storage facilities to larger, slower and less expensive facilities. The LSM tree later sort-merges runs in order to (1) remove obsolete entries to reclaim space, and (2) bound the number of runs that a lookup has to probe. Runs are organized into levels of exponentially increasing sizes. A “point lookup” starts from the smallest level and terminates when it finds the target key, whereas a “range lookup” accesses the relevant key range across all runs at all levels to form a complete result.

To speed up lookups on individual runs, modern designs maintain two additional data structures in main memory. First, for every run there is a set of fence pointers that contain the first key of every disk page of the run; this allows lookups to access a particular key within a run with just one I/O. Second, for every run there exists a Bloom filter, which probabilistically allows a run to be skipped if it does not contain the target key. (A Bloom filter is a probabilistic data structure used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not—i.e., query returns either “possibly in set” or “definitely not in set.” The more elements that are added to the set, the larger the probability of false positives will be.)

LSM-based key-value stores exhibit an intrinsic trade-off among the I/O costs of updates, point lookups, and range lookups, as well as the cost of storage (measured as space amplification, i.e., the amount of storage space occupied by obsolete entries). The reason is that they perform expensive merge operations in order to (1) bound the number of runs that a lookup has to probe, and (2) remove obsolete entries to reclaim space. Given this performance trade-off and the many parameters that can affect it, determining how best to organize storage and retrieval operations to maximize overall performance in a key-value store represents a significant challenge.

SUMMARY

Embodiments of the present invention provides an improved key-value approach based on LSM-trees that advantageously strikes the optimal balance between the costs of updates and lookups with any given main memory budget. The improved approach involves allocating memory to Bloom filters differently across different tree levels so as to minimize the sum of the false positive rates (FPRs) associated with the Bloom filters. In one implementation, the FPR of each Bloom filter is set to be proportional to the number of entries in the memory access run to which the Bloom filter corresponds; this indicates that the FPRs for shallower levels in the LSM-tree exponentially decrease. Because the same amount of memory can have a higher impact in reducing the FPR for smaller runs, this approach may advantageously shave a factor of O(L) (where L is the number of LSM-tree levels) from the worst-case lookup cost as well as allow the lookup cost to scale better with the data volume (as compared with conventional key-value systems based on LSM-trees). In addition, because the improved approach may remove the dependence of the lookup cost on the buffer size of LSM-tree, the contention in how to allocate main memory between the filters and the buffer may be removed, thereby simplifying system tuning.

In various embodiments, the improved key-value approach can predict how changing a system design parameter (e.g., the size ratio among the levels, the merge policy, the FPRs assigned to the Bloom filters across different levels, and/or the allocation of main memory between the buffer and the filters) or an environmental parameter (e.g., the main memory budget, the proportion of reads and writes in the workload, the number and/or size of data entries, the underlying storage medium, etc.) would impact worst-case performance. This may be achieved by closed-form models for the worst-case I/O costs of lookups and updates in terms of the LSM tree design parameters. For example, the closed-form models may predict how a change in main memory utilization or allocation may reposition the Pareto curve in the LSM-tree design space. (As further described below, a Pareto curve plots the cost trade-off between database lookups and updates. Along the Pareto curve, the lookup cost cannot be improved without sacrificing update cost, and vice versa). Thus, the improved approach may “self-tune” the system design parameters and/or environment parameters to maximize the worst-case throughput. In various embodiments, this is achieved by, first, using asymptotic analysis to map the design space and thereby devise a rule for allocation of main memory between the buffer and the filters; and modeling worst-case throughput with respect to (1) the model for the lookup cost and update cost, (2) the proportion of lookups and updates in the workload, and (3) the costs of reads and writes to persistent storage.

Accordingly, in one aspect, the invention pertains to a database system including a main memory having volatile storage and including multiple Bloom filters, each associated with a memory access run; a secondary store having nonvolatile storage for storing files; memory containing an LSM tree providing indexed access to files stored in the memory and the secondary store, the LSM tree being organized into levels and indexing the files as key-value pairs; and a processor for writing files to and reading files from the main memory and the secondary store in runs, each having a size. In one implementation, the processor is configured to limit the runs associated with a read or write operation in accordance with the Bloom filters. In addition, the Bloom filters are tuned to minimize a sum of false positive rates thereacross.

In various embodiments, each of the files includes multiple data entries and each of the runs (i) is associated with a specific level and (ii) includes approximately equal numbers of data entries. In addition, each of the Bloom filters associated with runs at a particular level is assigned the same false positive rate. The false positive rates across levels may be assigned so as to minimize an amount of memory utilized by the Bloom filters. In addition, the processor may be further configured to determine a number of the levels to which the Bloom filters are allocated; the false positive rate for each number of the levels may be assigned based on a capacity thereof In one implementation, the false positive rate assigned to each Bloom filter is proportional to a number of data entries in the memory access run corresponding to the Bloom filter.

The processor may be further configured to model an average number of the memory access runs probed by a lookup for a target key. The Bloom filters may be tuned based at least in part on the modeled number. In some embodiments, the average number of the memory access runs corresponds to the sum of the false positive rates. Additionally or alternatively, the processor may be further configured to compute the first cost associated with a zero-result lookup for a target key and the second cost associated with a non- zero-result lookup for the target key. The Bloom filters may be tuned based at least in part on the computed first and second costs. In addition, the false positive rates across the levels may be assigned so as to minimize the first and second costs.

In various embodiments, the processor is further configured to computationally predict relationships between one or more environmental parameters (e.g., a main memory budget, a proportion of reads and writes in a workload, a number of data entries associated with the files, and/or a size of the data entries) and a lookup cost for a target key. The Bloom filters are tuned based at least in part on the predicted relationships. Additionally or alternatively, the processor may be further configured to predict relationships between one or more system design parameters (e.g., a size ratio among the levels of the LSM tree, a merge policy, the false positive rates assigned to the Bloom filters across different levels, and/or an allocation of the main memory between the memory and the Bloom filters) and a lookup cost for a target key. The Bloom filters may be tuned based at least in part on the predicted relationship. In one implementation, the processor is further configured to holistically tune the system design parameter(s) so as to minimize the lookup cost.

In another aspect, the invention relates to a method for providing an improved key-value storing system. In various embodiments, the method includes providing a main memory having volatile storage and including multiple Bloom filters, each associated with a memory access run; providing a secondary store having nonvolatile storage for storing files; providing memory containing an LSM tree having indexed access to files stored in the memory and the secondary store, the LSM tree being organized into levels and indexing the files as key-value pairs; using a processor to write files to and read files from the main memory and the secondary store in runs each having a size, the processor being configured to limit the runs associated with a read or write operation in accordance with the Bloom filters; and tuning the Bloom filters to minimize a sum of false positive rates thereacross.

In some embodiments, each of the files includes multiple data entries and each of the runs (i) is associated with a specific level and (ii) includes approximately equal numbers of data entries. In addition, each of the Bloom filters associated with runs at a particular level is assigned the same false positive rate. The false positive rates across levels may be assigned so as to minimize an amount of memory utilized by the Bloom filters. In one implementation, the method further includes determining a number of the levels to which the Bloom filters are allocated, and assigning the false positive rate for each number of the levels based at least in part on a capacity thereof. In addition, the method may include proportionally assigning the false positive rate to each Bloom filter based on a number of data entries in the memory access run corresponding to the Bloom filter.

The method may further include modeling an average number of the memory access runs probed by a lookup for a target key. The Bloom filters may be tuned based at least in part on the modeled number. In some embodiments, the average number of the memory access runs corresponds to the sum of the false positive rates. Additionally or alternatively, the method may include computing the first cost associated with a zero-result lookup for a target key and the second cost associated with a non- zero-result lookup for the target key. The Bloom filters may be tuned based at least in part on the computed first and second costs. In addition, the method may include assigning the false positive rates across the levels so as to minimize the first and second costs.

In various embodiments, the method further includes computationally predicting relationships between one or more environmental parameters (e.g., a main memory budget, a proportion of reads and writes in a workload, a number of data entries associated with the files, and/or a size of the data entries) and a lookup cost for a target key. The Bloom filters is tuned based at least in part on the predicted relationships. Additionally or alternatively, the method may include predicting relationships between one or more system design parameters (a size ratio among the levels of the LSM tree, a merge policy, the false positive rates assigned to the Bloom filters across different levels, and/or an allocation of the main memory between the memory and the Bloom filters) and a lookup cost for a target key. The Bloom filters may be tuned based at least in part on the predicted relationship. In one implementation, the method further includes holistically tuning the system design parameter(s) so as to minimize the lookup cost

Reference throughout this specification to “one example,” “an example,” “one embodiment,” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the example is included in at least one example of the present technology. Thus, the occurrences of the phrases “in one example,” “in an example,” “one embodiment,” or “an embodiment” in various places throughout this specification are not necessarily all referring to the same example. Furthermore, the particular features, structures, routines, steps, or characteristics may be combined in any suitable manner in one or more examples of the technology. The headings provided herein are for convenience only and are not intended to limit or interpret the scope or meaning of the claimed technology.

