Archival data flow management

• US 9,563,681 B1
• Filed: 08/08/2012
• Issued: 02/07/2017
• 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: Sun, Weixiang, Patiejunas, Kestutis, Lazier, Colin L., Seigle, Mark C., Donlan, Bryan J.
• Primary Examiner(s): Willoughby, Alicia
• Assistant Examiner(s): Khakhar, Nirav K
• Application Number:
  US13/570,092
• Time in Patent Office: 1,644 Days
• Field of Search: 707/667
• US Class Current: 1/1
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

Methods and systems are provided herein to allow efficient management of data flowing in and out of an archival data storage system. In an embodiment, storage entities keep very little state information in memory to provide higher throughput. Further, storage entities may send data in large chunks to facilitate high throughput. Techniques such as batching and coalescing may be used by various storage entities to provide efficiency.

Claims

1. A computer system for managing data storage, comprising:

a plurality of data storage devices;

a plurality of storage nodes, each of the plurality of data storage nodes being operably connected to one or more of the plurality of data storage devices;

a storage node manager operably connected to the plurality of data storage nodes;

one or more processors;

memory, including executable instructions that, when executed by the one or more processors, cause the one or more processors to collectively at least;

receive, by the storage node manager, a request to store a data object;

obtain, by the storage node manager, the data object to be stored; and

allocate, by the storage node manager, storage space to store a plurality of redundantly encoded data components that are generated using at least one erasure code and based at least in part on the data object to be stored;

for each encoded data component of the plurality of redundantly encoded data components;

generate a data collection that includes at least the encoded data component and redundantly encoded data components associated with another data object, such that the data collection is redundantly encoded; and

provide, by the storage node manager, the encoded data component to a storage node;

after providing the encoded data component, make available storage space allocated to the plurality of encoded data components regardless of whether a response is received from the storage node;

receive, by a storage node, one of the plurality of encoded data components; and

store, by the storage node, the data collection on a storage device connected to the storage node.

2. The computer system of claim 1, wherein allocating storage space includes allocating memory and wherein making available storage space includes deallocating memory.

3. The computer system of claim 1, wherein for each encoded data component of the plurality of redundantly encoded data components, the data collection includes a page.

4. The computer system of claim 1, wherein the data based at least in part on another data object includes one or more encoded data components that are generated based at least in part on the another data object.

5. The computer system of claim 1, wherein the request to store the data object is selected, by the storage node manager, to optimize performance of the system.

6. The computer system of claim 1, wherein the executable instructions, when executed by the one or more processors, further cause the one or more processors to collectively, for each encoded data component of the plurality of redundantly encoded data components, provide a response by the storage node that indicates whether the encoded data component is successfully stored.

7. A computer-implemented method, comprising:

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

receiving a job to store a data object; and

executing the job by at least;

encoding the data object using at least one erasure code so as to obtain a plurality of redundantly encoded data components;

allocating storage space to store the plurality of redundantly encoded data components;

generating a data collection that includes at least the plurality of redundantly encoded data components and redundantly encoded data components associated with another data object, such that the data collection is redundantly encoded;

for each of the plurality of encoded data components, providing the redundantly encoded data component as part of the data collection in a request to store the redundantly encoded data component; and

for at least some of the plurality of redundantly encoded data components, deallocating the allocate storage space for the redundantly encoded data component regardless of whether a response to the request to store the redundantly encoded data component is received.

8. The computer-implemented method of claim 7, wherein for each of the plurality of redundantly encoded data components, providing the redundantly encoded data component in a request to store the redundantly encoded data component includes providing a data collection that includes the redundantly encoded data component and data based at least in part on another data object.

9. The computer-implemented method of claim 8, wherein the data collection includes a page.

10. The computer-implemented method of claim 8, wherein the data based at least in part on another data object includes one or more redundantly encoded data components that are generated based at least in part on the another data object.

11. The computer-implemented method of claim 7, further comprising receiving one or more responses corresponding to one or more of the plurality of redundantly encoded data components.

12. The computer-implemented method of claim 11, further comprising if one of the one or more received responses indicates that a redundantly encoded data component is not stored successfully, causing repetition of the job to store the data object.

13. A computer-implemented method, comprising:

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

receiving a plurality of data storage related requests, at least some of the plurality of data storage related requests specifying at least a data collection that includes a plurality of redundantly encoded data components derived by application of at least one erasure code;

determining a coalesced plurality of data storage related requests based at least in part on the received plurality of data storage related requests, the coalesced plurality of data storage related requests including at least a coalesced request formed based on two or more of the plurality of data storage related requests; and

causing the coalesced plurality of data storage related requests to be fulfilled by one or more storage devices according to a batch processing schedule, by at least generating and storing the data collection to includes at least the plurality of redundantly encoded data components and redundantly encoded data components associated with another data object, such that the data collection is redundantly encoded.

14. The computer-implemented method of claim 13, wherein the data collection includes a page.

15. The computer-implemented method of claim 13, wherein the plurality of redundantly encoded data components are based at least in part one or more data objects.

16. The computer-implemented method of claim 13, wherein determining the coalesced plurality of storage requests is based at least in part on a data size.

17. The computer-implemented method of claim 13, wherein the batch processing schedule is based at least in part on a power management schedule.

18. The computer-implemented method of claim 13, wherein the batch processing schedule is used at least in part to improve efficiency.

19. The computer-implemented method of claim 13, wherein received plurality of data storage related requests comprises requests to perform at least one of data storage, data retrieval, or data deletion.

20. One or more non-transitory computer-readable storage media having collectively stored thereon executable instructions that, when executed by one or more processors of a computer system, cause the computer system to at least:

receive a request to store a data object;

obtain a plurality of redundantly encoded data components based at least in part on the data object and derived using at least one erasure code;

allocate storage space to store the plurality of redundantly encoded data components;

generate a data collection that includes at least the encoded data component and redundantly encoded data components associated with another data object, such that the data collection is redundantly encoded;

for each of the plurality of encoded data components, provide the encoded data component to a storage node as part of the data collection; and

for at least some of the plurality of encoded data components, make available the allocate storage space for the encoded data component regardless of whether a response from the storage node is received.

21. The non-transitory computer-readable storage media of claim 20, wherein the instructions further comprise instructions that, when executed, further cause the computer system to at least:

for each of the plurality of encoded data components, cause storage of the data collection, by the storage node, according to a batch processing schedule.

22. The non-transitory computer-readable storage media of claim 20, wherein the request to store the data object is selected from a plurality of requests according to one or more criteria.

23. The non-transitory computer-readable storage media of claim 21, wherein the instructions further comprise instructions that, when executed, further cause the computer system to at least:

cause the request to store the data object to be repeated if a quorum of responses is not received, the size of the quorum is based at least in part on a redundancy encoding scheme used to obtain the plurality of redundantly encoded data components.

24. The non-transitory computer-readable storage media of claim 21, wherein for each of the plurality of encoded data components, causing storage of the data collection includes causing the data collection to be stored in a multi-tenant storage system.