基于稀疏纠删码矩阵的数据恢复方法与流程
本发明涉及分布式存储数据恢复,特别涉及一种基于稀疏纠删码矩阵的数据恢复方法以及一种计算机可读存储介质和一种计算机设备。
背景技术:
1、随着云计算、大数据以及分布式存储技术的不断发展,网络存储系统中的数据量呈现出爆炸式增长。为了在海量存储中保障数据的可靠性并降低冗余开销,纠删码(erasure coding, ec)技术被广泛应用于各种分布式存储系统(如ceph、hdfs等)。在现有的分布式存储系统中,纠删码是保障数据可靠性的核心技术。纠删码可以用极低的存储开销,换取极高的数据可靠性和容错能力。目前,存储系统中应用最广泛的纠删码方案主要包括里德-所罗门码(reed-solomon code, 简称rs码)和局部修复码(locally repairablecode, 简称lrc码)。然而,在实际的工业应用场景中,这两者都存在明显的性能瓶颈与技术痛点:
2、rs码虽然作为最常用的纠删码,拥有最小的存储冗余度,但其生成矩阵稠密,导致数据更新时计算开销大,且修复丢失数据时通常需要读取大量幸存数据块,网络和磁盘i/o带宽消耗高。
3、lrc码则相反,通过引入局部校验块,极大地增强了低阶擦除下的局部恢复能力,降低了单盘故障的修复带宽。但lrc码的设计本质上是以空间换时间,它需要生成额外的局部校验块,导致系统整体的空间冗余度大幅提高。此外,lrc码的参数配置复杂,缺乏良好的通用性。
4、这意味着,现有技术缺乏一种能够在保持低冗余度的同时,兼顾低修复带宽、低解码计算量及高效数据更新的编码方案。
技术实现思路
1、本发明旨在至少在一定程度上解决上述技术中的技术问题之一。为此,本发明的一个目的在于提出一种基于稀疏纠删码矩阵的数据恢复方法,通过构建特定的稀疏校验结构矩阵,在保证同等容错能力的前提下,显著降低数据修复时的读取块数、解码计算量以及数据更新时的编码开销。
2、本发明的第二个目的在于提出一种计算机可读存储介质。
3、本发明的第三个目的在于提出一种计算机设备。
4、为达到上述目的,本发明第一方面实施例提出了一种基于稀疏纠删码矩阵的数据恢复方法,该方法包括以下步骤:构建稀疏校验结构矩阵,其中,所述稀疏校验结构矩阵由0和1组成,每一列对应一个原始数据块,列中非零元素的数量为列权,每一行对应一个校验块,行中非零元素的数量为行权;当检测到数据块丢失时,定位丢失数据列集合;从可用校验行中贪心迭代筛选校验行,以最大化增秩和最小化行权为双重优化目标,生成满列秩的恢复子矩阵;根据所述恢复子矩阵对应的选中校验行在所述稀疏校验结构矩阵中确定最小化读取块列表,其中,所述最小化读取块列表包括选中校验行所依赖的所有存活数据块以及选中的校验块;根据所述最小化读取块列表进行解码,以恢复丢失数据块。
5、另外,根据本发明上述实施例提出的基于稀疏纠删码矩阵的数据恢复方法还可以具有如下附加的技术特征:
6、可选地,采用正交码构建规则构建对应的稀疏校验结构矩阵,其中,所述正交码构建规则包括设定目标容错能力,使每一列的列权均等于所述目标容错能力,每一行的行权最小化且均衡,并将非零元素均匀打散在稀疏校验结构矩阵中。
7、可选地,采用锁链码构建规则构建对应的稀疏校验结构矩阵,其中,所述锁链码构建规则包括设定目标容错能力,将所述稀疏校验结构矩阵划分为多个对角分布的局部密集区域,非对角互补区域置零,并在相邻局部区域交界处保留中间列的非零元素作为桥接列,同时保持每一列的列权恒等于所述目标容错能力。
8、可选地,构建所述稀疏校验结构矩阵后,在伽罗瓦域上对任意少于所述目标容错能力的丢失数据块数量的擦除模式进行秩检查,确认选中的可用校验行与丢失数据列构成的恢复子矩阵满列秩。
9、可选地,所述贪心迭代筛选校验行包括:初始化恢复子矩阵为空,当前秩为0;遍历每个可用校验行,在伽罗瓦域上评估引入校验行后能否带来秩的提升;优先选择能够带来实质增秩且行权最小的校验行,将其纳入恢复子矩阵并更新当前总秩;重复上述过程直至恢复子矩阵达到满列秩。
10、可选地,根据所述最小化读取块列表进行解码,以恢复丢失数据块,包括:在伽罗瓦域上根据所述最小化读取块列表构建已知向量,并对满列秩的恢复子矩阵执行矩阵求逆运算;将求得的逆矩阵与构建的已知向量在伽罗瓦域上进行乘加运算,以解出丢失数据列对应的原始数据块。
11、可选地,还包括将恢复的原始数据块写入目标节点,并更新集群元数据。
12、为达到上述目的,本发明第二方面实施例提出了一种计算机可读存储介质,其上存储有基于稀疏纠删码矩阵的数据恢复程序,该基于稀疏纠删码矩阵的数据恢复程序被处理器执行时实现如上述的基于稀疏纠删码矩阵的数据恢复方法。
13、为达到上述目的,本发明第三方面实施例提出了一种计算机设备,包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序,所述处理器执行所述程序时,实现如上述的基于稀疏纠删码矩阵的数据恢复方法。
14、根据上述基于稀疏纠删码矩阵的数据恢复方法,其有益效果在于:通过构建稀疏校验结构矩阵,并配合贪心迭代选行策略,使得系统在检测到数据块丢失时,能够从可用校验行中动态筛选出能带来秩的提升且依赖数据块最少的校验行参与恢复,从而生成最小化读取块列表,大幅减少数据恢复时需要从幸存节点读取的块数,显著降低网络传输带宽和磁盘i/o开销,同时由于选中的校验行行权极小,解码时参与运算的数据量也相应减少,进而降低了解码计算耗时,最终实现了在不增加存储冗余度的前提下,有效降低数据恢复时的修复带宽和解码计算量。
1.一种基于稀疏纠删码矩阵的数据恢复方法,其特征在于,包括以下步骤:
2.如权利要求1所述的基于稀疏纠删码矩阵的数据恢复方法,其特征在于,采用正交码构建规则构建对应的稀疏校验结构矩阵,其中,所述正交码构建规则包括设定目标容错能力,使每一列的列权均等于所述目标容错能力,每一行的行权最小化且均衡,并将非零元素均匀打散在稀疏校验结构矩阵中。
3.如权利要求1所述的基于稀疏纠删码矩阵的数据恢复方法,其特征在于,采用锁链码构建规则构建对应的稀疏校验结构矩阵,其中,所述锁链码构建规则包括设定目标容错能力,将所述稀疏校验结构矩阵划分为多个对角分布的局部密集区域,非对角互补区域置零,并在相邻局部区域交界处保留中间列的非零元素作为桥接列,同时保持每一列的列权恒等于所述目标容错能力。
4.根据权利要求2-3中任一项所述的基于稀疏纠删码矩阵的数据恢复方法,其特征在于,构建所述稀疏校验结构矩阵后,在伽罗瓦域上对任意少于所述目标容错能力的丢失数据块数量的擦除模式进行秩检查,确认选中的可用校验行与丢失数据列构成的恢复子矩阵满列秩。
5.根据权利要求2-3中任一项所述的基于稀疏纠删码矩阵的数据恢复方法,其特征在于,所述贪心迭代筛选校验行包括:
6.根据权利要求2-3中任一项所述的基于稀疏纠删码矩阵的数据恢复方法,其特征在于,根据所述最小化读取块列表进行解码,以恢复丢失数据块,包括:
7.根据权利要求1所述的基于稀疏纠删码矩阵的数据恢复方法,其特征在于,还包括将恢复的原始数据块写入目标节点,并更新集群元数据。
8.一种计算机可读存储介质,其特征在于,其上存储有基于稀疏纠删码矩阵的数据恢复程序,该基于稀疏纠删码矩阵的数据恢复程序被处理器执行时实现如权利要求1-7中任一项所述的基于稀疏纠删码矩阵的数据恢复方法。
9.一种计算机设备,包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序,其特征在于,所述处理器执行所述计算机程序时,实现如权利要求1-7中任一项所述的基于稀疏纠删码矩阵的数据恢复方法。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com