Merge tree garbage metrics

• US 10,706,105 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,912
• Publication Number:
  US 20180225321A1
• Time in Patent Office: 1,244 Days
• Field of Search: 707693
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Systems and techniques for collecting and using merge tree garbage metrics are described herein. A kvset is created for a node in a KVS tree. Here, a set of kvset metrics for the kvset are computed as part of the node creation. The kvset is added to the node. The node is selected for a compaction operation based on a metric in the set of kvset metrics. The compaction operation is performed on the node.

Claims

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

creating a key-value set (kvset) for a node in a key-value set (KVS) tree, the creation of the kvset including computation of a set of kvset metrics for the kvset, the kvset metrics included in the kvset, any kvset being arranged to store multiple key-value pairs in which a given key is unique to the kvset, the node comprising a temporally ordered sequence of 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, and the KVS tree having a determinative mapping that provides a rule such that any key-value pair maps a specific path through the KVS tree to a specific child node at any level of the KVS tree without regard to node content of the KVS tree;

adding the kvset to the temporally ordered sequence of kvsets of the node, the kvset being immutable once added to the temporally ordered sequence of kvsets of the node;

selecting the node for a compaction operation based on a metric in the set of kvset metrics; and

performing the compaction operation on the node.

2. The system of claim 1, wherein the kvset is created in response to a compaction operation, the compaction operation being at least one of a key compaction, a key-value compaction, a spill compaction, or a hoist compaction.

3. The system of claim 2, wherein the compaction operation is a key compaction, and the set of kvset metrics comprising metrics of unreferenced values in the kvset as a result of the key compaction.

4. The system of claim 2, wherein the set of kvset metrics comprise an estimate of obsolete key-value pairs in the kvset, the estimate of obsolete key-value pairs calculated by the processing circuitry to sum a number of key entries from pre-compaction kvsets that were not included in the kvset.

5. The system of claim 2, wherein the set of kvset metrics comprise an estimated storage size of obsolete key-value pairs in the kvset, the estimated storage size of obsolete key-value pairs calculated by the processing circuitry to sum storage sizes of key entries and corresponding values from pre-compaction kvsets that were not included in the kvset.

6. The system of claim 2, wherein the set of kvset metrics comprise an estimated storage size of valid key-value pairs in the kvset, the estimated storage size of valid key-value pairs calculated by the processing circuitry to sum storage sizes of key entries and corresponding values from pre-compaction kvsets that were included in the kvset.

7. The system of claim 1, wherein the processing circuitry is configured to modify node metrics in response to adding the kvset to the node.

8. The system of claim 7, wherein the node metrics comprise a value of a fraction of estimated obsolete key-value pairs in kvsets subject to prior compactions performed on a node group comprising the node.

9. The system of claim 8, wherein the node metrics comprise a summation of like metrics in the set of kvset metrics resulting from a compaction operation and previous kvset metrics from compaction operations performed on the node.

10. The system of claim 8, wherein the value is a mean of the fraction of estimated obsolete key-value pairs in kvsets subject to a set number of most recent prior compactions for the node.

11. The system of claim 8, wherein the node metrics comprise an estimated number of keys that are the same in the kvset and a different kvset of the node.

12. The system of claim 11, wherein, to calculate the estimated number of keys, the processing circuitry is further configured to:

obtain a first key bloom filter from the kvset;

obtain a second key bloom filter from the different kvset; and

intersect the first key bloom filter and the second key bloom filter to produce a node bloom filter estimated cardinality (NBEC).

13. The system of claim 12, wherein the node metrics comprise the processing circuitry to multiply a NKVcap value by a Fobs value, where the NKVcap value is a total storage capacity used by keys and values in each kvset in the node for which a bloom filter was intersected to produce the NBEC, and where the Fobs value is the result of subtracting the NBEC from an NKVcnt value and dividing by NKVcnt, where the NKVcnt value is a total count of key value pairs in each kvset of the node for which a bloom filter was intersected to produce the NBEC.

14. The system of claim 1, wherein, to selecting the node for the compaction operation, the processing circuitry is further configured to:

collect sets of kvset metrics for a multiple of nodes comprising the node;

sort the multiple of nodes based on the sets of kvset metrics; and

