Single quorum verification of erasure coded data

• US 10,289,481 B2
• Filed: 08/29/2018
• Issued: 05/14/2019
• Est. Priority Date: 11/19/2014
• 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, Suver, Claire Elizabeth, Schmitt, Ryan Charles, Franklin, Paul David
• Primary Examiner(s): Abraham, Esaw T
• Application Number:
  US16/116,777
• Publication Number:
  US 20180373587A1
• Time in Patent Office: 258 Days
• 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: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes

Abstract

Techniques described and suggested herein include various methods and systems for verifying integrity of redundancy coded data, such as erasure coded data shards. In some embodiments, a quantity of redundancy coded data elements, hereafter referred to as data shards (e.g., erasure coded data shards), sufficient to reconstruct the original data element from which the redundancy coded data elements are derived, is used to generate reconstructed data shards to be used for checking the validity of analogous data shards stored for the original data element.

Claims

1. A computer-implemented method, comprising:

for stored data shards of an original data element, identifying a subset of the stored data shards sufficient for reconstructing the original data element, the stored data shards collectively representing an erasure coded version of the original data element;

verifying integrity of the identified subset of the stored data shards by at least;

generating a version of the original data element from the identified subset of the stored data shards; and

verifying the version of the original data element by comparing at least one first hash value associated with the original data element with at least one second hash value associated with the version of the original data element;

reconstructing, using the version of the original data element, data shards outside of the identified subset of the stored data shards, thereby generating reconstructed data shards;

calculating one or more third hash values for the reconstructed data shards; and

verifying integrity of the stored data shards by comparing the calculated third hash value with one or more fourth hash values associated with one or more of the stored data shards outside of the identified subset of the stored data shards; and

initiating a mitigation workflow if, when verifying the integrity of the stored data shards, at least one of the stored data shards is identified as invalid.

2. The computer-implemented method of claim 1, wherein the identified subset has a number of members that is equal to a minimum number of members sufficient for reconstructing the data object.

3. The computer-implemented method of claim 1, wherein the one or more computer system are components of a data storage service and the original data element is a data object transmitted to the data storage service by a customer of the data storage service.

4. A system for storing data shards, comprising:

one or more processors; and

memory storing instructions executed by the one or more processors to cause the system;

receive a least one first hash value associated with an original data element, the original data element stored in a subset of the stored data shards, the stored data shards collectively representing an erasure coded version of the original data element, the integrity of the identified subset of the stored data shards having been verified by at least;

generating a version of the original data element from the identified subset of the stored data shards; and

verifying the version of the original data element by comparing at least one first hash value associated with the original data element with at least one second hash value associated with the version of the original data element;

reconstruct, using the version of the original data element, data shards outside of the identified subset of the stored data shards, thereby generating reconstructed data shards;

calculate one or more third hash values for the reconstructed data shards; and

verifying integrity of the stored data shards by comparing the calculated third hash value with one or more fourth hash values associated with one or more of the stored data shards outside of the identified subset of the stored data shards; and

initiate a mitigation workflow if the integrity of at least one of the stored data shards is identified as invalid.

5. The system of claim 4, wherein the identified subset has a number of members that is equal to a minimum number of members sufficient for reconstructing the data object.

6. The system of claim 4, wherein one or more processors are components of a data storage service and the original data element is a data object transmitted to the data storage service by a customer of the data storage service.

7. The system of claim 4, wherein the system to initiate a mitigation workflow if the integrity of at least one of the stored data shards is identified as invalid.

8. The system of claim 4, wherein the set of stored shards was generated from the original data element.

9. The system of claim 4, wherein the first subset is sufficient for reconstruction of the original data element.

10. The system of claim 4, wherein the subset of the stored data shards has a number of members that is equal to a minimum number of members sufficient for reconstructing the original data element.

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

receive a least one first hash value associated with an original data element, the original data element stored in a subset of the stored data shards, the stored data shards collectively representing an erasure coded version of the original data element, the integrity of the identified subset of the stored data shards having been verified by at least;

generating a version of the original data element from the identified subset of the stored data shards; and

verifying the version of the original data element by comparing at least one first hash value associated with the original data element with at least one second hash value associated with the version of the original data element;

reconstruct, using the version of the original data element, data shards outside of the identified subset of the stored data shards, thereby generating reconstructed data shards;

calculate one or more third hash values for the reconstructed data shards; and

verifying integrity of the stored data shards by comparing the calculated third hash value with one or more fourth hash values associated with one or more of the stored data shards outside of the identified subset of the stored data shards; and

initiate a mitigation workflow if the integrity of at least one of the stored data shards is identified as invalid.

12. The non-transitory computer readable storage medium of claim 11, wherein the identified subset has a number of members that is equal to a minimum number of members sufficient for reconstructing the data object.

13. The non-transitory computer readable storage medium of claim 11, wherein one or more processors are components of a data storage service and the original data element is a data object transmitted to the data storage service by a customer of the data storage service.

14. The non-transitory computer readable storage medium of claim 11, wherein the set of stored shards was generated from the original data element.

15. The non-transitory computer readable storage medium of claim 11, wherein the first subset is sufficient for reconstruction of the original data element.

16. The non-transitory computer readable storage medium of claim 11, wherein the subset of the stored data shards has a number of members that is equal to a minimum number of members sufficient for reconstructing the original data element.