Cross-datacenter validation of grid encoded data storage systems
First Claim
Patent Images
1. A computer-implemented method, comprising:
- generating, from a first data set using an erasure code, a grid of shards, the grid of shards comprising a set of data shards and a set of derived shards, wherein each shard of the grid of shards;
has a corresponding first index and a corresponding second index;
has a corresponding set of error-detection code values computed using an error-detection code;
is reproducible from other shards associated with the corresponding first index using a first error-detection code; and
is reproducible from other shards associated with the corresponding second index using a second error-detection code;
storing the grid of shards on a plurality of distributed data storage devices;
detecting alteration of any shard of the grid of shards using at least one of the first error-detection code or the second error-detection code;
in response to detecting a particular shard of the grid of shards is altered, determining a subset of a particular set of error-detection code values corresponding to the particular shard, error-detection code values of the subset of the particular set of error-detection code values selected based at least in part on a particular first index associated with the particular shard and based at least in part on a particular second index associated with the particular shard;
determining that the alteration to the particular shard is valid by processing the subset of the particular set of error-detection code values based at least in part on another value in the particular set of error-detection code values corresponding to the particular shard; and
as a result of determining that the alteration is valid, updating the grid of shards based at least in part on the subset of the particular set of error-detection code values.
1 Assignment
0 Petitions
Accused Products
Abstract
Techniques for validating grid encoded data storage systems are described herein. Data stored is stored in a grid of shards using grid encoding techniques that store the data in a combination of data shards and derived shards. Each of the shards has at least a first index corresponding to one dimension of the grid, a second index corresponding to a second dimension of the grid, and a set of error-detection code values. Updates that alter the grid of shards cause updates to the error-detection code values and the update can be validated based on the updated error-detection code values.
-
Citations
20 Claims
-
1. A computer-implemented method, comprising:
-
generating, from a first data set using an erasure code, a grid of shards, the grid of shards comprising a set of data shards and a set of derived shards, wherein each shard of the grid of shards; has a corresponding first index and a corresponding second index; has a corresponding set of error-detection code values computed using an error-detection code; is reproducible from other shards associated with the corresponding first index using a first error-detection code; and is reproducible from other shards associated with the corresponding second index using a second error-detection code; storing the grid of shards on a plurality of distributed data storage devices; detecting alteration of any shard of the grid of shards using at least one of the first error-detection code or the second error-detection code; in response to detecting a particular shard of the grid of shards is altered, determining a subset of a particular set of error-detection code values corresponding to the particular shard, error-detection code values of the subset of the particular set of error-detection code values selected based at least in part on a particular first index associated with the particular shard and based at least in part on a particular second index associated with the particular shard; determining that the alteration to the particular shard is valid by processing the subset of the particular set of error-detection code values based at least in part on another value in the particular set of error-detection code values corresponding to the particular shard; and as a result of determining that the alteration is valid, updating the grid of shards based at least in part on the subset of the particular set of error-detection code values. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A system, comprising at least one computing device that implements one or more services, wherein the one or more services at least:
-
generate a grid of shards, the grid of shards indexed at least by a first index and a second index, the grid of shards comprising a set of data shards and a set of derived shards, wherein each shard of the grid of shards; has a corresponding first index and a corresponding second index; has a corresponding set of error-detection code values computed using an error-detection code; is reproducible from other shards associated with the corresponding first index using a first redundancy code; and is reproducible from other shards associated with the corresponding second index using a second redundancy code; store the grid of shards across a plurality of distributed data storage devices; detect alteration of any shard of the grid of shards using at least one of the first redundancy code or the second redundancy code; in response to detecting a particular shard of the grid of shards is altered, determine a subset of a particular set of error-detection code values corresponding to the particular shard, error-detection code values of the subset of the particular set of error-detection code values selected based at least in part on a particular first index associated with the particular shard of the grid of shards and based at least in part on a particular second index associated with the particular shard of the grid of shards; determine that the alteration to the particular shard is valid by processing the subset of the particular set of error-detection code values based at least in part on another value in the particular set of error-detection code values corresponding to the particular shard; and as a result of determining that the alteration is valid, update the grid of shards based at least in part on the subset of the particular set of error-detection code values. - View Dependent Claims (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:
-
receive a request to update a particular shard of a grid of shards, the grid of shards; stored on a plurality of distributed data storage devices to enable the plurality of distributed data storage devices to detect an update of any shard of the grid of shards using at least one error-detection code; indexed by at least a first index and a second index; and comprising a set of data shards and a set of derived shards, wherein each shard of the grid of shards; has a corresponding first index and a corresponding second index; has a corresponding set of error-detection code values, the corresponding set of error-detection code values computed based at least in part on applying the error-detection code to one or more shards associated with the shard; is reproducible from other shards associated with the corresponding first index and the shard; and is reproducible from other shards associated with the corresponding second index; and as a result of receiving the request; update a particular data shard associated with the request; update a first subset of the set of derived shards, the first subset associated with the particular data shard; update a second subset of the corresponding set of error-detection code values; and determine that the update to the particular shard is valid as a result of determining that a sum of the corresponding set of error-detection code values is equal to a predetermined value. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
Specification