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
First Claim
Patent Images

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.

View all claims

    Thank you for your feedback