DATA STORAGE INTEGRITY VALIDATION

• US 20140046909A1
• Filed: 08/08/2012
• Published: 02/13/2014
• Est. Priority Date: 08/08/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Patiejunas, Kestutis, Lazier, Colin L., Seigle, Mark C., Donlan, Bryan J.
• Granted Patent: US 8,805,793 B2
• Time in Patent Office: Days
• US Class Current: 707/687
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with RAID systems with parity

Abstract

Embodiments of the present disclosure are directed to, among other things, validating the integrity of received and/or stored data payloads. In some examples, a storage service may perform a first partitioning of a data object into first partitions based at least in part on a first operation. The storage service may also verify the data object, by utilizing a verification algorithm, to generate a first verification value. In some cases, the storage service may additionally perform a second partitioning of the data object into second partitions based at least in part on a second operation. The second partitions may be different from the first partitions. Additionally, the archival data storage service may verify the data object using the verification algorithm to generate a second verification value. Further, the storage service may determine whether the second verification value equals the first verification value.

Claims

1. A computer-implemented method for data integrity verification, comprising:

under control of one or more computer systems configured with executable instructions,

receiving one or more parts of a data payload;

for each part of at least a subset of the one or more parts, generating a first sub-part as part of partitioning the data payload;

calculating a value based at least in part on the first generated sub-part;

generating at least a root node of a data structure based at least in part on the calculated value;

identifying a top-level value of the data structure associated with the root node of the data structure; and

verifying, based at least in part on the top-level value, that a repartitioned data payload matches the received data payload, the repartitioned data payload based at least in part on a second sub-part of the one or more parts.

2. The computer-implemented method of claim 1, further comprising providing an instruction to a remote computing device, the instruction configured to enable the remote computing device to generate the data structure and provide the identified top-level value.

3. The computer-implemented method of claim 1, wherein the one or more parts of the data payload are received as part of an electronic request, from a remote computing device, to store the data payload.

4. The computer-implemented method of claim 3, further comprising providing a function call for a remote device to make the electronic request, and wherein the electronic request includes at least the provided function call.

5. The computer-implemented method of claim 1, wherein the data structure includes at least a binary tree.

6. The computer-implemented method of claim 1, further comprising receiving an indication of a size for each of the one or more parts of the data payload.

7. A computer-implemented method for data integrity verification, comprising:

under control of one or more computer systems configured with executable instructions,

receiving one or more parts of a data payload;

for each part of at least a subset of the one or more parts, generating a sub-part of a first predefined size, the received one or more parts being a second size that is an integer multiple of the first predefined size;

calculating a value based at least in part on the generated sub-part;

generating at least a root node of a data structure based at least in part on the calculated value; and

determining a top-level value of the data structure associated with the root node of the data structure.

8. The computer-implemented method of claim 7, further comprising:

storing the data payload in archival data storage; and

validating, based at least in part on the determined top-level value and a received top-level value, that the stored data payload matches a received data payload corresponding to the received one or more parts.

10. The computer-implemented method of claim 7, wherein the integer is based at least in part on a degree of branches of the data structure.

11. The computer-implemented method of claim 7, further comprising providing a data object identifier for identifying the data payload, the data object identifier including the top-level value of the data structure.

12. The computer-implemented method of claim 11, further comprising:

receiving a request for the stored data payload; and

verifying, based at least in part on the top-level value, that the stored data payload has not changed prior to providing the data payload.

13. The computer-implemented method of claim 7, further comprising:

storing the data payload of a first storage device to second storage device; and

verifying, based at least in part on the top-level value, that the data payload stored in the second storage device matches the data payload of the first storage device.

14. The computer-implemented method of claim 7, further comprising:

repartitioning the data payload based at least in part on a second generated sub-part, the second generated sub-part being different from the generated sub-part; and

verifying, based at least in part on the top-level value, that the repartitioned data payload matches a stored data payload, the stored data payload based at least in part on the received data payload.

9. (canceled)

15. A system for verifying data integrity, comprising:

at least one memory that stores computer-executable instructions; and

at least one processor configured to access the at least one memory, wherein the at least one processor is configured to execute the computer-executable instructions to collectively at least;

store at least a chunk of data, the data comprising a plurality of chunks;

generate a first sub-chunk of the at least one chunk of data;

store at least a digest corresponding to the first sub-chunk;

generate a data structure based at least in part on the stored digest corresponding to the first sub-chunk;

provide a top-level digest of the generated data structure to a computing device, and

verify, based at least in part on the top-level digest, that a repartitioned chunk of data matches the stored at least a chunk of data, the repartitioned chunk of data based at least in part on a second sub-chunk of the one or more parts.

16. The system of claim 15, wherein the at least one processor is further configured to execute the computer-executable instructions to receive the at least a chunk of data from the computing device based at least in part on a predefined size indicated by the computing device.

17. The system of claim 16, wherein the at least a chunk of data is received in an electronic request, from the computing device, to store the data based at least in part on an instruction format provided by the system.

18. The system of claim 15, wherein the top-level digest is prepended to an identifier configured to identify the data.

19. The system of claim 18, wherein the at least one processor is further configured to execute the computer-executable instructions to:

store the data comprising the plurality of chunks;

receive a request to provide the data to the computing device, the request including the identifier; and

validate the data, based at least in part on the top-level digest, prior to providing the data to the computing device.

20. The system of claim 18, wherein the at least one processor is further configured to execute the computer-executable instructions to:

generate a digest for the identifier; and

validate the identifier, based at least in part on the generated digest for the identifier, prior to referencing the identifier in an instruction.

21. One or more computer-readable media storing computer-executable instructions for verifying data integrity that, when executed by one or more processors, configure the one or more processors to perform operations comprising:

performing a first data operation in connection with a data object, the first data operation based at least in part on a first partitioning of the data object into first partitions;

verifying the data object using a data verification algorithm to generate a first verification value based at least in part on the first partitions by generating one or more partitions of the data in a predetermined size;

performing a second data operation in connection with the data object, the second data operation based at least in part on a second partitioning of the data object into second partitions, the second partitions being different from the first partitions and at least one of the first partitions or at least one of the second partitions having a size that is a multiple of the predetermined size;

verifying the data object using the data verification algorithm to generate a second verification value; and

determining whether the second verification value matches the first verification value.

23. The one or more computer-readable media of claim 21, wherein the multiple is a result of integer exponentiation of a degree of a data structure associated with the first data object.

24. The one or more computer-readable media of claim 21, wherein the instructions further configure the one or more processors to perform operations comprising providing instructions for making method calls to perform at least one of the first data operation or the second data operation.

25. The one or more computer-readable media of claim 21, wherein at least one of the first data operation or the second data operation is a transfer of the data object over a network.

26. The one or more computer-readable media of claim 25, wherein the object is transferred over the network in parts.

27. The one or more computer-readable media of claim 21, wherein the first operation includes at least receiving the data object and the second operation includes at least storing the data object in archival data storage.

28. The one or more computer-readable media of claim 27, wherein the instructions further configure the one or more processors to perform operations comprising ensuring integrity of the data object based at least in part on the second verification value.

29. The one or more computer-readable media of claim 27, wherein the instructions further configure the one or more processors to perform operations comprising ensuring integrity of the data object based at least in part on the second partitions.

22. (canceled)