基于布谷鸟算法的Storm集群动态负载均衡策略

龙 笑，周 良，郑洪源

(南京航空航天大学 计算机科学与技术学院，江苏 南京 210016)

0 引 言

随着物联网和社交网络的快速发展，流数据的规模不断增长，流处理在交通监测、气象观测和银行交易管理等领域都有着广泛的应用。以无人机货运实时流数据为例，其产生的流数据具有到达速度快、到达时间持续和动态改变等特点，传统地大数据批处理框架已无法满足实时性的需求。Storm作为分布式实时数据计算系统，可以同时对数以亿计的流数据进行计算，比其他大数据计算框架更适合于实时流数据的处理。在数据处理要求实时性和高效率的情况下，节点的有效管理和资源的合理分配显得愈发重要，负载均衡的重要性也愈发突出。Storm实时计算应用程序通常是计算密集型应用程序，负载平衡在Storm实时计算应用程序的性能中起着决定性作用。

然而Storm默认调度在负载均衡方面的表现却无法令人满意，存在着较多的问题。首先，Storm平台在默认的任务调度上采用的是轮询调度(round robin scheduling)，该算法将用户提交的拓扑中包含的任务平均分配给每个工作流程，再将各工作进程平均分配到各工作节点上。由于其忽视了节点间性能和负载的差异，致使集群的资源利用率不高。其次，在集群节点动态增删后，Storm无法根据集群计算资源的变化做出有效的策略调整，影响负载均衡。此外，Storm默认任务调度算法只关心CPU利用率，而忽视了内存、磁盘IO、网络带宽等节点资源，这可能导致工作节点内存不足和网络阻塞等问题。

针对Storm集群动态负载实时调度优化问题，文中提出了一种基于布谷鸟搜索算法的Storm集群动态负载均衡策略(DLBSCSA)。该策略综合考虑了节点的CPU、内存、网络带宽、磁盘IO等资源，根据实时监测到的负载数据为集群的节点性能赋予权值，通过布谷鸟搜索算法的寻优过程动态调整权值，计算出节点上任务的分配权重，从而完成资源的动态分配，以此达到节点负载的均衡。

1 相关工作

截止目前，愈来愈多的人开始关注Storm默认调度算法的优化。文献[1]提出了一种资源感知在线调度算法RStorm，它利用任务需要与工作节点的静态资源之间的关系来实现调度，但是，由于资源需求完全依赖于人工设置，因此无法在数据流快速变化的情况下实现在线调度。文献[2]根据监测到的数据实现实时调度，但改进后的系统延迟略有提高。文献[3]提出在线调度算法TStorm，通过实时监测任务负载将通信开销大的任务动态分配至空闲资源较多的节点上，但需人为设定拓扑所需的节点数量。

文献[4]结合对历史任务的恢复和对单个节点的任务调度等不同情况针对Storm进行了改进。文献[5]提出了针对服务质量感知的调度算法，使Storm适用于地理信息系统的研究。文献[6]提出Storm环境下离线和在线的两种自适应调度算法，分别用于拓扑运行前后的结构分析和实时负载监测，但执行时未将当前任务与其直接通信的所有任务全部考虑进来，容易陷入局部最优。

文献[7]引入拓扑热边的概念，为减少通信开销，将热边关联的源和目标任务调度到同一节点，但忽略了非热边的调度。文献[8]提出一种两阶段调度算法，分别降低了进程间和节点间的通信开销，但并未考虑到各任务自身计算开销的差异性。文献[9]中提出了一种基于权重的任务调度算法，该算法根据每个任务的CPU资源和任务之间的数据流大小确定拓扑的点权重和边权重，并构造每个节点承载的任务集，但其资源权重为静态的，在面对集群节点资源变化的情况中表现不佳。

任务调度是非常有代表性的NP难问题，对其他物种行为特点进行模仿能够较好地解决此类问题，其中比较典型的有蚁群算法、遗传算法及PSO算法，但它们存在诸如实时性差、早熟收敛、后期震荡的问题。而布谷鸟搜索算法是Yang等[10]在2009年提出的一种智能优化算法，该算法具有模型简单、可调参数少及收敛速度快等优点，目前已被许多领域应用。文献[11]针对作业调度问题提出一种模拟退火下布谷鸟算法；文献[12]基于布谷鸟搜索算法，提出一种新的多处理器任务调度算法；文献[13]针对当前云计算资源调度开销大等难题,提出了改进布谷鸟搜索算法的云计算任务调度方法。

2 DLBSCSA相关描述及定义

2.1 Storm默认调度机制

