KEY-VALUE STORE TREE DATA BLOCK SPILL WITH COMPACTION

• US 20200117728A1
• Filed: 10/10/2018
• Published: 04/16/2020
• Est. Priority Date: 10/10/2018
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Tomlinson, Alexander, Becker, Greg A., Ramdasi, Gaurav Sanjay
• Granted Patent: US 11,100,071 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 2207/222 Binary data tree
• CPC Class Codes: G06F 7/14 Merging, i.e. combining at least two sets of record carriers each arranged in the same ordered sequence to produce a single set having the same ordered sequence

Abstract

Aspects of the present disclosure provide for operations of a key-value tree data structure that: merge key-value sets within a given node by merging and rewriting key blocks of the key-value sets while rewriting or deferring rewrite of value blocks of the merged key-value sets based on whether one or more child nodes of the given node comprise a leaf node; and move one or more portions of the merged key-value set into one or more child nodes of the given node.

Claims

1. A system comprising:

a set of memory components storing a key-value store tree data structure, the key-value store tree data structure comprising a set of nodes, wherein a node in the set of nodes comprises a sequence of key value sets; and

a processing device, operatively coupled to the set of memory components, configured to perform operations comprising;

detecting for a condition to merge and move the sequence of key-value sets from the node of the key-value store tree data structure to a set of child nodes of the node; and

in response to detecting the condition;

determining whether the set of child nodes of the node comprises a leaf node; and

moving the sequence of key-value sets to the set of child nodes based on the determining whether the set of child nodes comprises the leaf node.

2. The system of claim 1, wherein the moving the sequence of key-value sets to the set of child nodes comprises:

in response to determining that the set of child nodes does not comprise the leaf node;

merging the sequence of key-value sets to produce a merged key-value set comprising a set of new key blocks that reference a set of existing value blocks of the sequence of key-value sets, and the set of new key blocks being generated based on a set of existing key blocks of the sequence of key-value sets; and

moving the merged key-value set into the set of child nodes of the node.

3. The system of claim 2, wherein the moving the merged key-value set into the set of child nodes of the node comprises:

partitioning the merged key-value set into a set of split key-value sets, each split key-value set being assigned to a different child node in the set of child nodes; and

moving each split key-value set, in the set of split key-value sets, to an assigned child node in the set of child nodes.

4. The system of claim 2, wherein the merging the sequence of key-value sets to produce the merged key-value set comprises, after the merged key-value is generated:

in response to determining that the set of child nodes does not comprise the leaf node, deleting, from the node, each particular key-value set in the sequence of key-value sets, the deleting the particular key-value set comprising deleting one or more key blocks of the particular key-value set while leaving one or more value blocks of the particular key-value set.

5. The system of claim 2, wherein the set of new key blocks is generated based on the set of existing key blocks of the sequence of key-value sets by copying the set of existing key blocks such that the set of new key blocks comprises one or more references to the set of existing value blocks.

6. The system of claim 1, wherein each particular value block in the set of value blocks of the node is assigned a data generation number indicating a sequence order at which the particular value block was initially generated for the key-value store tree structure, and the moving the sequence of key-value sets to the set of child nodes comprises:

in response to determining that the set of child nodes comprises the leaf node;

merging the sequence of key-value sets to produce a merged key-value set comprising a set of new key blocks that reference a set of new value blocks, the set of new key blocks being generated based on a set of existing key blocks of the sequence of key-value sets, the set of new value blocks being generated based on a set of existing value blocks of the sequence of key-value sets, and the set of new value blocks being assigned a particular largest data generation number assigned to any value block in the set of existing value blocks; and

moving the merged key-value set into the set of child nodes of the node.

7. The system of claim 6, wherein the moving the merged key-value set into the set of child nodes of the node comprises:

partitioning the merged key-value set into a set of split key-value sets, each split key-value set being assigned to a different child node in the set of child nodes; and

moving each split key-value set, in the set of split key-value sets, to an assigned child node in the set of child nodes.

8. The system of claim 6, wherein the merging the sequence of key-value sets to produce the merged key-value set comprises, after the merged key-value set is generated:

in response to determining that the set of child nodes does comprise the leaf node;

determining a set of largest data generation numbers by determining, for each particular leaf node of the key-value store tree data structure, a largest data generation number assigned to any value block associated with the particular leaf node;

determining a smallest data generation number in the set of largest data generation numbers; and

deleting, from the node, each particular key-value set in the sequence of key-value sets, the deleting the particular key-value set comprising;

deleting any existing value block, referenced by an existing key block of the particular key-value set, that has a particular data generation number that is less than the smallest data generation number; and

deleting one or more existing key blocks of the particular key-value set.

