Transmission time refinement in a storage system

• US 9,672,110 B1
• Filed: 09/22/2015
• Issued: 06/06/2017
• Est. Priority Date: 09/22/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Patel, Rajesh Shanker
• Primary Examiner(s): Chase, Shelly A
• Application Number:
  US14/862,003
• Time in Patent Office: 623 Days
• 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/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G11C 29/4401 for self repair
• CPC Class Codes: G11C 29/50012 of timing
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: G11C 29/74 using duplex memories, i.e. using dual copies
• CPC Class Codes: G11C 29/765 in solid state disks
• 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

Abstract

A storage manager may be used to perform a decoding operation using a transmission time refinement technique on a data object stored in a storage system, such as an object-redundant storage system. The decoding operation may include requesting groups of corresponding blocks from storage devices of the storage system. The storage manager may maintain connections to a connection group of the storage devices and may iteratively request corresponding blocks of the data object from one or more various request groups of the storage devices of the connection group. The storage manager may evaluate performance of the request groups in sending the corresponding blocks of the data object and may modify the membership of the request groups for requests for subsequent blocks of the data object based at least in part on the performance of the request groups.

Claims

1. A system, comprising:

a storage system comprising a plurality of storage devices, wherein the storage system is configured to store a plurality of data objects according to an erasure encoding technique, wherein each respective data object of the plurality of data objects is stored as a shard group, wherein shards of a respective shard group include respective pluralities of blocks such that blocks of the respective data object can be reconstructed from a particular number of corresponding blocks of the data object from a particular number of storage devices, and wherein each shard of the shard group is stored on a different one of the plurality of storage devices than any other shard of the shard group; and

a storage manager implemented by one or more hardware processors and configured to;

receive a request from a client for one of the plurality of data objects;

maintain connections to a connection group of the storage devices that store respective shards of the data object, wherein the connection group includes a greater number of storage devices than the particular number of storage devices needed to reconstruct blocks of the requested data object;

request corresponding blocks of the data object from a request group of the storage devices of the connection group, wherein the request group is a subset of the connection group having fewer than all the storage devices of the connection group and having at least the particular number of the storage devices;

evaluate, based at least in part on performance criteria, performance of the storage devices of the request group in sending the corresponding blocks of the data object;

modify, based at least in part on evaluating the performance of the request group, membership of the request group to form a new request group using at least one different storage device of the connection group;

request subsequent corresponding blocks of the data object from the new request group;

in response to receiving at least the particular number of corresponding blocks from the storage devices of the request group, decode the particular number of corresponding blocks into a reconstructed block of the data object; and

return the reconstructed block of the data object to the client.

2. The system of claim 1, wherein modifying the membership of the request group is performed based at least in part on determining that at least one of the storage devices fails one or more of the performance criteria, and wherein, to modify the membership of the request group, the storage manager is configured to replace the at least one storage device of the request group with the at least one different storage device from the connection group.

3. The system of claim 2, wherein the storage manager is configured to replace the at least one corresponding storage device with the at least one different storage device using one of the maintained connections without performing a connection initiation process after determining that the at least one of the storage devices fails one or more of the performance criteria.

4. The system of claim 1, wherein the storage manager is further configured to:

maintain membership of the request group based at least in part on determining that all of the storage devices meet the performance criteria; and

request the subsequent corresponding blocks of the data object from the request group based at least in part on determining that all of the storage devices meet the performance criteria.

5. The system of claim 1,

wherein the performance criteria includes a threshold throughput, a threshold response latency, a threshold error rate, or any combination thereof,

wherein, to evaluate performance of the storage devices, the storage manager is configured to compare, to the performance criteria, performance data of the storage devices in sending the corresponding blocks of the data object to the storage manager,

wherein the performance data comprises respective throughputs, response latencies, error rates, or any combination thereof.

6. A method, comprising:

performing, by one or more computers;

receiving a request from a client for a data object stored at a storage system according to an erasure encoding technique, wherein blocks of the data object can be reconstructed from a particular number of corresponding blocks from a particular number of storage devices of the storage system;

maintaining connections to a connection group of the storage devices, wherein the connection group includes a greater number of storage devices than the particular number of storage devices needed to reconstruct blocks of the data object;

requesting corresponding blocks of the data object from a request group of the storage devices of the connection group, wherein the request group is a subset of the connection group having fewer than all the storage devices of the connection group and having at least the particular number of the storage devices;

evaluating, based at least in part on performance criteria, performance of the storage devices of the request group in sending the corresponding blocks of the data object;

modifying membership of the request group to form a new request group using at least one different storage device of the connection group; and

requesting subsequent corresponding blocks of the data object from the new request group.

7. The method of claim 6, wherein the storage devices of the storage system include respective shards of the data object, wherein the shards of the data object include respective pluralities of the blocks of the data object, wherein the data object can be reconstructed from a particular number of shards from the particular number of storage devices of the storage system, and wherein each shard of the data object is stored on a different one of the plurality of storage devices than any other shard of the data object.

8. The method of claim 6, wherein evaluating the performance of the storage devices comprises identifying a group of one or more underperforming storage devices, wherein the identifying comprises comparing respective performance data of the storage devices in sending the corresponding blocks of the data object to an absolute threshold of the performance criteria.

9. The method of claim 8, wherein evaluating the performance of the storage devices of the request group further comprises:

