Method and means for encoding and rebuilding the data contents of up to two unavailable DASDS in a DASD array using simple non-recursive diagonal and row parity
First Claim
1. A method for encoding and rebuilding of any data contents of up to two unavailable direct access storage devices (DASD'"'"'s) from an array of M failure independent DASDs and a plurality of DASDs operative as spares to said array of M failure independent DASDs and where a two DASD equivalent of spare space is distributed over said M failure independent DASDs, M being a prime number, said data contents being expressed as an (M-1)*(M-2) data block array, the blocks in each row of the data array being stored in counterpart ones of the DASDS forming the array of M failure independent DASDs, comprising the steps of:
- (a) generating an (M-1)*M data block array from the (M-1)*(M-2) data block array by calculating non-recursive simple parity values over diagonal and row traverses of the (M-1)*(M-2) data block array, said parity values being calculated in respective diagonal major and row major order and being defined over a counterpart diagonal or row of said data block array, a parity mode (odd or even) of data blocks along a reference diagonal operating as a mode for calculating a parity value for non-reference diagonals, the parity value for each row being calculated according to an even mode;
(b) writing the blocks in each row of said (M-1)*M data array to counterpart ones of said M failure independent DASDs; and
(c) responsive to the availability of up to two DASDs, rebuilding any portion of said data array from not less than (M-2) available DASDs and writing said rebuilt portion either to counterpart spare DASDs or to spare space available on no less than M-2 remaining DASDs.
0 Assignments
0 Petitions
Accused Products
Abstract
The data contents of up to two concurrently failed or erased DASDs can be reconstituted where the data is distributed across M DASDs as an (M-1)*M block array and where (1) the (M-1)st DASD contains the simple parity taken over each of the array diagonals in diagonal major order in the same mode (odd/even) as that exhibited by the major diagonal of the array and (2) where the M-th DASD contains the simple even parity over each of the rows in row major order. Relatedly, short write updates require fewer operations for data blocks located off the major data array diagonal.
-
Citations
10 Claims
-
1. A method for encoding and rebuilding of any data contents of up to two unavailable direct access storage devices (DASD'"'"'s) from an array of M failure independent DASDs and a plurality of DASDs operative as spares to said array of M failure independent DASDs and where a two DASD equivalent of spare space is distributed over said M failure independent DASDs, M being a prime number, said data contents being expressed as an (M-1)*(M-2) data block array, the blocks in each row of the data array being stored in counterpart ones of the DASDS forming the array of M failure independent DASDs, comprising the steps of:
-
(a) generating an (M-1)*M data block array from the (M-1)*(M-2) data block array by calculating non-recursive simple parity values over diagonal and row traverses of the (M-1)*(M-2) data block array, said parity values being calculated in respective diagonal major and row major order and being defined over a counterpart diagonal or row of said data block array, a parity mode (odd or even) of data blocks along a reference diagonal operating as a mode for calculating a parity value for non-reference diagonals, the parity value for each row being calculated according to an even mode; (b) writing the blocks in each row of said (M-1)*M data array to counterpart ones of said M failure independent DASDs; and (c) responsive to the availability of up to two DASDs, rebuilding any portion of said data array from not less than (M-2) available DASDs and writing said rebuilt portion either to counterpart spare DASDs or to spare space available on no less than M-2 remaining DASDs.
-
-
2. In a system having a plurality of direct access storage devices (DASDs), a portion of said plurality of DASDs forming an array of M failure independent DASDs, said system further having means responsive to a source of external commands for accessing subsets of data blocks logically addressed in an (M-1)*(M-2) array of data blocks from said M failure independent DASDs, M being a prime number, said array of data blocks having a plurality of diagonals definable thereover, a predetermined one of said diagonals being designated as a major or reference diagonal, said data blocks being arranged in said array of data blocks in diagonal and row major order, each diagonal and row order of data blocks having a parity mode (odd or even), a method for encoding and rebuilding of contents of said array of data blocks in the event that up to two DASD'"'"'s from the M failure independent DASD array become unavailable, comprising the steps of:
-
(a) ascertaining a parity mode of the major diagonal of data blocks in the (M-1)*(M-2) data block array; (b) generating an (M-1)*(M-2) data block array from said (M-1)*M-2) data array by forming an (M-1)th column by calculating simple parity values from the data blocks in diagonal major order according to the parity mode of step (a) and by forming an M-th column by calculating simple parity values from the data blocks in row major order according to an even parity mode; (c) writing said (M-1)*M data block array onto counterpart locations across the M failure independent DASD array or space equivalent in the event of DASD unavailability; and (d) responsive to the unavailability of up to two DASDs, rebuilding any portion of said data array from not less than (M-2) available DASDs. - View Dependent Claims (3, 4, 5, 6)
-
-
7. In a system having a plurality of DASDs, said system including means for operatively accessing an integer number M of said plurality in a higher level redundant array of inexpensive disks (RAID) configuration, M being a prime number, said accessing means being responsive to a source of external commands for reading and writing of data blocks stored on selected ones of said M of said plurality of DASDs, said data blocks being arranged in a (M-1)*(M-2) logical array, said logical array being formed from (M-1) rows and (M-2) data blocks per row, each of the (M-2) data blocks in each of the (M-1) rows in said logical array being written across counterpart ones of the M-2 of the DASDs, ones of said plurality being designated as spares, a method comprising the steps of:
-
(a) ascertaining a parity mode of the data blocks distributed over a major diagonal of the logical array, the data blocks in the logical array also being ordered as a plurality of diagonals; (b) generating an (M-1)*M logical array from the (M-1)*(M-2) logical array by forming a (M-1)st column of parity values by calculating a simple parity over each diagonal of said plurality of diagonals according to the parity mode of step (a) in a diagonal major order and by forming an M-th column of parity values by calculating the simple parity to over each row in row major order; (c) writing the generated (M-1)*M logical array across the M DASDs; (d) responsive to a write update command to modify a data block NOT located on the major diagonal of the logical array by reading the old data block, an old diagonal parity value, and an old row parity value, calculating a new diagonal and a new row parity value, and writing the modified data block and the new diagonal and row parity values in place among the M DASDs, and responsive to a write update command to modify a data block located on the major diagonal, repeating steps (a) and (b) with respect to generation of (M-1) new diagonal parity values and the new row parity value and writing the modified data block and new diagonal parities and new row parity in place among the M DASDs; and (e) responsive to unavailability of up to two DASDs, rebuilding a portion of said logical array from not less than (M-2) available DASDs and writing said rebuilt unavailable portion to counterpart ones of said plurality of DASDs operatively designated as spares. - View Dependent Claims (8, 9, 10)
-
Specification