Technique for correcting multiple storage device failures in a storage array

A method for encoding data for correction of double failures in a storage array, the method comprising the steps of:

• organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a local parity storage device, the storage array further including a global parity storage device for holding diagonal parity;
• assigning diagonal parity sets to each sub-array identically as if the sub-array were the only one present using a double failure protection encoding method;
• and
• computing the diagonal parity by logically combining together a plurality of equivalent diagonal parity sets each from a differing one of the sub-arrays.

A method for encoding data for correction of double failures in a storage array, the method comprising the steps of:

• organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a local parity storage device, the storage array further including a global parity storage device for holding diagonal parity;
• assigning diagonal parity sets to each sub-array identically as if the sub-array were the only one present using a double failure protection encoding method;
• computing the diagonal parity by logically combining together equivalent diagonal parity sets in each of the sub-arrays and computing diagonal parity blocks along the diagonal parity sets of each sub-array, and logically combining the computed diagonal parity blocks of corresponding diagonal parity sets of the sub-arrays for storage as the diagonal parity on the global parity storage device;
• and
• correcting storage device failure within the array using the local parity storage device associated with each sub-array and the global parity storage device associated with the storage array.

Apparatus for correcting double failures in a storage array, the apparatus comprising:

• means for organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a local parity storage device, the storage array further including a global parity storage device for holding diagonal parity;
• means for assigning diagonal parity sets to each sub-array identically as if the sub-array were the only one present using a double failure protection encoding method;
• means for computing the diagonal parity using parity encoding operations that logically combine together a plurality of equivalent diagonal parity sets each from a differing one of the sub-arrays;
• and
• means for correcting storage device failure within the array using parity decoding operations on the local parity storage device associated with each sub-array and the global parity storage device associated with the storage array.

A computer readable medium containing executable program instructions for correcting double failures in a storage array, the executable program instructions comprising program instructions for:

• organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a local parity storage device, the storage array further including a global parity storage device for holding diagonal parity;
• assigning diagonal parity sets to each sub-array identically as if the sub-array were the only one present using a double failure protection encoding method;
• computing the diagonal parity by logically combining together a plurality of equivalent diagonal parity sets each from a differing one of the sub-arrays;
• and
• correcting storage device failure within the array using the local parity storage device associated with each sub-array and the global parity storage device associated with the storage array.

A computer readable medium containing executable program instructions for correcting double failures in a storage array, the executable program instructions comprising program instructions for:

• organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a local parity storage device, the storage array further including a global parity storage device for holding diagonal parity;
• assigning diagonal parity sets to each sub-array identically as if the sub-array were the only one present using a double failure protection encoding method;
• computing the diagonal parity by logically combining together equivalent diagonal parity sets in each of the sub-arrays, computing diagonal parity blocks along the diagonal parity sets of each sub-array, and logically combining the computed diagonal parity blocks of corresponding diagonal parity sets of the sub-arrays for storage as the diagonal parity on the global parity storage device;
• and
• correcting storage device failure within the array using the local parity storage device associated with each sub-array and the global parity storage device associated with the storage array.

A method for correcting double failures within data adapted for transmission over a communication medium, the method comprising the steps of:

• dividing the data into packets for transmission over the communications medium;
• organizing the packets into n sub-groups of p packets, wherein p is a smallest prime number that is at least as large as a number of packets in any sub-group of packets and wherein each sub-group of packets includes data packets and a local parity packet configured to store values encoded with a single error correction method used to correct a failure of a single packet in the sub-group;
• assigning diagonal parity sets to each sub-group identically as if it were the only one present using a double failure protection encoding method;
• and
• providing a global parity packet with the group of packets, the global parity packet holding diagonal parity computed by logically combining equivalent diagonal parity sets in each of the sub-groups, wherein the global parity packet is used in connection with the local parity packet of each sub-group to correct a double failure within the sub-array.

A method for encoding data for correction of double failures in a storage array, comprising:

• organizing the storage array as a plurality of sub-arrays, each sub-array including a set of data storage devices and a plurality of local parity storage blocks, each of the plurality of local storage blocks storing parity information for a corresponding sub-array;
• assigning diagonal parity sets to each sub-array as if the sub-array were the only one present using a double failure protection encoding method;
• including a plurality of global diagonal parity storage blocks, the global diagonal parity storage blocks holding global diagonal parity;
• and
• computing the global diagonal parity by logically combining together a plurality of equivalent diagonal parity sets such that each diagonal parity set is logically combined with at least one other equivalent diagonal parity set from a differing one the sub-arrays.

An apparatus for encoding data for correction of double failures in a storage array, comprising:

