利索能及
我要发布
收藏
专利号: 2021106175527
申请人: 成都信息工程大学
专利类型:发明专利
专利状态:已下证
更新日期:2025-10-14
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种单节点故障快速修复纠删码的构造方法,其特征在于,包括:在分布式存储系统中单节点纠删码发生故障时,判断发生故障的单节点纠删码是分组内的任一原始数据块、任一横向局部校验块或分组外的任一横向全局校验块;

当判断发生故障的单节点纠删码是分组内的任一原始数据块或任一横向局部校验块时,确定出错原始数据块或横向局部校验块所在的条带集,并利用所述条带集中丢失块所在的校验链中的其他原始数据块、横向局部校验块和纵向局部校验块,对所述出错原始数据块或横向局部校验块的数据进行快速修复;

当判断发生故障的单节点纠删码是分组外的任一横向全局校验块时,确定出错横向全局校验块所对应的多个分组,并利用每个分组内的横向局部校验块,对所述出错横向全局校验块的数据进行快速修复。

2.根据权利要求1所述的方法,其特征在于,所述利用所述条带集中丢失块所在的校验链中的其他原始数据块、横向局部校验块和纵向局部校验块,对所述出错原始数据块或横向局部校验块的数据进行快速修复包括:从所述条带集中读取所述出错原始数据块或横向局部校验块所在校验链中未丢失的其他原始数据块、横向局部校验块和纵向局部校验块;

将所述其他原始数据块、横向局部校验块和纵向局部校验块进行异或解码处理,得到所述出错原始数据块或横向局部校验块的数据。

3.根据权利要求1所述的方法,其特征在于,所述利用每个分组内的横向局部校验块,对所述出错横向全局校验块的数据进行快速修复包括:从所述每个分组内读取与所述出错横向全局校验块相对应的横向局部校验块;

将所述每个分组内读取的横向局部校验块进行异或解码处理,得到所述出错横向全局校验块的数据。

4.根据权利要求1所述的方法,其特征在于,在分布式存储系统中单节点纠删码发生故障之前,还包括:

将分布式存储系统中的x原始数据节点进行分组和条带划分处理,得到包含y个第一条带的分组;

通过对所述分组内的每个包含原始数据块的第一条带进行横向编码处理,得到每个第一条带的横向局部校验块和横向全局校验块,并将所述横向局部校验块和所述横向全局校验块添加到对应的第一条带内,得到包含原始数据块、横向局部校验块和横向全局校验块的第二条带;

根据用户设定的条带集大小,将所有包含原始数据块、横向局部校验块和横向全局校验块的第二条带进行条带集划分处理,得到包含多个第二条带的条带集;

通过分别对所述条带集中的每个第二条带进行数据块旋转移位处理,得到第三条带,并生成包含所述第三条带的条带集;

通过对所述分组中每个包含所述第三条带的条带集进行纵向异或编码处理,得到多个纵向校验块,并根据所述多个纵向校验块构建一个新的纵向局部校验条带,并将所述纵向局部校验条带存放到所述条带集中。

5.根据权利要求4所述的方法,其特征在于,所述通过对所述分组内的每个包含原始数据块的第一条带进行横向编码处理,得到所述每个第一条带的横向局部校验块和横向全局校验块包括:

通过对所述分组内的每个包含原始数据块的第一条带进行组内横向编码处理,得到所述每个第一条带的横向局部校验块;

通过对所述每个第一条带的横向局部校验块进行横向异或编码处理,得到所述每个第一条带的横向全局校验块。

6.根据权利要求5所述的方法,其特征在于,所述通过对所述分组内的每个包含原始数据块的第一条带进行组内横向编码处理,得到所述每个第一条带的横向局部校验块包括:通过对所述分组内每个第一条带的k个原始数据块按纠错码的参数设置RS(k,r)进行编码,生成r个横向局部校验块;

其中,所述k是指原始数据块个数;所述r是指校验块个数;所述k和r均为正整数,且r

7.根据权利要求6所述的方法,其特征在于,当横向全局校验个数与每个分组内横向局部校验个数r相同时,所述通过对所述每个第一条带的横向局部校验块进行横向异或编码处理,得到所述每个第一条带的横向全局校验块包括:将所有分组的第一条带的第一个横向局部校验块进行横向异或编码处理,得到所述每个第一条带的第一个横向全局校验块;

将所有分组的第一条带的第二个横向局部校验块进行横向异或编码处理,得到所述每个第一条带的第二个横向全局校验块;

依次遍历所有分组的第一条带的横向局部校验块,进行横向异或处理,得到所属分组第一条带的所有横向全局校验块;

依次遍历所有分组的每个条带的横向局部校验块,进行横向异或处理,得到所有每个条带的横向全局校验块。

8.根据权利要求4所述的方法,其特征在于,所述通过分别对所述条带集中的每个第二条带进行数据块旋转移位处理,得到第三条带,并生成包含所述第三条带的条带集包括:按照数据块旋转移位公式对所述每个条带集中的每个第二条带进行数据块旋转移位处理,使所述每个条带集内的原始数据块和横向局部校验块均匀分布在每个纠删码节点内;

其中,所述数据块旋转移位公式包括:其中,所述 是指数据块旋转移位后的横向坐标和纵向坐标;所述m是指数据块的原始横向坐标;所述n是指数据块的原始纵向坐标;所述 是指数据块的纵向坐标由原始的横纵坐标之和 对组长 取模。

9.根据权利要求4所述的方法,其特征在于,所述通过对所述分组中每个包含所述第三条带的条带集进行纵向异或编码处理,得到多个纵向校验块包括:按照纵向异或编码公式对所述分组中每个包含所述第三条带的条带集进行纵向异或编码处理,得到多个纵向校验块;

其中,所述纵向异或编码公式包括:其中, 是指分组内局部校验块,所述S是每个分组内局部校验块的横坐标;所述j是每个分组内局部校验块的纵坐标;所述m是原始数据块的横坐标,所述 是组长,是原始数据块的纵坐标。