Storm的计算结构[14]是Topology，即一个有向无环图，其分别由stream，spout和bolt组成。Topology的核心数据结构是tuple，数据流就是由无数的tuple组成的实序序列。spout及bolt构成了组件，spout把stream分割为无数拓扑，并依据Topology转发相关拓扑。bolt则是数据计算单位，由上游获取拓扑并在处理后将结果转送下游bolt。Storm正是利用无数Topology来执行实时流处理的。

Storm的默认调度机制有两个主要步骤：

(1)将executor线程分配至worker；

(2)将worker分配至工作节点。

默认调度使用轮询的方式，将executor分送到相应worker上，然后当集群slot资源足够时,可以把任务均衡地分派到集群工作节点中。若slot缺少时，当前已有的slot将被分派所有任务。

图1 用户提交的Topology

以图1中用户提交的Topology为例，假定当前集群有3个工作节点且节点资源均很丰富，则在用户提交Topology后默认调度算法对任务的分配如下：

(1)工作节点1:T1,T4,T7；

(2)工作节点2:T2，T5，T8；

(3)工作节点3:T3，T6，T9。

默认调度算法未考虑到不同工作节点的性能和负载差异，致使节点资源利用率不高，这将对Storm处理的实时性产生较大影响。同时，默认调度策略更关心节点的CPU资源使用情况,而忽视了内存、磁盘、网络等其他类型的资源，这样可能会造成工作节点内存不足、网络堵塞等问题。

2.2 动态负载相关定义

Storm中的任务分配过程可描述为将一个Topology中的n个tasks分配到m个Supervisors工作节点上执行的过程。初始描述为:

T={t1,t2,…,tn}表示n个任务集，其中ti(i=1,2,…,n)表示第i个task。

S={s1,s2,…,sm}表示m个Supervisor节点集，其中sj(j=1,2,…,m)表示第j个Supervisor节点。

为反应CPU占用率、内存占用率等资源的利用情况，用向量L表示m个节点的动态负载向量L=[l1,l2,…,lm]。设集群系统的节点sj的负载为L(sj)，为计算L，引入集群节点性能向量U，有：

(1)

计算节点负载后，即可计算节点分配的权重(占比)向量W，W=[W1,W2,…,Wm]，其中Wi的计算定义为：

(2)

根据节点分配的占比向节点分配任务。

3 DLBSCSA设计

3.1 问题建模

根据DLBSCSA相关描述及定义，DLBSCSA设计的实质是根据系统当前或最近状态决定如何给分布式系统的每个节点分配任务，即找到最优的节点任务分配权重。所以，当集群节点的负载达到其最大承受程度时，集群能够以最佳方式运作，系统的整体性能最好。而为了达到资源的动态负载均衡，最主要的是根据集群运转情况实时地计算出最优的资源分配权重。

动态负载均衡模型可以描述为：向m个节点分配n个任务，综合多个性能指标加权计算反映节点的负载向量L，通过寻找最优的权重向量α，使负载向量L能够正确地反映集群系统的负载。再利用选择函数，根据历史信息和动态权重合理而均衡地选取节点来对负载进行处理，使整个任务具有最短的处理时间和最大的吞吐量。由于权重向量α随集群的负载情况而变化，需要对其进行实时检测并动态地计算最新的α。动态负载均衡模型如图2所示。

图2 动态负载均衡模型

动态负载均衡的最终目的是减少集群响应时间，做到任务的实时处理。为此将目标函数定义为集群系统的平均响应时间，目标函数越小表示集群系统的总体性能越好。即

F=∑Res/m

(3)

其中，F为目标函数；Res为集群系统响应时间向量。由上文知，Res由节点负载向量L，任务向量T和选择函数Sel来确定，即：

Res=(L,T,Sel)

(4)

其中选择函数Sel定义任务和节点间的映射关系，根据当前任务c、负载分配历史向量h及节点任务分配权重向量W来选取恰当的节点对当前任务进行处理，若选择的节点为sup，则有

sup=Sel(c,h,W)

(5)

根据式3知，目标函数值越小说明集群的整体性能越好，即当布谷鸟搜索算法求得的权重向量α收敛时目标函数最小：

(6)

因此，基于布谷鸟搜索算法的Storm集群动态负载均衡策略即找到目标函数的最优解，从而可以将节点的性能权重α作为目标，通过布谷鸟搜索算法寻求α的最优解。

3.2 权重向量的寻优

