Data storage integrity validation

• US 9,465,821 B1
• Filed: 08/11/2014
• Issued: 10/11/2016
• 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.
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US14/456,844
• Time in Patent Office: 792 Days
• Field of Search: 707/649, 707/698, 707/812, 709204-206, 370/389
• US Class Current: 1/1
• 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, comprising:

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

performing a first data operation in connection with a data object, the first data operation utilizing 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;

performing a second data operation in connection with the data object, the second data operation utilizing a second partitioning of the data object into second partitions, the second partitioning being different from the first partitioning;

using the data verification algorithm in connection with at least the data object to generate a second verification value; and

verifying the data object based at least on part whether the second verification value matches the first verification value.

2. The computer-implemented method of claim 1, wherein using the data verification algorithm includes generating one or more partitions of the data in a predetermined size.

3. The computer-implemented method of claim 2, wherein at least one of the first partitions or at least one of the second partitions has a size that is an integer multiple of the predetermined size.

4. The computer-implemented method of claim 3, wherein the integer multiple is based at least in part on integer exponentiation of a degree of a data structure associated with the data object.

5. The computer-implemented method of claim 1, wherein at least one of the first data operation or the second data operation comprises a transfer of the data object over a network in parts.

6. The computer-implemented method of claim 1, wherein the first operation includes at least receiving the data object and the second operation includes at least storing the data object in data storage.

7. 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 verification value based at least in part on first partitions of a first partitioning of a data object;

use a data verification algorithm to generate a second verification value based at least in part on second partitions of a second partitioning of the data object, the second partitioning of the data object being different from the first partitioning of the data object; and

verify the data object based at least on part whether the second verification value matches the first verification value.

8. The system of claim 7, wherein at least one partition of the second partitioning contains multiple partitions of the first partitioning.

9. The system of claim 7, wherein at least one partition of the first partitioning contains multiple partitions of the second partitioning.

10. The system of claim 7, wherein the first partitioning is based at least in part on a first partition size, the second partitioning is based on a second partition size, and the second partition size is an integer multiple of the first partition size.

11. The system of claim 7, wherein the first partitioning is based at least in part on a first partition size, the second partitioning is based on a second partition size, and the first partition size is an integer multiple of the second partition size.

12. The system of claim 7, wherein the one or more services are further configured to:

perform a first data operation utilizing the first partitioning;

use the first verification value to verify successful completion of the first data operation; and

perform a second data operation based at least in part on the second partitioning.

13. The system of claim 12, wherein the first data operation includes persistently storing the data object in a first manner and the second data operation includes persistently storing the data object in a second manner different from the first manner.

14. 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:

obtain a first verification value that was generated based at least in part on first partitions of a first partitioning of a data object;

use a data verification algorithm to generate a second verification value based at least in part on second partitions of a second partitioning of the data object, the second partitioning of the data object being different from the first partitioning of the data object; and

verify the data object based at least on part whether the second verification value matches the first verification value.

15. The non-transitory computer-readable storage medium of claim 14, wherein the first partitioning of the data object is based at least in part on a first partition size, the second partitioning of the data object is based at least in part on a second partition size, and the second partition size is an integer multiple of the first partition size.

16. The non-transitory computer-readable storage medium of claim 15, wherein the integer multiple of the first partition size is based at least in part on integer exponentiation of a degree of a data structure associated with the data object.

17. The non-transitory computer-readable storage medium of claim 15, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to transmit the data object in connection with determining that the second verification value matching the first verification value indicates the data storage operation was successful.

18. The non-transitory computer-readable storage medium of claim 14, wherein the second verification matches the first verification value as a result of the second verification value being equal the first verification value.

19. The non-transitory computer-readable storage medium of claim 14, wherein the first verification value and the second verification value are top-level tree digests.

20. The non-transitory computer-readable storage medium of claim 14, wherein a plurality of partitions of the first partitions have uniform size.

21. The non-transitory computer-readable storage medium of claim 14, wherein:

the data verification algorithm includes calculating a digest using a hierarchical data structure comprising an ordered plurality of levels;

the ordered plurality of levels includes a bottom level; and

each level of the ordered plurality of levels that is not the bottom level is generated based at least in part on a next lower level of the ordered plurality of levels.