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.