Device type differentiation for redundancy coded data storage systems

• US 9,838,041 B1
• Filed: 06/17/2015
• Issued: 12/05/2017
• Est. Priority Date: 06/17/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): Tabone, Jr., John J
• Application Number:
  US14/742,685
• Time in Patent Office: 902 Days
• Field of Search: 714774, 714769, 714763, 714770, 714 622, 714 624, 714 612, 714 48, 714 54, 711114, 711129, 711148
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 11/1072 in multilevel memories
• 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/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 11/167 Error detection by comparing the memory output
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 21/606 by securing the transmission between two devices or processes
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with RAID systems with parity
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 63/08 : for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1097 : for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Techniques described and suggested herein include systems and methods for optimizing performance characteristics by differentiating data storage device types for data archives stored on data storage systems using redundancy coding techniques. For example, redundancy coded shards, which may include identity shards that contain unencoded original data of archives, may be stored on different types of data storage devices to optimize for various retrieval use cases and implemented environments. Implementing systems may monitor various performance characteristics so as to adaptively account for changes to some or all of the monitored parameters.

Claims

1. A computer-implemented method, comprising:

receiving a plurality of archives associated with a plurality of volumes for storage on a plurality of storage devices;

generating a set of shards representing the plurality of volumes, a minimum quorum quantity of the shards in the set being usable, by a redundancy code, to generate original data of the archives, the set of shards including at least;

identity shards that contain the original data of the plurality of archives; and

encoded shards representing an encoded form of the original data; and

storing the set of shards on the plurality of storage devices such that the identity shards are stored on a subset of the plurality of storage devices having a different performance capability than that of a remainder of the plurality of storage devices; and

in response to receiving a request for an archive among the stored plurality of archives, at least;

determining a volume of the plurality of volumes associated with the archive;

determining an identity shard associated with the archive and the volume; and

retrieving the archive using the determined identity shard, a corresponding storage device of the subset of the plurality of storage devices, and the different performance capability.

2. The computer-implemented method of claim 1,

wherein each storage device of the plurality of storage devices is a different data storage facility.

3. The computer-implemented method of claim 1, wherein the subset having the different performance capability includes at least one device type selected from the group consisting of solid state disks, tape drives, hard disk drives, and optical disks.

4. The computer-implemented method of claim 1, further comprising, in response to receiving the request for the archive, determining whether the subset of the plurality of storage devices is capable of completing retrieval of the requested archive within a predetermined timeframe.

5. A system, comprising:

at least one computing device that implements one or more services, wherein the one or more services at least;

process a plurality of archives to generate a set of shards, a minimum quorum quantity of the shards in the set being usable, by a redundancy code, to generate original data of the archives, the set of shards including at least some identity shards that contain the original data of the plurality of archives;

store the set of shards on a plurality of storage devices associated with the system, a subset of the plurality of storage devices having a different performance capability than at least one other storage device of the plurality of storage device; and

in response to receiving a request for an archive of the plurality of archives, at least;

determine a storage device of the subset of the plurality of storage devices associated with an identity shard corresponding to the archive; and

retrieve, using the storage device, the identity shard, and the different performance capability, the requested archive.

6. The system of claim 5, wherein each shard of the set of shards is stored on a respective volume of a set of volumes associated with the system.

7. The system of claim 6, wherein each respective volume of the set of volumes is associated with a respective storage device of the plurality of storage devices associated with the system.

8. The system of claim 7, wherein each storage device of the plurality of storage devices is a data storage facility.

9. The system of claim 5, wherein the one storage device having the different performance capability has a higher random access capability than at least some of the other storage devices of the plurality.

10. The system of claim 5, wherein the subset of the plurality of storage devices having the different performance capability has a lower failure rate than the at least one other storage device.

11. The system of claim 5, wherein the services augment the retrieval of the requested archive from the identity shard by generating, in parallel with the retrieval, the requested archive from encoded shards in the plurality of shards.

12. The system of claim 5, wherein the services further receive the request from a customer device associated with the system via a programmatic interface associated with the one or more services.

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

generate, from archives received by the computer system, a set of shards, a minimum quorum quantity of the shards in the set being usable, by a redundancy code, to generate original data of the archives, the set of shards including at least some identity shards that contain the original data of the archives;

store the identity shards on a first set of storage devices having a differing performance capability than a second set of storage devices;

store a remainder of the set of shards on the second set of storage devices; and

in response to receiving a request for retrieving an archive of the archives;

determine a storage device of the first set of storage devices that stores a subset of the identity shards associated with the archive; and

retrieve, using the storage device, the subset of the identity shards, and the differing performance capability, the archive.

14. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, upon execution by the one or more processors, cause the computer system to receive the archives in connection with storage requests for the archives.

15. The non-transitory computer-readable storage medium of claim 13, wherein the performance capability is selected from the group consisting of data security capability, random access capability, sequential throughput capability, cost, and storage media durability.

16. The non-transitory computer-readable storage medium of claim 13, wherein each shard of the set of shards is stored on a separate storage device.

17. The non-transitory computer-readable storage medium of claim 13, wherein the first set of storage devices and the second set of storage devices have differing random access performance characteristics.

18. The non-transitory computer-readable storage medium of claim 13, wherein the redundancy code is an erasure code.

19. The non-transitory computer-readable storage medium of claim 13, wherein the first set of storage devices is associated with a first data storage facility.

20. The non-transitory computer-readable storage medium of claim 19, wherein the second set of data storage device is associated with a second data storage facility that is in a geographically different location than the first data storage facility.