Apparatus and method for using fields in N-space translation of storage requests

Patent metadata

Field	Value
Publication number	US-11010075-B2
Application number	US-201715458945-A
Country	US
Kind code	B2
Filing date	Mar 14, 2017
Priority date	Mar 15, 2013
Publication date	May 18, 2021
Grant date	May 18, 2021

Abstract

A translation system can translate a request having multiple fields to a physical address using the fields as indexes to a multi-dimensional graph. A field or portion of a field can represent a location along an axis. When combined together, the fields can represent a point in n-space, where n is the number of axes. In some embodiments, a nearest neighbor calculation can be sufficient along an axis. Therefore, a point in n-space defined by the fields can be translated along an axis until a nearest neighbor entry is determined. When the entry is determined, the entry can be accessed to determine a correct response to the translation request.

First claim

What is claimed is:

1. One or more machine-readable storage media comprising instructions stored therein, the instructions executable by one or more processors to perform a method, the method comprising:
receiving a request associated with a plurality of values for a set of fields identifying logical constructs related to a storage system, wherein the storage system comprises a non-volatile memory, wherein the logical constructs comprise a logical address of data stored in the non-volatile memory, wherein at least a subset of the set of fields are represented along a set of axes in a multidimensional graph, wherein the subset of the set of fields represents at least three of the following: a logical address, a logical unit identification, a snapshot identification, a storage node, and a clone identification, wherein each field in the subset is represented along a different axis in the multidimensional graph, and wherein a set of values of the subset of the set of fields are represented as a point in the multidimensional graph based at least in part on the set of axes;
traversing a data structure, associated with the set of axes, based at least in part on the set of values;
determining that an entry in the data structure represents the point in the multidimensional graph; and
providing, based on the entry, a physical location of the data stored in the non-volatile memory for performing an operation on the data, in response to the request, wherein the physical location comprises a physical address of the data stored in the non-volatile memory,
wherein the set of axes include a first axis, a second axis and a third axis that are different from one another,
wherein the first, second and third axes are perpendicular to one another,
wherein the subset includes a first field represented along the first axis, a second field represented along the second axis, and a third field represented along the third axis,
wherein the set of values includes a first value for the first field, a second value for the second field, and a third value for the third field,
wherein the point is an intersection point of the first value, the second value and the third value,
wherein when the data is not found at a first location corresponding to the point, tracing along one of the first, second and third axes to arrive at a second point representing a second location to locate the data.

2. The one or more machine-readable storage media of claim 1 , wherein the multidimensional graph is n-dimensional where n is a number of fields in the subset of the set of fields.

3. The one or more machine-readable storage media of claim 1 , wherein the set of fields represent a logical location in the storage system.

4. The one or more machine-readable storage media of claim 3 , wherein the entry describes the physical location in the storage system.

5. The one or more machine-readable storage media of claim 1 , wherein traversing the data structure comprises:
starting at a root node of a map, the map comprising a plurality of nodes, at least some of the plurality of nodes having a set of entries;
determining an end node of the map by traversing nodes in the map by:
determining a portion of the set of fields to use as a key to locate a node entry in the node;
locating the node entry in the node based at least in part on the key; and
when the node entry links to a next node, following a link to the next node.

6. The one or more machine-readable storage media of claim 5 , wherein locating the node entry in the node based at least in part on the key comprises:
selecting a node from a set of nodes in a node storage system;
selecting a first portion of the key to use as an index based at least in part on node metadata describing the first portion of the key to use as the index;
determining whether the index is located within an indexed section of node entries or a sorted section of node entries;
when determined that the index is located in the indeed section of node entries, using the index to determine an address of the node entry corresponding to the index; and
when determined that the index is located in the sorted section of node entries, using the index to search for the node entry corresponding to the index in the sorted section of node entries.

7. A storage system, comprising:
a data storage system comprising a set of physical locations, wherein the data storage system comprises a non-volatile memory, and wherein the set of physical locations comprises physical addresses of a plurality of data stored in the non-volatile memory; and
a translation system configured to form a translation of a logical storage location to a physical storage location by:
providing a set of fields that are associated with a range of logical storage locations, wherein the logical storage locations comprise a logical address of data, wherein the plurality of data comprises the data;
mapping a subset of the set of fields to a set of axes in a multidimensional graph that is n-dimensional,
wherein n is a number of fields in the subset of the set of fields,
wherein the subset of the set of fields represents the following: a logical address, a logical unit identification, and a snapshot identification, and
wherein each field in the subset is represented along a different axis in the multidimensional graph;

determining a physical location of the data accessible by a logical point representable by a set of field values mapped to corresponding axes within the set of axes; and
providing the physical location of the data for performing a read operation, an update operation, a delete operation or another operation on the data, based on the set of field values that match the logical point representable by the set of field values mapped to the corresponding axes within the set of axes, wherein the physical location of the data comprises a physical address of the data stored in the non-volatile memory,

wherein the set of axes include a first axis, a second axis and a third axis that are different from one another,
wherein the first, second and third axes are perpendicular to one another,
wherein the subset includes a first field represented along the first axis, a second field represented along the second axis, and a third field represented along the third axis,
wherein the set of field values includes a first field value for the first field, a second field value for the second field, and a third field value for the third field,
wherein the logical point is an intersection point of the first field value, the second field value and the third field value,
wherein when the data is not found at a first location corresponding to the logical point, tracing along one of the first, second and third axes to arrive at a second logical point associated with a second location to locate the data.

8. The storage system of claim 7 , wherein the translation system is further configured to enable a nearest neighbor search along at least one axis from the set of axes.

9. The storage system of claim 8 , wherein the nearest neighbor search is enabled for a snapshot axis corresponding to a snapshot field.

10. The storage system of claim 7 , wherein determining the physical location of the data comprises:
enabling an axis to use a nearest neighbor search;
when the logical point is not defined at a location defined by the set of field values, translating along the axis until a neighboring logical point is found; and
using the neighboring logical point as the logical point.

11. The storage system of claim 7 , wherein determining the physical location of the data comprises:
enabling an axis to use a nearest neighbor search;
applying the set of field va

Assignees

• Skyera Llc
• Western Digital Tech Inc

Inventors

• Danilak Radoslav
• Steffko Ladislav
• Wu Qi

Classifications

• G06F3/0641 Primary

  De-duplication techniques · CPC title

• G06F3/0638 Primary

  Organizing or formatting or addressing of data · CPC title

• G06F16/211

  Schema design and management · CPC title

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F2212/7201

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