云环境下基于蚁群算法的动态容错技术研究

云环境下基于蚁群算法的动态容错技术研究

　　0 引言

　　云计算是一个热门研究方向，许多企业都相继开发出自己的云端系统进行运算与研究。然而，只要是计算机就会发生错误[1]。在云计算中由于资源的高度动态性和异构性，使云计算平台较传统计算平台出错几率更高[2]。为减少发生错误所造成的损失，需要容错机制保证系统在故障情况下也能持续运行[3]。容错包括故障检测或识别、故障预测和故障恢复3个策略。故障检测或识别通常用于检测故障类型，然后用最合适的方案进行故障诊断。故障预测侧重于根据历史数据预测故障发生的概率，并应用合适的调度策略降低故障概率。故障恢复常用技术有作业复制和检查点[4]。作业复制的优点是不需要重新计算，因为每个作业都会同时分配给不同资源的多个副本，如果其中一个失败，其它作业副本仍然可以处理[5]。但是，这种技术不是很有效，因为作业的副本单独执行可能会占用作业队列。检查点是另一种技术，它要求将运行任务的状态存储在一个已定义的检查点上。如果作业执行失败，则从最后一次保存的状态重新启动任务执行而不是从头开始，这样可极大地节省任务执行时间。

　　针对云计算容错技术，国内外学者进行了相应研究，提出了许多算法：文献[6]提出了周期任务模型的容错调度算法，但是该模型要求所有任务的周期完全相同，文献[7] 研究了动态实时调度算法与速率单调算法。文献[8]讨论带固定优先级实时调度算法，这些算法均没有考虑系统的容错问题。文献[9]针对当前计算机系统计算和存储资源丰富但并行文件系统写带宽提高相对滞后的特点，提出了基于内存缓存的异步检查点容错技术。文献[10]提出了一种主备份的容错调度策略用于对宿主机的错误容忍，其使用主从宿主机结构，需要设置多个宿主机作为备份宿主机，对宿主机资源浪费比较严重。文献[11]提出了增强型蚁群优化算法（Enhanced Ant Colony Optimization， EACO），根据任务和资源数量引入动态蒸发速率确定信息素蒸发速率，确保每个资源处理的任务数量很多时蒸发率很小，否则蒸发率会很高，实验结果表明控制蒸发率可有效平衡所有资源的负载。文献[12]提出了基于信任的蚁群优化调度算法（Trust-based Ant Colony Optimization，TACO），旨在尽量减少作业完成时间，平衡所有可用资源的工作量，同时引入面向资源的信任机制处理资源故障问题。文献[13]通过ACS算法和有向无环图（DAG）方法相结合，提出了一种新的云计算故障管理算法，该算法可提供有效的资源分配但没有恢复操作。文献[14]提出基于遗传算法（Genetic Algorithm，GA）的混合蚁群优化算法，以克服元启发式算法不受控制的性质，但会降低云计算分配性能。文献[15]提出在云计算中使用检查点的容错蚁群优化算法（Fault Tolerance ACO，FTACO），有效利用云计算中的动态资源解决故障和负载平衡问题。文献[16]提出了使用蚁群优化算法进行云计算的容错作业调度以满足服务质量需求，该服务使用资源失败率和基于检查点的回滾恢复策略。在任务执行期间，故障索引管理器将不断与检查点处理程序交互以记录资源故障率，每发生一次故障，都将应用回滚恢复技术以节省执行时间，该算法减少了任务总执行时间，提高了吞吐量和平均周转时间。 　　1 系统建模

　　蚁群优化算法是一种生物启发式算法，为求解优化问题和设计元启发式算法提供一个自适应概念[17]。蚁群优化算法在处理调度和负载均衡时非常有效，且在查找最佳路径过程中出现故障时可构建替代路径，图1为蚁群在查找最佳路径期间出现故障最终找到替代路径的例证[18]。

　　流程如下：①通过蚁群1建立最优资源a的路径路线;②资源a执行任务失败，重新调用提交流程;③通过蚁群1建立替代资源b的新路径，并完成任务的提交和处理;④从不同来源的蚁群2选择由前一个蚁群1构造的最优路径分配下一个任务。

　　本文受蚁群寻找最适合资源的最佳路径概念启发，基于此概念进一步扩展，提出基于蚁群算法的动态容错技术（Dynamic ACS-based Fault Tolerance， DAFT），使蚁群能够在重新提交任务过程中执行资源研究，以确保任何执行失败的任务都被完全处理。此外，进一步改进信息素更新技术，作为一种惩罚失败的资源机制，使其不那么有吸引力以最终减少失败的可能性，并根据资源适当控制任务分配。