select a subset of the multiple of nodes based on a sort order from the sorting, wherein, to perform the compaction operation on the node, the processing circuitry configured to perform the compaction operation on each node in the subset of the multiple of nodes, the subset of the multiple of nodes comprising the node.

15. The system of claim 14, wherein a cardinality of the subset of the multiple of nodes is set by a performance value.

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

creating a key-value set (kvset) for a node in a key-value set (KVS) tree, the creation of the kvset comprising computing a set of kvset metrics for the kvset, the kvset metrics included in the kvset, any kvset being arranged to store multiple key-value pairs in which a given key is unique to the kvset, the node comprising a temporally ordered sequence of 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, and the KVS tree having a determinative mapping that provides a rule such that any key-value pair maps a specific path through the KVS tree to a specific child node at any level of the KVS tree without regard to node content of the KVS tree;

adding the kvset to the temporally ordered sequence of kvsets of the node, the kvset being immutable once added to the temporally ordered sequence of kvsets of the node;

selecting the node for a compaction operation based on a metric in the set of kvset metrics; and

performing the compaction operation on the node.

17. The at least one machine readable medium of claim 16, wherein the kvset is created in response to a compaction operation, the compaction operation being at least one of a key compaction, a key-value compaction, a spill compaction, or a hoist compaction.

18. The at least one machine readable medium of claim 17, wherein the compaction operation is a key compaction, and the set of kvset metrics comprising metrics of unreferenced values in the kvset as a result of the key compaction.

19. The at least one machine readable medium of claim 17, wherein the set of kvset metrics comprise an estimate of obsolete key-value pairs in the kvset, the estimate of obsolete key-value pairs calculated by summing a number of key entries from pre-compaction kvsets that were not included in the kvset.

20. The at least one machine readable medium of claim 17, wherein the set of kvset metrics comprise an estimated storage size of obsolete key-value pairs in the kvset, the estimated storage size of obsolete key-value pairs calculated by summing storage sizes of key entries and corresponding values from pre-compaction kvsets that were not included in the kvset.

21. The at least one machine readable medium of claim 17, wherein the set of kvset metrics comprise an estimated storage size of valid key-value pairs in the kvset, the estimated storage size of valid key-value pairs calculated by summing storage sizes of key entries and corresponding values from pre-compaction kvsets that were included in the kvset.

22. The at least one machine readable medium of claim 16, where the operations further comprise modifying node metrics in response to adding the kvset to the node.

23. The at least one machine readable medium of claim 22, wherein the node metrics comprise a value of a fraction of estimated obsolete key-value pairs in kvsets subject to prior compactions performed on a node group comprising the node.

24. The at least one machine readable medium of claim 23, wherein the node metrics comprise a summation of like metrics in the set of kvset metrics resulting from a compaction operation and previous kvset metrics from compaction operations performed on the node.

25. The at least one machine readable medium of claim 23, wherein the value is a mean of the fraction of estimated obsolete key-value pairs in kvsets subject to a set number of most recent prior compactions for the node.

26. The at least one machine readable medium of claim 23, wherein the node metrics comprise an estimated number of keys that are the same in the kvset and a different kvset of the node.

27. The at least one machine readable medium of claim 26, wherein the estimated number of keys are calculated by:

obtaining a first key bloom filter from the kvset;

obtaining a second key bloom filter from the different kvset; and

intersecting the first key bloom filter and the second key bloom filter to produce a node bloom filter estimated cardinality (NBEC).

28. The at least one machine readable medium of claim 27, wherein the node metrics comprise multiplying a NKVcap value by a Fobs value, where the NKVcap value is a total storage capacity used by keys and values in each kvset in the node for which a bloom filter was intersected to produce the NBEC, and where the Fobs value is the result of subtracting the NBEC from an NKVcnt value and dividing by NKVcnt, where the NKVcnt value is a total count of key value pairs in each kvset of the node for which a bloom filter was intersected to produce the NBEC.

29. The at least one machine readable medium of claim 16, wherein selecting the node for the compaction operation comprises:

collecting sets of kvset metrics for a multiple of nodes comprising the node;

sorting the multiple of nodes based on the sets of kvset metrics; and

