Cross-datacenter validation of grid encoded data storage systems

• US 10,198,311 B1
• Filed: 07/01/2015
• Issued: 02/05/2019
• Est. Priority Date: 07/01/2015
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Donlan, Bryan James, Franklin, Paul David
• Primary Examiner(s): Knapp, Justin R
• Application Number:
  US14/789,799
• Time in Patent Office: 1,315 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/13 Linear codes
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

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.

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.

2. The computer-implemented method of claim 1, wherein validating the update further comprises, if a count of the subset of the particular set of error-detection code values is not divisible by two:

adding a first precomputed error-detection code value to the subset of the particular set of error-detection code values;

computing an XOR value of the subset of the particular set of error-detection code values; and

validating that the XOR value is equal to zero.

3. The computer-implemented method of claim 1, further comprising:

generating a particular set of second error-detection code values associated with the particular data shard by, for each vertically-derived shard of the set of vertically-derived shards with a corresponding column equal to the corresponding column of the particular data shard, generating the particular set of second error-detection code values using the error-detection code;

if a count of vertically-derived shards of the set of vertically-derived shards is not divisible by two, adding a second precomputed error-detection code value to the particular set of second error-detection code values;

computing an XOR value of the particular set of second error-detection code values; and

validating the update as a result of determining that the XOR value of the particular set of second error-detection code values is equal to zero.

4. The computer-implemented method of claim 1, further comprising storing the particular set of error-detection code values in a set of grid metadata associated with the particular data shard.

5. The computer-implemented method of claim 1, wherein the error-detection code is a cyclic redundancy check code.

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.

7. The system of claim 6, wherein each error-correction code value of the particular set of error-detection code values is a cyclic redundancy check value.

8. The system of claim 6, wherein the one or more services are further configured to store the particular set of error-detection code values in a corresponding set of grid metadata of the particular shard.

9. The system of claim 6, wherein the particular set of error-detection code values at least includes a precomputed error-detection code value selected based at least in part on a linear erasure code associated with the particular set of error-detection code values.

10. The system of claim 6, wherein at least a subset of the particular set of error-detection code values is computed by applying the error-detection code to one or more shards, each shard of the one or more shards having a respective second index equal to the particular second index of the particular shard.

11. The system of claim 6, wherein at least the subset of the particular set of error-detection code values is premultiplied by applying a multiplication operation using a corresponding constant associated with each error-detection code value of the corresponding set of error-detection code values, the corresponding constant determined based at least in part on the first index of the corresponding error-detection code value, the multiplication operation based at least in part on the error-detection code.

12. The system of claim 6, wherein the one or more services are further configured to validate the update by at least determining that a sum of the particular set of error-detection code values is equal to a predetermined value, the sum computed by applying an addition operation to the particular set of error-detection code values, the addition operation based at least in part on the error-detection code.

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.

14. The non-transitory computer-readable storage medium of claim 13, wherein the predetermined value is zero.

15. The non-transitory computer-readable storage medium of claim 13, wherein the sum is determined by applying an addition operation to the corresponding set of error-detection codes, the addition operation applied based at least in part on the error-detection code.

16. The non-transitory computer-readable storage medium of claim 13, wherein the sum is determined based at least in part on a parity calculation associated with the error-detection code.

17. The non-transitory computer-readable storage medium of claim 13, wherein each shard of the grid of shards has a corresponding set of grid metadata, the set of grid metadata associated to a respective shard at least including:

a first set of constants associated with a first redundancy code usable to reproduce the respective shard from other shards associated with a respective first index associated with the respective shard; and

a second set of constants associated with a second redundancy code usable to reproduce the respective shard from other shards associated with a respective second index associated with the respective shard.

18. The non-transitory computer-readable storage medium of claim 17, wherein the corresponding set of grid metadata for each shard of the grid of shards further includes a respective corresponding set of error-detection code values of the respective shard.

19. The non-transitory computer-readable storage medium of claim 13, wherein the instructions that cause the computer system to produce the validation of the request further comprise instructions that, when executed by the one or more processors of a computer system, cause the computer system to at least send the validation of the request to a requester associated with the update request.

20. The non-transitory computer-readable storage medium of claim 13, wherein the instructions that cause the computer system to produce the validation of the request further comprise instructions that, when executed by the one or more processors of a computer system, cause the computer system to at least reject the update request.