Eventually durable redundancy encoded data storage

• US 9,792,179 B1
• Filed: 07/06/2015
• Issued: 10/17/2017
• Est. Priority Date: 07/06/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Lazier, Colin Laird
• Primary Examiner(s): McMahon, Daniel
• Application Number:
  US14/792,031
• Time in Patent Office: 834 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

Techniques for making storage of data objects eventually durable using redundancy encoding are described herein. Data objects are stored in a first set of data storage devices with a first durability. After a predetermined length of time, the data objects are converted to data shards and distributed to a second set of data storage devices with a second durability that is distinct from the first durability.

Claims

1. A computer-implemented method, comprising:

receiving, at a data storage service, a set of data objects over an interval of time;

storing, on at least one device of the data storage service, each data object of the set of data objects with a first durability;

selecting a subset of the set of the data objects that have been stored for at least a predetermined length of time with the first durability; and

changing durability of the subset of the set of data objects by at least;

applying a first redundancy encoding technique to generate, based at least in part on the selected subset of the set of data objects, a set of data shards; and

storing the set of data shards among a plurality of data storage devices such that the selected subset of the set of data objects is stored with at least a second durability that is different from the first durability.

2. The computer-implemented method of claim 1, wherein the first redundancy encoding technique is a bundle encoding technique.

3. The computer-implemented method of claim 1, wherein the first redundancy encoding technique is a grid encoding technique.

4. The computer-implemented method of claim 1, wherein the first durability is based at least in part on generating one or more copies of the set of data objects and storing, at the data storage service, the one or more copies of the set of data objects.

5. The computer-implemented method of claim 1, wherein the first durability is based at least in part on encoding the set of data objects using a second redundancy encoding technique that is different from the first redundancy encoding technique.

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

store a set of data objects using a first set of data storage devices, each data storage device of the first set of data storage devices having a first durability; and

after the set of data objects are stored with the first durability at least a determined length of time, at least;

apply a redundancy encoding technique to generate a set of data shards based at least in part on a subset of the set of data objects; and

store the set of data shards on a second set of data storage devices such that the subset of the set of data objects is stored with a second durability that is distinct from the first durability.

7. The system of claim 6, wherein the determined length of time is based at least in part on the first durability.

8. The system of claim 6, wherein the determined length of time is based at least in part on a number of changes made to the set of data objects during the storage of the set of data objects using the first set of data storage devices.

9. The system of claim 6, wherein each data object of the subset of the set of data objects is selected based at least in part on a corresponding number of changes made to the data object during the determined length of time.

10. The system of claim 6, wherein the set of data shards is distributed to a plurality of datacenter locations.

11. The system of claim 6, wherein one or more data storage devices of the first set of data storage devices is a magnetic disk and one or more data storage devices of the second set of data storage devices is a magnetic tape.

12. The system of claim 6, wherein the one or more services are configured to fulfill an application programming interface request to retrieve a selected data object of the set of data objects by retrieving the selected data object from the first set of data storage devices if the application programming interface request is received before the determined length of time.

13. The system of claim 6, wherein the one or more services are configured to fulfill an application programming interface request to retrieve a selected data object of the set of data objects by retrieving the selected data object from the second set of data storage devices if the application programming interface request is not received before the determined length of time.

14. The system of claim 6, wherein the second durability is greater than the first durability.

15. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of execution by one or more processors of a computer system, cause the computer system to at least:

select, from a set of data objects stored with a first durability using a first set of data storage devices provided by a data storage service, a subset of the set of data objects that have been stored with the first durability for at least a predetermined length of time; and

perform one or more operations that cause a set of data shards to be stored among a second set of data storage devices provided by the data storage service, each data shard of the set of data shards generated by applying a corresponding redundancy encoding technique to the subset of the set of data objects, the set of data shards stored among the set of data storage devices such that the subset of the set of data objects is stored with at least a second durability that is distinct from the first durability.

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

the first durability is based at least in part on a failure rate of the first set of data storage devices; and

