EP0499365A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Data processing system and method for encoding and rebuilding data contents of unavailable DASDS
Assignee: International Business Machines Corp
•
Filing: 1992-01-23
•
Granted: —
•
Expires: 2012-01-23
Abstract
Abstract A method and means for encoding data written onto an array of M synchronous DASDs and for rebuilding onto spare DASD array capacity when up to two DASDs fail. Data is mapped into the DASD array using an (M-1)*M data array as the storage model, where M is a prime number. Pairs of simple parities are recursively encoded over data in respective diagonal major and intersecting row major order array directions, the encoding traverse covering a topologically cylindrical path. Rebuilding data upon unavailability of no more than two DASDs merely requires accessing the data array and repeating the encoding step where the diagonals are oppositely sloped and writing the rebuilt array back onto M DASDs inclusive of the spare capacity.
Inventors
- 👤 Miguel Mario Blaum
- 👤 Hsieh Tung Hao
- 👤 Richard Lewis Mattson
- 👤 Jaishankar Moothedath Menon
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-29 14:36
CPC Classifications
G; G11; G11C; G11C29/00; G11C29/70; G11C29/88; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; G06F11/1092; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1833; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/11; G06F11/1008; G06F11/1012
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
90 words
A method of rebuilding the data contents of unavailable DASDs from an array of a plurality of failure independent DASDs, comprising the steps of: (a) recursively simple parity encoding over a data array following a zig/zag and wrap around traverse; (b) striping and writing the parity coded data array to a DASD array; and (c) responsive to DASD failure, rebuilding the data on a patterned or random basis by accessing the data array and repeating steps (a) and (b), modifying the traverse slightly to take account of the unavailable DASDs.
Claim 2
Independent Claim
118 words
A method for encoding and rebuilding of the data contents of up to two unavailable DASDs from an array of M failure independent DASDs, comprising the steps of: (a) recursively simple parity encoding over a (M-1)*M bit data array following a toroidal (zig/zag and wrap around) traverse, the 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 to take an inverse traverse.
Claim 3
Independent Claim
154 words
A method for encoding and rebuilding of the data contents of up to two unavailable DASDs 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 the parity encodings, the generation occurring in respective diagonal major and row major order covering the 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 diagonal 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
Dependent Claim
49 words
A method according to claim 3, wherein the data array can be generated along a two dimensional distribution of either DASDs or one dimension formed from M DASDs and the second dimension formed from the (M-1) bit recording extents on at least one track for each of M DASDs.
Claim 5
Dependent Claim
33 words
A method according to claim 1, 2, 3 or 4, wherein the rebuilding step includes striping and writing the rebuilt data using predetermined spare DASD array capacity in place of the unavailable DASDs.
Claim 6
Dependent Claim
20 words
A method according to claim 5, wherein the spare DASD capacity is in the form of DASDs reserved as spares.
Claim 7
Independent Claim
164 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, M being a prime number, the encoding being executed in an alternating diagonal and row manner covering the data array as a topological cylinder, each encoding action resulting in a first and second simple parity (XOR), the 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 the 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 repetition of the encoding and writing process covering the data array as a topological cylinder.
Claim 8
Dependent Claim
51 words
A method according to claim 7, wherein if M be not a prime number then 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 9
Dependent Claim
207 words
A computer implemented method for coding and rebuilding the contents of up to two unavailable DASDs in an M DASD array, the DASD array being attached by way of a controller to a computing system, comprising the steps of: (a) block encoding and writing onto the M DASD array at least one (M-1)*M data array of simple parity encoded data in alternating diagonal and row major wrap around 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 the 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 repetition of the encoding and writing process covering the data array in alternating diagonal and row major wrap around order.
Claim 10
Dependent Claim
100 words
A method according to claim 9, wherein the computer executes at least one small write access to the (M-1)*M data array stored on array of M DASDs, a first and a second DASD storing simple parity while M-2 other DASDs storing data, and wherein the 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 11
Dependent Claim
154 words
Data processing system including a central processing unit, an array of at least M DASDs and spares thereof, and means intercoupling the central processing unit and the array for synchronously accessing selectable ones of the DASDs, and including means for read and write accesses of M bits at a time striped over M DASDs, characterised in that the intercoupling means includes: (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, the 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) on a scheduled or opportunistic basis modified such that the array diagonals are oppositely sloped.
Claim 12
Dependent Claim
35 words
A system according to claim 10, wherein the said intercoupling means includes means for substituting unassigned spare DASDs for the failed ones and for writing back rebuild data across M DASDs including the substituted DASDs.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.