Uniform and symmetric double failure correcting technique for protecting against two disk failures in a disk array
First Claim
1. A system configured to provide double failure-correction of two or fewer storage device failures in a storage system, the system comprising:
- an array having a number of storage devices, wherein the number of storage devices is p and wherein p is a prime number greater than two, the storage devices including two storage devices selected to store redundant information, the remaining storage devices configured to store data; and
a storage module of the storage system, the storage module adapted to construct the redundant information using a redundant storage algorithm involving summation or combination computation along row parity sets (rows) and diagonal parity sets (diagonals) of the array for storage on the selected storage devices, wherein the redundant storage algorithm used to construct the two or fewer storage device failures is the same regardless of which storage devices fail or roles of the storage devices when constructing or reconstructing the redundant information or data.
2 Assignments
0 Petitions
Accused Products
Abstract
A uniform and symmetric, double failure-correcting technique protects against two or fewer disk failures in a disk array of a storage system. A RAID system of the storage system generates two disks worth of “redundant” information for storage in the array, wherein the redundant information (e.g., parity) is illustratively derived from computations along both diagonal parity sets (“diagonals”) and row parity sets (“rows”). Specifically, the RAID system computes row parity along rows of the array and diagonal parity along diagonals of the array. However, the contents of the redundant (parity) information disks interact such that neither disk contains purely (solely) diagonal or row redundancy information; the redundant information is generated using diagonal parity results in row parity computations (and vice versa).
74 Citations
63 Claims
-
1. A system configured to provide double failure-correction of two or fewer storage device failures in a storage system, the system comprising:
-
an array having a number of storage devices, wherein the number of storage devices is p and wherein p is a prime number greater than two, the storage devices including two storage devices selected to store redundant information, the remaining storage devices configured to store data; and
a storage module of the storage system, the storage module adapted to construct the redundant information using a redundant storage algorithm involving summation or combination computation along row parity sets (rows) and diagonal parity sets (diagonals) of the array for storage on the selected storage devices, wherein the redundant storage algorithm used to construct the two or fewer storage device failures is the same regardless of which storage devices fail or roles of the storage devices when constructing or reconstructing the redundant information or data. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A system configured to provide double failure-correction of two or fewer storage device failures in a storage system, the system comprising:
-
an array having a number of storage devices, wherein the number of storage devices is p and wherein p is a prime number greater than two, the storage devices including two storage devices selected to store redundant information, the remaining storage devices configured to store data; and
a storage module of the storage system, the storage module adapted to construct the redundant information using a redundant storage algorithm involving summation or combination computation along row parity sets (rows) and diagonal parity sets (diagonals) of the array for storage on the selected storage devices, the storage module further adapted to use the redundant storage algorithm to reconstruct the two or fewer storage device failures, wherein the storage devices have a storage space divided into stripes with any two storage devices selected to store the redundant information, the selected storage devices varying from stripe to stripe, arbitrarily, and wherein the two or fewer storage device failures are recovered without any knowledge of roles of those devices or any other storage device in the array. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. A method for protecting against two or fewer disk failures in a storage system, the method comprising the steps of:
-
providing an array with a number of disks, wherein the number of disks is p and wherein p is a prime number greater than two, the disks including two disks selected to store redundant information, the remaining disks configured to store data;
computing the redundant information through summation or combination computation along row parity sets (rows) and diagonal parity sets (diagonals) of the array; and
storing the computed redundant information on the selected disks. - View Dependent Claims (29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42)
-
-
43. A system configured to provide double failure-correction of two or fewer storage device failures in a storage system, the system comprising:
-
an array having a number of storage devices, wherein the number of storage devices is p and wherein p is a prime number greater than two, the storage devices including two storage devices selected to store redundant information, the remaining storage devices configured to store data; and
a storage module of the storage system, the storage module adapted to construct the redundant information using a redundant storage algorithm involving summation or combination computation along row parity sets (rows) and diagonal parity sets (diagonals) of the array for storage on the selected storage devices, the storage module further adapted to use the redundant storage algorithm to reconstruct the two or fewer storage device failures, regardless of which storage devices fail or whether the storage devices store redundant information or data, wherein the storage devices have a storage space divided into stripes with any two storage devices selected to store the redundant information, the selected storage devices varying from stripe to stripe, arbitrarily, and wherein the two or fewer storage device failures are recovered without any knowledge of roles of those devices or any other storage device in the array. - View Dependent Claims (44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60)
-
-
61. Apparatus for protecting against two or fewer disk failures in a storage system, the apparatus comprising:
-
means for providing an array with a number of disks, wherein the number of disks is p and wherein p is a prime, the disks including two disks selected to store redundant information, the remaining disks configured to store data;
means for computing the redundant information from both diagonal and row parity computation contributions; and
means for storing the computed redundant information on the selected disks, such that neither selected disk contains solely diagonal or row parity information. - View Dependent Claims (62)
-
-
63. A method for correcting double failures within data adapted for transmission over a communication medium, the method comprising the steps of:
-
dividing the data into packets for transmission over the communications medium;
organizing the packets into one or more groups adapted to employ a uniform and symmetric double failure-correcting algorithm to protect against two or fewer failures of packets within any one of the groups, wherein each group comprises p packets with p equal to a prime greater than two and wherein a value of p may vary among the groups, and wherein two packets of each group are selected to store redundant information, the remaining packets of the group configured to store data;
computing the redundant information through summation or combination computation along row parity sets (rows) and diagonal parity sets (diagonals) of the group; and
storing the computed redundant information in the selected packets.
-
Specification