XORing Elephants: Novel Erasure Codes for Big Data
XORing Elephants: Novel Erasure Codes for Big Data
复制标题
DOI：
10.14778/2535573.2488339
复制
发表时间：
2013-01
期刊：
影响因子：
--
通讯作者：
M. Sathiamoorthy;Megasthenis Asteris;Dimitris Papailiopoulos;A. Dimakis;Ramkumar Vadali;Scott Chen;
中科院分区：
文献类型：
--
作者：
M. Sathiamoorthy;Megasthenis Asteris;Dimitris Papailiopoulos;A. Dimakis;Ramkumar Vadali;Scott Chen;
大型集群的分布式存储系统通常使用复制来提供可靠性。最近，擦除码被用来降低三次复制系统的大存储开销。里德-所罗门码是标准的设计选择，其高昂的维护成本通常被认为是为高存储效率和高可靠性而付出的不可避免的代价。本文展示了如何克服这一限制。我们提出了一种新的纠删码，与Reed-Solomon码相比，它是可有效修复的，并提供了更高的可靠性。我们的分析表明，我们的编码在最近发现的局部性和最小距离之间的折衷上是最优的。我们在Hadoop HDFS中实现了我们的新代码，并与当前部署的使用里德-所罗门代码的HDFS模块进行了比较。我们改进的HDFS实现显示修复磁盘I/O和修复网络流量减少了大约2倍。新编码方案的缺点是，与Reed-Solomon码相比，它需要多14%的存储空间，这一开销被显示为获得局部性的理论上最优的信息。由于新代码修复故障的速度更快，因此提供了更高的可靠性，与复制相比高出一个数量级。
Distributed storage systems for large clusters typically use replication to provide reliability. Recently, erasure codes have been used to reduce the large storage overhead of three-replicated systems. Reed-Solomon codes are the standard design choice and their high repair cost is often considered an unavoidable price to pay for high storage efficiency and high reliability. This paper shows how to overcome this limitation. We present a novel family of erasure codes that are efficiently repairable and offer higher reliability compared to Reed-Solomon codes. We show analytically that our codes are optimal on a recently identified tradeoff between locality and minimum distance. We implement our new codes in Hadoop HDFS and compare to a currently deployed HDFS module that uses Reed-Solomon codes. Our modified HDFS implementation shows a reduction of approximately 2× on the repair disk I/O and repair network traffic. The disadvantage of the new coding scheme is that it requires 14% more storage compared to Reed-Solomon codes, an overhead shown to be information theoretically optimal to obtain locality. Because the new codes repair failures faster, this provides higher reliability, which is orders of magnitude higher compared to replication.