Range retrievals from archived data objects according to a predefined hash tree schema

• US 9,223,789 B1
• Filed: 03/14/2013
• Issued: 12/29/2015
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Lazier, Colin Laird, Seigle, Mark Christopher, Tirdad, Kamran
• Primary Examiner(s): Hoang, Son T
• Application Number:
  US13/827,137
• Time in Patent Office: 1,020 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446

Abstract

Ranges of data stored within archived data may be retrieved according to a predefined hash tree schema. A retrieval request for a range of one or more data chunks of an archived data object stored in archival data store may be retrieved. In response, the requested range of the archived data object may be determined to be tree-hash aligned. In response to determining that the requested range is tree-hash aligned, a retrieval job may be initiated to obtain the range of one or more data chunks and to stage the one or more data chunks for download. A download request may for one or more of the obtained and staged data chunks, and if determined to be tree-hash aligned, a tree hash root node may be sent to the requesting client in addition to the requested data.

Claims

1. An archive data storage system, comprising:

one or more computer processors configured to implement;

an archive data storage back end, configured to store one or more archived data objects, wherein each of the archived data objects is organized according to a plurality of data chunks, wherein each data chunk corresponds to a range of data stored within the archived data object;

an archive data storage front end, configured to;

receive a retrieval request for a range of one or more data chunks of an archived data object, wherein the range of the one or more data chunks is less than the entire archived data object;

in response to receiving the retrieval request;

determine that, when a root node of a hash tree for the requested range is equivalent to a predefined hash tree schema for the entire archived data object, the range of the one or more data chunks is tree-hash aligned;

initiate a retrieval job to obtain the one or more data chunks of the archived data object from the archive data storage system back end; and

stage the obtained one or more data chunks in the archive data storage front end for download;

upon completion of the retrieval job to obtain the one or more data chunks of the archived data object from the archive data storage back end, send a retrieval job completion notification to a client;

receive a download request from the client for at least some of the range of the one or more data chunks; and

in response to receiving the download request;

determine whether a root node of a hash tree for the requested download of the at least some of the range of the one or more data chunks is equivalent to a node of the predefined hash tree schema for the entire archived data object in order to determine whether the root node of the hash tree for the requested download is tree-hash aligned; and

send to the client one or more data chunks matching the at least some of the range and, when the root node of the hash tree for the requested download being tree-hash aligned, a hash value of a root node of a tree hash calculated according to the predefined hash tree schema for the at least some of the range of the one or more data chunks.

2. The system of claim 1, wherein the archive data storage front end is further configured to:

receive another retrieval request for another range of other one or more data chunks of the archived data object, wherein the other range of the other one or more data chunks is less than the entire archived data object;

in response to receiving the other retrieval request;

determine that a root node of a hash tree for the requested other range is not equivalent to a node of the predefined hash tree schema for the entire archived data object in order to determine that the other range of the other one or more data chunks is not tree-hash aligned;

initiate another retrieval job to obtain the other one or more data chunks of the archived data object from the archive data storage back end; and

stage the other obtained one or more data chunks in the archive data storage front end for download;

upon completion of the retrieval job to obtain the other one or more data chunks of the archived data object from the archive data storage back end, send a retrieval job completion notification to the client;

receive a download request from the client for at least some of the other range of the other one or more data chunks;

in response to receiving the download request, sending to the client one or more data chunks matching the at least some of the other range without sending a root node of a tree hash calculated according to the predefined hash tree schema for the at least some of the other range of the other one or more data chunks.

3. A method, comprising:

performing, by multiple computing devices;

receiving a retrieval request, from a client, for a range of one or more data chunks of an archived data object stored in an archival data store, wherein

the archived data object is organized as a plurality of data chunks including the one or more data chunks,

each data chunk of the plurality of data chunks corresponds to a range of data stored within the archived data object, and

the range of one or more data chunks is less than the entire archived data object;

in response to receiving the retrieval request;

determining that the requested range of the archived data object is tree-hash aligned with the archived data object based, at least in part, on a node of a hash tree for the requested range being equivalent to a node of a predefined hash tree schema for the archived data object; and

