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.

Description:
[0001]     This application claims the benefit of U.S. provisional patent application Ser. No. 60/571,884, filed May 18, 2004, the disclosure of which is herein incorporated by reference. 
     
    
     FIELD OF INVENTION  
       [0002]     The present invention relates to a method and apparatus for calculating exclusive OR (XOR) operations that can be used in any disk array architecture and which is independent of hardware architecture or RAID algorithms.  
       BACKGROUND OF THE INVENTION  
       [0003]     With the accelerating growth of Internet and intranet communication, high-bandwidth applications (such as streaming video), and large information databases, the need for networked storage systems has increased dramatically. System performance, data protection, and cost have been some of the main concerns in designing networked storage systems. In the past, many systems have used fibre channel drives because of their speed and reliability. However, fibre channel drives are very costly. Integrated drive electronics (IDE) drives are much cheaper in terms of dollars-per-gigabyte of storage; however, their reliability is inferior to that of fibre channel drives. Furthermore, IDE drives require cumbersome 40-pin cable connections and are not easily replaceable when a drive fails. Serial advanced technology attachment (SATA) drives that use the same receptor as their fibre channel counterparts are now available. These drives, therefore, have the speed required for acceptable system performance and are hot-swappable, meaning that failed drives are easily replaced with new ones. Furthermore, they provide more storage than do fibre channel drives and at a much lower cost. However, SATA drives do not offer the same reliability as do fibre channel drives. Thus, there is an industry push to develop high-capacity storage devices that are low cost and extremely reliable.  
         [0004]     To improve data reliability, many computer systems implement a RAID system, which is a disk system that includes a collection of multiple disk drives that are organized into a disk array and managed by a common array controller. The array controller presents the array to the user as one or more virtual disks. Disk arrays are the framework to which RAID functionality is added in functional levels in order to produce cost-effective, highly available, high-performance disk systems.  
         [0005]     In RAID systems, the data is distributed over multiple disk drives to allow parallel operation, and thereby enhance disk access performance, and to provide fault tolerance against drive failures. Currently, a variety of RAID levels from RAID level  0  through RAID level  6  have been specified in the industry. RAID levels  1  through  5  provide a single drive fault tolerance. That is, these RAID levels allow reconstruction of the original data, if any one of the disk drives fails. It is quite possible, however, that more than one SATA drive may fail in a RAID system. For example, dual drive failures are becoming more common, as RAID systems incorporate an increasing number of less expensive disk drives.  
         [0006]     To provide, in part, a dual-fault tolerance to such failures, the industry has specified a RAID level  6 . The RAID  6  architecture is similar to RAID  5 , but RAID  6  can overcome the failure of any two disk drives by using an additional parity block for each row (for a storage loss of 2/N). The first parity block (P) is calculated by performing an XOR operation on a set of positionally assigned data sectors (e.g., rows of data sectors). Likewise, the second parity block (Q) is generated by using the XOR function on a set of positionally assigned data sectors (e.g., columns of data sectors). When a pair of disk drives fails, the conventional dual-fault tolerant RAID systems reconstruct the data of the failed drives by using the parity sets. The RAID systems are well known in the art and are amply described, for example, in  The RAIDbook,  6 th Edition: A Storage System Technology Handbook,  edited by Paul Massiglia (1997), which is incorporated herein by reference.  
         [0007]     One disadvantage of RAID  6  is that it is processor-intensive and requires excessive processor cycles to calculate the many parity and data addresses required to perform RAID  6 . As a result, RAID controllers are becoming more complex in order to compensate for the additional processor requirements. As RAID  6  hardware architectures and algorithms become more complex, they also become increasingly vendor-specific and limit a customer&#39;s flexibility to mix and match RAID  6  systems, based on cost, performance, or other business related factors. What is needed is a flexible method of processing RAID  6  algorithms on any type of RAID  6  hardware architecture.  
         [0008]     An example RAID  6  system is described in U.S. Pat. No. 6,513,098, entitled “Method and Apparatus for Scalable Error Correction Code Generation Performance.” The &#39;098 patent describes a scalable memory controller for use in connection with error correction code. According to the invention, the channels of the controller are interconnected to a plurality of parity engines and associated cache memories through use of a switched fabric architecture. A processor is provided for allocating operations that require access to the parity engines or cache memories. By providing multiple parity engines and cache memories, error correction syndrome values can be calculated in parallel. The performance of the controller can be selectively scaled by providing a greater or lesser number of parity engines and associated cache memories. Furthermore, by use of a switched fabric internal architecture, data transfers between the internal components of the controller can be conducted simultaneously.  
         [0009]     The &#39;098 patent provides a RAID controller that is scalable, based on performance and cost requirements. Although this provides flexibility to the customer, such that the RAID controller is somewhat customizable, it does not provide instant or continuous flexibility, because additional hardware must be physically installed or uninstalled to change the RAID controller configuration. Hence, a method of performing parity calculations that is independent of RAID  6  hardware architecture and algorithms is still needed.  
         [0010]     It is therefore an object of the invention to provide an improved method of calculating XOR operations for any type of RAID  6  algorithm.  
         [0011]     It is another object of this invention to provide an improved method of calculating XOR operations for any type of RAID  6  algorithm that is independent of the hardware architecture.  
       SUMMARY OF THE INVENTION  
       [0012]     The present invention is directed to an interpretative script language which may be used to define a plurality of scripts for use with any exclusive OR (XOR) based RAID algorithm. The interpretative script language provides an abstraction layer between RAID hardware and RAID algorithms. This abstraction provides greater system flexibility, as a hardware designer can make hardware changes without being concerned about the details of RAID algorithms, while a RAID algorithm designer can make algorithm changes without being concerned about the details of the RAID hardware architecture. The semantics of the interpretative script language may be incorporated into the software stack of a RAID controller, which would permit the RAID controller to generate a plurality of scripts using the interpretative script language. The scripts are preferably generated offline, for example, during system power-up, in order to minimize system overhead while the RAID controller is executing a RAID algorithm. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0013]     The foregoing and other advantages and features of the invention will become more apparent from the detailed description of exemplary embodiments of the invention given below with reference to the accompanying drawings, in which:  
         [0014]      FIG. 1  is a dual parity generation and data recovery system in a networked storage system; and  
         [0015]      FIG. 2  is a flow diagram of a method of deriving surviving relationships.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0016]     The interpretative script language of the present invention is provides an abstraction layer between the hardware and the RAID algorithms of a RAID system. Accordingly, the interpretative script language of the present invention is independent of the implementation details of a RAID system&#39;s hardware and algorithm. In the description below, the interpretative script language of the present invention is explained in the context of a RAID system implementing the “surviving relationships algorithm” fully described in U.S. Application Ser. No. 60/553,98 (Attorney Docket A7995.0030/P030) filed Mar. 18, 2004, which is hereby incorporated by reference in its entirety. However, it should be recognized that the principles of the present invention may be practiced with any RAID system utilizing exclusive OR (XOR) operations.  
         [0017]     Now referring to the drawings, where like reference numerals designate like elements, there is shown in  FIG. 1 a  system  100  that includes at least one host  110 , a storage controller  160 , and a plurality of storage elements  140   a  through  140   h,  where ‘h’ is not representative of any other value ‘h’ described herein,  140   p,  which is representative of P parity data storage, and  140   q,  which is representative of Q parity data storage. Storage controller  160  further includes a system computer  150 , a software stack  155 , and a storage transaction controller  120 . Storage transaction controller  120  further includes a system computer interface  121 , a mapping engine  124 , an enhanced parity generation and data regeneration system  126 , and a buffer memory  129 . Enhanced parity generation and data regeneration system  126  further includes a table  128  and a nexus table  130 . Software stack  155  is responsible for initialization and configuration of storage transaction controller  120 .  
         [0018]     Host  110  is representative of any kind of mechanism that requests data reads and writes to and from storage elements  140 , which may be any type of networked storage system, for example, a fibre channel or SCSI. Individual storage elements  140  may be, for example, SATA or fibre channel drives. Mapping engine  124  is a transaction processor entity that translates all host  110  requests for specific volumes into the actual logical block addresses (LBAs) in storage elements  140  for storage transaction controller  120 . Storage transaction controller  120  is preferably an integrated I/O controller that is fully explained in U.S. patent application Ser. No. 09/716,195 and preferably which further includes a scalable transaction processing pipeline (not shown) that is explained in U.S. patent application Ser. No. 10/429,048, both of which are hereby incorporated by reference. However, it should be recognized that the present invention may also be practiced using other storage transaction controller architectures. System computer  150  is representative of any processor, which has an operating system and hosts software stack  155 . In one exemplary embodiment, the operating system is the Linux operating system, however, the present invention may be practiced with other operating systems as well. The scripts generated by the SRA are incorporated into software stack  455 . Preferably, the software stack  155  initializes table  128  with the SRA script information through system computer interface  121  at boot-up or power-on/reset.  
         [0019]     Table  128  is any kind of memory element. Nexus table  130  is a look-up table. Nexus table  130  holds two types of nexus lists. A nexus is a list of buffer memory  129  block addresses. A longform nexus has sixty-four such block addresses and a shortform nexus has four such block addresses. Each block address represents thirty-two sectors. Thus, a nexus is a scatter-gather list that represents a consolidated buffer memory  129  resource of either 2,048 sectors (longform nexus) or 128 sectors (shortform nexus).  
         [0020]      FIG. 2  is a flow diagram of a method  200  of deriving surviving relationships. Method  200  includes the following steps:  
         [0021]     Step  210 : Deriving a Candidate Q Relationship Set Based on P Relationship Set Inputs  
         [0022]     In this step, method  200  derives a candidate Q relationship set from a P relationship seed. The symbols in the Q relationships are randomly selected from the Q parity storage element symbols, the P parity storage element symbols, and one symbol each from all but one data storage element. No two Q relationships miss the same data storage element, and no two Q relationships have a common symbol between them. This process repeats until there are as many Q relationships as the number of symbols per column. Method  200  proceeds to step  220 .  
         [0023]     Step  220 : Have All Two Storage Element Failure Combinations Been Evaluated? 
         [0024]     In this decision step, method  200  determines whether all two storage element failure combinations have been evaluated for this candidate Q relationship set (i.e., can all unresolved symbols be resolved for all failure combinations?). If yes, method  200  proceeds to step  270 , and this Q candidate relationship set is designated as the Q relationship set; if no, initially unresolved symbols for the next two storage element failure combination are identified (32 unresolved symbols are created in any two storage element failure combinations in an 8+2 RAID architecture example) and method  200  proceeds to step  230 .  
         [0025]     Step  230 : Identifying Intact, Surviving, and Non-Surviving Relationships  
         [0026]     In this step, for the given set of unresolved symbols, method  200  identifies intact relationships, surviving relationships, and non-surviving relationships. These relationships include both P and Q relationship sets. Method  200  proceeds to step  240 .  
         [0027]     Step  240 : Are There Any Surviving Relationships? 
         [0028]     In this decision step, method  200  determines whether there are any surviving relationships. If yes, method  200  proceeds to step  250 ; if no, method  200  proceeds to step  260 .  
         [0029]     Step  250 : Resolving Unresolved Symbols  
         [0030]     In this step, method  200  expresses the unknown term as an XOR equation of resolved symbols. For example, if disk  1  symbol  2  (i.e., D [ 1 , 2  ]) is an unknown term, it can be resolved by use of the following XOR equation, where ‘{circumflex over ( )}’ is equivalent to XOR: 
 
