A graph theoretic algorithm for placing data and parity to tolerate two disk failures in disk array systems
A graph theoretic algorithm for placing data and parity to tolerate two disk failures in disk array systems
复制标题
一种图论算法，用于放置数据和奇偶校验以容忍磁盘阵列系统中的两个磁盘故障
DOI：
10.1109/iv.2005.8
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
S. Nanda
中科院分区：
文献类型：
--
作者：
N. Deo;S. Nanda
近年来，商业化的廉价磁盘冗余阵列（RAID）系统由于其增强的I/O带宽、大容量和低成本而变得越来越流行。然而，对低成本的更大容量的持续需求导致使用更大的阵列，增加了随机磁盘故障的可能性。因此，RAID系统需要在不牺牲性能或存储空间的情况下容忍两个或更多随机磁盘故障。在本文中，我们设计了一种新的图论方法，将数据和奇偶校验的N个磁盘阵列（N/spl ges/3），使其恢复从任何两个随机磁盘故障。首先给出了圆盘个数N = P-1的一个算法，其中P是素数，然后推广了任意N的解。我们还使用我们的算法确定了N个磁盘阵列中用于存储奇偶校验的空间比例，并表明对于所有N = P-1，该比例的最佳值为21 N。为了说明，对于5和255之间的N值，该分数及其与最佳比率的差异的百分比被绘制成图。最后，我们描述了一种方法，用于确定的数据块，从那里可以开始在这样的阵列中的两个故障磁盘的重建。
In recent years commercial redundant arrays of inexpensive disks (RAID) systems have become increasingly popular because of their enhanced I/O bandwidths, large capacities and low cost. However, the continued demand for larger capacities at low cost, has led to the use of larger arrays with increased probability of random disk failures. Hence the need for RAID systems to tolerate two or more random disk failures without sacrificing performance or storage space. In this paper, we devise a novel graph-theoretic method for placing data and parity in an array of N disks (N /spl ges/ 3) to enable its recovery from any two random disk failures. We first provide an algorithm for the case when the number of disks N = P - 1, where P is a prime number, and then generalize the solution for any arbitrary N. We also determine the fraction of space used for storing parity in an array of N disks employing our algorithm, and show that this fraction has the optimal value of 21N for all N = P - 1. For illustration, this fraction and the percentage of its difference from the optimal ratio are graphed for values of N between 5 and 255. Finally, we describe a method for determining the data-blocks from where the reconstruction of two failed disks can be started in such an array.