US5271012A — Method and means for encoding and rebuilding data…

Claim 1

Independent Claim 110 words

A method for encoding and rebuilding of the data contents of up to two unavailable DASD's form an array of a M failure independent DASDs, comprising the steps of: (a) simple parity encoding over a (M-1)*M bit data array following a cylindrical, zig/zag traverse, said encoding being defined over pairs each formed from an array diagonal and a row intersecting the parity assigned to the diagonal; (b) striping and writing the parity coded data array to the M DASD array; and (c) responsive to up to two DASD failures, rebuilding the data on a patterned or random basis by accessing the data array and repeating steps (a) and (b) modified.

Claim 2

Independent Claim 110 words

A method for encoding and rebuilding of the data contents of up to two unavailable DASD's form an array of a M failure independent DASDs, comprising the steps of: (a) simple parity encoding over a (M-1)*M bit data array following a cylindrical, zig/zag traverse, said encoding being defined over pairs each formed from an array diagonal and a row intersecting the parity assigned to the diagonal; (b) striping and writing the parity coded data array to the M DASD array; and (c) responsive to up to two DASD failures, rebuilding the data on a patterned or random basis by accessing the data array and repeating steps (a) and (b) modified.

Claim 3

Independent Claim 155 words

A method for encoding and rebuilding of the data contents of up to two unavailable DASD's from an array of M failure independent DASDs, comprising the steps of: (a) recursively generating pairs of simple parity encodings over bits within an (M-1)*M data bit array inclusive of said parity encodings, said generation occurring in respective diagonal major order and row major order covering said array as a topological cylinder, one parity encoding over each diagonal and one parity encoding over the row intersecting the diagonal parity, M being a prime number; (b) striping and writing M bits at a time in row major order to counterpart ones of M failure independent DASDs in the array; and (c) responsive to the unavailability of up to two DASDs, rebuilding the data from no less than (M-2) available DASDs by accessing the data array inclusive of erasures and repeating steps (a) and (b) on a scheduled or opportunistic basis.

Claim 4

Independent Claim 155 words

A method for encoding and rebuilding of the data contents of up to two unavailable DASD's from an array of M failure independent DASDs, comprising the steps of: (a) recursively generating pairs of simple parity encodings over bits within an (M-1)*M data bit array inclusive of said parity encodings, said generation occurring in respective diagonal major order and row major order covering said array as a topological cylinder, one parity encoding over each diagonal and one parity encoding over the row intersecting the diagonal parity, M being a prime number; (b) striping and writing M bits at a time in row major order to counterpart ones of M failure independent DASDs in the array; and (c) responsive to the unavailability of up to two DASDs, rebuilding the data from no less than (M-2) available DASDs by accessing the data array inclusive of erasures and repeating steps (a) and (b) on a scheduled or opportunistic basis.

Claim 5

Dependent Claim 44 words

The method according to claim 2, wherein said DASD array has spare capacity assigned thereamong in a predetermined manner, and further wherein the rebuilding step includes striping and writing the rebuilt data using the spare DASD array capacity in place of the unavailable DASDs.

Claim 6

Dependent Claim 20 words

The method according to claim 3, wherein the spare DASD capacity is in the form of DASDs reserved as spares.

Claim 7

Independent Claim 162 words

A method for encoding and rebuilding the data contents of up to two unavailable DASDs of an M DASD array, comprising the steps of: (a) block encoding and writing to counterpart locations on the M DASD array original data elements of an (M-1)*M data array, said encoding being executed in an alternating diagonal and row manner covering said data array as a topological cylinder, each diagonal and row encoding action resulting in a first and second simple parity (XOR), said first and second parity being stored on respective first and second failure independent ones of the M DASD array; and (b) responsive to the unavailability of no more than two DASDs, rebuilding the data from said unavailable DASD by simple parity coding of the referenced array elements from M-1 or M-2 other available DASDs on a scheduled or opportunistic basis on spare DASD array capacity by the dual of the encoding and writing process covering the data array as a topological cylinder.

Claim 8

Independent Claim 162 words

A method for encoding and rebuilding the data contents of up to two unavailable DASDs of an M DASD array, comprising the steps of: (a) block encoding and writing to counterpart locations on the M DASD array original data elements of an (M-1)*M data array, said encoding being executed in an alternating diagonal and row manner covering said data array as a topological cylinder, each diagonal and row encoding action resulting in a first and second simple parity (XOR), said first and second parity being stored on respective first and second failure independent ones of the M DASD array; and (b) responsive to the unavailability of no more than two DASDs, rebuilding the data from said unavailable DASD by simple parity coding of the referenced array elements from M-1 or M-2 other available DASDs on a scheduled or opportunistic basis on spare DASD array capacity by the dual of the encoding and writing process covering the data array as a topological cylinder.

Claim 9

Dependent Claim 51 words

