System and method for symmetric triple parity for failing storage devices

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, including a plurality of first devices configured to store data, and symmetric parity, the predetermined number of storage devices is p and 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;
• computes a diagonal parity along diagonal parity sets that span the first devices,
• computes an anti-diagonal parity along anti-diagonal parity sets that span the first devices, the diagonal and anti-diagonal parity are assigned a predetermined value,
• computes a total of p 4-tuple sums along an intermediate storage device of the failed storage devices;
• and
• generates the computed 4-tuple sums using a number of crosses, the computed sums 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 TP parity technique.

A computer readable medium containing executable program instructions executed by a processor, comprising

• program instructions that provide an array with a predetermined number of storage devices including a plurality of first devices configured to store data, and symmetric parity, the predetermined number of storage devices is p and p is a prime number;
• program instructions that divide each device into blocks;
• program instructions that organize the blocks into stripes that contain a same number of blocks in each device, each stripe having p-1 rows of blocks;
• program instructions that define a diagonal parity along diagonal parity sets that span the first devices, the diagonal parity sets wrapping around within a group of p-1 rows allowing all blocks belonging to diagonal parity sets of a stripe to be stored in the stripe;
• program instructions that define an anti-diagonal parity along anti-diagonal parity sets that span the first devices, the anti-diagonal parity set wrapping around within a group of p-1 rows allowing all blocks belonging to the anti-diagonal parity sets of a stripe to be stored in the stripe;
• program instructions that assign a predetermined value to the diagonal parity and anti-diagonal parity;
• and
• program instructions that compute parity for a plurality of devices configured to store row parity and symmetric parity using values written to a plurality of devices configured to store data and the predetermined value assigned to the diagonal parity and anti-diagonal parity, the computed parity enabling recovery from three concurrent failures of storage devices in a storage array.

A method comprising:

• detecting that three storage devices have concurrently failed
• 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 a diagonal parity value and an anti-diagonal parity value are set to a predetermined value;
• and
• computing a set of 4-tuple sums on a middle failed storage device, the computed parity-sum enabling recovery from three concurrent failures of storage devices in a storage array.

A method for recovering from three concurrent disk failures in a computer data storage system, comprising:

• computing row parity for a set of data disks;
• computing a first diagonal parity for the set of data disks and disks on which the row parity was stored;
• computing a second diagonal parity for the set of data disks and disks on which the row parity was stored;
• detecting a failure on each of three different disks of the set of disks, referred to hereinafter as the three failed disks;
• choosing an intermediate disk of the three failed disks;
• performing sums using the row parity and the first diagonal parity and the second diagonal parity to generate an equation having one unknown, the computed sums enabling recovery from three concurrent failures of storage devices in a storage array;
• and
• solving the equation to reconstruct a data block on a disk of the three failed disks.

A computer readable medium containing executable program instructions for recovering from three concurrent disk failures in a computer data storage system, the executable program instructions comprising program instructions for:

• computing row parity for a set of data disks;
• computing a first diagonal parity for the set of data disks and disks on which the row parity was stored;
• computing a second diagonal parity for the set of data disks and disks on which the row parity was stored;
• detecting a failure on each of three different disks of the set of disks, referred to hereinafter as the three failed disks;
• choosing an intermediate disk of the three failed disks;
• performing sums using the row parity and the first diagonal parity and the second diagonal parity to generate an equation having one unknown, the computed sums enabling recovery from three concurrent failures of storage devices in a storage array;
• and
• solving the equation to reconstruct a data block on a disk of the three failed disks.

A system configured to enable recovery from three concurrent disk failures in a computer data storage system, the system comprising:

• an array having a predetermined number of storage devices, including a plurality of first devices configured to store data, and symmetric parity, the predetermined number of storage devices is p and p is a prime number;
• a storage operating system including a device storage layer configured to implement a symmetric triple parity technique configured to,
• compute row parity for a set of data disks;
• compute a first diagonal parity for the set of data disks and disks on which the row parity was stored;
• compute a second diagonal parity for the set of data disks and disks on which the row parity was stored;
• detect a failure on each of three different disks of the set of disks, referred to hereinafter as the three failed disks;
• choose an intermediate disk of the three failed disks;
• perform sums using the row parity and the first diagonal parity and the second diagonal parity to generate an equation having one unknown, the computed sums enabling recovery from three concurrent failures of storage devices in a storage array;
• and
• solve the equation to reconstruct a data block on a disk of the three failed disks.