P-Code: a new RAID-6 code with optimal properties

ABSTRACT

RAID-6 significantly outperforms the other RAID levels in disk-failure tolerance due to its ability to tolerate arbitrary two concurrent disk failures in a disk array. The underlying parity array codes have a significant impact on RAID-6's performance. In this paper, we propose a new XOR-based RAID-6 code, called the Partition Code (P-Code). P-Code is a very simple and flexible vertical code, making it easy to understand and implement. It works on a group of (prime-1) or (prime) disks, and its coding scheme is based on an equal partition of a specified two-integer-tuple set. P-Code has the following properties: (1) it is a Maximum-Distance-Separable (MDS) code, with optimal storage efficiency; (2) it has optimal construction and reconstruction computational complexity; (3) it has optimal update complexity (i.e., the number of parity blocks affected by a single data-block update is minimal). These optimal properties of P-Code are proven mathematically in this paper. While X-Code is provably optimal and RDP is proven optimal in computational complexity and storage efficiency, the latter in its current form is not optimal in update complexity. We propose a row-parity placement strategy for RDP to help it attain optimal update complexity. P-Code complements the other two optimal RAID-6 codes, X-code and the tweaked RDP, to provide a near-full set of optimal RAID-6 configurations of typical disk-array size (e.g., 4-20 disks). That is, for any prime in a typical array size range, P-code can be deployed for (prime-1) disks optimally, while X-code (or P-Code) and the tweaked RDP can be respectively deployed for (prime) and (prime+1) disks optimally. Moreover, P-code's potentially beneficial properties such as the flexible association between the blocks and their labels may find useful applications in distributed environments.

REFERENCES

• 1: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), ACM SIGMOD Record, v.17 n.3, p.109-116, June 1988
• 2: Bianca Schroeder , Garth A. Gibson, Disk failures in the real world: what does an MTTF of 1,000,000 hours mean to you?, Proceedings of the 5th USENIX conference on File and Storage Technologies, p.1-es, February 13-16, 2007, San Jose, CA
• 3: Eduardo Pinheiro , Wolf-Dietrich Weber , Luiz André Barroso, Failure trends in a large disk drive population, Proceedings of the 5th USENIX conference on File and Storage Technologies, p.2-2, February 13-16, 2007, San Jose, CA
• 4: James S. Plank, A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems, Software—Practice & Experience, v.27 n.9, p.995-1012, Sept. 1997 [doi>10.1002/(SICI)1097-024X(199709)27:9<995::AID-SPE111>3.3.CO;2-Y]
• 5: Mario Blaum , Jim Brady , Jehoshua Bruck , Jai Menon, EVENODD: An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures, IEEE Transactions on Computers, v.44 n.2, p.192-202, February 1995 [doi>10.1109/12.364531]
• 6: J. Hartiline. R5X0: An efficient high distance parity-based code with optimal update complexity. Research Report RJ10322 (A0408-005), IBM Research Division, 2004.
• 7: M. Blaum and R. M. Roth. On lowest density mds codes. IEEE Transactions on Information Theory, 45(1):46--59, 1999.
• 8: J. L. Hafner et al. Performance Metrics For Erasure Codes in Storage Systems. Research Report RJ10321 (A0408-003), IBM Research Division, 2004.
• 9: L. Xu, and J. Bruck. X-Code: MDS array codes with optimal encoding. IEEE Transactions on Information Theory, 45(1):272--276, 1999.
• 10: Peter Corbett , Bob English , Atul Goel , Tomislav Grcanac , Steven Kleiman , James Leong , Sunitha Sankar, Awarded Best Paper! -- Row-Diagonal Parity for Double Disk Failure Correction, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 11: F. J. Macwilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland Publishing Company, Amsterdam, New York, Oxford, 1977.
• 12: I. S. Reed and G. Solomon. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics 8, pp. 300--304, 1960.
• 13: James S. Plank, The RAID-6 liberation codes, Proceedings of the 6th USENIX Conference on File and Storage Technologies, p.1-14, February 26-29, 2008, San Jose, California
• 14: G. Zaitsev, V. Zinov'ev, and N. Semakov. Minimum-check-density codes for correcting bytes of errors, erasures, or defects. Problems of Information Transmission, vol. 19, pp. 197--204, 1981.
• 15: L. Xu, V. Bohossian, J. Bruck, and D. Wagner. Low-density MDS codes and factors of complete graphs. IEEE Transactions on Information Theory, 45(6):1817--1826, 1999.
• 16: Y. Cassuto and J. Bruck, Cyclic low density MDS array codes, In proceedings of the 2006 IEEE International Symposium on Information Theory, pp. 2794--2798, Seattle, WA, U.S.A., July 2006.
• 17: S. Nanda and N. Deo, An algorithm for a two-disk fault-tolerant array with (prime-1) disks. Congressus Numerantium, vol. 171, pp. 13--23, 2004.
• 18: Cheng Huang , Lihao Xu, STAR: an efficient coding scheme for correcting triple storage node failures, Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, p.15-15, December 13-16, 2005, San Francisco, CA
• 19: Gui-Liang Feng , Robert H. Deng , Feng Bao , Jia-Chen Shen, New Efficient MDS Array Codes for RAID Part I: Reed-Solomon-Like Codes for Tolerating Three Disk Failures, IEEE Transactions on Computers, v.54 n.9, p.1071-1080, September 2005 [doi>10.1109/TC.2005.150]
• 20: Gui-Liang Feng , Robert H. Deng , Feng Bao , Jia-Chen Shen, New Efficient MDS Array Codes for RAID Part II: Rabin-Like Codes for Tolerating Multiple (greater than or equal to 4) Disk Failures, IEEE Transactions on Computers, v.54 n.12, p.1473-1483, December 2005 [doi>10.1109/TC.2005.200]
• 21: James Lee Hafner, HoVer Erasure Codes For Disk Arrays, Proceedings of the International Conference on Dependable Systems and Networks, p.217-226, June 25-28, 2006 [doi>10.1109/DSN.2006.40]
• 22: James Lee Hafner, WEAVER codes: highly fault tolerant erasure codes for storage systems, Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, p.16-16, December 13-16, 2005, San Francisco, CA

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance

General Terms:
Algorithms, Performance, Reliability

Keywords:
computational complexity, partition code, raid-6, storage efficiency, update complexity