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

Patent metadata

Field	Value
Publication number	US-10915546-B2
Application number	US-201816156400-A
Country	US
Kind code	B2
Filing date	Oct 10, 2018
Priority date	Oct 10, 2018
Publication date	Feb 9, 2021
Grant date	Feb 9, 2021

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.

First claim

What is claimed is:

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

Assignees

• Micron Technology Inc

Inventors

• Tomlinson Alexander

Classifications

• H04L9/08

  Key distribution {or management, e.g. generation, sharing or updating, of cryptographic keys or passwords (network architectures or network communication protocols for supporting key management in a packet data network H04L63/06)} · CPC title

• G06F21/78

  to assure secure storage of data (address-based protection against unauthorised use of memory G06F12/14; record carriers for use with machines and with at least a part designed to carry digital markings G06K19/00) · CPC title

• G06F21/71 Primary

  to assure secure computing or processing of information · CPC title

• G06F21/62

  Protecting access to data via a platform, e.g. using keys or access control rules · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title