-
随着互联网的快速发展,各种数据出现爆炸式增长,分布式存储系统得到了广泛应用[1]。在分布式存储系统中,通常采取数据冗余技术,最简单的方式是复制[2],这需要非常高的存储开销。纠删码技术可降低存储开销[3],但是当存储节点故障时,修复成本远高于复制。为了解决上述问题,文献[4]提出了局部修复码(locally repairable codes, LRCs)的概念。LRCs具有很好的局部性,在修复过程中通过访问少量的节点来降低修复成本。目前对LRCs的研究主要集中在参数研究和其构造方面。
已有不少文献对LRCs的参数边界进行了研究。文献[5]提出的修复局部性
$r$ 是衡量修复效率的重要指标,对于信息位具有局部性$r$ 的LRCs给出了码的最小距离的上界。文献[6-9]给出了最小距离达到此上界的 LRCs的相关构造。为了在多个节点故障的情况下实现局部恢复,文献[10]提出了$(r,t)$ 局部性的概念,并且证明了信息位具有$(r,t)$ 局部性的单校验LRCs最小距离的上界,如果码的最小距离达到该上界,则该码是最小距离最优的码。文献[11]提出并证明了具有$t$ 个大小为$r$ 的不相交修复集的$(r,t)$ -LRCs的码率上界。文献[12]通过将文献[5]提出的修复局部性进行推广,构造了可以同时恢复两个Erasure(删余)的LRCs,证明了可用性$t = 2$ 时的最优码率。除以上研究文献外,目前也有大量文献对LRCs的构造进行研究。文献[11]基于
$t$ 个二进制$(r + 1, r)$ 奇偶校验码的直积构造了具有$(r,t)$ 局部性的二元局部修复码(binary locally repairable codes, BLRCs),构造出的BLRCs虽然能够实现任意的$(r,t)$ 局部性,但是其码率较小。文献[13]利用有限域上的迹函数构造了一类循环$(r,t)$ LRCs,构造出的BLRCs达到了最优最小距离,但是此构造方法只能构造特定参数的BLRCs且码率较小。文献[14]采用有限平面LDPC码和阵列LDPC码构造了具有$(r,t)$ 局部性的BLRCs,构造出的BLRCs虽然达到了最优最小距离,但是参数条件限制较多且码率较小。文献[15]对文献[14]中的构造进行了扩展,进一步构造了最小距离更大的最优单校验$(r,t)$ LRCs,但其码率仍然不高。文献[16]基于$(r,t)$ 超图构造的BLRCs的最小距离达到了最优最小距离界,但是构造出的BLRCs具有很大的参数限制。文献[17]采用矩阵迭代的方法构造了具有$(r,t)$ 局部性的BLRCs,但是这种构造方法只能构造可用性$t$ =2的BLRCs,限制了可用性的参数选择。文献[18]基于随机函数提出了一种新的局部性$r$ =2且具有不均匀可用性的BLRCs,但是构造出的BLRCs码率较低。为解决上述LRCs构造中存在的参数限制较多且码率较低的问题,本文基于可分解均衡不完全区组设计(resolvable balanced incomplete block design, RBIBD),提出了信息位具有
$(r,t)$ 局部性的单校验最优BLRCs的构造方法。首先利用方阵循环移位进行RBIBD设计,运用RBIBD若干平行类中的区组与有限集中元素的对应关系构造关联矩阵,基于关联矩阵构造BLRCs。构造的BLRCs达到了最优最小距离界,是最小距离最优的LRCs;特别地,当可用性$t = 2$ 时,该BLRCs达到了文献[12]提出的最优码率边界,同时也是码率最优的LRCs。与文献[15]提出的单校验BLRCs相比,构造的BLRCs在码率上表现得更优并且参数选择更加灵活,和文献[11]提出的直积码相比,该构造在码率上表现得也更优。 -
推论1由生成矩阵
${\boldsymbol{G}} = \left[ {\left. {{{\boldsymbol{I}}_{{p^2}}}} \right|{\boldsymbol{M}}} \right]$ 构造得到的单校验${(n,k,r,t)_i}$ BLRCs是最小距离最优的BLRCs,且码的最小距离$d = t + 1$ 。证明:由于构造的单校验
${(n,k,r,t)_i}$ BLRCs信息位具有局部性$ r $ 和可用性$ t $ ,根据式(1),最小距离应满足$d \geqslant t + 1$ 。又因为构造的BLRCs的参数满足$n = {p^2} + pq,k = {p^2},r = p,t = q$ ,将这些参数代入式(2),可得:因为
$q = t$ ,所以构造出的BLRCs的最小距离$d = t + 1$ ,达到了式(2)中的最小距离边界,则该码是最小距离最优的BLRCs,证毕。 -
本文构造的BLRCs的码率为:
将本文构造的BLRCs与文献[15]基于阵列LDPC码构造的BLRCs、文献[11]基于直积码构造的BLRCs以及基于矩阵迭代构造的BLRCs[17]进行比较,4种BLRCs的构造参数如表1所示。
构造方法 $n$ $k$ $R$ 本文构造的BLRCs ${r^2}+rt$ ${r^2}$ $\dfrac{r}{ {r + t} }$ 基于阵列LDPC码构造的BLRCs ${r^2}+rt+1$ ${r^2}$ $\dfrac{ { {r^2} } }{ { {r^2} + rt + 1} }$ 基于直积码构造的BLRCs $(r+1)^t$ ${r^t}$ ${\left( {\dfrac{r}{ {r + 1} } } \right)^t}$ 基于矩阵迭代构造的BLRCs $\dfrac{ {(r + 1)(r + 2)} }{2}$ $\dfrac{ {(r - 1)(r + 2)} }{2}$ $\dfrac{ {r - 1} }{ {r + 1} }$ 由表1可知,当这些码的局部性都取
$(r,t)$ 时,有$\dfrac{r}{{r + t}} > \dfrac{{{r^2}}}{{{r^2} + rt + 1}}$ ,即本文构造的BLRCs的码率高于基于阵列LDPC码构造的BLRCs。当$t > 1$ 时,可知${\left( {1 + \dfrac{1}{r}} \right)^t} > 1 + \dfrac{t}{r}$ ,因此基于直积码构造的BLRCs的码率${\left( {\dfrac{r}{{r + 1}}} \right)^t} = \dfrac{1}{{{{\left( {1 + \dfrac{1}{r}} \right)}^t}}} < \dfrac{1}{{1 + \dfrac{t}{r}}} = \dfrac{r}{{r + t}}$ 。经分析可知,当局部性相同且$t > 1$ 时,本文构造的BLRCs的码率总高于基于阵列LDPC码构造的BLRCs和基于直积码构造的BLRCs。此外,当可用性$t = 2$ 时,基于矩阵迭代构造的BLRCs的码率$R = \dfrac{{r - 1}}{{r + 1}} < \dfrac{r}{{r + 2}}$ ,即本文构造的BLRCs的码率高于基于矩阵迭代构造的BLRCs。图1给出了当局部性
$r = 11$ 时,码率$R$ 随可用性$t$ 的变化曲线。可以看出,当局部性一定,随着可用性$t$ 的增加,码率降低。当可用性$t$ 取相同值时,本文构造的BLRCs的码率高于基于阵列LDPC码构造的BLRCs、基于直积码构造的BLRCs以及基于矩阵迭代构造的BLRCs,尽管基于阵列LDPC码构造的BLRCs比本文构造的BLRCs在码率上小得不是很多,但是其参数限制较大,可用性$t$ 只能取偶数。这3种BLRCs的码率都没有达到文献[11]提出的码率上界。进一步,在可用性
$t = 2$ 时,本文构造的BLRCs的码率$R = \dfrac{r}{{r + 2}}$ ,达到了文献[12]提出的码率上界,是码率最优的码。图2给出了可用性$t = 2$ 时,码率$R$ 随局部性$r$ 的变化曲线。可以看出,当可用性$t = 2$ ,随着局部性$r$ 的增大,3种码的码率同时呈增大的趋势;当局部性$r$ 取相同值时,本文构造的BLRCs的码率高于基于阵列LDPC码构造的BLRCs、基于直积码构造的BLRCs以及基于矩阵迭代构造的BLRCs。此外,由不同的构造方法构造出的BLRCs的参数可取范围也不尽相同,灵活的参数选择可以为系统设计提供便利。文献[13]基于迹函数构造的BLRCs需满足
$t = r + 1$ ,其码率$R = \dfrac{{{2^r} - 1}}{{{2^{r + 1}} - 1}} < \dfrac{1}{2}$ ,小于本文构造的BLRCs的码率。文献[14]基于仿射平面仅能构造局部性$r$ 与可用性$t$ 相等的BLRCs,并且其码率$R$ 仅为$\dfrac{1}{2}$ 。文献[16]基于$(r,t)$ 超图构造具有$(r,t)$ 局部性的BLRCs,但是$(r,t)$ 超图存在的必要条件是超图的顶点数$v \geqslant t(r - 1) + 1$ 并且$r|vt$ ,使得构造出的BLRCs具有极大的参数限制。文献[18]基于随机函数仅能构造局部性$r = 2$ 的BLRCs,构造出的BLRCs主要是针对特定参数的系统,且其码率$R = \dfrac{1}{{k - 1}}$ ,当信息位长度$k$ 越大时,码率$R$ 越低。本文基于RBIBD构造的BLRCs不仅参数选择更加灵活,而且在码率上表现得更优。
Construction of Optimal Locally Repairable Codes Based on RBIBD
doi: 10.12178/1001-0548.2022158
- Received Date: 2022-05-24
- Rev Recd Date: 2022-10-09
- Available Online: 2023-05-26
- Publish Date: 2023-05-28
-
Key words:
- distributed storage system /
- locally repairable code /
- minimum distance /
- resolvable balanced incomplete block design
Abstract: With the rapid growth of data, the requirements of the reliability and effectiveness for distributed storage systems are increasing. Locally repairable codes (LRCs) have better locality, which can effectively realize the reliable and efficient storage of massive data in distributed storage system. It has become a research hotspot to construct locally repairable codes with (r, t) locality. Therefore, this paper proposes a construction method of optimal locally repairable codes based on resolvable balanced incomplete block design (RBIBD), which can construct binary optimal single parity LRCs with (r, t) locality of information symbols. The performance analyses show that, the constructed LRCs reach the minimum distance bound, and compared with the LRCs proposed by Xia et al., the LRCs proposed in this paper perform better in code rate. In particular, when the availability t=2, the LRCs is also the code with the optimal code rate.
Citation: | WANG Jing, LI Jinghui, YANG Jiarong, WANG E. Construction of Optimal Locally Repairable Codes Based on RBIBD[J]. Journal of University of Electronic Science and Technology of China, 2023, 52(3): 366-371. doi: 10.12178/1001-0548.2022158 |