Apparatus and method for providing data redundancy and reconstruction for redundant arrays of disk drives

In a processing board, a circuit for generating a next column vector of a T-matrix for use in providing redundancy data for a data storage device, said circuit comprising:

• a first circuit element for receiving a preceding column vector;
• a second circuit element for receiving a T-polynomial constant;
• a third circuit element for performing an exclusive-or of said preceding column vector and said T-polynomial constant;
• a fourth circuit element for shifting said preceding column vector;
• and
• a fifth circuit element for selecting said next column vector from either said third or fourth circuit element.

A computer-implemented method for constructing data in an array of disks, said method comprising the steps of:

• (a) partitioning said array into at least one group of m disks;
• (b) selecting at least two of said disks as redundancy disks and m-2 of said disks as data disks, said redundancy disks storing a plurality of second-level redundancy codewords, each said redundancy codeword including a first codeword and a second codeword;
• (c) assigning a first one of said redundancy disks to store said first codewords and a second one of said redundancy disks to store said second codewords, each of said first codewords representing data stored at a specified location in each of said data disks and said second redundancy disk, each said first set codewords used to restore said represented data when specified ones of said disks fail, each of said second codewords representing data stored at a specified location in each of said data disks, each of said second codewords used to restore said represented data when two of said data disks fails;
• (d) identifying as a first symbol, one of said first codewords and as a second symbol, one of said second codewords;
• (e) forming a subset of said disks, said subset including each said data disk;
• (f) generating said second symbol, said generation comprising the steps of:
• (i) for each disk of said subset,
• (1) formulating an n-bit column vector t.sup.n representing a first column of a N.times.N T-matrix associated with a specified one of said disks of said subset, said T-matrix corresponding to a predefined polynomial of degree N,
• (2) expanding said column vector into an associated T-matrix,
• (3) determining a partial sum associated with said specified disk, said partial sum determined as a modula-2 product of said associated T-matrix and a data symbol read from said specified disk;
• (ii) computing said second symbol as a modula-2 sum of each said partial sums;
• and
• (iii) storing said second symbol in said second redundancy disk;
• (g) generating a first symbol;
• and
• (h) storing said first symbol in said first redundancy disc drive.

A method for constructing redundancy data in a I/O system having an array of data storage devices, said method comprising the steps of:

• (a) selecting at least one of said data storage devices for storage of said redundancy data, said redundancy data used to restore data residing in more than one of said data storage devices;
• (b) providing at least one column vector representing a first column of a N.times.N T-matrix associated with a polynomial of degree N, each said column vector associated with a specified one of said data storage devices;
• (c) expanding each said column vector into an associated T-matrix in accordance with the following mathematical relation:
• ##EQU14## (d) utilizing said generated T-matrices to construct said redundancy data;
• and
• (e) storing said redundancy data in said redundancy data storage device.

An apparatus for generating redundancy data for use in an I/O system including an army of storage mediums, comprising:

• at least one group of m storage mediums, each said group including at least one redundancy storage medium and at least one data storage medium, each said redundancy storage medium for storing said redundancy data, each said data storage medium for storing information data;
• a first processing unit including a first memory for storing a program including instructions to generate an n-bit column vector t.sup.n representing a first column of a N.times.N T-matrix associated with a specified one of said data storage mediums;
• a second processing unit, coupled to said first processing unit and to said storage mediums, for generating said redundancy data and transmitting said redundancy data to a respective redundancy storage medium, said second processing unit including:
• a matrix generating circuit for receiving said column vector and generating a corresponding N.times.N matrix, T.sup.N, representing a predefined polynomial expression;
• a multiplier, coupled to said matrix generating circuit, for performing a modula-2 product of said matrix with a datum associated with one of said data storage mediums, said multiplier generating a first result;
• and
• a modula-2 summation circuit, coupled to said multiplier and a second memory, for summing said first result with a specified partial sum stored in said second memory, said summation circuit generating a second result that is stored in said second memory;
• said program further including instructions that
• for each said data storage medium, transmit a column vector t.sup.n associated with a specified data storage medium to said second processing unit, transmit a datum associated with said specified data storage medium to said second processing unit, transmit a plurality of control signals to said second processing unit, a first subset of said control signals for use in generating a partial sum associated with said data storage medium, a second subset of said control signals for transmitting said generated redundancy data to said specified data storage medium.