KVS tree

• US 10,725,988 B2
• Filed: 02/09/2017
• Issued: 07/28/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,877
• Publication Number:
  US 20180225315A1
• Time in Patent Office: 1,265 Days
• Field of Search: 707693
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2455 Query execution

Abstract

A KVS tree and operations thereon are described herein. A key-value set (kvset) is received to store in a key-value data structure on at least one machine readable medium. The kvset includes a mapping of unique keys to values with the keys and the values of the kvset being immutable. The key-value data structure is organized as a tree with nodes of the tree including a temporally ordered sequence of kvsets. The kvset, once received, is written to a sequence of kvsets of a root-node of the tree.

Claims

1. A key-value data structure, organized as a tree, on at least one non-transitory machine readable medium, the key-value data structure comprising:

a multiple of nodes, a node from the multiple of nodes comprising;

a temporally ordered sequence of immutable 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; and

a determinative mapping for a key-value pair, in a kvset of the temporally ordered sequence of immutable key-value sets, to any one child node of the node, the key-value pair comprising one key and one value, the one key being unique in the kvset, the kvset holding storing multiple key-value pairs, the determinative mapping providing a rule such that any key-value pair maps to a specific path through the tree to a specific child node at any level of the tree without regard to node content of the tree.

2. The key-value data structure of claim 1, wherein the determinative mapping comprises a portion of a hash of a portion of a key.

3. The key-value data structure of claim 2, wherein the hash comprises a multiple of non-overlapping portions comprising the portion of the hash.

4. The key-value data structure of claim 3, wherein each of the multiple of non-overlapping portions corresponds to a level of the tree.

5. The key-value data structure of claim 4, wherein the portion of the hash is determined from the multiple of non-overlapping portions by a level of the node.

6. The key-value data structure of claim 5, wherein a maximum number of child nodes for the node is defined by a size of the portion of the hash.

7. The key-value data structure of claim 1, wherein the kvset comprises a key-tree to store key entries of key-value pairs of the kvset.

8. The key-value data structure of claim 1, wherein key entries of the kvset are stored in a set of key-blocks comprising a primary key-block and zero or more extension key-blocks, members of the set of key-blocks corresponding to media blocks for a storage medium, each key-block comprising a header to identify it as a key-block;

and

wherein values are stored in a set of value-blocks, members of the set of value-blocks corresponding to media blocks for the storage medium, each value-block comprising a header to identify it as a value-block.

9. The key-value data structure of claim 8, wherein a value-block comprises storage section to one or more values without separation between values.

10. The key-value data structure of claim 8, wherein the primary key-block comprises a list of media block identifications for the one or more extension key-blocks of the kvset.

11. The key-value data structure of claim 8, wherein the primary key-block comprises a list of media block identifications for value-blocks in the set of value-blocks.

12. The key-value data structure of claim 8, wherein the primary key-block comprises a copy of a lowest key in a key-tree of the kvset, the lowest key determined by a pre-set sort-order of the tree.

13. The key-value data structure of claim 8, wherein the primary key-block comprises a copy of a highest key in a key-tree of the kvset, the highest key, determined by a pre-set sort-order of the tree.

14. The key-value data structure of claim 8, wherein the primary key-block comprises a header to a key-tree of the kvset.

15. The key-value data structure of claim 8, wherein the primary key-block comprises a list of media block identifications for a key-tree of the kvset.

16. The key-value data structure of claim 8, wherein the primary key-block comprises a bloom filter header for a bloom filter of the kvset.

17. The key-value data structure of claim 8, wherein the primary key-block comprises a list of media block identifications for a bloom filter of the kvset.

18. The key-value data structure of claim 8, wherein the primary key-block comprises a set of metrics for the kvset.

19. A system comprising processing circuitry to:

receive a key-value set (kvset) to store in a key-value data structure, organized as a tree on at least one non-transitory machine readable medium, the kvset comprising a mapping of unique keys to values, the keys and the values of the kvset being immutable, a node of the tree comprising;

a temporally ordered sequence of kvsets with key-value pairs with keys that determinatively map to the nodes, 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

a determinative mapping for a key-value pair, in a kvset of the temporally ordered sequence of immutable key-value sets, to any one child node of the node, the key-value pair comprising one key and one value, the one key being unique in the kvset, the kvset storing multiple key-value pairs, the determinative mapping providing a rule such that any key-value pair maps to a specific path through the tree to a specific child node at any level of the tree without regard to node content of the tree; and

write the kvset to a sequence of kvsets of a root-node of the tree.

20. The system of claim 19, wherein the processing circuitry is configured to:

receive a search request comprising a search key;

