US 8,015,472 B1 · Triple parity technique for enabling efficient recovery from triple failures in a storage array

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.

Claims23

Dependent claims

A method for enabling recovery from three concurrent failures of storage devices in a storage array, comprising:

detecting that three storage devices in the storage array have concurrently failed, wherein the storage array is made up of a predetermined number n 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;
computing both diagonal parity and anti-diagonal parity that were not previously stored for the three failed storage devices;
computing an algebraic operation on missing blocks on each of a set of failed storage devices along a row, a diagonal and an anti-diagonal;
and
computing a set of 4-tuple sums on a middle storage device of the three failed storage devices to enable recovery of the three concurrently failed storage devices.

2 more elements

A non-transitory computer readable medium containing executable program instructions executed by a processor, comprising:

program instructions that detect that three storage devices in a storage array have concurrently failed, wherein the storage array is made up of a predetermined number n 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;
program instructions that compute a diagonal parity and anti-diagonal parity that was not previously stored for the three failed storage devices;
program instructions that compute an algebraic operation on missing blocks on each of a set of failed storage devices along a row, a diagonal and an anti-diagonal;
and
program instructions that compute a set of 4-tuple sums on a middle storage device of the three failed storage devices to enable recovery of the three concurrently failed storage devices.

2 more elements

A storage system to enable recovery from three concurrent failures of storage devices in a storage array, comprising:

a processor configured to execute a storage operating system on the storage system, the storage operating system when executed configured to
detect that three storage devices in the storage array have concurrently failed wherein the storage array is made up of a predetermined number n 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,
compute a diagonal parity and anti-diagonal parity that was not previously stored for the three failed storage devices,
compute an algebraic operation on missing blocks on each of a set of failed storage devices along a row, a diagonal and an anti-diagonal, and
compute a set of 4-tuple sums on a middle storage device of the three failed storage devices to enable recovery of the three concurrently failed storage devices.

2 more elements

Dependencies are inferred from the claim text.

Triple parity technique for enabling efficient recovery from triple failures in a storage array

Life of this patent

Triple parity technique for enabling efficient recovery from triple failures in a storage array

Life of this patent

Abstract

Claims23