Compaction of information in tiered data structure

• US 9,626,400 B2
• Filed: 07/21/2014
• Issued: 04/18/2017
• Est. Priority Date: 03/31/2014
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Chander, Ramesh, George, Johann, O'Krafka, Brian W., Krishnan, Manavalan
• Primary Examiner(s): Lewis, Cheryl
• Application Number:
  US14/336,967
• Publication Number:
  US 20150278271A1
• Time in Patent Office: 1,002 Days
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/9027 Trees

Abstract

A computer system detects a request to access a first data object stored in a tiered data structure, that includes internal nodes and leaf nodes, where data objects in the leaf nodes include unique key information and corresponding values, and the first data object is uniquely identified by a first key. In response to detecting the request to access the first data object, the computer system retrieves a leaf node that includes the first data object and identifies the first data object in the leaf node by combining unique key information of the first data object with a key prefix that is stored separately in the leaf node to generate a combined key and determining that the combined key matches the first key that uniquely identifies the first data object. After identifying the first data object, the computer system provides access to the first data object.

Claims

1. A method, performed by a computer system having one or more processors and memory, the method comprising:

detecting a request, received from a requestor, to access a first data object stored in a tiered data structure, the tiered data structure stored in one or more memory devices, wherein;

the tiered data structure includes a plurality of internal nodes and a plurality of leaf nodes;

two or more of the leaf nodes each include multiple data objects, each of the data objects including unique key information and a corresponding value; and

the first data object is uniquely identified by a first key that is specified by the request;

in response to detecting the request to access the first data object;

retrieving a leaf node that includes the first data object; and

identifying the first data object in the leaf node, including;

combining unique key information of the first data object with a key prefix to generate a combined key, wherein the unique key information of the first data object and the key prefix are separated by other information in the leaf node; and

determining that the combined key matches the first key that uniquely identifies the first data object; and

after identifying the first data object, providing access to the first data object to the requestor.

2. The method of claim 1, wherein the key prefix for the first data object is stored as part of a second data object that is stored before the first data object in predefined order in the leaf node.

3. The method of claim 1, wherein the key prefix for the first data object comprises a predefined portion of a key of a distinct second data object in the leaf node.

4. The method of claim 1, wherein the data objects in the leaf node are sorted by key in a predefined key order.

5. The method of claim 1, wherein:

identifying the first data object further includes searching through the leaf node for the first data object by comparing the first key with a plurality of candidate keys for candidate data objects in the leaf node; and

a respective candidate key for a respective candidate data object is generated by combining unique key information for the respective candidate data object with a corresponding key prefix for the respective candidate data object to generate the respective candidate key.

6. The method of claim 1, wherein each respective data object of a plurality of the data objects in the leaf node, including the first data object, includes metadata that identifies a location of a key prefix for a key corresponding to the respective data object.

7. The method of claim 6, wherein:

first metadata for the first data object has a first length; and

second metadata for a second data object in the plurality of data objects has a second length that is different from the first length.

8. The method of claim 6, wherein:

the leaf node includes a fixed length header for each of the plurality of data objects;

for each of the plurality of data objects, the fixed length header includes information identifying a format of metadata included in the data object; and

different data objects in the plurality of data objects have different formats of metadata.

9. The method of claim 1, wherein:

the leaf node, as stored, is compressed; and

the method further comprises, after retrieving the leaf node and prior to identifying the first data object in the leaf node, decompressing the leaf node.

10. The method of claim 1, further comprising:

detecting a request to insert a new data object in the tiered data structure; and

in response to detecting the request to insert the new data object in the tiered data structure;

identifying a respective leaf node, of the plurality of leaf nodes in the tiered data structure, into which the new data object is to be inserted;

identifying a position in the respective leaf node that is after a prior data object in the respective leaf node in a predefined order;

determining a prefix for a key of the new data object based on a comparison between the key of the new data object and a key of the prior data object; and

inserting the new data object into the respective leaf node along with an indication of a location in the leaf node of the determined prefix for the key of the new data object.

11. The method of claim 1, further comprising:

detecting a request to delete a respective data object in the leaf node that is before a subsequent data object in the leaf node, the respective data object having a key; and

in response to detecting the request to delete the respective data object, and in accordance with a determination that the subsequent data object relies on a portion of the key of the respective data object as a key prefix for the subsequent data object, updating the subsequent data object so that metadata of the subsequent data object does not rely on the portion of the key of the respective data object as the key prefix for the subsequent data object.

12. The method of claim 1, further comprising:

detecting a request to update the first data object in the leaf node; and

in response to detecting the request to update the first data object;

updating a value of the first data object, wherein updating the value of the first data object changes a location of the key prefix for the first data object in the leaf node; and

updating the unique key information of the first data object to indicate the change in the location of the key prefix for the first data object.

13. A computer system, comprising:

one or more processors;

memory; and

one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for;

detecting a request, received from a requestor, to access a first data object stored in a tiered data structure, the tiered data structure stored in one or more memory devices, wherein;

the tiered data structure includes a plurality of internal nodes and a plurality of leaf nodes;

two or more of the leaf nodes each include multiple data objects, each of the data objects including unique key information and a corresponding value; and

the first data object is uniquely identified by a first key that is specified by the request;

in response to detecting the request to access the first data object;

retrieving a leaf node that includes the first data object; and

identifying the first data object in the leaf node, including;