D[ 1 , 2 ]=Q[ 0 ] {circumflex over ( )} D[ 2 , 6 ] {circumflex over ( )} D[ 3 , 2 ] {circumflex over ( )} D[ 4 , 0 ] {circumflex over ( )} D[ 5 , 3 ] {circumflex over ( )} D[ 6 , 7 ] {circumflex over ( )} D[ 7 , 11 ] {circumflex over ( )} P[ 13 ]
 
 Therefore, D[ 1 , 2 ] is resolved and becomes a known term. It should be clear to one skilled in the art that this particular step illustrates a single resolution; however, multiple resolutions are possible, if there are more surviving relationships. The set of unresolved symbols is updated to remove the newly resolved symbol (D [ 1 , 2  ] for this example). Method  200  returns to step  230 . 
 
         [0031]     Step  260 : Are All Relationships Intact? 
         [0032]     In this decision step, method  200  determines whether all the relationships are intact. If yes, method  200  determines that this candidate Q relationship set is the correct set with which to generate parity and/or data for this particular two storage element failure combination and method  200  returns to step  220 ; if no, method  200  returns to step  210 .  
         [0033]     Step  270 : Writing Out Scripts  
         [0034]     In this step, method  200  generates a plurality of scripts that correspond to each failure case. For each failure case (single and dual) evaluated for a successful Q candidate, the XOR equations needed to resolve all missing symbols are written out to a disk file as a script using the semantics described later. Method  200  ends.  
         [0035]     The disk file is then incorporated onto software stack  155  during compilation of stack  155  source code.  
         [0036]     The instructions of the script specify the list of locations of the resolved symbols in buffer memory  129  which are to be XOR-ed to recover a missing symbol and the location in buffer memory  129  where the recovered missing symbol (result of XOR) is to be saved. Each script also has an end of script command, so that script execution terminates at the end of the correct script and before the beginning of the next contiguous script. The semantics of this script language are described later, in connection with Table 2.  
         [0037]     In the event of single or dual storage elements  140  failure(s), storage controller  120  determines which storage element failure case is applicable. Mapping engine  124  determines the corresponding storage elements  140  LBAs ( 140   p,    140   q  and  140   a - 140   h ) for the corresponding volume and host  110  LBAs. For cases in which no storage elements  140  have failed and a write operation is requested, mapping engine  124  specifies the offset (start of the relevant script) in table  128  for the script that corresponds to a dual failure by storage elements  140   p  and  140   q  via a data packet that is known as a RAID  6  buffer command.  
         [0038]     Table 1 is the format for a RAID  6  buffer command that mapping engine  124  sends to enhanced parity generation and data regeneration system  126 .  
                                 TABLE 1                           Format of a RAID 6 buffer command                    Size           #   Field Name   (Bytes)   Description               1   Opcode   2   Will be set to R6_XOR_BUF_CMD or                   R6_SCRUB_BUF_CMD to indicate RAID 6                   buffer command nexus       2   Main_NexusPtr   2   A pointer to the longform nexus, which                   contains or will contain a full RAID 6 stripe       3   P_NexusPtr   2   A pointer to the shortform nexus that                   contains the P parity       4   Q_NexusPtr   2   A pointer to the shortform nexus that                   contains the Q parity       5   Scratch_NexusPtr   2   A pointer to the nexus (either long or                   short form), which is used to hold                   intermediate XOR results       6   XorSeqNum   2   The Entry number in Table 128, from which                   the enhanced parity and data regeneration                   system 126 starts executing the XOR                   sequence needed for this RAID 6 Buffer                   command.                  
 
         [0039]     The buffer command (opcode=R6_XOR_BUF_CMD) instructs enhanced parity and data regeneration system  126  to execute a specified script (specified by XorSeqNum) located in table  128 . The entry location in table  128  for the start of the script to be executed is specified in the XorSeqNum field. The nexus pointers indicate the start of each respective nexus in nexus table  130 . The main nexus pointer holds the buffer memory  129  block addresses for data, the P-nexus pointer holds the buffer memory  129  block addresses for P parity, the Q-nexus pointer holds the buffer memory  129  block addresses for Q parity, and the scratch nexus pointer holds buffer memory  129  block addresses for intermediate data and parity calculations. Enhanced parity and data regeneration system  126  proceeds to process each command located in table  128  until the end-of-script is reached. At that point, all of the missing symbols caused by a dual drive failure or an update to parity have been regenerated or reconstructed in buffer memory  129 .  
         [0040]     Table 2 specifies the XOR sequence entry format in table  128 .  
                                                                         TABLE 2                           XOR sequence entry data format            #   FieldName   Size(Bytes)   Description               1   Flags   1               SubfieldName   Bit               Positions                1.0   Reserved   7   Reserved.           1.1   NOP   6   A 1 indicates No-operation                       and the remaining flag bits                       and fields should be treated                       as “don&#39;t care”.           1.2   SetSectorCount   5   A 1 indicates that the forth-                       coming SectorCount_Offset                       field specifies the XOR-                       command size in sectors for                       forthcoming XOR-operations.           1.3   BeginOfChain   4   A 1 indicates that this is                       the beginning of XOR chain.                       When this bit is set, the                       destination nexus pointer                       is reset to null.           1.4   EndOfScript   3   A 1 indicates that this is                       the last operation in the                       list of XOR operations                       associated with a buffer                       command.           1.5   Destination   2   A 0 indicates that this                       entry specifies a source.                       A 1 indicates that this                       entry specifies a destination,                       the destination nexus is set                       to point to what is specified                       by NexusSelect.           1.6   NexusSelect   1:0   00 selects Main_Nexus                       01 selects P_Nexus                       10 selects Q_Nexus                       11 selects Scratch_Nexus            2   SectorCount_Offset   2   When SetSectorCount is set                   to zero, this field specifies                   the sector offset in the                   selected nexus from where a                   RAID symbol begins. If                   SetSectorCount is set to one,                   this field specifies XOR                   command size in sectors for                   forthcoming XOR-operations.       3   BlockOffset   1   This field specifies the                   offset into the list of blocks                   in the selected nexus where                   the symbol begins. This field is                   valid only when SetSectorCount                   is set to zero.                  
 
         [0041]     Each entry in table  128  is treated as an “instruction” by enhanced parity and data regeneration system  126 . A script is a set of chains, where a chain is a series of instructions for the same destination block addresses; therefore, each chain has a fixed SectorCount value and Destination symbol address.  
         [0042]     In operation, enhanced parity generation and data regeneration system  126  reads the first instruction located in table  128  and executes the instruction. Parity generation and data regeneration system  126  proceeds to the next consecutive instruction entry in table  128  and executes that instruction. The process continues until an end of script instruction is reached. A change in symbol size (SetSectorCount bit is set and SectorCount_Offset is equal to new symbol size) or destination represents the start of a new chain. For example, the script in table  128  may look like the following example, shown in Table 3 below.  
                                           TABLE 3                           An example RAID interpretive script where each       group of three fields is an instruction                Code (binary)   Description                        Instruction   0010 0000   SetSectorCount = 1           0000 0000 1000 0000   SectorCount_Offset = 128           0001 0101   Begin of chain = true; Set               Destination D1, DestNexus =               P nexus       Instruction   0000 0000   Set Source Symbol S1,               SourceNexus = Main nexus           0000 0000 0000 0000   SectorCount_Offset = 0           0000 0000   BlockOffset = 0       Instruction   0000 0000   Set Source Symbol S2;               SourceNexus = Main_nexus           0000 0001 0000 0000   SectorCount_Offset = 256           0000 1000   BlockOffset = 8       Instruction   0000 0000   Set Source Symbol S3;               SourceNexus = Main_nexus           0000 0000 1000 0000   SectorCount_Offset = 128           0000 1100   BlockOffset = 4       Instruction   0000 1000   Set Source Symbol S4;               SourceNexus = Main_nexus;               end of script = true           0000 0001 1000 0000   SectorCount_Offset = 384           0000 1100   BlockOffset = 12       Instruction   0001 0110   //Next chain               Begin of chain = true; Set               Destination D2, DestNexus =               Q_nexus           0000 0000 0000 0000   SectorCount_Offset = 0           0000 0000   BlockOffset = 0                  
 
         [0043]     In this example (which shows only the last chain,of the script), the chain instructs enhanced parity and data regeneration system  126  to XOR S 1  {circumflex over ( )} S 2  {circumflex over ( )} S 3  {circumflex over ( )} S 4  and put the result into D 1 . Note that the addresses of S 1  through S 4  reside in the Main_nexus (the actual nexus number is specified by the RAID  6  buffer command) in nexus table  130  and the D 1  address resides in the P_nexus the actual nexus number is specified by the RAID  6  buffer command) in nexus table  130 .  
         [0044]     The BlockOffset operand allows enhanced parity and data regeneration system  126  to operate at a higher performance by removing the otherwise required block offset calculation; however, this is not required for the invention to be operable.  
         [0045]     The previous example assumes a four-input hardware XOR architecture and four symbols. However, the script method of generating parity and/or data provides an abstraction layer, such that the hardware architecture is independent of the algorithm. For example, for a two-input hardware architecture, enhanced parity and data regeneration system  126 , using the previous example, the result of S 1  {circumflex over ( )} S 2  is stored in D 1 , then the result of D 1  {circumflex over ( )} S 3  is stored into D 1  and, finally, the result of S 4  and D 1  is stored in D 1  as the final result. In a four-input hardware architecture and an eight symbol example, enhanced parity and data regeneration system  126  may perform S 1  {circumflex over ( )} S 2  {circumflex over ( )} S 3  {circumflex over ( )} S 4  and store the result into D 1  then perform the operation: D 1  {circumflex over ( )} S 5  {circumflex over ( )} S 6  {circumflex over ( )} S 7  and store that result into D 1  and, finally, perform the operation D 1  {circumflex over ( )} S 8  to obtain the final result. Other hardware architectures and algorithms may be performed by using this system, as may be appreciated by those skilled in the art.  
         [0046]     Regardless of the hardware architecture for the RAID system or the RAID algorithms themselves, the invention described herein provides a method for scripting RAID algorithms and brings in a layer of abstraction between hardware architectures and RAID algorithms.  
         [0047]     While the invention has been described in detail in connection with the exemplary embodiment, it should be understood that the invention is not limited to the above disclosed embodiment. Rather, the invention can be modified to incorporate any number of variations, alternations, substitutions, or equivalent arrangements not heretofore described, but which are commensurate with the spirit and scope of the invention. Accordingly, the invention is not limited by the foregoing description or drawings, but is only limited by the scope of the appended claims.