US5671349A — Apparatus and method for providing data redundanc…

Claim 1

Independent Claim 118 words

In a data storage system having a plurality of data storage devices, an apparatus for constructing and reconstructing redundancy data by utilizing a set of N×N T-matrices formed from a polynomial of degree N, said apparatus comprising: said plurality of data storage devices arranged in a parallel array; a host interface means for receiving read and write requests from a host for data stored in said plurality of data storage devices; a means for constructing a reconstructing said redundancy data, said means comprising a means for constructing each of said N×N T-matrices, each of a select one of said N×N T-matrices constructed from a given column vector of said selected N×N T-matrix according to the following equation: ##EQU10##

Claim 2

Dependent Claim 118 words

In a data storage system having a plurality of data storage devices, an apparatus for constructing and reconstructing redundancy data by utilizing a set of N×N T-matrices formed from a polynomial of degree N, said apparatus comprising: said plurality of data storage devices arranged in a parallel array; a host interface means for receiving read and write requests from a host for data stored in said plurality of data storage devices; a means for constructing a reconstructing said redundancy data, said means comprising a means for constructing each of said N×N T-matrices, each of a select one of said N×N T-matrices constructed from a given column vector of said selected N×N T-matrix according to the following equation: ##EQU10##

Claim 3

Dependent Claim 12 words

The apparatus as recited in claim 1 wherein said polynomial is primitive.

Claim 4

Dependent Claim 18 words

The apparatus as recited in claim 2 wherein said given column is the first column of said T-matrices.

Claim 5

Dependent Claim 16 words

The apparatus as recited in claim 3 wherein the entries of said T-matrices are binary digits.

Claim 6

Dependent Claim 94 words

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.

Claim 7

Dependent Claim 94 words

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.

Claim 8

Dependent Claim 14 words

The circuit of claim 5, said T-polynomial constant is set to A9 h .

Claim 9

Dependent Claim 13 words

The circuit of claim 5, said fourth circuit element performing a left-shift operation.

Claim 10

Dependent Claim 346 words

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 n representing a first column of a N×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.

Claim 11

Dependent Claim 346 words

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 n representing a first column of a N×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.

Claim 12

Dependent Claim 60 words

The method of claim 8, said step (g) generating said first symbol in accordance with the following equation: ##EQU11## where m is the number of disc drives in the array, i o is the redundancy disc associated with the first symbol, s j is the data symbol corresponding to the j-th data disk, and the summation is a modula-2 sum.

Claim 13

Dependent Claim 69 words

The method of claim 8, said step (f)(i)(1) formulating said column vector t n in accordance with the following equation: t.sup.n =A(b-a mod 255) where b=L(t.sup.i.sbsp.l⊕ t.sup.j), t.sup.i.sbsp.l =A(i.sub.l), t.sup.j =A(j), a=L(t.sup.a), t.sup.a =t.sup.i.sbsp.o⊕ t.sup.i.sbsp.l, t.sup.i.sbsp.o =A(i.sub.0), t.sup.i.sbsp.l =A(i.sub.l), A represents the antilog operation, L represents the log operation, i l represents the second redundancy disk, i o represents the first redundancy disk, and j represents a specified disk.

Claim 14

Dependent Claim 21 words

The method of claim 10, wherein said antilog operation A is performed as a table look-up operation in an antilog table.

Claim 15

Dependent Claim 21 words

The method of claim 10, wherein said log operation L is performed as a table look-up operation in a log table.

Claim 16

Dependent Claim 17 words

The method of claim 8, said step (f)(i)(2) is expanded in accordance with the following equation: ##EQU12##

Claim 17

Dependent Claim 104 words

The method of claim 8 further comprising the step of: when at least two of said data disks fail simultaneously, identifying as said first symbol, datum to be restored in one of said failed disks and as said second symbol, datum to be restored to a second one of said failed disks, reforming said subset of said disks to include each said non-failed disk in said group, repeating steps (f)(i) through (f)(ii) to reconstruct said second symbol, storing said reconstructed second symbol in a corresponding disk, repeating step (g) to reconstruct said first symbol, and storing said reconstructed first symbol in a respective disk.

Claim 18

Dependent Claim 55 words

The method of claim 8, when a read-modify-write operation is performed on a datum stored in one of said data disks, repeating said steps (f)(i)(1)-(f)(i)(2) to formulate a corresponding T-matrix, T n , for a data disk associated with said updated datum; updating an associated second codeword in accordance with the following mathematical relation: ##EQU13##

Claim 19

Dependent Claim 32 words

The method of claim 15, further comprising the step of updating an associated first set codeword when a read-modify-write operation is performed on a datum stored in one of said data disks.

Claim 20

Independent Claim 132 words

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×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.

Claim 21

Independent Claim 132 words

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×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.

Claim 22

Independent Claim 332 words

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 n representing a first column of a N×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×N matrix, T 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 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.

Claim 23

Independent Claim 332 words

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 n representing a first column of a N×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×N matrix, T 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 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.

Claim 24

Dependent Claim 67 words

The apparatus of claim 18, said second processing unit further comprising a storage device coupled to said matrix generating circuit, said storage device used to store a T-polynomial constant value, A9 h , for use by said matrix generating circuit for generating said matrix; and said matrix generating circuit, further coupled to said storage device, and generating said matrix in accordance with the following mathematical relation: ##EQU15##

Claim 25

Dependent Claim 66 words

The apparatus of claim 18, said redundancy data including a first codeword and a second codeword; said second processing unit generating a first codeword for storage in a first redundancy storage medium; and a third processing unit, identical to said second processing unit, coupled to said first processing unit and said storage mediums, for generating said second codeword for storage in a second redundancy storage medium.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2000-09-22	2001-03-24	2001-09-23	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2004-09-22	2005-03-24	2005-09-23	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2008-09-22	2009-03-24	2009-09-23	$7700.00	Window Closed / Lapsed

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

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag