考虑负载平衡的科学工作流容错聚类算法研究

高玮军，张春霞，杨 杰，师 阳

兰州理工大学 计算机与通信学院，兰州 730050

1 引言

科学工作流为科学研究提供了一种流程定义和自动运行的平台，可以屏蔽底层繁琐的计算过程以此简化科学实验。科研人员只需关注专业问题的处理，从而使得科学实验能够更便捷、高效地进行。在科学研究领域，例如：生物基因学、天文学、物理学、地震学等大规模应用中，工作流包含许多细粒度计算任务，任务间存在复杂的依赖关系。这些任务通常只需要几秒钟或几分钟的执行时间，任务实际执行时间可能比系统开销（系统中除执行用户计算以外的其他开销）更短[1]。系统开销是分布式计算中普遍存在的问题，也是科学工作流应用程序的性能可以显著提升的主要原因[2]。随着网格计算、云计算等分布式环境的出现和硬件设备的优化，系统开销问题更加凸显，严重影响了科学工作流的执行效率。

任务聚类方法对具有某一特征的任务进行聚集生成聚类，系统以类为单位进行调度。该方法虽然增加了作业运行耗时，但是显著地降低了系统的总开销[3]。文献[4]结合计算任务划分技术与任务聚类，解决了数据密集型地震模拟工作流（CyberShake）在求解时间方面所面临的问题。细粒度任务的低性能问题在广泛使用的分布式平台中更加凸显，其中资源的调度开销和队列等待占用的时间较长。文献[5]为了减少工作流的总运行时间和云资源使用，提出了一种基于任务分组和复制技术的调度算法，来降低用户执行成本。针对跨地域跨学科的科学研究工作中，普遍存在数据传输开销严重影响系统运行效率的问题，任务聚类方法被用于数据放置策略和资源调度策略中[6]，以减少数据传输所产生的时间开销。科学工作流执行过程中存在故障风险，而大部分任务聚类算法及其优化算法并未考虑故障对系统的影响。

在任务聚类算法执行后，工作流系统以类为基本单位进行调度和执行，类中有一个任务失败，整个类被标记为失败。解决任务失败问题最常用的方法是重试失败的作业、备份技术、设置检查点[7-9]。对于运行周期比较长的作业，备份技术会造成严重的资源浪费。为了减少资源浪费，可以按周期检查作业执行情况，以限制重试的任务量。由于检查点机制实现相对重试技术较为复杂，执行检查点的开销会同样会限制系统的运行效率。Chen等人[10]针对瞬时故障提问题提出了任务/作业故障模型，并提出了动态重聚类算法（DR）。随后又提出了三种任务容错聚类方法，可以有效地解决任务失败的问题[11]。文献[12]提出了一种新的基于簇的异构最早完成时间（CHEFT）的启发式算法，利用资源预配置后的空闲时间运行已失败的任务，来增强云环境中科学工作流的容错机制。文献[13]对现有的云平台容错机制进行分析，对科学工作流应用程序中出现的特定故障，讨论和推荐解决故障的容错方法和容错模型。现有的容错聚类算法忽略了聚类可能会导致负载不平衡问题[14-15]，这种不平衡会导致下一层任务的释放延迟，系统的总运行时间也会随之增加。

工作流分解是处理负载不平衡的常用技术[16-17]，该方法将科学工作流划分成多个子工作流，子工作流可以高效地并行执行。但是对工作流进行分割会增加中间数据管理开销，同时，可以进行分割的工作流种类也比较受限。文献[18]提出了一种基于路径平衡的费用优化算法，能够有效地增大了费用优化空间。文献[19]提出了三种衡量指标来量化描述不平衡问题，根据运行时间不平衡、依赖关系不平衡、位置关系不平衡提出了三种平衡聚类算法，有效缩短了系统总运行时间。

容错聚类算法在有效解决故障问题的同时，也面临着负载不平衡问题，本文结合水平运行时间平衡策略与现有的容错聚类算法，提出了一种平衡重聚类算法。通过平衡聚类的运行时间以实现负载平衡，在提高系统运行效率的同时保证系统的健壮性。

2 定义与基础理论

2.1 动态重聚类（DR）

负载不平衡：在不考虑任务运行时间存在差异的情况下将科学工作流中多个任务合并为一个聚类，可能会导致聚类的之间的运行时间差异较大，造成虚拟机运行时间严重不平衡。

如图1 所示，任务 t 1，t2，t3 和 t 4 为相互独立的任务，其中t1，t2，t3，t4 的任务运行时间分别是10 s，10 s，30 s，30 s。

图1 初始任务集

