Merge tree garbage metrics

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.

What is claimed is: 
     
         1 . A system comprising processing circuitry configured to perform operations comprising:
 generating a key-value set (kvset) for a node in a key-value set tree, the generation of the kvset comprising computation of a set of kvset metrics for the kvset, the node comprising a temporally ordered sequence of kvsets, and 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;   adding the kvset 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 generating the kvset is performed in response to execution of a compaction operation, the compaction operation comprising at least one of a key compaction, a key-value compaction, a spill compaction, or a hoist compaction. 
     
     
         3 . The system of  claim 1 , wherein the generating the kvset is performed in response to execution of a compaction operation, the compaction operation comprising 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 1 , wherein the set of kvset metrics comprises an estimate of obsolete key-value pairs in the kvset, the estimate of obsolete key-value pairs being calculated by summing a number of key entries from pre-compaction kvsets that were not included in the kvset. 
     
     
         5 . The system of  claim 1 , wherein the set of kvset metrics comprises an estimated storage size of obsolete key-value pairs in the kvset, the estimated storage size of obsolete key-value pairs being calculated by summing storage sizes of key entries and corresponding values from pre-compaction kvsets that were not included in the kvset. 
     
     
         6 . The system of  claim 1 , wherein the set of kvset metrics comprises an estimated storage size of valid key-value pairs in the kyset, the estimated storage size of valid key-value pairs being calculated by summing 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 operations further comprise modifying 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 the operations further comprise:
 calculating the estimated number of keys by:
 obtaining a first key bloom filter from the kvset; 
 obtaining a second key bloom filter from the different kyset; and 
 intersecting 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 1 , wherein the selecting the node for the compaction operation based on the metric in the set of kvset metrics 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, and the subset of the multiple of nodes comprising the node.   
     
     
         14 . The system of  claim 13 , wherein a cardinality of the subset of the multiple of nodes is set by a performance value. 
     
     
         15 . At least one non-transitory machine readable medium comprising instructions that, when executed by a machine, cause the machine to perform operations comprising:
 generating a key-value set (kvset) for a node in a key-value set tree, the generation of the kvset comprising computation of a set of kvset metrics for the kvset, the node comprising a temporally ordered sequence of kvsets, and 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;   adding the kvset 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.   
     
     
         16 . The at least one non-transitory machine readable medium of  claim 15 , wherein the generating the kvset is performed in response to execution of a compaction operation, the compaction operation comprising at least one of a key compaction, a key-value compaction, a spill compaction, or a hoist compaction. 
     
     
         17 . The at least one non-transitory machine readable medium of  claim 15 , wherein the generating the kvset is performed in response to execution of a compaction operation, the compaction operation comprising a key compaction, and the set of kvset metrics comprising metrics of unreferenced values in the kvset as a result of the key compaction. 
     
     
         18 . The at least one non-transitory machine readable medium of  claim 15 , wherein the operations further comprise modifying node metrics in response to adding the kvset to the node. 
     
     
         19 . The at least one non-transitory machine readable medium of  claim 18 , 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. 
     
     
         20 . A method comprising:
 generating, by processing circuitry, a key-value set (kvset) for a node in a key-value set tree, the generation of the kvset comprising computation of a set of kvset metrics for the kvset, the node comprising a temporally ordered sequence of kvsets, and 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;   adding, by the processing circuitry, the kvset to the temporally ordered sequence of kvsets of the node;   selecting, by the processing circuitry, the node for a compaction operation based on a metric in the set of kvset metrics; and   performing, by the processing circuitry, the compaction operation on the node.