Apparatus and method for referencing dense and sparse information in multi-dimensional to linear address space translation

Patent metadata

Field	Value
Publication number	US-10101937-B2
Application number	US-201314091053-A
Country	US
Kind code	B2
Filing date	Nov 26, 2013
Priority date	Mar 15, 2013
Publication date	Oct 16, 2018
Grant date	Oct 16, 2018

Abstract

A translation system can translate a storage request having multiple fields to a physical address using the fields as keys to traverse a map. The map can be made of nodes that include one or more node entries. The node entries can be stored in a hashed storage area or sorted storage area of a node. A hashed storage area can enable a quick lookup of densely addressed information by using a portion of the key to determine a location of a node entry. A sorted storage area can enable compact storage of sparse information by storing node entries that currently exist and allowing the entries to be searched. By offering both types of storage in a node, a node can be optimized for both dense and sparse information. A node entry can include a link to a next node or the physical address for the storage request.

First claim

What is claimed is:

1. A non-transitory computer-readable storage media having stored thereon executable instructions that, when executed by one or more processors of a computer system, cause the computer system to at least:
create a map of a set of nodes, the map including information to translate a logical storage request related to different layers of a storage system into a physical storage request that retrieves data on one or more physical storage devices, the logical storage request including information corresponding to particular requests for data related to the different layers of the storage system, the map enabling a use of a key to traverse the map to locate the data related to the different layers of the storage system, the map including information that corresponds to the key, wherein each node of a plurality of nodes from the set of nodes includes metadata, a hashed storage section comprising hashed node entries, and a sorted storage section comprising sorted node entries;
for at least one node from the plurality of nodes:
identify a portion of the key to use as an index in selecting a node entry included in the at least one node based, at least in part, on the metadata included in a header of the at least one node;
determine a division of node storage within the at least one node, the division of node storage including the hashed storage section and the sorted storage section;
determine a range of the hashed storage section for hashed node entries of the at least one node, wherein a location in the hashed storage section is calculable using the index;
provide the sorted storage section of node storage storing the sorted node entries of the at least one node, wherein the sorted storage section is searchable using the index; and
store at least one value indicating the determined range of the hashed storage section in the metadata of the header of the at least one node, the range indicating a number of hashed node entries;

cause a first node entry of the at least one node to link to a second node in the set of nodes, the first node entry including information about the link to the second node from the at least one node; and
store information in a second node entry of the second node, the information indicating a second portion of the key to use as the index in selecting the second node entry.

2. The non-transitory computer-readable storage media of claim 1 , wherein identifying the portion of the key in the metadata further comprises storing a field mask that identifies the portion of the key that represents the index for the at least one node.

3. The non-transitory computer-readable storage media of claim 1 , wherein a first field mask of a third node, which is closer to a root of the map, identifies digits having a greater significance than a second field mask of a fourth node that is further from the root of the map.

4. The non-transitory computer-readable storage media of claim 1 , wherein the map enables a translation from a logical location in an enterprise storage system to a physical location of data on storage media.

5. The non-transitory computer-readable storage media of claim 4 , wherein the key is a combination of fields describing the location in the enterprise storage system, the combination of fields comprising at least one of a field indicating a storage node, a field indicating a logical unit number, a field indicating a snapshot number, a field indicating a clone number, and a field indicating a logical block address.

6. The non-transitory computer-readable storage media of claim 1 , wherein the instructions further comprise instructions that, when executed, cause the computer system to at least:
select a node the map;
select the portion of the key to use as the index based at least in part on the metadata identifying the portion of the key to use as the index;
determine whether the index is located within the hashed storage section of hashed node entries or the sorted storage section of sorted node entries;
when determined that the index is located in the hashed storage section of hashed node entries, use the index to determine an address of the node entry corresponding to the index;
when determined that the index is located in the sorted storage section of sorted node entries, use the index to search for the node entry corresponding to the index in the sorted storage section of sorted node entries; and
access the node entry.

7. The non-transitory computer-readable storage media of claim 1 , wherein the metadata included in the header of the at least one node further comprises at least one of a field key that indicates a field that is used as the key, a field mask indicating one or more bits used in matching the key or determining an index, a bitmap indicating data for retrieving from a previous clone, and at least one attribute indicating one or more values stored in the hashed storage section or the sorted storage section.

8. The non-transitory computer-readable storage media of claim 1 , wherein to identify the portion of the key to use as the index in selecting the node entry is based on one or more bits of a field indicating a logical block address from a logical storage request.

9. The non-transitory computer-readable storage media of claim 8 , wherein the information, indicating the second portion of the key to use as the index in selecting the second node entry, comprises second one or more bits of the field indicating the logical block address, the second one or more bits being different than the one or more bits used as the index in selecting the node entry.

10. The non-transitory computer-readable storage media of claim 1 , wherein the storage system comprises a management system, the management system configured to manage the different layers of the storage system as a single layer, each of the different layers corresponding to a particular layer that provides a particular functionality for the storage system.

11. The non-transitory computer-readable storage media of claim 10 , wherein
the different layers of the storage system include a file system layer, a snapshot and clone layer, and a mapping layer, and
the logical storage request includes respective fields related to the file system layer, the snapshot and clone layer, and the mapping layer, the respective fields including a first field requesting a storage node, a second field requesting a logical block address, a third field requesting a snapshot number, a fourth field requesting a clone number, and a fifth field requesting a logical block address.

12. The non-transitory computer-readable storage media of claim 10 , wherein the management system is further configured to map data across a plurality of storage devices utilizing physical addressing, and the logical storage request corresponds to the data across the plurality of storage devices, the plurality of storage devices including a plurality of solid state drives.

13. A computer implemented method, comprising:
identifying a portion of a key to use as an index in selecting a node entry of a node based, at least in part, on node metadata included in a header of the node, the key corresponding to a field of a logical storage request related to different layers of a storage system, the logical storage request including information corresponding to particular requests for data related to the different layers of the storage system, the key enabling locating the data related to the different layers of the storage system;
determining a division of node storage within the node, the division of node storage including a hashed storage section comprising hashed node entries and a sorted storage section

Assignees

• Skyera Llc
• Western Digital Tech Inc

Inventors

• Danilak Radoslav
• Steffko Ladislav
• Wu Qi

Classifications

• G06F3/0683

  Plurality of storage devices · CPC title

• G06F2212/7201

  Logical to physical mapping or translation of blocks or pages · CPC title

• G06F12/1018

  involving hashing techniques, e.g. inverted page tables · CPC title

• G06F3/0641 Primary

  De-duplication techniques · CPC title

• G06F3/0631

  by allocating resources to storage systems · CPC title