Cycled clustering for redundancy coded data storage systems

• US 10,366,062 B1
• Filed: 03/28/2016
• Issued: 07/30/2019
• Est. Priority Date: 03/28/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Lazier, Colin Laird, Brock, Adam Frederick, Kirschner, James Caleb
• Primary Examiner(s): Fleurantin, Jean B
• Application Number:
  US15/083,125
• Time in Patent Office: 1,219 Days
• Field of Search: 707664
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A cluster of data transfer devices is used to augment the capabilities of a data storage system. For example, the cluster of data transfer devices may be configured to store a portion of a bundle of redundancy coded shards in a similar fashion as a data storage system. As another example, the cluster may be configured to provide other capabilities incident to the devices used, such as computational capabilities. Data stored on the cluster may be read from and written directly to the cluster without transfer of data to the data storage system. In some embodiments, a connecting entity (such as a customer entity) may interchangeably interface with the data storage system and the cluster, and the requested capabilities may be directed to either in a fashion that is transparent to the requestor.

Claims

1. A computer-implemented method, comprising:

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

configuring a data storage system to at least;

apportion at least a first bundle of redundancy coded shards and a second bundle of redundancy coded shards between a plurality of data transfer devices provisioned by the data storage system to be capable of processing data storage requests and data retrieval requests without a network connection between the plurality of data transfer devices and the data storage system, the first bundle including at least a first identity shard, a second identity shard, and a first derived shard, the first bundle being configured such that a first quorum quantity of shards of the first bundle is sufficient to reconstruct, using a redundancy code, original data associated with the first identity shard, the second bundle including the second identity shard, a second derived shard, and a third identity shard, the second bundle being configured such that a second quorum quantity of shards of the second bundle is sufficient to reconstruct, using the redundancy code, the second identity shard, the first bundle and second bundle overlapping by virtue of both including the second identity shard; and

configure a fill pattern such that the first identity shard, the second identity shard, and the third identity shard are subject to receiving data for storage in a specified order comprising, sequentially, the first identity shard, the second identity shard, and the third identity shard;

monitoring the plurality of data transfer devices to detect an event associated with the first identity shard that indicates an inability to accept additional data; and

if the event is detected, at least;

configuring any data storage requests to store associated data in the second identity shard;

initiating an ingestion process of the data storage system to transfer, by a data transfer device of the plurality of data transfer devices, data associated with the first identity shard to durable storage of the data storage system;

verifying that the data associated with the first identity shard is durably stored in the data storage system; and

if verified that the data associated with the first identity shard is durably stored, at least;

deleting the first identity shard and the first derived shard;

generating a third bundle comprising a fourth identity shard, the third identity shard, and a third derived shard, the third bundle overlapping with the second bundle by virtue of sharing the third identity shard; and

adding the fourth identity shard to the specified order of the fill pattern after the third identity shard.

2. The computer-implemented method of claim 1, wherein each of the shards of the first bundle and the second bundle are stored on a different data transfer device of the plurality of data transfer devices.

3. The computer-implemented method of claim 1, wherein at least two shards of the first bundle or the second bundle are stored on a data transfer device of the plurality of data transfer devices.

4. The computer-implemented method of claim 1, wherein at least one of the data transfer devices of the plurality of data transfer devices is reused for either the fourth identity shard or the third derived shard after either the first identity shard or the first derived shard is deleted therefrom.

5. The computer-implemented method of claim 4, wherein the plurality of data transfer devices is monitored by an entity of the plurality of data transfer devices to detect the event.

6. The computer-implemented method of claim 1, wherein the ingestion process is initiated in connection with physical co-location of the data transfer device with the data storage system.

7. The computer-implemented method of claim 1, wherein the ingestion process is initiated such that the data associated with the first identity shard is transferred from the plurality of data transfer devices to the data storage system over a network between at least one of the data transfer devices and the data storage system.

8. The computer-implemented method of claim 1, wherein the first quorum quantity includes all shards in the first bundle other than the first identity shard.

9. The computer-implemented method of claim 1, wherein the redundancy code is a linear erasure code.

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

provision a first plurality of data transfer devices to store at least a first bundle of redundancy coded shards and a second bundle of redundancy coded shards, the first bundle including at least a first identity shard, a second identity shard, and a first derived shard, the first bundle being configured such that a first quorum quantity of shards of the first bundle is sufficient to reconstruct, using a redundancy code, original data associated with the first identity shard, the second bundle including the second identity shard, a second derived shard, and a third identity shard, the second bundle being configured such that a second quorum quantity of shards of the second bundle is sufficient to reconstruct, using the redundancy code, the second identity shard, the first bundle and second bundle overlapping by virtue of both including the second identity shard;

monitor data transfer devices associated with the first bundle for an event associated with the first identity shard; and

if the event is detected, at least;

store data associated with data storage requests received after the event on a data transfer device associated with the second identity shard;

transfer data associated with the first identity shard from the data transfer device to a data storage system;

delete the first identity shard and the first derived shard; and

provision a second plurality of data transfer devices to store a third bundle comprising a fourth identity shard, the third identity shard, and a third derived shard, the third bundle overlapping with the second bundle by virtue of sharing the third identity shard.

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

in response to a retrieval request for a set of data associated with the first identity shard after the event;

if the first identity shard is available, service the retrieval request by at least retrieving the set of data from the first identity shard; and

if the first identity shard is unavailable, service the retrieval request by regenerating the set of data, using the redundancy code, from the quorum quantity of other shards of the first bundle.

12. The system of claim 11, wherein if the transfer of the data has taken place and the first identity shard and the first derived shard have been deleted, service the retrieval request using the data storage system.

13. The system of claim 10, wherein the data storage system is a data transfer device outside of the first plurality or the second plurality of data transfer devices.

14. The system of claim 10, wherein the data storage system is an archival data storage service.

15. The system of claim 10, wherein the second plurality of data transfer devices comprises the data transfer devices on which the first identity shard and the first derived shard were stored prior to deletion.

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

generate at least a first bundle of redundancy coded shards and a second bundle of redundancy coded shards, the first bundle including at least a first identity shard, a second identity shard, and a first derived shard, the first bundle being configured such that a first quorum quantity of shards of the first bundle is sufficient to reconstruct, using a first redundancy code, original data associated with the first identity shard, the second bundle including the second identity shard, a second derived shard, and a third identity shard, the second bundle being configured such that a second quorum quantity of shards of the second bundle is sufficient to reconstruct, using a second redundancy code, the second identity shard, the first bundle and second bundle overlapping by virtue of both including the second identity shard;

monitor the first bundle for an event associated with the first identity shard; and

if the event is detected, at least;

store data associated with data storage requests received after the event in the second identity shard;

transfer data associated with the first identity shard to a data storage system;

delete the first identity shard and the first derived shard; and

generate a third bundle comprising a fourth identity shard, the third identity shard, and a third derived shard, the third bundle overlapping with the second bundle by virtue of sharing the third identity shard.

17. The non-transitory computer-readable storage medium of claim 16, wherein the first redundancy code and the second redundancy code are the same redundancy code.

18. The non-transitory computer-readable storage medium of claim 16, wherein the instructions further cause the computer system to transfer the data from the first identity shard to the data storage system over the Internet.

19. The non-transitory computer-readable storage medium of claim 16, wherein the data storage system is not physically co-located with the computer system.

20. The non-transitory computer-readable storage medium of claim 16, wherein the first redundancy code and the second redundancy code are linear erasure codes.