System and method for reconstructing lost data in a storage system

Abstract

A system (and method) for determining reconstruction formulas for partial strip reconstruction in a storage system in which a plurality of lost strips have been detected, includes using a combination of a direct reconstruction method and a sequential reconstruction method.

1 . A method for partial strip reconstruction in a storage system in which a plurality of lost strips have been detected, said method comprising: 
 using a combination of a direct reconstruction method and a sequential reconstruction method to reconstruct said partial strip.    
   
   
       2 . The method according to  claim 1 , wherein said direct reconstruction method determines at least one initialization point for said sequential reconstruction method.  
   
   
       3 . The method according to  claim 1 , wherein said storage system includes at least one of a parity scheme and an XOR-based RAID scheme.  
   
   
       4 . The method according to  claim 1 , wherein said sequential reconstruction method reconstructs a data element, from an input set of data elements to reconstruct, by collapsing said sequential reconstruction method to reduce cost.  
   
   
       5 . The method according to  claim 4 , wherein said collapsing said sequential reconstruction method comprises at least one of: 
 using implicit intermediate results to reconstruct said data element;    determining whether any unnecessary data elements exist in at least one strip of the plurality of lost strips that are not part of said partial strip, and combining at least a portion of steps in said sequential reconstruction method to eliminate reconstruction of said unnecessary data elements;    avoiding unnecessary use of data elements that are not lost;    avoiding duplicate use of data elements that are not lost; and    avoiding multiple use of data elements that are not lost.    
   
   
       6 . The method according to  claim 1 , wherein said direct reconstruction method determines a most cost effective starting point for said sequential reconstruction method.  
   
   
       7 . The method according to  claim 1 , further comprising: 
 from an input set of data elements to reconstruct, identifying at least one data element which has a lowest reconstruction cost using said direct reconstruction method;    reconstructing said data element using said direct reconstruction method; and    removing said data element from the input set of data elements to reconstruct.    
   
   
       8 . The method according to  claim 7 , further comprising: 
 from said input set of data elements to reconstruct, determining if at least one data element from the input set is sequentially reconstructable by no more than a predetermined number of steps using available data and parity elements;    reconstructing said data element using said sequential reconstruction method; and    removing said data element from the input set of data elements to reconstruct.    
   
   
       9 . The method according to  claim 7 , further comprising: 
 collapsing said sequential reconstruction method to reduce cost.    
   
   
       10 . The method according to  claim 8 , wherein, if at least one data element from the input set is not sequentially reconstructable by no more than a predetermined number of steps using available data and parity elements, identifying at least one other data element, from said input set of data elements to reconstruct, which has a lowest reconstruction cost using said direct reconstruction method; 
 reconstructing said at least one other data element using said direct reconstruction method; and    removing said at least one other data element from the input set of data elements to reconstruct.    
   
   
       11 . The method according to  claim 1 , further comprising: 
 from an input set of data elements to reconstruct, determining if at least one data element from the input set is sequentially reconstructable by no more than a predetermined number of steps using available data and parity elements;    reconstructing said data element using said sequential reconstruction method; and    removing said data element from the input set of data elements to reconstruct.    
   
   
       12 . The method according to  claim 1   1 , wherein, if at least one data element from the input set is not sequentially reconstructable by no more than a predetermined number of steps using available data and parity elements, identifying at least one other data element, from said input set of data elements to reconstruct, which has a lowest reconstruction cost using said direct reconstruction method; 
 reconstructing said at least one other data element using said direct reconstruction method; and    removing said at least one other data element from the input set of data elements to reconstruct.    
   
   
       13 . A system for partial strip reconstruction in a storage system, said system comprising: 
 a storage unit of said storage system including an input set of data elements to reconstruct; and    means for reconstructing a data element from said input set of data elements to reconstruct based on a combination of a direct reconstruction method and a sequential reconstruction method.    
   
   
       14 . The system according to  claim 13 , wherein said means for reconstructing uses said direct reconstruction method to determine at least one initialization point for said sequential reconstruction method.  
   
   
       15 . The system according to  claim 13 , wherein said storage system includes at least one of a parity scheme and an XOR-based RAID scheme.  
   
   
       16 . The system according to  claim 13 , wherein said means for reconstructing reconstructs a data element, from an input set of data elements to reconstruct, by collapsing said sequential reconstruction method to reduce cost.  
   
   
       17 . The system according to  claim 16 , wherein said means for reconstructing collapses said sequential reconstruction method by at least one of: 
 using implicit intermediate results to reconstruct said data element;    determining whether any unnecessary data elements exist in at least one strip of the plurality of lost strips that are not part of said partial strip, and combining at least a portion of steps in said sequential reconstruction method to eliminate reconstruction of said unnecessary data elements;    avoiding unnecessary use of data elements that are not lost;    avoiding duplicate use of data elements that are not lost; and    avoiding multiple use of data elements that are not lost.    
   
   
       18 . The system according to  claim 13 , wherein said means for reconstructing determines a most cost effective starting point for said sequential reconstruction method using said direct reconstruction method.  
   
   
       19 . A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for determining reconstruction formulas for partial strip reconstruction in a storage system, the method comprising a combination of a direct reconstruction method and a sequential reconstruction method.  
   
   
       20 . A method of deploying computing infrastructure in which computer-readable code is integrated into a computing system, and combines with said computing system to perform a method for determining reconstruction formulas for partial strip reconstruction in a storage system, the method comprising a combination of a direct reconstruction method and a sequential reconstruction method.  
   
   
       21 . A system for partial strip reconstruction in a storage system, said system comprising: 
 a storage unit of said storage system including an input set of data elements to reconstruct; and    a reconstruction unit that reconstructs a data element from said input set of data elements to reconstruct based on a combination of a direct reconstruction method and a sequential reconstruction method.    
   
   
       22 . A method for determining reconstruction formulas for partial strip reconstruction in a storage system, said method comprising: 
 determining a combination of a direct reconstruction method and a sequential reconstruction method to reconstruct said partial strip.    
   
   
       23 . The method according to  claim 22 , further comprising: 
 reconstructing said partial strip based on said combination of said direct reconstruction method and said sequential reconstruction method.