Data redundancy methods and apparatus

A data storage apparatus comprising:

• a plurality of n storage devices;
• and
• a storage controller for controlling writing and reading data to and from the storage devices, the controller having stored program instructions or a logic circuit operable to
• select a control value m indicative of a degree of data redundancy, mn being an integer variable from 1 to n−1 inclusive,
• logically configure each storage device into one or more stripes, each stripe including H data portions for storing user data and Q data redundancy portions for storing redundancy data, H and Q being positive integers and H/Q<(n−m)/m,
• generate redundancy data from the user data using a data redundancy function obtained based on the value n and the control value m,
• store the user data in the data portions of the storage devices, store the redundancy data in the data redundancy portions of the storage devices, and
• when any subset of m or fewer storage devices is unavailable, recover user data stored in the unavailable storage devices from the user data and redundancy data stored in n−m remaining storage devices using a corresponding data recovery function.

A method for generating redundant data from user data, comprising:

• generating an n*H by n*Q encoding bit matrix, n, H and Q being positive integers and H/Q<(n−m)/m, m being an integer between 1 and n−1 inclusive;
• and
• generating redundant data by multiplying user data by the encoding bit matrix,
• wherein the step of generating the encoding bit matrix comprises:
• (a) generating an n*H by n*Q candidate matrix represented by an n by n array of H by Q submatrices;
• (b) selecting a set of m columns of the n by n array;
• (c) forming an m*H by (n−m)*Q composite submatrix of the candidate matrix from the H by Q submatrices located at the intersection of the set of m columns of the n by n array and (n−m) rows of the n by n array that correspond to the (n−m) columns not included in the set of m columns;
• (d) determining whether the composite submatrix is of maximal rank;
• (e) if the composite submatrix is not of maximal rank in step (d), repeating steps (a) to (d) for another candidate matrix;
• (f) if the composite submatrix is of maximal rank in step (d), repeat steps (b) to (d) for another set of m columns until all possible sets of m columns are selected;
• and
• (g) if all possible composite submatrices for a candidate matrix are of maximal rank, select the candidate matrix as the encoding bit matrix.

A method for providing user data to or retrieving user data from a plurality of n data channels, comprising:

• selecting a control value m indicative of a degree of data redundancy, m being an integer variable from 1 to n−1 inclusive;
• generating redundancy data from user data using a data redundancy function obtained based on the value n and the control value m;
• and
• providing the user data to H data portions and the redundancy data to Q data redundancy portions of each data channel, H and Q being positive integers and H/Q<(n−m)/m,
• wherein the data redundancy function is such that the user data provided to any subset of m or fewer unavailable data channels is recoverable from the user data and redundancy data provided to n−m remaining data channels using a set of data recovery functions corresponding to the data redundancy function.

In a system for providing data to and retrieving data from a plurality of n data channels, the data provided to each data channel comprising user data provided to H data portions and redundancy data provided to Q data redundancy portions, m being a value indicative of a degree of data redundancy and an integer from 1 to n−1 inclusive, the redundancy data having been generated from the user data using a data redundancy function capable of recovering from the loss of any m or fewer known channels, a method of detecting faulty data channels comprising:

• retrieving user data and redundancy data from each data channel;
• generating expected redundancy data from the retrieved user data using the data redundancy function;
• and
• estimating which data channels are faulty by comparing the expected redundancy data with the retrieved redundancy data.

A computer program product comprising a computer usable medium having a computer readable code embodied therein for controlling a data storage apparatus including a plurality of n storage devices, the computer program product comprising:

• first computer readable program code configured to cause the data storage apparatus to select a control value m indicative of a degree of data redundancy, m being an integer variable from 1 to n−1 inclusive;
• second computer readable program code configured to cause the data storage apparatus to logically configure each storage device into one or more stripes, each stripe including H data portions for storing user data and Q data redundancy portions for storing redundancy data, H and Q being positive integers and H/Q<(n−m)/m;
• and
• third computer readable program code configured to provide a data redundancy function and a corresponding set of data recovery functions based on the value n and the control value m, the data redundancy function being useful for generating redundancy data from user data, the data redundancy function being such that the user data stored in any subset of m or fewer unavailable storage devices is recoverable from the user data and redundancy data stored in n−m remaining storage devices using the data recovery functions.

A data storage apparatus comprising:

• a plurality of n storage devices, and
• a storage controller for controlling writing and reading data to and from the storage devices, the controller having stored program instructions or a logic circuit operable to
• logically configure each storage device into one or more stripes, each stripe including H data portions for storing user data and Q data redundancy portions for storing redundancy data, H and Q being positive integers and H/Q<(n−m)/m, wherein m is a control value indicative of a degree of data redundancy and an integer between 1 and n−1 inclusive,
• generate redundancy data from the user data using a data redundancy function obtained based on the value n and the control value m,
• store the user data in the data portions of the storage devices,
• store the redundancy data in the data redundancy portions of the storage devices, and
• when any subset of m or fewer storage devices is unavailable, recover user data stored in the unavailable storage devices from the user data and redundancy data stored in n−m remaining storage devices using a corresponding data recovery function.