留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于Hadamard矩阵构造部分重复码

王静 孙伟 何亚锦 沈克勤 张鑫楠 刘向阳

王静, 孙伟, 何亚锦, 沈克勤, 张鑫楠, 刘向阳. 基于Hadamard矩阵构造部分重复码[J]. 电子科技大学学报, 2021, 50(2): 173-179. doi: 10.12178/1001-0548.2020028
引用本文: 王静, 孙伟, 何亚锦, 沈克勤, 张鑫楠, 刘向阳. 基于Hadamard矩阵构造部分重复码[J]. 电子科技大学学报, 2021, 50(2): 173-179. doi: 10.12178/1001-0548.2020028
WANG Jing, SUN Wei, HE Ya-jin, SHEN Ke-qin, ZHANG Xin-nan, LIU Xiang-yang. Construction of Fractional Repetition Codes Based on Hadamard Matrix[J]. Journal of University of Electronic Science and Technology of China, 2021, 50(2): 173-179. doi: 10.12178/1001-0548.2020028
Citation: WANG Jing, SUN Wei, HE Ya-jin, SHEN Ke-qin, ZHANG Xin-nan, LIU Xiang-yang. Construction of Fractional Repetition Codes Based on Hadamard Matrix[J]. Journal of University of Electronic Science and Technology of China, 2021, 50(2): 173-179. doi: 10.12178/1001-0548.2020028

基于Hadamard矩阵构造部分重复码

doi: 10.12178/1001-0548.2020028
基金项目: 国家自然科学基金(62001059);陕西省自然科学基金(2019JM-386);陕西省重点研发计划项目(2021GY-019)
详细信息
    作者简介:

    王静(1982 − ),女,博士,教授,主要从事网络编码及分布式存储编码等方面的研究

    通讯作者: 孙伟,E-mail:1277874948@qq.com
  • 中图分类号: TN911.2

