Hybridized storage operation for redundancy coded data storage systems

• US 10,678,664 B1
• Filed: 03/28/2016
• Issued: 06/09/2020
• Est. Priority Date: 03/28/2016
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Lazier, Colin Laird, Kirschner, James Caleb, Brock, Adam Frederick
• Primary Examiner(s): Guyton, Philip
• Application Number:
  US15/083,145
• Time in Patent Office: 1,534 Days
• CPC Class Codes: G06F 11/008 Reliability or availability analysis
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/2069 Management of state, configuration or failover
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0683 Plurality of storage devices

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:

configuring a data storage system to apportion a bundle of redundancy coded shards between at least durable storage of the data storage system and a data transfer device, the bundle including at least a plurality of identity shards, a first identity shard of the plurality of identity shards containing an original form of data stored in the bundle, and an encoded shard containing a redundancy coded form of the data, the bundle being configured such that a quorum quantity of shards of the bundle is sufficient to reconstruct, using a redundancy code, original data associated with the bundle, the bundle being apportioned such that a first subset of the bundle is apportioned to the data transfer device and second subset of the bundle is apportioned to the durable storage, the first subset of the bundle comprising a subset of the plurality of identity shards and excluding the encoded shard, the second subset of the bundle comprising a remainder of the bundle outside of the first subset of the bundle, the number of shards in the second subset being greater than the quorum quantity;

providing the data transfer device to a different physical location than that of the data storage system, the different physical location being associated with a customer of the data storage system, and the data transfer device is in operable communication with the data storage system;

receiving, by the data transfer device at the different physical location, a first set of customer data;

storing, by the data transfer device at the different physical location, the first set of customer data in the first subset of the bundle;

storing, by the durable storage of the data storage system, a second set of customer data in identity shards of the second subset of the bundle;

processing, using the redundancy code, the first set of customer data and the second set of customer data to generate the encoded shard;

storing, by the durable storage, the encoded shard as part of the second subset of the bundle to enable the durable storage to regenerate, from only the second subset of the bundle, the first set of customer data; and

in response to a retrieval request for at least a portion of the first set of customer data;

if the data transfer device is available, service the retrieval request by at least retrieving the portion of the first subset of customer data from the first subset of the bundle; and

if the data transfer device is unavailable, service the retrieval request by at least regenerating the portion of the first subset of customer data, using the redundancy code, from the second subset of the bundle.

2. The computer-implemented method of claim 1, further comprising responding to a second retrieval request for at least a portion of the second set of customer data by at least retrieving the portion of the second set of customer data from the second subset of the bundle.

3. The computer-implemented method of claim 1, further comprising responding a second retrieval request for at least a portion of the second set of customer data by regenerating the portion of the second set of customer data, using the redundancy code, from at least one shard of the first subset of the bundle and at least the encoded shard in the second subset of the bundle.

4. The computer-implemented method of claim 1, further comprising causing the data transfer device to transfer the first set of customer data to the data storage system for storage in the durable storage of the data storage system.

5. The computer-implemented method of claim 4, wherein the data transfer device is caused to transfer the first set of customer data to the data storage system after the data transfer device is physically co-located with the data storage system.

6. The computer-implemented method of claim 1, wherein the data storage system is a first data storage system, and further comprising causing the data transfer device to transfer the first set of customer data to a second data storage system that is different than the first data storage system.

7. The computer-implemented method of claim 1, wherein the data transfer device is operably connected to the data storage system via the Internet.

8. The computer-implemented method of claim 1, wherein the data transfer device is a first data transfer device, and further comprising replacing the first data transfer device with a second data transfer device in connection with information indicating that the first data transfer device is at or above a specified capacity threshold.

9. The computer-implemented method of claim 1, wherein the data transfer device is a first data transfer device, and further comprising, in response to receiving information that the first data transfer device is full, at least:

configuring the bundle to include an additional identity shard;

apportioning the additional identity shard to a second data transfer device;

providing the second data transfer device to the different physical location;

storing a third set of customer data on the second data transfer device; and

using the redundancy code and the third set of customer data, recalculate the encoded shard.

10. The computer-implemented method of claim 1, wherein the data storage system is configured to apportion shards of the bundle differently between the data storage system and the data transfer device such that encoded shards of the bundle are stored at the redundant storage of the data storage system.

11. The computer-implemented method of claim 1, further comprising:

receiving a third set of customer data at the data transfer device; and

updating the encoded shard based at least in part on the redundancy code and the third set of customer data.

12. A system, comprising at least one computing device that implements one or more services, wherein the one or more services at least:

