Method and means for distributed sparing in DASD arrays

• US 5,258,984 A
• Filed: 06/13/1991
• Issued: 11/02/1993
• Est. Priority Date: 06/13/1991
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ng, Spencer W., Menon, Jaishankar M., Mattson, Richard L.
• Primary Examiner(s): Canney, Vincent P.
• Application Number:
  US07/714,969
• Time in Patent Office: 873 Days
• Field of Search: 371/10.1, 371/10.2, 371/11.1, 395/575, 364/268.5, 364/269.2
• US Class Current: 714/6.32
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G11C 29/88 with partially good memories

Abstract

A method and means in which data and parity blocks forming parity groups together with spare blocks are distributed over array block locations according to at least one combinatorial design, each group having N data and P parity blocks. The combinatorial designs yield uniform or balanced loading thereby minimizing the number of accesses to reconstruct missing data and parity blocks and their copyback into spare block locations, and, minimize the number of accesses to the reconstructed data referenced subsequent to its copyback. Distributions of the spare block capacity of one or two DASDs are shown over single and multiple arrays and shared among multiple arrays. Parity block distribution although ancillary to spare distribution enhances throughput and reduces the number of accesses for rebuild etc.

Claims

1. In a storage subsystem having a plurality of DASDs, a method for rebuilding portions of parity groups resident on a failed one of said DASDs, each parity group including N data, P parity, and S spare blocks, each DASD storing K blocks, comprising the steps of:

(a) configuring an array of N+P+S DASDs;

(b) distributing K parity groups in synchronous array addresses across subsets of N+P DASDs of the array such that no two blocks from the same parity group reside on the same DASD, each DASD storing data or parity blocks from (K-K*S/N+P+S)) parity groups, and distributing K*S blocks as spare storage across the array such that each DASD includes K*S/(N+P+S) spare blocks thereon; and

(c) in the event of a single DASD failure, for each of the K-K*S/(N+P+S) parity groups on the failed DASD, logically combining N+P+S-2 blocks belonging to the group from N+P+S-2 other DASDs into a single block, and, writing said single block into a counterpart one of the remaining K*S*(N+P+S-1)/(N+P+S) spare blocks such that no two blocks of the same parity group are distributed on the same DASD.

24. The method according to any one of the claims 1, 2, or 21, wherein the step of distributing parity groups includes the step for alternatively distributing parity blocks to a dedicated one of the DASDs.

2. In a storage subsystem having a plurality of DASDs, a method for rebuilding portions of parity groups resident on a failed one of said DASDs, each parity group including N data and 1 parity blocks, each DASD storing K blocks, comprising the steps of:

(a) configuring an array of N+2 DASDs;

(b) distributing K parity groups in synchronous array addresses across subsets of N+1 DASDs of the array such that no two blocks from the same parity group reside on the same DASD, each DASD storing K-K/(N+2) data or parity blocks, and distributing K blocks as spare storage across the array such that each DASD includes K/(N+2) spare blocks thereon; and

(c) in the event of a single DASD failure, for each of the K-K/(N+2) parity groups, logically combining N blocks belonging to the group from N other DASDs into a single block, and, writing said single block into a counterpart one of the remaining K*(N+1)/(N+2) spare blocks such that no two blocks of the same parity group are distributed on the same DASD.

3. The method according to claim 2, wherein each parity group is written into N+1 storage locations, and upon failure of a single DASD and rebuilding of said parity groups, only K-(K/(N+2)) storage locations are rendered unavailable.

4. The method according to claim 2, wherein all array DASDs other than failed DASD are addressable and responsive to access commands whether operated in fault tolerant or degraded modes.

5. The method according to claim 2, wherein the steps of distributing up to K parity groups and K spare storage blocks further comprises the steps of:

distributing said parity groups and spare blocks across N+2 DASDs such that no more than one spare storage block nor more than one parity block are stored on the same synchronous array address or on the same DASD.

6. The method according to claim 2, wherein steps (b) and (c) further comprise the steps of

distributing 2*K blocks of spare storage and K*P parity blocks such that no more than two spare storage blocks nor more than P parity blocks are stored on the same synchronous array address or on the same DASD.

7. The method according to claim 2, wherein the parity block from each of the K groups is written to a dedicated one of the N+2 DASDs.

8. The method according to claim 2, wherein each parity group is accessed concurrently from a selective subset of N+1 of the N+2 DASDs.