The method according to claim 5, wherein if M is not a prime number than causing steps (a) and (b) being operative to behave as if the data array were expanded to include additional columns of uniform binary value to yield an effective array (M'-1)*M' where M' constitutes a prime number.

Claim 10

Dependent Claim 208 words

A computer implemented method for coding and rebuilding the contents of up to two unavailable DASDs in an M DASD array, said DASD array being attached to a computing system, comprising the steps of: (a) block encoding and writing onto said M DASD array at least one (M-1)*M data array of simple parity encoded data, said encoding being executed in alternating diagonal major wrap-around order and row major order, M being a prime number, each parity encoding along a data array diagonal intercepting M-2 data elements and the results being placed in a first position on a first one of the M DASD, each parity encoding along a data array row intersecting the first parity position and intercepting M-1 data elements and the results being placed in a second parity position in that row on a second one of the M DASD; and (b) responsive to accesses to any unavailable DASD, rebuilding the data from said unavailable DASD by simple parity coding of the referenced array elements from M-1 or M-2 other available DASDs on a scheduled or opportunistic basis on spare DASD array capacity by the dual of the encoding and writing process covering the data array in alternating diagonal major wrap-around order and row major order.

Claim 11

Dependent Claim 208 words

A computer implemented method for coding and rebuilding the contents of up to two unavailable DASDs in an M DASD array, said DASD array being attached to a computing system, comprising the steps of: (a) block encoding and writing onto said M DASD array at least one (M-1)*M data array of simple parity encoded data, said encoding being executed in alternating diagonal major wrap-around order and row major order, M being a prime number, each parity encoding along a data array diagonal intercepting M-2 data elements and the results being placed in a first position on a first one of the M DASD, each parity encoding along a data array row intersecting the first parity position and intercepting M-1 data elements and the results being placed in a second parity position in that row on a second one of the M DASD; and (b) responsive to accesses to any unavailable DASD, rebuilding the data from said unavailable DASD by simple parity coding of the referenced array elements from M-1 or M-2 other available DASDs on a scheduled or opportunistic basis on spare DASD array capacity by the dual of the encoding and writing process covering the data array in alternating diagonal major wrap-around order and row major order.

Claim 12

Dependent Claim 101 words

The method according to claim 7, wherein said computer executes at least one small write access to the (M-1)*M data array stored on the array of M DASDs, a first and a second DASD storing simple parity while M-2 other DASDs storing data, and wherein said method further comprises the steps of reading the old data from at least one data DASD and old parity from the first and second DASDs; determining the new parity (x,y)' to be written onto the respective first and second DASDs by XORing old data, new data, old parity, old adjacent parity and new adjacent parity.

Claim 13

Dependent Claim 142 words

In a system having a CPU, an array of at least M DASDs and spared thereof, and means intercoupling the CPU and the array for synchronously accessing selectable ones of the DASDs, said means including means for read and write accesses of M bits at a time striped over M DASDs, wherein said intercoupling means further comprise: (a) means for formatting an (M-1)*M data bit array inclusive of simple parity encodings onto M DASDs of the array in a recursively generated pattern of diagonal major and intersecting row major order, said order traversing a topological cylinder, M being a prime number; and (b) means responsive to the unavailability of up to two DASDs for rebuilding the data from no less than (M-2) available DASDs by accessing the data array and repeating steps (a) and (b) modified on a scheduled or opportunistic basis.

Claim 14

Dependent Claim 142 words

In a system having a CPU, an array of at least M DASDs and spared thereof, and means intercoupling the CPU and the array for synchronously accessing selectable ones of the DASDs, said means including means for read and write accesses of M bits at a time striped over M DASDs, wherein said intercoupling means further comprise: (a) means for formatting an (M-1)*M data bit array inclusive of simple parity encodings onto M DASDs of the array in a recursively generated pattern of diagonal major and intersecting row major order, said order traversing a topological cylinder, M being a prime number; and (b) means responsive to the unavailability of up to two DASDs for rebuilding the data from no less than (M-2) available DASDs by accessing the data array and repeating steps (a) and (b) modified on a scheduled or opportunistic basis.

Claim 15

Dependent Claim 175 words

The system according to claim 9, wherein said array includes unassigned spare DASDs, and further, wherein said intercoupling means includes means for substituting spare DASDs for the failed ones and for writing back rebuild data across M DASDs including the substituted DASDs. to counterpart locations on the M DASD array original data elements of an (M-1)*M data array, said encoding being executed in an alternating diagonal and row manner covering said data array as a topological cylinder, each diagonal and row encoding action resulting in a first and second simple parity (XOR), said first and second parity being stored on respective first and second failure independent ones of the M DASD array; and (b) responsive to the unavailability of no more than two DASDs, rebuilding the data from said unavailable DASD by simple parity coding of the referenced array elements from M-1 or M-2 other available DASDs on a scheduled or opportunistic basis on spare DASD array capacity by the dual of the encoding and writing process covering the data array as a topological cylinder.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1996-12-13	1997-06-14	1997-12-14	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2000-12-13	2001-06-14	2001-12-14	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2004-12-13	2005-06-14	2005-12-14	$7700.00	Window Closed / Lapsed

Method and means for encoding and rebuilding data contents of up to two unavailable DASDs in an array of DASDs

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag