Method and means for coding and rebuilding that data contents of unavailable DASDs or rebuilding the contents of DASDs in error in the presence of reduced number of unavailable DASDs in a DASD array
First Claim
1. An external storage subsystem having a plurality of DASDs and a control unit for attaching a subset of said plurality of DASDs to a processor in the form of an array of M DASDs, said array of M DASDs including P DASDs for storing parity blocks and M-P DASDs for storing data blocks, logically related ones of said data and parity blocks forming addressable parity groups, no two blocks from the same parity group being stored on the same DASD in said array, said processor sending sequences of read and write commands to said control unit for selectively accessing at least one data block and one parity block from the same parity group, M being at least equal to two and P being at least equal to one, a subset of S DASDs of said plurality of DASDs being available as spares for inclusion in said DASD array, S being at least equal to P,a method for encoding and rebuilding the data contents of up to R failed data and parity DASDs, R being less than or equal to P, comprising the steps of:
- (a) parity coding and writing a (M-1)×
M array of data and parity blocks onto the M DASDs, each block being uniform in extent and at least one bit in length, said data and parity blocks being coded and written onto the M DASDs by said control unit by(1) traversing M parity lines projected onto said (M-1)×
M data and parity block array for each one of a set of slopes consisting of slope magnitudes 0, 1, 2, . . . , P-1, and extending cyclically over said (M-1)×
M data and parity block array; and
(2) inserting Boolean values into the (M-1)×
M data and parity block array in counterpart DASD array locations during each traverse such that data and parity blocks in said data and parity block array encountered over each traverse sum to zero modulo 2 (even parity), M being a prime number, said data and parity block array being fully encoded in M*(P-18) parity line traverses; and
(b) responsive to any unavailability of R DASDs distributed among the M-P data and P parity DASDs,(1) rebuilding the data and parity block array by said controller by coding the data and parity blocks from M-R available DASD'"'"'s according to step (a) in which those data and parity blocks as stored on the R unavailable DASDs are assumed to exhibit a uniform default value, and,(2) rewriting the rebuilt data and parity block array onto a DASD array formed from M-R available DASDs and R of the S spare DASDs.
0 Assignments
0 Petitions
Accused Products
Abstract
A method and means for coding an (M-1)×M data array written onto an array of M synchronous recording paths and for rebuilding and writing onto spare recording path capacity when up to a preselected number R of array DASDs fail, or one DASD becomes erroneous and up to R-2 fail. Data is mapped into the parallel paths using an (M-1)×M data and parity block array as the storage model where M is a prime number and each block extent is uniform and at least one bit in length. The (M-1)×M data and parity block array is encoded to include zero XOR sums along a traverses of slopes 0, 1, 2, . . . , P-1, extended cyclically over said data array. Rebuilding data and parity blocks is occasioned upon unavailability of no more than R less than or equal to P recording path failures, or one recording path in error and up to R-2 recording path failures. This includes calculating XOR-sums along the traversed paths of P-1 slopes, cyclic and linear shifts and XOR operations, recovering the unavailable DASDs by means of iterative solution of a set of recursions, and finally writing the rebuilt array back to onto M recording paths inclusive of any spare paths.
177 Citations
9 Claims
-
1. An external storage subsystem having a plurality of DASDs and a control unit for attaching a subset of said plurality of DASDs to a processor in the form of an array of M DASDs, said array of M DASDs including P DASDs for storing parity blocks and M-P DASDs for storing data blocks, logically related ones of said data and parity blocks forming addressable parity groups, no two blocks from the same parity group being stored on the same DASD in said array, said processor sending sequences of read and write commands to said control unit for selectively accessing at least one data block and one parity block from the same parity group, M being at least equal to two and P being at least equal to one, a subset of S DASDs of said plurality of DASDs being available as spares for inclusion in said DASD array, S being at least equal to P,
a method for encoding and rebuilding the data contents of up to R failed data and parity DASDs, R being less than or equal to P, comprising the steps of: -
(a) parity coding and writing a (M-1)×
M array of data and parity blocks onto the M DASDs, each block being uniform in extent and at least one bit in length, said data and parity blocks being coded and written onto the M DASDs by said control unit by(1) traversing M parity lines projected onto said (M-1)×
M data and parity block array for each one of a set of slopes consisting of slope magnitudes 0, 1, 2, . . . , P-1, and extending cyclically over said (M-1)×
M data and parity block array; and(2) inserting Boolean values into the (M-1)×
M data and parity block array in counterpart DASD array locations during each traverse such that data and parity blocks in said data and parity block array encountered over each traverse sum to zero modulo 2 (even parity), M being a prime number, said data and parity block array being fully encoded in M*(P-18) parity line traverses; and(b) responsive to any unavailability of R DASDs distributed among the M-P data and P parity DASDs, (1) rebuilding the data and parity block array by said controller by coding the data and parity blocks from M-R available DASD'"'"'s according to step (a) in which those data and parity blocks as stored on the R unavailable DASDs are assumed to exhibit a uniform default value, and, (2) rewriting the rebuilt data and parity block array onto a DASD array formed from M-R available DASDs and R of the S spare DASDs. - View Dependent Claims (2, 3, 4, 5, 7)
-
-
6. An external storage subsystem having a plurality of DASDs and a control unit for attaching a subset of said plurality of DASDs to a processor in the form of an array of M DASDs, said array of M DASDs including P DASDs for storing parity blocks and M-P DASDs for storing data blocks, logically related ones of said data and parity blocks forming addressable parity groups, no two blocks from the same parity group being stored on the same DASD in said array, said processor sending sequences of read and write commands to said control unit for selectively accessing at least one data block and one parity block from the same parity group, M being at least equal to two and P being at least equal to one, a capacity equivalent to subset of S DASDs of said plurality of DASDs being distributed among the M DASDs as spare space, S being at least equal to P, a method comprising the steps of:
-
(a) parity coding and writing a (M-1)×
M array of data and parity blocks onto the M DASDs, each block being uniform in extent and at least one bit in length, said array data and parity blocks being coded and written onto the M DASDs by said control unit by(1) traversing M parity lines projected onto said data and parity block array for each one of a set of slopes consisting of slope magnitudes 0, 1, 2, . . . , P-1, and extending cyclically over said data and parity block array; and (2) inserting Boolean values into the (M-1)×
M data and parity block array in counterpart DASD array locations during each traverse such that data and parity blocks in said data and parity block array encountered over each traverse sum to zero modulo 2 (even parity), M being a prime number, said data and parity block array being fully encoded in M*(P-1) parity line traverses; and(b) responsive to any unavailability of R DASDs distributed among the M-P data and P parity DASDs, (1) rebuilding the data and parity block array by said control unit by coding the data and parity blocks from M-R available DASD'"'"'s according to step (a) in which those data and parity blocks as stored on the R unavailable DASDs are assumed to exhibit a uniform default value, and (2) rewriting the rebuilt data and parity block array onto a DASD array formed from M-R available DASDs and R of the S spare DASDs.
-
-
8. An external storage subsystem having a plurality of DASDs and a control unit for attaching a subset of said plurality to a processor in the form of an array of M DASDs, said array of M DASDs including P DASDs for storing parity blocks and M-P DASDs for storing data blocks, logically related ones of said data and parity blocks forming addressable parity groups, no two blocks from the same parity group being stored on the same DASD, said processor sending sequences of read and write commands to said control unit for selectively accessing at least one data block and one parity block from the same parity group, M being at least equal to two and P being at least equal to one, a subset of S DASDs of said plurality being available as spares for inclusion in said array, S being at least equal to P, wherein said control unit comprises:
-
(a) means for parity coding and writing a (M-1)×
M array of data and parity blocks onto the M DASDs, each block being uniform in extent and at least one bit in length, said array data and parity blocks being coded and written onto the M DASDs, said parity coding and writing means include(1) means for traversing M parity lines projected onto said data and parity block array for each one of a set of slopes consisting of slope magnitudes 0, 1, 2, . . . , P-1, and extending cyclically over said data and parity block array; and (2) means for inserting Boolean values into the (M-1)×
M data and parity group array in counterpart DASD array locations during each traverse such that data and parity blocks in said data and parity block array encountered over each traverse sum to zero modulo 2 (even parity), M being a prime number, said data and parity block array being fully encoded in M*(P-1) parity line traverses; and(b) means responsive to any unavailability of R DASDs distributed among the M-P data and P parity DASDs for (1) rebuilding the data and parity block array by said control unit by coding the data and parity blocks from M-R available DASD'"'"'s according to the parity coding and writing means in which those data and parity blocks as stored on the R unavailable DASDs are assumed to exhibit a uniform default value, and, (2) rewriting the rebuilt data and parity block array onto a DASD array formed from M-R available DASDs and R of the S spare DASDs. - View Dependent Claims (9)
-
Specification