分布式存储系统中基于两级映射的冗余转换方法及装置

本发明属于电子数据，更进一步地涉及分布式存储一种分布式存储系统中基于两级映射的冗余转换方法及装置。本发明可用于解决纠删码存储系统存储冗余转换中跨机架传输流量开销大以及机架间负载不均衡的问题。

背景技术：

1、随着数据规模的持续增长，分布式存储系统已成为云计算、大数据分析和人工智能等应用的重要基础设施。通过将数据分布在多个存储节点上，分布式存储系统能够实现容量和带宽的横向扩展，并利用多副本或纠删码等冗余机制提升数据可靠性和系统可用性。在实际应用中，数据访问模式、可靠性需求和系统资源状态会随时间动态变化。单一冗余编码方式难以同时满足高性能、低成本和高可靠性的要求。因此，编码冗余转换技术被用于根据数据生命周期和业务需求动态调整冗余策略。例如，热数据可采用多副本方式以降低访问延迟，冷数据可转换为纠删码方式以降低存储成本；系统也可以在不同纠删码参数之间转换，以适应不同可靠性和性能需求。传统方法通常需要先解码恢复原始数据，再重新编码生成目标编码数据，导致大量磁盘 i/o、网络传输和计算开销。部分优化方法虽然能够降低转换过程中的数据传输量或计算量，但通常依赖特定编码类型、编码参数或转换场景，通用性不足。同时，编码转换往往需要在系统在线运行过程中完成，容易与前台业务竞争资源，并可能引发负载不均衡、转换延迟增加以及服务质量下降等问题。

2、厦门大学在其申请的专利文献“跨机架感知的纠删码存储系统均衡冗余转换方法及装置”（申请日 2023-06-02 申请号 202310648438.x授权公告号 cn 116909475 b）中公开了一种跨机架感知的纠删码存储系统均衡冗余转换方法及装置。该方法包括：制定机架间平衡的数据布局和机架内聚合的校验块布局，并在冗余转换过程中维护该布局，以减少数据块重定位和校验块更新所导致的跨机架传输流量；设计数据块选择和奇偶校验块增量更新策略，以进一步减少校验块更新的跨机架传输流量；提出了一种启发式算法，挑选条带组并行进行冗余转换，以平衡各机架的流量负载。该方法在抑制冗余转换导致的跨机架传输流量的同时平衡机架之间的负载，能够缩短完成冗余转换的时间。拉伸里德-所罗门（srs）编码（stretched reed-solomon codes）在首次转换过程中消除了数据重定位开销，而弹性里德-所罗门码（ers）elastic reed-solomon codes通过扩展编码矩阵进一步降低了奇偶校验更新流量。但是，这些方法仍然存在的不足之处是，一方面，该方法主要从机架级布局维护和启发式并行调度角度优化冗余转换过程，未进一步结合节点级块放置与校验更新任务分散机制，因而在节点层面仍可能出现块分布不均衡和局部热点问题；另一方面，该方法主要面向当前轮冗余转换进行优化，其启发式条带组选择结果依赖于候选条带集合，难以保证连续多轮转换过程中各轮之间始终保持兼容的条带合并关系，从而导致经过前一轮转换后的布局难以继续满足后续转换所需的结构条件，原有局部性优势无法自然延续至后续轮次，因而在连续转换场景下仍容易产生较大的跨机架传输流量。由此可见，现有技术尚难同时兼顾连续多轮冗余转换中的低跨机架传输开销以及机架级、节点级的负载均衡。

技术实现思路

1、本发明的目的是针对上述现有技术存在的不足，提出一种分布式存储系统中的冗余编码数据转换方法及装置，旨在解决现有技术存在的在连续多轮转换场景下跨机架传输流量较大、转换过程中的机架级和节点级负载难以均衡以及转换后布局难以兼顾后续轮次兼容性的问题。

2、实现本发明目的的技术思路是，由于本发明采用基于条带集合校验重叠度序列的递归边界结构构造技术，能够预先确定不同轮次条带冗余转换边界处的数据组重叠关系，并使当前轮转换后的布局直接满足下一轮合并输入要求，因此可保证连续多轮转换中的布局兼容性，并减少后续轮次的数据迁移开销。由于本发明采用基于正交数组构造的机架级映射数组与节点级映射数组进行机架级与节点级确定性映射，能够在满足机架感知放置约束的前提下，将条带分组以及分组内的数据块、校验块确定性映射至目标机架和目标存储节点，因此可实现数据块和校验块在机架级与节点级上的较均匀分布。由于本发明采用确定性冗余转换机制，并利用系统性 vandermonde reed-solomon 码的线性特性对校验块执行本地更新，能够使参与同一校验更新过程的相关校验块预先对齐并优先在本地完成更新，因此可减少转换过程中对跨机架数据采集的依赖，降低跨机架传输开销。