determining a relative threshold of the performance criteria based at least in part on one or more of the respective performance data of the storage devices in sending the corresponding blocks of the data object;

comparing the respective performance data of storage devices not identified as being underperforming storage devices to the relative threshold and adding one or more storage devices to the group of one or more underperforming storage devices based on the comparing; and

identifying storage devices not in the group of one or more underperforming storage devices as being performant storage devices.

10. The method of claim 9, wherein modifying the membership of the request group to form the new request group further comprises:

selecting performant storage devices to add to the new request group, wherein the selecting comprises;

determining that a number of the performant storage devices exceeds a number of storage devices needed to form the new request group; and

in response to determining that the number of performant storage devices exceeds the number of storage devices needed to form the new request group, adding performant storage devices to the new request group based at least in part on network locality of the performant storage devices to a storage manager performing the requesting the corresponding blocks of the data object.

11. The method of claim 9, wherein modifying the membership of the request group to form the new request group further comprises:

in response to determining that a number of the performant storage devices is insufficient for the new request group, selecting one or more underperforming storage devices to add to the new request group, wherein the selecting comprises;

adding underperforming storage devices to the new request group having least most recently generated performance data.

12. The method of claim 6,

wherein requesting the corresponding blocks of the data object comprises requesting a particular number of corresponding blocks from each storage device of the request group,

wherein requesting the subsequent corresponding blocks of the data object comprises requesting a different particular number of corresponding blocks from each storage device of the new request group, and

wherein the different particular number of corresponding blocks is larger than the particular number of corresponding blocks.

13. The method of claim 6, further comprising:

evaluating, based at least in part on performance criteria, performance of the storage devices of the new request group in sending the subsequent corresponding blocks of the data object;

modifying membership of the new request group to form an updated new request group using at least one different storage device of the connection group; and

requesting additional subsequent corresponding blocks of the data object from the updated new request group.

14. The method of claim 6, further comprising:

evaluating, based at least in part on one or more performance measures, performance of the storage devices of the new request group in sending at least some of the subsequent corresponding blocks of the data object; and

in response to the new request group failing to meet at least one of the one or more performance measures;

adding at least one different storage device of the connection group to the request group; and

requesting blocks from the at least one different storage device corresponding to at least some of the subsequent corresponding blocks of the data object.

15. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to:

implement a storage manager configured to;

receive a request from a client for a data object stored at a storage system according to an erasure encoding technique, wherein blocks of the data object can be reconstructed from a particular number of corresponding blocks from a particular number of storage devices of the storage system;

maintain connections to a connection group of the storage devices, wherein the connection group includes a greater number of storage devices than the particular number of storage devices needed to reconstruct blocks of the data object;

request corresponding blocks of the data object from a request group of the storage devices of the connection group, wherein the request group is a subset of the connection group having fewer than all the storage devices of the connection group and having at least the particular number of the storage devices;

evaluate, based at least in part on performance criteria, performance of the storage devices of the request group in sending the corresponding blocks of the data object; and

modify membership of the request group to form a new request group using at least one different connection of the connection group; and

request subsequent corresponding blocks of the data object from the new request group.

16. The non-transitory, computer-readable storage medium of claim 15, wherein the storage devices of the storage system include respective shards of the data object, wherein the shards of the data object includes respective pluralities of the blocks of the data object, wherein the data object can be reconstructed from a particular number of shards from the particular number of storage devices of the storage system, and wherein each shard of the data object is stored on a different one of the plurality of storage devices than any other shard of the data object.

17. The non-transitory, computer-readable storage medium of claim 15, wherein the storage manager is further configured to:

in response to receiving at least the particular number of corresponding blocks from the storage devices of the request group, decode the particular number of corresponding blocks into a reconstructed block of the data object,

wherein decoding the particular number of corresponding blocks is performed subsequent to requesting the subsequent corresponding blocks and prior to receiving at least one of the subsequent corresponding blocks.

18. The non-transitory, computer-readable storage medium of claim 17, wherein the storage manager is further configured to:

store the corresponding blocks of the data object received from the request group in an input buffer,

wherein decoding the particular number of corresponding blocks comprises removing the at least the particular number of corresponding blocks from the input buffer, and

wherein requesting the subsequent corresponding blocks of the data object is performed in response to an amount of free space in the input buffer exceeding a request threshold amount.

19. The non-transitory, computer-readable storage medium of claim 18, wherein, to request subsequent corresponding blocks of the data object from the new request group, the storage manager is further configured to determine, based at least in part on the amount of free space in the input buffer, a number of blocks to request from the new request group.

20. The non-transitory, computer-readable storage medium of claim 18, wherein the storage manager is further configured to:

store the reconstructed block of the data object in an output buffer; and

in response to receiving an indication that the client is ready to receive the reconstructed block;

halt decoding a different particular number of corresponding blocks into a different reconstructed block of the data object;

initiate transmission of the reconstructed block to the client; and

resume decoding the different particular number of corresponding blocks into the different reconstructed block.

21. The non-transitory, computer-readable storage medium of claim 18, wherein the storage manager is further configured to:

store the reconstructed block of the data object in an output buffer using a consistency scheme that prevents the reconstructed block from being read from the output buffer until the storage manager finishes storing the reconstructed block to the output buffer.