Merge tree modifications for maintenance operations

• US 10,706,106 B2
• Filed: 02/09/2017
• Issued: 07/07/2020
• Est. Priority Date: 02/09/2017
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Boles, David, Groves, John M., Moyer, Steven, Tomlinson, Alexander
• Primary Examiner(s): Hasan, Syed H
• Assistant Examiner(s): Ahmed, Saba
• Application Number:
  US15/428,951
• Publication Number:
  US 20180225322A1
• Time in Patent Office: 1,244 Days
• Field of Search: 707693
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Systems and techniques for merge tree modifications for maintenance operations are described herein. A request for a KVS tree is received. Here, the KVS tree is a data structure including nodes and the nodes include a temporally ordered sequence of kvsets that store keys in sorted order. A parameter set for the KVS tree is received. The request is executed on the KVS tree by modifying operation of the KVS tree in accordance with the parameter.

Claims

1. A system comprising processing circuitry configured to perform operations comprising:

receiving, by the processing circuitry, a request for a Key-Value Set (KVS) tree stored on non-transitory computer-readable media, the KVS tree being a data structure comprising nodes, a node of the KVS tree comprising a temporally ordered sequence of key-value sets (kvsets), the temporally ordered sequence comprising an oldest kvset at one end of the temporally ordered sequence and a newest kvset at another end of the temporally ordered sequence, each kvset storing keys in sorted order within the kvset;

receiving a parameter set for the KVS tree, the receiving of the parameter set being separate from the request; and

executing, by the processing circuitry, the request on the KVS tree by performing an operation of the KVS tree as modified in accordance with the parameter set.

2. The system of claim 1, wherein the request comprises a key prefix and a tombstone, the parameter set having a member in the request that defines the tombstone as a prefix-tombstone, and to execute the request on the KVS tree, the processing circuitry being configured to write the prefix-tombstone to a kvset of the KVS tree.

3. The system of claim 1, wherein the request comprises a key, the parameter set comprising a member that specifies tombstone acceleration;

and to execute the request on the KVS tree, the processing circuitry being configured to write a tombstone in at least one child node specified by performing a spill function on the key.

4. The system of claim 3, wherein the tombstone is written to all extant child nodes specified by performing the spill function on the key.

5. The system of claim 1, wherein the request comprises a key, tombstone, and a storage size of a value in the KVS tree corresponding to the key, the parameter set having a member that specifies garbage collection statistics storage, and to execute the request on the KVS tree, the processing circuitry being configured to store the key and the storage size in a data structure for the KVS tree.

6. The system of claim 1, wherein the parameter set comprises a member that specifies that the KVS tree is immutable, to execute the request on the KVS tree, the processing circuitry being configured to write the request to a root node of the KVS tree.

7. The system of claim 6, wherein the KVS tree uses key compaction exclusively when the KVS tree is immutable.

8. The system of claim 7, wherein the processing circuitry is further configured to:

store key search statistics in response to the KVS tree being immutable; and

perform key compaction in response to the key search statistics meeting a threshold.

9. The system of claim 8, wherein the processing circuitry is further configured to reset the key search statistics in response to at least one of a compaction, an ingest, after a specified number of searches, or after a specified time interval.

10. The system of claim 6, wherein a second member of the parameter set specifies that the KVS tree removes elements on a first-in-first-out basis, a third member of the parameter set specifying a retention constraint of the KVS tree, the KVS tree performing key compactions on kvsets based on the retention constraint, and the KVS tree removing an oldest kvset when the retention constraint is violated.

11. At least one non-transitory machine readable medium comprising instruction that, when executed by a machine, cause the machine to perform operations comprising:

receiving, by processing circuitry of the machine, a request for a Key-Value Set (KVS) tree stored on non-transitory computer-readable media, the KVS tree being a data structure comprising nodes, a node of the KVS tree comprising a temporally ordered sequence of key-value sets (kvsets), the temporally ordered sequence comprising an oldest kvset at one end of the temporally ordered sequence and a newest kvset at another end of the temporally ordered sequence, each kvset storing keys in sorted order within the kvset;

receiving a parameter set for the KVS tree, the receiving of the parameter set being separate from the request; and

executing, by the processing circuitry of the machine, the request on the KVS tree by performing an operation of the KVS tree as modified in accordance with the parameter set.

12. The at least one machine readable medium of claim 11, wherein the request comprises a key prefix and a tombstone, the parameter set having a member in the request that defines the tombstone as a prefix-tombstone, and executing the request on the KVS tree comprising writing the prefix-tombstone to a kvset of the KVS tree.

13. The at least one machine readable medium of claim 12, wherein a prefix-tombstone matches any key with the same prefix as the key prefix of the prefix-tombstone on a KVS tree operation comparing keys.

14. The at least one machine readable medium of claim 11, wherein the request comprises a key, the parameter set comprising a member that specifies tombstone acceleration;

and the executing the request on the KVS tree comprising writing a tombstone in at least one child node specified by performing a spill function on the key.

15. The at least one machine readable medium of claim 14, wherein the tombstone is written to all extant child nodes specified by performing the spill function on the key.

16. The at least one machine readable medium of claim 14, wherein the request comprises a tombstone.

17. The at least one machine readable medium of claim 14, wherein the request comprises a value.

