本发明涉及分布式存储系统，特别是一种基于蚁群优化的纠删编码存储系统数据更新方法。
背景技术：
由于高可用性和空间效率，纠删码已成为在分布式存储系统中提供数据持久性的事实标准。纠删码将大的数据对象划分成小的数据块，然后将其编码为多个数据块以及校验块，并将其部署在不同群集的节点上。
对持久性和存储效率的需求使纠删码成为一个新的有吸引力的设计点。关于众所周知的纠删码rs(n，k)，一个大小为d字节的文件被分为k个大小相等的数据块di(1≤i≤k)，每个大小d/k字节。然后，这些数据块被编码成一组(也称为条带)k数据块和(n-k)校验块，这些块分布在n个不同的存储节点(d1...dk；p1...pn-k)中，属于不同的集群，以此来最大限度地提高系统的可靠性。每个校验块pj(1≤j≤(n-k))可以是根据式:
数据更新在分布式存储系统中很常见。许多企业的服务器和网络文件系统，更新请求主导了写入工作负载(通常超过90％)。在典型的(n,k)mds纠删码存储系统中，一个数据块的更新请求涉及(n-k)个校验块的更新。根据更新过程中是否传输整个数据块，更新可以分为两类：基于raid的更新和基于增量的更新。基于raid的更新方案需要在数据节点和校验节点之间传输整个数据块，也就是说，为了完成对数据节点的更新，数据节点需要收集所有数据块，然后重新计算所有的校验快，并将其传到相应的校验节点。相比之下，基于增量的更新方案可以节省更多的i/o和网络带宽，因为数据节点上的更新可以通过将增量(数据块要修改的部分)通过广播的方式传输到每一个校验节点。但是，频繁的数据更新会导致巨大的i/o和带宽开销。尤其是在使用纠删码的健/值存储系统中，对健/值数据进行密集的小型更新会导致昂贵的i/o操作和网络流量。
提高纠删码的更新效率具有重要意义。因此，最近投入了大量精力来优化更新性能，同时减少i/o和网络延迟。现有的更新方案，如azure和codfs，采用追加式更新或替换式更新和混合更新。在大规模分布式存储系统中执行纠删码更新的琐碎操作可能导致性能显著下降。数据更新涉及到对多个校验节点的更新，不可避免地会导致相当大的i/o和带宽开销。
第一个挑战是当有多个数据节点需要更新时，这些节点之间的协作将导致大量的网络流量和编码操作。增量和编码计算操作可以在所有数据节点上高效地执行，以实现并行更新。然而，如何以最小网络流量将这些δpj传递到相应的校验节点是一个关键问题。
第二个挑战是如何为异构大型网络存储系统中的每一个传输找到一个最佳路径，涉及到不平等的i/o吞吐量、跨节点的链路带宽和其他qos限制。从根本上说，这是一个多目标的路由发现优化问题，充分利用网络资源，提高数据更新效率。
技术实现要素：
本发明所要解决的技术问题是，针对现有技术不足，提供一种基于蚁群优化的纠删编码存储系统数据更新方法，为数据增量的收集以及校验增量的分发找到最佳路由，从而降低数据在网络中的延时，提高纠删码的更新效率。
为解决上述技术问题，本发明所采用的技术方案是：一种基于蚁群优化的纠删编码存储系统数据更新方法，包括以下步骤：
1)将所有的蚂蚁分为m轮发放，每一轮的数量蚂蚁为k只；
2)将当前轮蚂蚁当前所处的位置赋值为i，判断是否收敛的布尔型变量设为converge，并初始化为false；；初始化每条路径上的信息素τ；
3)计算当前节点i到目的节点d的距离d(i,d)；i∈v；v表示网络节点的集合；
4)对于每一轮中的每一只蚂蚁，若节点i到邻居节点j的链路带宽b(i，j)>breq且节点j没有被访问过，即
5)当本轮所有的蚂蚁爬行结束后，记录每一轮中每一只蚂蚁的爬行路径，如果这只蚂蚁的终点是目的节点，则记录这只蚂蚁从源节点到目的节点的路径和时间，时间即为延时，如果这只蚂蚁的终点不是目的节点，则将蚂蚁在这条路径上的延时记为无穷大，更新每条路径上的信息素；
6)判断蚂蚁的爬行路径是否收敛，如果收敛则停止循环，输出该爬行路径，即最佳路径，以及最佳路径的延时；若不收敛，则返回步骤2)。(刚开始的路径不同，随着蚂蚁数量的增加，由于信息素和启发式因子的作用，越来越多的蚂蚁会沿着某一条路径爬行，这个路径就是收敛路径，也是最佳路径，这个路径的延时也是最小的，例如，本发明中收敛的判断条件是当有连续200只蚂蚁爬行的路径一样时就可判断路径是收敛的)
步骤3)中，利用下式选择使概率
其中，η(i,j)＝(1/d(j,d))β*(1/(wi we))λ,j∈φ(i)；η(i,j)即ηij；θ为启发式因子的权重，
步骤6)中，判断路径是否收敛的条件为：当有连续m只蚂蚁爬行的路径一样时，就判断该路径是收敛的。
本发明还提供了一种集合节点更新方法，其包括以下步骤：
1)对于每一个需要更新的数据节点di，利用上述方法计算其它每个需要更新的数据节点到此数据节点di的延时，即数据增量的收集阶段的延时，利用权利要求1所述方法计算此数据节点di到每一个校验节点的延时，即校验快增量的分发阶段的延时；
2)将数据节点di的数据增量的收集阶段的延时和校验快增量的分发阶段的延时进行累加求和，记为sum(i)；
3)从最小的sum(i)中选择延时最小的节点d(i)作为集合节点。
与现有技术相比，本发明所具有的有益效果为：本发明利用纠删码存储系统中的存储节点性能不同的特点，设计一种基于蚁群算法的多目标优化路由算法，可以充分利用网络中的资源，为数据增量的收集以及校验增量的分发找到最佳路由，从而降低数据在网络中的延时，提高纠删码的更新效率。
附图说明
图1为集中式更新模式；
图2集中式更新的两个阶段。图2(a)集中式更新的第一阶段，图2(b)集中式更新的第二阶段；
图3.基于macou算法的多目标更新树实例研究；图3(a)显示了多目标更新树；图3(b)描绘了路径path(v1，v7)的搜索步骤；
图4.不同rn下的延时对比；
图5.两种典型的数据中心网络拓扑；图5(a)和图5(b)分别为胖树和dcell中心网络拓扑的更新方案；
图6.不同大小的数据增量下的延时；
图7.r的数量改变，k的数量不变；
图8.k的数量改变，r的数量不变；
图9.不同网路规模下的延时；
图10不同网路规模下的延时；
图11.不同规模的胖树的延时；
图12.不同规模的dcell结构下的延时；
图13.收敛性比较：不同网络拓扑下随着蚂蚁数量增加的更新。图13(a)随机网络拓扑收敛图；图13(b)胖树网络拓扑收敛图；图13(c)dcell网络拓扑收敛图；图13(d)网络中的节点个数为200时，3种网络拓扑图收敛情况的比较。
具体实施方式
为了描述方便，本发明把基于纠删码数据更新模式的蚁群优化，简称为acous，把基于多目标蚁群优化路由算法，简称为macou。
本发明设计的基于纠删码数据更新模式的蚁群优化分为以下几个步骤：第一步说明现有的纠删码更新的两种模式：分布式模式和集中式模式以及多数据更新路由问题，从而得出结论：和分布式更新模式相比，集中式更新模式节约资源，网络开销较小；第二步围绕第一步的介绍的集中式更新模式，提出了acous算法设计，为了更清楚的说明问题又利用一个例子来描述构造多目标更新树的构造过程；第三步对集合模式中集合节点的选择效率进行分析。第四个步针对我们提出的基于蚁群优化的纠删编码存储系统数据更新方案进行实验并分析。
第一步：多个节点更新的路由问题分析
这一步介绍了多个数据节点更新下的数据路由问题以及异构纠删码存储系统的相应qos指标。
路由的qos度量
针对下面的典型qos指标，提高大规模纠删码存储系统的多个数据节点更新的效率。
距离：节点s到节点d之间的距离d(s,d)可以通过这两个节点之间的跳数来衡量，这个因素通常用来构建数据传输的最小生成树较短的网络距离表示数据传输的跳数较少，传输延迟较少。
带宽：带宽是衡量网络中链路容量的指标。通常，数据传输的瓶颈由传输路径上的最小带宽确定。由于难以获得实时可用带宽，我们利用平均带宽b(e)作为链路e的链路带宽。如公式(6)所示，b(s,d)表示路径p(s,d)上的最小平均带宽。
b(s,d)＝min{b(e),e∈path(s,d)}(1)
延迟：延迟是本发明采用的衡量更新效率的关键指标。延迟越小表示传输效率越高。如公式(7)所示，路径path(s,d)上的总延迟delay(s,d)是处理延迟dproc，传输延迟dtrans和其上的传播延迟dprop之和。这里省略了排队延迟，因为这超出了我们的讨论范围。
delay(s,d)＝∑e∈path(s,d)(dprop dproc dtrans)(2)
接下来我们将围绕这几个指标设计多目标优化路由算法来提高纠删码的更新效率。
首先我们详细介绍了纠删码的两种更新模式：分布式更新模式和集中式更新模式。然后结合着两种方式的特点从中选择一种相对较好的更新方式。
纠删码存储系统多数据更新的两种模式
当有多个数据节点需要更新时，有两种潜在的更新模式：分布式和集中式。分布式模式用于更新的每个数据节点分别向每个校验节点发送δdi。集中式更新模式的更新过程分为两步：
第一步：所有更新的数据节点di发送δdi到集合节点rn；
第二步：集合节点计算δpj，然后将δpj发送到对应的校验节点pj。
表1显示了如果u(1≤u≤k)数据块需要更新，两种更新模式产生的数据传输和读写量。从表一可以看出，分布式模式和集合模式的i/o开销与计算方式几乎相等。分布式模式下的数据传输开销随着u的增加而迅速超过了集合模式中的数据传输开销，因此我们采用集中式更新模式来完成多节点更新。
表1两种更新模式产生的数据传输和读写量
第二步：设计基于蚁群优化的多数据节点更新方案
基于上面列出的qos指标，这一步我们将详细说明acous的更新方案的设计。我们首先介绍两阶段集中式数据更新过程，然后介绍多目标优化更新路由算法。此外，还讨论了集合节点选择机制。
集中式更新分为两步：
acous的主要思想是采用两阶段集中式更新方案，以通过多目标更新树对rs(k r,k)执行有效的数据增量收集和校验增量分布。
第一步：数据增量收集。图2(a)描述了集合式更新中以数据节点d2的作为集合节点更新的第一步。如果有u(u≤k)个数据节点需要更新，则每个数据节点直接用新的数据块d′i(1≤i≤k)覆盖原始数据块di，同时计算数据增量δdi，并将数据增量δdi通过下一节介绍的macous传递到集合节点d2。通过这种方式，第一阶段完成数据增量收集产生的数据传输量为u-1，本地读取次数为u，本地写入次数为u。
第二步：校验块增量的分发。图2(b)描述了集合式更新的第二步。rn基于第一步收到的δdi，通过公式
多目标蚁群优化更新路由算法算法1：多目标蚁群优化更新路由算法
输入：1.网络拓扑图g(v，e)
2.每个节点的权重wi(i∈v)和每个边的权重we(e∈e)
3.每条边带宽b(i,j)和最小带宽breq约束；
4.源节点s和目标节点d.
注：将处理延时和传输延时的和作为每个节点的权重，将传播延时作为每条链路的权重
输出：满足最小带宽约束下延时最小的路径path(s,d)
第一步:初始化参数，需要初始化地参数有信息素τ重要程度的参数α，跳数重要程度的参数β,延时重要程度的参数λ,轮回的次数k,每次轮回蚂蚁的只数m,将蚂蚁当前所处的位置赋值为i,判断是否收敛的布尔型变量converge，并初始化为false；初始化每条路径上的信息素τ
第二步:计算当前节点到目的节点的距离d(i,d),(i∈v)
第三步:对于每一轮中的每一只蚂蚁，如当前位置不是终点位置并且还有路径可走(节点i到邻居节点j的链路带宽b(i，j)>b且节点j没有被访问过)即
概率计算公式为：
公式3中的全局启发式因子η(i,j)：
η(i,j)＝(1/d(j,d))β*(1/(wi we))λ,j∈φ(i)(4)，
公式3中的信息素变化情况为：
τij(t 1)＝(1-ρ)τij(t) δτij
第四步：记录每一轮中每一只蚂蚁的爬行路径，并更新每条路径上的信息素。
第五步：判断蚂蚁的路径是否收敛，如果收敛则停止循环。
表2算法1中涉及的符号
算法1详细叙述了我们提出的macou算法，其目的是搜索从节点s到节点d的在带宽约束下的最小延时的路径。表2显示了算法1中涉及的符号。节点s和节点d之间的最佳更新路径的问题可以定义如下:
argmin{delay(s,d)},s.t.b(e)≥breq,e∈path(s,d)(8)
图3说明了macou算法的效率。图3(a)显示了多目标更新树，其中v1是集合节点，其他节点是校验节点。节点的权重是延时的总和，边的权重是带宽的大小。假设最小传送带宽要求是breq＝50mbps，我们需要找到一个具有最小延时的更新树，其每个边e应满足b(e)≥50mpbs。图3(a)中的粗体和所有节点的边构造了多目标更新树。图3(b)描绘了路径path(v1，v7)的搜索步骤。让蚂蚁从v1开始，在初始信息素的相同情况下，由于b(v1，v2)小于50mbps，下一跳是v3。类似地，蚂蚁然后从v3开始，距离d(v2，v7)是2，距离d(v4，v7)和距离d(v5，v7)是1.同时，v5的延时大于v4。所以，蚂蚁选择v4作为下一跳。最后，v4可以直接到达v7。由于macou的正反馈机制，选择路径：v1→v3→v4→v7的蚂蚁数量越多，该路径上的信息素就越多。因此，经过多次迭代后，从v1到v7的路径最终收敛到v1→v3→v4→v7，满足最小更新延时和带宽约束。
类似地，我们可以找到v1到其它校验节点最佳更新路径，并由此构造出图3(a)中的更新树。值得注意的是，acous第一阶段的数据增量收集也可以通过macou以与分发相同的方式构建。
第三步：选择集合节点
通常，关于多个qos度量，最优节点选择是np-hard问题。acous以随机或延时最小的方式简化集合节点的选择。由于集合节点完成数据增量收集和校验块增量分发的特点，所以rn的选择也是一个重要的问题。其中，随机选择的集合节点称为rnn，选择延时最优的集合节点称为orn。rrn是从数据节点中随机选择一个节点作为rn进行更新。尽管rrn可能不是最佳的，但与orn相比，其选择过程更有效。相反，如算法2所示，基于算法1，orn是当有u个节点时更新时，从中选择延时最小的节点作为rn，选择orn的问题可以定义为：argmin，i∈v{sumdelay[i]}，其中sumdely[i]给出如下：
算法2：orn选择过程
输入:1.网络拓扑g(v,e)；
2.每个节点的权重wi(i∈v)和每条边的权重we(e∈e)
3.每条边上的带宽b(i,j)
4.需要更新的数据节点的集合d和校验节点的集合p
输出:orn
第一步：对于每一个需要更新的数据节点di，利用macou算法计算每一个需要更新的数据节点到数据节点di的延时
第二步：利用macou算法计算数据节点d(i)到每一个校验节点的延时。
第三步：将数据节点到每一个需要更新的数据节点和所有校验节点的延时和进行累加求和，记为sum(i)。
第四步：从最小的sum(i)中选择延时最小的节点d(i)作为集合节点
如图4所示，我们进行了一项实验来验证orn和rrn的更新延时对比。在选择计算的成本可以忽略不计的情况下随着更新节点数量的增加，orn变得比rrn更有效。考虑到可用计算资源的有限性，最好对大规模存储系统采用orn。第六节提供了对两种rn的更多评估。
第四步：实验评估
我们在存储集群上开发原型并实现我们macou算法，我们在大规模网络拓扑(≥200个节点)上进行仿真。opnet是众所周知的基于组件的网络模拟器，我们利用opnet进行了大量实验，并以此来评估我们的在异构分布式存储网络系统中的更新方案。除了对大型的随机网络拓扑进行实验外，如图5所示，我们也评估了其他两种典型数据中心网络拓扑的更新方案，即胖树和dcell，两者都具有高网络容量和强大的连接性。我们将属于同一条带的数据节点和校验节点随机部署在不同的集群中。同时，还在相同条件下实现dijkstraospf路由算法。以下介绍了实验中用到的关键参数。
第一步：对不同的数据传输量产生的延时进行实验并评估
首先，我们在不同大小的数据增量δd下比较不同的更新方案。从图6中我们可以看出，随着数据增量的大小的增加更新延时也增加。采用orn和macou的方案不仅优于其他两种方案，而且与传统的dijkstraospf路由算法相比，降低了大约26％的延时。同时，采用orn和macou的方案比采用rrn和macou的方案延时降低了18％左右的，因为orn中的节点选择操作的延时通常是微秒并且与数据传输的延时相比变得可忽略。
图7显示了当k＝9时更新延时随着校验节点的数量的增加而增加。图8显示了当r＝5时更新延时随着需要更新的数据节点的数量的增加而增加。总之，需要更新的节点的数量越多，在更新期间，需要传输的数据包也越多。当网络规模增加或者传输的数据包的数量增加时，我们的方案的优势变得更加明显。总的来说，与基于dijkstraosfp路由的更新算法相比，采用orn和macou的方案减少了30％的延迟。
第二步：对不同规模下的存储系统的更新延时进行实验并评估
图9描述了在不同规模的存储系统下，当需要更新的数据节点和校验节点分别占总节点数量的5％时的更新延时。用于更新的节点随机部署在网络中并定期启动更新过程。随着系统规模的增加，与采用orn和macou的方案相比，dijkstra更新算法的延迟增加得更快。图10显示了当只有5个数据节点和5个校验节点进行更新时的延时。我们发现，采用orn和macou的方案的更新延时优于传统的更新算法，因为随着系统的扩展，数据传输经过的跳数将增加。当节点数超过250时，我们的方案在寻找路由方面的优势更加明显，相同条件下在更新延时减少了28％到30％。
第三步：对不同网络拓扑下的更新延时进行实验并评估
为了进一步研究我们提出的方案的适应性，我们在两个典型的数据中心网络拓扑(即胖树和dcell)下进行了大量的实验，如图5所示。图11和图12给出了各种数据中心拓扑结构下更新延迟的实验结果。从图11和图12可以看出，与以前的实验类似，我们的方案也能够实现几乎相同的延时节省，这表明我们提出的方案具有良好的适应性。
第四步：对蚁群算法的收敛性进行实验并评估
定期更新信息素使蚁群算法能够快速收敛。图13评估了我们的方案的收敛性，当我们设置α＝1，β＝1，λ＝1.6，ρ＝0.4时。如图13所示，更新延迟随着蚂蚁数量的增加而迅速减少，然后达到最佳蚂蚁数量的下限，这意味着搜索的收敛。例如，图13(a)中300个节点的存储网络的最佳蚂蚁数约为500。图13(a)，(b)和(c)表明，较大规模的网络拓扑通常会导致较慢的收敛。例如，当pod的数量分别为6和8时，最佳蚂蚁数量接近250和500，而当pod数量为10时，需要大约1000个蚂蚁才能完成更新路径搜索。图13(d)比较了由200个节点组成的三种网络拓扑下的更新方案的收敛速度。我们可以看到，在dcell拓扑结构中，由于其高效的全局连接性，我们的方案在蚂蚁数量达到230左右时实现了最快的收敛速度。相反，由于随机边缘的复杂性和冗余性，随机网络拓扑收敛速度最慢。
1.一种基于蚁群优化的纠删编码存储系统数据更新方法，其特征在于，包括以下步骤：
1)将所有的蚂蚁分为m轮发放，每一轮的数量蚂蚁为k只；
2)将当前轮蚂蚁当前所处的位置赋值为i，判断是否收敛的布尔型变量设为converge，并初始化为false；初始化每条路径上的信息素τ；
3)计算当前节点i到目的节点d的距离d(i,d)；i∈v；v表示网络节点的集合；
4)对于每一轮中的每一只蚂蚁，若节点i到邻居节点j的链路带宽b(i，j)>breq且节点j没有被访问过，即
5)当本轮所有的蚂蚁爬行结束后，记录每一轮中每一只蚂蚁的爬行路径，如果这只蚂蚁的终点是目的节点，则记录这只蚂蚁从源节点到目的节点的路径和时间，时间即为延时，如果这只蚂蚁的终点不是目的节点，则将蚂蚁在这条路径上的延时记为无穷大，更新每条路径上的信息素；
6)判断蚂蚁的爬行路径是否收敛，如果收敛则停止循环，输出该爬行路径，即最佳路径，以及最佳路径的延时；若不收敛，则返回步骤2)。
2.根据权利要求1所述的基于蚁群优化的纠删编码存储系统数据更新方法，其特征在于，步骤3)中，利用下式选择使概率
其中，η(i,j)＝(1/d(j,d))β*(1/(wi we))λ,j∈φ(i)；η(i,j)即ηij；θ为启发式因子的权重，
3.根据权利要求1所述的基于蚁群优化的纠删编码存储系统数据更新方法，其特征在于，步骤6)中，判断路径是否收敛的条件为：当有连续m只蚂蚁爬行的路径一样时，就判断该路径是收敛的。
4.根据权利要求3所述的基于蚁群优化的纠删编码存储系统数据更新方法，其特征在于，m＝200。
5.一种集合节点更新方法，其特征在于，包括以下步骤：
1)对于每一个需要更新的数据节点di，利用权利要求1所述方法计算其它每个需要更新的数据节点到此数据节点di的延时，即数据增量的收集阶段的延时，利用权利要求1所述方法计算此数据节点di到每一个校验节点的延时，即校验快增量的分发阶段的延时；
2)将数据节点di的数据增量的收集阶段的延时和校验快增量的分发阶段的延时进行累加求和，记为sum(i)；
3)从最小的sum(i)中选择延时最小的节点d(i)作为集合节点。
技术总结