initiating a retrieval job to obtain one or more data chunks of the archived data object matching the requested range from the archival data store;

receiving a download request from the client for at least some of the range of the one or more data chunks; and

in response to the receiving the download request;

determining whether a root node of a hash tree for the requested download of the at least some of the range of the one or more data chunks is equivalent to a node of the predefined hash tree schema for the entire archived data object in order to determine whether the root node of the hash tree for the requested download is tree-hash aligned; and

sending to the client one or more data chunks matching the at least some of the range and, when the root node of the hash tree for the requested download being tree-hash aligned, a hash value of a root node of a tree hash calculated according to the predefined hash tree schema for the at least some of the range of the one or more data chunks.

4. The method of claim 3, the method further comprising:

in response to the initiating the retrieval job to obtain the requested one or more data chunks of the archived data object from the archival data store;

staging the obtained one or more data chunks for download.

5. The method of claim 4, further comprising, upon completion of the retrieval job to obtain the requested range of the one or more data chunks of the archived data object, providing notification that the retrieval job is complete to the client.

6. The method of claim 4, further comprising, in response to receiving the retrieval request for the range of the one or more data chunks of the archived data object, sending a retrieval job identifier that identifies the retrieval job initiated to obtain the requested range of the one or more data chunks of the archived data object from the archival data store.

7. The method of claim 6, further comprising:

receiving another download request including the retrieval job identifier for at least some other ones of the requested range of the one or more data chunks; and

in response to receiving the other download request;

determining that the other download request for the at least some other ones of the requested range of the one or more data chunks of the archived data object is tree-hash aligned with the archived data object based, at least in part, on the predefined hash tree schema for the archived data object; and

sending one or more data chunks matching the at least some other ones of the requested range and a root node of a tree hash calculated according to the predefined hash tree schema for the at least some other ones of the requested range of the one or more data chunks.

8. The method of claim 4, further comprising:

receiving another retrieval request for another range of one or more data chunks of the archived data object, wherein the other range of one or more data chunks is less than the entire archived data object;

in response to receiving the other retrieval request;

determining that the other requested range of the archived data object is not tree-hash aligned with the entire archived data object based, at least in part, on the predefined hash tree schema for the archived data object;

initiating another retrieval job to obtain one or more data chunks of the archived data object matching the other requested range from the archival data store and staging the obtained one or more data chunks of the other requested range for download; and

upon completion of the retrieval job, sending a retrieval job completion notification for the other retrieval job to the client.

9. The method of claim 8, further comprising:

receiving a download request for at least some of the other requested range of the one or more data chunks; and

in response to receiving the download request, sending one or more data chunks matching the at least some of the other requested range without sending a root node of a tree hash calculated according to the predefined hash tree schema for the at least some of the other requested range of the one or more data chunks.

10. The method of claim 4, wherein:

the multiple computing devices are implemented as part of a network-based archive data storage service,

the archived data object is one of a plurality of different archived data objects stored in the archival data store,

a plurality of different customer accounts for one or more network-based services including the network-based archive data storage service are linked to the plurality of different archived data objects, and

the client is authorized to access the archived data object via a customer account of the plurality of different customer accounts linked to the archived data object.

11. The method of claim 10, wherein the method further comprises:

in response to the completion of the retrieval job for the requested range of the one or more data chunks of the archived data object;

determining a data retrieval metric based, at least in part, on the one or more data chunks retrieved from the archival data store; and

recording a data retrieval service fee for the customer account linked to the archived data object based, at least in part, on the data retrieval metric.

12. A non-transitory, computer-readable storage medium, storing program instructions that when executed by multiple computing devices implements:

receiving a retrieval request, from a client, for a range of one or more data chunks of an archived data object stored in an archival data store, wherein

the archived data object is organized as a plurality of data chunks including the one or more data chunks,

each data chunk of the plurality of data chunks corresponds to a range of data stored within the archived data object, and

the range of the one or more data chunks is less than the entire archived data object;