apportion a bundle of redundancy coded shards between at least durable storage of a first data storage system and a second data storage system, the bundle being configured such that a quorum quantity of shards of the bundle is sufficient to reconstruct, using a redundancy code, original data associated with the bundle, the bundle being apportioned such that a first subset of the bundle is apportioned to the durable storage and a second subset of the bundle is apportioned to the second data storage system, the first subset including a number of shards equal to or greater than the quorum quantity of shards;

cause storage of a first set of customer data in the first subset of the bundle apportioned to the durable storage of the first data storage system;

cause storage of a second set of customer data in the second subset of the bundle apportioned to the second data storage system, wherein the second set of customer data is received by the second data storage system while the second data storage system is at a different physical location than the first data storage system, and wherein the second data storage system may, while at the different physical location, communicate with the first data storage system;

process, using the redundancy code, the first set of customer data and the second set of customer data to generate an encoded shard;

store the encoded shard in the first subset of the bundle, wherein the first subset of the bundle is sufficient to enable the first storage system to reconstruct, from only the first subset of the bundle, the second set of customer data;

service a retrieval request for a portion of the second set of customer data, using the redundancy code, from the first subset of the bundle; and

as a result of the second data storage system being moved from the different physical location to the physical location of the data storage system, cause the second data storage system to transfer at least the second set of customer data to the first data storage system for storage in the durable storage of the first data storage system.

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

if the second subset of the bundle is available, service the retrieval request by at least retrieving the second set of customer data from the second subset of the bundle.

14. The system of claim 12, wherein the one or more services are further configured to, in response to a retrieval request for the first set of customer data, if an original form of the first set of customer data is not directly readable from the first subset of the bundle, service the retrieval request by regenerating the first set of customer data, using the redundancy code and at least one shard of the second subset of the bundle.

15. The system of claim 12, wherein the second data storage system is a data transfer device.

16. The system of claim 15, wherein the data transfer device includes persistent storage configured to store the second subset of the bundle.

17. The system of claim 12, wherein the one or more services are further configured to generate the bundle of redundancy coded shards to include at least a plurality of identity shards, a first identity shard of the plurality of identity shards containing an original form of data stored in the bundle, and an encoded shard containing a redundancy coded form of the data.

18. The system of claim 12, wherein the one or more services are further configured to, while the second data storage system is at the different physical location, cause the first data storage system to receive at least the first set of customer data.

19. A non-transitory computer-readable storage medium comprising 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, from a first set of data and a second set of data received by the computer system and using a redundancy code, a plurality of erasure coded shards as a bundle of bundle-encoded shards, the plurality of erasure coded shards being configured such that a quorum quantity of the shards of the plurality of erasure coded shards is sufficient to reconstruct, using the redundancy code, the first set of data and the second set of data;

store the shards of the plurality of erasure coded shards on durable storage of a first data storage system and a second data storage system, such that;

a second subset of the shards includes original data of the first second set of data and is apportioned to the durable storage of the first second data storage system; and

a first subset of the shards includes original data of the first data, a first encoded shard generated from the original data of the first set of data, and a second encoded shard generated from the original data of the second set of data, and is apportioned to the first data storage system to enable the first data storage system to regenerate the second set of data using only the first subset of the shards, wherein the second set of data is received at the second data storage system while the second data storage system is at a different physical location than the first data storage system, and wherein the second data storage system is capable of operable communication with the first data storage system at the different physical location;

service a retrieval request for a portion of the second set of data, using the redundancy code, from the first subset of the shards; and

add a third set of data, received by the first data storage system, to the bundle, by at least adding the third set of data to identity shards in the second subset of the shards and updating the encoded shard in the second subset of the shards using the redundancy code.

20. The non-transitory computer-readable storage medium of claim 19, wherein the instructions further cause the computer system to at least add a fourth set of data, received by the second data storage system, to the bundle, by at least adding the fourth set of data to one or more identity shards of the first subset of the shards.

21. The non-transitory computer-readable storage medium of claim 19, wherein the second data storage system is located on a different network than that of the first data storage system, the first data storage system being on a customer network and acting as a proxy for the second data storage system.

22. The non-transitory computer-readable storage medium of claim 19, wherein the redundancy code is a linear erasure code.

23. The non-transitory computer-readable storage medium of claim 19, wherein the instructions further cause the computer system to at least, as a result the second data storage system being moved to a same physical location of the data storage system, cause the second data storage system to transfer at least the second set of customer data to the first data storage system for storage in the durable storage of the first data storage system.