Heuristics for Reducing the Number of XOR's in Erasure Coding Systems

Опубликовано 17 августа 2016, 22:30

As a community, storage systems practitioners are just beginning to scratch the surface with regard to leveraging all that erasure codes have to offer. The higher RAID levels (4-6, 10 and 01) use very limited erasure codes to protect systems from small numbers of failures. More advanced systems are being built to satisfy the goals of large-scale storage, archival storage and widescale data distribution, and these systems make use of erasure codes that are far richer than those required by RAID. The best performing erasure codes rely on the bitwise exclusive-or operation (XOR) and express their encoding and decoding operations using binary (bit) matrices. There is a great deal of flexibility when generating a schedule of XOR operations from a bit matrix, and it is an open problem to generate optimally performing schedules from a matrix. This paper explores this open problem, focusing on techniques to convert encoding and decoding bit matrices into schedules of XOR operations that perform well. We develop two heuristics, named Uber- CSHR and X-Sets, and evaluate them on a variety of realistic erasure- coding settings. The results show that these techniques significantly improve the performance of encoding and decoding compared to the current state of the art.