Paper Info
Title
Flat XOR-based erasure codes in storage systems: Constructions, efficient recovery, and tradeoffs
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.
Year
DOI
Venue
2010
10.1109/MSST.2010.5496983
Mass Storage Systems and Technologies
Keywords
DocType
ISSN
erasure code,flat xor-codes,stark tradeoff,efficient recovery,storage system,raid extension,flat xor-code,recovery schedule,enumerates recovery equation,cost-benefit tradeoff gap,failed disk,recovery equation,fault tolerant,differential equations,raid,fault tolerance,scheduling algorithm,hamming distance,construction industry,redundancy
Conference
2160-195X
ISBN
Citations 
PageRank 
978-1-4244-7153-9
55
2.13
References 
Authors
31
3
Name
Order
Citations
PageRank
Kevin M. Greenan145122.59
Xiaozhou Li21648.55
Jay J. Wylie368544.29