Counter-based compaction of key-value store tree data block

• US 10,915,546 B2
• Filed: 10/10/2018
• Issued: 02/09/2021
• Est. Priority Date: 10/10/2018
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Tomlinson, Alexander
• Primary Examiner(s): Corrielus, Jean M
• Application Number:
  US16/156,400
• Publication Number:
  US 20200117744A1
• Time in Patent Office: 853 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 16/258 Data format conversion from or to a database
• 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 merges key-value pair data of a node, in a key-value tree data structure using counter values.

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 each key-value set in the sequence of key-value sets is associated with an individual count value; and

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

accessing, on the set of memory components, the key-value store tree data structure;

detecting whether the sequence of key-value sets comprises a first sub-sequence of key-value sets comprising a predetermined number of key-value sets where each key-value set is associated with a similar count value; and

in response to detecting that the sequence of key-value sets comprises the first sub-sequence of key-value sets;

merging the first sub-sequence of key-value sets to produce a merged key-value set;

associating the merged key-value set with a first new count value, the first new count value being generated based on the similar count value; and

replacing the first sub-sequence of key-value sets, within the sequence of key-value sets, with the merged key-value set to produce an updated sequence of key-value sets.

2. The system of claim 1, wherein generating the first new count value that is generated based on the similar count value comprises setting the first new count value to be equal to the similar count value incremented by a specific value.

3. The system of claim 2, wherein the specific value comprises a value of one.

4. The system of claim 1, wherein the merged key-value set comprises a set of new key blocks that reference a set of existing value blocks of the first sub-sequence of key-value sets, and the set of new key blocks is generated based on a set of existing key blocks of the first sub-sequence of key-value sets.

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

6. The system of claim 1, wherein the merged key-value set comprises a set of new value blocks and a set of new key blocks that reference the set of new value blocks, the set of new value blocks is generated based on a set of existing value blocks of the first sub-sequence of key-value sets, and the set of new key blocks is generated based on a set of existing key blocks of the sequence of key-value sets.

7. The system of claim 6, wherein the set of new value blocks is generated based on the set of value key blocks of the first sub-sequence of key-value sets by copying values of the set of existing value blocks to the set of new value blocks, and the set of new key blocks is generated based on the set of existing key blocks of the first sub-sequence of key-value sets by copying values of the set of existing key blocks to the set of new key blocks.

8. The system of claim 1, wherein the replacing the first sub-sequence of key-value sets, in the sequence of key-value sets, with the merged key-value set to produce the updated sequence of key-value sets comprises:

deleting, from the node, each particular key-value set in the first sub-sequence of key-value sets.

9. The system of claim 1, wherein the replacing the first sub-sequence of key-value sets, in the sequence of key-value sets, with the merged key-value set to produce the updated sequence of key-value sets comprises:

deleting one or more key blocks of each particular key-value set in the first sub-sequence of key-value sets.

10. The system of claim 1, wherein the replacing the first sub-sequence of key-value sets, in the sequence of key-value sets, with the merged key-value set, to produce the updated sequence of key-value sets comprises:

deleting one or more value blocks of each particular key-value set in the first sub-sequence of key-value sets.

11. The system of claim 1, wherein the operations further comprise:

detecting whether a second sub-sequence of key-value sets, in the updated sequence of key-value sets, comprises the predetermined number of key-value sets where each key-value set is associated with a second similar count value;

in response to detecting the second sub-sequence of key-value sets in the updated sequence of key-value sets;

merging the second sub-sequence of key-value sets to produce a second merged key-value set;

associating the second merged key-value set with a second new count value, the second new count value being generated based on the second similar count value; and

replacing the second sub-sequence of key-value sets, within the updated sequence of key-value sets, with the merged key-value set to produce a second updated sequence of key-value sets.

12. The system of claim 1, wherein the first sub-sequence of key-value sets comprises one or more key-value sets within the node.

13. 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, and each key-value set in the sequence of key-value sets is associated with an individual count value;

detecting, by a processing device, whether the sequence of key-value sets comprises a sub-sequence of key-value sets comprising a predetermined number of key-value sets where each key-value set is associated with a similar count value; and

in response to detecting that the sequence of key-value sets comprises the sub-sequence of key-value sets;

merging, by the processing device, the sub-sequence of key-value sets to produce a merged key-value set;

associating, by the processing device, the merged key-value set with a first new count value, the first new count value being generated based on the similar count value; and

replacing, by the processing device, the sub-sequence of key-value sets, within the sequence of key-value sets, with the merged key-value set to produce an updated sequence of key-value sets.

14. The method of claim 13, wherein generating the first new count value that is generated based on the similar count value comprises setting the first new count value to be equal to the similar count value incremented by a specific value.

15. The method of claim 14, wherein the specific value comprises a value of one.

16. The method of claim 13, wherein the sub-sequence of the key-value sets comprises a last key-value set in the sequence of key-value sets.

17. The method of claim 13, further comprising:

updating the node by appending a new key-value set to the sequence of the key-value sets; and

associating the new key-value set with an initial count value.

18. The method of claim 13, further comprising:

detecting whether an update to the node results in a new key-value set being appended to the sequence of key-value sets; and

in response to detecting the update to the node, associating the new key-value set with an initial count value.

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

generate, on a set of memory components, an index data structure comprising an index to store a sequence of sub-indexes, each sub-index in the sequence storing a set of key-value pairs;

update the index by appending a new sub-index to the sequence of sub-indexes, the new sub-index comprising a new set of key-value-pairs;

associate the new sub-index with an initial count value;

detecting whether the sequence of sub-indexes comprises a sub-sequence of sub-indexes comprising a predetermined number of sub-indexes where each sub-index is associated with a similar count value;

in response to detecting that the sequence of sub-indexes comprises the sub-sequence of sub-indexes;

merging the sub-sequence of sub-indexes to produce a merged sub-index;

associating the merged sub-index with a first new count value, the first new count value being generated based on the similar count value; and

replacing the sub-sequence of sub-indexes, within the sequence of sub-indexes, with the merged sub-index set to produce an updated sequence of sub-indexes.

20. The non-transitory machine-readable storage medium of claim 19, wherein the index data structure comprises a key-value store tree data, structure, and each sub-index in the sequence comprises a key-value set comprising a set of key blocks for storing one or more keys of the set of key-value pairs and a set of value blocks for storing one or more values of the set of key-value pairs.