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

• US 5,579,475 A
• Filed: 08/24/1995
• Issued: 11/26/1996
• Est. Priority Date: 02/11/1991
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Brady, James T., Bruck, Jehoshua, Menon, Jaishankar M., Blaum, Miguel M.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): CHUNG, PHUNG M
• Application Number:
  US08/518,955
• Time in Patent Office: 460 Days
• Field of Search: 371/10.1, 371/10.2, 371/37.4, 371/50.1, 371/51.1, 371/40.1, 371/40.4, 371/2.1, 371/37.1, 371/37.6, 371/38.1, 371/37.7, 371/49.1, 371/49.3, 395/182.05
• US Class Current: 714/6.32
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: G11C 29/88 with partially good memories
• CPC Class Codes: H03M 13/11 using multiple parity bits

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.

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.

3. The method according to claim 2, wherein step (d) includes writing said rebuilt portion either to counterpart ones of said plurality of DABDs operatively designated as spares or to spare space available on not less than M-2 remaining DASDs.

4. The method according to claim 2, wherein if M is not a prime number then causing steps (b), (c), and (d) to emulate a data block array expanded to include additional columns of uniform binary value to yield an effective array (M'"'"'-i)*M'"'"' where M'"'"' constitutes a prime number larger than M.

5. The method according to claim 2, wherein said method executes at least one small write access through said means for accessing said subsets of data blocks to the (M-1)*M data array stored on array of M DASDs, a first DASD and a second DASD of the M failure independent DASDs storing simple parity values while M-2 other DASDs of the M failure independent DASDs storing data blocks, and wherein said method further comprises the steps of:

(1) ascertaining whether a selected old data block to be updated to a new data block lies on a main or reference diagonal of the data block array;

(2) in the event that the old data block is not located on the main diagonal, then

(a) reading the old data block from a DASD of the M-2 other DASDs storing said old data block and reading old diagonal and old row parity values from the first DASD and second DASD, respectively;

(b) determining a new diagonal parity value by XOR'"'"'ing the old data block, new data block, and old diagonal parity value, and determining a new row parity value by XOR'"'"'ing the old data block, new data block, and old row parity value; and

(c) writing said new data block, and new diagonal and row parity values in place in the DASD of the M-2 other DASD and the first DASD and second DASD, respectively;

(3) in the event that the old data block is located on the main diagonal, then

(a) reading the old data block from the DASD of the M-2 other DASDs storing said old data block, the old row parity value from the second DASD, and M diagonal parity values from the first DASD;

(b) determining each of M new diagonal parity values by XOR'"'"'ing an old counterpart diagonal parity value of the M diagonal parity values, the old data block and the new data block, and determining a new row parity value by XOR'"'"'ing the old data block, the new data block, and the old row parity value; and

(c) writing said new data block, new row parity value, and M new diagonal parity values to counterpart ones of the M failure independent DASDs.

6. The method according to claim 5, wherein step (3)(c) further includes the step of writing said data blocks and parity values in place in said counterpart ones of the M failure independent DASDs.

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.

8. The method according to claim 7, wherein said accessing means includes means for reserving spare space across M-2 DASDs of said M DASDs, and further wherein step (e) includes the step of writing said rebuilt unavailable portion to spare space available on not less than the M-2 of said M DASDs.

9. The method according to claim 7, wherein in step (d) the step of generation of the (M-1) new diagonal parity values responsive to the write update command to modify a data block located on the major diagonal further includes the step of logically complementing counterpart old diagonal parity values.

10. The method according to claim 7, wherein step (e) is modified such that

(1) if two unavailable DASDs consist of the DASDs storing the diagonal parity and row parity values respectively on an (M-1)st DASD and on an Mth DASD, then repeating step (b) and writing the reconstituted row and parity values to spare DASD substitutes for the (M-1)st and Mth DASDs respectively,

(2) if the two unavailable DASDs consist of an ith DASD storing data blocks and an Mth DASD storing row parity values, then reconstructing the ith DASD by ascertaining the parity mode of the major diagonal, calculating each data block of the ith DASD by XOR'"'"'ing only the data blocks lying along the diagonal intersecting the ith DASD according to the ascertained parity mode, and reconstructing the Mth DASD by calculating each row parity value by XOR'"'"'ing only the data blocks lying along the row intersecting the Mth DASD, and writing said calculated data blocks and row parity values to the spare DASD substitutes for the ith DASD and Mth DASD respectively,

(3) if the two unavailable DASDs consist of the ith DASD storing data blocks and the (M-1)st DASD storing diagonal parity values, then reconstructing the ith DASD by calculating each data block of the ith DASD by XOR'"'"'ing each of any remaining data blocks and the row parity value intersecting the ith DASD, and reconstructing the (M-1)st DASD by ascertaining the parity mode of the major diagonal, calculating each diagonal parity value by XOR'"'"'ing the data blocks lying along the diagonal intersecting the (M-1)st DASD, together with said parity mode of the major diagonal, and writing said calculated data blocks and diagonal parity values to the spare DASD substitutes for the ith DASD and (M-1)st DASD respectively, and

(4) if the two unavailable DASDs consist of a pair of DASDs (ith and jth DASDS) storing data blocks, then ascertaining the parity mode of the major array diagonal as being odd if the XOR of the diagonal parity values is not equal to the XOR of the row parity values and as being even otherwise, ascertaining each data block value in either the ith or jth DASD as an XOR solution to a single equation with a single unknown formed by either a diagonal of data blocks and diagonal parity value intersecting said each data block being calculated or a row of data blocks and row parity value intersecting said each data block being calculated, and writing said calculated data blocks to the spare DASD substitutes for the ith and jth DASDs.