当有两个聚类时，水平聚类（HC）方法运行结果如图2 所示，将任务t1 和任务t2 合并为聚类J1，将任务t3和任务t4聚为J2。则聚类J1的运行时间为20 s，聚类J2的运行时间为60 s，聚类J1 和J2 的运行时间严重不平衡。由于下一层任务释放的必须等待上一层所有任务运行完成，即在60 s后下一层的任务才可以释放。

图2 水平聚类

负载不平衡衡量指标：本文采用水平运行时间方差（Horizontal Runtime Variance，HRV）来描述运行时间不平衡问题。HRV描述了一组任务或作业运行时间的差异大小，HRV定义如下：

HRV 表示在同一水平层中所有任务/聚类运行时间的方差。公式中分子σ(tv)为所有任务/聚类运行时间的标准差，μ(tv)为该层中任务/聚类运行时间的平均值。在μ(tv)相同的情况下，σ(tv)的值越大，HRV 的值也越大。

初始任务集图1中，μ(tv)=20 则：

由于科学工作流任务间存在依赖关系，下一层作业的释放时间取决于上一层任务中最长运行时间。如图2，HC算法运行后，μ(tv)=40 得：

水平运行时间平衡衡聚类（HRB）算法根据任务运行时间的差异进行聚类操作，如图3 所示，运行时间较长的任务t3 和运行时间较短的任务t1 合并至一个聚类中，任务t4 和任务t2 合并至一个聚类中。聚类J1 和J2的运行时间都为40 s，下一层任务的释放将在40 s后，计算可得：μ(tv)=40，

图3 水平运行时间平衡聚类

对比HC 算法在60 s 后释放下一层任务，水平运行时间平衡聚类算法（HRB）将在30 s后释放下一层任务，HRB 算法明显优于HC 算法。较高的HRV 值意味着下一层任务的释放较迟。因此，为了提高运行性能，减少作业运行时间方差很有意义。

2.2 容错机制

在科学工作流执行过程中，故障频繁发生，严重影响科学研究工作。工作流管理系统为工作流执行提供软件环境，主要负责工作流的定义和管理。科学工作流管理系统中的容错机制主要用于解决科学工作流流程组合结构设计异常等问题，主要有以下几种：（1）基于其他任务技术。其他任务是指当前任务的另外一种实现方式，如果流程中正在运行的任务出现错误，则启动另外一种实现方式。（2）备份技术。为全部工作流任务创建多个备份，并将备份任务分配至在不同数据节点上运行，类似于Hadoop 中的文件存储系统。多个备份任务将同步执行，一旦故障发生，直接调用备份任务代替原任务继续运行。（3）修复工作流方式。在工作流第一次运行时，科学工作流管理系统记录下执行过程中间所产生的错误信息，然后根据记录数据，修正工作流组件组合方式和运行参数，经过多次运行和修改，故障率可以大幅度降低。（4）用户自定义异常处理。用户拥有一定权限，可以根据自己的需求根据经验，按照自己的意愿设计错误处理方案。

流程级的容错机制，大多以流程为单位进行容错，其他任务技术、副本技术都对资源和成本浪费较为严重，而修复工作流对于执行次数少或者初次执行的科学工作流，执行效率太低。所以研究人员开发了一系列任务级容错技术，用于科学工作流调度和执行阶段的故障恢复，细化了故障恢复单元，降低故障恢复成本。任务级容错主要包括：重试技术、副本技术以及检查点技术。其中，Chen等人[10-11]对科学工作流中故障问题进行了深入的研究，所提出的重聚类算法，重新运行发生故障的任务，改变了传统的重试技术重新运行所有任务的模式。重聚类算法在有效避免重试技术和备份技术所造成的资源浪费的同时，考虑聚类数量等方面的优化，很大程度地提高了科学工作流系统的运行效率。

科学工作流通常需要大量复杂的分析和计算，相对其他类型工作流故障概率更高。并且科学工作流任务之间存在很强的约束关系，如果其中一个任务发生故障，则与其有依赖关系的所有后续任务都需要重新执行。这表明故障发生后，故障恢复规模较大。为了能够提高重聚类算法性能，减少任务故障所带来的损失。本文从负载不平衡角度，研究对重聚类算法进行改进，提出了平衡重聚类算法（BR），在任务调度和执行阶段进行故障恢复。

2.3 故障模型

故障的产生具有随机性和不确定性，因此需要根据历史数据对故障的产生进行建模，通过故障模型评估容错算法。在文献[1]中已经证明系统开销可以用Gamma分布或者Weibull 分布来描述。Schroeder 和Gibson 已经证实[20]，任务失败的到达间隔时间更符合Weibull 分布（由形状参数0.78定义）。文献[21]中指出，Weibull分布、Gamma分布和Lognormal分布是估计一组工作流任务运行时间的最佳选择。在本文中，采用Gamma 分布模拟任务运行时间(t)和系统开销(S)，采用Weibull 分布模拟故障间隔到达时间(u)。

