Key-value store tree data block spill with compaction

• US 11,100,071 B2
• Filed: 10/10/2018
• Issued: 08/24/2021
• 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
• Primary Examiner(s): Vital, Pierre M
• Assistant Examiner(s): Ho, Andrew N
• Application Number:
  US16/156,440
• Publication Number:
  US 20200117728A1
• Time in Patent Office: 1,049 Days
• Field of Search: None
• 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 memory sub-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, wherein each key-value set of the node comprises at least one value block, and wherein each individual value block of the node is assigned a data generation number indicating a sequence order at which the individual value block was initially generated for the key-value store tree data structure; 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

in response to determining that the set of child nodes comprises the leaf node, moving the sequence of key-value sets to the set of child nodes, the moving the sequence of key-value sets to the set of child nodes comprising;

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

2. The memory sub-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 the merged key-value set comprising the set of new key blocks that reference the 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 memory sub-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 memory sub-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 memory sub-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 memory sub-system of claim 1, wherein the moving the sequence of key-value sets to the set of child nodes comprises:

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

7. The memory sub-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 memory sub-system of claim 1, 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:

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 memory sub-system of claim 1, wherein the operations further comprise:

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

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

deleting the 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 memory sub-system of claim 1, wherein a host system comprises the processing device, and the memory sub-system comprises the set of memory components.

11. A method comprising:

generating, on a set of memory components of a memory sub-system, 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, wherein each key-value set of the node comprises at least one value block, and wherein each individual value block of the node is assigned a data generation number indicating a sequence order at which the individual value block was initially generated for the key-value store tree data structure;

detecting, by a processing device of the memory sub-system, 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

in response to determining that the set of child nodes comprises the leaf node, moving, by the processing device, the sequence of key-value sets to the set of child nodes, the moving the sequence of key-value sets to the set of child nodes comprising;

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

12. The method of claim 11, 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 the merged key-value set comprising the set of new key blocks that reference the set of existing value blocks of the sequence of key-value sets, and the set of new key blocks being generated based on the 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.

13. The method of claim 12, 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.

14. The method of claim 12, 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.

15. The method of claim 12, 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.

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

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

17. The method of claim 16, 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.

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

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.

19. A non-transitory machine-readable storage medium comprising instructions that, when executed by a processing device of a memory sub-system, cause the processing device to:

access, on a set of memory components of the memory sub-system, 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, wherein each key-value set of the node comprises at least one value block, and wherein each individual value block of the node is assigned a data generation number indicating a sequence order at which the individual value block was initially generated for the key-value store tree data structure;

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

in response to determining that the set of child nodes comprises the leaf node, move the sequence of key-value sets to the set of child nodes, the moving the sequence of key-value sets to the set of child nodes comprising;

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

20. The non-transitory machine-readable storage medium of claim 19, wherein the moving the sequence of key-value sets to the set of child nodes comprises:

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