Bandwidth Cost of Code Conversions in Distributed Storage: Fundamental Limits and Optimal Constructions
Bandwidth Cost of Code Conversions in Distributed Storage: Fundamental Limits and Optimal Constructions
复制标题
DOI：
10.1109/tit.2023.3265512
复制
发表时间：
2020-08
影响因子：
2.5
通讯作者：
Student Member Ieee Francisco Maturana;M. I. K. V. Rashmi
中科院分区：
文献类型：
--
作者：
Student Member Ieee Francisco Maturana;M. I. K. V. Rashmi
Erasure code已经成为分布式存储系统中不可缺少的一部分，作为一种工具，可以在设备故障不断的情况下保证数据的可靠性和持久性。在这样的系统中，在有限域$\mathbb {F}_{q}$上的$[n, k]$代码将$\mathbb {F}_{q}$中的$k$消息符号编码为$\mathbb {F}_{q}$中的$n$码字符号，然后存储在系统中的$n$不同节点上。最近的研究表明，通过调整$n$和$k$以适应设备故障率的变化，可以显著节省存储空间。这样的调优需要代码转换：将初始$[n^{I}, k^{I}]$代码下已经编码的数据转换为最终$[n^{F}, k^{F}]$代码下的等效数据的过程。默认的转换方法是在新代码下重新编码数据，这给系统资源带来了很大的负担。可转换代码是最近提出的一类用于实现资源高效转换的代码。可转换代码的现有工作主要集中在最小化访问成本，即在转换期间访问的代码符号的数量。带宽（对应于读取和传输的数据量）是转换期间需要优化的另一个重要资源。本文研究了码转换过程中带宽的基本限制，并给出了最优带宽转换码的结构。首先，我们利用具有可变容量边的网络信息流图对代码转换问题进行建模。其次，重点研究了MDS码和一个重要的参数域，即合并域，推导了转换带宽的严格下界。导出的边界表明，与默认方法相比，即使在已经表明不能降低访问成本的区域，转换带宽也可以显着减少。第三，我们提出了一种新的MDS可转换码结构，该结构符合所提出的下界，因此在转换过程中带宽最优。
Erasure codes have become an integral part of distributed storage systems as a tool for providing data reliability and durability under the constant threat of device failures. In such systems, an $[n, k]$ code over a finite field $\mathbb {F}_{q}$ encodes $k$ message symbols from $\mathbb {F}_{q}$ into $n$ codeword symbols from $\mathbb {F}_{q}$ which are then stored on $n$ different nodes in the system. Recent work has shown that significant savings in storage space can be obtained by tuning $n$ and $k$ to variations in device failure rates. Such a tuning necessitates code conversion: the process of converting already encoded data under an initial $[n^{ I}, k^{ I}]$ code to its equivalent under a final $[n^{ F}, k^{ F}]$ code. The default approach to conversion is to re- encode the data under the new code, which places significant burden on system resources. Convertible codes are a recently proposed class of codes for enabling resource-efficient conversions. Existing work on convertible codes has focused on minimizing the access cost, i.e., the number of code symbols accessed during conversion. Bandwidth, which corresponds to the amount of data read and transferred, is another important resource to optimize during conversions. In this paper, we study the fundamental limits on bandwidth used during code conversion and present constructions for bandwidth-optimal convertible codes. First, we model the code conversion problem using network information flow graphs with variable capacity edges. Second, focusing on MDS codes and an important parameter regime called the merge regime, we derive tight lower bounds on conversion bandwidth. The derived bounds show that conversion bandwidth can be significantly reduced as compared to the default approach even in regions where it has been shown that access cost cannot be reduced. Third, we present a new construction for MDS convertible codes which matches the proposed lower bound and is thus bandwidth-optimal during conversion.