Granted Patent B2

US 7,149,847 · App. 11/064,392 · Granted Dec 12, 2006

Abstract

Claims (57)

1. In an N-column by R-row logical representation of a set of stored elements in an array of independent disks, N being an odd number and R minus 1 being less than N divided by a number of disk failures F from which the array is to be recovered, the stored elements in the set to be recovered being organized into a plurality of stripes, each stripe comprising a plurality of strips, all strips of a column located on the same disk, a first portion of the strips containing stored data and a second portion of the strips containing parity values, and one and only one strip containing a parity value stored per column per set, except that at least two parity values are stored in at least one of a plurality of N-columns, a method of providing multiple disk fault tolerance comprising:

assigning each strip containing stored data to at least F different parity groups, F being greater than 2, so that each strip containing stored data in a respective column is assigned to parity groups different than other strips containing stored data in the same column;

calculating, for each parity group, a parity value corresponding to all of the strips assigned to the parity group; and

storing each of the parity values in strips of different columns so that none of the strips containing stored data in a column are assigned to a parity group whose parity value is stored in a strip of that column;

wherein storing each of the parity values further comprises:

reserving at least one parity row for storing a first portion of the parity values;

reserving at least one strip in a row different from the at least one parity row for storing a second portion of the parity values;

storing each of the parity values of the first portion in respective strips of the at least one reserved parity row; and

storing each of the parity values of the second portion in respective reserved strips in the row different from the at least one parity row.

2. The method of claim 1 , wherein calculating the parity values for each parity set comprises computing the exclusive-or (XOR) of the information in each stored data strip assigned to the respective parity group.

3. The method of claim 1 , wherein N−2 stored data strips are assigned to each parity group.

4. The method of claim 1 , wherein each stored element comprises one or more bits of information.

5. The method of claim 1 , further comprising, in the case of a simultaneous F disk failure, recovering data from the failed disks, comprising the steps of:

a. locating a first strip containing stored data on a first one of the failed disks so that none of the remaining strips containing stored data contributing to at least one of the parity groups of which the first data strip is a member of are located on the first one of the failed disks;

b. reconstructing the first strip containing stored data on the first one of the failed disks based on an XOR operation of the other members of the parity group of which the first strip containing stored data is a member and the parity value for the group;

c. locating a next strip containing stored data on the another failed disk, the next strip containing stored data being a member of a different parity group of which the previously reconstructed strip containing stored data is a member and of which parity group no other strip on any of the other (F−2) failed disks is a member;

d. reconstructing the next strip containing stored data based on an XOR operation of members of the different parity group and the parity for the different group;

e. sequentially locating and reconstructing remaining strips according to steps c–d until no further data strips can be recreated or a parity strip on a failed disk is reconstructed; and

f. sequentially locating and reconstructing strips according to steps a–e if un-reconstructed strips containing stored data remain after reconstructing the parity strip.

6. A method of providing multiple disk fault tolerance in an array of N independent disks, the array organized into a plurality of stripes, each stripe comprising a plurality of strips, the method comprising:

partitioning the array into a plurality of logically represented N-column by R-row sets, N being an odd number and R minus 1 being less than N divided by a number of disk failures F of the array to be recovered from, so that a plurality of N-columns correspond to a plurality of disks in the array, all strips of a column are located on the same disk, and a plurality of R-rows extend across all the disks in the array;

a first portion of the strips containing stored data and a second portion of the strips containing parity values, and one and only one strip containing a parity value stored per column per set, except that at least two parity values are stored in at least one of the plurality of N-columns;

assigning each strip containing data to at least three different parity groups, so that each strip containing stored data in a respective column is assigned to parity groups different than other strips containing stored data in the same column;

calculating a parity value for each parity group, wherein the parity value corresponds to all of the strips assigned to the parity group;

storing each of the parity values in strips of different columns so that none of the strips containing stored data in a column are assigned to a parity group whose parity value is stored in that column;

wherein storing each of the parity values further comprises:

reserving at least one parity row for storing a first portion of the parity values;

reserving at least one strip in a row different from the at least one parity row for storing a second portion of the parity values;

storing each of the parity value of the first portion in respective strips of the at least one reserved parity row; and

storing each of the parity values of the second portion in respective reserved strips in the row different from the at least one parity row.

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

