Method of implementing XOR based raid algorithms

Abstract

An interpretive script language that provides an abstraction layer between redundant array of independent disks (RAID) algorithms and RAID hardware architecture. The interpretive script language provides greater flexibility and performance over conventional RAID processors. The interpretive script language may be used with any RAID hardware architecture, is not dependent on a specific RAID algorithm, and enables efficient communication to a RAID processor from any entity that desires RAID services. The entity requesting RAID services sends a command to a RAID processor, which includes pointers to a script entry point for scripts stored in a table memory in the RAID processor, and pointers to the data and parity (for example, in a buffer memory) on which to perform exclusive OR (XOR) operations.

1 . A storage system, comprising: 
 a plurality of storage elements for storing information comprising data and a parity;    a storage controller for controlling transfer of said information between said plurality of storage elements and at least one host, said storage controller comprising: 
 a parity unit comprising a script table for storing as a plurality of scripts, each of said scripts defining a set of relationships between said parity and said data;  
 a computer system coupled to said parity system for creating said plurality of scripts;  
   wherein each script comprises a set of instructions and respectively corresponds to a failure mode of a set of at least one failed storage elements, such that said parity unit is capable of regenerating information previously stored on the set of at least one failed storage element by executing said set of instructions.    
     
     
         2 . The storage system of  claim 1 , wherein each relationship comprises a plurality of exclusive-OR (XOR) operations between said data and said parity.  
     
     
         3 . The storage system of  claim 1 , wherein said storage controller further comprises: 
 a mapping engine coupled to said parity unit for mapping an address asserted by said at least one host into an address space of said plurality of storage elements; and    a buffer, for storing information in transit between said at least one host and said plurality of storage elements.    
     
     
         4 . The storage system of  claim 3 , wherein said mapping engine identifies one of said plurality of scripts stored in said script table when said storage controller receives a write command and write data from said at least one host.  
     
     
         5 . The storage system of  claim 4 , wherein said parity unit executes instructions in said one of said plurality of scripts to generate parity associated with said write data.  
     
     
         6 . The storage system of  claim 4 , wherein said mapping engine identifies said one of said plurality of scripts by issuing a buffer instruction to said parity unit.  
     
     
         7 . The storage system of  claim 6 , wherein said parity system further comprises a nexus table for storing a plurality of nexuses, each nexus comprising a plurality of sector addresses in said plurality of storage elements.  
     
     
         8 . The storage system of  claim 7 , wherein said buffer instruction comprises: 
 an operational code identifying said buffer instruction;    a pointer to a first nexus corresponding to a complete stripe of said plurality of storage elements;    a set of pointers to a set of second nexuses corresponding to parity information;    a pointer to a nexus for holding intermediate calculation results; and    an identifier corresponding to one of said plurality of scripts stored in said script table.    
     
     
         9 . The storage system of  claim 8 , wherein said parity unit maintains a P-parity and a Q-parity, and said set of pointers to said set of second nexuses include a nexus associated with said P-parity and a nexus associated with said Q-parity.  
     
     
         10 . The storage system of  claim 7 , wherein said nexus table include a plurality of short form nexuses for storing a relatively small number of sector addresses and a plurality of long form nexuses for storing a relatively large number of sector addresses.  
     
     
         11 . The storage system of  claim 10 , wherein each long form nexus stores 2048 sector addresses.  
     
     
         12 . The storage system of  claim 10 , wherein each short form nexus stores 128 sector addresses.  
     
     
         13 . The storage system of  claim 8 , wherein each instruction in each script comprises: 
 a first field for selecting one of said nexuses in said buffer instruction;    a second field for storing either: 
 a sector address offset associated with a RAID symbol in said selected one of said nexuses in said buffer instruction, or  
 a number of sectors to be part of an exclusive-OR operation; and  
   a third field for storing a block address offset associated with a RAID symbol in said selected one of said nexuses in said buffer instruction.    
     
     
         14 . The storage system of  claim 13 , wherein said first field comprise: 
 a first subfield for indicating whether to treat said instruction as a no operation (NOP) instruction;    a second subfield for indicating whether said second field stores said sector address offset or said number of sectors;    a third subfield for indicating whether said instruction corresponds to a beginning of a chain of exclusive-OR operations;    a fourth subfield for indicating whether said instruction corresponds to a last instruction in said script;    a fifth subfield for indicating whether said instruction is associated with a source or a destination; and    a sixth subfield for selecting one of the plurality of nexuses in a buffer instruction.    
     
     
         15 . A method for operating a storage system, comprising: 
 at a power-on or restart of said storage system: 
 creating a plurality of scripts, each one of said plurality of scripts comprising a set of instructions respectively corresponding to a failure mode of a set of at least one failed storage element in said storage system.  
   
     
     
         16 . The method of  claim 15 , wherein said initialization comprises: 
 identifying a set comprising plurality of unresolved RAID symbols;    repeatedly: 
 defining a relationship to resolve one of said unresolved RAID symbols; and  
 removing said one of said unresolved RAID symbols from said set until said set of unresolved RAID symbol is an empty set; and  
   writing out a plurality of scripts corresponding to each defined relationship.    
     
     
         17 . The method of  claim 15 , further comprising: 
 receiving, from a host, a read command including a read address;    responsive to said read command, reading information from a plurality of storage elements associated with said read address;    if a set of at least one storage element associated with said read address cannot be read, 
 identifying a script associated said set;  
 executing instructions in said script to regenerate information previously stored on said set of at least one storage elements; and  
   sending to said host, data associated with said read address.    
     
     
         18 . The method of  claim 15 , further comprising: 
 receiving, from a host, a write command including write data;    responsive to said write command, identifying a script associated with said write data;    executing instructions in said script to generate parity associated with said write data;    writing, to a plurality of storage elements of said storage system, said write data and parity associated with said write data.