Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Row-Diagonal Parity (RDP) is a new algorithm for protecting against double disk failures. It stores all data unencoded, and uses only exclusive-or operations to compute parity. RDP is provably optimal in computational complexity, both during construction and reconstruction. Like other algorithms, it is optimal in the amount of redundant information stored and accessed. RDP works within a single stripe of blocks of sizes normally used by file systems, databases and disk arrays. It can be utilized in a fixed (RAID-4) or rotated (RAID-5) parity placement style. It is possible to extend the algorithm to encompass multiple RAID-4 or RAID-5 disk arrays in a single RDP disk array. It is possible to add disks to an existing RDP array without recalculating parity or moving data. Implementation results show that RDP performance can be made nearly equal to single parity RAID-4 and RAID-5 performance.

REFERENCES

• 1: Kenneth Salem , Hector Garcia-Molina, Disk Striping, Proceedings of the Second International Conference on Data Engineering, p.336-342, February 05-07, 1986
• 2: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• 3: W. Burkhard, and J. Menon, "Disk array storage system reliability". Proceedings of the International Symposium on Fault-tolerant Computing, pgs.432-441, 1993.
• 4: Qin Xin , Ethan L. Miller , Thomas Schwarz , Darrell D. E. Long , Scott A. Brandt , Witold Litwin, Reliability Mechanisms for Very Large Storage Systems, Proceedings of the 20 th IEEE/11 th NASA Goddard Conference on Mass Storage Systems and Technologies (MSS'03), p.146, April 07-10, 2003
• 5: M. Blaum , J. Brady , J. Bruck , J. Menon, EVENODD: an optimal scheme for tolerating double disk failures in RAID architectures, Proceedings of the 21ST annual international symposium on Computer architecture, p.245-254, April 18-21, 1994, Chicago, Illinois, United States
• 6: F. J. MacWilliams and J. J. A. Sloane. The Theory of Error-Corrrecting Codes, North-Holland, 1977.
• 7: Guillermo A. Alvarez , Walter A. Burkhard , Flaviu Cristian, Tolerating multiple failures in RAID architectures with optimal storage and uniform declustering, Proceedings of the 24th annual international symposium on Computer architecture, p.62-72, June 01-04, 1997, Denver, Colorado, United States
• 8: Chan-Ik Park, Efficient Placement of Parity and Data to Tolerate Two Disk Failures in Disk Array Systems, IEEE Transactions on Parallel and Distributed Systems, v.6 n.11, p.1177-1184, November 1995 [doi>10.1109/71.476189]
• 9: Richard R. Muntz , John C. S. Lui, Performance analysis of disk arrays under failure, Proceedings of the sixteenth international conference on Very large databases, p.162-173, September 1990, Brisbane, Australia
• 10: Dave Anderson , Jim Dykes , Erik Riedel, More Than an Interface---SCSI vs. ATA, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 11: Mark Holland , Garth A. Gibson, Parity declustering for continuous operation in redundant disk arrays, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.23-35, October 12-15, 1992, Boston, Massachusetts, United States
• 12: A. Papoulis, Probability, Random Variables, and Stochastic Processes, Second Edition, McGraw-Hill, New York, 1984.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Storage hierarchies
      D.4.3 File Systems Management
          Subjects: File organization

General Terms:
Management, Reliability