An Efficient XOR-Scheduling Algorithm for Erasure Codes Encoding

Jianqiang Luo, Computer Science Department, Wayne State University,
Lihao Xu, Computer Science Department, Wayne State University,
James S. Plank, EECS Department, University of Tennessee.

Appearing in DSN-2009: The 39th Annual IEEE/IFIP Internaltional Conference on Dependable Systems and Networks, Lisbon, Portugal, June, 2009.

PDF of the paper.

Abstract

In large storage systems, it is crucial to protect data from loss due to failures. Erasure codes lay the foundation of this protection, enabling systems to reconstruct lost data when components fail. Erasure codes can however impose significant performance overhead in two core operations: encoding, where coding information is calculated from newly written data, and decoding, where data is reconstructed after failures.

This paper focuses on improving the performance of encoding, the more frequent operation. It does so by scheduling the operations of XOR-based erasure codes to optimize their use of cache memory. We call the technique XOR-scheduling and demonstrate how it applies to a wide variety of existing erasure codes. We conduct a performance evaluation of scheduling these codes on a variety of processors and show that XOR-scheduling significantly improves upon the traditional approach. Hence, we believe that XOR-scheduling has great potential to have wide impact in practical storage systems.

Citation Information

Plain Text:

.inproceedings  lxp:09:aex
author          J. Luo and L. Xu and J. S. Plank
title           An Efficient {XOR}-{S}cheduling Algorithm for Erasure Codes Encoding
booktitle       DSN-2009: The International Conference on Dependable Systems and Networks
publisher       IEEE
address         Lisbon, Portugal
month           June
year            2009
where           http://web.eecs.utk.edu/~jplank/plank/papers/DSN-2009.html

Bibtex:

@INPROCEEDINGS{lxp:09:aex,
        author = "J. Luo and L. Xu and J. S. Plank",
        title = "An Efficient {XOR}-{S}cheduling Algorithm for Erasure Codes Encoding",
        booktitle = "DSN-2009: The International Conference on Dependable Systems and Networks",
        publisher = "IEEE",
        address = "Lisbon, Portugal",
        month = "June",
        year = "2009",
        where = "http://web.eecs.utk.edu/~jplank/plank/papers/DSN-2009.html"
}