一种纠删码存储系统均衡冗余转换方法及装置

1.本发明涉及存储技术领域，特别涉及一种纠删码存储系统均衡冗余转换方法及装置。


背景技术：

2.随着如今大规模存储系统的故障越来越普遍，为了保护数据的可靠性不受意外故障的影响，大多数现有的存储系统通常通过“备份”和“纠删码”来提前维护额外的数据冗余，以便在出现故障时利用预先存储的冗余恢复原始数据。备份将数据复制n份并分别存储于n个不同节点中，因而它的存储开销是原始数据的n倍。纠删码则是引入轻量计算，将固定大小的数据(称为数据块)作为输入，通过计算得到少量同等大小的冗余数据(称为校验块)。具体地，纠删码由两个参数k和m进行配置，在编码时将k个数据块计算生成m个校验块，这(k+m)个块组成一个“条带”并存入(k+m)个不同节点中(需要保证每个节点只有该条带的一个块)，同时条带中的任意k个块都可解码出其余m个块，纠删码以此来保证了出现故障时能够恢复原始数据。与存储多个相同副本的备份相比，纠删码的空间效率更高，能够在拥有更少数据冗余的情况下保持与备份相同的容错能力。目前，纠删码已广泛应用于各个存储系统，主要用于冷数据的持久性存储和缓解频繁访问数据的拖延者。
3.在大多数情况下，存储系统通常采用一系列不同冗余级别(也就是存储开销，计算为)的纠删码，以便在面对不断变化的访问特性和不断变化的可靠性需求时，从容地调整访问性能。因此，在不同冗余级别纠删码之间的转换(称为冗余转换)对于现代存储系统至关重要，其过程却容易产生大量的转换流量(即通过网络传输的数据进行转换)。通常情况下，冗余转换代表将(k,m)纠删码转化为(k',m)纠删码的操作，本发明考虑使得k'＞k的冗余转换操作，这也是现有方法常考虑的情况，以下的冗余转换默认为使得k'＞k的转换。具体来说，冗余转换需要对(k,m)编码的一些旧条带进行拆解(称为拆解条带)，将其中的数据块分配给其它(k,m)编码的条带(称为拉伸条带)，以便在新的(k',m)编码下重新编码。假设{d1,d2,...,dk}和{p1,p2,...,pm}为某一条带的k个数据块和m个校验块，每个校验块即为k个数据块的线性组合，可以通过伽罗瓦域[1]下的公式来计算，其中α
i,j
(1≤i≤k,1≤j≤m)为由数据块di计算校验块pj时使用的编码系数。对于拆解条带，需要将旧有的线性关系解耦，即无效掉其校验块，并将其数据块视为新数据块加入拉伸条带中；对于拉伸条带，需要接收这些新数据块并更新自己的校验块，用pj'表示被更新后的校验块pj，则在公式上可计算为其中1≤j≤m，δpj称为校验增量块。
[0004]
冗余转换的流量开销由两个部分组成，即数据块迁移和校验块更新。转换过程中，一部分数据块需要迁移到其他节点以保证(k',m)编码的新条带的(k'+m)块仍然存储在(k'
+m)个不同节点中，产生的流量即为数据块迁移流量。同时，拉伸条带由(k,m)编码转换为(k',m)编码，由于新加入了数据块，需要重新计算每个拉伸条带的m个校验块以保证容错能力在转换之后仍然生效，这部分流量即为校验块更新流量。现有的工作主要通过减少流量以加速冗余转换过程，如srs[2]通过设计数据布局以消除数据块迁移流量；ers[3]同srs一样设计了特殊数据布局，不仅消除了数据块迁移流量，还进一步减少了校验块更新流量；stripemerge[4]通过直接合并两个条带以达到k到2k的转换。现有的方法存在如下不足：(i)冗余转换的参数选择缺乏灵活性(srs和ers需要提前给定参数以配置布局，stripemerge只能进行k到其倍数的转换)；(ii)尽管优化了单次转换流量，但是它们在连续转换(即进行多次转换)时仍然容易产生大量流量(srs和ers在每次转换之前都需要重新调整布局)；(iii)没有考虑转换过程中节点之间负载不均衡问题，因而延长转换时间。
[0005]
[1]plank j s,simmerman s,schuman c d.jerasure:a library in c/c++facilitating erasure coding for storage applications-version 1.2[j].university of tennessee,tech.rep.cs-08-627,2008,23.
[0006]
[2]taranov k,alonso g,hoefler t.fast and strongly-consistent per-item resilience in key-value stores[c]//proceedings of the thirteenth eurosys conference.2018:1-14.
[0007]
[3]wu s,shen z,lee p p c.enabling i/o-efficient redundancy transitioning in erasure-coded kv stores via elastic reed-solomon codes[c]//2020 international symposium on reliable distributed systems(srds).ieee,2020:246-255.
[0008]
[4]yao q,hu y,cheng l,et al.stripemerge:efficient wide-stripe generation for large-scale erasure-coded storage[c]//2021ieee 41st international conference on distributed computing systems(icdcs).ieee,2021:483-493.


技术实现要素：

[0009]
本发明提出一种纠删码存储系统均衡冗余转换方法及装置，减少冗余转换过程中的流量，同时使节点间流量负载均衡，从而更快地完成转换过程。在发起冗余转换之后，本发明通过如下三个主要步骤达到上述目的，其一，制定一个最大流问题来指导数据块重分配，通过检查条带分布，并寻找适当的数据块来补充拉伸条带，以减少数据块迁移的流量；其二，设计先收集再编码算法来更新拉伸条带的校验块，以减少校验块更新的流量；其三，提出了一种启发式算法，仔细挑选条带进行分解或拉伸，以平衡各节点的流量负载。
[0010]
本发明采用如下技术方案：
[0011]
第一方面，一种纠删码存储系统均衡冗余转换方法，包括：
[0012]
数据块分配步骤，为各拉伸条带分配适当的数据块以最小化迁移流量；
[0013]
校验块更新步骤，基于为拉伸条带分配的数据块，使用先收集再更新的方式更新其校验块；
[0014]
负载均衡步骤，通过启发式算法迭代地挑选剩余未进行冗余转换的条带作为拉伸或者拆解条带以实现负载均衡。
[0015]
优选的，所述数据块分配步骤，具体包括：
[0016]
(1.1)建立网络流图；每个拉伸条带、拆解条带以及存储节点分别用一个顶点表示；拆解条带的顶点连有指向存储节点的顶点的有向边，边容量为1，每个拆解条带连接有k个存储节点；存储节点的顶点连有指向拉伸条带的顶点的有向边，边容量为1，若拉伸条带的k个数据块有存于该存储节点，则该存储节点的顶点和该拉伸条带的顶点之间不连接有向边；建立源点，源点连有指向每个拆解条带的顶点的有向边，边容量为k，表示每个拆解条带拥有k个数据块待分配；建立汇点，每个拉伸条带的顶点都连有指向汇点的有向边，边容量为k'-k，表示每个拉伸条带都需要k'-k个数据块以完成冗余转换；
[0017]
(1.2)运行dinic算法找到最大流；
[0018]
(1.3)根据找到的最大流来分配拆解条带的数据块给拉伸条带：若最大流中包含了某一存储节点的顶点到拉伸条带的顶点之间的有向边，将对应的存储节点中的任意拆解条带的数据块分配给对应的拉伸条带，每个拉伸条带使用分得的k'-k个数据块完成冗余转换。
[0019]
优选的，系统包括有t个拉伸条带和e个拆解条带，为保证t个拉伸条带能够完全接收e个拆解条带的数据块并完成k到k'的冗余转换，需满足条件
[0020]
优选的，所述校验块更新步骤，具体包括：
[0021]
(2.1)对每个条带，将存储其数据块的节点设置为数据节点，存储其校验块的节点设置为校验节点；为每个拉伸条带选取一个校验节点作为收集者节点，默认选取拉伸条带第一个校验块所在节点为其收集者节点；
[0022]
(2.2)分配给拉伸条带的k'-k个数据块所在的数据节点将对应数据块发送给拉伸条带的收集者节点；
[0023]
(2.3)收集者节点收集完k'-k个数据块后，计算出每个校验块所需的校验增量块，即需要计算m个校验增量块；
[0024]
(2.4)收集者节点将其他m-1个校验块需要的校验增量块发送给对应的校验节点，并更新拉伸条带在自身节点上的1个校验块；
[0025]
(2.5)其他m-1个校验节点接收到自己的校验增量块之后，更新拉伸条带存储在自身上的校验块。
[0026]
优选的，所述负载均衡步骤，具体包括：
[0027]
(3.1)挑选条带作为拉伸条带；遍历剩余未转换的条带尝试将其作为拉伸条带，若某一条带作为拉伸条带，将会为其校验节点带来负载以更新校验块，第一个校验块所在校验节点会新增k'-k个下载负载以收集新增数据块，并新增m-1个上传负载以发送其余校验块需要的校验增量块，其余m-1个校验节点新增1个下载负载以接收收集者节点传输的校验增量块；
[0028]
(3.2)记录将每个剩余条带尝试作为拉伸条带时系统的负载情况，并计算对应的系统负载均衡比；
[0029]
(3.3)选出拥有系统负载均衡比最小的条带作为拉伸条带；
[0030]
(3.4)重复步骤(3.1)～(3.3)，直到拉伸条带数量满足所需；
[0031]
(3.5)对于拆解条带的挑选，遍历剩余为转换的条带并尝试将其作为拆解条带，若
考虑某一条带为拆解条带，对系统负载的影响为其k个数据节点将新增1个上传负载以帮助拉伸条带进行冗余转换；记录将每个剩余条带尝试作为拆解条带时系统的负载情况，并计算对应的系统负载均衡比；选出拥有系统负载均衡比最小的条带作为拆解条带；重复步骤(3.5)直到拆解条带数量满足所需。
[0032]
优选的，所述系统负载均衡比为系统最大负载数与系统平均负载的比值；所述系统最大负载数为上传负载和下载负载之间的最大值。
[0033]
第二方面，一种纠删码存储系统均衡冗余转换装置，包括：
[0034]
数据块分配模块，用于为各拉伸条带分配适当的数据块以最小化迁移流量；
[0035]
校验块更新模块，用于为拉伸条带分配的数据块，使用先收集再更新的方式更新其校验块；
[0036]
负载均衡模块，用于通过启发式算法迭代地挑选剩余未进行冗余转换的条带作为拉伸或者拆解条带以实现负载均衡。
[0037]
第三方面，一种计算机设备，包括程序或指令，当所述程序或指令被执行时，所述的纠删码存储系统均衡冗余转换方法被执行。
[0038]
第四方面，一种存储介质，包括程序或指令，当所述程序或指令被执行时，所述的纠删码存储系统均衡冗余转换方法被执行。
[0039]
与现有技术相比，本发明的有益效果如下：
[0040]
(1)本发明由三个部分组成：通过建立最大流问题以减少数据块迁移；通过先收集再编码算法以减少校验块更新流量；通过启发式算法以平衡节点间负载；与现有方法相比，本发明的冗余转换参数能够灵活选择，在连续转换中也能保持较好的性能，是一种更普适的设计，同时平衡了节点间负载，更好地利用了i/o并行性；
[0041]
(2)本发明的冗余转换的参数没有限制，可以用于任意给定的k到k'的转换，也无需提前给定参数；
[0042]
(3)本发明在连续的冗余转换操作中仍然能保持良好且稳定的性能，现有的srs和ers无法保证；
[0043]
(4)本发明考虑到了冗余转换中的负载均衡问题，提出了一种启发式算法，仔细选择条带进行拉伸或拆解，以平衡各节点的负载。
附图说明
[0044]
图1为本发明实施例的纠删码存储系统均衡冗余转换方法的流程图；
[0045]
图2为本发明实施例的建立最大流问题来分配数据块以减少数据块迁移的示例图；其中，(a)表示冗余转换前的条带布局；(b)表示建立网络流图并寻找最大流；(c)表示冗余转换后的条带布局；
[0046]
图3为本发明实施例的先收集再更新算法的示例图；其中，(a)表示收集数据块，(b)表示更新数据块；
[0047]
图4为本发明实施例的启发式算法挑选拉伸条带的示例图；其中，(a)表示挑出s1作为拉伸条带，(b)表示挑出s2作为拉伸条带；
[0048]
图5为本发明实施例的纠删码存储系统均衡冗余转换系统的结构框图；
[0049]
图6为本发明实施例的原型系统结构示意图，该系统用于在亚马逊云服务器进行
真实云环境的测试；
[0050]
图7为本发明实施例的大规模模拟实验中对数据迁移比例的实验结果图；
[0051]
图8为本发明实施例的大规模模拟实验中连续转换流量的实验结果图；
[0052]
图9为本发明实施例的大规模模拟实验中不同节点数量的实验结果图；其中，(a)表示100节点，(b)表示200节点；
[0053]
图10为本发明实施例的大规模模拟实验中不同m值的实验结果图；其中，(a)表示m等于3，(b)表示m等于4；
[0054]
图11为本发明实施例的大规模模拟实验中负载均衡实验的结果图；
[0055]
图12为本发明实施例的亚马逊云环境实验中连续转换时间和计算时间的实验结果图；其中，(a)表示转换时间；(b)表示计算时间；
[0056]
图13为本发明实施例的亚马逊云环境实验中不同网络带宽的实验结果图；其中，(a)表示网络带宽为1gb/s时的转换时间实验结果图；(b)表示网络带宽为3gb/s时的转换时间实验结果图；
[0057]
图14为本发明实施例的亚马逊云环境实验中不同块大小的实验结果图其中，其中，(a)表示块大小为32mb时的转换时间实验结果图；(b)表示块大小为64mb时的转换时间实验结果图。
具体实施方式
[0058]
下面结合具体实施例，进一步阐述本发明。应理解，这些实施例仅用于说明本发明而不用于限制本发明的范围。此外应理解，在阅读了本发明讲授的内容之后，本领域技术人员可以对本发明作各种改动或修改，这些等价形式同样落于本技术所附权利要求书所限定的范围。
[0059]
本发明的核心是在纠删码存储系统中实现了一直通用的冗余转换方法，能够减少数据迁移和校验块更新的流量，并进一步启发式地平衡节点间负载，从而加速冗余转换过程。
[0060]
参见图1所示，本实施例一种纠删码存储系统均衡冗余转换方法，包括：
[0061]
步骤1，数据块分配步骤，为各拉伸条带分配适当的数据块以最小化迁移流量；
[0062]
步骤2，校验块更新步骤，基于为拉伸条带分配的数据块，使用先收集再更新的方式更新其校验块；
[0063]
步骤3，负载均衡步骤，通过启发式算法迭代地挑选剩余未进行冗余转换的条带作为拉伸或者拆解条带以实现负载均衡。
[0064]
具体的，所述步骤1的具体实现如下。
[0065]
(1.1)建立网络流图。假设有t个拉伸条带和e个拆解条带，需满足条件以保证t个拉伸条带能够完全接收e个拆解条带的数据块并完成k到k'的冗余转换。在网络流图中，每个拉伸条带、拆解条带以及存储节点分别用一个顶点表示。拆解条带的顶点(简称为拆解顶点)连有指向存储节点的顶点(简称为存储顶点)的有向边，边容量为1，表示该拆解条带有一个数据块在该存储节点中，因此每个拆解条带应该连接有k个存储节点(因为每个拆解条带有k个数据块)。存储顶点连有指向拉伸条带的顶点(简称为拉伸顶点)的有向
边，边容量为1，表示该存储节点可以为该拉伸条带提供一个数据块而不会发生数据块迁移(即拉伸条带的k个数据块均未存储在该节点中)，若拉伸条带的k个数据块有存于该存储节点，则该存储顶点和该拉伸顶点之间不连接有向边。建立源点，源点连有指向每个拆解顶点的有向边(即有e条)，边容量为k，表示每个拆解条带拥有k个数据块待分配。建立汇点，每个拉伸顶点都连有指向汇点的有向边，边容量为k'-k，表示每个拉伸条带都需要k'-k个数据块以完成冗余转换。至此，网络流图建立完毕；
[0066]
(1.2)运行dinic算法找到最大流，dinic算法为现有的一种寻找最大流的算法；
[0067]
(1.3)根据找到的最大流来分配拆解条带的数据块给拉伸条带：若最大流中包含了某一存储顶点到拉伸顶点之间的有向边，那么将对应的存储节点中的任意拆解条带的数据块分配给对应的拉伸条带即可，每个拉伸条带分得k'-k个数据块以帮助其完成冗余转换。
[0068]
参见图2所示，步骤1通过制定最大流问题来为拉伸条带分配数据块以减少数据迁移流量。根据拉伸条带和拆解条带的数据布局建立网络流图，使用最大流算法找出其中的最大流，根据最大流为拉伸条带分配数据块以减少数据迁移流量。图1展示了利用最大流来分配数据块的示例图。图2(a)展示了冗余转换之前拉伸条带{s1,s2,...,s5}和拆解条带{s6,s7,...,s
10
}在节点{n1,n2,...,n6}中的数据布局，其中k＝2，m＝1，k需要转换为k'＝4，d表示数据块，p表示校验块。图2(b)展示了根据步骤1描述的规则所建立的网络流图，拆解顶点{s6,s7,...,s
10
}连有指向存储顶点{n1,n2,...,n6}的有向边，每条边容量为1；存储顶点连有指向拉伸顶点{s1,s2,...,s5}的有向边，每条边容量为1；源点连有指向拆解顶点的有向边，其容量为k＝2；拉伸顶点连有指向汇点的有向边，容量为k'-k＝2。其中存储顶点与拉伸顶点之间的红色边为网络流图最大流的一部分，指示了将哪些存储节点中的数据块分配给对应拉伸条带。图2(c)展示了冗余转换后拉伸条带的布局，可以看出根据图2(b)的最大流来分配数据块没有产生数据迁移。
[0069]
所述步骤2的具体实现如下。
[0070]
(2.1)对每个条带，将存储其数据块的节点成为数据节点，存储其校验块的节点称为校验节点。为每个拉伸条带选取一个校验节点作为收集者节点，本发明默认选取拉伸条带第一个校验块所在节点为其收集者节点；
[0071]
(2.2)分配给拉伸条带的k'-k个数据块所在的数据节点将对应数据块发送给拉伸条带的收集者节点；
[0072]
(2.3)收集者节点收集完k'-k个数据块后，计算出每个校验块所需的校验增量块，即需要计算m个校验增量块；
[0073]
(2.4)收集者节点将其他m-1个校验块需要的校验增量块发送给对应的校验节点，并更新拉伸条带在自身节点上的1个校验块；
[0074]
(2.5)其他m-1个校验节点接收到自己的校验增量块之后，更新拉伸条带存储在自身上的校验块。
[0075]
具体的，步骤2中，使用先收集再编码算法来更新拉伸条带校验块。对每个拉伸条带，首先选择其第一个校验块所在校验节点为收集者节点，之后将数据分配模块为该拉伸条带分配的数据块从其存储的数据节点中传输给收集者节点，最后，收集者节点统一计算各校验块所需校验块增量并传输给对应校验节点更新其校验块，同时更新本节点的校验
块。图3展示了对一拉伸条带先收集再编码算法的例子，其中k＝2，m＝2，k'＝4，d3和d4为分配给该拉伸条带的新数据块。首先确定收集者节点为第一个校验块p1所在节点n3，之后n5和n6将d3和d4传输给n3，最后n3计算2个校验块所需的校验增量块δp1和δp2用于更新，其中δp2需要发送给n4以更新校验块p2。
[0076]
所述步骤3的具体实现如下。
[0077]
(3.1)挑选条带作为拉伸条带。遍历剩余未转换的条带尝试将其作为拉伸条带，若某一条带作为拉伸条带，将会为其校验节点带来负载以更新校验块(此处只考虑校验块更新而忽略数据迁移为节点带来的负载，因步骤一的数据块分配阶段几乎消除了数据迁移的流量)，第一个校验块所在校验节点(即收集者节点)会新增k'-k个下载负载以收集新增数据块，并新增m-1个上传负载以发送其余校验块需要的校验增量块，其余m-1个校验节点会新增1个下载负载以接收收集者节点传输的校验增量块；
[0078]
(3.2)记录将每个剩余条带尝试作为拉伸条带时系统的负载情况，并计算对应的系统负载均衡比，即系统最大负载数(上传负载和下载负载之间的最大值)与系统平均负载的比值；
[0079]
(3.3)选出拥有系统负载均衡比最小的条带作为拉伸条带；
[0080]
(3.5)重复上述步骤直到拉伸条带数量满足所需；
[0081]
(3.5)对于拆解条带的挑选，遍历剩余为转换的条带并尝试将其作为拆解条带，若考虑某一条带为拆解条带，对系统负载的影响为其k个数据节点将新增1个上传负载以帮助拉伸条带进行冗余转换。记录将每个剩余条带尝试作为拆解条带时系统的负载情况，并计算对应的系统负载均衡比，即系统最大负载数(上传负载和下载负载之间的最大值)与系统平均负载的比值；选出拥有系统负载均衡比最小的条带作为拆解条带；重复上述步骤直到拆解条带数量满足所需。
[0082]
具体的，步骤3中，利用启发式算法迭代地从未转换的条带中挑选出拉伸条带和拆解条带，以实现节点间负载均衡。对每个未转换条带，尝试将其作为拉伸(拆解)条带，统计系统负载情况，计算负载均衡比并记录，遍历过所有未转换条带之后选出其中负载均衡比最小的(越小的负载均衡比代表节点之间负载均衡情况越好，负载均衡比能达到的最小值也是理论最优值为1)条带作为实际的拉伸(拆解)条带，并根据选择的拉伸条带更新当前系统的负载情况，重复上述步骤直到拉伸(拆解)条带数量足够。图4展示了启发式算法挑选拉伸条带的示例图，其中k＝2，m＝2，k'＝4，且需要挑选2个拉伸条带。首先挑选第一个拉伸条带，尝试遍历s1，s2，...，s4作为拉伸条带，拉伸条带会对第一个校验块所在校验节点(即收集者节点)产生k'-k＝2个下载负载用于收集新数据块，以及m-1＝1个上传负载用于发送其他校验块所需校验增量块，同时另外的m-1＝1个校验节点会产生1的下载负载用于接收校验增量块。由于四个条带作为第一个拉伸条带时系统的负载均衡比均为6，因此选择任意一个作为实际的拉伸条带均可，图4(a)中选择了s1作为第一个拉伸条带。之后在s2，s3，s4中挑选第二个拉伸条带，图4(b)展示遍历三个条带之后，s3作为第二个拉伸条带时，系统的负载均衡比最小，因此将其作为拉伸条带。至此，挑选完毕。
[0083]
参见图5所示，本实施例还公开了一种纠删码存储系统均衡冗余转换装置，包括：
[0084]
数据块分配模块501，用于为各拉伸条带分配适当的数据块以最小化迁移流量；
[0085]
校验块更新模块502，用于为拉伸条带分配的数据块，使用先收集再更新的方式更
新其校验块；
[0086]
负载均衡模块503，用于通过启发式算法迭代地挑选剩余未进行冗余转换的条带作为拉伸或者拆解条带以实现负载均衡。
[0087]
一种纠删码存储系统均衡冗余转换装置中各模块的具体实现参见一种纠删码存储系统均衡冗余转换方法，本实施例不做重复说明。
[0088]
进一步的，参见图6所示，本实施例公开了系统结构原型，系统原型包含一个集中式控制器和多个代理，控制器在元数据服务器中运行，以方便访问元数据信息(例如，每个条带的块的位置)，而代理则运行在存储节点中(每个节点有一个代理)以进行数据访问。一旦接收到冗余转换请求，控制器将生成转换决策，包括挑选拉伸和拆解条带、为拉伸条带分配新数据块以及参与校验更新的节点之间的数据路由信息。这些转换决策被发送到参与转换的代理(图6中的步骤)。在接收到控制器的决策后，代理首先解析命令以了解其任务：对于负责数据迁移的节点，它们将通过发送和接收需要迁移的块来协同完成工作(图6中的步骤)；对于负责校验更新的节点，它们将首先把新数据块发送给指定的收集者节点，然后更新拉伸条带的校验块(图6中的步骤)。分配给节点的任务全部完成后，节点将向控制器发送确认信息进行通知(图6中的步骤)。
[0089]
如下使用本发明的冗余转换方法/冗余转换装置进行性能测试。
[0090]
通过大规模的模拟和云环境实验来评估本发明的性能。将本发明与另外两种最先进的冗余转换方法进行了比较：(i)srs，它基于预固定的编码参数建立条带布局，消除了第一次转换操作的数据迁移；(ii)ers，也是通过预固定的编码参数建立条带布局，消除了第一次转换操作的数据迁移，但进一步通过提前扩大编码矩阵减少了校验更新流量。在实验结果图中，(k,m,k')表示将纠删码(k,m)转换为纠删码(k',m)的冗余转换。
[0091]
a、大规模模拟实验
[0092]
首先进行模拟，以揭示本发明部署在大规模存储系统时的性能。实验设置：删除了网络传输和存储操作，并测量了常用纠删码配置下的冗余转换流量。具体来说，实验首先部署了纠删码(k,m)，并不断地增加k的值，同时保持m的值不变。除非另有说明，否则将选择以下默认配置：将条带的数量设置为5000条带，并将它们分布在100个节点上，块的大小设置为64mb(在hadoop hdfs中使用)。
[0093]
a.1数据迁移比例实验：
[0094]
为了证明通过最大流来分配数据块能够几乎消除数据迁移而进行了该实验。将节点数量设置为50，并布置5000个由纠删码(6,3)编码的条带。实验执行多次冗余转换(从纠删码(6,3)到纠删码(45,3))，并测量发生数据迁移的拉伸条带的比例。图7显示，前7个转换操作没有引发任何数据迁移流量，而在最后一次转换操作中，只有5.7％的拉伸条带发生了数据迁移。在(35，3，45)转换之后几乎不会再执行转换操作，因为纠删码(45，3)编码的条带已经有48个块，这些块的数量接近系统中的节点数量(即50个)。
[0095]
a.2连续转换流量实验：
[0096]
将k的值从6增加到97来执行16个转换操作，并测量三种方法的转换流量。图8显示，本发明的方法大大减少了冗余转换流量，而srs和ers放大了连续转换操作中的转换流量。总体而言，本发明分别比ers和srs平均减少了79.6％和92.6％的冗余转换流量。
[0097]
a.3不同节点数量实验：
[0098]
将系统中的节点数量从100个增加到200个并测量三种方法的转换流量。图9显示，在不同节点数下，本发明方法的转换流量几乎没有变化。其根本原因是节点的数量只会影响本发明方法的数据迁移流量，而本发明通过建立最大流量来消除了大部分的数据迁移流量。与ers和srs相比，本发明平均分别减少了71.1％和89.3％的冗余转换流量。
[0099]
a.4不同m值实验：
[0100]
实验中，对于不同m值分别进行测试。图10结果表明，三种方法的转换流量随m值的增加而增加。原因是，更大的m值意味着需要更新更多的校验块，因而带来了更多的校验更新流量。与ers和srs相比，本发明平均分别减少了71.7％和89.4％的冗余转换流量。
[0101]
a.5负载均衡实验：
[0102]
实验评估了三种方法的负载平衡比。图11显示了本发明可以很好地平衡节点间负载，因为它仔细地选择了拉伸条带和拆解条带来进行负载平衡。在所有连续转换操作中，ers和srs的平均负载平衡比均为2.9，而本发明的方法将负载平衡比降低到1.2，更接近最优(最优值为1)。
[0103]
b、亚马逊云环境实验
[0104]
在亚马逊云环境中布置本发明原型并评估了其性能，以证明其在真实云存储系统中使用的效率。实验在美国东部(北弗吉尼亚州)地区分配了21个m5.xmlage的虚拟机实例，每个实例都配备了4个vcpu(3.1ghz intel xeon platinum)，16gb内存，40gb的ebs存储空间。操作系统为ubuntu 18.04，每个实例之间的网络带宽约为2gb/s(由iperf测量)。
[0105]
在这21个实例中，一个实例被部署了本发明原型中的控制器来指导冗余转换，其余20个实例运行本发明原型中的代理，每个实例均有一个代理。最初在20个实例中部署了由纠删码(6,3)编码的200个条带，并不断地将k的值增加到15。数据块的大小被设置为64mb。使用linux工具tc来控制这些实例之间的网络带宽。每个实验重复5次，并计算平均每个拉伸条带的冗余转换时间。实验结果还绘制了误差条来显示所有实验中的最大值和最小值(其中一些可能太小)。
[0106]
b.1连续转换时间实验：
[0107]
图12(a)为连续冗余转换时间实验结果，其显示本发明方法总是能达到最少的转换时间，平均分别比ers和srs少69.8％和89.2％。
[0108]
b.2计算时间实验：
[0109]
实验测量了本发明方法在不同节点和条带数量下，对每个拉伸条带生成冗余转换方案所需的平均计算时间。节点的数量从25个增加到200个，并将条带的数量从500个增加到8000个，并考虑(6,3,8)转换。图12(b)中n表示节点数量，结果显示每条拉伸条的平均计算时间小于0.007s，与拉伸每条所需的总的转换时间(约0.2s，见实验b.1)相比，几乎可以忽略不计。
[0110]
b.3不同网络带宽实验：
[0111]
实验研究了本发明方法在不同网络带宽下的性能，利用tc将带宽从1gb/s变为2gb/s。图13的实验结果显示，在不同带宽下，本发明方法的转换时间均为最少，说明本发明方法在不同的网络条件下可以保持其有效性。总体而言，与ers和srs相比，本发明平均分别减少了68.8％和89.0％的转换时间。
[0112]
b.4不同块大小实验：
[0113]
最后，通过改变块大小从32mb到64mb来测量转换时间。图14表明，三种方法的转换时间都随着块大小的增加而增加，原因是更大的块大小将放大转换流量和存储i/o。总体上，与ers和srs相比，本发明的平均转换时间分别减少了69.7％和89.2％。
[0114]
本发明是一种通过最小化冗余转换流量和平衡节点负载来促进纠删码存储系统中的冗余转换的方法。本发明首先抑制数据迁移流量和先收集再编码以进行校验更新，达到最小化转换流量的目的，然后仔细地选择拉伸和拆解条带，以平衡跨节点的负载。大规模模拟和亚马逊云环境实验都证明了本发明的有效性和通用性。
[0115]
本发明实施例还提供一种计算机设备，包括程序或指令，当所述程序或指令被执行时，用以执行本发明实施例提供的一种纠删码存储系统均衡冗余转换方法及任一可选方法。
[0116]
本发明实施例提供一种存储介质，包括程序或指令，当所述程序或指令被执行时，用以执行本发明实施例提供的一种纠删码存储系统均衡冗余转换方法及任一可选方法。
[0117]
最后应说明的是：本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、光学存储器等)上实施的计算机程序产品的形式。
[0118]
本发明是参照根据本发明的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
[0119]
这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0120]
显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。

技术特征：
1.一种纠删码存储系统均衡冗余转换方法，其特征在于，包括：数据块分配步骤，为各拉伸条带分配适当的数据块以最小化迁移流量；校验块更新步骤，基于为拉伸条带分配的数据块，使用先收集再更新的方式更新其校验块；负载均衡步骤，通过启发式算法迭代地挑选剩余未进行冗余转换的条带作为拉伸或者拆解条带以实现负载均衡。2.根据权利要求1所述的纠删码存储系统均衡冗余转换方法，其特征在于，所述数据块分配步骤，具体包括：(1.1)建立网络流图；每个拉伸条带、拆解条带以及存储节点分别用一个顶点表示；拆解条带的顶点连有指向存储节点的顶点的有向边，边容量为1，每个拆解条带连接有k个存储节点；存储节点的顶点连有指向拉伸条带的顶点的有向边，边容量为1，若拉伸条带的k个数据块有存于该存储节点，则该存储节点的顶点和该拉伸条带的顶点之间不连接有向边；建立源点，源点连有指向每个拆解条带的顶点的有向边，边容量为k，表示每个拆解条带拥有k个数据块待分配；建立汇点，每个拉伸条带的顶点都连有指向汇点的有向边，边容量为k'-k，表示每个拉伸条带都需要k'-k个数据块以完成冗余转换；(1.2)运行dinic算法找到最大流；(1.3)根据找到的最大流来分配拆解条带的数据块给拉伸条带：若最大流中包含了某一存储节点的顶点到拉伸条带的顶点之间的有向边，将对应的存储节点中的任意拆解条带的数据块分配给对应的拉伸条带，每个拉伸条带使用分得的k'-k个数据块完成冗余转换。3.根据权利要求2所述的纠删码存储系统均衡冗余转换方法，其特征在于，系统包括有t个拉伸条带和e个拆解条带，为保证t个拉伸条带能够完全接收e个拆解条带的数据块并完成k到k'的冗余转换，需满足条件4.根据权利要求2所述的纠删码存储系统均衡冗余转换方法，其特征在于，所述校验块更新步骤，具体包括：(2.1)对每个条带，将存储其数据块的节点设置为数据节点，存储其校验块的节点设置为校验节点；为每个拉伸条带选取一个校验节点作为收集者节点，默认选取拉伸条带第一个校验块所在节点为其收集者节点；(2.2)分配给拉伸条带的k'-k个数据块所在的数据节点将对应数据块发送给拉伸条带的收集者节点；(2.3)收集者节点收集完k'-k个数据块后，计算出每个校验块所需的校验增量块，即需要计算m个校验增量块；(2.4)收集者节点将其他m-1个校验块需要的校验增量块发送给对应的校验节点，并更新拉伸条带在自身节点上的1个校验块；(2.5)其他m-1个校验节点接收到自己的校验增量块之后，更新拉伸条带存储在自身上的校验块。5.根据权利要求4所述的纠删码存储系统均衡冗余转换方法，其特征在于，所述负载均衡步骤，具体包括：(3.1)挑选条带作为拉伸条带；遍历剩余未转换的条带尝试将其作为拉伸条带，若某一
条带作为拉伸条带，将会为其校验节点带来负载以更新校验块，第一个校验块所在校验节点会新增k'-k个下载负载以收集新增数据块，并新增m-1个上传负载以发送其余校验块需要的校验增量块，其余m-1个校验节点新增1个下载负载以接收收集者节点传输的校验增量块；(3.2)记录将每个剩余条带尝试作为拉伸条带时系统的负载情况，并计算对应的系统负载均衡比；(3.3)选出拥有系统负载均衡比最小的条带作为拉伸条带；(3.4)重复步骤(3.1)～(3.3)，直到拉伸条带数量满足所需；(3.5)对于拆解条带的挑选，遍历剩余为转换的条带并尝试将其作为拆解条带，若考虑某一条带为拆解条带，对系统负载的影响为其k个数据节点将新增1个上传负载以帮助拉伸条带进行冗余转换；记录将每个剩余条带尝试作为拆解条带时系统的负载情况，并计算对应的系统负载均衡比；选出拥有系统负载均衡比最小的条带作为拆解条带；重复步骤(3.5)直到拆解条带数量满足所需。6.根据权利要求5所述的纠删码存储系统均衡冗余转换方法，其特征在于，所述系统负载均衡比为系统最大负载数与系统平均负载的比值；所述系统最大负载数为上传负载和下载负载之间的最大值。7.一种纠删码存储系统均衡冗余转换装置，其特征在于，包括：数据块分配模块，用于为各拉伸条带分配适当的数据块以最小化迁移流量；校验块更新模块，用于为拉伸条带分配的数据块，使用先收集再更新的方式更新其校验块；负载均衡模块，用于通过启发式算法迭代地挑选剩余未进行冗余转换的条带作为拉伸或者拆解条带以实现负载均衡。8.一种计算机设备，其特征在于，包括程序或指令，当所述程序或指令被执行时，如权利要求1至6中任意一项所述的方法被执行。9.一种存储介质，其特征在于，包括程序或指令，当所述程序或指令被执行时，如权利要求1至6中任意一项所述的方法被执行。

技术总结
本发明公开了一种纠删码存储系统均衡冗余转换方法及装置，方法在发冗余转换发起之后进行高效且均衡的转换，包括：数据块分配步骤，制定一个最大流问题来指导数据块重分配，通过检查条带分布，并寻找适当的数据块来补充拉伸条带，以减少数据块迁移的流量；校验块更新步骤，设计先收集再编码算法来更新拉伸条带的校验块，以减少校验块更新的流量；负载均衡步骤，提出了一种启发式算法，仔细挑选条带进行分解或拉伸，以平衡各节点的流量负载。本发明在抑制冗余转换流量的同时平衡节点之间的负载，能够更快地完成转换过程。够更快地完成转换过程。够更快地完成转换过程。


技术研发人员：沈志荣 万志国 龚国文 舒继武
受保护的技术使用者：厦门大学
技术研发日：2023.07.17
技术公布日：2023/10/8