Merge tree modifications for maintenance operations

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.

What is claimed is: 
     
         1 . A system comprising processing circuitry configured to perform operations comprising:
 receiving a request for a key-value set tree, the key-value set tree being a data structure comprising nodes, a node of the key-value set 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;   receiving, separate from the request, a parameter set for the key-value set tree; and   executing the request on the key-value set tree by performing an operation of the key-value set 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 comprising a member that defines the tombstone as a prefix-tombstone, and the executing the request on the key-value set tree comprising writing the prefix-tombstone to a kvset of the key-value set tree. 
     
     
         3 . The system of  claim 1 , wherein the request comprises a key, the parameter set comprising a member that specifies tombstone acceleration; and the executing the request on the key-value set tree comprising writing a tombstone in at least one child node identified by performing a spill function on the key. 
     
     
         4 . The system of  claim 3 , wherein the tombstone is written to all extant child nodes identified 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 key-value set tree corresponding to the key, the parameter set comprising a member that specifies garbage collection statistics storage, and the executing the request on the key-value set tree comprising storing the key and the storage size in a data structure for the key-value set tree. 
     
     
         6 . The system of  claim 1 , wherein the parameter set comprises a member that specifies that the key-value set tree is immutable, and the executing the request on the key-value set tree comprising writing the request to a root node of the key-value set tree. 
     
     
         7 . The system of  claim 6 , wherein the key-value set tree uses key compaction exclusively when the key-value set tree is immutable. 
     
     
         8 . The system of  claim 7 , wherein the operations further comprise:
 storing key search statistics in response to the key-value set tree being immutable; and   performing key compaction in response to the key search statistics meeting a threshold.   
     
     
         9 . The system of  claim 8 , wherein the operations further 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.   
     
     
         10 . The system of  claim 6 , wherein the parameter set comprises a second member that specifies that elements are removed from the key-value set tree on a first-in-first-out basis, the parameter set comprises a third member that specifies that a retention constraint of the key-value set tree, the key-value set tree performing key compactions on kvsets based on the retention constraint, and the key-value set 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 a request for a key-value set tree, the key-value set tree being a data structure comprising nodes, a node of the key-value set 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;   receiving, separate from the request, a parameter set for the key-value set tree; and   executing the request on the key-value set tree by performing an operation of the key-value set tree as modified in accordance with the parameter set.   
     
     
         12 . The at least one non-transitory machine readable medium of  claim 11 , wherein the request comprises a key prefix and a tombstone, the parameter set comprising a member that defines the tombstone as a prefix-tombstone, and the executing the request on the key-value set tree comprising writing the prefix-tombstone to a kvset of the key-value set tree. 
     
     
         13 . The at least one non-transitory 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 key-value set tree comprising writing a tombstone in at least one child node identified by performing a spill function on the key. 
     
     
         14 . The at least one non-transitory machine readable medium of  claim 11 , wherein the request comprises a key, tombstone, and a storage size of a value in the key-value set tree corresponding to the key, the parameter set comprising a member that specifies garbage collection statistics storage, and the executing the request on the key-value set tree comprising storing the key and the storage size in a data structure for the key-value set tree. 
     
     
         15 . The at least one non-transitory machine readable medium of  claim 11 , wherein the parameter set comprises a member that specifies that the key-value set tree is immutable, and the executing the request on the key-value set tree comprising writing the request to a root node of the key-value set tree. 
     
     
         16 . The at least one non-transitory machine readable medium of  claim 15 , wherein the key-value set tree uses key compaction exclusively when the key-value set tree is immutable. 
     
     
         17 . The at least one non-transitory machine readable medium of  claim 16 , wherein the operations further comprise:
 storing key search statistics in response to the key-value set tree being immutable; and   performing key compaction in response to the key search statistics meeting a threshold.   
     
     
         18 . The at least one non-transitory machine readable medium of  claim 17 , wherein the operations further 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.   
     
     
         19 . The at least one non-transitory machine readable medium of  claim 15 , wherein the parameter set comprises a second member that specifies that elements are removed from the key-value set tree on a first-in-first-out basis, the parameter set comprises a third member that specifies that a retention constraint of the key-value set tree, the key-value set tree performing key compactions on kvsets based on the retention constraint, and the key-value set tree removing an oldest kvset when the retention constraint is violated. 
     
     
         20 . A method comprising:
 receiving, by processing circuitry, a request for a key-value set tree, the key-value set tree being a data structure comprising nodes, a node of the key-value set 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;   receiving, by the processing circuitry, a parameter set for the key-value set tree, the parameter set being received separately from the request; and   executing, by the processing circuitry, the request on the key-value set tree by performing an operation of the key-value set tree as modified in accordance with the parameter set.