an N-column by R-row logical representation of a set of stored elements in an array of independent disks, N being an odd number and R minus 1 being less than N divided by a number of disk failures F of the array to be recovered from, the stored elements in the set organized into a plurality of stripes, each stripe comprising a plurality of strips, all strips of a column located on the same disk, a first portion of the strips containing stored data and a second portion of the strips containing parity values, except at least two parity values are stored in respective different strips of at least one of a plurality of N-columns; and

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

a. assign each strip containing stored data to at least F different parity groups, F being greater than 2, so that each strip containing stored data in a respective column is assigned to parity groups different than other strips containing stored data in the same column;

b. calculate, for each parity group, a parity value corresponding to all of the strips assigned to the parity group; and

c. store each of the parity values in strips of different columns so that none of the strips containing stored data in a column are assigned to a parity group whose parity value is stored in a strip of that column;

wherein storing each of the parity values further comprises:

reserving at least one parity row for storing a first portion of the parity values;

reserving at least one strip in a row different from said at least one parity row for storing a second portion of the parity values;

storing each of the parity values of the first portion in respective strips of the at least one reserved parity row; and

storing each of the parity values of the second portion in respective reserved strips in the row different from the at least one parity row.

8. The system of claim 7 , the array controller further configured to recover data from failed disks by:

a. locating a first strip containing stored data on a first one of the failed disks so that none of the remaining strips containing stored data contributing to at least one of the parity groups of which the first data strip is a member of are located on the first one of the failed disks;

b. reconstructing the first strip containing stored data on the first one of the failed disks based on an XOR operation of the other members of the parity group of which the first strip containing stored data is a member and the parity value for the group;

c. locating a next strip containing stored data on the other failed disk, the next strip containing stored data being a member of a different parity group of which the previously reconstructed strip containing stored data is a member;

d. reconstructing the next strip containing stored data based on an XOR operation of members of the different parity group and the parity for the different group;

e. sequentially locating and reconstructing remaining strips according to steps c–d until no further data strips can be recreated or a parity strip on a failed disk is reconstructed; and

f. sequentially locating and reconstructing strips according to steps a–e if un-reconstructed strips containing stored data remain after reconstructing the parity strip.

9. A computer readable media storing a data structure suitable for providing multiple disk fault tolerance for an array of independent disks, the data elements in the array of independent disks represented by an N-column by R-row logical matrix, N being an odd number and R minus 1 being less than N divided by a number of disk failures, F, from which the array is to be recovered, the data elements in the matrix organized into a plurality of matrix stripes, each matrix stripe comprising a plurality of matrix strips, all strips of a matrix column located on the same disk; each matrix strip containing data being assigned to F different parity groups so that each matrix strip containing data in a respective matrix column is assigned to parity groups different than other matrix strips containing data in the same matrix column, a respective parity value corresponding to all of the matrix strips assigned to the parity group being stored in respective matrix strips of different matrix columns so that none of the matrix strips containing data in a matrix column are assigned to a parity group whose parity value is stored in that matrix column, except that at least two mapping table entries mapped to respective parity values are stored in respective different matrix strips of at least one of a plurality of N-columns, the data structure comprising:

an N-column by R-row mapping table, each mapping table entry mapped to a corresponding data element in the matrix and organized into mapping table columns and mapping table rows;

each mapping table entry mapped to a respective data value in the matrix comprising F parity group identifiers, each group identifier indicative of the respective F different parity groups to which the data value has been assigned; and

each mapping table entry mapped to respective parity value in the matrix comprising a parity value identifier, each parity value identifier indicative of the respective parity group to which the parity value belongs;

wherein storing mapping table entries mapped to respective parity values further comprises:

reserving at least one matrix parity row for storing a first portion of the mapping table entries mapped to respective parity values;

reserving at least one matrix strip in a matrix row different from the at least one matrix parity row for storing a second portion of the mapping table entries mapped to respective parity values;

storing each of the mapping table entries mapped to respective parity values of the first portion in respective matrix strips of the at least one reserved matrix parity row; and

storing each of the mapping table entries mapped to respective parity values of the second portion in respective reserved matrix strips in the matrix row different from the at least one matrix parity row.

Assignments (17)