Compaction of information in tiered data structure

Patent metadata

Field	Value
Publication number	US-9626400-B2
Application number	US-201414336967-A
Country	US
Kind code	B2
Filing date	Jul 21, 2014
Priority date	Mar 31, 2014
Publication date	Apr 18, 2017
Grant date	Apr 18, 2017

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.

First claim

What is claimed is:

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 respect

Assignees

• Sandisk Entpr Ip Llc
• Sandisk Technologies Llc

Inventors

• Chander Ramesh
• George Johann
• O'Krafka Brian W
• Krishnan Manavalan

Classifications

• G06F16/23

  Updating · CPC title

• G06F17/30117

  Physics · mapped topic

• G06F17/30961

  Physics · mapped topic

• G06F17/30327 Primary

  Physics · mapped topic

• G06F17/30345

  Physics · mapped topic