Triple parity technique for enabling efficient recovery from triple failures in a storage array
First Claim
1. A method for enabling recovery from three or fewer concurrent failures of storage devices in a storage array, comprising:
- providing the away with a predetermined number of storage devices, including a plurality of first devices configured to store data and row parity, one diagonal parity device configured to store diagonal parity and one anti-diagonal parity device configured to store anti-diagonal parity, wherein the predetermined number of storage devices n is p+2 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−
3 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−
3 rows;
computing and storing the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device;
defining the anti-diagonal parity along anti-diagonal parity sets that span the first devices, wherein the anti-diagonal parity set wraps around within a group of n−
3 rows; and
computing and storing the anti-diagonal parity for all the diagonal parity sets except one on the anti-diagonal parity device.
2 Assignments
0 Petitions
Accused Products
Abstract
A triple parity (TP) technique reduces overhead of computing diagonal and anti-diagonal parity for a storage array adapted to enable efficient recovery from the concurrent failure of three 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. Similarly, the anti-diagonal parity is computed along anti-diagonal parity sets that collectively span all data disks and a row parity disk of the array. The parity for all of the anti-diagonal parity sets except one is stored on the anti-diagonal parity disk. The TP technique provides a uniform stripe depth and an optimal amount of parity information.
-
Citations
16 Claims
-
1. A method for enabling recovery from three or fewer concurrent failures of storage devices in a storage array, comprising:
-
providing the away with a predetermined number of storage devices, including a plurality of first devices configured to store data and row parity, one diagonal parity device configured to store diagonal parity and one anti-diagonal parity device configured to store anti-diagonal parity, wherein the predetermined number of storage devices n is p+2 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−
3 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−
3 rows;computing and storing the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device; defining the anti-diagonal parity along anti-diagonal parity sets that span the first devices, wherein the anti-diagonal parity set wraps around within a group of n−
3 rows; andcomputing and storing the anti-diagonal parity for all the diagonal parity sets except one on the anti-diagonal parity device. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A system to enable recovery from three or fewer concurrent failures of storage devices in a storage array, comprising:
-
the storage array configured with a predetermined number of storage devices, including a plurality of first devices configured to store data and row parity, one diagonal parity device configured to store diagonal parity and one anti-diagonal parity device configured to store anti-diagonal parity, wherein the predetermined number of storage devices n is p+2 and wherein p is a prime number, wherein each device is divided into blocks and the blocks are organized into stripes that contain a same number of blocks in each device, wherein each stripe comprises n−
3 rows of blocks;the diagonal parity defined along diagonal parity sets that span the first devices, wherein the diagonal parity sets wrap around within a group of n−
3 rows;the anti-diagonal parity defined along anti-diagonal parity sets that span the first devices, wherein the anti-diagonal parity set wraps around within a group of n−
3 rows; anda storage operating system including a device storage layer configured to compute and store the diagonal parity for all of the diagonal parity sets except one on the diagonal parity device, and to compute and store the anti-diagonal parity for all the diagonal parity sets except one on the anti-diagonal parity device. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16)
-
Specification