根据上文，为实现资源的动态负载均衡，文中引入了布谷鸟搜索算法，通过其寻优过程为节点的CPU、内存、磁盘IO及网络带宽等资源赋予动态的权值，即寻找节点性能权重向量α的最优解。

布谷鸟搜索算法是一种随机搜索算法，它将布谷鸟寄生孵育雏鸟的生物学行为与一些鸟类和果蝇的莱维飞行行为结合起来。在本质上，布谷鸟找到宿主鸟巢的过程是随机的，为了对其进行模拟，需要先设定以下几个规则：

(1)布谷鸟每次产卵一枚，并采用随机方式寻找宿主巢穴；

(3)可搜寻的巢穴数量是固定的，宿主鸟巢主人可以发觉外来卵的概率是P，鸟蛋一经发现即会被宿主移除，或直接遗弃该鸟巢。

基于以上3个理想状态，布谷鸟寻找宿主鸟巢的位置更新公式如下：

(7)

在实际应用中，鸟巢的位置表示问题的解的有效取值范围，鸟巢的适应度函数值表示目标函数的值。文中算法由于寻优的目标是一个矢量，因此假定每个鸟巢中有若干个卵，分别代表一种解决方案，在更优新解代替旧解的过程中寻找到权重向量的最优解。因此位置更新公式为：

(8)

布谷鸟标准算法中的初始步长因子通常被设计为固定值，而之后步长的设定在寻优过程中缺乏自适应，这样会导致算法收敛性能下降，影响算法准确性。因此文中在莱维飞行中加入自适应方法设置动态的步长因子。将步长设置为第t次迭代中第j个解集中各解与初始值之间距离的平均值，即：

(9)

为最大限度地避免因步长过大而产生的算法最优解的遗漏，则位置更新公式最终可表示为：

(10)

若想对产生的解进行优越性的评估，目标函数需经计算以具体数字形式体现，由此定义了一个适应度函数：

(11)

函数fitness作为评价解的数值基准，评估解在时间效率方面的优越性，适应度越小表示解越优。其中矩阵ETC中的值表示任务i在第j个节点上完成所需的理论时间，因此ETC矩阵可表示为：

美国官员和一些科学家希望到21世纪20年代中期能形成一种有效的治疗方案，但临床试验的挫折加剧了人们的担忧。纽约市西奈山伊坎医学院阿尔茨海默病研究员塞缪尔·甘迪（Samuel Gandy）说：“我确信我们无法实现2025年的目标，看来我们的承诺要落空了。”对于把这么多钱仅仅集中于阿尔茨海默病的研究上，有些研究人员也表示出担心。加州诺瓦托市巴克老龄化研究所的生物学家朱蒂·坎皮西（Judy Campisi）想知道，是否应该多拿出一些资金来支持基础研究，对于这样有针对性的资助，生物医学界“怀有复杂的心情”。

(12)

文中ETC矩阵的初始值通过几次测试求均值后得到，由于任务不断分派，未完成的任务数将越来越少，任务理论完成时间也会发生变化[15]。因此，任务的理论完成时间的更新公式定义为:

(13)

文中的布谷鸟搜索算法可以描述为：

(1)初始化算法相关参数，确定宿主鸟巢的数目n，搜索空间维数d，外来鸟蛋被发现的概率P，设定全局最大迭代次数Max，步长初值a0，适应度阈值Val。随机选择鸟窝的位置，设定t初值为0，鸟蛋代表的就是权重的解

(2)利用fitness函数(式11)对鸟窝位置的优越性进行评估，并对最佳鸟窝进行记录

(3)While(未达到最大迭代次数Max或适应度函数大于阈值Val) do

(4)根据式9计算莱维飞行的动态步长因子

(5)根据式10更新鸟巢位置

(6)将当前解作为计算负载向量L的参数，代入模型中得到理论完成时间矩阵ETC，并根据适应度函数(式11)评估鸟巢位置优劣，若更优则接受步骤中更新后的位置，否则保持位置不变

(7)if(K>P) then

(8)对当前的鸟窝位置进行随机更新

(9)end if

(10)对鸟窝位置优越性进行评价，方法与步骤6中相同，若更优则接受步骤8中更新后的位置，否则保持位置不变

(11)记录迭代完成产生的最佳鸟窝位置

(12)end while

(13)输出最优值

经过以上迭代，算法最终将收敛至一个最优的性能权重向量α，能够使该负载均衡模型正确计算集群当前负载，并合理地分配新到达的负载。

3.3 动态分配负载