selecting a subset of the multiple of nodes based on a sort order from the sorting, the performing the compaction operation on the node comprising performing the compaction operation on each node in the subset of the multiple of nodes, the subset of the multiple of nodes comprising the node.

30. The at least one machine readable medium of claim 29, wherein a cardinality of the subset of the multiple of nodes is set by a performance value.

31. A machine-implemented method comprising:

creating a key-value set (kvset) for a node in a key-value set (KVS) tree, the creation of the kvset comprising computing a set of kvset metrics for the kvset, the kvset metrics included in the kvset, any kvset being arranged to store multiple key-value pairs in which a given key is unique to the kvset, the node comprising a temporally ordered sequence of 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, and the KVS tree having a determinative mapping that provides a rule such that any key-value pair maps a specific path through the KVS tree to a specific child node at any level of the KVS tree without regard to node content of the KVS tree;

adding the kvset to the temporally ordered sequence of kvsets of the node, the kvset being immutable once added to the temporally ordered sequence of kvsets of the node;

selecting the node for a compaction operation based on a metric in the set of kvset metrics; and

performing the compaction operation on the node.

32. The method of claim 31, wherein the kvset is created in response to a compaction operation, the compaction operation being at least one of a key compaction, a key-value compaction, a spill compaction, or a hoist compaction.

33. The method of claim 31, further comprising modifying node metrics in response to adding the kvset to the node.

34. The method of claim 33, wherein the node metrics comprise a value of a fraction of estimated obsolete key-value pairs in kvsets subject to prior compactions performed on a node group comprising the node.

35. The method of claim 34, wherein the node metrics comprise an estimated number of keys that are the same in the kvset and a different kvset of the node.

36. The method of claim 35, wherein the estimated number of keys are calculated by:

obtaining a first key bloom filter from the kvset;

obtaining a second key bloom filter from the different kvset; and

intersecting the first key bloom filter and the second key bloom filter to produce a node bloom filter estimated cardinality (NBEC).

37. The method of claim 31, wherein selecting the node for the compaction operation comprises:

collecting sets of kvset metrics for a multiple of nodes comprising the node;

sorting the multiple of nodes based on the sets of kvset metrics; and

selecting a subset of the multiple of nodes based on a sort order from the sorting, the performing the compaction operation on the node comprising performing the compaction operation on each node in the subset of the multiple of nodes, the subset of the multiple of nodes comprising the node.

38. A system comprising:

means for creating a key-value set (kvset) for a node in a key-value set (KVS) tree, the creating comprising computing a set of kvset metrics for the kvset, the node comprising a temporally ordered sequence of 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, the KVS tree having a determinative mapping that provides a rule such that any key-value pair maps a specific path through the KVS tree to a specific child node at any level of the KVS tree without regard to node content;

means for adding the kvset to the temporally ordered sequence of kvsets of the node, the kvset being immutable once added to the temporally ordered sequence of kvsets of the node;

means for selecting the node for a compaction operation based on a metric in the set of kvset metrics; and

means for performing the compaction operation on the node.

39. The system of claim 38, wherein the kvset is created in response to a compaction operation, the compaction operation being at least one of a key compaction, a key-value compaction, a spill compaction, or a hoist compaction.

40. The system of claim 38, further comprising means for modifying node metrics in response to adding the kvset to the node.

41. The system of claim 40, wherein the node metrics comprise a value of a fraction of estimated obsolete key-value pairs in kvsets subject to prior compactions performed on a node group comprising the node.

42. The system of claim 41, wherein the node metrics comprise an estimated number of keys that are the same in the kvset and a different kvset of the node.

43. The system of claim 42, wherein the estimated number of keys are calculated by:

obtaining a first key bloom filter from the kvset;

obtaining a second key bloom filter from the different kvset; and

intersecting the first key bloom filter and the second key bloom filter to produce a node bloom filter estimated cardinality (NBEC).

44. The system of claim 38, wherein the means for selecting the node for the compaction operation comprise:

means for collecting sets of kvset metrics for a multiple of nodes comprising the node;

means for sorting the multiple of nodes based on the sets of kvset metrics; and

means for selecting a subset of the multiple of nodes based on a sort order from the sorting, the performing the compaction operation on the node comprising performing the compaction operation on each node in the subset of the multiple of nodes, the subset of the multiple of nodes comprising the node.