Techniques for combining grid-encoded data storage systems
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
26 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. - View Dependent Claims (2, 3, 4)
-
-
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. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
-
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. - View Dependent Claims (22, 23, 24, 25, 26)
-
Specification