Evaluating Approximately Balanced
Parity-Declustered Data Layouts for Disk Arrays
Eric J. Schwabe
Ian M. Sutherland
Bruce K. Holmer
Northwestern University
Abstract:
Parity declustering has been used to reduce the time required to
reconstruct a failed disk in a disk array. Most existing work on
parity declustering uses BIBD-based data layouts, which distribute
the workload of reconstructing a failed disk over the remaining disks
of the array with perfect balance. For certain array sizes, however,
there is no known BIBD-based layout. In this paper, we evaluate data
layouts that are approximately balanced --- that is, that distribute
the reconstruction workload over the disks of the array with only
approximate balance. Approximately balanced layouts are considerably
easier to construct than perfectly balanced layouts. We consider
three methods for generating approximately balanced layouts:
randomization, simulated annealing, and perturbing a BIBD-based
layout whose size is near the desired size. We compare the performance
of these approximately balanced layouts with that of perfectly balanced
layouts using a disk array simulator. We conclude that, on uniform
workloads, approximately balanced data layouts have performance nearly
identical to that of perfectly balanced layouts. Approximately
balanced layouts therefore provide the reconstruction performance
benefits of perfectly balanced layouts for arrays where perfectly
balanced layouts are either not known, or do not exist.
David Kotz --
Last modified: Wed Jan 31 12:10:23 1996