4th USENIX Conference on File and Storage TechnologiesAbstract
Pp. 197210 of the Proceedings
STAR : An Efficient Coding Scheme for
Correcting Triple Storage Node Failures
Cheng Huang, Microsoft Research; Lihao Xu, Wayne State University
Proper data placement schemes based on erasure correcting
code are one of the most important components for a
highly available data storage system. For such schemes,
low decoding complexity for correcting (or recovering)
storage node failures is essential for practical systems.
In this paper, we describe a new coding scheme, which
we call the STAR code, for correcting triple storage node
failures (erasures). The STAR code is an extension of
the double-erasure-correcting EVENODD code, and a
modification of the generalized triple-erasure-correcting
EVENODD code. The STAR code is an MDS code, and
thus is optimal in terms of node failure recovery capability
for a given data redundancy. We provide detailed
STAR code's decoding algorithms for correcting various
triple node failures. We show that the decoding complexity
of the STAR code is much lower than those of
the existing comparable codes, thus the STAR code is
practically very meaningful for storage systems that need
- View the full text of this paper in HTML and PDF.
Until December 2006, you will need your USENIX membership identification in order to access the full papers. The Proceedings are published as a collective work, © 2005 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.