Check out the new USENIX Web site.

USENIX Home . About USENIX . Events . membership . Publications . Students
4th USENIX Conference on File and Storage Technologies—Abstract

Pp. 197–210 of the Proceedings

STAR : An Efficient Coding Scheme for Correcting Triple Storage Node Failures

Cheng Huang, Microsoft Research; Lihao Xu, Wayne State University

Abstract

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 higher reliability.
  • View the full text of this paper in HTML and PDF.
    Click here if you have forgotten your password 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.
To become a USENIX Member, please see our Membership Information.

?Need help? Use our Contacts page.

Last changed: 8 Dec. 2005 rc
Technical Program
FAST '05 Home
USENIX home