Granted Patent B1

US 7,188,270 · App. 10/300,981 · Granted Mar 6, 2007

Abstract

Claims (71)

1. A method of providing disk fault tolerance in an array of independent data storage disks, wherein the disks are indexed and organized into a plurality of indexed stripes, each stripe further comprising a plurality of strips indexed by both disk and stripe, each of the strips being located on only a corresponding single disk, the method comprising:

forming a plurality of blocks, each block comprising a plurality of stripes extending across multiple disks;

reserving at least one parity stripe in each block for storing only parity in parity strips of the parity stripe;

dividing each block into a plurality of chunks, wherein each chunk is defined by the intersection of a respective block and the respective disk on which the strips comprising the chunk are located, and each strip of each chunk is defined by the intersection of a respective stripe and the respective disk on which the strip is located;

reserving at least one of the chunks for storing horizontal parity;

reserving at least one of the chunks for storing diagonal parity;

arranging, in respective blocks, strips containing data into horizontal and diagonal parity sets, wherein each parity set comprises at least one data strip as a member and no single data strip is repeated in any one parity set;

calculating, for respective blocks, a horizontal parity for each horizontal parity set;

calculating, for respective blocks, a diagonal parity for each diagonal parity set;

storing, in respective blocks, each respective calculated horizontal parity of each horizontal parity set in a corresponding strip of a horizontal parity chunk;

storing, in respective blocks, at least some of the calculated diagonal parities of each diagonal parity set in a respective one of a plurality of strips of a first diagonal parity chunk and storing, in respective blocks, a remainder of the calculated diagonal parities in a respective one of a plurality of strips in a first diagonal parity stripe so that no members of a contributing diagonal parity set have the same disk index as the disk index of the respective one of a plurality of strips of the first diagonal parity stripe; and

shifting the position of each parity chunk in each block to a different disk with respect to a corresponding parity chunk storing parity values of a corresponding parity set in adjacent blocks.

2. The method of claim 1 further comprising shifting the position of each parity strip in the at least one parity stripe in each block to a different disk with respect to corresponding parity strips in parity stripes in adjacent blocks.

3. The method of claim 1 , wherein shifting each parity chunk comprises:

moving each parity chunk in a block to a next lower indexed disk with respect to a preceding block; and

wrapping a parity chunk located in a lowest indexed disk to a highest indexed disk.

4. The method of claim 1 , further comprising, for each block:

establishing an initial diagonal parity set in a first diagonal direction as a data strip having the lowest disk index and the lowest stripe index of the block;

establishing consecutive diagonal parity sets by diagonally grouping the data strips adjacent to the previously established diagonal parity set until each data strip has been assembled into a diagonal parity set without wrapping around the array; and

grouping the established sets in the first diagonal direction into a first group.

5. The method of claim 4 further comprising, for each block:

establishing an initial diagonal parity set in a second diagonal direction different from the first diagonal direction as a data strip having the highest disk index of a disk storing data and the lowest stripe index of the block;

establishing consecutive diagonal parity sets by diagonally assembling the data strips adjacent to the previously established diagonal parity set until each data strip has been assembled into a diagonal parity set without wrapping around the array; and

grouping the established sets in the second diagonal direction into a second group so that each data strip is a member of the first and second group.

6. The method of claim 1 further comprising, for each block:

reserving the first diagonal parity stripe, across each of the disks in the array, to store diagonal parity; and

reserving the remaining unreserved strips in the remaining unreserved columns of the block for data.

7. The method of claim 5 , further comprising, for each block:

reserving a second diagonal parity chunk to store diagonal parity for the second group; and

reserving a second diagonal parity stripe to store diagonal parity for the second group.

8. The method of claim 1 , wherein calculating the horizontal parity, hP i , for each stripe containing data in each block using the XOR of the information in each data strip is performed according to the equation:

hP i =S i,1 ⊕S i,2 ⊕S i,3 . . . S i,N

where i is an index counter for the number of stripes in the array containing data, S i,j is the information stored in strip i of column j, and N is the number of disks containing data.

9. The method of claim 4 , wherein calculating a diagonal parity, d1P i , for each diagonal set of a first group traversing the stripes containing data using the exclusive-or sum of the information in each diagonal is performed according to the equations:

d 1 P i =S 1,i ⊕S 2,i−1 ⊕S 3,i−2 ⊕ . . . S i,1 , for i≦N;

d 1 P i =S i−N+1,N ⊕S i−N+2,N−1 ⊕S i−N+3,N−2 ⊕ . . . S i,1 , for N<i≦M ; and

d 1 P i =S i−N+1,N ⊕S i−N+2,N−1 ⊕S i−N+3,N−2 ⊕ . . . S M,i−M+1 , for M<i<M+N;