Construction of Fractional Repetition Codes Based on Hadamard Matrix

  • 摘要: 针对分布式存储系统故障节点修复问题,提出一种部分重复(FR)码的构造算法。由Hadamard矩阵经过简单变换直接构造FR码。随后引入了分组思想,由8阶Hadamard矩阵构造分组FR码(HGFR),构造更加简洁直观,实现多故障节点在局部修复组内进行精确无编码修复。理论分析发现,与RS码和SRC简单再生码相比,设计的HGFR码在分布式存储系统节点发生故障时的修复局部性、修复复杂度和修复带宽开销都降低,且修复效率提高,减少了故障节点的修复时间。
  • 图  1  $ ({12},{9},{4})$FR码

    图  2  FR码的节点存储结构图

    图  3  分组FR码的节点存储结构图

    图  4  单节点故障时的修复带宽开销

    图  5  2个节点故障时的修复带宽开销

    图  6  单节点故障时的修复局部性

    表  1  3种编码方案的故障节点修复性能比较

    开销简单再生码RS码基于Hadamard矩阵的分组FR码
    节点存储开销$ \left( {f + 1} \right)M/k$M/k3M/k
    修复带宽开销单节点故障$ \left( {f + 1} \right)M/k $M3M/k
    两节点故障MM3M/k或6M/k
    修复局部性单节点故障2fk3
    两节点故障kk3或6
    下载: 导出CSV
  • [1] SIDDIQA A, KARIM A, GANI A. Big data storage technologies: A survey[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(8): 1040-1070.
    [2] WANG Yi-jie, XU Fang-liang, PEI Xiao-qiang. Research on erasure code-based fault-tolerant technology for distributed storage[J]. Chinese Journal of Computers, 2017, 40(1): 238-257.
    [3] DIMAKIS A G, GODFREY P B, WU Y, et al. Network coding for distributed storage systems[J]. IEEE Transactions on Information Theory, 2010, 56(9): 4539-4551. doi:  10.1109/TIT.2010.2054295
    [4] YANG Bin, TANG Xiao-hu, LI Jie. A Systematic piggybacking design for minimum storage regenerating codes[J]. IEEE Transactions on Information Theory, 2015, 61(11): 5779-5786. doi:  10.1109/TIT.2015.2472524
    [5] RRWAT A S, SILBERSTEIN N, KOYLUOGLU O O, et al. Optimal locally repairable codes with local minimum storage regeneration via rank-metric codes[C]//2013 Information Theory and Applications Workshop (ITA). [S.l.]: IEEE, 2013: 1-8.
    [6] PAPAILIOPOULOS D S, DIMAKIS A G. Locally repairable codes[C]//IEEE International Symposium on Information Theory (ISIT). [S.l.]: IEEE, 2012: 2771-2775.
    [7] KAMATH G M, PRAKASH N, LALITHA V, et al. Codes with local regeneration and erasure correction[J]. IEEE Transactions on Information Theory, 2014, 60(8): 4637-4660. doi:  10.1109/TIT.2014.2329872
    [8] RAWAT A S, KOYLUOGLU O O, SILBERSTEIN N, et al. Optimal locally repairable and secure codes for distributed storage systems[J]. IEEE Transactions on Information Theory, 2014, 60(1): 212-236. doi:  10.1109/TIT.2013.2288784
    [9] WANG Jing, YAN Zhi-yuan, LI K C, et al. Local codes with cooperative repair in distributed storage of cyber-physical-social systems[J]. IEEE Access, 2020, 8: 38622-38632. doi:  10.1109/ACCESS.2020.2975577
    [10] ROUAYHEB S E, RAMCHANDRAN K. Fractional repetition codes for repair in distributed storage systems[C]//Proceedings of 2010 48th Annual Allerton Conference on Communication, Control, and Computing. Allerton, IL, USA: IEEE, 2010: 1510-1517.
    [11] OLMEZ O, RAMAMOORTHY A. Repairable replication-based storage systems using resolvable designs[C]//Proceedings of 2012 50th Annual Allerton Conference on Communication, Control, and Computing. Monticello, IL, USA: IEEE, 2012: 1174-1181.
    [12] KOO J C, GILL J T. Scalable constructions of fractional repetition codes in distributed storage systems[C]// Proceedings of 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton). Monticello, IL, USA: IEEE, 2011: 1366-1373.
    [13] SILBERSTEIN N, ETZION T. Optimal fractional repetition codes based on graphs and designs[J]. IEEE Transactions on Information Theory, 2015, 61(8): 4164-4180. doi:  10.1109/TIT.2015.2442231
    [14] ZHU Bing, LI Hui, SHUM K W. Repair efficient storage codes via combinatorial configurations[C]//Proceedings of IEEE International Conference on Big Data. [S.l.]: IEEE, 2014: 80-81.
    [15] OLMEZ O, RAMAMOORTHY A. Fractional repetition codes with flexible repair from combinatorial designs[J]. IEEE Transactions on Information Theory, 2016, 62(4): 1565-1591. doi:  10.1109/TIT.2016.2531720
    [16] KIM Y S, PARK H, NO J S. Construction of new fractional repetition codes from relative difference sets with λ = 1[J]. Entropy, 2017, 19(10): 563. doi:  10.3390/e19100563
    [17] SANGIAMCHIT P, FAKCHAROENPHOL J. Practical differential privacy for location data aggregation using a hadamard matrix[C]//The 16th International Joint Conference on Computer Science and Software Engineering (JCSSE). Chonburi, Thailand: [s.n.], 2019: 79-84.
    [18] PETR L, KOCHEN S. Sets and Hadamard matrices[J]. Theoretical Computer Science, 2019, 800: 142-145. doi:  10.1016/j.tcs.2019.10.021
    [19] 秦小二, 胡双年, 姜灏, 等. 用Hadamard矩阵构造线性码[J]. 四川大学学报(自然科学版), 2015, 52(6): 1221-1224.

    QIN Xiao-er, HU Shuang-nian, JIANG Hao, et al. Constructing linear codes by Hadamard matrices[J]. Journal of Sichuan University (Natural Science Edition), 2015, 52(6): 1221-1224.
    [20] 朱兵, 李挥, 陈俊, 等. 基于可分组设计的部分重复码研究[J]. 通信学报, 2015, 36(2): 102-109.

    ZHU Bing, LI Hui, CHEN Jun, et al. Research on fractional repetition codes based on group divisible designs[J]. Journal on Communications, 2015, 36(2): 102-109.
    [21] SU Yi-Sheng. Pliable fractional repetition codes for distributed storage systems: Design and analysis[J]. IEEE Transactions on Communications, 2018, 66(6): 2359-2375. doi:  10.1109/TCOMM.2018.2799213
  • [1] 李虎泉, 郭世盛, 陈家辉, 崔国龙, 孔令讲.  分布式穿墙成像雷达空间配准方法 . 电子科技大学学报, 2023, 52(1): 30-37. doi: 10.12178/1001-0548.2022162
    [2] 王静, 李静辉, 杨佳蓉, 王娥.  基于RBIBD的最优局部修复码构造 . 电子科技大学学报, 2023, 52(3): 366-371. doi: 10.12178/1001-0548.2022158
    [3] 王静, 雷珂, 李家仪, 田松涛, 王相隆.  基于非均匀循环编码的分组修复码构造 . 电子科技大学学报, 2022, 51(1): 57-64. doi: 10.12178/1001-0548.2021013
    [4] 王静, 田松涛, 雷珂, 王相隆, 任亚倩.  基于Hadamard矩阵的最优局部修复码构造 . 电子科技大学学报, 2022, 51(6): 856-861. doi: 10.12178/1001-0548.2022037
    [5] 罗四维, 侯孟书, 牛新征, 吕孟婕.  基于免疫优化策略的副本放置算法 . 电子科技大学学报, 2017, 46(5): 741-746. doi: 10.3969/j.issn.1001-0548.2017.05.017
    [6] 包昕, 周磊砢, 何可, 游凌.  LDPC码稀疏校验矩阵的重建方法 . 电子科技大学学报, 2016, 45(2): 191-196.
    [7] 王聪, 张凤荔, 杨晓翔.  分布式环境下动态网络时延矩阵正则化重建 . 电子科技大学学报, 2014, 43(6): 923-928. doi: 10.3969/j.issn.1001-0548.2014.06.022
    [8] 胡学海, 王厚军, 黄建国.  分布式目标检测融合决策优化算法 . 电子科技大学学报, 2013, 42(3): 375-379. doi: 10.3969/j.issn.1001-0548.2013.03.011
    [9] 陈建英, 刘心松.  基于大规模分布式副本定位的分级索引压缩机制 . 电子科技大学学报, 2011, 40(4): 554-558. doi: 10.3969/j.issn.1001-0548.2011.04.016
    [10] 邓凯, 唐友喜.  分布式V-BLAST OFDM中存在多个频偏时的信号检测 . 电子科技大学学报, 2010, 39(4): 513-516. doi: 10.3969/j.issn.1001-0548.2010.04.008
    [11] 张海涛, 艾云峰.  一种分布式实时嵌入式系统的调度分析算法 . 电子科技大学学报, 2007, 36(3): 489-492.
    [12] 廖勇, 熊光泽, 陈旭东, 桑楠, 朱清新.  分布式实时嵌入式系统端到端性能确保 . 电子科技大学学报, 2007, 36(3): 541-544.
    [13] 戴江山, 李向阳, 张增军, 肖军模.  网络取证日志分布式安全管理 . 电子科技大学学报, 2007, 36(2): 235-238.
    [14] 李慧贤, 庞辽军, 程春田, 蔡皖东.  基于资源可用门限的分布式作业调度 . 电子科技大学学报, 2007, 36(2): 254-256,308.
    [15] 陈文宇, 桑楠, 屈鸿.  分布式对象调试中的事件模型 . 电子科技大学学报, 2005, 34(3): 377-380.
    [16] 杨挺, 罗光春.  分布式入侵检测系统修复机制 . 电子科技大学学报, 2005, 34(5): 634-637.
    [17] 王路, 袁宏春, 万里冰.  基于IP的点对点分布式VPN系统 . 电子科技大学学报, 2004, 33(1): 67-70.
    [18] 龚俊杰, 周建华, 周晓军, 邱琪, 白晓明.  分布式光纤温度传感器 . 电子科技大学学报, 2003, 32(3): 328-330.
    [19] 陈霖.  分布式入侵检测系统的设计 . 电子科技大学学报, 2002, 31(2): 188-191.
    [20] 王广彬, 黄廷祝.  局部双α对角占优矩阵 . 电子科技大学学报, 2001, 30(2): 199-202.
  • 加载中
图(6) / 表(1)
计量
  • 文章访问数:  4400
  • HTML全文浏览量:  1199
  • PDF下载量:  39
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-02-04
  • 修回日期:  2020-12-08
  • 网络出版日期:  2021-03-31
  • 刊出日期:  2021-03-22

基于Hadamard矩阵构造部分重复码

doi: 10.12178/1001-0548.2020028
    基金项目:  国家自然科学基金(62001059);陕西省自然科学基金(2019JM-386);陕西省重点研发计划项目(2021GY-019)
    作者简介:

    王静(1982 − ),女,博士,教授,主要从事网络编码及分布式存储编码等方面的研究

    通讯作者: 孙伟,E-mail:1277874948@qq.com
  • 中图分类号: TN911.2

摘要: 针对分布式存储系统故障节点修复问题,提出一种部分重复(FR)码的构造算法。由Hadamard矩阵经过简单变换直接构造FR码。随后引入了分组思想,由8阶Hadamard矩阵构造分组FR码(HGFR),构造更加简洁直观,实现多故障节点在局部修复组内进行精确无编码修复。理论分析发现,与RS码和SRC简单再生码相比,设计的HGFR码在分布式存储系统节点发生故障时的修复局部性、修复复杂度和修复带宽开销都降低,且修复效率提高,减少了故障节点的修复时间。

English Abstract

王静, 孙伟, 何亚锦, 沈克勤, 张鑫楠, 刘向阳. 基于Hadamard矩阵构造部分重复码[J]. 电子科技大学学报, 2021, 50(2): 173-179. doi: 10.12178/1001-0548.2020028
引用本文: 王静, 孙伟, 何亚锦, 沈克勤, 张鑫楠, 刘向阳. 基于Hadamard矩阵构造部分重复码[J]. 电子科技大学学报, 2021, 50(2): 173-179. doi: 10.12178/1001-0548.2020028
WANG Jing, SUN Wei, HE Ya-jin, SHEN Ke-qin, ZHANG Xin-nan, LIU Xiang-yang. Construction of Fractional Repetition Codes Based on Hadamard Matrix[J]. Journal of University of Electronic Science and Technology of China, 2021, 50(2): 173-179. doi: 10.12178/1001-0548.2020028
Citation: WANG Jing, SUN Wei, HE Ya-jin, SHEN Ke-qin, ZHANG Xin-nan, LIU Xiang-yang. Construction of Fractional Repetition Codes Based on Hadamard Matrix[J]. Journal of University of Electronic Science and Technology of China, 2021, 50(2): 173-179. doi: 10.12178/1001-0548.2020028
  • 近年来,由于数据量的快速上升,急需一种适宜的大数据存储系统。分布式存储系统由许多廉价磁盘组成,以其突出优势成为海量数据存储的有效系统,并被广泛部署和使用[1]。但在分布式存储系统中,节点容易发生故障,造成数据丢失。因此,故障节点的快速修复研究成为了分布式存储系统可靠性的重中之重。

    目前,分布式存储系统主要通过复制和纠删码策略来恢复节点故障。复制策略中三副本复制最为常见,故障节点修复具有较低的修复带宽开销,但需要存储大量的副本数据,存储开销较大。纠删码策略通过增加校验数据块来确保数据存储的可靠性,实现故障节点修复,且存储开销较小。虽然纠删码弥补了复制策略存储开销大的缺点,但是纠删码在修复故障节点时的修复带宽开销过大[2]

    鉴于复制和纠删码策略存在上述局限性,文献[3]将网络编码应用到分布式存储中,提出了再生码的概念,降低了故障节点的修复带宽开销。现在再生码研究重点在最小存储再生(minimum storage regeneration, MSR)码和最小带宽再生(minimum bandwidth regeneration, MBR)码[4-5]。再生码在修复故障节点时,需要连接大量存活节点以获得较低的修复带宽开销,且在修复过程中涉及有限域运算,计算复杂度相对较高。随后,文献[6]提出了局部修复码(locally repairable codes, LRC),使修复过程中需要连接的存活节点数较小,修复带宽开销较低,具有较好的修复局部性。将再生码和局部修复码结合,文献[7-8]提出了局部再生码的概念,达到存储−带宽开销的最佳折中。其中,基于系统MSR码的局部再生码,故障局部码可以通过相邻局部码进行协作修复[9]

    文献[10]提出了一种精确最小带宽再生码—部分重复(fractional repetition, FR)码,故障节点修复过程中的计算复杂度和修复带宽开销都有所降低,可以实现故障节点的精确无编码修复。近年来,许多研究人员对FR码进行了研究,文献[11]利用组合设计来构造FR码。随后,学者们又相继给出了几种基于组合结构的FR码构造,包括基于射影几何的FR码构造[12]、基于正则图的FR码构造[13]及基于可分组设计的FR码构造[14]

    现有FR码对于故障节点的修复,特别是多节点故障修复,其修复带宽开销和修复局部性较高,同时修复复杂度也较高。文献[13]提出了基于正则图构造FR码,随后文献[15]提出了运用网格构造FR码,但其都只能修复单节点故障。基于相对差集的FR码构造,能够修复分布式存储系统中的多节点故障,但是随着参数的增大,其节点存储容量和构造复杂度会随之增大[16]。而且常见的FR码构造随着系统规模和参数的增大,其节点数或节点容量增大,构造复杂度也会增大。本文提出基于Hadamard矩阵构造FR码,同时对其进行分组,运用8阶Hadamard矩阵提出了分组构造FR(Hadamard grouping fractional repetition, HGFR)码的一般算法,实现故障节点的局部修复。基于Hadamard矩阵分组构造FR码可以对多个节点故障进行快速精确无编码修复,有效降低了运算复杂度,同时运用了分组可以实现组内修复,复杂度进一步降低,实现故障节点的快速修复。理论分析发现,与RS码和SRC简单再生码相比,设计的FR码在分布式存储系统节点发生故障时,修复局部性、修复复杂度和修复带宽开销进一步降低,且修复效率提高,减少了故障节点的修复时间。

    • Hadamard矩阵是在工程技术上运用较多的一类矩阵,Hadamard矩阵是特殊的1、−1二元矩阵,具体定义如下:

      定义1[17-18] $n$阶方阵${{{\mathit{\boldsymbol{H}}}}_n}$,其元素为1或−1,并且满足:

      $$ {{{\mathit{\boldsymbol{H}}}}_n}{{{\mathit{\boldsymbol{H}}}}_n}^{\rm{T}} = n{{{\mathit{\boldsymbol{I}}}}_n} $$

      ${{{\mathit{\boldsymbol{H}}}}_n}$$n$阶Hadamard矩阵,其中${{{\mathit{\boldsymbol{I}}}}_n}$$n$阶单位矩阵。

      ${{{\mathit{\boldsymbol{H}}}}_n}$的第1行和第1列全是1,该${{{\mathit{\boldsymbol{H}}}}_n}$为Hadamard矩阵的标准型。以下所涉及的Hadamard矩阵${{{\mathit{\boldsymbol{H}}}}_n}$均为Hadamard标准型矩阵。

      Hadamard矩阵有如下一些性质:

      1) 将Hadamard矩阵的任意两行(或两列)交换,Hadamard矩阵的任意一行(或一列)的所有元素乘以−1,得到的矩阵仍然为Hadamard矩阵。

      2) 若${{{\mathit{\boldsymbol{H}}}}_n}$$n$阶Hadamard矩阵$(n > 2)$,则$n$是4的倍数。

      定义2 [19] 令:

      $$ {{{\mathit{\boldsymbol{K}}}}_n} = \frac{{{{{\mathit{\boldsymbol{J}}}}_n}{\rm{ + }}{{{\mathit{\boldsymbol{H}}}}_n}}}{2} $$

      其中${{{\mathit{\boldsymbol{J}}}}_n}$表示元素全为1的$n$阶矩阵,则得到$n$阶0-1矩阵${{{\mathit{\boldsymbol{K}}}}_n}$

      性质1 矩阵${{{\mathit{\boldsymbol{K}}}}_n}$中除第一行之外,每一行都有$n/{\rm{2}}$个1和$n/{\rm{2}}$个0。

    • FR码是在MBR码基础上提出的,典型的FR码由两部分组成,外部的MDS码和内部的重复码[20]

      定义3(FR码)[21] 分布式存储系统中参数为$(n,k,d)$的部分重复码$C = \left( {\eta ,M} \right)$,将数据块复制$\rho $倍(即重复度为$\rho $),特定地,$n$个子集的集合$M{\rm{ = }} $$ \{ {M_1},{M_2}, \cdots ,{M_n}\}$,子集中的元素都来自于集合$\eta {\rm{ = }} $$ \{ {\rm{1}},2, \cdots ,\theta \} $

      同时应满足以下两个条件:

      1)每个子集的大小均为$d$

      2) $\eta $中的每个元素属于$M$中的$\rho $个子集。

      上述定义中,数据块是经过MDS编码后的数据块。FR码的实质是将数据块复制$\rho $倍,然后将其排列到$n$个节点,同时使相同的数据块不出现在同一个节点上。图1为经过$({\rm{12}},{\rm{9}})$MDS编码后构成$ ({12},{9},{4})$FR码,其中$\rho $为2,数据复制2倍,每个节点存放4个编码数据块。

      FR码修复故障节点时直接从未失效节点中下载丢失的所需数据块,不进行编译码操作即可完成故障节点的迅速修复。FR码可实现精确无编码修复,修复带宽开销和修复时间较低,修复复杂度较小,同时能够容忍$\rho - 1$个节点故障。

      图  1  $ ({12},{9},{4})$FR码

    • 本节基于Hadamard矩阵构造FR码。首先选取一个$4t(t = 1,2,3, \cdots )$阶的Hadamard矩阵,对其进行简单的变换得到所需要的矩阵;再将矩阵与分布式存储节点和编码数据块相对应,矩阵的行代表存储节点,矩阵中不同的列表示不同的编码数据块。由Hadamard矩阵引出FR码一般性构造算法,其具体步骤如下:

      1) 将原始文件$M$分成$k$个原始数据块,这里$k \geqslant 2$。对该$k$个原始数据块采用$(n,k)$MDS编码$(n \geqslant k)$,得到$n$个编码数据块${c_{\rm{1}}}, \cdots ,{c_{k{\rm{ - }}1}},{c_k}, {c_{k + 1}}, \cdots ,{c_n}$$n$个编码数据块包括$k$个原始数据块和$n - k$个校验数据块;

      2) 取一个n+1阶标准型Hadamard矩阵${{{\mathit{\boldsymbol{H}}}}_{n + 1}}$,其中n+1=1,2,或n+1=0(mod4);

      3) 根据公式:

      $${{{\mathit{\boldsymbol{K'}}}}_{n + 1}} = \frac{{{{{\mathit{\boldsymbol{J}}}}_{n{\rm{ + 1}}}}{\rm{ + }}{{{\mathit{\boldsymbol{H}}}}_{n{\rm{ + 1}}}}}}{2}$$ (1)

      得到0-1矩阵${{{\mathit{\boldsymbol{K'}}}}_{n + 1}}(n \geqslant k)$,其中${{{\mathit{\boldsymbol{J}}}}_{n + 1}}$表示元素全为1的$n + 1$阶矩阵,${{{\mathit{\boldsymbol{H}}}}_{n + 1}}$为标准Hadamard矩阵,需满足$n + 1$为4的倍数;

      4) 对0-1矩阵${{{\mathit{\boldsymbol{K'}}}}_{n + 1}}$进行变换,将第一行第一列删去得到新矩阵${{{\mathit{\boldsymbol{K}}}}_n}$

      5) 通过矩阵${{{\mathit{\boldsymbol{K}}}}_n}$构造FR码,具体过程为:

      ① 矩阵${{{\mathit{\boldsymbol{K}}}}_n}$中每一行代表一个节点,用矩阵${{{\mathit{\boldsymbol{K}}}}_n}$中的第$i$行表示分布式存储系统中的第$i$个存储节点${N_i}$,共有$n$个存储节点,$i = 1,2, \cdots ,n$

      ② 由以下公式构造FR码:

      $${N_i} = \left\{ {j:{a_{ij}} = 1} \right\}$$ (2)

      式中,$j = 1,2, \cdots ,n$$i$表示第$i$个FR节点;${a_{ij}}$表示矩阵第i行第j列的值;${N_i}$表示FR码的存储节点。${N_i}$中包含的数据块为矩阵${{{\mathit{\boldsymbol{K}}}}_n}$中第$i$行所有1所对应的列数,将列数提取出即得到一个节点所存储的数据块,构成了所需FR码。

      采用上述FR码的一般性构造算法,在包含$n = {\rm{11}}$个存储节点的分布式存储系统中,构造FR码。选取如式(3)所示的12阶Hadamard矩阵,利用式(1)对该Hadamard矩阵进行变换,进一步得到所需的11阶矩阵${{{\mathit{\boldsymbol{K}}}}_{{\rm{11}}}}$,如式(4)所示。采用该${{{\mathit{\boldsymbol{K}}}}_{{\rm{11}}}}$矩阵,按照步骤5)构造得到FR码,该FR码的节点存储结构具体如图2所示。其中矩阵的行代表分布式存储系统中的存储节点,矩阵中不同的列表示不同的编码数据块,每个存储节点存储$d = {\rm{5}}$个编码块,编码块的重复度$\rho = {\rm{5}}$

      $$ {{{\mathit{\boldsymbol{H}}}}_{12}} = \left[ \begin{array}{l} 1\quad1\quad1\quad1\quad1\quad1\quad1\quad1\quad1\quad1\quad1\quad1\\ 1 \,- 1\quad1 \,- 1\quad1\quad1\quad1 \,- 1\,- 1 \,- 1\quad1 \,- 1\\ 1 \,- 1 \,- 1\quad1 \,- 1\quad1\quad1\quad1 \,- 1 \,- 1 \,- 1\quad1\\ 1\quad1 \,- 1 \,- 1\quad1 \,- 1\quad1\quad1\quad1 \,- 1 \,- 1 \,- 1\\ 1 \,- 1\quad1 \,- 1 \,- 1\quad1 \,- 1\quad1\quad1\quad1 \,- 1 \,- 1\\ 1 \,- 1 \,- 1\quad1 \,- 1 \,- 1\quad1 \,- 1\quad1\quad1\quad1 \,- 1\\ 1 \,- 1 \,- 1 \,- 1\quad1 \,- 1\, - 1\quad1 \,- 1\quad1\quad1\quad1\\ 1\quad1\, - 1 \,- 1\, - 1\quad1 \,- 1 \,- 1\quad1 \,- 1\quad1\quad1\\ 1\quad1\quad1 \,- 1 \,- 1 \,- 1\quad1 \,- 1 \,- 1\quad1 \,- 1\quad1\\ 1\quad1\quad1\quad1\, - 1 \,- 1 \,- 1\quad1 \,- 1 \,- 1\quad1 \,- 1\\ 1 \,- 1\quad1\quad1\quad1 \,- 1 \,- 1 \,- 1\quad1 \,- 1 \,- 1\quad1\\ 1\quad1 \,- 1\quad1\quad1\quad1 \,- 1 \,- 1\quad1\quad1 \,- 1 \,- 1 \end{array} \right] $$ (3)
      $$ {{{\mathit{\boldsymbol{K}}}}_{11}}=\left[ \begin{array}{l} 0\quad1\quad0\quad1\quad1\quad1\quad0\quad0\quad0\quad1\quad0\\ 0\quad0\quad1\quad0\quad1\quad1\quad1\quad0\quad0\quad0\quad1\\ 1\quad0\quad0\quad1\quad0\quad1\quad1\quad1\quad0\quad0\quad0\\ 0\quad1\quad0\quad0\quad1\quad0\quad1\quad1\quad1\quad0\quad0\\ 0\quad0\quad1\quad0\quad0\quad1\quad0\quad1\quad1\quad1\quad0\\ 0\quad0\quad0\quad1\quad0\quad0\quad1\quad0\quad1\quad1\quad1\\ 1\quad0\quad0\quad0\quad1\quad0\quad0\quad1\quad0\quad1\quad1\\ 1\quad1\quad0\quad0\quad0\quad1\quad0\quad0\quad1\quad0\quad1\\ 1\quad1\quad1\quad0\quad0\quad0\quad1\quad0\quad0\quad1\quad0\\ 0\quad1\quad1\quad1\quad0\quad0\quad0\quad1\quad0\quad0\quad1\\ 1\quad0\quad1\quad1\quad1\quad0\quad0\quad0\quad1\quad0\quad0 \end{array} \right] $$ (4)

      图  2  FR码的节点存储结构图

      当一个节点发生故障时,可以运用其他节点对故障节点进行修复,在其他节点中找到并下载含有故障节点的数据块,故障节点即完成了修复,且该过程不需要进行编码译码操作。对于图2中的FR码,若节点${N_1}$发生故障,可以分别从存活节点${N_3}$中下载数据块4和6,从存活节点${N_4}$中下载数据块2和5,以及存活节点${N_5}$中下载数据块10,实现节点${N_1}$的修复。对于两个节点发生故障的情况,与一个节点故障修复的方法相同。

    • 运用Hadamard矩阵构造FR码发现,随着Hadamard矩阵阶数的增加,FR码的重复度和节点存储容量也会随之增加,从而导致存储开销也相应地增加,故障节点修复性能受到一定限制。为此,本节引入分组构造的思想构造部分重复码。当Hadamard矩阵的阶数为12时构造的FR码的重复度为5,重复度较大;当阶数为8时FR码的重复度降为3,更满足实际存储需求,所以本文利用8阶标准Hadamard矩阵构造分组FR码。

    • 对分布式存储系统节点进行分组,并利用8阶Hadamard矩阵构造分组FR码(hadamard grouping fractional repetition, HGFR)。分组FR码的具体构造算法如下:

      1) 取一个8阶标准Hadamard矩阵${{{\mathit{\boldsymbol{H}}}}_{\rm{8}}}$;由上节构造部分重复码方法的步骤1)~步骤4)得到新矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$,并利用新矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码;

      2) 记原始文件M包含$s$个原始数据块,将原始数据块进行分组,得到$t$个局部修复组,每组分配$k{\rm{ = 5}}$个原始数据块。包含以下几种情况:

      ① 如果$s$可以被$k{\rm{ = 5}}$整除,即$s = tk$,此时每个局部修复组内首先进行(7, 5)MDS码编码,然后采用步骤3)中的矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码;

      ② 如果$s$不能被$k{\rm{ = 5}}$整除,即$s = tk + m$m=1,前t−1个局部修复组采用(7, 5)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码,第t个局部修复组采用(7,6)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码;

      ③ 若$s = tk + m$$m = {\rm{2}}$,前$t - {\rm{2}}$个局部修复组采用(7, 5)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码,第t−1个和第t个局部修复组采用(7, 6)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码;

      ④ 若$s = tk + m$$m = 3$或者4时,前t−1个局部修复组采用(7,5)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码,第t个局部修复组采用(7,m)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码。

      以包含$s = 11$个数据块的原始文件为例,$s = 2k + 1$,这里m=1,满足情况②。第1个局部修复组采用(7,5)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码,第2个局部修复组采用(7,6)MDS码以及矩阵${{{\mathit{\boldsymbol{K}}}}_{\rm{7}}}$构造FR码。构造的分组FR码如图3所示。

      图  3  分组FR码的节点存储结构图

    • 下面考虑分布式存储系统采用基于Hadamard矩阵的分组FR码,其故障节点的修复。考虑到3个以上节点同时故障的概率很低,本文只考虑分布式存储系统中1个、2个或者3个节点故障,且在同一个或者不同局部修复组内的情况。具体故障节点修复过程如下:

      1)当分布式存储系统只有1个节点故障,此时只需考虑在一个局部修复组内对单一故障节点进行修复。具体地,在该局部修复组内其他存活节点中找到含有故障节点的数据块,直接下载故障节点丢失的数据块,即可完成故障节点修复,该过程不需要进行编码操作。如图2所示,如第一个局部修复组中第一个节点发生故障,可以下载节点${N_{\rm{2}}}$${N_{\rm{4}}}$${N_{\rm{6}}}$中的2、4和6这3个数据块完成第一个节点的修复。

      2)当分布式存储系统中有2个节点同时发生故障时,存在以下两种情况:① 2个故障节点在同一局部修复组内,可以从剩余的5个存活节点中下载故障节点所含有的数据块,完成故障节点的快速修复;② 发生故障的2个节点不在同一局部修复组,则需要在两个修复组内分别对其组内的故障节点进行修复。在图2中,如节点${N_{\rm{2}}}$和节点${N_{{\rm{10}}}}$发生故障导致数据块丢失,可以在第一个局部修复组内从节点${N_{\rm{1}}}$${N_{\rm{4}}}$${N_{\rm{5}}}$中分别下载数据块4、1和5完成节点${N_{\rm{2}}}$的修复,在第二个局部修复组内从节点${N_{\rm{9}}}$${N_{{\rm{11}}}}$${N_{{\rm{13}}}}$下载数据块11、10和14完成节点${N_{{\rm{10}}}}$的快速修复。

      3)当分布式存储系统中有3个节点同时发生故障,存在以下两种情况:①发生故障的3个节点不在同一局部修复组,该情况下的故障节点修复与前面两种修复过程完全一样,只需直接从局部修复组中下载所需的数据块;②发生故障的3个节点在同一局部修复组中,如果3个故障节点中没有同时含有同一个数据块,则可以直接从其他存活节点中下载丢失的数据块,完成故障节点的修复;否则,需要运用MDS编码进行修复。如图2中节点${N_{\rm{1}}}$${N_{\rm{2}}}$${N_{\rm{3}}}$发生故障,剩余存活节点无法直接修复,需要从存活节点下载数据块进行MDS编码修复数据块4,即完成故障节点${N_{\rm{1}}}$${N_{\rm{2}}}$${N_{\rm{3}}}$的精确修复。

    • 本节对提出的基于Hadamard矩阵构造分组FR码进行性能分析,修复带宽开销、修复局部性、修复复杂度为分析的主要性能,并与SRC简单再生码以及RS码进行比较。取文件大小$M{\rm{ = }} $$ 1\;000\;{\rm{Mb}}$,SRC简单再生码的子文件数$f = 4$

    • 当节点发生故障时,修复故障节点被下载的数据量大小称为修复带宽开销。在分布式存储系统中,原文件大小为$M$,当发生单节点故障时,若采用$(n,k)$RS码,则需要下载全部的原文件来修复故障节点,所以采用$(n,k)$RS码修复单节点故障的修复带宽开销为文件大小$M$;对于$(n,k,f)$SRC简单再生码,每个节点存储$f + 1$个数据块,每个数据块大小为${M / {fk}}$,当一个数据块发生故障,$f$个数据块被下载进行修复,所以1个节点发生故障的修复带宽开销为${{(f + 1)M} / k}$;如果采用基于Hadamard矩阵的分组FR码,每个数据块大小为${M / k}$,每个节点含有3个数据块,所以基于Hadamard矩阵的分组FR码的单节点故障的修复带宽开销为${\rm{3}}M/{\rm{}}k$。单节点故障的3种编码方式修复带宽开销对比如图4所示。

      图  4  单节点故障时的修复带宽开销

      当2个节点发生故障时,若采用$(n,k)$RS码,仍然需要下载全部的原文件来修复故障节点,所以$(n,k)$RS码修复2个故障节点的修复带宽开销仍为$M$;对于$(n,k,f)$SRC简单再生码,如果2个故障节点数大于$f{\rm{ - 1}}$,则2个节点发生故障的修复带宽开销为${\rm{2}}{{(f + 1)M}/ k}$,如果2个故障节点数小于$f{\rm{ - 1}}$,需要先恢复原文件,所以修复带宽开销为$M$,这里$f$=4,所以2个节点故障时,SRC简单再生码的修复带宽开销为M;如果采用基于Hadamard矩阵的分组FR码,2个故障节点在同一修复组时,修复带宽开销为${\rm{3}}M/{\rm{}}k$,不在同一修复组时,修复带宽开销为${\rm{6}}M/{\rm{}}k$。修复带宽开销对比如图5所示。

      图  5  2个节点故障时的修复带宽开销

      图4图5可以看出,基于Hadamard矩阵的分组FR码,单节点和两节点故障时的修复带宽开销性能明显优于RS码和SRC简单再生码,且在图5中RS码和SRC简单再生码由于修复带宽开销一样,所以曲线重合。

    • 修复局部性是指故障节点修复过程中需要连接的存活节点数目,即修复过程中的磁盘I/O开销。首先对于单节点失效,简单再生码修复时需要连接$2f$个存活节点,所以局部修复性为$2f$;RS码发生单节点故障时,需要连接$k$个节点恢复原文件修复故障节点,所以RS码修复局部性为$k$;基于Hadamard矩阵的分组FR码,连接3个未发生故障的节点来恢复单个节点故障,所以其修复局部性为3。单节点故障时的修复局部性对比如图6所示。

      对于2个节点发生故障,SRC简单再生码需要先恢复原文件才可以修复故障节点,所以SRC简单再生码的修复局部性为$k$;对于RS码,仍然需要恢复原文件,所以修复2个节点的修复局部性也为$k$;基于Hadamard矩阵的分组FR码,分两种情况:1) 如果一个修复组中发生2个节点故障,从3个未失效节点中下载所需数据,修复局部性为3;2) 2个故障节点不在同一个局部修复组内,其修复两个故障节点需要连接6个存活节点,修复局部性为6。

      图  6  单节点故障时的修复局部性

      修复故障节点时,可以看出基于Hadamard矩阵的分组FR码的修复局部性,优于简单再生码和RS码的修复局部性。

    • 本文提出的基于Hadamard矩阵的分组FR码,当发生节点故障时,可以直接从其他存活节点下载数据块进行修复,无需进行编码运算。对于RS码修复故障节点需要先恢复原文件,之后再编码生成所需要的数据块,编码数据块由$k$个数据块在有限域$GF(q)$上运算得到。所以RS码在修复单节点故障时需要${k^2} + k$次有限域乘法运算和${k^2} - 1$次有限域加法运算。对于SRC简单再生码,其修复一个故障节点需要进行$(f - 1)(f + 1)$次异或运算。可以看出,本文构造的FR码修复复杂度明显低于RS码和SRC简单再生码的修复复杂度,可以快速修复故障节点,修复时间减少。

      表1给出了分布式存储系统中,RS码、简单再生码和基于Hadamard矩阵的分组FR码分别在修复带宽开销、修复局部性及节点存储开销三方面的性能比较。从表1可以看出,基于Hadamard矩阵的分组FR码其修复局部性和带宽开销较低。而且,基于Hadamard矩阵的分组FR码在修复节点故障时可以实现精确无编码修复,运算复杂度较低,修复时间减少,可靠性提高。

      表 1  3种编码方案的故障节点修复性能比较

      开销简单再生码RS码基于Hadamard矩阵的分组FR码
      节点存储开销$ \left( {f + 1} \right)M/k$M/k3M/k
      修复带宽开销单节点故障$ \left( {f + 1} \right)M/k $M3M/k
      两节点故障MM3M/k或6M/k
      修复局部性单节点故障2fk3
      两节点故障kk3或6
    • 现有传统编码方式对于故障节点的修复,特别是对多故障节点的修复,其修复带宽开销和修复局部性能受限,同时修复复杂度较高。为此,本文提出了基于Hadamard矩阵的FR码,同时对其进行分组,运用8阶Hadamard矩阵提出了分组FR码的一般性构造算法。理论分析发现,基于Hadamard矩阵的分组FR码可以对多故障节点进行快速精确无编码修复,有效降低了运算复杂度,同时运用了分组可以实现组内修复,复杂度进一步降低。与RS码和SRC简单再生码相比,发生故障时的修复局部性、修复复杂度和修复带宽开销进一步降低,且修复效率提高,减少了故障节点的修复时间。

参考文献 (21)

目录

    /

    返回文章
    返回