Heuristics for Optimizing Matrix-Based Erasure Codes for Fault-Tolerant Storage Systems

James S. Plank, EECS Department, University of Tennessee.
Catherine D. Schuman, EECS Department, University of Tennessee.
B. Devin Robison, School of Computing, University of Utah.

Appearing in DSN-2012: The 42nd Annual IEEE/IFIP Internaltional Conference on Dependable Systems and Networks, Boston, MA, June, 2012.

PDF of the accepted submission. When I get a link, I'll point you to the final IEEE version on their web site.

Open Source Software of the Algorithms

Abstract

Large scale, archival and wide-area storage systems use erasure codes to protect users from losing data due to the inevitable failures that occur. All but the most basic erasure codes employ bit-matrices so that encoding and decoding may be effected solely with the bitwise exclusive-OR (XOR) operation. There are CPU savings that can result from strategically scheduling these XOR operations so that fewer XOR's are performed. It is an open problem to derive a schedule from a bit-matrix that minimizes the number of XOR operations.

We attack this open problem, deriving two new heuristics called Uber-CHRS and X-Sets to schedule encoding and decoding bit-matrices with reduced XOR operations. We evaluate these heuristics in a variety of realistic erasure coding settings and demonstrate that they are a significant improvement over previously published heuristics. We provide an open-source implementation of these heuristics so that practitioners may leverage our work.

IEEE Copyright Information

© 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Citation Information

Plain Text:

.inproceedings  psr:12:ho
author          J. S. Plank and C. D. Schuman and B. D. Robison
title           Heuristics for Optimizing Matrix-Based Erasure Codes
                for Fault-Tolerant Storage Systems
booktitle       DSN-2012: The International Conference on
                Dependable Systems and Networks
publisher       IEEE
address         Boston, MA
month           June
year            2012
where           http://web.eecs.utk.edu/~jplank/plank/papers/DSN-2012.html

Bibtex:

@INPROCEEDINGS{psr:12:ho,
	author = "J. S. Plank and C. D. Schuman and B. D. Robison",
	title = "Heuristics for Optimizing Matrix-Based Erasure Codes 
                for Fault-Tolerant Storage Systems",
	booktitle = "DSN-2012: The International Conference on
                Dependable Systems and Networks",
	publisher = "IEEE",
	address = "Boston, MA",
	month = "June",
	year = "2012",
	where = "http://web.eecs.utk.edu/~jplank/plank/papers/DSN-2012.html"
}