Browse Prior Art Database

Efficient Addressing Scheme for Clustered Redundant Array of Independent Disks

IP.com Disclosure Number: IPCOM000105007D
Original Publication Date: 1993-Jun-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 6 page(s) / 201K

Publishing Venue

IBM

Related People

Yu, PS: AUTHOR

Abstract

Disclosed is an efficient address mapping scheme is developed for clustered RAID to determine the disk address of any data or parity block. A Redundant Array of Independent Disks (RAID) of G disks provides protection against single disk failures by adding one parity block for each G-1 data blocks. In a clustered RAID , the G data/parity blocks are distributed over a cluster of C disks (C gt G), thus reducing the additional load on each disk due to a single disk failure. However, no efficient mechanism for implementing such a mapping has yet been proposed for general C and G values.

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

Efficient Addressing Scheme for Clustered Redundant Array of Independent Disks

      Disclosed is an efficient address mapping scheme is developed
for clustered RAID to determine the disk address of any data or
parity block.  A Redundant Array of Independent Disks (RAID) of G
disks provides protection against single disk failures by adding one
parity block for each G-1 data blocks.  In a clustered RAID , the G
data/parity blocks are distributed over a cluster of C disks (C gt
G), thus reducing the additional load on each disk due to a single
disk failure.  However, no efficient mechanism for implementing such
a mapping has yet been proposed for general C and G values.

      Consider an array (cluster) of C disks, with parity groups of G
le C blocks.  A parity group consists of G-1 blocks of data, and an
additional parity block, which is typically the bitwise exclusive-or
of the other blocks in the group.  These blocks are stored on
different disks, so that if one disk fails, any block resident on it
can be reconstructed from the remaining blocks in its group, which
are still available.  A block is simply a unit of data, which may be
as small as a page (the smallest amount of data read or written), or
it may be as large as an entire track.

      It is assumed that there are B blocks available per disk, so
that the disk array has a physical capacity of BC blocks.  Without
loss of generality, the data can be assumed to be on a single logical
disk with blocks numbered 0, 1, ..., BC-1; these blocks include
parity blocks.  The subsets  lbrace 0, 1, ..., G-1 rbrace ,
 lbrace G, G+1, ..., 2G-1 rbrace, ...  form parity groups, and the
last block in each group is the parity block.

      Having described the logical configuration of a disk array, it
is next considered how this configuration is mapped into the physical
array.  The mapping is described by the addressing scheme
Address(i)=(Disk(i), LocalBlock(i)) which indicates that block i is
block number LocalBlock(i) on disk number Disk(i).  This addressing
scheme must fit several requirements:

1.  It must map members of the same parity group to different disks.
2.  Since a page in the parity block is updated whenever any page in
    the group is updated, it attracts much more traffic than the
    other blocks.  To balance the load, the addressing scheme  must
    distribute the parity blocks of the groups uniformly over the
    disks.
3.  If a disk fails, a data page requested from it causes reads on
    the G-1 disks  holding the group-mates of this block.  To balance
    the additional load during failure, therefore, the group-mates of

    the blocks on each disk are required to be uniformly distributed
    over the remaining disks.
4.  Finally, the address must be efficient to compute, since this
    occurs whenever data is accessed.

      A simple addressing scheme based on random permutations is
proposed.  For simplicity, i...