Layered error correction encoding for large scale distributed object storage system

Abstract

A method is described. The method includes fragmenting data of an object for storage into an object storage system into multiple data fragments and performing a first error correction encoding process on the data to generate one or more parity fragments for the object. The method also includes sending the multiple data fragments and the one or more parity fragments over a network to different storage servers of the object storage system. The method also includes performing the following at each of the different storage servers: i) incorporating the received one of the multiple data fragments and one or more parity fragments into an extent comprising multiple fragments of other objects; ii) performing a second error correction encoding process on multiple extents including the extent to generate parity information for the multiple extents; and, iii) storing the multiple extents and the parity information.

1 . A method, comprising:
 a) fragmenting data of an object for storage into an object storage system into multiple data fragments and performing a first error correction encoding process on the data to generate one or more parity fragments for the object;   b) sending the multiple data fragments and the one or more parity fragments over a network to different storage servers of the object storage system;   c) performing the following at each of the different storage servers:
 i) incorporating the received one of the multiple data fragments and one or more parity fragments into an extent comprising multiple fragments of other objects; 
 ii) performing a second error correction encoding process on multiple extents including the extent to generate parity information for the multiple extents; and, 
 iii) storing the multiple extents and the parity information. 
   
     
     
         2 . The method of  claim 1  wherein the parity information comprises one or more parity extents of same size. 
     
     
         3 . The method of  claim 2  wherein the multiple extents and the parity extents are stored on different respective storage devices within their respective storage server. 
     
     
         4 . The method of  claim 1  wherein the multiple extents are stored on different respective storage devices within their respective storage server. 
     
     
         5 . The method of  claim 1  wherein the first and second error correction encoding processes are maximum distance separable (MDS) error correction encoding processes. 
     
     
         6 . The method of  claim 1  wherein the method further comprises performing a third error correction encoding process for each of the multiple extents to generate respective parity information for each of the multiple extents and storing the respective parity information. 
     
     
         7 . The method of  claim 6  further comprising:
 a) in response to a data item for the object being corrupted, attempting to recover the data item with the respective parity information from the third error correction encoding process generated for the extent; and, 
 b) in response to the data item not being recovered from a), attempting to recover the data item with the parity information from the second error correction encoding process and at least some of the multiple extents and parity information. 
 
     
     
         8 . The method of  claim 7  further comprising:
 in response to the lost information not being recovered, attempting to recover the lost information with at least some of the multiple data fragments and the one or more parity fragments. 
 
     
     
         9 . The method of  claim 1  further comprising:
 a) in response to a data item for the object being corrupted, attempting to recover the data item with the parity information from the second error correction encoding process and at least some of the multiple extents and parity information; 
 b) in response to the lost information not being recovered, attempting to recover the lost information with at least some of the multiple data fragments and the one or more parity fragments. 
 
     
     
         10 . The method of  claim 1  wherein the object storage system comprises a distributed hash table storage ring. 
     
     
         11 . A method, comprising:
 a) fragmenting data of an object for storage into an object storage system into multiple data fragments and performing a first error correction encoding process on the data to generate one or more parity fragments for the object;   b) sending the multiple data fragments and the one or more parity fragments over a network to different storage entities of the object storage system, where, at least one of the different storage entities is a cloud storage service; and,   c) in response to an inability to cure a corruption of one of the fragments locally by its corresponding one of the different storage entities, reading the multiple data fragments and the one or more parity fragments from the different storage entities and processing the read fragments to cure the corruption.