Locality and Availability in Distributed Storage
Locality and Availability in Distributed Storage
复制标题
DOI：
10.1109/tit.2016.2524510
复制
发表时间：
2014-02
影响因子：
2.5
通讯作者：
A. Rawat;Dimitris Papailiopoulos;A. Dimakis;S. Vishwanath
中科院分区：
文献类型：
--
作者：
A. Rawat;Dimitris Papailiopoulos;A. Dimakis;S. Vishwanath
本文研究了码中信息符号的可用性问题：如果一个系统码中的每个信息（系统）符号都可以从t个不相交的码符号组中重构出来，且每个码符号组的长度至多为r，则称该系统码为具有（r，t）-可用性的码。本文表明，它是可能的构造代码，可以支持一个缩放数量的并行读取，同时保持率是一个任意高的常数。它进一步表明，这是可能的最小汉明距离任意接近单例界。本文还提出了一个界限，展示了速率，最小汉明距离和可用性参数之间的权衡。我们的代码符合上述的界限，它们的构造依赖于某些组合结构。可分解设计提供了一种实现这些所需组合结构的方法。本文提出的两种构造需要的字段大小，这是线性和指数的代码长度，分别。从实际的角度来看，我们的代码与涉及热数据的分布式存储应用相关，即，这些信息经常被多个进程并行访问。
This paper studies the problem of information symbol availability in codes: we refer to a systematic code as code with (r, t)-availability if every information (systematic) symbol can be reconstructed from t disjoint groups of other code symbols, each of the sizes at most r. This paper shows that it is possible to construct codes that can support a scaling number of parallel reads while keeping the rate to be an arbitrarily high constant. It further shows that this is possible with the minimum Hamming distance arbitrarily close to the Singleton bound. This paper also presents a bound demonstrating a tradeoff between rate, minimum Hamming distance, and availability parameters. Our codes match the aforementioned bound, and their constructions rely on certain combinatorial structures. Resolvable designs provide one way to realize these required combinatorial structures. The two constructions presented in this paper require field sizes, which are linear and exponential in the code length, respectively. From a practical standpoint, our codes are relevant for distributed storage applications involving hot data, i.e., the information, which is frequently accessed by multiple processes in parallel.