File management with log-structured merge bush
Embodiments of the present invention provide a new multi-level data structure, log-structured merge bush (LSM-bush), to alleviate the performance compromise between LSH-table and LSM-tree data structures. Similar to LSM-tree, LSM-bush may buffer writes in memory, merge the writes as sorted runs across multiple levels in storage, and use in-memory fence pointers and Bloom filters to facilitate lookups. LSM-bush differs from LSM-tree in that it allows newer data to be merged more “lazily” than LSM-tree. This can be achieved by allowing larger numbers of runs to be collected at the smaller levels before merging them.
1. A database system comprising:
a main memory comprising volatile storage and including a file buffer and a plurality of Bloom filters each associated with a memory access run;
a secondary store comprising nonvolatile storage for storing files;
memory comprising volatile storage and containing a data structure providing indexed access to files stored in the file buffer and the secondary store, the data structure being organized into a plurality of 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,
wherein (i) each of the data structure levels has a capacity specifying a number of runs included therein before being merged and moved to a level having a larger capacity, and (ii) the processor is further configured to determine the capacity associated with each level such that a first capacity ratio corresponding to the capacities of a first pair of hierarchically adjacent levels in the data structure is different from a second capacity ratio corresponding to the capacities of a second pair, different from the first pair, of hierarchically adjacent levels in the data structure.
2. The database system of claim 1 , wherein at least one capacity ratio between two adjacent smaller levels is larger than the capacity ratio between two adjacent larger levels such that larger numbers of runs are collected at the smaller levels before being merged.
3. The database system of claim 2 , wherein the capacity ratio satisfies an equation:
r
i
=
{
T
2
L
-
i
-
1
1
≤
i
≤
L
-
1
2
i
=
L
wherein r i represents the capacity ratio of the capacity in level i to the capacity in level i−1; T represents a growth rate of the capacity ratios; and L represents the largest level in the data structure.
4. The database system of claim 3 , wherein the capacity ratio further satisfies an equation:
r i =r i+1 2 .
5. The database system of claim 1 , wherein the largest level comprises exactly one run and each of the other levels comprises one or more runs.
6. The database system of claim 1 , wherein the processor is further configured to tune a total number of levels in the data structure so as to provide a desired trade-off among a write cost, a read cost and a memory footprint.
7. The database system of claim 6 , wherein the processor is further configured to tune the total number of levels based at least in part on an application workload and an available memory budget.
8. The database system of claim 6 , wherein the processor is further configured to tune the total number of levels within two boundary values.
9. The database system of claim 7 , wherein the two boundary values satisfy an equation:
L min =3 when T =( N L /2 ·P ) 1/3
L max =(1+log 2 (log 2 ( N L /2 ·P ))+1) when T= 2
where L min and L max represent a minimal value and a maximal value of the total number of levels, respectively; N L represents a number of data entries at the largest level; P represents a size of the file buffer; and T represents a growth rate of the capacity ratios.
10. The database system of claim 1 , wherein the processor is further configured to allocate the Bloom filters so as to minimize a sum of false positive rates thereacross.
11. The database system of claim 10 , wherein each of the Bloom filters is associated with one of the levels, the processor being further configured to assign a false positive rate to each Bloom filter based at least in part on the capacity ratio associated with the corresponding level.
12. A method of managing electronic files, the method comprising the steps of:
providing a main computer memory comprising volatile storage and including a file buffer and a plurality of Bloom filters each associated with a memory access run;
providing a secondary store comprising nonvolatile storage for storing files;
storing, in a memory comprising volatile storage, a data structure providing indexed access to files stored in the file buffer and the secondary store, the data structure being organized into a plurality of levels and indexing the files as key-value pairs; and
writing files to and reading files from the main memory and the secondary store in runs each having a size, wherein each of the data structure levels has a capacity specifying a number of runs included therein before being merged and moved to a level having a larger capacity; and
determining the capacity associated with each level such that a first capacity ratio corresponding to the capacities of a first pair of hierarchically adjacent levels in the data structure is different from a second capacity ratio corresponding to the capacities of a second pair, different from the first pair, of hierarchically adjacent levels in the data structure.
13. The method of claim 12 , wherein at least one capacity ratio between two adjacent smaller levels is larger than the capacity ratio between two adjacent larger levels such that larger numbers of runs are collected at the smaller levels before being merged.
14. The method of claim 13 , wherein the capacity ratio satisfies an equation:
r
i
=
{
T
2
L
-
i
-
1
1
≤
i
≤
L
-
1
2
i
=
L
wherein r i represents the capacity ratio of the capacity in level i to the capacity in level i−1; T represents a growth rate of the capacity ratios; and L represents the largest level in the data structure.
15. The method of claim 14 , wherein the capacity ratio further satisfies an equation:
r i =r i+1 2 .
16. The method of claim 14 , wherein the largest level comprises exactly one run and each of the other levels comprises one or more runs.
17. The method of claim 14 , further comprising the step of tuning a total number of levels in the data structure so as to provide a desired trade-off among a write cost, a read cost and a memory footprint.
18. The method of claim 17 , further comprising the step of tuning the total number of levels based at least in part on an application workload and an available memory budget.
19. The method of claim 17 , further comprising the step of tuning the total number of levels within two boundary values.
20. The method of claim 18 , wherein the two boundary values satisfy an equation:
L min =3 when T =( N L /2 ·P ) 1/3
L max =(1+log 2 (log 2 ( N L /2 ·P ))+1) when T =2
where L min and L max represent a minimal value and a maximal value of the total number of levels, respectively; N L represents a number of data entries at the largest level; P represents a size of the file buffer; and T represents a growth rate of the capacity ratios.
21. The method of claim 12 , further comprising the step of allocating the Bloom filters so as to minimize a sum of false positive rates thereacross.
22. The method of claim 21 , wherein each of the Bloom filters is associated with one of the levels, and further comprising the step of assigning a false positive rate to each Bloom filter based at least in part on the capacity ratio associated with the corresponding level.