9. The method according to claim 2, wherein each parity group is accessed non-concurrently from a selective subset of N+1 of the N+2 DASDs.

10. The method according to claim 2, wherein each DASD includes cyclic track storage means of m tracks;

and means for moving from track to track and reading or writing data or parity blocks selectively along one or more tracks; and

further wherein the method step (c) includes the steps of;

(1) positioning the moving means to a predetermined location on the cyclic track storage means of each of the remaining N+1 DASDs and traversing all m tracks starting from the predetermined location;

(2) at the start of the traverse, logically combining and writing the block lost from the first parity group onto the spare block of (N+2)nd DASD concurrent with a reading operation performed by the remaining N other DASDs;

(3) continuing logically combining and writing the block lost from the second parity group on the spare block of the (N+1)st DASD concurrent with a reading operation performed by the remaining N DASDs; and

(4) repeating step (3) until each block stored on the failed DASD from the K-K/(N+2) parity groups is recreated and rewritten into a counterpart spare block across each of the remaining DASDs.

11. A storage subsystem for accessing parity groups of N data blocks and 1 parity block each, comprising:

an array formed from N+2 DASDs, each DASD having the storing K blocks;

first means for distributing N+1 blocks of each of K parity groups across counterpart subsets of N+1 DASDs selected from the array such that no two blocks from the same parity group is stored on the same DASD;

means for distributing K blocks of storage as spare blocks such that each array DASD reserves K/(N+2) blocks thereon;

second means for identifying any single DASD failure; and

means responsive to any single DASD failure identified by the seconds means for processing each of up to K-K/(N+2) parity groups by logically combining N blocks belonging to the group from N other DASDs into a single block, and, writing said single block into a counterpart one of the remaining up to K*(N+1)/(N+2) spare blocks such that no two blocks of the same parity group are distributed on the same DASD.

12. The storage subsystem according to claim 11, wherein the K spare blocks are distributed such that no two blocks occupy the same array address and the same DASD.

13. The storage subsystem according to claim 11, wherein upon failure of a single DASD and rebuilding of said parity groups, only K-(K/(N+2)) block storage locations are rendered unavailable for array use.

14. The storage subsystem according to claim 11, wherein the parity block from each of the K-K/(N+2) groups is written to a dedicated one of the N+2 DASDs.

15. The storage subsystem according to claim 11, wherein each DASD includes cyclic track storage means of m tracks;

and means for moving from track to track and reading or writing data or parity blocks selectively along one or more tracks; and

further wherein the means for logically combining and writing the K parity groups includes;

means for positioning the moving means to a predetermined location on the cyclic track storage means of each of the remaining N+1 DASDs and for traversing all m tracks starting from the predetermined location;

third means at the start of the traverse, for logically combining and for writing the block lost from the first parity group on the spare block of (N+2)nd DASD concurrent with a reading operation performed by the remaining N other DASDs; and

fourth means including the third means for continuing logically combining and writing the block lost from the second parity group on the spare block of the (N+1)st DASD concurrent with a reading operation performed by the remaining N DASDs, and for repeating the combining and writing until each block stored on the failed DASD from the K parity groups is recreated and rewritten into a counterpart spare block across the remaining DASDs.

23. The storage subsystem according to any one of the claims 11, 16, or 19, wherein said first means for distributing parity groups includes means for alternatively distributing parity blocks to only a dedicated one of the DASDs.

16. A storage subsystem comprising:

an array formed from at least N+P+2 DASDs, each DASD having the capacity to store K blocks;

first means for distributing K parity groups across any N+P DASD subset of the N+P+2 DASDs in synchronous addresses, each parity group consisting of N data blocks+P parity blocks such that no two blocks from the same parity group are stored on the same DASD;

means for reserving and distributing the capacity equivalent of up to 2*K blocks of storage as spare blocks across the array of N+P+2 DASDs such that no more than two spare storage locations nor more than one parity block are stored on the same synchronous address or on the same DASD,

second means for identifying up to any two DASD failures in said array; and

means responsive to identification by said second means of up to any two DASD failures for logically combining the K-2*K/(N+P+2) parity grups from N remaining DASDs into single blocks, and writing the single blocks into the 2*(K-1) blocks of remaining reserved spare storage such that no two portions of the same parity group are distributed on the same DASD.

17. The storage subsystem according to claim 16, wherein said system further comprises means for distributing K*P parity blocks such that not more than one parity block is located at the same synchronous address nor on the same DASD.

