Skip to main content
SpringerLink
Log in

A cascading Latin scheme to tolerate double disk failures in raid architectures

  • Published:
Journal of Electronics (China)

Abstract

In recent years, a lot of XOR-based coding schemes have been developed to tolerate double disk failures in Redundant Array of Independent Disks (RAID) architectures, such as EVENODD-code, X-code, B-code and BG-HEDP. Despite those researches, the decades-old strategy of Reed-Solomon (RS) code remains the only popular space-optimal Maximum Distance Separable (MDS) code for all but the smallest storage systems. The reason is that all those XOR-based schemes are too difficult to be implemented, it mainly because the coding-circle of those codes vary with the number of disks. By contrast, the coding-circle of RS code is a constant. In order to solve this problem, we develop a new MDS code named Latin code and a cascading scheme based on Latin code. The cascading Latin scheme is a nearly MDS code (with only one or two more parity disks compared with the MDS ones). Nevertheless, it keeps the coding-circle of the basic Latin code (i.e. a constant) and the low encoding/ decoding complexity similar to other parity array codes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. S. Plank. A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems. Software: Practice and Experience, 27(1999)9, 995–1012.

    Article  Google Scholar 

  2. J S. Plank and Lihao Xu. Optimizing cauchy reed-solomon codes for fault-tolerant network storage applications. In Proceedings of the 5th IEEE International Symposium on Network Computing and Applications (IEEE NCA, 06), Cambridge, MA, July 2006, 173–180.

  3. Shu Lin and Daniel J. Costello. Error Control Coding. 2nd ed. Prentice Hall, 2004, 156–179.

  4. M. Blaum, J. Brady, J. Bruck, and J. Menon. EVENODD: An efficient scheme for tolerating double disk failures in RAID architectures. IEEE Transactions on Computing, 44(1995)2, 192–202.

    Article  MATH  Google Scholar 

  5. M. Blaum, J. Brady, J. Bruck, J. Menon, and A. Vardy. The EVENODD code and its generalization: An efficient scheme for tolerating multiple disk failure in RAID architectures. in High Performance Mass Storage and Parallel I/O. John Wiley & Sons, Inc., 2002, 187–208.

  6. M. Blaum, J. Bruck, and A. Vardy. MDS array codes with independent parity symbols. IEEE Transactions on Information Theory, 42(1996)2, 529–542.

    Article  MATH  MathSciNet  Google Scholar 

  7. M. Blaumund and R. M. Roth. New array codes for multiple phased burst correction. IEEE Transactions on Information Theory, 39(1993)1, 66–77.

    Article  Google Scholar 

  8. L. Xu and J. Bruck. X-code. MDS array codes with optimal encoding. IEEE Transactions on Information Theory, 45(1999)1, 272–276.

    Article  MATH  MathSciNet  Google Scholar 

  9. L. Xu, V. Bohossian, J. Bruck, and D. Wagner. Low density MDS codes and factors of complete graphs. IEEE Transactions on Information Theory, 45(1999)1, 1817–1826.

    MATH  MathSciNet  Google Scholar 

  10. Wang Gang, Dong Sha-sha, Liu Xiao-guang, Lin Sheng, and Liu Jing. Construct double-erasure data layout using P1F. Acta Electronica Sinica, 34(2006) 12A, 2447–2450 (in Chinese). 王刚, 董沙沙, 刘小光, 林胜, 刘璟. 利用图的完全1-因子分解构造双容错数据布局. 电子学报, 34(2006) 12A, 2447–2450.

    Google Scholar 

  11. Wang Gang, Lin Sheng, Liu Xiaoguang, Xie Guangjun, and Liu Jing. Combinatorial constructions of multi-erasure-correcting codes with independent parity symbols for storage systems. IEEE PRDC’2007, Melbourne, Victoria, Australia, Dec. 2007, 61–68.

  12. Wang Gang, Xiaoguang Liu, Sheng Lin, Guangjun Xie, and Jing Liu. Constructing double-and tripe-erasure-correcting codes with high availability using mirroring and parity approaches. 13th International Conference on Parallel and Distributed Systems (ICPADS’07), Hsinchu, 2007, 1–8.

  13. Wang Gang, Lin Sheng, Liu Xiaoguang, Xie Guangjun, and Liu Jing. Generalization of RDP code using combinatorial method. Seventh IEEE International Symposium on Network Computing and Applications, Cambridge, MA, USA, 2008, 93–100.

  14. J. S. Plank. The RAID-6 liberation codes. 6th USENIX Conference on File and Storage Technologies, San Francisco, 2008, 97–110.

  15. Lisa Hellerstein, Garth A. Gibson, Richard M. Karp, Randy H. Katz, and David A. Patterson. Coding techniques for handling failures in large disk arrays. Algorithmica, 12(1994)2/3, 182–208.

    Article  MathSciNet  Google Scholar 

  16. I. M. Wanless. Perfect factorizations of bipartite graphs and latin squares without proper subrectangles. The Electronic Journal of Combinatorics, 6(1999)1, R9.

    MathSciNet  Google Scholar 

  17. Charles J. Colbourn and Jeffrey H. Dinitz. Handbook of Combinatorial Designs. 2nd ed (Discrete Mathematics and Its Applications). Chapman and Hall/CRC, November 2, 2006, 135–151.

  18. Cheng Huang and Lihao Xu. STAR: An efficient coding scheme for correcting triple storage node failures. 4th USENIX Conference on File and Storage Technologies, San Francisco, 2005, 197–210.

  19. J. L. Hafner. WEAVER codes: highly fault tolerant erasure codes for storage systems. In Proceedings of the 4th USENIX Conference on File and Storage Technologies, San Francisco, 2005, 211–224.

  20. J. L. Hafner. Hover erasure codes for disk arrays. International Conference on Dependable Systems and Networks, Philadelphia, PA, USA, 2006, 217–226.

Download references

Author information

Authors and Affiliations

  1. Nankai-Baidu Joint Laboratory, College of Information and Technical Science, Nankai University, Tianjin, 300071, China

    Sheng Lin, Gang Wang, Xiaoguang Liu & Jing Liu

Authors
  1. Sheng Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gang Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiaoguang Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jing Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sheng Lin.

Additional information

Supported in part by the National High Technology Research and Development Program of China (2008 AA01Z-401), the National Science Foundation of China (No. 60903028), Doctoral Fund of Ministry of Education of China (20070055054), and Science and Technology Development Plan of Tianjin (08JCYBJC13000).

Communication author: Lin Sheng, born in 1973, male, Doctor.

About this article

Cite this article

Lin, S., Wang, G., Liu, X. et al. A cascading Latin scheme to tolerate double disk failures in raid architectures. J. Electron.(China) 27, 243–249 (2010). https://doi.org/10.1007/s11767-010-0311-y

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11767-010-0311-y

Key words

CLC index

Search

Navigation