2010 · 81 citations · 54 references
ComputingComputer EngineeringComputer ScienceFault ToleranceFault-tolerant SystemsStorage SystemsData RedundancyError-correcting CodesFault-tolerant Storage SystemsReliable Storage SystemsStorage Fault ToleranceStorage ReliabilityDisk Failure RecoveryMds CodesParity-based StorageRaid SystemsRegenerating CodesStorage Erasure CodingStorage Recovery MechanismsXor-based Codes
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.
54
Low-density parity-check codes
Robert G. Gallager · IEEE Transactions on Information Theory · 1962 · 10.6K citations · Full text