Techniques for combining grid-encoded data storage systems

• US 10,235,402 B1
• Filed: 12/17/2015
• Issued: 03/19/2019
• Est. Priority Date: 12/17/2015
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Franklin, Paul David, Brock, Adam Frederick, Kirschner, James Caleb, Donlan, Bryan James
• Primary Examiner(s): Alam, Hosain T
• Assistant Examiner(s): May, Robert F
• Application Number:
  US14/973,712
• Time in Patent Office: 1,188 Days
• Field of Search: 707741
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

One or more grids of redundancy coded shards, such as those stored or otherwise represented on grid encoded storage systems, are combinable or extensible. For example, a generator matrix of a redundancy code may be configured so as to have a sufficient number of fields to generate a grid. The generator matrix may initially be used to generate smaller grids, which can be combined into the target grid without re-encoding most or all of the data represented thereon. In some cases, vertically derived shards of the input grids may be combined using, e.g., matrix addition, which may then be directly allocated to the target grid, while data shards and horizontally derived shards may be allocated to the target grid with no further transformation.

Claims

1. A computer-implemented method, comprising:

generating a first grid of shards to be stored on a plurality of storage devices, the first grid of shards indexed at least by a first index and a second index, the first grid of shards comprising a first set of data shards and a first set of derived shards, wherein each shard of the first grid of shards has a corresponding first index, and a corresponding second index, each shard configured such that the shard is reproducible from other shards associated with the first index and the shard is reproducible from other shards associated with the second index;

generating a second grid of shards to be stored on the plurality of storage devices, the second grid of shards indexed at least by a third index and a fourth index, the second grid of shards comprising a second set of data shards and a second set of derived shards, wherein each shard of the second grid of shards has a corresponding third index, and a corresponding fourth index, each shard configured such that the shard is reproducible from other shards associated with the third index and the shard is reproducible from other shards associated with the fourth index; and

combining the first grid and the second grid to form a third grid indexed by a fifth index and a sixth index, the sixth index having a number of members equal to that of the second and fourth indices, by at least;

allocating the first set of data shards to the third grid;

indexing the first set of data shards in the third grid with a first subset of the fifth index;

allocating the second set of data shards to the third grid;

indexing the second set of data shards in the third grid with a second subset of the fifth index, the second subset of the fifth index being outside of the first subset of the fifth index;

combining a subset of the first set of derived shards with a corresponding subset of the second set of derived shards to generate a set of combined derived shards;

allocating the combined derived shards to the third grid; and

indexing the combined derived shards in the third grid with a third subset of the fifth index, the third subset of the fifth index being outside both the first subset and the second subset of the fifth index.

2. The computer-implemented method of claim 1,

further comprising generating the first grid of shards using a first portion of a generator matrix and the second grid of shards using a different portion of the generator matrix.

3. The computer-implemented method of claim 1, further comprising combining the subset of the first set of derived shards with the corresponding subset of the second set of derived shards by using a matrix operation.

4. The computer-implemented method of claim 1, further comprising generating the first grid and the second grid of shards by applying a linear erasure code to data sets to be stored on the respective first or second grid of shards.

5. A system, comprising at least one computing device configured to implement one or more services, wherein the one or more services are configured to:

generate a first grid of shards to be stored on a plurality of storage devices, the first grid of shards indexed at least by a first index and a second index, the first grid of shards comprising a first set of data shards and a first set of derived shards, wherein each shard of the first grid of shards has a corresponding first index, and a corresponding second index, each shard configured such that the shard is reproducible from other shards associated with the first index and the shard is reproducible from other shards associated with the second index;

generate a second grid of shards to be stored on the plurality of storage devices, the second grid of shards indexed at least by a third index and a fourth index, the second grid of shards comprising a second set of data shards and a second set of derived shards, wherein each shard of the second grid of shards has a corresponding third index, and a corresponding fourth index, each shard configured such that the shard is reproducible from other shards associated with the third index and the shard is reproducible from other shards associated with the fourth index; and

combine the first grid and the second grid to form a third grid indexed by a fifth index and a sixth index, the sixth index having a number of members equal to that of the second and fourth indices, by at least;

allocating the first set of data shards to the third grid;

indexing the first set of data shards in the third grid with a first subset of the fifth index;

allocating the second set of data shards to the third grid;

indexing the second set of data shards in the third grid with a second subset of the fifth index, the second subset of the fifth index being outside of the first subset of the fifth index;

combining a subset of the first set of derived shards with a corresponding subset of the second set of derived shards to generate a set of combined derived shards;

allocating the combined derived shards to the third grid; and

indexing the combined derived shards in the third grid with a third subset of the fifth index, the third subset of the fifth index being outside both the first subset and the second subset of the fifth index.

6. The system of claim 5, wherein the one or more services are further configured to generate the first grid of shards using a first portion of a generator matrix and the second grid of shards using a different portion of the generator matrix.

