System and method for symmetric triple parity for failing storage devices
First Claim
1. A method comprising:
- providing an array with a predetermined number of storage devices p configured to store data and three parity values, wherein p is a prime number;
dividing each of the predetermined storage device into blocks;
organizing the blocks into stripes, the stripes having a same number of blocks in each of the predetermined storage device;
defining a diagonal parity along a plurality of diagonal parity sets;
defining an anti-diagonal parity along a plurality of anti-diagonal parity sets;
assigning a predetermined value to the diagonal parity and anti-diagonal parity; and
computing parity for the predetermined storage devices using values written to a plurality of the predetermined storage devices and the predetermined values assigned to the diagonal and anti-diagonal parity sets, the computed parity enabling recovery from three concurrent failures of storage devices in a storage array.
1 Assignment
0 Petitions
Accused Products
Abstract
A symmetric triple parity (TP) technique in an array comprising a number p of storage devices, such as disks, with p being a prime number is provided. The p disks are organized as one row parity disk, two symmetric parity disks and p-3 data disks. Phantom diagonal and anti-diagonal parity disks assumed to be present are further assumed to contain a predetermined value, thereby enabling parity encoding/decoding utilizing the phantom (anti-) diagonal disks. Row parity and symmetric parity values are included within the computation of the diagonal and anti-diagonal parities; accordingly, the two symmetric parity and the row parity values may be computed using the same technique as used for a triple parity erasure, i.e., in a symmetric fashion.
-
Citations
20 Claims
-
1. A method comprising:
-
providing an array with a predetermined number of storage devices p configured to store data and three parity values, wherein p is a prime number; dividing each of the predetermined storage device into blocks; organizing the blocks into stripes, the stripes having a same number of blocks in each of the predetermined storage device; defining a diagonal parity along a plurality of diagonal parity sets; defining an anti-diagonal parity along a plurality of anti-diagonal parity sets; assigning a predetermined value to the diagonal parity and anti-diagonal parity; and computing parity for the predetermined storage devices using values written to a plurality of the predetermined storage devices and the predetermined values assigned to the diagonal and anti-diagonal parity sets, the computed parity enabling recovery from three concurrent failures of storage devices in a storage array. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A system configured to enable recovery from three or fewer concurrent failures of storage devices, the system comprising:
-
an array having a predetermined number of storage devices p configured to store data and three parity values, wherein p is a prime number; a storage operating system including a device storage layer configured to implement a symmetric triple parity (TP) technique configured to, detect that three storage devices have concurrently failed; compute a diagonal parity along diagonal parity sets, compute an anti-diagonal parity along anti-diagonal parity sets, the diagonal and anti-diagonal parity are assigned a predetermined value, compute parity for the predetermined storage devices using values written to a plurality of the predetermined storage devices and the predetermined values assigned to the diagonal and anti-diagonal parity sets, the computed parity enabling recovery from three concurrent failures of storage devices in a storage array; 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 triple parity technique. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18, 19)
-
-
20. A computer readable medium containing executable program instructions executed by a processor, comprising:
-
program instructions that divide each of a predetermined storage devices p, configured to store data and three parity values, into blocks, wherein p is a prime number; program instructions that organize the blocks into stripes, the stripes having a same number of blocks in each of the predetermined storage device; program instructions that define a diagonal parity along a plurality of diagonal parity sets; program instructions that define an anti-diagonal parity along a plurality of anti-diagonal parity sets; program instructions that assign a predetermined value to the diagonal parity and anti-diagonal parity; and program instructions that compute parity for the predetermined storage is devices using values written to a plurality of the predetermined storage devices and the predetermined values assigned to the diagonal and anti-diagonal parity sets, the computed parity enabling recovery from three concurrent failures of storage devices in a storage array.
-
Specification