combining unique key information of the first data object with a key prefix to generate a combined key, wherein the unique key information of the first data object and the key prefix are separated by other information in the leaf node; and

determining that the combined key matches the first key that uniquely identifies the first data object; and

after identifying the first data object, providing access to the first data object to the requestor.

14. The computer system of claim 13, wherein the key prefix for the first data object is stored as part of a second data object that is stored before the first data object in predefined order in the leaf node.

15. The computer system of claim 13, wherein:

identifying the first data object further includes searching through the leaf node for the first data object by comparing the first key with a plurality of candidate keys for candidate data objects in the leaf node; and

a respective candidate key for a respective candidate data object is generated by combining unique key information for the respective candidate data object with a corresponding key prefix for the respective candidate data object to generate the respective candidate key.

16. The computer system of claim 13, wherein each respective data object of a plurality of the data objects in the leaf node, including the first data object, includes metadata that identifies a location of a key prefix for a key corresponding to the respective data object.

17. The computer system of claim 13, wherein the one or more programs further include instructions for:

detecting a request to insert a new data object in the tiered data structure; and

in response to detecting the request to insert the new data object in the tiered data structure;

identifying a respective leaf node, of the plurality of leaf nodes in the tiered data structure, into which the new data object is to be inserted;

identifying a position in the respective leaf node that is after a prior data object in the respective leaf node in a predefined order;

determining a prefix for a key of the new data object based on a comparison between the key of the new data object and a key of the prior data object; and

inserting the new data object into the respective leaf node along with an indication of a location in the leaf node of the determined prefix for the key of the new data object.

18. The computer system of claim 13, wherein the one or more programs further include instructions for:

detecting a request to delete a respective data object in the leaf node that is before a subsequent data object in the leaf node, the respective data object having a key; and

updating the subsequent data object so that metadata of the subsequent data object does not rely on a portion of the key of the respective data object as a key prefix for the subsequent data object, in response to detecting the request to delete the respective data object, and in accordance with a determination that the subsequent data object relies on the portion of the key of the respective data object as the key prefix for the subsequent data object.

19. The computer system of claim 13, wherein the one or more programs further include instructions for:

detecting a request to update the first data object in the leaf node; and

in response to detecting the request to update the first data object;

updating a value of the first data object, wherein updating the value of the first data object changes a location of the key prefix for the first data object in the leaf node; and

updating the unique key information of the first data object to indicate the change in the location of the key prefix for the first data object.

20. A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions that, when executed by a computer system with one or more processors, cause the computer system to:

detect a request, received from a requestor, to access a first data object stored in a tiered data structure, the tiered data structure stored in one or more memory devices, wherein;

the tiered data structure includes a plurality of internal nodes and a plurality of leaf nodes;

two or more of the leaf nodes each include multiple data objects, each of the data objects including unique key information and a corresponding value; and

the first data object is uniquely identified by a first key that is specified by the request;

in response to detecting the request to access the first data object;

retrieve a leaf node that includes the first data object; and

identify the first data object in the leaf node, including;

combining unique key information of the first data object with a key prefix to generate a combined key, wherein the unique key information of the first data object and the key prefix are separated by other information in the leaf node; and

determining that the combined key matches the first key that uniquely identifies the first data object; and

after identifying the first data object, provide access to the first data object to the requestor.

21. The non-transitory computer readable storage medium of claim 20, wherein:

identifying the first data object further includes searching through the leaf node for the first data object by comparing the first key with a plurality of candidate keys for candidate data objects in the leaf node; and

a respective candidate key for a respective candidate data object is generated by combining unique key information for the respective candidate data object with a corresponding key prefix for the respective candidate data object to generate the respective candidate key.

22. The non-transitory computer readable storage medium of claim 20, wherein each respective data object of a plurality of the data objects in the leaf node, including the first data object, includes metadata that identifies a location of a key prefix for a key corresponding to the respective data object.

23. The non-transitory computer readable storage medium of claim 20, wherein the one or more programs, when executed by the one or more processors, further cause the computer system to:

detect a request to insert a new data object in the tiered data structure; and

in response to detecting the request to insert the new data object in the tiered data structure;

identify a respective leaf node, of the plurality of leaf nodes in the tiered data structure, into which the new data object is to be inserted;

identify a position in the respective leaf node that is after a prior data object in the respective leaf node in a predefined order;

determine a prefix for a key of the new data object based on a comparison between the key of the new data object and a key of the prior data object; and

insert the new data object into the respective leaf node along with an indication of a location in the leaf node of the determined prefix for the key of the new data object.

24. The non-transitory computer readable storage medium of claim 20, wherein the one or more programs, when executed by the one or more processors, further cause the computer system to:

detect a request to delete a respective data object in the leaf node that is before a subsequent data object in the leaf node, the respective data object having a key; and

update the subsequent data object so that metadata of the subsequent data object does not rely on a portion of the key of the respective data object as a key prefix for the subsequent data object, in response to detecting the request to delete the respective data object, and in accordance with a determination that the subsequent data object relies on the portion of the key of the respective data object as the key prefix for the subsequent data object.

25. The non-transitory computer readable storage medium of claim 20, wherein the one or more programs, when executed by the one or more processors, further cause the computer system to:

detect a request to update the first data object in the leaf node; and

in response to detecting the request to update the first data object;

update a value of the first data object, wherein updating the value of the first data object changes a location of the key prefix for the first data object in the leaf node; and

update the unique key information of the first data object to indicate the change in the location of the key prefix for the first data object.