Reducing write tail latency in storage systems

Abstract

In order to reduce write tail latency, a storage system generates redundant write requests when performing a storage operation for an object. The storage operation is determined to be effectively complete when a minimum number of write requests have completed. For example, the storage system may generate twelve write requests and also generate four redundant write requests for a total of sixteen write requests. The storage system considers the object successfully stored once twelve of the sixteen writes complete successfully. To generate the redundant writes, the storage system may use replication or erasure coding. For replication, the storage system may issue a redundant write request for each of n chunks being written. For erasure coding, the storage system may use rateless codes which can generate unlimited number of parity chunks or use an n+k+k' erasure code which generates an additional k encoded chunks, in place of an n+k erasure code.

What is claimed is: 
     
         1 . A method comprising:
 in response to receiving a first object to be stored, generating a first set of data units based, at least in part, on the first object;   sending each of the first set of data units with a write request to a different one of a plurality of storage devices; and   in response to determining that a minimum number of write requests have completed,
 identifying locations for a subset of the first set of data units which correspond to the completed write requests; and 
 updating an index with an identifier for the first object and the locations of the subset of data units. 
   
     
     
         2 . The method of  claim 1 , further comprising:
 in response to determining that a completion period for the completed write requests exceeds a threshold, increasing a specified number of data units to be generated in response to receiving an object to be stored; and   in response to receiving a second object to be stored, generating a second set of data units based, at least in part, on the second object, wherein a number of data units in the second set of data units is equal to the increased specified number of data units to be generated.   
     
     
         3 . The method of  claim 2 , wherein said generating the second set of data units based, at least in part, on the second object comprises:
 determining an erasure code used to generate the first set of data units; and   modifying the erasure code to generate a number of data units equal to the increased specified number of data units to be generated.   
     
     
         4 . The method of  claim 1 , further comprising:
 generating a second set of data units based, at least in part, on the first object; and   sending each of the second set of data units with a write request to a different one of the plurality of storage devices;   wherein said determining that the minimum number of write requests have completed comprises determining that a number of the completed write requests for the first set of data units added to a number of completed write requests for the second set of data units is equal to the minimum number of the write requests.   
     
     
         5 . The method of  claim 4 , wherein sending each of the second set of data units with a write request to a different one of the plurality of storage devices comprises:
 for each of the second set of data units,
 determining that a write request corresponding to one of the first set of data units failed to complete within a threshold; 
 wherein the data unit is sent in response to determining that the write request corresponding to the one of the first set of data units failed to complete within the threshold. 
   
     
     
         6 . The method of  claim 1 , wherein the minimum number of the write requests is equal to a minimum number of data units required to reconstruct the first object, wherein a number of data units in the first set of data units is equal or greater than a minimum number of data units required to reconstruct the first object. 
     
     
         7 . The method of  claim 1 , further comprising cancelling write requests corresponding to data units not in the subset of data units. 
     
     
         8 . A non-transitory machine readable medium having stored thereon instructions for storing an object comprising machine executable code which when executed by at least one machine, causes the machine to:
 in response to receipt of a first object to be stored, generate a first set of data units based, at least in part, on the first object;   send each of the first set of data units with a write request to a different one of a plurality of storage devices; and in response to a determination that a minimum number of write requests have completed,
 identify locations for a subset of the first set of data units which correspond to the completed write requests; and 
 update an index with an identifier for the first object and the locations of the subset of data units. 
   
     
     
         9 . The machine readable medium of  claim 8 , further comprising machine executable code which when executed by the machine, causes the machine to:
 in response to a determination that a completion period for the completed write requests exceeds a threshold, increase a specified number of data units to be generated in response to receiving an object to be stored; and   in response to receipt of a second object to be stored, generate a second set of data units based, at least in part, on the second object, wherein a number of data units in the second set of data units is equal to the increased specified number of data units to be generated.   
     
     
         10 . The machine readable medium of  claim 9 , wherein the machine executable code which when executed by the machine, causes the machine to generate the second set of data units based, at least in part, on the second object comprise instructions to:
 determine an erasure code used to generate the first set of data units; and   modify the erasure code to generate a number of data units equal to the increased specified number of data units to be generated.   
     
     
         11 . The machine readable medium of  claim 8 , further comprising machine executable code which when executed by the machine, causes the machine to:
 generate a second set of data units based, at least in part, on the first object; and   send each of the second set of data units with a write request to a different one of the plurality of storage devices;   wherein the machine executable code which when executed by the machine, causes the machine to determine that the minimum number of write requests have completed comprise machine executable code which when executed by the machine, causes the machine to determine whether a number of the completed write requests for the first set of data units added to a number of completed write requests for the second set of data units is equal to the minimum number of the write requests.   
     
     
         12 . The machine readable medium of  claim 11 , wherein the machine executable code which when executed by the machine, causes the machine to send each of the second set of data units with a write request to a different one of the plurality of storage devices comprise machine executable code which when executed by the machine, causes the machine to:
 for each of the second set of data units,
 determine whether a write request corresponding to one of the first set of data units failed to complete within a threshold; 
 wherein the data unit is sent in response to a determination that the write request corresponding to the one of the first set of data units failed to complete within the threshold. 
   
     
     
         13 . The machine readable medium of  claim 8 , wherein the minimum number of the write requests is equal to a minimum number of data units required to reconstruct the first object, wherein a number of data units in the first set of data units is equal to or greater than a minimum number of data units required to reconstruct the first object. 
     
     
         14 . A computing device comprising:
 a processor; and   a machine readable medium comprising machine executable code having stored thereon instructions executable by the processor to cause the computing device to:
 in response to receipt of a first object to be stored, generate a first set of data units based, at least in part, on the first object; 
 send each of the first set of data units with a write request to a different one of a plurality of storage devices; and 
 in response to a determination that a minimum number of write requests have completed,
 identify locations for a subset of the first set of data units which correspond to the completed write requests; and 
 update an index with an identifier for the first object and the locations of the subset of data units. 
 
   
     
     
         15 . The computing device of  claim 14 , further comprising machine executable code executable by the processor to cause the computing device to:
 in response to a determination that a completion period for the completed write requests exceeds a threshold, increase a specified number of data units to be generated in response to receiving an object to be stored; and   in response to receipt of a second object to be stored, generate a second set of data units based, at least in part, on the second object, wherein a number of data units in the second set of data units is equal to the increased specified number of data units to be generated.   
     
     
         16 . The computing device of  claim 15 , wherein the machine executable code executable by the processor to cause the computing device to generate the second set of data units based, at least in part, on the second object comprises program code executable by the processor to cause the apparatus to:
 determine an erasure code used to generate the first set of data units; and   modify the erasure code to generate a number of data units equal to the increased specified number of data units to be generated.   
     
     
         17 . The computing device of  claim 14 , further comprising machine executable code executable by the processor to cause the computing device to:
 generate a second set of data units based, at least in part, on the first object; and   send each of the second set of data units with a write request to a different one of the plurality of storage devices;   wherein the machine executable code executable by the processor to cause the computing device to determine that the minimum number of write requests have completed comprises machine executable code executable by the processor to cause the computing device to determine whether a number of the completed write requests for the first set of data units added to a number of completed write requests for the second set of data units is equal to the minimum number of the write requests.   
     
     
         18 . The computing device of  claim 17 , wherein the machine executable code executable by the processor to cause the computing device to send each of the second set of data units with a write request to a different one of the plurality of storage devices comprises machine executable code executable by the processor to cause the computing device to:
 for each of the second set of data units,
 determine whether a write request corresponding to one of the first set of data units failed to complete within a threshold; 
 wherein the data unit is sent in response to a determination that the write request corresponding to the one of the first set of data units failed to complete within the threshold. 
   
     
     
         19 . The computing device of  claim 14 , wherein the minimum number of the write requests is equal to a minimum number of data units required to reconstruct the first object, wherein a number of data units in the first set of data units is equal to or greater than a minimum number of data units required to reconstruct the first object. 
     
     
         20 . The computing device of  claim 14 , further comprising machine executable code executable by the processor to cause the computing device to cancel write requests corresponding to data units not in the subset of data units.