MERGE TREE GARBAGE METRICS

• US 20180225321A1
• Filed: 02/09/2017
• Published: 08/09/2018
• 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
• Granted Patent: US 10,706,105 B2
• Time in Patent Office: Days
• 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:

create a kvset for a node in a KVS tree, the creating including computing a set of kvset metrics for the kvset;

add the kvset to the node;

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

perform 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 wherein the set of kvset metrics include 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 include 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 include 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 include 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 the node metrics in response to adding the kvset to the node.

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

9. The system of claim 8, wherein the node metrics include 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 include 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 include 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 including 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 including 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 machine readable medium including instructions that, when executed by a machine, cause the machine to perform operations comprising:

creating a kvset for a node in a KVS tree, the creating including computing a set of kvset metrics for the kvset;

adding the kvset to 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 wherein the set of kvset metrics include 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 include 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 include 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 include 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 include a value of a fraction of estimated obsolete key-value pairs in kvsets subject to prior compactions performed on a node group including the node.

24. The at least one machine readable medium of claim 23, wherein the node metrics include 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 include 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 include 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 includes:

collecting sets of kvset metrics for a multiple of nodes including 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, wherein performing the compaction operation on the node includes performing the compaction operation on each node in the subset of the multiple of nodes, the subset of the multiple of nodes including 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 kvset for a node in a KVS tree, the creating including computing a set of kvset metrics for the kvset;

adding the kvset to 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, comprising modifying node metrics in response to adding the kvset to the node.

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

35. The method of claim 34, wherein the node metrics include 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 includes:

collecting sets of kvset metrics for a multiple of nodes including 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, wherein performing the compaction operation on the node includes performing the compaction operation on each node in the subset of the multiple of nodes, the subset of the multiple of nodes including the node.

38. A system comprising:

means for creating a kvset for a node in a KVS tree, the creating including computing a set of kvset metrics for the kvset;

means for adding the kvset to 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, 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 include a value of a fraction of estimated obsolete key-value pairs in kvsets subject to prior compactions performed on a node group including the node.

42. The system of claim 41, wherein the node metrics include 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 include:

means for collecting sets of kvset metrics for a multiple of nodes including 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, wherein performing the compaction operation on the node includes performing the compaction operation on each node in the subset of the multiple of nodes, the subset of the multiple of nodes including the node.