where i is an index counter for the number of stripes in the block containing data, S i,j is the information stored in strip i of column j, N is the number of disks containing data in the array, and M is the number of stripes containing data in the block.

10. The method of claim 5 , wherein calculating a diagonal parity, d2P i , for each diagonal of a second group traversing the stripes containing data using the exclusive-or sum of the information in each diagonal is performed according to the equations:

d 2 P i =S 1,N−i+1 ⊕S 2,N−i−1+2 ⊕S 3,N−i+3 ⊕ . . . S i,N , for i≦N;

d 2 P i =S i−N+1,1 ⊕S i−N+2,2 ⊕S i−N+3,3 ⊕ . . . S i,N , for N<i≦M ; and

d 2 P i =S i−N+1,1 ⊕S i−N+2,2 ⊕S i−N+3,3 ⊕ . . . S M,M+N−i , for M<i<M+N;

where i is an index counter for the number of stripes in the block containing data, S i,j is the information stored in strip i of column j, N is the number of disks containing data in the array, and M is the number of stripes containing data in the block.

11. The method of claim 1 , further comprising, for each block, reconstituting lost data on simultaneously failed disks by using the corresponding stored parity and data stored in the chunks on the remaining intact disks of the array.

12. A system for providing disk fault tolerance in an array of independent disks, comprising:

an array of disks consecutively indexed and organized into a plurality of indexed stripes, each stripe further comprising a plurality of strips indexed by both disk and stripe; and

an array controller coupled to the disk array and configured to:

form a plurality of blocks, each block comprising a plurality of stripes extending across multiple disks;

reserve at least one parity stripe in each block for storing only parity in parity strips of the parity stripe;

divide each block into a plurality of chunks, wherein each chunk is defined by the intersection of a respective block and the respective disk on which the strips comprising the chunk are located, and each strip of each chunk being defined by the intersection of a respective stripe and the respective disk on which the strip is located;

reserve at least one of the chunks for storing horizontal parity;

reserve at least one of the chunks for storing diagonal parity;

arrange, in respective blocks, strips containing data into horizontal and diagonal parity sets, wherein each parity set comprises at least one data strip as a member and no single data strip is repeated in any one parity set;

calculate, for respective blocks, a horizontal parity for each horizontal parity set for each block;

calculate, for respective blocks, a diagonal parity for each diagonal parity set for each block;

store, in respective blocks, each respective calculated horizontal parity of each horizontal parity set in a corresponding strip of a horizontal parity chunk for each block;

store, in respective blocks, at least some of the calculated diagonal parities of each diagonal parity set in a respective one of a plurality of strips of a first diagonal parity chunk and store, in respective blocks, a remainder of the calculated diagonal parities in a respective one of a plurality of strips in a first diagonal parity stripe so that no members of a contributing diagonal parity set have the same disk index as the disk index of the respective one of a plurality of strips of the first diagonal parity stripe for each block; and

shift the position of each parity chunk in each block to a different disk with respect to the parity chunk in adjacent blocks.

13. The system of claim 12 , wherein the array controller is further configured to shift the position of each parity strip in the at least one parity stripe in each block to a different disk with respect to corresponding parity strips in parity stripes in adjacent blocks.

14. The system of claim 12 , wherein the array controller is further configured to:

rotate each parity chunk in a block to a next lower indexed disk with respect to a preceding block; and

wrap a parity chunk located in a lowest indexed disk to a highest indexed disk.

15. The system of claim 12 , wherein the array controller is further configured for arranging strips containing data into diagonal parity sets, for respective blocks by:

establishing an initial diagonal parity set in a first diagonal direction as a data strip having the lowest disk index and the lowest stripe index of the block;

establishing consecutive diagonal parity sets by diagonally grouping the data strips adjacent to the previously established diagonal parity set until each data strip has been assembled into a diagonal parity set without wrapping around the array; and

grouping the established sets in the first diagonal direction into a first group.

16. The system of claim 15 , wherein the array controller is further configured for arranging strips containing data into diagonal parity sets, for respective blocks by:

establishing an initial diagonal parity set in a second diagonal direction as a data strip having the highest disk index of a disk storing data and the lowest stripe index of the block;

establishing consecutive diagonal parity sets by diagonally grouping the data strips adjacent to the previously established diagonal parity set until each data strip has been assembled into a diagonal parity set without wrapping around the array; and

grouping the established sets in the second diagonal direction into a second group so that each data strip is a member of the first and second group.

17. The system of claim 12 , wherein the array controller is further configured, for respective blocks, to reconstitute lost data on simultaneously failed disks by using the corresponding parity and data stored in the chunks on the remaining intact disks of the array.

Assignments (18)