Gamma如公式（1）所示，Gamma分布通常使用两个参数描述：形状参数(α)和比例参数(β)。形状参数决定分布的形状，比例参数决定分布的拉伸或收缩。Weibull分布是可靠性分析和寿命检验的理论基础，Weibull 分布形式与Gamma分布相似，α表示形状参数，β表示比例参数。

已知a、b为先验知识，D为观测数据，β为目标估计参数。由贝叶斯概率论可知，当观测数据集已知时β的后验分布定义如下：

公式中的D可以代表失误间隔时间(u)、任务运行时间(t)或者系统开销(S)的观测值。P(β|a,b)是已知的先验知识，P(β|D,a,b)是需要计算的后验概率。定义失误到达间隔时间u的观测值为X={x1,x2,…,xn} ；任务运行时间t的观测值表示为RT={t1,t2,…,tn} ，采用S={s1,s2,…,sn} 表示系统开销S的观测值。通过已有的观测参数，可以得到β的估计值。

使用Weibull 分布来建模失误到达时间间隔u，其中参数α为已知形式参数（由经验值给出），只需要计算规模参数β。具有已知形状参数α的Weibull分布与逆Gamma 分布为共轭对，这表明如果先验分布遵循逆Gamma 分布，形状参数为a，比例参数为b，则后验分布服从逆Gamma分布，形式如下：

对比例参数β进行最大似然估计估计，β的估计定义如下：

通过相同的步骤，对总运行时间T、系统开销S以及故障到达时间u等需要提前预知的参数进行估计，从而建立任务故障模型。通过调整故障模型中故障到达间隔时间（故障出现频率），对所提出的算法进行测试。

3 容错聚类算法

3.1 选择重聚类（SR）

选择重聚类算法在作业运行结束后，输入标记运行失败的聚类作业，筛选出作业中运行失败的任务，并将这些任务合并到新的群集中，提交至主机再次执行。算法1为选择重聚类算法的伪代码。

算法1选择重聚类

输入：W，科学工作流；C，每个类中的任务数量

输出：W，科学工作流

1.procedureRECLUSTERING（J）

2.TL←divideAtLeve（lJ）

3.Jnew←{ }

4.forTask∈TLdo

5. iftis failed then

6.Jnew.add(t)

7. end if

8.end for

9.W=W-Jnew

10.returnW

11.end procedure

3.2 动态重聚类（DR）

动态重聚算法对选择重聚类算法进行改进，考虑聚类规模（聚类中任务数量）对故障的影响。根据故障到达时间间隔、任务规模动态地估计出使得系统开销可以取到最小的聚类任务数量(K)，在每次重运行时，动态更新K值，根据K值进行聚类划分。动态重聚类算法的伪代码如算法2所示。

算法2动态重聚类

输入：W，科学工作流；C，每个类中任务的数量

输出：W，科学工作流

1.procedureRECLUSTERING（J）

2.TL←DivideAtLeve（lJ）

3.Jnew←{ }

4. forTask∈TLdo

5. iftis failed then

6.Jnew.add(t)

7. end if

8. ifJnew.size()＞Kthen

9.W=W+Jnew

10.Jnew←{ }

11. end if

12.end for

13.W=W+Jnew

14.returnW

15.end procedure

3.3 平衡重聚类（BR）

本文旨在解决重聚类算法在聚类过程中所面临的负载不平衡问题。平衡重聚类算在SR 算法的基础上，根据各层任务运行时间的差异，来调节聚类总运行时间，以达到负载平衡的目的。负载平衡过程类似于HRB 算法，首先根据任务运行时间长短对故障任务列表进行排序。然后进行聚类操作，每次分配运行时间最长的任务至总运行时间最短的聚类。

筛选出运行失败的任务后，负载平衡的实现仍面临一个关键问题，即聚类规模的确定。聚类个数与总运行时之间存在约束关系。如下所示：

R=min{MLE(T)}

根据需重运行任务的规模、可用资源数量，估计出使得总运行时间最小的聚类个数R。以R作为已知数据输入，进行平衡重聚类。算法3展示了平衡重聚类算法的伪代码。

算法3运行时间平衡容错聚类

输入：W，科学工作流；R，每一层作业中的聚类数量

输出：W，科学工作流

1.procedureRECLUSTERING（W，R）

2.TL←DivideAtLevel(W,level)

