Optimal locally repairable codes and connections to matroid theory
Optimal locally repairable codes and connections to matroid theory
复制标题
DOI：
10.1109/isit.2013.6620540
复制
发表时间：
2013-01
期刊：
影响因子：
--
通讯作者：
Itzhak Tamo;Dimitris Papailiopoulos;A. Dimakis
中科院分区：
文献类型：
--
作者：
Itzhak Tamo;Dimitris Papailiopoulos;A. Dimakis
PETABYTE规模的分布式存储系统目前正在过渡到擦除代码以实现更高的存储效率。诸如Reed-Solomon之类的经典代码对于分布式环境而言是高度最佳的，因为它们在一次性失败事件中的高架。本地维修代码（LRC）构成了一个新的修复级代码系列。特别是，LRCS最大程度地减少了参与单个节点维修的节点的数量，在此过程中它们会产生较小的网络流量。两个大规模的分布式存储系统已经实现了不同类型的LRC：Windows Azure存储和Facebook使用的Hadoop分布式文件系统RAID。最近发现了LRC的基本界限，即给定代码局部性的最佳距离，但很少有明确的结构。在这项工作中，我们提出了一个明确而易于实施最佳LRC的构建，以供以前通过存在结果建立的代码参数。为了分析代码的最优性，我们在代码生成器矩阵表示的矩阵上得出了新的结果。
Petabyte-scale distributed storage systems are currently transitioning to erasure codes to achieve higher storage efficiency. Classical codes like Reed-Solomon are highly suboptimal for distributed environments due to their high overhead in single-failure events. Locally Repairable Codes (LRCs) form a new family of codes that are repair efficient. In particular, LRCs minimize the number of nodes participating in single node repairs during which they generate small network traffic. Two large-scale distributed storage systems have already implemented different types of LRCs: Windows Azure Storage and the Hadoop Distributed File System RAID used by Facebook. The fundamental bounds for LRCs, namely the best possible distance for a given code locality, were recently discovered, but few explicit constructions exist. In this work, we present an explicit and simple to implement construction of optimal LRCs, for code parameters previously established by existence results. For the analysis of the optimality of our code, we derive a new result on the matroid represented by the code's generator matrix.