7. The system of claim 5, wherein the one or more services are further configured to combine the subset of the first set of derived shards with the corresponding subset of the second set of derived shards by using a matrix operation.

8. The system of claim 5, wherein the one or more services are further configured to generate the first grid and the second grid of shards by applying a linear erasure code to data sets to be stored on the respective first or second grid of shards.

9. The system of claim 5, wherein the shards of the subset of the first set of derived shards and the shards of the corresponding subset of the second set of derived shards are vertically-derived shards.

10. The system of claim 9, wherein a remainder of the shards of the first set outside of the subset of the first set of derived shards and the shards of the corresponding remainder of the shards of a second set outside of the subset of the second set of derived shards are allocated to the third grid.

11. The system of claim 5, wherein the services are further configured to generate the first grid of shards and the second grid of shards by processing received data using a redundancy code.

12. The system of claim 5, wherein the plurality of storage devices include at least one of:

magnetic tape, magnetic disk, optical disk, a memory resistor, or computer memory.

13. A non-transitory computer-readable storage medium having stored thereon executable instructions that, when executed by one or more processors of a computer system, cause the computer system to at least:

process data for storage on a first grid of shards and a second grid of shards, the first and second grid of shards each comprising;

a respective set of data shards;

a respective set of derived shards;

a respective first index;

a respective second index; and

each shard of the first and second grid of shards having a corresponding identifier in the respective first index and a corresponding identifier in the respective second index, and configured such that;

the shard is reproducible using only other shards sharing the corresponding identifier in the first index; and

the shard is reproducible using only other shards sharing the corresponding identifier in the second index; and

combine the first grid and the second grid to form a third grid indexed by a third index and a fourth index, the fourth index having a number of identifiers equal to that of the respective second indices of the first and second grids if combined, by at least;

placing the respective sets of data shards for the first and second grid into the third grid;

combining a subset of the respective set of derived shards of the first grid with a corresponding subset of the respective set of derived shards of the second grid to generate a set of combined derived shards; and

placing the combined derived shards in the third grid such that the combined derived shards so as to have the same corresponding identifier as in the respective first index of the first grid.

14. The non-transitory computer-readable storage medium of claim 13, wherein:

the respective set of derived shards includes a first subset of shards that are derived based at least in part on a first linear erasure code, and a second subset of shards that are derived based at least in part on a second linear erasure code.

15. The non-transitory computer-readable storage medium of claim 14, wherein the second subset of shards are derived from other shards that include at least some shards in the first subset of shards.

16. The non-transitory computer-readable storage medium of claim 15, wherein the second subset of shards are associated with identifiers of the second index that are not shared with other identifiers associated with shards outside of the second subset of shards.

17. The non-transitory computer-readable storage medium of claim 15, wherein:

the first linear erasure code is a parity code; and

the second linear erasure code is Reed-Solomon.

18. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further include instructions that, when executed, process the data by applying a first subset of a generator matrix of a redundancy code to the data for storage on the first grid of shards.

19. The non-transitory computer-readable storage medium of claim 18, wherein the instructions further include instructions that, when executed, process the data by applying a second subset of the generator matrix, the second subset being outside of the first subset of the generator matrix, to the data for storage on the second grid of shards.

20. The non-transitory computer-readable storage medium of claim 13, wherein the first index corresponds to grid columns.

21. A computer-implemented method, comprising:

processing data for storage on a first grid of shards and a second grid of shards, the first and second grid of shards each comprising;

a respective set of data shards;

a respective set of derived shards;

a respective first index;

a respective second index; and

each shard of the first and second grid of shards having a corresponding identifier in the respective first index and a corresponding identifier in the respective second index, and configured such that;

the shard is reproducible using only other shards sharing the corresponding identifier in the first index; and

the shard is reproducible using only other shards sharing the corresponding identifier in the second index; and

combining the first grid and the second grid to form a third grid indexed by a third index and a fourth index, the fourth index having a number of identifiers equal to that of the respective second indices of the first and second grids if combined, by at least;

placing the respective sets of data shards for the first and second grid into the third grid;

combining a subset of the respective set of derived shards of the first grid with a corresponding subset of the respective set of derived shards of the second grid to generate a set of combined derived shards; and

placing the combined derived shards in the third grid such that the combined derived shards so as to have the same corresponding identifier as in the respective first index of the first grid.

22. The computer-implemented method of claim 21, wherein the respective set of derived shards includes a first subset of shards that are derived based at least in part on a first linear erasure code, and a second subset of shards that are derived based at least in part on a second linear erasure code.

23. The computer-implemented method of claim 22, wherein the second subset of shards are derived from other shards that include at least some shards in the first subset of shards.

24. The computer-implemented method of claim 23, wherein the second subset of shards are associated with identifiers of the second index that are not shared with other identifiers associated with shards outside of the second subset of shards.

25. The computer-implemented method of claim 23, wherein:

the first linear erasure code is a parity code; and

the second linear erasure code is Reed-Solomon.

26. The computer-implemented method of claim 21, wherein the first index corresponds to grid columns.