• means for organizing the storage array as a plurality of sub-arrays, each sub-array including a set of data storage devices and a plurality of local parity storage blocks, each of the plurality of local storage blocks storing parity information for a corresponding sub-array;
• means for assigning diagonal parity sets to each sub-array as if the sub-array were the only one present using a double failure protection encoding method;
• means for including a plurality of global diagonal parity storage blocks, the global diagonal parity storage blocks holding global diagonal parity;
• and
• means for computing the global diagonal parity by logically combining together a plurality of equivalent diagonal parity sets such that each diagonal parity set is logically combined with at least one other equivalent diagonal parity set from a differing one of the sub-arrays.

A system for encoding data for correction of double failures, comprising:

• a storage array organized as a plurality of sub-arrays, each sub-array including a set of data storage devices and a plurality of local parity storage blocks, each of the local parity storage blocks storing parity information for a corresponding sub-array;
• a storage operating system within a storage system to assign diagonal parity sets to each sub-array as if the sub-array were the only one present using a double failure protection encoding method;
• a plurality of global diagonal parity storage blocks within the storage array, the global diagonal parity storage blocks holding global diagonal parity;
• and
• the storage operating system computing the global diagonal parity by logically combining together equivalent diagonal parity sets in each of the sub-arrays such that each diagonal parity set is logically combined with at least one other equivalent diagonal parity set from a differing one of the sub-arrays.

A computer readable media, comprising:

• said computer readable media having instructions written thereon for execution on a processor for the practice of the method of encoding data for correction of double failures in a storage array, comprising:
• organizing the storage array as a plurality of sub-arrays, each sub-array including a set of data storage devices and a plurality of local parity storage blocks, each of the plurality of local storage blocks storing parity information for a corresponding sub-array;
• assigning diagonal parity sets to each sub-array as if the sub-array were the only one present using a double failure protection encoding method;
• including a plurality of global diagonal parity storage blocks, the global diagonal parity storage blocks holding global diagonal parity;
• and
• computing the global diagonal parity by logically combining together equivalent diagonal parity sets in each of the sub-arrays such that each diagonal parity set is logically combined with at least one other equivalent diagonal parity set from a differing one of the sub-arrays.

A method for correcting double failures within data adapted for transmission over a communication medium, the method comprising the steps of:

• dividing the data into packets for transmission over the communications medium;
• organizing the packets into subgroups, wherein each subgroup of packets includes data packets and a local parity packet configured to store values encoded with a single error correction method used to correct a failure of a single packet within the subgroup;
• assigning diagonal parity sets to each subgroup as if it were the only subgroup present using a double failure protection encoding method;
• and
• providing a global parity packet within the group of packets, the global parity packet holding diagonal parity computed by logically combining together a plurality of equivalent diagonal parity sets in each of the subgroups such that each diagonal parity set is logically combined with at least one other equivalent diagonal parity set from a differing one of the subgroups, wherein the global parity packet is used in connection with the local parity packet of each subgroup to correct a double failure within the subgroup.

An apparatus for correcting double failures within data adapted from transmission over a communications medium, comprising:

• means for dividing the data into packets for transmission over the communications medium;
• means for organizing the packets into subgroups, wherein each subgroup of packets includes data packets and a local parity packet configured to store values encoded with a single error correction method used to correct a failure of a single packet within the subgroup;
• means for assigning diagonal parity sets to each subgroup as if it were the only subgroup present using a double failure protection encoding method;
• and
• means for providing a global parity packet within the group of packets, the global parity packet holding diagonal parity computed by logically combining together a plurality of equivalent diagonal parity sets in each of the subgroups such that each diagonal parity set is logically combined with at least one other equivalent diagonal parity set from a differing one of the subgroups, wherein the global parity packet is used in connection with the local parity packet of each subgroup to correct a double failure within the subgroup.

A method for correcting multiple storage element failures in a storage array, the method comprising the steps of:

• dividing the storage array into a first sub-array and a second sub-array, the first sub-array and the second sub-array each including a plurality of storage devices;
• calculating row parity for the first sub-array and storing the row parity for the first-sub array on one or more storage devices of the first sub-array;
• calculating row parity for the second sub-array and storing the row parity for the second sub-array on one or more storage devices of the second sub-array;
• selecting a plurality of diagonal parity sets on the first sub-array;
• selecting a plurality of diagonal parity sets on the second sub-array;
• pairing each diagonal parity set on the first sub-array with a corresponding diagonal parity set on the second sub-array, and calculating a global diagonal parity value for each pair of diagonal parity sets;
• and
• storing the global diagonal parity values on one or more storage devices of the storage array.