Device type differentiation for redundancy coded data storage systems

• US 10,009,044 B1
• Filed: 06/17/2015
• Issued: 06/26/2018
• 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,687
• Time in Patent Office: 1,105 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/1469 Backup restoration techniques
• 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/25 Integrating or interfacing systems involving database management systems
• 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
• 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 16/909 using geographical or spatial information, e.g. location spatiotemporally dependent retrieval from the web G06F16/9537
• 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/0428 : wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• 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 for data archives stored on data storage systems using redundancy coding techniques by placing different processed portions of the data in disparate systems. For example, redundancy coded shards, which may include identity shards that contain unencoded original data of archives, may be stored on different types of systems 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:

storing a plurality of archives by at least;

generating 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 plurality of 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 of the plurality of archives;

causing the identity shards to be stored on at least a first data storage system, the first data storage system having greater performance capabilities than a second data storage system; and

causing the encoded shards to be stored on at least the second data storage system, the second data storage system having a lower failure rate than the first data storage system; and

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

locating, in the first data storage system, a respective identity shard corresponding to the requested archive; and

retrieving the located respective identity shard so as to retrieve the requested archive.

2. The computer-implemented method of claim 1, wherein the data storage system is a programmatically accessible data storage service.

3. The computer-implemented method of claim 1, wherein the performance capabilities include at least read throughput.

4. The computer-implemented method of claim 1, further comprising, in response to receiving the request for the archive, determining whether the first data storage system 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 redundancy coded shards, a minimum quorum quantity of the redundancy coded shards in the set being usable, by a redundancy code, to generate original data of the plurality of archives, the set of redundancy coded shards including at least some identity shards that contain the original data of the plurality of archives;

cause storage of the identity shards on at least a first data storage system accessible to the at least one computing device;

cause storage of a remainder of the set of redundancy coded shards on at least a second data storage system that differs from the first data storage system; and

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

cause the first data storage system to locate a corresponding identity shard; and

cause retrieval of the located corresponding identity shard.

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

7. The system of claim 5, wherein each shard of the set of redundancy coded shards is associated with a different data storage system.

8. The system of claim 5, wherein the first data storage system is accessible to the at least one computing device via a programmatic interface.

9. The system of claim 8, wherein the services are further configured to locate the corresponding identity shard using the programmatic interface.

10. The system of claim 8, wherein the services are further configured to retrieve the corresponding identity shard using the programmatic interface.

11. The system of claim 5, wherein the first data storage system having greater performance capabilities has a higher random access capability than at least the second data storage system.

12. The system of claim 5, wherein the services are further configured to receive the request for the original data from a customer of the system via a programmatic interface.

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

generate, from received archives and using a redundancy code, a set of shards, a minimum quorum quantity of the redundancy coded shards in the set being usable to generate any unavailable shard within the set of redundancy coded shards, the set of redundancy coded shards including identity shards that contain original data of the plurality of received archives;

cause storage of the identity shards on at least a first data storage system accessible to the computer system;

cause storage of a remainder of the set of redundancy coded shards on at least a second data storage system geographically separate from the first data storage system; and

respond to requests for archive retrieval by at least;

causing the first data storage system to locate a corresponding identity shard; and

causing retrieval of the located corresponding identity shard.

14. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to receive the received archives in connection with storage requests received via a programmatic interface of the computer system.

15. The non-transitory computer-readable storage medium of claim 13, wherein the first data storage system has a shorter average time-to-retrieval capability than the second data storage system.

16. The non-transitory computer-readable storage medium of claim 13, wherein each of the set of redundancy coded shards is stored in a separate data storage device, each of which is stored in a physically separate data storage facility.

17. The non-transitory computer-readable storage medium of claim 13, wherein the first data storage system and the second data storage system have different 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 data storage system is associated with a first data storage facility separate from the computer system.

20. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, provide the requested archive to a customer of the computer system via the programmatic interface.