Apparatus and method for insertion and deletion in multi-dimensional to linear address space translation
View Patent ↗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.
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;
traversing a map of nodes from a root node to a first parent node of a first node identified as containing the logical location, wherein at least a subset of fields from the set of fields represent a key for navigating the map of nodes, each node identifying, based on information in a header of the node, a portion of the key to use to select an entry in the node, the entry identifying a next node or a physical location in the storage system;
determining that adding a node entry to the first node exceeds a threshold utilization of entries;
creating a new parent node for the first node, wherein an entry in the first parent node points to the new parent node;
determining, based on information in a header of the new parent node, a portion of the key to enable redistribution of first node entries from the first node;
creating a second node;
determining, based on information in the header of the new parent node, a first offset value of a portion of the key to use to select an entry in the new parent node that leads to the first node;
determining a second offset value of the portion of the key to use to select an entry in the new parent node that leads to the second node;
redistributing first node entries from the first node to the first node and the second node based at least in part on the header information in the new parent node; and
providing entries for the first node and the second node based at least in part on the first or second offset values.
2. The computer implemented method of claim 1 , wherein traversing the map of nodes from the root node to the first parent node further comprises:
starting at the root node of the map of nodes describing the storage system, the map of nodes comprising a plurality of nodes, at least some of the plurality 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 the key to a node entry in the node;
locating the node entry in the hashed portion or the sorted portion 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 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 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 wherein the key is represented as a set of bits.
6. A system comprising:
a storage interface configured to receive requests for data at a logical 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;
traversing a map of nodes to locate a first node to receive a reference to the data based at least in part on a subset of fields from the set of fields that represent a key for navigating the map of nodes, each node identifying, based on information in a header of the node, a portion of the key to use to select an entry in the node, the entry identifying a next node or a physical location in the storage system;
determining that the first node exceeds a threshold utilization of entries;
creating a new parent node to the first node;
creating a second node;
rebalancing node entries from the first node to at least the first node and the second node;
determining, based on information in a header of the new parent node, a first offset value of a portion of the key to use to select the first node;
determining, based on information in the header of the new parent node, a second offset value of a portion of the key to use to select the second node;
providing entries for the first node and the second node based at least in part on the information in the header of the new parent node; and
adding a node entry to the rebalanced node entries based at least in part on the first or second offset values.
7. The system of claim 6 , wherein the storage system comprises solid state drives.
8. The system of claim 6 , wherein the set of fields represents a logical block location.
9. The system of claim 8 , wherein the logical block location further comprises an identifier of a storage node, logical unit number, snapshot number, clone number or logical block address.
10. The system of claim 6 , wherein the set of fields represents a file system location.
11. The system of claim 10 , wherein the file system location further comprises an identifier of a storage volume, file system, file, stream, snapshot number, clone number or 3 logical block address.
12. The system of claim 6 , further comprising an operating system in communication with the storage interface.
13. One or more non-transitory computer-readable storage media having collectively stored thereon executable instructions that, when executed by one or more 3 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;
traverse a map of nodes to locate a first node including a node entry that references the data based at least in part on a subset of fields from the set of fields that represent a key for navigating the map of nodes, wherein each node in the map of nodes identifies, based on information in a header of the node, a portion of the key used to select an entry in the node, the entry identifying a next node or a physical location in the storage system;
invalidate the node entry from the first node;
determine that the first node is below a threshold utilization of entries based at least in part on invalidating the node entry;
determine that a second node is a sibling of the first node and has sufficient space to merge node entries from the first node;
merge node entries from the first node to the second node;
remove the first node from the map of nodes;
remove a parent node of the first node and the second node;
revise an entry in a parent node of the parent node to point to the second node;
and
revise key information for the second node based at least in part on the merged node entries.
14. The non-transitory computer-readable storage media of claim 13 , 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 subset of fields from the second set of fields that represent a second key for navigating the map of nodes, wherein each node in the map of nodes identifies, based on information in a header of the node, a portion of the key used to select an entry in the node, the entry identifying a next node or a physical location in the storage system;
invalidate the second node entry from the third node;
determine that the third node is below the threshold utilization of entries based at least in part on invalidating the second node entry;
determine that a fourth node has a sibling relationship to the third node and has insufficient space to merge node entries from the first node;
rebalance a node entry distribution between the third node and the fourth node in the map of nodes; and
revise key information in use for the third node, the fourth node and the parent node of the third node and the fourth node based at least in part on the rebalanced node entry distribution.
15. The non-transitory computer-readable storage media of claim 13 , 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 subset of fields from the second set of fields that represent a second key for navigating the map of nodes, wherein each node in the map of nodes identifies, based on information in a header of the node, a portion of the key used to select an entry in the node, the entry identifying a next node or a physical location in the storage system;
invalidate the second node entry from the third node;
determine that the third node is below the threshold utilization of entries based at least in part on invalidating the second node entry;
determine that the third node has no sibling relationship to a next node in the map of nodes;
rebalance a node entry distribution between the third node and the parent node of the third node in the map of nodes; and
revise key information in use for the third node and the parent node of the third node based at least in part on the rebalanced node entry distribution.
16. The non-transitory computer-readable storage media of claim 13 , wherein the instructions further comprise instructions that, when executed, cause the computer system to at least mark a physical location of the data as free space.
17. The non-transitory computer-readable storage media of claim 13 , wherein revising key information in use for the second node further comprises remapping, in the second node, a hashed portion of node entries and an indexed portion of node entries.
18. The non-transitory computer-readable storage media of claim 13 , wherein the instructions further comprise instructions that, when executed, cause the computer system to at least respond to the request confirming removal of the data.