Row-diagonal parity technique for enabling efficient recovery from double failures in a storage array
First Claim
Patent Images
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.
207 Citations
103 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; andcomputing 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, 8, 9, 10)
-
-
11. 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 (12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 37)
-
-
22. 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 (23, 24, 25, 26, 27, 28, 29, 30, 31)
-
-
32. 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 (33, 34, 35, 36)
-
-
38. 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 (39, 40, 41, 42, 43)
-
-
44. 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 (45, 46, 47, 48)
-
-
49. 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.
-
-
50. A method for enabling recovery from two or fewer concurrent failures of storage devices in a storage array, comprising:
-
storing data and row parity in stripes on a plurality of first storage devices, the stripes configured as rows of blocks on the first devices; defining diagonal parity sets that span the first devices; computing a diagonal parity for the diagonal parity sets; and storing the diagonal parity on a diagonal parity device, the diagonal parity device separate from the first storage devices, the storage array including the plurality of first storage devices and the diagonal parity device. - View Dependent Claims (51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71)
-
-
72. A storage array organized to enable recovery from two or fewer concurrent failures of storage devices, comprising:
-
means for storing data and row parity in stripes on a plurality of first storage devices, the stripes configured as rows of blocks on the first devices; means for defining diagonal parity sets that span the first devices; means for computing a diagonal parity for the diagonal parity sets; and means for storing the diagonal parity on a diagonal parity device, the diagonal parity device separate from the first storage devices, the storage array including the plurality of first storage devices and the diagonal parity device. - View Dependent Claims (73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93)
-
-
94. Computer readable media, comprising:
-
said computer readable media having instructions written thereon for execution on a processor for the practice of a method for enabling recovery from two or fewer concurrent failures of storage devices in a storage array, the method having the steps of, storing data and row parity in stripes on a plurality of first storage devices, the stripes configured as rows of blocks on the first devices; defining diagonal parity sets that span the first devices; computing a diagonal parity for the diagonal parity sets; and storing the diagonal parity on a diagonal parity device, the diagonal parity device separate from the first storage devices, the storage array including the plurality of first storage devices and the diagonal parity device.
-
-
95. A method for enabling recovery from two or fewer concurrent failures of storage devices in a storage array, the method comprising the steps of:
-
associating the array with a predetermined maximum number of storage devices, wherein the predetermined maximum number of storage devices n is p+1 and wherein p is a prime number; providing less than p first storage devices configured to store data and row parity; providing a diagonal parity storage device configured to store diagonal parity; configuring the array to treat one or more absent storage devices as a present storage device that contains zero-valued data; dividing the storage devices into blocks; defining the diagonal parity along diagonal parity sets that span the first storage devices and the one or more absent storage devices, wherein the diagonal parity sets wrap around within a group of n−
2 rows; andcomputing the diagonal parity for all of the diagonal parity sets except one, and storing the diagonal parity on the diagonal parity device.
-
-
96. Apparatus for enabling recovery from two or fewer concurrent failures of two storage devices in a storage array, the apparatus comprising:
-
means for associating the array with a predetermined maximum number of storage means, wherein the predetermined maximum number of storage means n is p+1 and wherein p is a prime number; less than p first storage means configured to store data and row parity; a diagonal parity storage means configured to store diagonal parity; means for configuring the array to treat one or more absent storage means as a present storage means that contains zero-valued data; means for dividing the storage means into blocks; means defining the diagonal parity along diagonal parity sets that span the first storage means and the one or more absent storage means, wherein the diagonal parity sets wrap around within a group of n−
2 rows; andmeans for computing the diagonal parity for all of the diagonal parity sets except one, and storing the diagonal parity on the diagonal parity storage means.
-
-
97. 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:
-
associating the array with a predetermined maximum number of storage devices, wherein the predetermined maximum number of storage devices n is p+1 and wherein p is a prime number; providing less than p first storage devices configured to store data and row parity; providing a diagonal parity storage device configured to store diagonal parity; configuring the array to treat one or more absent storage devices as a present storage device that contains zero-valued data; dividing the storage devices into blocks; defining the diagonal parity along diagonal parity sets that span the first storage devices and the one or more absent storage devices, wherein the diagonal parity sets wrap around within a group of n−
2 rows; andcomputing the diagonal parity for all of the diagonal parity sets except one, and storing the diagonal parity on the diagonal parity device.
-
-
98. A method for enabling recovery from two or fewer concurrent failures of storage devices in a storage array, the method comprising the steps of:
-
associating the array with a predetermined maximum number of storage devices, wherein the predetermined maximum number of storage devices n is p+1 and wherein p is a prime number; providing less than p first storage devices configured to store data and row parity; configuring the array to treat one or more absent storage devices as a present storage device that contains zero-valued data; defining row parity and storing row parity data; providing a diagonal parity storage device configured to store diagonal parity; defining the diagonal parity along diagonal parity sets that span the first storage devices; and computing the diagonal parity, and storing the diagonal parity on the diagonal parity device. - View Dependent Claims (99)
-
-
100. Apparatus for enabling recovery from two or fewer concurrent failures of two storage devices in a storage array, the apparatus comprising:
-
means for associating the array with a predetermined maximum number of storage devices, wherein the predetermined maximum number of storage devices n is p+1 and wherein p is a prime number; means for providing less than p first storage devices configured to store data and row parity; means for configuring the array to treat one or more absent storage devices as a present storage device that contains zero-valued data; means for defining row parity and storing row parity data; means for providing a diagonal parity storage device configured to store diagonal parity; means for defining the diagonal parity along diagonal parity sets that span the first storage devices; and means for computing the diagonal parity, and storing the diagonal parity on the diagonal parity device. - View Dependent Claims (101)
-
-
102. 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:
-
associating the array with a predetermined maximum number of storage devices, wherein the predetermined maximum number of storage devices n is p+1 and wherein p is a prime number; providing less than p first storage devices configured to store data and row parity; configuring the array to treat one or more absent storage devices as a present storage device that contains zero-valued data; defining row parity and storing row parity data; providing a diagonal parity storage device configured to store diagonal parity; defining the diagonal parity along diagonal parity sets that span the first storage devices; and computing the diagonal parity, and storing the diagonal parity on the diagonal parity device. - View Dependent Claims (103)
-
Specification