Irregular Array Codes with Arbitrary Access Sets for Geo-Distributed Storage
Irregular Array Codes with Arbitrary Access Sets for Geo-Distributed Storage
复制标题
DOI：
10.1109/isit45174.2021.9517809
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Francisco Maturana;K. V. Rashmi
中科院分区：
文献类型：
--
作者：
Francisco Maturana;K. V. Rashmi
分布式存储系统通常使用擦除码来提供对节点故障的容错。删除码将消息编码成由几个符号组成的码字，然后在系统中的节点之间分配这些码字。最大距离可分(MDS)$[n，k]$标量码在实践中是常用的，它具有这样的性质：$n$节点中的$k$的任何子集都足以对消息进行解码。然而，在地理分布式存储系统等应用程序中，不需要从其中许多子集进行解码。在这篇文章中，我们研究了这样的码，其中只需要某些节点的子集，称为访问集，就可以满足可译码。我们的分析集中在两个具有实际重要性的指标上：更新成本和存储开销。为了最小化这些度量，我们证明了使用非规则阵列码是必要的。我们推导出作为所需访问集的函数的更新代价的下界，并且证明了它是可实现的。现有工作为存储开销提供了一个可实现的下限。虽然这两个下限都是可以单独实现的，但我们证明了它们不是总体上可以同时实现的。由于广域网络带宽成本高于存储成本，我们将重点放在更新成本最低的代码(称为MUC)上。最后，我们得到了MUC码存储开销的一个下界，并通过随机化构造证明了满足这个下界的MUC码的存在性。因此，我们的结果表明，通过根据所需的访问集定制代码设计，可以显著节省更新成本和存储开销。
Distributed storage systems typically use erasure codes to provide tolerance against node failures. An erasure code encodes a message into a codeword made up of several symbols, which are then distributed among nodes in the system. Maximum distance separable (MDS) $[n, k]$ scalar codes are commonly used in practice, which have the property that any subset of $k$ out of $n$ nodes is enough to decode the message. However, in applications such as geo-distributed storage systems, decodability from many of these subsets is unnecessary. In this paper, we study codes where only certain subsets of nodes, named access sets, are required to satisfy decodability. Our analysis focuses on two metrics of practical importance: update cost and storage overhead. For minimizing these metrics, we show that it is necessary to employ irregular array codes. We derive a lower bound on update cost as a function of the required access sets and show that it is achievable. Existing work provides an achievable lower bound on storage overhead. While both lower bounds are individually achievable, we show that they are not simultaneously achievable in general. Due to the premium in wide-area network bandwidth cost over storage cost, we focus on codes with minimum update cost (termed MUC). Finally, we derive a lower bound on the storage overhead of MUC codes and show the existence of MUC codes meeting this lower bound via a randomized construction. Our results thus show that it is possible to achieve significant savings in update cost and storage overhead by tailoring the design of codes to the required access sets.