18. The storage subsystem according to claim 16, wherein each parity group is accessed concurrently from a selective N DASD subset of the N+2 DASDs.

19. A storage subsystem comprising:

a first and a second failure independent array each formed from at least N+P+1 DASDs, each DASD having the capacity to store K blocks;

first means for distributing K parity groups across N+P+1 DASDs of either the first or second arrays mutually exclusively, each parity group consisting of N data blocks+P parity blocks such that no two blocks from the same parity group are stored on the same DASD;

means for distributing K blocks of storage as spare blocks across N+P+1 DASDs of the first array and K blocks of storage as spare blocks across N+P+1 DASDs of the second array such that in each array only one storage block resides at each synchronous address and on each DASD;

second means for identifying a first or a second DASD failure occurring in either the first or second arrays;

means responsive to any single DASD failure identified by the second means for processing, in the array in which the failure occurred, each of the K-K/(N+P+1) parity groups by logically combining N+P-1 blocks belonging to the group from N+P-1 other DASDs into a single block, and, writing said single block into a counterpart one of the remaining K*(N+P)/(N+P+1) spare blocks such that no two blocks of the same parity group are distributed on the same DASD; and

means responsive to any second DASD failure identified in the same or other array by the second means for processing, in the array having available spare blocks, each of the K-K/(N+2) parity groups by logically combining N+P-1 blocks belonging to the group from N+P-1 other DASDs in the array in which the second failure occurred into a single block, and, writing said single block into a counterpart one of the remaining K*(N+P)/(N+P+1) spare blocks such that no two blocks of the same parity group are distributed on the same DASD.

20. The storage subsystem according to claim 19, wherein the means responsive to said second failure DASD failure maintains the subsystem in a lossless information state only if the second failure occurs after the means responsive to the first failure has rebuilt the parity groups on the failed DASD and written them into counterpart spare blocks.

21. In a storage subsystem comprising a first and a second failure independent array of DASDs, each DASD having the capacity to store K blocks, a method for rebuilding portions of parity groups resident on a failed DASD, each parity group including N data and P parity blocks, comprising the steps of:

(a) configuring a first array of N+P+1 DASDs and a second array of N+P DASDs;

(b) distributing up to K parity groups in synchronous array addresses across subsets of N+P DASDs out of N+P+1 DASDs of the first array and K parity groups across N+P DASDs of the second array such that no two blocks from the same parity group reside on the same DASD, and distributing K blocks as spare storage across the first array such that each DASD includes K/(N+P+1) spare blocks thereon, each synchronous address and DASD having only one spare block thereon;

(c) in the event of a single DASD failure occurring in the first array, for each of the K-K/(N+P+1) parity groups, logically combining N+P-1 blocks belonging to the group from N+P-1 other DASDs into a single block, and, writing said single block into a counterpart one of the remaining K*(N+P)/(N+P+1) spare blocks such that no two blocks of the same parity group are distributed on the same DASD; and

(d) in the event of a single DASD failure occurring in the second array, for each of the K parity groups, logically combining the N+P-1 blocks belonging to the group from the N+P-1 other DASDs into a single block, and, writing said single block into a counterpart one of the K spare blocks located on the first array.

22. In a storage subsystem having a plurality of DASDs, a method for rebuilding portions of parity groups resident on a failed one of said DASDs, each parity group including N data and P parity blocks, each DASD storing K blocks, comprising the steps of:

(a) configuring 2*(N+P)+1 DASDs of the plurality to form first and second addressible arrays of N+P DASDs each with one DASD shared by both arrays;

(b) distributing K spare blocks across the 2*(N+P)+1 DASDs such that each synchronous address thereacross and each DASD includes only K/(2*(N+P)+1) blocks, and

(1) distributing K parity groups across the first array of DASDs such that no synchronous first array address has more than a single parity block and that each parity group is written into a counterpart first array synchronous address to effectuate block offset or rotation from address to address; and

(2) distributing K other parity groups across subsets of N+P DASDs of the N+P+1 DASDs addressibly part of the second array such that no synchronous second array address has more than a single parity block and that each said other parity group is written into a counterpart second array synchronous address to effectuate block offset or rotation from address to address; and

(c) in the event of a single DASD failure occurring in either the first or second array, for each of the parity groups in that array, logically combining the remaining blocks belonging to the group from other DASDs in that array into a single block, and, writing said single block into a counterpart one of the remaining spare blocks distributed across both arrays such that no two blocks of the same parity group are distributed on the same DASD.