根据布谷鸟搜索算法寻找到的最佳性能权重能够得到集群节点当前负载，从而得出分配权重向量W，文中通过实时监听节点的负载数据对任务的分配进行动态调整。根据式2可求出节点上任务的分配权重，为进一步确定任务处理的节点，需要综合目前任务、负载分配历史及节点任务分配权重来确定节点对当前任务进行处理，因此引入选择函数来定义任务和节点间的映射关系，做出合理且平稳的分配方案。通过一个判断向量ThrVal来描述选择函数，对于集群节点有：

Hissu/ResTol≈Wsu/∑w

(14)

式14可作为负载平衡的目标，其中ResTol表示负载任务总数，Hissu表示历史任务分配向量的一个分量，即某个单个节点的历史任务分配。计算节点的判断向量ThrVal，单个节点的判断分向量定义为：

ThrValsu=Wsu×ResTol-∑w×Hissu

(15)

因此选择函数Sel可以描述为：

{δ=Sel(T,h,W)ThrValδ=max(ThrVal)}

(16)

利用选择函数能够准确地根据任务分配权重进行节点任务分派，实现集群的负载均衡，从而实现资源的合理分配。

4 实验结果及分析

实验目的是在Storm集群环境中，分别测试文中动态负载均衡算法与Storm默认调度算法的处理延迟、系统吞吐量和负载均衡情况。比较和分析相关结果，验证文中算法在性能上的先进性。

实验利用Pluggable Scheduler对Storm任务调度算法进行自定义，而对于集群节点状态的监测则使用Ganglia，监测诸如CPU、内存、磁盘I/O和网络带宽等资源的利用情况，并根据Ganglia生成的数据对实验结果进行辅助分析。实验采用5台物理机器组成的Storm分布式集群，各个节点的硬件配置如表1所示。

表1 节点配置信息

每个节点运行Ubuntu 12.04操作系统。其中一个作为主节点运行Nimbus进程，实现资源分配以及任务调度；从节点执行Nimbus分派的任务,启动和停止由其自身管理的Worker进程。同时还搭建了Zookeeper集群，它们始终处于运行状态。

文中选择典型的大数据处理应用WordCount来进行实验，分别实现了默认算法与文中算法的WordCount程序并提交到Storm集群运行。同时，为了避免其他不确定性对实验结果的干扰，将2个程序进行多次实验，计算结果的平均值完成实验的结果分析。

所有节点硬盘为20 GB，网卡为10 G bit。

在处理时延方面，文中算法与默认调度算法的处理时延如图3所示。可以看出，较之于默认调度算法，文中算法的处理时延大体上有所下降，约降低20%～25%左右。

图3 算法时延比较

在系统吞吐量方面，文中基于布谷鸟搜索算法的Storm集群动态负载均衡算法与默认调度算法的吞吐量如图4所示。可以看出，较之于默认调度算法，文中算法的吞吐量在整体上有所提高，约提高了20%左右。

针对负载均衡性能的测试，设计了四种对资源种类需求不一样的Topology以评估文中算法在不同资源使用情况集群下的处理能力。其中，Topology1～Topology4分别属于CPU密集型作业、内存密集型作业、磁盘密集型作业、网络密集型作业。各作业的估计资源使用值向量按CPU、内存、磁盘IO和网络带宽的次序分别为：[9,4,4,3],[5,8,3,4],[2,4,5,9],[5,3,8,4]。将以上Topology均提交至Storm集群，其平均处理时间分别如图5所示。

图4 算法吞吐量比较

(a)Topology 1

(b)Topology 2

(c)Topology 3

从图中可以看出，提交的四个Topology进行初始时表现均不如默认调度，而随着节点资源的变化，文中算法平均处理时间逐渐降低并低于默认算法。这是由于在作业初始时节点可提供资源相同，默认的轮询算法更有优势，而随着节点资源的变化，默认算法则表现乏力。较之于默认调度算法，文中算法的作业平均处理时间缩短了一半左右，并且伴随着时间推移逐步趋于稳定，有助于提升作业的执行效率。

5 结束语

针对Storm默认任务调度算法存在的节点资源利用率不高及难以将节点资源与任务实际相结合等问题，提出了一种基于布谷鸟搜索算法的Storm集群动态负载均衡策略。通过引入布谷鸟搜索算法并稍作修改，将任务调度模拟为布谷鸟寻窝产卵的过程，通过算法的寻优过程为集群的CPU、内存及网络带宽等资源赋予动态权值，以完成资源的动态分配，达到节点负载的均衡。实验结果表明，该算法可以实现资源的合理分配，与默认算法相比具有更优的任务调度效率，更高的集群吞吐量和更少的平均处理时间。