Abstract:
A method of calculating single and dual parity for a networked array of storage elements is presented. The method includes deriving a first set of n relationships where each of the first set of n relationships consists of an XOR statement equaling zero. Each of the first set of n relationships contains n data symbols from n storage elements and one parity symbol from a first set of parity symbols. The method also includes deriving a second set of n+1 relationships where each of the second set of n+1 relationships consists of an XOR statement equaling zero, containing at least n−1 data symbols from at least n−1 storage elements and one parity symbol from a second set of parity symbols. Using both the first and second sets of derived relationships, scripts are generated to resolve unresolved symbols resulting from possible single- and dual-storage element failure combinations.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0001]     This patent application claims priority to U.S. Provisional Application No. 60/598,439 filed on Aug. 4, 2004 in the U.S. Patent and Trademark Office, the entire content of which is incorporated by reference herein. 
     
    
     FIELD OF THE INVENTION  
       [0002]     The present invention relates to a method that calculates single and dual parity in a networked storage system and specifically relates to an algorithm that compensates for dual-drive failures in a networked storage system.  
       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, which means that failed SATA 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 still do not offer the same reliability as 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 redundant array of independent disks (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 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, where N represents the number of networked drives). The first parity block (P) is calculated by the performance of an exclusive or (XOR) operation on a set of positionally assigned data sectors (i.e., rows of data sectors). Likewise, the second parity block (Q) is generated by the use of the XOR function on a set of positionally assigned data sectors (i.e., 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. 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]     An examplary dual-parity algorithm is found in U.S. Pat. No. 6,453,428, entitled, “Dual-drive Fault Tolerant Method and System for Assigning Data Chunks to Column Parity Sets.” The &#39;428 patent describes a method and system for assigning data chunks to column parity sets in a dual-drive fault tolerant storage disk drive system that has N disk drives, where N is a prime number. Each of the N disk drives is organized into N chunks, such that the N disk drives are configured as one or more N×N array of chunks. The array has chunks arranged in N rows from row 1 to row N and in N columns from column 1 to column N. Each row includes a plurality of data chunks for storing data, a column parity chunk for storing a column parity set, and a row parity chunk for storing a row parity set. These data chunks are assigned in a predetermined order. The data chunks in each row are assigned to the row parity set. Each column parity set is associated with a set of data chunks in the array, wherein row m is associated with column parity set Q m , where m is an integer that ranges from 1 to N. For row 1 of a selected N×N array, a first data chunk is assigned to a column parity set Q i , wherein i is an integer determined by rounding down (N/2). For each of the remaining data chunks in row 1, each data chunk is assigned to a column parity set Q j , wherein j is an integer one less than the column parity set for the preceding data chunk and wherein j wraps to N when j is equal to 0. For each of the remaining rows 2 to N of the selected array, a first logical data chunk is assigned to a column parity set Q k , wherein k is one greater than the column parity set for the first logical data chunk in a preceding row and wherein k wraps to 1 when k is equal to (N+1). For each of the remaining data chunks in rows 2 to N, each data chunk is assigned to a column parity set Q n , wherein n is an integer one less than a column parity set for the preceding data chunk and wherein n wraps to N when n is equal to 0.  
         [0008]     The algorithm described in the &#39;428 patent safeguards against the loss of data in the event of a dual-drive failure. However, performance of the algorithm described uses excess XOR processing cycles, known as XOR bandwidth that may otherwise be utilized for performing system storage tasks. Hence, the &#39;428 patent describes a suitable dual-parity algorithm for calculating dual-parity and for restoring data from a dual-drive failure, yet it fails to provide an optimized software system that is capable of performing the dual-parity algorithm without affecting system performance.  
         [0009]     Furthermore, the algorithm described in the &#39;428 patent is dependent on row and column parity, which requires a prime number of data drives to be present in the system. The requirement of a specific number of drives limits system design flexibility, which can lead to increased cost (e.g., a system that requires fourteen drives to meet storage needs would need seventeen drives, the next prime number of drives, in order to meet parity algorithm requirements). In some cases, phantom drives are used to fill in the missing number of drives in order to achieve a prime number of drives. These phantom drives are assumed to contain data equal to logical ‘0’ and are used during XOR calculations to create parity or restore lost data. This method uses excess system overhead and processing cycles on the phantom data, which lowers overall system performance.  
         [0010]     There is, therefore, a need for an effective means of calculating parity, such that the storage system is fault tolerant against a dual-drive failure, provides optimal system performance by optimizing XOR bandwidth, is capable of generating parity regardless of symbol position (i.e., not dependent on row, diagonal/column parity), and is not dependant on a prime number of drives, phantom drives, or phantom data.  
         [0011]     In short, there is a need for an algorithm that compensates for dual-storage element failures in a networked storage system. There is a need for a dual parity calculating algorithm that is not dependent on symbol position, a prime number of drives, phantom drives, or phantom data. And, there is a need for a dual parity calculating algorithm that either runs once a priori or that may be used in real time, without adversely affecting system performance.  
       BRIEF SUMMARY OF THE INVENTION  
       [0012]     A method of calculating single and dual parity for a networked array of storage elements is presented. The method includes deriving a first set of n relationships where each of the first set of n relationships consists of an XOR statement equaling zero. Each of the first set of n relationships contains n data symbols from n storage elements and one parity symbol from a first set of parity symbols. The method also includes deriving a second set of n+1 relationships where each of the second set of n+1 relationships consists of an XOR statement equaling zero, containing at least n−1 data symbols from at least n−1 storage elements and one parity symbol from a second set of parity symbols. Using both the first and second sets of derived relationships, scripts are generated to resolve unresolved symbols resulting from possible single- and dual-storage element failure combinations.  
         [0013]     A system is also presented that calculates single and dual parity for a networked array of storage elements. The system includes a set of n networked data storage elements, each of the n data storage elements partitioned into n partitions, each partition configured to store a symbol. The system also includes a first parity storage element partitioned into n partitions and networked with the set of n data storage elements, each partition configured to store a symbol. A second parity storage element is partitioned into n+1 partitions and networked with the set of n data storage elements and the first parity storage element, each partition configured to store a symbol. The system further includes a storage controller that contains a parity generation and data regeneration module. The module is configured to access and run scripts to resolve unresolved symbols resulting from possible single- and dual-storage element failure combinations. The scripts use a first and a second set of relationships, wherein each of the first set of relationships consists of n data symbols from the n data storage elements and one parity symbol from the first parity storage element. Each of the first set of relationships consist of an XOR statement equaling zero. Each of the second set of relationships consists of at least n−1 data symbols from at least n−1 storage elements and one parity symbol from the second parity storage element. Each of the second set of relationships consists of an XOR statement equaling zero.  
         [0014]     These and other aspects of the invention will be more clearly recognized from the following detailed description of the invention which is provided in connection with the accompanying drawings.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0015]      FIG. 1  is a flow diagram that illustrates a method of deriving surviving relationships in a networked storage system in accordance with an embodiment of the invention;  
         [0016]      FIG. 2  is a flow diagram that illustrates a more detailed method of resolving symbols in accordance with an embodiment of the invention; and  
         [0017]      FIG. 3  illustrates a dual-parity generation and data recovery system, according to an embodiment of the invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0018]     The present invention is a method of calculating dual parity that compensates for one or two storage element failures in a networked storage system with n number of storage elements, without imposing a requirement to install a prime number of storage elements, use phantom storage elements, or use phantom data. The method enables efficient calculation of updated parity symbols for every write operation and data regeneration with fewer XOR operations than other existing prior art algorithms. Unlike most RAID 6 dual-parity calculation algorithms which use row symbol and column symbol parity (or diagonal symbol parity), the method described in this invention works independent of symbol positions and is, therefore, more versatile.  
         [0019]     The method uses n number of symbols for n number of data storage elements, where n is any integer value. Additionally, there is a P storage element that includes n number of symbols, and a Q storage element that includes n+1 number of symbols. For example, in an 8+2 system, there are eight data storage elements plus a P storage element and a Q storage element. In this example, there are also eight symbols per data storage element and per P storage element. There are nine symbols on the Q storage element.  
         [0020]     The following table, Table 1, illustrates an example of an 8+2 system with eight data storage elements, each including eight symbols, a P storage element, also including eight symbols, and a Q storage element that includes nine symbols.  
         [0021]     The disclosed method of calculating dual parity for a networked storage system assumes that each block of data in a storage element (represented by a column in Table 1) is a group of n symbols. For this example, there are eight data storage elements and, thus, eight symbols per data storage element. A symbol may be an arbitrary number of bytes, a word, a portion of a sector, or a block of sectors.  
                                                                                                                     TABLE 1                           Example P relationships, where the P relationships are the seed       for a method of calculating dual parity for an       8 + 2 networked storage system.       P Relationships                D r i v e s                 0   1   2   3   4   5   6   7       P                        0   P 1     P 6     P 2     P 3     P 8     P 6     P 1     P 3     0   P 3         1   P 2     P 3     P 1     P 2     P 3     P 7     P 3     P 1     1   P 2         2   P 3     P 1     P 3     P 5     P 4     P 2     P 4     P 2     2   P 1         3   P 4     P 2     P 6     P 4     P 6     P 1     P 2     P 5     3   P 8         4   P 5     P 4     P 5     P 1     P 2     P 3     P 5     P 6     4   P 7         5   P 6     P 8     P 4     P 6     P 7     P 5     P 7     P 4     5   P 4         6   P 7     P 5     P 7     P 8     P 1     P 4     P 6     P 7     6   P 6         7   P 8     P 7     P 8     P 7     P 5     P 8     P 8     P 8     7   P 5                    
 
         [0022]     A relationship is a set of symbols that XOR to logical ‘0.’ Additionally, the number of symbols in each relationship equation is equal to the number of data drives in the networked system plus one. The P relationships are a simple set of relationships between the symbols of storage elements and one symbol from the P parity storage element, where each relationship is P n . Each P n  includes one symbol from each data storage element and one symbol from the P storage element; each non-Q storage element symbol is in one, and only one, P n .  
         [0023]     For example, in Table 1, using the symbol ˆ to mean XOR, D[d,s] to represent a data storage element symbol where d is the storage element number and s is the symbol number, and P[s] and Q[s] of the P parity and the Q parity storage elements, respectively: P 1 : 0=P[2]ˆD[0,0]ˆD[1,2]ˆD[2,1]ˆD[3,4]ˆD[4,6]ˆD[5,3]ˆD[6,0]ˆD[7,1]. This example relationship represents a P relationship, because a symbol from the P storage element is used in the equation, the equation includes n+1 symbols, and there are n P n  relationship equations, which translates to eight P relationships (P 1 -P 8 ) for this example. In the example in Table 1, the number of terms in the XOR equation for each P relationship is equal to the number of data storage elements in the system plus the P parity symbol, which is nine.  
         [0024]     There are no relational requirements, such as horizontal, diagonal, or adjacent positions of symbols, as required by other algorithms. In the example in Table 1, there are eight individual P n  relationships. The number of relationship equations is equal to the number of symbols in a column. For this example, there are eight relationship equations (P 1 -P 8 ). No two relationships have a symbol in common, and each relationship has one symbol from each data storage element and one symbol from the P parity storage element. Thus, for any one missing non-Q symbol, there is a P relationship that can be used to resolve the missing symbol. The P relationship set is made up of the individual P n  relationships. The P relationship set shown in Table 1 is as follows: 
    P 1 : 0=P[2]ˆD[0,0]ˆD[1,2]ˆD[2,1]ˆD[3,4]ˆD[4,6]ˆD[5,3]ˆD[6,0]ˆD[7,1]    P 2 : 0=P[1]ˆD[0,1]ˆD[1,3]ˆD[2,0]ˆD[3,1]ˆD[4,4]ˆD[5,2]ˆD[6,3]ˆD[7,2]    P 3 : 0=P[0]ˆD[0,2]ˆD[1,2]ˆD[2,2]ˆD[3,0]ˆD[4,1]ˆD[5,4]ˆD[6,1]ˆD[7,0]    P 4 : 0=P[5]ˆD[0,3]ˆD[1,4]ˆD[2,5]ˆD[3,3]ˆD[4,2]ˆD[5,6]ˆD[6,2]ˆD[7,5]    P 5 : 0=P[7]ˆD[0,4]ˆD[1,6]ˆD[2,4]ˆD[3,2]ˆD[4,7]ˆD[5,5]ˆD[6,4]ˆD[7,3]    P 6 : 0=P[6]ˆD[0,5]ˆD[1,0]ˆD[2,3]ˆD[3,5]ˆD[4,3]ˆD[5,0]ˆD[6,6]ˆD[7,4]    P 7 : 0=P[4]ˆD[0,6]ˆD[1,7]ˆD[2,6]ˆD[3,7]ˆD[4,5]ˆD[5,1]ˆD[6,1]ˆD[7,6]    P 8 : 0=P[3]ˆD[0,7]ˆD[1,5]ˆD[2,7]ˆD[3,6]ˆD[4,0]ˆD[5,7]ˆD[6,7]ˆD[7,7]   
 
         [0033]     The Q relationship set is derived by use of the following first embodiment guidelines. The individual relationships within the Q relationship set are defined as Q n . There are n+1 individual Q relationships. Each Q n  includes a symbol from the Q parity storage element and one symbol from all the data storage elements and P parity storage element except one. Each storage element symbol is in one, and only one, Q n . No two symbols in a Q n  relationship are in a P n  relationship. No two Q n  relationships exclude the same storage element. Table 2 shows an example Q relationship set constrained by the P relationship set shown in Table 1.  
                                                                                                                             TABLE 2                           An example 8 + 2 Q relationship set constrained by       the P relationship set shown in Table 1.       Q Relationships                d r i v e s                0   1   2   3   4   5   6   7       P   Q                        0   Q 1     Q 5     Q 9     Q 9     Q 4     Q 1     Q 4     Q 5     0   Q 4     Q 2         1   Q 2     Q 2     Q 8     Q 8     Q 8     Q 2     Q 6     Q 3     1   Q 3     Q 1         2   Q 3     Q 9     Q 1     Q 2     Q 9     Q 6     Q 7     Q 4     2   Q 2     Q 3         3   Q 4     Q 1     Q 4     Q 1     Q 2     Q 5     Q 5     Q 7     3   Q 9     Q 5         4   Q 5     Q 3     Q 3     Q 7     Q 7     Q 7     Q 8     Q 8     4   Q 8     Q 6         5   Q 6     Q 7     Q 2     Q 3     Q 3     Q 9     Q 1     Q 6     5   Q 5     Q 4         6   Q 7     Q 4     Q 5     Q 5     Q 6     Q 8     Q 9     Q 9     6   Q 7     Q 9         7   Q 8     Q 6     Q 6     Q 4     Q 1     Q 3     Q 2     Q 1     7   Q 6     Q 8                                                     Q 7                    
 
         [0034]     The Q n  relationships that make up the Q relationship set are as follows:  
         [0035]     Q 1 : 0=Q[1]ˆD[0,0]ˆD[1,3]ˆD[2,2]ˆD[3,3]ˆD[4,7]ˆD[5,0]ˆD[ 6 , 5 ]ˆD[ 7 , 7 ] (skipped P)  
         [0036]     Q 2 : 0=Q[0]ˆP[2]ˆD[0,1]ˆD[1,3]ˆD[2,5]ˆD[3,2]ˆD[4,3]ˆD[5,1]ˆD[6,7] (skipped D7)  
         [0037]     Q 3 : 0=Q[2]ˆP[1]ˆD[0,2]ˆD[1,4]ˆD[2,4]ˆD[3,5]ˆD[4,5]ˆD[5,7]ˆD[7,1] (skipped D6)  
         [0038]     Q 4 : 0=Q[5]ˆP[0]ˆD[0,3]ˆD[1,6]ˆD[2,3]ˆD[3,7]ˆD[4,0]ˆD[6,0]ˆD[7,2] (skipped D5)  
         [0039]     Q 5 : 0=Q[3]ˆP[5]ˆD[0,4]ˆD[1,0]ˆD[2,6]ˆD[3,6]ˆD[5,3]ˆD[6,3]ˆD[7,0] (skipped D4)  
         [0040]     Q 6 : 0=Q[4]ˆP[7]ˆD[0,5]ˆD[1,7]ˆD[2,7]ˆD[4,6]ˆD[5,2]ˆD[6,1]ˆD[7,5] (skipped D3)  
         [0041]     Q 7 : 0=Q[8]ˆP[6]ˆD[0,6]ˆD[1,5]ˆD[3,4]ˆD[4,4]ˆD[5,4]ˆD[6,2]ˆD[7,3] (skipped D2)  
         [0042]     Q 8 : 0=Q[7]ˆP[4]ˆD[0,7]ˆD[2,1]ˆD[3,1]ˆD[4,1]ˆD[5,6]ˆD[6,4]ˆD[7,4] (skipped D1)  
         [0043]     Q 9 : 0=Q[6]ˆP[3]ˆD[1,2]ˆD[2,0]ˆD[3,0]ˆD[4,2]ˆD[5,5]ˆD[6,6]ˆD[7,6] (skipped D0)  
         [0044]     The Q relationship set shown in Table 2 abides by the algorithmic constraints, i.e., no data storage element symbol resides in two different Q relationships, only one data storage element or P parity storage element is missing from each Q relationship, and each non-Q storage element is skipped only once. Additionally, no two symbols in a Q relationship are in the same single P relationship. For example, D[0,0] and D[1,3] may not reside together in a single P n  relationship, as they reside in the same Q relationship, Q 1 , in this case.  
         [0045]     In a second embodiment, the symbol Q[8] may be generated (rather than stored) by the performance of an XOR operation on the symbols Q[0] through Q[7].  
         [0046]     In a second embodiment, the symbol Q[8] may be generated (rather than stored) by the performance of an XOR operation on the symbols Q[0] through Q[7]. This is because every data symbol and parity symbol exists in the expressions for Q[0] through Q[8]. For example, looking at the above equations: 
    Q[0]=P[2]ˆD[0,1]ˆD[1,3]ˆD[2,5]ˆD[3,2]ˆD[4,3]ˆD[5,1]ˆD[6,7]    Q[1]=D[0,0]ˆD[1,3]ˆD[2,2]ˆD[3,3]ˆD[4,7]ˆD[5,0]ˆD[6,5]ˆD[7,7]    Q[2]=P[1]ˆD[0,2]ˆD[1,4]ˆD[2,4]ˆD[3,5]ˆD[4,5]ˆD[5,7]ˆD[7,1]    Q[3]=P[5]ˆD[0,4]ˆD[1,0]ˆD[2,6]ˆD[3,6]ˆD[5,3]ˆD[6,3]ˆD[7,0]    Q[4]=P[7]ˆD[0,5]ˆD[1,7]ˆD[2,7]ˆD[4,6]ˆD[5,2]ˆD[6,1]ˆD[7,5]    Q[5]=P[0]ˆD[0,3]ˆD[1,6]ˆD[2,3]ˆD[3,7]ˆD[4,0]ˆD[6,0]ˆD[7,2]    Q[6]=P[3]ˆD[1,2]ˆD[2,0]ˆD[3,0]ˆD[4,2]ˆD[5,5]ˆD[6,6]ˆD[7,6]    Q[7]=P[4]ˆD[0,7]ˆD[2,1]ˆD[3,1]ˆD[4,1]ˆD[5,6]ˆD[6,4]ˆD[7,4]    Q[8]=P[6]ˆD[0,6]ˆD[1,5]ˆD[3,4]ˆD[4,4]ˆD[5,4]ˆD[6,2]ˆD[7,3]   
 
         [0056]     Therefore, Q[0]ˆQ[1]ˆQ[2]ˆQ[3]ˆQ[4]ˆQ[5]ˆQ[6]ˆQ[7]ˆQ[8]= 0 , thus Q[8]=Q[0]ˆQ[1]ˆQ[2]ˆQ[3]ˆQ[4]ˆQ[5]ˆQ[6]ˆQ[7].  
         [0057]     This embodiment has the advantage of providing data efficiency equal to n/(n+2), which is 80% for this example ( 8/10=80%). In the previous embodiment, the data efficiency is equal to n 2 /(n 2 +2n+1), which is 79% for the 8+2 example. During write operations, this embodiment provides better data efficiency, because there is no need to calculate the Q[n+1] symbol (shown as Q[8] in this example) and, thus, the processing cycles required to calculate Q[8] are saved; however, there is processor overhead required to calculate the Q[n+1] symbol (Q[8] in this example) during degraded operations (e.g., one or two storage elements have failed and data from a failed drive has been requested). In the first embodiment, additional processing cycles required to calculate the Q[n+1] symbol during degraded operations is avoided, because the Q[n+1] symbol has been previously calculated and stored during the last write operation.  
         [0058]     For any two storage element failures, sixteen symbols in Tables 1 and 2 become unknown. Thus, for any P or Q relationship, there are one or two missing symbols. A surviving relationship has only one symbol that is unknown. Any relationship that has no unknown symbols is called an intact relationship, and relationships that have two unknowns are called non-surviving relationships. By generating symbols from surviving relationships, more non-surviving relationships are resolved-into surviving relationships. The result of the method described herein is a set of P and Q relationships that satisfies the cases where all lost symbols can be regenerated (i.e., no data is lost) for any single- and dual-storage element failures.  
         [0059]     This method for calculating surviving relationships uses a P relationship set (example shown in Table 1) as a seed for deriving a Q relationship set (example shown in Table 2). The resulting parity symbols ensure data integrity, regardless of any combination of dual-storage element failures. The method for deriving the Q relationship set is further described below.  
         [0060]      FIG. 1  is a method  100  of deriving a P and Q relationship set.  
         [0061]     Step  110 : Deriving a P Relationship Set Based on Constraints.  
         [0062]     In this step, method  100  derives a P relationship from the constraints provided in the detailed example above and further summarized as follows. There are n P relationships. Each P relationship has n+1 symbols: one symbol from each storage element from a set of n+1 storage elements formed of n data storage elements and one P parity storage element. No two P relationships share the same symbol. These P relationships may be obtained manually or by the use of a simple computer program that could be easily developed by one skilled in the art. Method  100  proceeds to step  120 .  
         [0063]     Step  120 : Deriving a Q Relationship Set Based on Constraints.  
         [0064]     In this step, method  100  derives the Q relationship set from the constraints provided in the detailed example above and further summarized as follows. There are n+1 Q-relationships.  
         [0065]     Each Q relationship has n+1 symbols: one symbol from the Q parity storage element and one symbol from each storage element, from a set of n storage elements chosen out of a set of n+1 storage elements formed of n data storage elements and one P parity storage element. No two Q relationships miss the same storage element. No two symbols in a Q relationship have a P relationship in common (every non-Q symbol is in exactly one P relationship and one Q relationship). No two Q relationships share the same symbol. Method  100  proceeds to step  130 .  
         [0066]     Step  130 : Generating Scripts.  
         [0067]     In this step, method  100  evaluates all single- and dual-storage element failure combinations. For each failure case, method  100  identifies intact, surviving, and non-surviving relationships. These relationships include both P and Q relationship sets (totaling 2n+1 relationships). Method  100  resolves missing symbols by using the surviving relationships, which in turn result in additional surviving relationships. This process continues until all missing symbols have been resolved (thus, all relationships are intact) and the XOR expression that corresponds to each resolved symbol is written to a file as a script. The ability to resolve all missing symbols for all failure cases proves that the corresponding P and Q relationship sets ensure that no data is lost. Method  100  ends. A detailed description of a method resolving the symbols of method  100  is described in  FIG. 2 .  
         [0068]      FIG. 2  is a detailed description of a method  200  of resolving the symbols described in step  130  of  FIG. 1 .  
         [0069]     Step  210 : Have all Storage Element Failure Combinations been Evaluated (Single and Dual)? 
         [0070]     In this decision step, method  200  determines whether all one- or two-storage element failure combinations have been evaluated. If yes, method  200  ends; if no, initially unresolved symbols for the next storage element failure combination are identified (32 unresolved symbols are created in any two-storage element failure combinations in the 8+2 example). Method  200  proceeds to step  220 .  
         [0071]     Step  220 : Identifying Intact, Surviving, and Non-Surviving Relationships.  
         [0072]     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 (totaling 2n+1 relationships). Method  200  proceeds to step  230 .  
         [0073]     Step  230 : Are all Relationships Intact? 
         [0074]     In this decision step, method  200  determines whether all relationships are intact. If yes, method  200  returns to step  210 ; if no, method  200  proceeds to step  240 .  
         [0075]     Step  240 : Resolving Unresolved Symbols.  
         [0076]     In this step, method  200  expresses the unresolved symbol as an XOR equation of resolved symbols. For example, if D[1,2] in Table 2 is an unresolved symbol, it can be resolved by use of the following XOR equation: 
    Q 9 : D[1,2]=Q[6]ˆP[3]ˆD[2,0]ˆD[3,0]ˆD[4,2]ˆD[5,5]ˆD[6,6]ˆD[7,6]   
 
         [0078]     Therefore, D[1,2] is known and becomes a resolved symbol. 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 (e.g., D[1,2] for this example). Method  200  returns to step  220 . Method  200  may be performed off-line in a separate system or in real time on networked storage system resources.  
         [0079]      FIG. 3  illustrates a dual-parity generation and data recovery system  300 . System  300  includes a host  310 , a storage controller  320  and a plurality of networked storage elements  340 . Storage controller  320  further includes a cache  322 , a mapping engine  324 , an enhanced parity generation and data regeneration system  226  which also includes a table  328 , and a buffer memory  329 . Host  310  is representative of any kind of mechanism that requests data reads and writes to and from storage elements  340 , which may be any type of networked storage system, for example, a fibre channel or SCSI. Individual storage elements  340  may be, for example, SATA or fibre channel drives. Mapping engine  324  is a transaction processor entity that translates all host  310  requests for specific volumes into the actual logical block addresses (LBAs) in storage elements  340  for storage controller  320 . Storage controller  320  is an integrated I/O controller that is fully explained in U.S. application Ser. No. 10/912,157 and further includes a scalable transaction processing pipeline that is explained in U.S. application Ser. No. 10/429,048; both US applications are hereby incorporated by reference.  
         [0080]     The scripts generated by method  100  are made available as scripts in table  328 . Each line of the script specifies the list of locations of the resolved symbols in buffer memory  329  that are to be XOR-ed to recover a missing symbol and the location where the recovered missing symbol (result of XORs) is to be saved. The semantics of this script language are described in U.S. Provisional Application No. 60/624,564, titled “Interpretive Language to Implement XOR-Based Algorithms,” hereby incorporated by reference.  
         [0081]     Table  328  includes a plurality of method  100  generated scripts that are initialized at power on. The number of scripts contiguously located in table  328  is representative of the number of possible storage element  340  failures. In this example, there is an 8+2 configuration (eight storage elements  340   a  through  340   h  for data and two storage elements for parity,  340   p  and  340   q,  respectively). Thus, the number of possible storage element failure combinations is  n C 2 + n C 1 , where n is the number of storage elements, and in this case is fifty-five for this particular configuration. For a 16+2 storage element configuration, the number of possible storage element failure combinations is 163.  
         [0082]     Each script corresponds to a particular storage element(s)  340  failure(s), including single- and dual-storage element  340  failures. For example, script one may correspond to a single failure by storage element  340   a,  and script fifty-five may correspond to a dual failure by storage elements  340   p  and  340   q.  These examples are provided for illustration only, and it will appreciated by one skilled in the art that the script number is arbitrarily assigned to a storage element failure or combination of failures.  
         [0083]     In the event of single- or dual-storage element  340  failure(s), storage controller  320  determines which storage element failure case is applicable. Mapping engine  324  determines the corresponding storage element  340  LBAs ( 340   p,    340   q,  and  340   a - 340   h ) for the corresponding volume and host  310  LBAs. For cases where no storage elements  340  have failed and a write operation is requested, mapping engine  324  specifies the offset (start of the relevant script) in table  328  for the script that corresponds to a dual failure by storage elements  340   p  and  340   q,  as this is the script for rebuilding the parity data stored on storage elements  340   p  and  340   q.  This script is executed by enhanced parity generation and data regeneration system  326 . 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.  
         [0084]     In a write operation, host  310  generates a write request to storage controller  320 . Cache  322  stores the write request and write data. Cache  322  sends a request to mapping engine  324  to flush the relevant data in buffer memory  329  to storage elements  340 . Mapping engine  324  determines that storage elements  340   p  and  340   q  need to be updated, as a result of the write operation. Mapping engine  324  specifies the script (table  328  offset) that needs to be executed by enhanced parity generation and data regeneration system  326  for generating the updated  340   p  and  340   q  parity data. Enhanced parity generation and data regeneration system  326  executes the commands for the specified script in table  328 , until the end of the script is reached. The result is updated P parity and Q parity symbols in buffer memory  329 . Storage controller  320  flushes the updated P and Q parity to storage elements  340   p  and  340   q,  respectively. Host  310  data is also flushed from buffer memory  329  to the corresponding storage elements  340   a - 340   h.  Finally, storage controller  320  sends a “done” signal to host  310 , which completes the write operation.  
         [0085]     In a missing data read operation caused by failed storage elements (for this example, storage elements  340   c  and  340   f  have failed), cache  322  determines that the host command is a cache miss. Cache  322  issues a read request to mapping engine  324 . Mapping engine  324  determines which storage elements  340  corresponding LBA ranges need to be read to satisfy the host  310  command and also allocates space in buffer memory  329  for holding parity and other data needed for regenerating missing data. Mapping engine  324  then issues read commands to the storage element  340  controllers (not shown) to read the relevant data from remaining functional storage elements  340 , including storage elements  340   p  and  340   q,  into buffer memory  329 . Mapping engine  324  translates the storage elements  340   c  and  340   f  failures to a corresponding table  328  script and passes the script offset and location of data and parity (read from storage element  340 ) in buffer memory  329  to enhanced parity generation and data regeneration system  326 . Enhanced parity and data regeneration system  326  executes the script in table  328  (mapping engine  324  specifies an offset location in table  328 , which is the start of the script). Enhanced parity and data regeneration system  326  regenerates the missing data for storage elements  340   c  and  340   f  from the remaining data (relevant data from functional storage elements  340 , including  340   p  and  340   q ) in buffer memory  329  and stores the regenerated data in buffer memory  329 . Storage controller  320  sends the requested data, including the reconstructed data, to host  310  from buffer memory  329 .  
         [0086]     The above description and drawings should only be considered illustrative of exemplary embodiments that achieve the features and advantages of the invention. Modification and substitutions to specific process conditions and structures can be made without departing from the spirit and scope of the invention. Accordingly, the invention is not to be considered as being limited by the foregoing description and drawings, but is only limited by the scope of the appended claims.