in response to receiving the retrieval request;

determining that the range of the one or more data chunks of the archived data object is tree-hash aligned with the entire archived data object based, at least in part, on a node of a hash tree for the requested range being equivalent to a node of a predefined hash tree schema for the archived data object;

initiating a retrieval job to obtain one or more data chunks of the archived data object matching the requested range from the archival data store and staging the obtained one or more data chunks for download;

sending a retrieval job identifier to the client that identifies the retrieval job initiated to obtain the requested range of the one or more data chunks of the archived data object; and

upon completion of the retrieval job to obtain the one or more data chunks of the archived data object, sending notification to the client that the retrieval job is complete;

receiving a download request from the client for at least some of the range of the one or more data chunks; and

in response to said receiving the download request;

determining whether a root node of a hash tree for the requested download of the at least some of the range of the one or more data chunks is equivalent to a node of the predefined hash tree schema for the entire archived data object in order to determine whether the root node of the hash tree for the requested download is tree-hash aligned; and

sending to the client one or more data chunks matching the at least some of the range and, when the root node of the hash tree for the requested download being tree-hash aligned, a hash value of a root node of a tree hash calculated according to the predefined hash tree schema for the at least some of the range of the one or more data chunks.

13. The non-transitory, computer-readable storage medium of claim 12, wherein the program instructions when executed by the multiple computing devices further implement:

receiving another download request including the retrieval job identifier for at least some other ones of the requested range of the one or more data chunks; and

in response to receiving the other download request;

determining that the other download request for the at least some other ones of the requested range of the one or more data chunks of the archived data object is not tree-hash aligned with the archived data object based, at least in part, on the predefined hash tree schema for the archived data object; and

sending one or more data chunks matching the at least some other ones of the requested range without sending a root node of a tree hash calculated according to the predefined hash tree schema for the at least some other ones of the requested range of the one or more data chunks.

14. The non-transitory, computer-readable storage medium of claim 13, wherein the program instructions when executed by the multiple computing devices further implement:

receiving another retrieval request for another range of one or more data chunks of the archived data object, wherein the other range of one or more data chunks is less than all of the archived data object, wherein the other range is a different size than the range of the one or more data chunks of the archived data object;

in response to receiving the other retrieval request;

determining that the other requested range of the archived data object is tree-hash aligned with the archived data object based, at least in part, on the predefined hash tree schema for the archived data object;

initiating another retrieval job to obtain one or more data chunks of the archived data object matching the other requested range from the archival data store and staging the obtained one or more data chunks of the other requested range for download;

sending another retrieval job identifier to the client that identifies the other retrieval job; and

upon completion of the other retrieval job, sending another retrieval job completion notification for the other retrieval job to the client.

15. The non-transitory, computer-readable storage medium of claim 13, wherein the archived data object comprises an aggregation of a plurality of separate data files, and wherein the one or more data chunks of the retrieval request comprise one of the plurality of separate data files.

16. The non-transitory, computer-readable storage medium of claim 12, wherein

the multiple computing devices are implemented as part of a network-based archive data storage service,

the archived data object is one of a plurality of different archived data objects stored in the archival data store,

a plurality of different customer accounts for one or more network-based services including the network-based archive data storage service are linked to the plurality of different archived data objects,

the client is authorized to access the archived data object via a customer account of the plurality of different customer accounts linked to the archived data object, and

the program instructions when executed by the multiple computing devices further implement:

in response to the completion of the retrieval job for the requested range of the one or more data chunks of the archived data object;

determining a data retrieval metric based, at least in part, on the one or more data chunks retrieved from the archival data store; and

recording a data retrieval service fee for the customer account linked to the archived data object based, at least in part, on the data retrieval metric.

17. The non-transitory, computer-readable storage medium of claim 16, wherein one or more other retrieval requests are received to retrieve the entire archived data object, wherein data retrieval service fees determined for these retrieval requests summed with the data retrieval service fee are less than a data retrieval service determined based, at least in part, on a data retrieval metric for retrieving the entire archived data object in one retrieval request.