Logical sector mapping in a flash storage array
AssigneePure Storage, Inc.
InventorsJohn Colgrove, John Hayes, Ethan Miller, Feng Wang
Life of this patent
Estimating the term…
Abstract
A system and method for efficiently performing user storage virtualization for data stored in a storage system including a plurality of solid-state storage devices. A data storage subsystem supports multiple mapping tables. Records within a mapping table are arranged in multiple levels. Each level stores pairs of a key value and a pointer value. The levels are sorted by time. New records are inserted in a created newest (youngest) level. No edits are performed in-place. All levels other than the youngest may be read only. The system may further include an overlay table which identifies those keys within the mapping table that are invalid.
Claims37
A computer system comprising:
- a data storage medium;
- a data storage controller coupled to the data storage medium;
- and
- a mapping table that includes a plurality of levels, each level comprising one or more mapping table entries, wherein each respective mapping table entry corresponds to a respective mapping from a respective logical address to a respective physical address;
- wherein the data storage controller is configured to:
- receive a request, wherein the request indicates a logical address;
- generate, in dependence upon the logical address, a query key;
- and
- determine, in dependence upon the query key, a youngest level of the plurality of levels that includes a mapping table entry corresponding to a mapping from the logical address to a physical address.
A method comprising:
- storing a mapping table that includes a plurality of levels, each level comprising one or more mapping table entries, wherein each respective mapping table entry corresponds to a respective mapping from a respective logical address to a respective physical address;
- receiving a request, wherein the request indicates a logical address;
- generating, in dependence upon the logical address, a query key;
- and
- determining, in dependence upon the query key, a youngest level of the plurality of levels that includes a mapping table entry corresponding to a mapping from the logical address to a physical address.
A non-transitory computer readable storage medium storing program instruction executable by a processor to:
- store a mapping table that includes a plurality of levels, each level comprising one or more mapping table entries, wherein each respective mapping table entry corresponds to a respective mapping from a respective logical address to a respective physical address;
- receive a request, wherein the request indicates a logical address;
- generate, in dependence upon the logical address, a query key;
- and
- determine, in dependence upon the query key, a youngest level of the plurality of levels that includes a mapping table entry corresponding to a mapping from the logical address to a physical address.
Dependencies are inferred from the claim text.