Key-value stores implemented using fragmented log-structured merge trees

1. A method of updating a fragmented log-structured merge (FLSM) tree implementing a key-value store on a computer system having a central processing unit (CPU), a memory, and a storage system, the method comprising:

obtaining a plurality of key-value pairs having keys defined within a key space, the key space divided by a plurality of guards for each of H levels of the FLSM tree, where H is an integer greater than one, wherein a number of the plurality of guards for each of the H levels of the FLSM tree varies in proportion to an amount of data to be stored in the storage system at such level;

sorting, through execution of code by the CPU, the plurality of key-value pairs into one or more segments of sorted key-value pairs based on the plurality of guards of a target level of the H levels of the FLSM tree, wherein a first guard log of a plurality of guard logs of the target level comprises at least one segment of sorted key-value pairs; and

appending, by writing to the storage system, each of the one or more segments to a different corresponding one of the plurality of guard logs of the target level of the FLSM tree without modifying any existing segments in the plurality of guard logs of the target level, wherein a first segment of the one or more segments is appended to the first guard log without modifying the at least one segment.

2. The method of claim 1 , wherein the number of the plurality of guards in each of the H levels of the FLSM tree increases from one level to the next between an upper level and a lower level of the H levels of the FLSM tree.

3. The method of claim 1 , wherein the step of obtaining comprises:

loading a full guarded log from a level above the target level into the memory; and

sorting key-value pairs stored in the full guarded log to generate the plurality of key-value pairs.

4. The method of claim 3 , further comprising:

removing the plurality of key-value pairs from the full guarded log to produce an empty guarded log in the level above the target level.

5. The method of claim 1 , wherein each of the plurality of guards for each of H levels of the FLSM tree comprises a key in the key space.

6. The method of claim 5 , wherein, for each of the H levels of the FLSM tree, the respective plurality of guards is selected randomly from the key space.

7. The method of claim 1 , further comprising:

receiving a query specifying a key in the key space;

reading H guard logs of the FLSM tree into the memory from the storage system based on a relation between the key and the plurality of guards for each of the H levels of the FLSM tree;

identifying, through execution of code by the CPU, at least one key-value pair in the H guard logs that satisfies the query; and

providing as output at least one value corresponding to the at least one key-value pair.

8. The method of claim 7 , wherein the query is a range query that further specifies a condition associated with the key.

9. The method of claim 7 , wherein the at least one key-value pair comprises a plurality of key-value pairs in the H guard logs that satisfy the query, wherein the at least one value provided as output comprises one value, and wherein the step of providing comprises:

filtering the plurality of values corresponding to the plurality of key-value pairs to identifying the one value provided as output.

10. The method of claim 1 , further comprising:

determining the first guard log is full;

sorting all key-value pairs of all segments of the first guard log into second one or more segments of sorted key-value pairs based on the plurality of guards of a second target level of the H levels of the FLSM tree;

appending each of the second one or more segments to a different corresponding one of a second plurality of guard logs of the second target level of the FLSM tree without modifying any existing segments in the second plurality of guard logs of the second target level; and

clearing all the key-value pairs from the first guard log.

11. A non-transitory computer readable medium comprising instructions, which when executed in a computer system, causes the computer system to carry out a method of updating a fragmented log-structured merge (FLSM) tree implementing a key-value store on a computer system having a central processing unit (CPU), a memory, and a storage system, the method comprising:

obtaining a plurality of key-value pairs having keys defined within a key space, the key space divided by a plurality of guards for each of H levels of the FLSM tree, where H is an integer greater than one, wherein a number of the plurality of guards for each of the H levels of the FLSM tree varies in proportion to an amount of data to be stored in the storage system at such level;

sorting, through execution of code by the CPU, the plurality of key-value pairs into one or more segments of sorted key-value pairs based on the plurality of guards of a target level of the H levels of the FLSM tree, wherein a first guard log of a plurality of guard logs of the target level comprises at least one segment of sorted key-value pairs; and

appending, by writing to the storage system, each of the one or more segments to a different corresponding one of the plurality of guard logs of the target level of the FLSM tree without modifying any existing segments in the plurality of guard logs of the target level, wherein a first segment of the one or more segments is appended to the first guard log without modifying the at least one segment.

12. The non-transitory computer readable medium of claim 11 , wherein the number of the plurality of guards in each of the H levels of the FLSM tree increases from one level to the next between an upper level and a lower level of the H levels of the FLSM tree.

13. The non-transitory computer readable medium of claim 11 , wherein the step of obtaining comprises:

loading a full guarded log from a level above the target level into the memory; and

sorting key-value pairs stored in the full guarded log to generate the plurality of key-value pairs.

14. The non-transitory computer readable medium of claim 13 , further comprising:

removing the plurality of key-value pairs from the full guarded log to produce an empty guarded log in the level above the target level.

15. The non-transitory computer readable medium of claim 11 , further comprising:

receiving a query specifying a key in the key space;

reading H guard logs of the FLSM tree into the memory from the storage system based on a relation between the key and the plurality of guards for each of the H levels of the FLSM tree;

identifying, through execution of code by the CPU, at least one key-value pair in the H guard logs that satisfies the query; and

providing as output at least one value corresponding to the at least one key-value pair.

16. The non-transitory computer readable medium of claim 15 , wherein the query is a range query that further specifies a condition associated with the key.

17. A computer system, comprising:

a memory storing program code;

a storage system storing at least a portion of a fragmented log-structured merge (FLSM) tree implementing a key-value store, the FLSM tree including H levels, where H is an integer greater than one, wherein a number of a plurality of guards dividing a key space for each of the H levels of the FLSM tree varies in proportion to an amount of data to be stored in the storage system at such level; and

a central processing unit (CPU) configured to execute the program code stored in the memory to store a plurality of key-value pairs in the FLSM tree, the plurality of key-value pairs having keys defined within the key space, each of the key-value pairs being stored a maximum of H times in the FLSM tree, by:

sorting the plurality of key-value pairs into one or more segments of sorted key-value pairs based on the plurality of guards of a target level of the H levels of the FLSM tree, wherein a first guard log of a plurality of guard logs of the target level comprises at least one segment of sorted key-value pairs; and

appending, by writing to the storage system, each of the one or more segments to a different corresponding one of the plurality of guard logs of the target level of the FLSM tree without modifying any existing segments in the plurality of guard logs of the target level, wherein a first segment of the one or more segments is appended to the first guard log without modifying the at least one segment.

18. The computer system of claim 17 , wherein the CPU is configured to execute the program code to store each of the plurality of key-value pairs in a guarded log in H pluralities of guard logs corresponding to the H levels of the FLSM tree.

19. The computer system of claim 18 , wherein the number of the plurality of guards in each of the H levels of the FLSM tree increases from one level to the next between an upper level and a lower level of the H levels of the FLSM tree.

20. The computer system of claim 18 , wherein each of the plurality of guards for each of H levels of the FLSM tree comprises a key in the key space.

21. The computer system of claim 20 , wherein, for each of the H levels of the FLSM tree, the respective plurality of guards is selected randomly from the key space.