traverse the tree until at least one of the entire tree is traversed or a first instance of the search key is found in a kvset of a node of the tree, to traverse the tree comprising the processing circuitry is further configured to;

begin at a root-node of the tree; and

for each node being traversed;

examine kvsets of the node from newest kvset to oldest kvset return a found indication and cease the traversal when the search key is found; and

continue the traversal to a child node when the search key is not found, the child node existing and identified by a spill value derived from the search key and a tree-level of the node being traversed.

21. The system of claim 20, wherein to examine the kvsets comprises, for a given kvset, the processing circuitry to use a bloom filter of the kvset to determine whether the search key might be in the kvset.

22. The system of claim 20, wherein to examine the kvsets comprises, for a given kvset, the processing circuitry to determine that the search key is less than or equal to a maximum key value of the kvset.

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

receiving a key-value set (kvset) to store in a key-value data structure, organized as a tree, of at least one machine readable medium, the kvset comprising a mapping of unique keys to values, the keys and the values of the kvset being immutable, a node of the tree comprising;

a temporally ordered sequence of kvsets with key-value pairs with keys that determinatively map to the nodes, 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

a determinative mapping for a key-value pair, in a kvset of the temporally ordered sequence of immutable key-value sets, to any one child node of the node, the key-value pair comprising one key and one value, the one key being unique in the kvset, the kvset storing multiple key-value pairs, the determinative mapping providing a rule such that any key-value pair maps to a specific path through the tree to a specific child node at any level of the tree without regard to node content of the tree; and

writing the kvset to a sequence of kvsets of a root-node of the tree.

24. The at least one machine readable medium of claim 23, wherein the operations comprise:

receiving a key and a corresponding value to store in the key-value data structure;

placing the key and the value in a preliminary kvset, the preliminary kvset being mutable; and

writing the kvset to the key-value data structure when a metric is reached.

25. The at least one machine readable medium of claim 23, wherein the operations comprise:

receiving a second kvset;

writing the second kvset to the sequence of kvsets for the root-node; and

performing a spill operation on the root node in response to a metric of the root-node exceeding a threshold in response to writing the second kvset.

26. The at least one machine readable medium of claim 25, wherein the spill operation comprises:

selecting a subset of the sequence of kvsets, the subset comprising contiguous kvsets comprising an oldest kvset;

calculating a child-mapping for each key in each kvset of the subset of kvsets, the child mapping being the determinative mapping from a parent node to a child node based on a particular key and a tree-level of the parent node;

collecting keys and corresponding values into kvsets based on the child-mapping with each kvset set mapped to exactly one child node;

writing the kvsets to a newest position in respective sequences of kvsets in respective child nodes; and

removing the subset of kvsets from the root node.

27. The at least one machine readable medium of claim 26, wherein calculating the child-mapping comprises:

extracting a portion of a key;

deriving a spill value from the portion of the key; and

returning a portion of the spill value based on the tree-level of the parent node.

28. The at least one machine readable medium of claim 27, wherein deriving the spill value from the portion of the key comprises performing a hash of the portion of the key.

29. The at least one machine readable medium of claim 25, wherein the operations comprise performing a second spill operation on a child node in response to a metric of the child node exceeding a threshold after operation of the spill operation.

30. The at least one machine readable medium of claim 23, wherein the operations comprise compacting a node of the tree.

31. The at least one machine readable medium of claim 30, wherein compacting the node comprises performing a key compaction, the key compaction comprising:

selecting a subset of kvsets from a sequence of kvsets for the node, the subset of kvsets comprising contiguous kvsets

locating a set of collision keys, members of the set of collision keys comprising key entries in at least two kvsets in the sequence of kvsets for the node;

adding a most recent key entry for each member of the set of collision keys to a new kvset;

adding entries for each key in members of the subset of kvsets that are not in the set of collision keys to the new kvset; and

replacing the subset of kvsets with the new kvset by writing the new kvset to the node and removing the subset of kvsets.

32. The at least one machine readable medium of claim 30, wherein the node includes a child node, wherein compacting the node causes a metric to drop below a threshold, and wherein the operations comprise performing a hoist compaction on the child node in response to the metric dropping below the threshold.

33. The at least one machine readable medium of claim 23, wherein the operations comprise:

receiving a search request comprising a search key;

traversing the tree until at least one of the entire tree is traversed or a first instance of the search key is found in a kvset of a node of the tree, traversing the tree comprising;

beginning at a root-node of the tree; and

for each node being traversed;

examining kvsets of the node from newest kvset to oldest kvset

returning a found indication and cease the traversal when the search key is found; and

continuing the traversal to a child node when the search key is not found, the child node existing and identified by a spill value derived from the search key and a tree-level of the node being traversed.

34. The at least one machine readable medium of claim 23, wherein the operations comprise:

