Data storage integrity validation

• US 10,157,199 B2
• Filed: 10/05/2016
• Issued: 12/18/2018
• 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:
  US15/286,473
• Publication Number:
  US 20170024428A1
• Time in Patent Office: 804 Days
• 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:

receiving a request to store a data object comprising a first plurality of partitions, each partition of the first plurality of partitions having a first partition size selected by a requestor associated with the request;

verifying the data object using a data verification algorithm to generate a first verification value based at least in part on the first partition size, wherein the first verification value is derived from a second verification value generated based at least in part on at least two of the first plurality of partitions;

storing the data object and the first verification value;

partitioning the data object into a second plurality of partitions, each partition of the second plurality of partitions having a second partition size different than the first partition size; and

verifying the data object using the data verification algorithm by at least;

generating a third verification value based at least on the second partition size; and

comparing the third verification value with the first verification value.

2. The computer-implemented method of claim 1, wherein the data verification algorithm generates the second plurality of partitions from the data object.

3. The computer-implemented method of claim 2, wherein the first partition size is an integer multiple of the second partition 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 3, wherein the data verification algorithm determines the integer multiple.

6. The computer-implemented method of claim 1, wherein the first partition size selected by the requestor is part of the request.

7. A system, comprising at least one computing device configured to implement one or more services, wherein the one or more services at least:

receive a selection for a first partition size for a data object;

generate, based at least in part on a first verification value generated based at least in part on at least two partitions of the data object partitioned according to the first partition size, a second verification value;

generate a third verification value for the data object according to a second partition size for the data object, the second partition size differing from the first partition size; and

provide, to an entity from which the selection was received, a verification of the data object based at least in part on a comparison of the second verification value and the third verification value.

8. The system of claim 7, wherein the one or more services further generate a first plurality of partitions according to the first partition size.

9. The system of claim 7, wherein the one or more services further generate a second plurality of partitions according to the second partition size.

10. The system of claim 7, wherein the second partition size is an integer multiple of the first partition size.

11. The system of claim 7, wherein 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 further:

perform a first data operation based at least in part on the first partition size;

use the second 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 partition size.

13. The system of claim 12, wherein the first data operation includes 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, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:

obtain a first verification value for a data object according to a first partition size selected by a requestor;

use a data verification algorithm to generate a second verification value, the second verification value being derived from a third verification value generated based at least in part on at least two partitions of the data object partitioned based at least in part on a second partition size for the data object, the second partition size being different than the first partition size;

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

provide an outcome of verifying the data object to the requestor.

15. The non-transitory computer-readable storage medium of claim 14, wherein 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 executable instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to perform a data storage operation based at least in part on the second partition size, wherein 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 value matches the first verification value as a result of the second verification value being equal to 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 the first partition size is a uniform size of each partition of a plurality of partitions of the data object.