18. The at least one machine readable medium of claim 11, wherein the request comprises a key, tombstone, and a storage size of a value in the KVS tree corresponding to the key, the parameter set having a member that specifies garbage collection statistics storage, and executing the request on the KVS tree comprising storing the key and the storage size in a data structure for the KVS tree.

19. The at east one machine readable medium of claim 18, wherein the tombstone is a prefix-tombstone.

20. The at least one machine readable medium of claim 11, wherein the parameter set comprises a member that specifies that the KVS tree is immutable, executing the request on the KVS tree comprising writing the request to a root node of the KVS tree.

21. The at least one machine readable medium of claim 20, wherein the KVS tree uses key compaction exclusively when the KVS tree is immutable.

22. The at least one machine readable medium of claim 21, wherein the operations comprise:

storing key search statistics in response to the KVS tree being immutable; and

performing key compaction in response to the key search statistics meeting a threshold.

23. The at least one machine readable medium of claim 22, wherein the key search statistics are at least one of a minimum, maximum, average, or mean time to search.

24. The at least one machine readable medium of claim 22, wherein the key search statistics are a number of kvsets in the root node.

25. The at least one machine readable medium of claim 22, wherein the operations comprise resetting the key search statistics in response to at least one of a compaction, an ingest, after a specified number of searches, or after a specified time interval.

26. The at least one machine readable medium of claim 20, wherein a second member of the parameter set specifies that the KVS tree removes elements on a first-in-first-out basis, a third member of the parameter set specifying a retention constraint of the KVS tree, the KVS tree performing key compactions on kvsets based on the retention constraint, and the KVS tree removing an oldest kvset when the retention constraint is violated.

27. The at least one machine readable medium of claim 26, wherein to perform key compactions on kvsets based on the retention constraint comprises:

grouping contiguous kvsets to produce a set of groups, a summed metric from each member in the set of groups approximating a fraction of the retention constraint; and

performing key compaction on each member of the set of groups.

28. The at least one machine readable medium of claim 26, wherein the retention constraint is a maximum number of key-value pairs.

29. The at least one machine readable medium of claim 26, wherein the retention constraint is a maximum age of a key-value pair.

30. The at least one machine readable medium of claim 26, wherein the retention constraint is a maximum storage value consumed by key-value pairs.

31. A machine-implemented method comprising:

receiving, by processing circuitry of a machine, a request for a Key-Value Set (KVS) tree stored on non-transitory computer-readable media, the KVS tree being a data structure comprising nodes, a node of the KVS tree comprising a temporally ordered sequence of key-value sets (kvsets), the temporally ordered sequence comprising an oldest kvset at one end of the temporally ordered sequence and a newest kvset at another end of the temporally ordered sequence, each kvset storing keys in sorted order within the kvset;

receiving a parameter set for the KVS tree, the receiving of the parameter set being separate from the request; and

executing, by the processing circuitry of the machine, the request on the KVS tree by performing an operation of the KVS tree as modified in accordance with the parameter set.

32. The method of claim 31, wherein the request comprises a key prefix and a tombstone, the parameter set having a member in the request that defines the tombstone as a prefix-tombstone, and executing the request on the KVS tree comprising writing the prefix-tombstone to a kvset of the KVS tree.

33. The method of claim 31, wherein the request comprises a key, the parameter set comprising a member that specifies tombstone acceleration;

and the executing the request on the KVS tree comprising writing a tombstone in at least one child node specified by performing a spill function on the key.

34. The method of claim 31, wherein the parameter set comprises a member that specifies that the KVS tree is immutable, wherein executing the request on the KVS tree comprises writing the request to a root node of the KVS tree.

35. The method of claim 34, wherein the KVS tree uses key compaction exclusively when the KVS tree is immutable.

36. The method of claim 35, comprising:

storing key search statistics in response to the KVS tree being immutable; and

performing key compaction in response to the key search statistics meeting a threshold.

37. A system comprising:

means for receiving a request for a Key-Value Set (KVS) tree stored on non-transitory computer-readable media, the KVS tree being a data structure comprising nodes, a node of the KVS tree comprising a temporally ordered sequence of key-value sets (kvsets), the temporally ordered sequence comprising an oldest kvset at one end of the temporally ordered sequence and a newest kvset at another end of the temporally ordered sequence, each kvset storing keys in sorted order within the kvset;

means for receiving a parameter set for the KVS tree the receiving of the parameter set being separate from the request; and

means for executing the request on the KVS tree by performing an operation of the KVS tree as modified in accordance with the parameter set.

38. The system of claim 37, wherein the request comprises a key prefix and a tombstone, the parameter set having a member in the request that defines the tombstone as a prefix-tombstone, and executing the request on the KVS tree comprising writing the prefix-tombstone to a kvset of the KVS tree.

39. The system of claim 37, wherein the request comprises a key, the parameter set comprising a member that specifies tombstone acceleration;

and the executing the request on the KVS tree comprising writing a tombstone in at least one child node specified by performing a spill function on the key.

40. The system of claim 37, wherein the parameter set comprises a member that specifies that the KVS tree is immutable, executing the request on the KVS tree comprising writing the request to a root node of the KVS tree.

41. The system of claim 40, wherein the KVS tree uses key compaction exclusively when the KVS tree is immutable.

42. The system of claim 41, comprising:

means for storing key search statistics in response to the KVS tree being immutable; and

means for performing key compaction in response to the key search statistics meeting a threshold.