the second durability is based at least in part on a failure rate of the second set of data storage devices.

17. The non-transitory computer-readable storage medium of claim 15, wherein the instruction that cause the computer system to select the subset of the set of data objects further include instructions that, as a result of execution by the one or more processors of the computer system, cause the computer system to select the subset of the set of data objects based at least in part on one or more events received by the computer system.

18. The non-transitory computer-readable storage medium of claim 15, wherein:

the redundancy encoding technique is a bundle encoding technique, comprising;

process a plurality of archives to be stored on a plurality of volumes to generate a plurality of shards, the plurality of shards including a set of encoded shards having data derived from at least a subset of the plurality of archives and a set of identity shards having at least a subset of original data of the plurality of archives, by at least;

determine which archives of the plurality of archives will be stored on each volume of the plurality of volumes;

generate the set of identity shards to be stored on the plurality of volumes by apportioning the original data of the plurality of archives to each identity shard of the set of identity shards according to a respective volume of the plurality of volumes to which the archives will be stored;

apply a redundancy code to the plurality of archives to generate the set of encoded shards; and

store the set of identity shards and the set of encoded shards on corresponding volumes of the plurality of volumes; and

the second durability is determined based at least in part on applying the bundle encoding technique to a set of shards, the set of shards at least including;

the set of data shards; and

a set of derived shards associated with the set of data shards.

19. The non-transitory computer-readable storage medium of claim 15, wherein:

the redundancy encoding technique is a grid encoding technique, comprising;

generating a grid of shards, the grid of shards forming a data set, the grid of shards being indexed by at least a first index and a second index, and the grid of shards comprising a set of data shards and a set of derived shards, the set of derived shards comprising a set of horizontally-derived shards and a set of vertically-derived shards, wherein;

the data set includes one or more shards containing one or more portions of the data set and one or more shards generated by applying an erasure code to the one or more shards containing the one or more portions of the data set; and

each shard of the grid of shards has a corresponding first index and corresponding second index and is configured such that;

the shard is reproducible from other shards associated with the first index and reproducible from other shards associated with the second index;

if the shard is a horizontally-derived shard of the set of horizontally-derived shards, the shard is derived based at least in part on a set of data shards associated with the first index; and

if the shard is a vertically-derived shard of the set of vertically derived shards, the shard is derived based at least in part on a set of shards associated with the second index; and

the second durability is determined based at least in part on applying the grid encoding technique to a set of shards, the set of shards at least including;

the set of data shards;

a set of horizontal derived shards associated with the set of data shards; and

a set of vertical derived shards associated with the set of horizontal derived shards.

20. The non-transitory computer-readable storage medium of claim 15, wherein the instructions that cause the computer system to store, with a first durability, each data object of the set of data objects using a first set of data storage devices provided by the data storage service, further comprise instructions that cause the computer system to:

generate a first data shard from the set of data objects;

store the first data shard using the first set of data storage devices provided by the data storage service; and

add one or more data objects from the first shard to one or more data shards of the set of data shards.

21. The non-transitory computer-readable storage medium of claim 20, wherein the set of data shards is distributed to a plurality of datacenter locations.

22. The non-transitory computer-readable storage medium of claim 15, wherein:

each data storage device of the first set of data storage devices is at least one of;

magnetic tape, magnetic disk, optical disk, memory resistor, or computer memory; and

each data storage device of the second set of data storage devices is at least one of;

magnetic tape, magnetic disk, optical disk, memory resistor, or computer memory.

23. The non-transitory computer-readable storage medium of claim 15, wherein the second durability is less than the first durability.

24. The non-transitory computer-readable storage medium of claim 15, wherein:

the set of data objects stored with a first redundancy using the first set of data storage devices provided by the data storage service; and

the set of data shards is distributed such that the subset of the set of data objects is stored with a second redundancy that is distinct from the first redundancy.

25. The non-transitory computer-readable storage medium of claim 24, wherein the second redundancy is greater than the first redundancy.