Browse Prior Art Database

Parity Group Placement for Improved Degraded Mode and Rebuild Performance in Disk Arrays with Multiple Disk Failures

IP.com Disclosure Number: IPCOM000106544D
Original Publication Date: 1993-Nov-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 4 page(s) / 135K

Publishing Venue

IBM

Related People

Mattson, RL: AUTHOR [+2]

Abstract

Disclosed is a parity group placement technique which maintains with each successive disk failure of a redundant disk array with distributed sparing improved degraded mode performance and rebuild performance.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 45% of the total text.

Parity Group Placement for Improved Degraded Mode and Rebuild Performance in Disk Arrays with Multiple Disk Failures

      Disclosed is a parity group placement technique which maintains
with each successive disk failure of a redundant disk array with
distributed sparing improved degraded mode performance and rebuild
performance.

      Earlier work [*]  has shown that when the extra workload caused
by the failure of a disk in a redundant disk array is evenly
distributed among all the remaining surviving disks, then the
degraded mode performance and the rebuild performance are improved.
The approach is called uniform parity group distribution (UPGD).
Other prior work has shown the benefits of distributing spare space
throughout an entire array over the dedicated spare disks approach.
The distributed sparing technique can be combined with the uniform
parity group distribution technique by simply adding some spare space
to each disk of a UPGD array.  While such an array will have the
desirable performance characteristics of UPGD when the first disk
failure occurs, however, after the content of the failed disk has
been rebuild onto the distributed spare space, there is no guarantee
that the resulting array is another UPGD array.  Thus, if a second
disk failure occurs, the array will not have the desirable
performance characteristics of UPGD.

      A procedure is described here for constructing and maintaining
an array with distributed sparing such that it becomes another UPGD
array after the rebuild for each disk failure.  An example is shown
in the Figure.  In the following, let (x,y)-BCBD denote a balanced
complete block design formed by the enumerations in a (x,y)-BCBD,
which is x!/((x-y)!y!).  In addition, let v sub i be the number of
disks containing data/parity before the (i+1)th disk failure where i
= 0, 1, ..., f-1.  Note that v sub 0 = v, v sub i+1 = v sub i-1, and
v sub i = v - i

1.  Specify a disk array size of v disks (v = 5 in example).

2.  Specify a parity group size of k domains per parity group (k = 3
    in example).

3.  Specify a number f = < (v-k) indicating the number of failed
    disks that can be mapped to spare space in the array (f = 2 in
    example).

4.  Determine an integer Z - < (v-k)(v-k-1)...(v-k-f+1) so that
         b = Z x E(v,k), and (v sub i-k) x E(v sub i,k) divides b
    evenly for all values of i = 0, 1, and f-1.  In other words, for
    each value of i = 0, 1, ..., and f-1, there is an integer Q sub i
    such that
         b = Q sub i x (v sub i-k) x E(v sub i,k).

          The existence of this integer value for Q sub i is
    important for the remaining steps.  Obviously, Z -
    (v-k)(v-k-1)...(v-k-f+1) is one solution, however, smaller values
    of Z will often satisfy the above divisibility condition and will
    reduce the size of the UPGD layout design at each step.  (Z - 2
    in example.)

5.  Form an initial U...