ANALYTIC MODELING OF CLUSTERED RAID WITH MAPPING BASED ON NEARLY RANDOM PERMUTATION

A Redundant Array of Independent Disks (RAID) of G disks provides prot ection against single disk failures by adding one parity block for eac h G-1 data blocks. In a clustered RAID, the G data/parity blocks are d istributed over a cluster of C disks (C > G), thus reducing the additi onal load on each disk due to a single disk failure. However, most met hods proposed for implementing such a mapping do not work for general C and G values. In this paper, we describe a fast mapping algorithm ba sed on almost-random permutations. An analytical model is constructed, based on the queue with a permanent customer, to predict recovery tim e and read/write performance. The accuracy of the results derived from this model is validated by comparing with simulations. Our analysis s hows that clustered RAID is significantly more tolerant of disk failur e than the basic RAID scheme. Both recovery time and performance degra dation during recovery are substantially reduced in clustered RAID; mo reover, these gains can be achieved using fairly small C/G ratios.