3.Jnew←{ }

4. fortask∈TLdo

5. iftis failed then

6.Jnew.add(t)

7. end if

8. ifJnew.size＞Rthen

9.C=C+Jnew

10.Jnew←{ }

11.end if

12.end for

13.W=W+Jnew

14.end procedure

15.procedureMERGE(TL,C,R)

16.ifi＜Rthen

17.Jnew←{ }

18.end if

19.CL←{ }

20.sort(TL)

21.fort∈TLdo

22.J.add(t)

23.end for

24.fori＜Rdo

25.CL.add(Ji)

26.end for returnCL

27.end procedure

选择重聚类将聚类规模简单定义为运行失败任务的数量，并不考虑聚类大小对SR 算法的性能影响。但是，实际的最佳聚类规模会随着故障任务的数量和可用资源数量的变化而改变。动态重聚类算法弥补了选择重聚类算法的不足，根据可用资源状况和任务规模计算出最佳聚类规模，每次重新运行时动态地调整聚类规模。与SR 算法和DR 算法相比，BR 算法在解决重聚类算法中负载不平问题的同时，根据资源数量和故障规模计算最佳聚类数，兼并HRB 算法和DR 算法的优点，很大程度地提高了重聚类算法的性能。

4 实验与分析

4.1 实验设置

实验在五个常用科学工作流应用程序上进行，评估了选择重聚类算法、动态重聚类算法和平衡重聚类算法的性能。五个科学工作流应用程序分别为：天文学应用程序（Montage）、激光干涉引力波天文台（LIGO）、地震应用程序（CyberShake）、表观基因组学（Epigenomics）和细菌学应用（SIPHT）。文献[22]详细分析和描述了五种工作流各自的结构和特征。

实验环境由WorkflowSim[23]仿真器提供，Workflow-Sim作为常用的科学工作流实验仿真环境，提供了20个虚拟机（VM），每一个VM 都有512 MB 的内存，用于模拟真实的分布式环境。平台提供了五种科学工作流的仿真实现、基础调度算法、资源分配计划以及测试程序。测试数据集均由WorkflowGenerator[24]生成，文献[24]中已经证明WorkflowGenerator 的可用性及其合理性。本实验在平台调度阶段实现三种重聚类算法，调用测试程序对算法性能进行评估。

实验首先设置了不同的u（失败到达间隔时间）值，观测不同故障率情况下，三种重聚类算法实现后系统总运行时间变化。u的值越高故障产生的概率越小，u的值越低故障产生的概率越大。然后，固定u值，观测采用BR算法运行前后五种科学工作流负载平衡衡量指标HRV的变化。根据变化情况来评价算法在负载平衡方面的成果。

4.2 实验结果及分析

实验中u在任务平均运行时间（平均运行时间由文献[24]计算得出，如表1所示）的1～10倍范围内取值，这样工作流运行时间合理，并且算法的性能差异能够很好地体现。下面为五个科学工作流中三种重聚类方法的性能对比。

表1 五种科学工作流的特征

Montage：图4 显示了Montage 工作流的测试结果，可以看出当故障到达时间间隔u取值较小时，BR算法、DR 算法性能明显优于SR 算法。随着u逐渐增大时，BR、DR、SR 算法的性能结果趋于相等。这表明当故障出现的频率越高，BR算法和DR算法对系统性能提升越大。当u取最小值20 s 的时候，对比BR 算法与SR 算法，性能增益最高为42%。随着u的增大，性能增益逐渐降低。在u=100 s 时，性能增益为−2.76%。BR 算法相对DR算法的性能增益最高为7.14%，随着u的增大，性能增益逐渐降至0.61%。

图4 Montage工作流中三种重聚类算法性能对比

CyberShake：如图5 所示，三类容错算法在Cyber-Shake工作流中测试结果的整体变化趋势与Montage工作流的变化趋势相似。在u=100 s时，相对SR算法，BR算法的性能增益提高了61.5%，随后逐渐降低。BR 算法相对DR 算法的性能增益最高为3.79%。当u>500 s时，明显看到BR、DR、SR之间的性能增益幅度非常小，性能增益均在0.45%以下。

LIGO：LIGO 工作流中三种重聚类算法的实验结果如图6所示，BR算法相对SR算法性能增益最高提升了43.0%，最低提高4.2%。当u从800 s增加到2 000 s，BR 相对DR 算法的性能增益逐渐降低，从0.93%降低到−0.19%。这表明BR 算法的性能提升与DR 算法相近。在u=1 000 s处，SR算法性能略高于DR、BR算法。

图5 CyberShake工作流中三种重聚类算法性能对比

