Method for storing parity and rebuilding data contents of failed disks in an external storage subsystem and apparatus thereof

A method for storing parity and rebuilding the data contents of two failed disks in an external storage subsystem, comprising the steps of:

• providing a disk array defined as a matrix of (N-1)*(N+1) including N+1 disks each logically divided into N-1 data blocks where N is a prime number, the data blocks of a row being defined as a horizontal parity group, the data blocks except the data blocks of the last (N+1) disk being in a rightwardly and upwardly continuous diagonal line being defined as a diagonal parity group;
• defining the data blocks of the last disk as horizontal parity blocks;
• defining the data blocks existing in the (N-1) row of said matrix as diagonal parity blocks;
• XORing the contents of each of said horizontal and diagonal parity groups to obtain the parity value stored into the parity block of the corresponding horizontal or diagonal parity group;
• and
• analyzing a diagonal parity group including an error data block of said two failed disks to restore said error data block and then, the horizontal parity group including said restored error data block to restore another error data block, wherein the last analyzing step is repeated to completely rebuild the data contents of said two failed disks.

In an external storage subsystem, which comprises a disk array defined as a matrix or (N-1)*N consisting of N disks each logically divided into N-1 data blocks where N is a prime number, the data blocks of each row being defined as a horizontal parity group, the data blocks existing in a rightwardly and upwardly continuous diagonal line being defined as a diagonal parity group, the data blocks existing in the diagonal line leftwardly and downwardly from the first data block of the (N-1) disk to the last data block of the first disk being defined as the horizontal parity blocks, the data blocks existing in the (N-1) row of said matrix being defined as diagonal parity blocks, where the contents of each of said horizontal and diagonal parity groups are XOR'ed by a controller to produce the parity value stored into the parity block of the corresponding horizontal or diagonal parity group, a method for rebuilding the data contents of two failed disks i and j where 0.ltoreq.i<j.ltoreq.N-1, comprising the steps of:

• (a) obtaining the difference k between the sequential numbers i and j of said two failed disks and initializing the parameter m to repeat the operation of rebuilding the data contents of said two failed disks to 0;
• (b) obtaining the value a(.sub.nj) of the "n"th block of the disk j having an error in the corresponding diagonal parity group by employing the following:
• ##EQU27## where n=N-1-k-m*k mod N and i+1-m*k+1 mod N.notident.j;
• (c) obtaining the value a(.sub.n,i) of the "n"th block of the disk i having an error in the corresponding horizontal parity group by employing the following:
• ##EQU28## Where 1.notident.j;
• and (d) repeating steps (b) and (c) while increasing the parameter to N-2.

In an external storage subsystem, which comprises a disk array defined as a matrix of (N-1)*(N+1) consisting of N+1 disks each logically divided into N-1 data blocks where N is a prime number, the data blocks of each row being defined as a horizontal parity group, the data blocks except the data blocks of the last (N+1) disk existing in a rightwardly and upwardly continuous diagonal line being defined as a diagonal parity group, the data blocks of the last disk being defined as horizontal parity blocks, the data blocks existing in the (N-1) row of said matrix being defined as the diagonal parity blocks, where the contents of each of said horizontal and diagonal parity groups are XOR'ed by a controller to produce the parity value stored into the parity block of the corresponding horizontal or diagonal parity group, a method for rebuilding the data contents of two failed disks i and j where 0.ltoreq.i<j.ltoreq.N-1, comprising the steps of:

• (a) obtaining the difference k between the sequential numbers i and j of said two failed disks and initializing the parameter m to repeat the operation of rebuilding the data contents of said two failed disks to 0;
• (b) obtaining the value a(.sub.nj) of the "n"th block of the disk j having an error in the corresponding diagonal parity group by employing the following:
• ##EQU29## where n=N-1-k-m*k mod N and
• i+l-m*k+l mod N.notident.j
• (c) obtaining the value a(.sub.n,i) of the "n"th block of the disk i having an error in the corresponding horizontal parity group by employing the following:
• ##EQU30## in case of n.notident.N-2 and i.notident.1 and ##EQU31## in case of n=N-2 and 1.notident.i;
• and (d) repeating steps (b) and (c) while increasing the parameter to N-2.