Method and means for encoding and rebuilding data contents of up to two unavailable DASDs in an array of DASDs
First Claim
1. 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.
1 Assignment
0 Petitions
Accused Products
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 array DASD 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 to onto M DASDs inclusive of the spare capacity.
183 Citations
10 Claims
-
1. 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.
-
-
2. 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. - View Dependent Claims (3, 4)
-
-
5. 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. - View Dependent Claims (6)
-
-
7. 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. - View Dependent Claims (8)
-
-
9. 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. - View Dependent Claims (10)
-
Specification