SIPHT：图7 为三种重聚类算法在SIPHT 工作流中的实验结果。不同于上述三种工作流中，BR相对SR的性能增益随着u的增加而降低。当u取2 500 s 时，BR算法相对SR的性能增益为61.54%。当u分别取3 500、4 500、5 500时，BR算法相对SR的性能增益分别为9.1%、−0.35%、6.35%。同时，相对DR算法，BR算法的性能增益随u的增加逐渐降低，从7.89%降到了−0.39%。

Epigenomics：如图8 所示，为三种重聚类方法在Epigenomics工作流中的实验结果。与其他四种工作流相比，BR 算法的性能增益明显高于其他四类工作流。BR 算法相比SR 算法性能增益最高为84.0%，最低为50%。同时，相对于DR 算法，BR 算法性能增益高达18.75%，最低为4.55%，这是一个比较可观的提升。

图8 Epigenomics工作流中三种重聚类算法性能对比

对比三种重聚类算法在五类工作流中的性能表现，可以看出随着u的变化，性能增益所变现出来的规律有很大差别。为了更好地解释这一结果，只能根据工作流的机构以及任务运行时间特点进行分析。表1 列举了五类个科学工作流任务的平均大小和平均任务运行时间，但是缺少了任务运行的细节。因此，设计了第二组实验，在取定u值的情况下分析BR算法对负载（运行时间）的影响。

根据前面的实验结果选取平均任务运行时间的一倍作为u值，因为u取该值时，三种重聚类算法性能间的差异更加明显。取定u值后，分析对比五个科学工作流中执行BR 算法前的HRV 和执行BR 算法后HRV 值的变化，其结果如图9所示。

Montage：如图9（a）所示，由于大多从层均为单任务，因此HRV都为0值。而第2、5层HRV值降低非常明显，下降率分别为85.3%、98.1%。

CyberShake：如图9（ b）所示，HRV 值在 B R 算法运行前后的下降率最大为55.9%，最小为30.4%。

LIGO：如图9（c）所示，在第1层中HRV的下降率最高为82.8%，而其他层都低于50%。

SIPHT：如图9（d）所示，在第3 层HRV 下降率最高为41%，其他层HRV下降率均小于30%。

Epigenomics：如图9（e）所示，相对其他工作流BR算法运行前后HRV 的下降率，该工作流HRV 下降率较低，最大下降率仅为38.9%。

分析图9 中五个实验结果，可以发现较Montage、LIGO中BR算法运行前后HRV的值都非常小，而SIPHT中HRV的值远高于其他四个的值。结合表1可知，LIGO工作流程的平均任务运行时间相对较短，即使BR 算法运行后平均每层HRV 的值降低了将近50%，而最终的系统开销相对DR 算法只提升了0.93%，而Montage 中HRV 值的变化最大，在第二层中，HRV 值减小了68%，即使Montage 的平均运行时间相对较小，但BR 算法对于DR算法的性能增益为7.14%。SIPHT工作流的结构非常不对称，HRV 值相对较高。BR 算法可以通过平衡运行时间进行优化，DR 算法可以通过动态调整聚类大小进行优化，而SR 算法的随机性较大。这就可以解释BR 相对SR 算法的性能增益不规律问题。Epigenomics工作流的HRV 值的下降率平均为25%，在level=4 时，HRV值仍为0.64，相对较高。根据表1可知，Epigenomics的平均任务运行时间是Montage 的300 倍，所以将近20%的运行时间平衡导致了系统开销18.75%的提升。

图9 五种科学工作流中执行BR算法前后HRV的对比结果

结合两组实验结果分析，可知当故障出现频率较高时，平衡重聚类算法性能提升明显高于动态重聚类算法、选择重聚类算法。当工作流任务结构不对称（HRV值较高的SIPHT 工作流）或运行时间严重不平衡时（例如，Epigenomics 工作流），即使故障率较低下，BR 算法对工作流系统的运行效率仍有较大的提高。

5 总结

为解决容错聚类算法面临的负载不平衡问题，本文提出了一种考虑任务运行时间平衡的容错聚类算法BR，通过调整模型中故障出现频率测试算法性能。实验结果表明，在故障率较高的情况下，与现有的任务容错聚类方法相比，BR 算法显著降低了科学工作流的完工时间，在故障率较低的情况下，平衡容错聚类方法在Epigenomics 工作流中表现最佳。BR 算法采用水平运行时间平衡方法来解决负载平衡问题，未来的工作可以考虑任务间距离平衡或依赖关系平衡方法与容错聚类方法的结合。根据不同工作流呈现出的不平衡问题，推荐相应的平衡重聚类算法。