3、为实现上述目的，本发明方法的具体实现步骤包括如下：

4、步骤1，将所有原始条带划分为条带集合，确定每个条带集合内相邻原始条带之间的转换轮次；

5、步骤2，计算每个条带集合的校验重叠度序列，对每个原始条带内的数据块与校验块进行分组；

6、步骤3，构造每个条带集合内原始条带之间的递归边界结构；

7、步骤4，对每个条带集合内原始条带中的校验组与数据组执行机架级确定性映射；

8、步骤5，对每个已确定映射机架的校验组和数据组中的校验块和数据块执行节点级确定性映射；

9、步骤6，根据机架级确定性映射结果和节点级确定性映射结果，将每次转换后的条带中数据块与校验块总数超出单机架容错限制的机架上的数据块，迁移至未超出单机架容错限制的机架中，并基于 vandermonde reed-solomon 码的线性特性更新转换后条带的校验块；

10、步骤7，将更新转换后条带的数据块和校验块写回目标位置，更新分布式存储系统的元数据。

11、进一步地，所述将所有原始条带划分为条带集合是指，将所有原始条带按照每 个为一组进行划分，其中， 表示分布式存储系统所支持的最大转换次数。

12、所述分布式存储系统所支持的最大转换次数  为满足  的最大正整数，其中，表示向上取整操作，表示每个原始条带中数据块的数量，表示每个原始条带的校验块的数量，每个原始条带均具有相同的数据块数量和校验块数量，表示分布式存储系统中部署的机架总数。

13、进一步地，所述确定每个条带集合内相邻原始条带之间的转换轮次的步骤如下：

14、第一步，将每个条带集合内的原始条带从1开始依次进行编号；

15、第二步，按照相邻原始条带逐轮两两合并的方式，确定任意两个相邻编号的原始条带首次被归入同一条带时所对应的轮次，并将所述轮次作为该两个相邻原始条带之间的转换轮次。

16、进一步地，所述计算每个条带集合的校验重叠度序列由下式得到的：

17、，，；

18、其中，表示每个条带集合的校验重叠度序列，表示每个条带集合第t次转换的校验重叠度，表示每个条带集合第t次转换的校验重叠度。

19、进一步地，所述对每个原始条带内的数据块与校验块进行分组的步骤如下：

20、第一步，判断分布式存储系统所支持的最大转换次数  是否为1，若是，则执行第二步；否则，执行第四步；

21、第二步，判断每个条带集合的校验重叠度序列是否为2，若是，则执行第三步，否则，执行第四步；

22、第三步，将每个原始条带内的数据块和校验块划分为两个校验组和  个数据组中，，其中，一个校验组由两个校验块与 个数据块组成，另一个校验组由个校验块与一个数据块组成，其余数据块划分到  个数据组中，使得任意两个数据组中的数据块数量之差不超过1；

23、第四步，将每个原始条带内的所有校验块划分为一个校验组，将每个原始条带内的所有数据块划分到  个数据组中，，使得任意两个数据组中的数据块数量之差不超过1。

24、进一步地，所述构造每个条带集合内的原始条带之间的递归边界结构的步骤如下：

25、第一步，判断分布式存储系统所支持的最大转换次数  是否为1，若是，则执行第二步，否则，执行第三步；

26、第二步，将每个条带集合内所有原始条带的校验组与该条带集合内的第一个原始条带的校验组对齐，并将每个条带集合内的所有原始条带的数据组根据原始条带在条带集合内的编号顺序依次排开，且彼此之间不重叠；

27、第三步，将每个条带集合内所有原始条带的校验组与该条带集合内的第一个原始条带的校验组对齐，并根据每个条带集合内相邻原始条带之间的转换轮次以及每个条带集合的校验重叠度序列 ，确定相邻原始条带边界处重叠的数据组的数量为 ；每一个条带集合内的所有原始条带中剩余的数据组依次排开，且彼此之间不重叠，其中， 表示条带集合中两个相邻原始条带之间的第  次转换的校验重叠度。

28、进一步地，所述对每个条带集合内原始条带中的校验组与数据组执行机架级确定性映射的步骤如下：

29、第一步，将定义在  个符号上的正交数组中每行元素均相同的  行删除，保留其余各行在所述正交数组中的相对次序，并由保留后的各行构成机架级映射数组，其中，每个符号对应一个机架， 表示所述正交数组的符号数量， 表示所删除的每行元素均相同的行数，；

