Erasure Codes for Storage Applications

``Erasure Codes for Storage Applications''

Tutorial given at FAST-2005: 4th Usenix Conference on File and Storage Technologies San Francisco, CA, December, 2005.

PDF of the presentation.

Tutorial Abstract

Who should attend: Anyone who deals with storage systems. This includes researchers, programmers, and managers of disk array systems, distributed storage systems, wide-area storage systems, and peer-to-peer storage systems. No hard-core math or programming knowledge is required. The goal is for the participants to come away with a basic understanding of how erasure codes may be used in storage systems, including all the available techniques and technologies, plus their performance tradeoffs and their complexity.

We all know that RAID Level 5, or parity coding, can protect storage systems composed of multiple disks from single disk failures. However, disk array systems are becoming so large that multiple disk failures occur with a high enough probability to become worrisome. With wide-area, distributed, and peer-to-peer storage systems, storage failures and network outages are everyday occurrences.

Unfortunately, solutions to tolerating multiple failures are not as standardized as RAID Level 5. The goal of this tutorial is for the participants to understand all of the options for tolerating multiple failures in storage systems.

Topics include:

Erasure coding technologies
- Standard Reed-Solomon coding, for tolerating any number of failures with optimal space overhead.
- Cauchy Reed-Solomon coding, which improves the performance of Reed-Solomon coding.
- Parity-Array coding, including EVENODD coding, plus other Horizontal and Vertical codes. These are parity-based codes that tolerate small numbers of failures with much better performance than Reed-Solomon codes.
- Low-Density, Parity-Check (LDPC) coding, including Tornado Codes. These are parity-based codes that tolerate large numbers of failures with much better performance than Reed-Solomon codes.
A comparison of the above codes, with a discussion of programming/implementation options.

PDF of the presentation.

Citation Information

Plain Text:

author          J. S. Plank
title           Erasure Codes for Storage Applications
howpublished    Tutorial Slides, presented at FAST-2005:
                4th Usenix Conference on File and Storage Technologies
address         San Francisco, CA
year            2005
where           http://web.eecs.utk.edu/~jplank/plank/papers/FAST-2005.html

Bibtex:

@MISC{p:05:ecsa,
        author = "J. S. Plank",
        title = "Erasure Codes for Storage Applications",
        howpublished = "Tutorial Slides, presented at {\em FAST-2005:
                4th Usenix Conference on File and Storage Technologies},
                \url{http://web.eecs.utk.edu/~jplank/plank/papers/FAST-2005.html}",
        address = "San Francisco, CA",
        year = "2005",
        where = "http://web.eecs.utk.edu/~jplank/plank/papers/FAST-2005.html"
}