Apparatus and method for insertion and deletion in multi-dimensional to linear address space translation

Patent metadata

Field	Value
Publication number	US-10282121-B2
Application number	US-201715470695-A
Country	US
Kind code	B2
Filing date	Mar 27, 2017
Priority date	Mar 15, 2013
Publication date	May 7, 2019
Grant date	May 7, 2019

Abstract

A translation system can translate a storage request to a physical address using fields as keys to traverse a map of nodes with node entries. A node entry can include a link to a next node or a physical address. Using a portion of the key as noted in node metadata, a node entry can be determined. When adding node entries to a node, a node utilization can exceed a threshold value. A new node can be created such that node entries are split between the original and new node. Node metadata of the parent node, new node and original node can be revised to identify which parts of the key are used to identify a node entry. When removing node entries from a node, node utilization can cross a minimum threshold value. Node entries from the node can be merged with a sibling, or the map can be rebalanced.

First claim

What is claimed is:

1. A computer implemented method, comprising:
receiving a request to add data at a logical location in a storage system, the request including a set of fields describing the logical location in the storage system;
translating the logical location in the storage system to a physical location in the storage system based on traversing a map of nodes, a header of a respective node identifying at least one field of the set of fields as a key for selecting a next node in the map of nodes, wherein a leaf node includes an identification of the physical location in the storage system;
determining that adding a node entry to a first node of the map of nodes exceeds a threshold utilization of entries; and
in response to determining that adding the node entry to the first node exceeds the threshold utilization of entries:
creating a second node and a new parent node, the new parent node including a first entry for identifying the first node and a second entry for identifying the second node, the new parent node including revised header information, based on header information of a current parent node of the first node, identifying at least a portion of a field in the set of fields as a key for selecting between the first node and second node;
creating an entry to identify the new parent node in the current parent node; and
redistributing first node entries from the first node to the first node and the second node based at least in part on the revised header information of the new parent node.

2. The computer implemented method of claim 1 , wherein traversing the map of nodes comprises:
starting at a root node of the map of nodes, at least some of the nodes in the map of nodes comprising a hashed portion and a sorted portion; and
determining an end node of the map of nodes by traversing nodes in the map of nodes through:
determining a first portion of the set of fields to use as a key to locate a node entry in the node;
locating the node entry of the node based on the key;
when the node entry links to a next node, following a link to the next node; and
when the node entry includes a physical address, retrieving data from a storage device using the physical address.

3. The computer implemented method of claim 1 , wherein determining that adding the node entry to the first node exceeds the threshold utilization of entries further comprises determining that a hashed portion of node storage exceeds the threshold utilization of entries.

4. The computer implemented method of claim 1 , wherein determining that adding the node entry to the first node exceeds the threshold utilization of entries further comprises determining that a sorted portion of node storage exceeds the threshold utilization of entries.

5. The computer implemented method of claim 1 , further comprising:
determining the revised header information, by dividing a parent portion of a key into a set including a more significant portion and a less significant portion.

6. The computer implemented method of claim 5 , further comprising selecting a more significant portion to use in the revised header information.

7. The computer implemented method of claim 5 , wherein the key is represented as a set of bits.

8. A system comprising:
a storage interface configured to receive requests for data at a logical storage a storage location;
a storage system comprising a set of physical locations; and
a translation system configured to form a translation of the logical storage location to a physical storage location in the set of physical locations by:
receiving a request to add data at a logical location in the storage system, the request including a set of fields describing the logical location in the storage system;
translating the logical location in the storage system to a physical location in the storage system based on traversing a map of nodes, a header of a respective node identifying at least one field of the set of fields as a key for selecting a next node in the map of nodes, wherein a leaf node includes an identification of the physical location in the storage system;
determining that adding a node entry to a first node of the map of nodes exceeds a threshold utilization of entries; and
in response to determining that adding the node entry to the first node exceeds the threshold utilization of entries:
creating a second node and a new parent node, the new parent node including a first entry for identifying the first node and a second entry for identifying the second node, the new parent node including revised header information, based on header information of a current parent node of the first node, identifying at least a portion of a field in the set of fields as a key for selecting between the first node and second node;
creating an entry in the current parent node to identify the new parent node; and
rebalancing node entries from the first node to at least the first node and the second node based on the revised header information of the new parent node.

9. The system of claim 8 , wherein the storage system comprises solid state drives.

10. The system of claim 8 , wherein the set of fields represents a logical block location.

11. The system of claim 10 , wherein the logical block location further comprises an identifier of a storage node, logical unit number, snapshot number, clone number or logical block address.

12. The system of claim 8 , wherein the set of fields represents a file system location.

13. The system of claim 12 , wherein the file system location further comprises an identifier of a storage volume, file system, file, stream, snapshot number, clone number or logical block address.

14. The system of claim 8 , further comprising an operating system in communication with the storage interface.

15. One or more non-transitory computer-readable storage media having collectively stored thereon executable instructions that, when executed by one or more processors of a computer system, cause the computer system to at least:
receive a request to remove data at a logical location in a storage system, the request including a set of fields describing the logical location in the storage system;
translate the logical location in the storage system to a physical location in the storage system based on a traversal of a map of nodes, a header of a respective node identifying at least one field of the set of fields as a key for selecting a next node in the map of nodes, wherein a leaf node includes an identification of the physical location in the storage system;
invalidate a node entry of a first node;
determine, based on invalidating the node entry, that utilization of entries in the first node is below a threshold utilization of entries; and
in response to determining that utilization of entries is below the threshold utilization of entries:
merge node entries from the first node to a second node;
replace a parent node of the first node and the second node with the second node; and
create header information for the second node for the merged node entries.

16. The non-transitory computer-readable storage media of claim 15 , wherein the instructions further comprise instructions that, when executed, cause the computer system to at least:
receive a second request to remove second data at a second logical location in the storage system, the second request including a second set of fields describing the second logical location in the storage system;
traverse the map of nodes to locate a third node including a second node entry that references the second data based at least in part on a second su

Assignees

• Skyera Llc
• Western Digital Tech Inc

Inventors

• Danilak Radoslav
• Steffko Ladislav
• Wu Qi

Classifications

• G06F3/0688

  Non-volatile semiconductor memory arrays · CPC title

• G06F2212/7201

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

• G06F3/0689

  Disk arrays, e.g. RAID, JBOD · CPC title

• G06F3/065

  Replication mechanisms · CPC title

• A63F13/795

  for finding other players; for building a team; for providing a buddy list · CPC title