Repair-Optimal Parity Code

Abstract

Techniques for generating parities and repairing data erasures using repair-optimal parities are disclosed. The system includes an encoding module, which receives a request to recreate data for a subset of a plurality of content stores. The encoding module generates a new first parity and a new second parity using a subset of remaining content from the plurality of content stores. The encoding module generates a first portion of the requested data using the new first parity and a first subset of an original first parity for the plurality of content stores and a second portion of the requested data using the new second parity and a second subset of an original second parity for the plurality of content stores. The encoding module may recreate the data for the content store using the first portion of the requested data and the second portion of requested data.

What is claimed is: 
     
         1 . A system comprising:
 a plurality of content stores; and   a storage controller configured to:
 receive a request to recreate data for a subset of the plurality of content stores; 
 generate a new first parity using a subset of remaining content from the plurality of content stores; 
 generate a new second parity using the subset of the remaining content from the plurality of content stores; 
 generate a first portion of the requested data using the new first parity and a first subset of an original first parity for the plurality of content stores; 
 generate a second portion of the requested data using the new second parity and a second subset of an original second parity for the plurality of content stores; and 
 recreate the data for the content store using the first portion of the requested data and the second portion of requested data. 
   
     
     
         2 . The system of  claim 1 , wherein to generate the new first parity and the new second parity, the storage controller is configured to:
 update the new first parity with a first part of the new first parity, a second part of the new first parity and a third part of the new first parity; and   update the new second parity with a first part of the new second parity and a second part of the new second parity.   
     
     
         3 . The system of  claim 2 , wherein the second part of the new second parity includes a subset of content from the second part of the new first parity and the third part of the new first parity. 
     
     
         4 . The system of  claim 3 , wherein the subset of content is selected from even rows of the new first parity. 
     
     
         5 . The system of  claim 1 , wherein the storage controller is configured to:
 determine that the new first parity and the new second parity are complete.   
     
     
         6 . The system of  claim 1 , wherein to generate the first portion of the requested data and the second portion of the requested data, the storage controller is configured to:
 compare the new first parity and the new second parity with the first subset of the original first parity for the plurality of content stores and the second subset of the original second parity for the plurality of content stores.   
     
     
         7 . The system of  claim 6  wherein the storage controller is configured to:
 perform an “exclusive or” (XOR) operation on the new first parity and the first subset of the original first parity for the plurality of content stores; and 
 perform an XOR operation on the new second parity and the second subset of the original second parity for the plurality of content stores. 
 
     
     
         8 . A method comprising:
 receiving a request to recreate data for a subset of a plurality of content stores;   generating a new first parity using a subset of remaining content from the plurality of content stores;   generating a new second parity using the subset of the remaining content from the plurality of content stores;   generating a first portion of the requested data using the new first parity and a first subset of an original first parity for the plurality of content stores;   generating a second portion of the requested data using the new second parity and a second subset of an original second parity for the plurality of content stores; and   recreating the data for the content store using the first portion of the requested data and the second portion of requested data.   
     
     
         9 . The method of  claim 8 , wherein generating the new first parity and the new second parity further comprises:
 updating the new first parity with a first part of the new first parity, a second part of the new first parity and a third part of the new first parity; and   updating the new second parity with a first part of the new second parity and a second part of the new second parity.   
     
     
         10 . The method of  claim 9 , wherein the second part of the new second parity includes a subset of content from the second part of the new first parity and the third part of the new first parity. 
     
     
         11 . The method of  claim 10 , wherein the subset of content is selected from even rows of the new first parity. 
     
     
         12 . The method of  claim 8 , further comprising determining that the new first parity and the new second parity are complete. 
     
     
         13 . The method of  claim 8 , wherein the request to recreate data is a failure notification. 
     
     
         14 . The computer program product of  claim 8 , wherein the requested data is recreated based on “exclusive or” (XOR) operation on the new first parity and the first subset of the original first parity for the plurality of content stores and an XOR operation on the new second parity and the second subset of the original second parity for the plurality of content stores. 
     
     
         15 . A system comprising:
 means for receiving a request to recreate data for a subset of the plurality of content stores;   means for generating a new first parity using a subset of remaining content from the plurality of content stores;   means for generating a new second parity using the subset of the remaining content from the plurality of content stores;   means for generating a first portion of the requested data using the new first parity and a first subset of an original first parity for the plurality of content stores;   means for generating a second portion of the requested data using the new second parity and a second subset of an original second parity for the plurality of content stores; and   means for recreating the data for the content store using the first portion of the requested data and the second portion of requested data.   
     
     
         16 . The system of  claim 15 , wherein to generate the new first parity and the new second parity, the system further comprises:
 means for updating the new first parity with a first part of the new first parity, a second part of the new first parity and a third part of the new first parity; and   means for updating the new second parity with a first part of the new second parity and a second part of the new second parity.   
     
     
         17 . The system of  claim 16 , wherein the second part of the new second parity includes a subset of content from the second part of the new first parity and the third part of the new first parity. 
     
     
         18 . The system of  claim 17 , wherein the subset of content is selected from even rows of the new first parity. 
     
     
         19 . The system of  claim 15 , wherein to generate the first portion of the requested data and the second portion of the requested data, the system further comprises:
 means for comparing the new first parity and the new second parity with the first subset of the original first parity and the second subset of the original second parity.   
     
     
         20 . The system of  claim 19  wherein the system further comprises:
 means for performing an “exclusive or” (XOR) operation on the new first parity and the first subset of the original first parity for the plurality of content stores; and 
 means for performing an XOR operation on the new second parity and the second subset of the original second parity for the plurality of content stores.