Flat XOR-based erasure codes in storage systems: Constructions, efficient recovery, and tradeoffs
Authors:
- 1 May 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 2160195X,p. 1-14
Abstract
Large scale storage systems require multi-disk fault tolerant erasure codes. Replication and RAID extensions that protect against two- and three-disk failures offer a stark tradeoff between how much data must be stored, and how much data must be read to recover a failed disk. Flat XOR-codes-erasure codes in which parity disks are calculated as the XOR of some subset of data disks-offer a tradeoff between these extremes. In this paper, we describe constructions of two novel flat XOR-code, Stepped Combination and HD-Combination codes. We describe an algorithm for flat XOR-codes that enumerates recovery equations, i.e., sets of disks that can recover a failed disk. We also describe two algorithms for flat XOR-codes that generate recovery schedules, i.e., sets of recovery equations that can be used in concert to achieve efficient recovery. Finally, we analyze the key storage properties of many flat XOR-codes and of MDS codes such as replication and RAID 6 to show the cost-benefit tradeoff gap that flat XOR-codes can fill.Keywords
This publication has 39 references indexed in Scilit:
- The Raid-6 Liber8Tion CodeThe International Journal of High Performance Computing Applications, 2009
- Hard-disk drivesCommunications of the ACM, 2009
- PARAIDACM Transactions on Storage, 2007
- An analysis of latent sector errors in disk drivesACM SIGMETRICS Performance Evaluation Review, 2007
- Network codingACM SIGCOMM Computer Communication Review, 2006
- X-code: MDS array codes with optimal encodingIEEE Transactions on Information Theory, 1999
- MDS array codes with independent parity symbolsIEEE Transactions on Information Theory, 1996
- Efficient placement of parity and data to tolerate two disk failures in disk array systemsIEEE Transactions on Parallel and Distributed Systems, 1995
- EVENODD: an efficient scheme for tolerating double disk failures in RAID architecturesIEEE Transactions on Computers, 1995
- Polynomial Codes Over Certain Finite FieldsJournal of the Society for Industrial and Applied Mathematics, 1960