9. The system of claim 1, wherein each particular value block in the set of value blocks of the node is assigned a data generation number indicating a sequence order at which the particular value block was initially generated for the key-value store tree structure, and the operations further comprise:

determining a smallest data generation number in the set of largest data generation numbers;

determining whether a particular data generation number of the given value block is less than the smallest data generation number; and

deleting a given value block of the key-value store tree data structure in response to determining that the particular data generation number is less than the smallest data generation number.

10. The system of claim 1, wherein the system is a memory sub-system.

11. The system of claim 1, wherein a host system comprises the processing device, and a memory sub-system comprises the set of memory components.

12. A method comprising:

generating, on a set of memory components, a key-value store tree data structure, the key-value store tree data structure comprising a set of nodes, wherein a node in the set of nodes comprises a sequence of key value sets;

detecting, by a processing device, for a condition to merge and move the sequence of key-value sets from the node to a set of child nodes of the node; and

in response to detecting the condition;

determining, by the processing device, whether the set of child nodes of the node comprises a leaf node; and

moving, by the processing device, the sequence of key-value sets to the set of child nodes based on the determining whether the set of child nodes comprises the leaf node.

13. The method of claim 12, wherein the moving the sequence of key-value sets to the set of child nodes comprises:

in response to determining that the set of child nodes does not comprise the leaf node;

merging the sequence of key-value sets to produce a merged key-value set comprising a set of new key blocks that reference a set of existing value blocks of the sequence of key-value sets, and the set of new key blocks being generated based on a set of existing key blocks of the sequence of key-value sets; and

moving the merged key-value set into the set of child nodes of the node.

14. The method of claim 13, wherein the moving the merged key-value set into the set of child nodes of the node comprises:

partitioning the merged key-value set into a set of split key-value sets, each split key-value set being assigned to a different child node in the set of child nodes; and

moving each split key-value set, in the set of split key-value sets, to an assigned child node in the set of child nodes.

15. The method of claim 13, wherein the merging the sequence of key-value sets to produce the merged key-value set comprises, after the merged key-value set is generated:

in response to determining that the set of child nodes does not comprise the leaf node, deleting, from the node, each particular key-value set in the sequence of key-value sets, the deleting the particular key-value set comprising deleting one or more key blocks of the particular key-value set while leaving one or more value blocks of the particular key-value set.

16. The method of claim 13, wherein the set of new key blocks is generated based on the set of existing key blocks of the sequence of key-value sets by copying the set of existing key blocks such that the set of new key blocks comprises one or more references to the set of existing value blocks.

17. The method of claim 12, wherein each particular value block in the set of value blocks of node is assigned a data generation number indicating a sequence order at which the particular value block was initially generated for the key-value store tree structure, and the moving the sequence of key-value sets to the set of child nodes comprises:

in response to determining that the set of child nodes comprises the leaf node;

merging the sequence of key-value sets to produce a merged key-value set comprising a set of new key blocks that reference a set of new value blocks, the set of new key blocks being generated based on a set of existing key blocks of the sequence of key-value sets, the set of new value blocks being generated based on a set of existing value blocks of the sequence of key-value sets, and the set of new value blocks being assigned a particular largest data generation number assigned to any value block in the set of existing value blocks; and

moving the merged key-value set into the set of child nodes of the node.

18. The method of claim 17, wherein the moving the merged key-value set into the set of child nodes of the node comprises:

partitioning the merged key-value set into a set of split key-value sets, each split key-value set being assigned to a different child node in the set of child nodes; and

moving each split key-value set, in the set of split key-value sets, to an assigned child node in the set of child nodes.

19. The method of claim 17, wherein the merging the sequence of key-value sets to produce the merged key-value set comprises, after the merged key-value is generated:

in response to determining that the set of child nodes does comprise the leaf node;

determining a set of largest data generation numbers by determining, for each particular leaf node of the key-value store tree data structure, a largest data generation number assigned to any value block associated with the particular leaf node;

determining a smallest data generation number in the set of largest data generation numbers; and

deleting, from the node, each particular key-value set in the sequence of key-value sets, the deleting the particular key-value set comprising;

deleting any existing value block, referenced by an existing key block of the particular key-value set, that has a particular data generation number that is less than the smallest data generation number; and

deleting one or more existing key blocks of the particular key-value set.

20. A non-transitory machine-readable storage medium comprising instructions that, when executed by a processing device, cause the processing device to:

access, on a set of memory components, a key-value store tree data structure, the key-value store tree data structure comprising a set of nodes, wherein a node in the set of nodes comprises a sequence of key value sets;

detect for a condition to merge and move the sequence of key-value sets from the node to a set of child nodes of the node; and

in response to detecting the condition;

determine whether the set of child nodes of the node comprises a leaf node; and

move the sequence of key-value sets to the set of child nodes based on the determining whether the set of child nodes comprises the leaf node.