基于Hadamard矩阵构造部分重复码.docx
版权申诉
186 浏览量
2022-12-15
14:26:47
上传
评论
收藏 288KB DOCX 举报
近年来，由于数据量的快速上升，急需一种适宜的大数据存储系统。分布式存储系统
由许多廉价磁盘组成，以其突出优势成为海量数据存储的有效系统，并被广泛部署和使用
[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 码在分布式存储系统节点发生故障时，修复局部性、
修复复杂度和修复带宽开销进一步降低，且修复效率提高，减少了故障节点的修复时间。
剩余11页未读，继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3652
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
VIP享7折，此内容立减5.97元 开通VIP
