Optimized navigable key-value store
Embodiments of the invention utilize an improved LSM-tree-based key-value approach to strike 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 levels so as to minimize the sum of the false positive rates associated with the Bloom filters. In addition, the improved approach may predict the impact of the system design parameter(s) and/or environmental parameter(s) on the lookup performance. Subsequently, the improved approach may “self-tune” the system design parameter(s) and/or environment parameter(s) to maximize the throughput.
1. A database system comprising:
a main memory comprising volatile storage and including a plurality of Bloom filters each associated with a memory access run;
a secondary store comprising nonvolatile storage for storing files;
memory containing a log-structured merge-tree (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;
a processor for writing files to and reading 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,
wherein the Bloom filters are tuned to minimize a sum of false positive rates thereacross.
2. A method for providing an improved key-value storing system, the method comprising:
providing a main memory comprising volatile storage and including a plurality of Bloom filters each associated with a memory access run;
providing a secondary store comprising nonvolatile storage for storing files;
providing memory containing a log-structured merge-tree (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.
3. The system of claim 1 , wherein each of the files comprises a plurality of data entries and each of the runs (i) is associated with a specific level and (ii) comprises approximately equal numbers of data entries.
4. The system of claim 1 , wherein the processor is further configured to computationally predict relationships between a plurality of environmental parameters and a lookup cost for a target key, wherein the Bloom filters are tuned based at least in part on the predicted relationships.
5. The system of claim 1 , wherein the processor is further configured to predict relationships between a plurality of system design parameters and a lookup cost for a target key, wherein the Bloom filters are tuned based at least in part on the predicted relationship.
6. The system of claim 3 , wherein each of the Bloom filters associated with runs at a particular level is assigned the same false positive rate.
7. The system of claim 3 , wherein the processor is further configured to model an average number of the memory access runs probed by a lookup for a target key, wherein the Bloom filters are tuned based at least in part on the modeled number.
8. The system of claim 3 , wherein the processor is further configured to compute a first cost associated with a zero-result lookup for a target key and a second cost associated with a non-zero-result lookup for the target key, wherein the Bloom filters are tuned based at least in part on the computed first and second costs.
9. The system of claim 4 , wherein the environmental parameters comprise 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.
10. The system of claim 5 , wherein the system design parameters comprise 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.
11. The system of claim 6 , wherein the false positive rates across levels are assigned so as to minimize an amount of memory utilized by the Bloom filters.
12. The system of claim 6 , wherein the processor is 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 being assigned based on a capacity thereof.
13. The system of claim 6 , wherein 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.
14. The system of claim 7 , wherein the average number of the memory access runs corresponds to the sum of the false positive rates.
15. The system of claim 8 , wherein the false positive rates across the levels are assigned so as to minimize the first and second costs.
16. The system of claim 10 , wherein the processor is further configured to holistically tune the system design parameters so as to minimize the lookup cost.