　　基于蚁群算法的动态容错算法对每个任务都会生成一个蚁群，根据信息素值选择执行资源。初始化的信息素值首先被启动，以确定所有资源的状态，然后提交队列中的第一个任务。资源的选择是基于信息素初始计算或信息素更新过程的信息素值的量。在执行过程中，每个任务被分成几个检查点，这些检查点将按顺序处理以保持输出的真实性。如果任务执行成功，蚁群会更新全局信息素再执行后增加的信息素;但是，如果在执行过程中出现任何故障，最后一个检查点将重新提交给另一个合适的资源，并且会更新本地信息素，此外每个成功的检查点还将更新本地信息素。最后，资源将与更新的信息素一起发布，用于下一个任务分配。利用重新提交的新资源、检查点技术和资源执行历史记录的方法，减少任务执行和处理时间，提高云计算环境的成功率。

　　2 基于蚁群算法的动态容错技术

　　2.1 算法描述

　　在初始任務期间，每个资源应具有预定义的参数，例如处理器速度、当前负载和带宽以及处理元素的数量，所有这些参数将用来计算初始的信息素值，[PVij] 用于每个资源[i]和任务[j]的组合。 初始信息素值由公式（1）给出。

　　假定所有资源都是相互关联的，这意味着如果任务来自特定资源，那么它就可以分配给所有可用的资源。[PVmatrix] 中的每一行都列出了资源[i]的可能任务列表，任务[j]的可能资源列表。

　　每列中最大的信息素值被蚁群视为最适合的资源，并且该任务分配给选定索引所引用的资源进行处理。 一旦任务被分配，相应[PVmatrix]中的信息素值将根据公式（3）更新全局信息素，以减少分配给当前资源的信息素量，使它变得对下一个蚁群不具有吸引力，让其探索其它资源。

　　2.2 算法流程

　　图2为DAFT算法流程，实现步骤如下：

　　（1）初始化。配置所有参数，根据公式（1）计算每个资源的初始化信息素值，为每项任务生成一个单独的蚁群，在第一次迭代中确定具有最高初始信息素的资源。

　　（2）开始循环。根据蚁群优化算法思想确定最适合的资源，然后发出任务提交信号，通过公式（3）更新全局信息素的值，确实任务是否完成。如果任务完成则结束，否则继续判断任务执行状态。如果任务执行成功就保存检查点，增加成功计数，并根据公式（1）-公式（5）更新局部信息素值。如果任务执行失败，则检索最后一个检查点，重新提交，增加失败计数，并根据公式（5）更新局部信息素，重复步骤（2）操作。

　　（3）任务状态。任务完成时，终止执行。

　　3 实验结果

　　为了验证本文的DAFT算法性能，定义平均成功率为70%（0.7），误差范围用标准偏差±0%（0.0）～±30%（0.3）表示。使用具有标准偏差的伪随机算法分配成功率，在初始化过程中定义每个单独资源范围。每种资源具有不同的成功率，且这些信息在资源分配期间不被蚁群知道。为确保实验的可靠性，每个资源都设置为具有相同的处理能力，参数如表1所示。

　　在云计算环境中，除了处理能力之外，每个可用资源都具有不同的适应性。在这种情况下，可使用最小和最大适应值形成适应范围。实验结果表明，启发式能够改善任务分配过程并最终提高云计算环境性能。随着执行深入，成功和失败的次数被记录并最终影响资源信息素值的蒸发。可根据资源适应度动态分配任务，如资源的成功率为0%，则分配给它的任务量最少。另一方面，如果资源的成功率非常高，则会分配最多的任务。除了在调度或重新提交过程中考虑资源适应性以外，检查点还允许从最后保存的状态重新提交失败的任务，这大大减少了处理时间，因为任务不需要从头开始。

　　4 结语

　　为了提高云计算容错性能，本文提出在云环境下基于蚁群算法的动态容错技术，利用检查点回滚技术消除从一开始就重新启动任务，减少了任务总执行时间，提高了吞吐量和平均周转时间。在资源分配期间，根据其适合度通过蚁群算法的启发式能力选择最佳资源，不但减少了每个任务的处理时间，还提高了云计算环境的成功率。与TACO算法和FTACO算法进行比较，仿真结果表明，本文方法在容错性上明显优于TACO算法和FTACO算法，最大限度提高了云环境下的容错性能。但是，在任务调度过程中，保存检查点的数量太多会加大数据量计算，因此如何控制保存检查点数量是后续研究目标。