Back to results
US 10,592,336 B1Granted
Layered indexing for asynchronous retrieval of redundancy coded data
AssigneeAmazon Technologies, Inc.
InventorsBryan James Donlan, Paul David Franklin, James Caleb Kirschner
Life of this patent
Estimating the term…
Abstract
A multilayered index is implemented for data stored in a data storage system. The multilayered index may include a granular index that specifies the location of specific files or abstractions within the data storage system, while a skip table specifies segments of the abstractions, and may point to both the granular index and the data storage devices of the data storage system. In redundancy coded systems, the use of multilayered indices may enable asynchronous retrieval of data during normal or adverse operation (such as during periods of varying data availability).
Claims19
A computer-implemented method, comprising:
- processing data to be stored in a plurality of volumes of durable storage of a data storage system by at least:
- using a redundancy code, redundancy coding at least the data to generate a bundle of bundle-encoded shards, a quorum quantity of which is sufficient to reconstruct original data associated with the bundle, such that a plurality of data objects associated with the data are each uniquely identified using a respective identifier and sorted for storage within the bundle according to the identifier, the plurality of data objects being a plurality of data files, the bundle including at least:
- identity shards, at least one identity shard of which contains an original form of the encrypted data;
- encoded shards representing a redundancy coded form of the encrypted data, and
- one or more indices, each index of the one or more indices
- comprising:
- a granular index that includes a plurality of pointers, each pointer of the plurality of pointers being associated with one or more locations of a first set of locations, within the bundle, of each data object of at least a subset of the plurality of data objects;
- and a skip table that includes:
- a plurality of sections, each section of the plurality of sections being associated with one or more plural subsets of the plurality of pointers, each plural subset being sequentially contiguous according to the identifier, and
- a second set of locations, within the bundle, of each section of the plurality of sections;
- and
- in response to receiving a retrieval request to retrieve at least one of the data objects, processing the retrieval request by at least:
- locating a requested data object within the original form of the data associated with the section.
10 more elements
A system, comprising:
- at least one computing device configured to implement one or more services that:
- index a set of data stored on a data storage system as a set of redundancy coded shards and according to a sort order associated with a plurality of data objects within the set of data the plurality of data objects being a plurality of data files, the index comprising a first index and a second index;
- the first index including a first set of pointers to a first set of locations within the data storage system associated with each of a first plurality of subsets of the set of data;
- and
- the second index including:
- a second set of pointers to a second set of locations, each of which points to a plurality of the locations of the first set of locations;
- and
- a third set of pointers to a plurality of the pointers of the first set of pointers associated with the plurality of the locations of the first set;
- and
- locate a requested subset of the indexed set of data by at least:
- using the sort order and the second index, identifying a respective plurality of the first set of locations to which the request subset is associated;
- and
- retrieving a second subset of the indexed set of data from the identified plurality of the first set of locations, the second subset including at least the requested subset of the indexed data.
10 more elements
A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:
- for data stored as a set of redundancy-coded shards and in connection with an identifier associated with each data object of a plurality of data objects of the data, each data object being a data file, generate a first index and a second index:
- the first index including a first set of pointers to a first set of storage locations, each storage location of the first set of storage locations being associated with each of a first plurality of subsets of the data, each pointer of the first set of pointers mapping to a different storage location of the first set of storage locations;
- and
- the second index including:
- a second set of pointers to a second set of locations, each pointer of the second set of pointers referring to a plurality of the locations of the first set of locations;
- and
- a third set of pointers to a plurality of the pointers of the first set of pointers associated with the plurality of the locations of the first set;
- and
- retrieve a requested data object of the data by at least:
- using an identifier value of the requested subset of the data, a sort order associated with the identifier, and the second index, identifying a respective plurality of the first set of locations to which the requested data object is associated;
- and
- retrieving a second subset of the data from the identified plurality of the first set of locations, the second subset including at least the requested data object of the data.
9 more elements
Dependencies are inferred from the claim text.