Locally repairable codes with multiple repair alternatives
Locally repairable codes with multiple repair alternatives
复制标题
DOI：
10.1109/isit.2013.6620355
复制
发表时间：
2013-02
期刊：
影响因子：
--
通讯作者：
Lluis Pamies-Juarez;H. Hollmann;F. Oggier
中科院分区：
文献类型：
--
作者：
Lluis Pamies-Juarez;H. Hollmann;F. Oggier
分布式存储系统需要冗余地存储数据，以提供一些容错并保证系统可靠性。已经提出了不同的编码技术来比传统复制方案更有效地提供所需的冗余。但是，与复制相比，编码技术可用于修复冗余的效率较低，因为它们需要从较大的存储节点中检索大量数据。为了减轻这些问题，最近的几项工作介绍了旨在最大程度地减少维修流量和每个维修涉及的节点的数量的本地维修代码。不幸的是，现有方法通常会导致代码，其中只有一个可以修复一块丢失数据的节点子集，从而将局部修复性限制为该子集中的节点的可用性。在本文中，我们提出了一个新的可当地维修代码系列，可以在每次维修的接触节点的数量与可以维修的不同子集的不同子集的数量之间进行不同的权衡。我们表明，每次维修的接触节点的数量略有增加，可以使用维修替代方案，从而增加了能够进行有效维修的可能性。最后，我们提出了PG-BLRC，这是一种具有多种修复替代方案的局部维修代码的明确结构，该代码是由部分几何形状构建的，尤其是通过广义四边形。我们展示了这些代码如何实现实用的长度和高率，同时每个维修需要少量节点，并提供多种维修替代方案。
Distributed storage systems need to store data redundantly in order to provide some fault-tolerance and guarantee system reliability. Different coding techniques have been proposed to provide the required redundancy more efficiently than traditional replication schemes. However, compared to replication, coding techniques are less efficient for repairing lost redundancy, as they require retrieval of larger amounts of data from larger subsets of storage nodes. To mitigate these problems, several recent works have presented locally repairable codes designed to minimize the repair traffic and the number of nodes involved per repair. Unfortunately, existing methods often lead to codes where there is only one subset of nodes able to repair a piece of lost data, limiting the local repairability to the availability of the nodes in this subset. In this paper, we present a new family of locally repairable codes that allows different trade-offs between the number of contacted nodes per repair, and the number of different subsets of nodes that enable this repair. We show that slightly increasing the number of contacted nodes per repair allows to have repair alternatives, which in turn increases the probability of being able to perform efficient repairs. Finally, we present pg-BLRC, an explicit construction of locally repairable codes with multiple repair alternatives, constructed from partial geometries, in particular from Generalized Quadrangles. We show how these codes can achieve practical lengths and high rates, while requiring a small number of nodes per repair, and providing multiple repair alternatives.