receiving a scan request comprising a key criterion;

collecting keys specified by the key criterion from each kvset of a node set from the tree into a found set;

reducing the found set to a result set by keeping key-value pairs that correspond to a most recent entry for a key that is not a tombstone; and

returning the result set.

35. A method comprising:

receiving a key-value set (kvset) to store in a key-value data structure, organized as a tree on at least one non-transitory machine readable medium, the kvset comprising a mapping of unique keys to values, the keys and the values of the kvset being immutable, a node of the tree comprising;

a temporally ordered sequence of kvsets with key-value pairs with keys that determinatively map to the nodes, 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

a determinative mapping for a key-value pair, in a kvset of the temporally ordered sequence of immutable key-value sets, to any one child node of the node, the key-value pair comprising one key and one value, the one key being unique in the kvset, the kvset storing multiple key-value pairs, the determinative mapping providing a rule such that the key-value pair maps to a specific path through the tree to a specific child node at any level of the tree without regard to node content of the tree; and

writing the kvset to a sequence of kvsets of a root-node of the tree.

36. The method of claim 35, further comprising compacting a node of the tree.

37. The method of claim 36, wherein compacting the node comprises performing a key compaction, the key compaction comprising:

selecting a subset of kvsets from a sequence of kvsets for the node, the subset of kvsets comprising contiguous kvsets;

locating a set of collision keys, members of the set of collision keys comprising key entries in at least two kvsets in the sequence of kvsets for the node;

adding a most recent key entry for each member of the set of collision keys to a new kvset;

adding entries for each key in members of the subset of kvsets that are not in the set of collision keys to the new kvset; and

replacing the subset of kvsets with the new kvset by writing the new kvset to the node and removing the subset of kvsets.

38. The method of claim 37, wherein the node has no children, wherein the subset of kvsets comprises the oldest kvset, and wherein writing the most recent key entry for each member of the set of collision keys to the new kvset and writing entries for each key in members of the subset of kvsets that are not in the set of collision keys to the new kvset comprises omitting any key entries that comprise a tombstone.

39. The method of claim 37, wherein the node has no children, wherein the subset of kvsets comprises the oldest kvset, and wherein writing the most recent key entry for each member of the set of collision keys to the new kvset and writing entries for each key in members of the subset of kvsets that are not in the set of collision keys to the new kvset comprises omitting any key entries that are expired.

40. The method of claim 37, wherein compacting the node comprises performing a value compaction, wherein keys and values in a kvset are stored in separate addressable blocks, and wherein the value compaction comprises copying values references in key entries for the new kvset to new blocks and deleting blocks corresponding to the subset of kvsets.

41. The method of claim 36, wherein the node comprises a child node, wherein compacting the node causes a metric to drop below a threshold, and comprising performing a hoist compaction on the child node in response to the metric dropping below the threshold.

42. The method of claim 41, wherein the hoist compaction include comprises:

performing a key and value compaction on the child node to produce a new kvset without writing the new kvset to the child node; and

writing the new kvset to the node in an oldest position for a sequence of kvsets of the node.

43. A system comprising:

means for receiving a key-value set (kvset) to store in a key-value data structure, organized as a tree on at least one non-transitory machine readable medium, the kvset comprising a mapping of unique keys to values, the keys and the values of the kvset being immutable, a node of the tree comprising;

a temporally ordered sequence of kvsets with key-value pairs with keys that determinatively map to the nodes, 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

a determinative mapping for a key-value pair in a kvset of the temporally ordered sequence of immutable key-value sets, to any one child node of the node, the key-value pair comprising one key and one value, the one key being unique in the kvset, the kvset storing multiple key-value pairs, the determinative mapping providing a rule such that any key-value pair maps to a specific path through the tree to a specific child node at any level of the tree without regard to node content of the tree; and

means for writing the kvset to a sequence of kvsets of a root-node of the tree.

44. The system of claim 43, further comprising:

means for receiving a second kvset;

means for writing the second kvset to the sequence of kvsets for the root-node; and

means for performing a spill operation on the root node in response to a metric of the root-node exceeding a threshold in response to writing the second kvset.

45. The system of claim 44, wherein the spill operation comprises:

means for selecting a subset of the sequence of kvsets, the subset comprising contiguous kvsets comprising an oldest kvset;

means for calculating a child-mapping for each key in each kvset of the subset of kvsets, the child mapping being determinative mapping from a parent node to a child node based on a particular key and a tree-level of the parent node;

means for collecting keys and corresponding values into kvsets based on the child-mapping with each kvset set mapped to exactly one child node;

means for writing the kvsets to a newest position in respective sequences of kvsets in respective child nodes; and

means for removing the subset of kvsets from the root node.