Row-diagonal parity technique for enabling efficient recovery from double failures in a storage array
First Claim
1. A method for enabling recovery from two or fewer concurrent failures of storage devices in a storage array, the method comprising the steps of:
- providing the array with a predetermined number of storage devices, including a plurality of first devices configured to store data and row parity, and one diagonal parity device configured to store diagonal parity, wherein the predetermined number of storage devices n is p+1 and wherein p is a prime number;
dividing each device into blocks;
organizing the blocks into stripes that contain a same number of blocks in each device, wherein each stripe comprises n−
2 rows of blocks;
defining the diagonal parity along diagonal parity sets that span the first devices, wherein the diagonal parity sets wrap around within a group of n−
2 rows so that all blocks belonging to diagonal parity sets of a stripe are stored in the stripe; and
computing and storing the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device.
4 Assignments
0 Petitions
Accused Products
Abstract
A “row-diagonal” (R-D) parity technique reduces overhead of computing diagonal parity for a storage array adapted to enable efficient recovery from the concurrent failure of two storage devices in the array. The diagonal parity is computed along diagonal parity sets that collectively span all data disks and a row parity disk of the array. The parity for all of the diagonal parity sets except one is stored on the diagonal parity disk. The R-D parity technique provides a uniform stripe depth and an optimal amount of parity information.
118 Citations
41 Claims
-
1. A method for enabling recovery from two or fewer concurrent failures of storage devices in a storage array, the method comprising the steps of:
-
providing the array with a predetermined number of storage devices, including a plurality of first devices configured to store data and row parity, and one diagonal parity device configured to store diagonal parity, wherein the predetermined number of storage devices n is p+1 and wherein p is a prime number;
dividing each device into blocks;
organizing the blocks into stripes that contain a same number of blocks in each device, wherein each stripe comprises n−
2 rows of blocks;
defining the diagonal parity along diagonal parity sets that span the first devices, wherein the diagonal parity sets wrap around within a group of n−
2 rows so that all blocks belonging to diagonal parity sets of a stripe are stored in the stripe; and
computing and storing the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A system configured to enable recovery from two or fewer concurrent failures of two storage devices, the system comprising:
-
an array having a predetermined number of storage devices, including a plurality of first devices configured to store data and row parity, and one diagonal parity device configured to store diagonal parity, wherein the predetermined number of storage devices n is p+1 and wherein p is a prime number;
a storage operating system including a device storage layer configured to implement a row-diagonal (R-D) parity technique that computes the diagonal parity along diagonal parity sets that span the first devices, and that stores the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device; and
a processing element configured to execute the storage operating system to thereby invoke storage access operations to and from the array in accordance with the R-D parity technique. - View Dependent Claims (8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. Apparatus for enabling recovery from two or fewer concurrent failures of two storage devices in a storage array, the apparatus comprising:
-
means for providing the array with a predetermined number of storage devices, including a plurality of first devices configured to store data and row parity, and one diagonal parity device configured to store diagonal parity, wherein the predetermined number of storage devices n is p+1 and wherein p is a prime number;
means for computing the diagonal parity along diagonal parity sets that span the first devices; and
means for storing the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device. - View Dependent Claims (19, 20, 21, 22, 23)
-
-
24. A computer readable medium containing executable program instructions for enabling recovery from two or fewer concurrent failures of two storage devices in a storage array, the executable program instructions comprising program instructions for:
-
providing the array with a predetermined number of storage devices, including a plurality of first devices configured to store data and row parity, and one diagonal parity device configured to store diagonal parity, wherein the predetermined number of storage devices n is p+1 and wherein p is a prime number;
computing the diagonal parity along diagonal parity sets that span the first devices; and
storing the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device. - View Dependent Claims (25, 26, 27, 28, 29)
-
-
30. A method for enabling recovery from two or fewer concurrent failures of two storage devices in a storage array, the method comprising the steps of:
-
providing the array with a predetermined number of storage devices equal to n, where n=p+1 and p is a prime number, including n−
2 data devices configured to hold data, one row parity device and one diagonal parity device;
dividing each device into blocks of fixed size;
organizing the blocks into stripes, wherein each stripe comprises n−
2 rows of blocks such that each device contains n−
2 blocks per stripe;
computing the diagonal parity along n−
2 of n−
1 parity sets (diagonal) of blocks that span the data devices and the row parity device, wherein the blocks of a diagonal are contained within a stripe, each diagonal containing a set of n−
2 blocks selected from among data and row parity blocks in a stripe such that no diagonal contains more than one block from a same row, each diagonal further containing n−
2 blocks from a group of n−
2 rows and no diagonal containing two blocks from a same device;
storing, on the row parity device, row parity for rows of blocks computed across all of the data devices such that each row contains one block from each data device and no row contains two blocks from a same diagonal; and
storing, in the n−
2 blocks in the stripe on the diagonal parity device, the diagonal parity of n−
2 of the n−
1 diagonals, wherein selection of the diagonals stored on the diagonal parity device is predetermined and wherein an order of placement of the n−
2 diagonal parity blocks in the stripe on the diagonal parity device is predetermined. - View Dependent Claims (31, 32, 33, 34, 35)
-
-
36. A method for enabling recovery from two or fewer concurrent failures of two storage devices in a storage array, the method comprising the steps of:
-
providing the array with a predetermined number of storage devices, including a plurality of first devices configured to store data and row parity, and one diagonal parity device configured to store diagonal parity;
computing the diagonal parity along diagonal parity sets that span the first devices; and
storing the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device. - View Dependent Claims (37, 38, 39, 40)
-
-
41. A method for enabling recovery from two or fewer concurrent failures of two storage devices in a storage array, the method comprising the steps of:
-
providing the array with a predetermined number of storage devices equal to n, where n=p+1 and p is a prime number, including n−
2 data devices configured to hold data, one row parity device and one diagonal parity device;
dividing each device into blocks of fixed size;
organizing the blocks into stripes, wherein each stripe comprises n−
2 rows of blocks such that each device contains n−
2 blocks per stripe and wherein locations of parity blocks shift from device to device within different stripes;
computing the diagonal parity along n−
2 of n−
1 parity sets (diagonal) of blocks that span the data devices and the row parity device, wherein the blocks of a diagonal are contained within a stripe, each diagonal containing a set of n−
2 blocks selected from among data and row parity blocks in a stripe such that no diagonal contains more than one block from a same row, each diagonal further containing n−
2 blocks from a group of n−
2 rows and no diagonal containing two blocks from a same device;
storing, on the row parity device, row parity for rows of blocks computed across all of the data devices such that each row contains one block from each data device and no row contains two blocks from a same diagonal; and
storing, in the n−
2 blocks in the stripe on the diagonal parity device, the diagonal parity of n−
2 of the n−
1 diagonals, wherein selection of the diagonals stored on the diagonal parity device is predetermined and wherein an order of placement of the n−
2 diagonal parity blocks in the stripe on the diagonal parity device is predetermined.
-
Specification