30、第二步，从机架级映射数组的第一行开始选取机架映射行，每个条带集合分配一行机架映射行；节点映射行从节点级映射数组的第一行开始，按照各行的排列顺序依次轮换；当节点映射行完成对节点级映射数组各行的一轮轮换后，机架映射行切换至机架级映射数组中的下一行，同时节点映射行重新从节点级映射数组的第一行开始选取；

31、第三步，根据条带集合内原始条带中校验组的数量，按列选取机架映射行中数量与所述校验组数量相同的前置列，并将所选前置列对应的机架作为校验组的映射机架，同一个条带集合中对齐的校验组选择相同的机架；

32、第四步，将条带集合内原始条带中排好的数据组按照排列顺序依次映射至机架映射行中剩余各列所对应的机架，重叠的数据组选择相同的机架。

33、进一步地，所述对每个已确定映射机架的校验组和数据组中的校验块和数据块执行节点级确定性映射的步骤如下：

34、第一步，将定义在  个符号上的正交数组中每行元素均相同的  行删除，保留其余各行在所述正交数组中的相对次序，并由保留后的各行构成节点级映射数组，其中每个符号对应一个存储节点， 表示所述正交数组的符号数量， 表示所删除的每行元素均相同的行数，且 ， 为每个机架中部署的存储节点数量，各机架具有相同的节点规模；

35、第二步，从节点级映射数组中的第一行开始选取节点映射行，并按照各行的排列顺序依次轮换，每个条带集合分配一行节点映射行；

36、第三步，将每个已确定映射机架的校验组中所包含的校验块数量，按列选取分配节点映射行中数量与所述校验块数量相同的前置列，并将所选前置列对应的节点作为校验块的映射节点；

37、第四步，当校验组中还包含数据块时，将该校验组中的数据块按照其所属原始条带在条带集合中的编号顺序依次排列，将数据块按照列的顺序依次映射至节点映射行中除已分配给校验块之外的其余各列对应的节点；

38、第五步，将每个已确定映射机架的数据组中的数据块，按照列的顺序依次映射至分配节点映射行的各列对应的节点。

39、本发明的冗余转换装置包括以下模块：

40、所述条带组织模块，用于将所有原始条带按照预定数量划分为条带集合，对每个条带集合内的原始条带进行编号，并确定每个条带集合内相邻原始条带之间的转换轮次；

41、所述校验重叠度计算与分组模块，用于计算每个条带集合的校验重叠度序列，并根据分布式存储系统所支持的最大转换次数以及所述校验重叠度序列，对每个原始条带内的数据块与校验块进行分组，得到校验组和数据组；

42、所述递归边界构造模块，用于根据每个条带集合内相邻原始条带之间的转换轮次以及每个条带集合的校验重叠度序列，构造每个条带集合内原始条带之间的递归边界结构；

43、所述机架级映射模块，用于基于正交数组构造机架级映射数组，并对每个条带集合内原始条带中的校验组与数据组执行机架级确定性映射；

44、所述节点级映射模块，用于基于正交数组构造节点级映射数组，并对每个已确定映射机架的校验组和数据组中的校验块和数据块执行节点级确定性映射；

45、所述转换执行模块，用于根据机架级确定性映射结果和节点级确定性映射结果，将每次转换后的条带中数据块与校验块总数超出单机架容错限制的机架上的数据块迁移至未超出单机架容错限制的机架中，并基于vandermonde reed-solomon码的线性特性更新转换后条带的校验块；

46、所述写回更新模块，用于将更新转换后条带的数据块和校验块写回目标位置，并更新分布式存储系统的元数据。

47、本发明与现有技术相比较，具有如下优点：

48、第一，本发明根据条带集合的校验重叠度序列，构造递归边界结构，支持多轮冗余转换，使当前轮转换后的布局可直接作为下一轮合并输入，克服了现有技术主要针对单轮转换进行优化、难以在连续多轮冗余转换的过程中保持布局兼容性的缺陷，使得本发明能够适应连续冗余转换场景，并在多轮转换过程中保持较低的数据迁移开销。

49、第二，本发明采用基于正交数组构造的机架级映射数组与节点级映射数组进行机架级与节点级确定性映射，克服了现有技术在冗余转换中仅能兼顾机架级放置均衡、难以保证节点级块分布均衡的缺陷，使得本发明在满足机架感知容错约束的同时，实现了条带分组以及分组内数据块、校验块在机架级和节点级上的均匀分布，提高了分布式存储系统的负载均衡能力。

50、第三，本发明采用确定性冗余转换机制，利用系统性 vandermonde reed-solomon码的线性特性实现校验块本地更新，克服了现有技术在校验块更新过程中跨机架数据采集较多、网络通信开销较大的缺陷，使得本发明能够实现校验块本地更新，减少转换过程中跨机架数据传输量，降低了网络带宽占用，并缩短了冗余转换完成时间。