Storm环境下基于拓扑结构的任务调度策略

刘 粟，于 炯，鲁 亮，李梓杨

(新疆大学 信息科学与工程学院，乌鲁木齐 830046)(*通信作者电子邮箱yujiong@xju.edu.cn)

0 引言

随着互联网+时代来临，全球数据量急剧增长。国际数据公司(International Data Corporation, IDC)发布的白皮书《数据时代2025》中提出，预计到2025年全球数据量将达到163 ZB，其中超过25%的数据将成为实时数据，而物联网实时数据将占到95%[1]，面对如此庞大的实时数据量，需要时效性高、可扩展性和稳定性强的流式计算框架。与批量计算不同，流式计算不再对数据的中间结果进行存储，数据直接在各个工作节点的内存中进行计算。在这种应用场景下，以Twitter公司的Storm系统为代表的几种实时计算框架应运而生，也将流式计算的应用范围逐渐扩展到物联网、金融、社交媒体以及实时交通等实时性要求高的领域[2]。其中在Storm环境下，针对套牌车识别具有时效性约束的问题，相关学者提出了一种基于实时车牌识别的流式并行检测方法，并且该方法的准确率达到了98.7%[3]，实时获取车辆的动态信息已经成为可能。

Storm平台在时效性、扩展性和稳定性等各方面均有着良好的表现，但是其采用的默认轮询调度策略(Round-Robin Scheduling, RRS)，将需要计算的任务平均分配到集群中的各个工作节点上，忽略了集群中各个节点的网络通信开销，在一定程度上增加了通信延迟。针对Storm缺乏智能调度机制的问题，本文根据已有的研究工作，将Storm环境下的优化调度策略分为以下三类[4]：第一类是通过改变拓扑组件中任务实例的通信方式减小通信开销。由于Storm平台中，通信方式在很大程度上决定了任务间通信开销的大小，因此，降低通信开销的核心做法是尽可能地降低节点间通信与进程间通信开销。这类文献的做法主要分为全局性和局部性的任务调度优化策略。其中，文献[5-9]采用的是全局性的任务调度优化策略，根据对各类资源和数据流的动态监测，对所提交拓扑中的所有任务进行一次性的全局重新部署，调度过后，集群的整体通信开销降低。但由于全局性的任务调度优化策略是对全部的任务进行重部署，影响作业的实时运行，进而出现集群短暂不可用的现象，且全局调度的开销比较大。而局部性的任务调度优化策略则选取部分任务进行重部署，对作业处理的实时性影响较小。文献[10-11]采用局部性的任务调度优化策略，对任务所需的各类资源进行限制或是对数据流的传输速率设定阈值，以便选择需要重部署的任务,从而减少需要重部署的任务数量，降低算法执行开销，减少对系统实时性的影响。第二类优化策略的核心思想是通过合理的资源分配，优化资源分配结构，提高系统运算效率。文献[12]提出R-Storm策略，利用任务所需的资源和工作节点可提供资源之间的关系实现调度；优点是可以基本满足节点对CPU、内存和网络带宽的约束，但缺陷是该策略无法从监控中直接获取以上资源且只适合同构环境。文献[13-14]将图形处理器(Graphics Processing Unit, GPU)作为一类资源，利用其在并行处理方面的优势，将GPU运用到Storm框架中，实现大幅度的性能优化。文献[15]将能耗作为一类资源，提出了高性能低延迟的实时流式计算系统Re-Stream，但Re-Stream本身度量资源的维度比较单一。文献[16-17]提出了服务质量感知的调度优化策略，基于CPU和内存资源的状态信息，构建成本空间模型，以寻求新任务的最优放置策略。第三类是根据集群运行的实时状况对集群进行调度，从而实现负载均衡。在Flink平台中，节点对数据元组的广播、轮询和随机三种路由策略同Storm环境下的轮询调度策略一样，均未考虑节点负载不均衡的问题。文献[18]针对这一弊端，提出Flink环境下的基于负载感知算法的动态负载均衡策略。文献[19-21]根据节点资源情况，提出合理的数学模型进而找出更优的任务调度策略。

以上三类均为在线的调度策略，这些调度策略的触发阶段发生在拓扑运行过程中，通过监控获取集群的实时运行状态，因此调度的精确性较高。然而，这些调度策略不可避免地会对用户作业运行的实时性带来不良影响，因此有学者提出作用于拓扑部署阶段的离线调度策略[5]。文献[5]通过分析拓扑结构，尽可能地将相互关联的一对任务放置在同一个进程中，进而将所有的进程通过轮询调度策略放置到各个工作节点。但该策略忽略了任务关联的紧密程度以及由节点异构性带来的任务分配不均衡问题。考虑Storm默认调度策略和已有研究工作的不足，本文提出一种Storm环境下基于拓扑结构的任务调度策略(Task Scheduling Strategy based on Topology Structure, TS2)。该策略作用于异构环境下的拓扑部署阶段，建立CPU资源限制模型和通信开销最小化模型，通过分析拓扑结构，考虑任务关联关系的紧密程度，尽可能地将任务均匀分配至各个工作节点，达到优化进程和线程部署的效果。实验结果表明，相比于Storm默认任务调度策略与文献[5]离线任务调度策略，TS2在Storm集群通信开销、延迟时间和吞吐量方面均有所改进。

1 Storm拓扑模型

Storm作为分布式的流式计算平台，其作业是用户实现业务逻辑的应用程序。在Storm中，作业对应的是拓扑，而拓扑的表现形式为由组件和数据流构成的有向无环图(Directed Acyclic Graph, DAG)。根据处理逻辑的不同，组件分为Spout和Bolt两种。其中Spout组件作为Storm中的数据源编程单元，为拓扑生产消息(数据)，负责从外部数据源(关系型数据库、非关系型数据库NoSQL、Kafka、实时日志以及Hadoop分布式文件系统(Hadoop Distributed File System, HDFS)等)中不间断地读取数据，并作为一定的结构的数据项(元组)传递给拓扑进行处理。Bolt组件作为Storm中的数据处理编程单元，实现拓扑中数据的处理逻辑，如对数据的过滤、聚合、查询等操作，并将处理结果传递给下游的组件。而拓扑的数据流是Storm对组件间数据通信的抽象，表现为无限的元组序列，且数据流在组件中传输时具有多种流组模式。在拓扑的运行过程中，为提高拓扑的并行度，每一个组件均可实例化成多份任务，其数量由组件的数目和配置情况而定，每个线程会执行一个或多个任务，而一般情况下，一个线程只执行一个任务。因此，任务调度实质上与线程的调度相同。在此基础上，本文对基于拓扑结构的任务调度策略进行研究。对拓扑关系图的定义如下所示。

定义1 拓扑关系图。拓扑二元组可以表示为(C,S)，其中C={c1,c2,…,c|C|}是拓扑中所有组件的集合，每一个元素代表一个Spout组件或Bolt组件。对于∀ci∈C，∃Eci={e1,e2,…,e|Eci|}，其中ej表示拓扑中组件ci在运行实例化的第j个线程。另一个为边的集合S，S={se1,e3,se2,e3,…,sek,el,…,se6,e11}，其中sek,el表示从任务实例ek到el的数据流。这种由组件、线程以及数据流构成的有向无环图称为拓扑关系图。

由组件、数据流和任务构成的拓扑关系图如图1所示。

图1 Storm的拓扑关系图Fig. 1 Relationship diagram of Storm topology

观察图1可知，度大的组件反映了与该组件中的任务存在通信的任务数量较多，而这种通信方式会带来较高的节点间通信开销。考虑到如果可以将这些互相通信的任务尽可能地部署到同一个节点上，可以降低节点间通信开销，基于这一思想，提出关联任务的定义。

定义3 关联任务。对于拓扑中任意的任务ef、eg和eh，若任务ef和eg之间存在数据流sef,eg，并且任务eg和eh之间存在数据流seg,eh，则任务ef、eh均为任务eg的关联任务。如图1所示，以任务e3为例，Spout组件中的任务e1、e2以及Bolt B组件中的任务e10、e11均为任务e3的关联任务。

当图1所示的拓扑关系图提交到集群后，根据Storm默认调度策略，以轮询的方式进行任务分配，进而形成拓扑的任务分配图，如图2所示。

图2 拓扑的任务分配Fig. 2 Task assignment of topology

一般情况下，在Storm集群中存在三种通信方式，分别为节点间通信、节点内进程间通信和进程内线程间通信，不同的通信方式其通信开销也各不相同。由于节点间通信开销需要占用网络带宽资源，其通信开销最大，而线程间通信开销最小且不可避免。文献[6]提出在单拓扑环境中，如果每个节点上只分配一个槽，即一个节点上只部署一个进程，可以避免节点内进程间通信方式，有效降低通信开销。基于这种方法，本文考虑通过拓扑关系图向集群分配任务时，在各节点上仅分配一个槽，此时，默认轮询调度策略便简化为拓扑中全部线程在各节点上的均匀分配。在此基础上，任务与节点之间的映射关系定义如下。

2 问题建模与分析

本章基于Storm的拓扑关系图建立了CPU资源限制模型和通信开销最小化模型。CPU资源限制模型从工作节点的理论CPU资源出发， 通过设定阈值为节点保留一定的CPU资源。同时，根据节点剩余CPU资源对各节点最多可放置的线程数量进行限制。通信开销最小化模型基于拓扑的任务数量和数据流数量不变的原则，尽可能将高通信开销的节点间通信转化为低通信开销的节点内线程间通信，为实现通信开销最小化提供了理论依据。

2.1 CPU资源限制模型

根据Storm环境下流式计算模型的特征，考虑集群中各个节点的CPU资源需求。设Storm集群包含的工作节点集合为M={m1,m2,…,m|M|}，其中mk表示集群中第k个节点。为简便，下文中出现的“节点”均指工作节点。各工作节点理论可用的CPU资源构成了集合R={rm1,rm2,…,rm|M|}(单位为Hz)。在集群运行过程中，各节点的CPU资源主要用于处理提交的拓扑，即服务于拓扑组件中分配到该节点的线程ei，只有当节点在非满负荷的状态下运行，才能保证节点处于最佳的工作状态，因而设阈值α(0<α<1)，在理论条件下为节点保留一定的CPU资源。故：对于∀mk∈M，rei代表线程ei在运行过程中所需要的CPU资源，故有:

(1)

考虑到各工作节点的CPU资源是有限的，且在异构环境下，为了达到一定的负载均衡效果，各个节点最多可以承载的线程数量也是不同的。为满足式(1)提出的限制条件，节点上部署的线程数量应低于其可承载最大线程数。

定义5 节点可承载最大线程数。假设将集群中工作节点按照剩余CPU资源排序后的节点集合记为M′= {m1′,m2′,…,m|M|′}，其中|M′|=|M|，每个工作节点所对应的当前剩余CPU资源依次为Rsurplus={rm1′surplus,rm2′surplus,…,rm|M|′surplus}。根据用户设定的工作节点数量，选择前|Mτp|个节点为用户提供计算服务，即Mτp={m1′,m2′,…,m|Mτp|′}，其中Mτp⊆M′，对应的当前各节点的CPU剩余资源为Rτpsurplus={rm1′surplus,rm2′surplus,…,rm|Mτp|′surplus}。拓扑τp的线程总数应为该拓扑分配在各个节点上的线程数量之和，即:

|eτp|=|em1′τp|+|em2′τp|+…+|em|Mτp|′τp|=

(2)

其中，|emi′τp|表示拓扑τp分配到第mi′个节点上的线程数量的个数。为保证在异构环境下各节点在分配工作任务时遵循一定的分配均衡性，每个节点分配的线程数量应该与其剩余CPU资源成正比，即拥有更多CPU资源的节点承担更多的工作任务，故有如下计算式：

(3)

此时X·rm|Mτp|′surplus即为Storm集群中各个工作节点的节点最大可承载线程数。

2.2 通信开销最小化模型

在Storm集群中，不同种类通信方式的开销差异较大。如果集群中每个节点只配置一个槽，即每个节点最多运行一个进程，避免节点内进程间的通信，因此，在此基础上进一步降低节点间传输的数据流总和，能有效降低集群的通信开销。

定理1 通信开销最小化原则。当Storm集群中不存在节点内进程间通信时，最小化节点间传输的数据流的个数等同于最大化节点内线程间传输的数据流的个数，即：

证明 由Storm的拓扑关系图得知，拓扑一旦提交到集群完成部署后，拓扑关系图便是固定的，每个组件包含的任务数量和数据流总量都是不会发生改变的。因此设总数据流的大小为定值，记为C。即：

(4)

得证

由定理1可得出，为满足通信开销最小化的条件，应该最大限度地把通信频繁的任务分配到同一个节点上，尽可能地实现通信开销最小化。

3 基于拓扑结构的任务部署策略

为实现上述CPU资源限制模型和通信开销最小化模型的目标，本章主要对提出的Storm环境下基于拓扑结构的任务调度策略(TS2)中的两个算法进行阐述和评估。

3.1 基于拓扑结构的进程部署算法

由于Storm中默认的轮询调度策略并不考虑各个工作节点的异构性，忽略了节点自身可能存在的性能差异。但在实际应用中，Storm集群多为节点异构性集群，针对传统调度策略存在的缺陷，考虑各节点在处理任务的同时，也要有良好的计算性能。为克服传统缺陷，基于CPU资源限制模型，实现了基于拓扑结构的进程部署算法。在拓扑提交过后的部署阶段，该进程部署算法触发，即在工作节点具有较为充分的CPU资源和可用槽的条件下，利用默认的轮询调度策略为满足这两种条件的节点分配一个进程。具体算法描述如下。

算法1 基于拓扑结构的进程部署算法。

输入 集群中工作节点集合M←{m1,m2,…,m|M|};|Mτp|为用户设置的对于运行拓扑τp所需的工作节点个数；

输出 运行拓扑τp所需的工作节点Mτp←{m1′,m2′,…,mMτp′} 及各个节点的可用槽。

1)

M′←sortByCPURemainingResource(M);

/*根据剩余CPU资源对集群中所有节点排序*/

2)

if needsScheduling(τp)=true then

/*如果拓扑τp即将调度*/

3)

Mτp←{m1′,m2′,…,m|Mτp|′} ;

/*分配M′中前|Mτp|个节点运行拓扑τp*/

4)

/*未被分配的节点*/

5)

for eachi∈Mτpdo

6)

if availableSlots(i)=NULL then

/*如果节点i没有可用槽*/

7)

Mτp.remove(i);

8)

16)

end for

17)

end if

18)

assign(availableSlots(i)[0],i);

/*每个节点分配一个进程*/

19)

end for

20)

end if

3.2 基于拓扑结构的线程部署算法

算法1完成了对执行拓扑的节点选取与进程部署。接下来根据拓扑关系图，考虑如何将组件中的线程部署到已选取的节点进程上，即得到优化部署后的拓扑任务分配图。由于Storm默认的任务调度策略在部署线程时，没有兼顾到不同通信方式的开销差异，导致较高的通信开销。针对该问题，本节提出基于拓扑结构的线程部署算法，利用节点可承载线程最大数的思想对部署在同一节点上的线程数量进行约束，基于通信开销最小化模型，尽可能将度较大的组件中的线程部署到同一节点上，进一步降低节点间通信开销，完成负载较为均衡、通信开销较低的线程部署。具体算法描述如算法2所示。

算法2 基于拓扑结构的线程部署算法。

输入 根据算法1输出的运行拓扑τp所需的工作节点Mτp←{m1′,m2′,…,mMτp′} 及各个节点的可用槽;拓扑τp中所有组件以及各个组件的度；

输出 各工作节点部署的工作线程。

初始化EULnowτp←{0,0,…,0};

/*设置每个节点当前分配的线程个数均为0*/

1)

Cτp←getComponent(τp);

2)

Dτp←getDegree(Cτp);

3)

/*获取度最大的组件*/

4)

/*获取该组件包含的所有实例(线程)*/

5)

6)

Cτp′←BFSComponentTraversal(cτp*);

/*以度最大的

组件cτp*为根，对拓扑关系图进行广度优先遍历*/

7)

/*对于除cτp*以外的

所有组件按照广度优先遍历结果依次执行以下部署算法*/

8)

/*获取该组件的所有线程*/

9)

/*获取其前驱线程所在的所有节点*/

10)

/*每个节点上当前

分配的线程个数小于该节点上应分配的线程上限*/

11)

12)

else

/*该节点当前分配的线程个数已达上限*/

13)

ifMk≠∅ then

14)

Mk←Mk-{mk};

15)

/*除去不符合条件的

16)

Mτp←Mτp-{mk};

17)

else

18)

配线程个数的上限，则将其轮询分配到其他节点上*/

19)

end if

20)

end if

21)

22)

end for

4 实验结果与分析

为验证基于拓扑结构的任务调度策略的有效性，本章将通过以下实验进行评估和分析。

4.1 实验环境

在Storm集群中一共设置9个节点，包括1个主控节点和8个工作节点，其中集群中各个节点的软件配置情况如表1所示。

表1 Storm集群各节点的软件配置Tab. 1 Software configuration of nodes in Storm cluster

表2所示为集群中各节点的硬件配置，其中:Supervisor1,2为高配节点;Supervisor3,4,5,6为中配节点;Supervisor7,8为低配节点。总体硬件配置信息表明该集群为异构集群。

表2 Storm集群各节点的硬件配置Tab. 2 Hardware configuration of nodes in Storm cluster

为更好观测在异构环境下TS2的有效性，文中不仅与Storm默认调度策略进行了对比，同时还在集群中部署了文献[5]中的离线调度策略。实验中，离线任务调度策略的各项参数配置信息如下：alpha为0.5，beta为1.0，epsilon为0.5。

实验数据取自GitHub上的storm-benchmark-master提供的基准测试用例，一共是3组，分别为WordCount、SOL、RollingCount。除表1、表2所示参数之外还有一些通用的参数配置，这些参数在通过多次实验后确定如下：1)为消除进程间通信开销，在基准测试中各节点内仅分配一个进程，即topology.workers的值为8。2)为保证数据流传输的可靠性，各个进程不仅要运行分配的线程，还要运行一个Acker Bolt实例，即topology.acker.executors的值为8。3)为对Spout组件的元组发射频率进行控制，防止元组因超时而重传，设置Spout组件的缓存队列长度topology.max.spout.pending的值为50，并以此决定Storm系统的吞吐量。此外，各基准测试用例的参数配置如表3所示，对参数的说明如下：1)component.xxx_num表示组件的并行度，即一个Spout或Bolt组件在运行时的线程数量。2)在SOL中，topology.level表示拓扑的层次，设置为3。message.size表示元组的大小为100 B。3)在RollingCount中，window.length表示窗口长度为150 s，emit.frequency为每隔30 s发送一次数据。

表3 基准测试参数配置Tab. 3 Benchmark test parameter configuration

4.2 结果分析

实验分别选用Storm默认的轮询任务调度策略(图例中Default)、文献[5]中的离线任务调度策略(图例中Offline)和本文中提出的基于拓扑结构的任务调度策略(图例中TS2)进行对比，并选取以下四项指标，系统延迟时间、CPU资源占用率、工作节点之间的数据流传输速率和平均吞吐量来衡量、分析TS2的性能优劣。同时，利用Nmon对集群中的各工作节点进行监控。

4.2.1 系统延迟时间评估

系统延迟时间统计的是一个元组从Spout消息源头发出，直至最终被系统成功处理所需的时间，反映了系统运行拓扑的处理效率。本组实验所设置的取样周期为10 s，采样时间长度为10 min。由图3可知，三个基准测试在三种不同策略下的延迟时间的趋势大致相同。当拓扑提交之后，在运行时间0 s开始之后的一段时间内，延迟时间先是陡增，随后下降，并逐渐趋于平缓。在零延迟时间阶段，由于拓扑中不存在成功调度的任务，因而没有完整的数据流，Acker无法获取到系统延迟时间的信息。在50 s之前，Spout组件的缓存队列中存放着大量未处理的元组，且元组的数量源源不断地增加。任务部署完成意味着短时间内需要处理大量的元组，因而系统延迟时间会出现一个峰值。随着大量的元组处理过后，负载逐渐趋于稳定，系统的延迟时间也随之降低，并趋于平稳。图3充分地反映了提交拓扑、任务调度到运行稳定这三个阶段的运行效率。

图3(a)表示的是WordCount执行3种不同任务调度策略的系统延迟时间。由图3(a)可知，在执行Storm默认的轮询调度策略和离线调度策略时，系统的延迟时间分别在50 s、40 s时大幅度上升，并在110 s时达到峰值；而TS2的调度过程则相对缓慢，在第50 s之后延迟时间迅速上升，在120 s达到峰值，峰值为819.2 ms，并在较长一段时间段内维持在较高水平，延迟时间的回落速度相比较于默认调度策略和离线调度策略较慢。分析该现象可得，TS2的调度开销较大，但由于调度过程是在拓扑运行之前，所以并不会对用户作业运行产生影响。三种策略执行过后，系统延迟时间迅速收敛。拓扑运行稳定后，Storm默认调度策略、离线调度策略和TS2在第180 s～600 s的平均延迟时间分别为391.5 ms、345.5 ms和328 ms。TS2相比于Storm默认调度策略和离线调度策略的延迟时间分别降低了16.22%和5.07%。由此可见，TS2在系统延迟方面的效果更佳，更符合流式计算环境的实时性要求。

图3 不同任务调度策略下的系统延迟对比Fig. 3 Comparison of system delays under different task scheduling strategies

图3(b)表示SOL在执行三种不同调度策略下的系统延迟时间，曲线走势与图3(a)相类似，与Storm默认调度策略和离线调度策略相比，TS2的调度过程略微缓慢，部署开销略大。在拓扑执行稳定后，三种调度策略在第130 s～600 s内的延迟均值分别为182.1 ms、157.1 ms和148.9 ms。TS2相比于Storm默认调度策略和离线调度策略的延迟时间分别降低了18.23%和6.49%，优化效果略高于WordCount的优化效果。

图3(c)表示RollingCount在执行三种不同调度策略下的系统延迟时间，与Storm默认调度策略和离线调度策略相比，TS2的调度过程较为缓慢，进入峰值的时间略晚于默认调度策略和离线调度策略，部署开销略大。在拓扑执行稳定后，三种调度策略在第170 s～600 s内的延迟时间均值分别为377.5 ms、334.3 ms和315.9 ms。TS2相比于Storm默认调度策略和离线调度策略的延迟时间分别降低了16.32%和5.50%。优化效果略低于在执行SOL时的优化效果。

综上所述，对于任何调度策略而言，可用节点和可用槽的选择都是一个不可回避的过程。由于算法1在执行过程中有无法避免的系统延迟存在，因此，拓扑部署初期会出现系统延迟陡增的现象。虽然TS2延长了拓扑部署时间，但部署完成后系统延迟时间会逐步降低，其最终收敛时间会略低于默认调度策略和离线调度策略。实验结果表明，WordCount和RollingCount的系统延迟时间要高于SOL，即优化结果略低于SOL。由于WordCount和RollingCount两个基准测试中存在按域分组的流组模式，那么上游的组件包含的任务流向下游时，各数据流元组速率也是不同的，因此，使用任务间的关系进行调度存在一定的不精确性，但由于该调度策略实现简单，开销较小，在不影响用户作业的正常运行的条件下，还能有效降低系统延迟时间。综上所述，就不同的基准测试而言，TS2均具有更低的系统延迟时间，并且对于各基准测试而言，TS2相比于Storm默认调度策略和离线调度策略的平均优化率分别为16.91%和5.69%。该实验证明了基于拓扑结构的任务调度策略在降低系统延迟方面的有效性。

4.2.2 CPU资源占用率评估

WordCount、SOL和RollingCount这三组基准测试在不同任务调度策略下的CPU资源占用率如图4所示。

由图4可知，在默认的轮询调度策略下，每个工作节点的CPU资源占用率差别较为明显，高配节点的CPU资源占用率较低，低配节点的CPU资源占用率较高，中配节点的CPU资源占用率维持在中间水平。造成这种现象的原因是，Storm的默认调度策略在分发任务时，不考虑节点的自身资源可用情况，忽略异构环境下的节点性能差异，直接将任务经过轮询调度策略放置在各节点上，导致各节点的负载不均衡。因此，低配节点在自身资源不充足的条件下，承载较多的线程数量，需要耗费大量系统CPU资源，故低配节点的CPU资源占用率较高。而高配节点的自身可用CPU资源较为充足，在执行轮询策略时，即使放置在该节点的线程数量和低配节点相同，也不会对自身的CPU资源产生过多的影响，所以高配节点的CPU资源占用率偏低。三个基准测试中，WordCount和RollingCount均属于CPU敏感型的测试，因此其整体CPU资源占用率略高于SOL的CPU资源占用率。

同时由图4可以看出，执行离线调度策略时，各节点的CPU资源占用率的整体水平较为均衡，高配和中配节点的CPU资源占用率较为接近，低配节点的CPU资源占用率则略高于其他两种节点。由于离线调度策略通过对节点CPU资源的限制，控制各个节点上放置的线程个数，改善集群中各个节点的负载。因此，在离线调度策略的作用下，三个基准测试的各节点CPU资源占用率整体较为平均，集群的负载均衡效果明显优于默认调度策略。但是由于该策略未考虑到各类节点中拥有资源总量的差异性，因而会出现低配节点上的CPU资源占用率比其他两类节点的CPU资源占用率高的现象。

图4 不同任务调度策略下的CPU资源占用率对比Fig. 4 Comparison of CPU utilization under different task scheduling strategies

在执行TS2时，图4中的负载均衡效果明显优于默认调度策略，但与离线策略的整体趋势明显不同。高配节点Supervisor 1,2具有更高的CPU负载，而低配节点Supervisor 7,8节点的CPU负载较低。由于算法优先将组件中的线程部署在其前驱线程所在的工作节点上，导致一些关联紧密的后继线程更倾向于分配至资源较为丰富的高配节点，故CPU资源占用率会持续增加，进而超过其他两类工作节点。而低配节点上初始化分配的线程数量较少，其后继线程倾向于分配至该节点上的可能性较小，因而其CPU资源占用率略低。TS2充分考虑到了异构环境下的节点间计算资源的差异性，尽可能地将关联线程部署在同一个节点上，虽无法保证完全的负载均衡，但为了满足线程分配的平均性的同时兼顾通信开销的最小化，这一现象是不可避免的。由算法2可知，度最大的组件会被优先调度，该组件中的线程会在轮询调度策略的作用下均匀地分配至集群中剩余CPU资源充足的高配节点上。相比于其他组件，这种度较大的组件所需的计算和通信资源较大，为保证拓扑的执行效率，对于这样的组件更倾向于设置更多的线程数量，以便提高拓扑的处理速度。因此，这些线程将会近似均衡地分布到各工作节点，由于任务间的关联性，其后继线程也会均匀地分配到集群的各节点，达到任务整体分配的平衡。因而执行TS2时，集群规模的大小并不会对任务分配的均衡性造成影响。

4.2.3 节点间通信开销评估

本节统计并分析在WordCount、SOL、RollingCount三个基准测试中，工作节点间的平均数据流传输速率情况。10次实验中各基准测试在运行平稳的状况下，单位时间内各节点间数据流传输总量的平均值如图5所示。

图5 不同任务调度策略下的节点间平均数据流速率对比Fig. 5 Comparison of average data flow rates between nodes under different task scheduling strategies

由图5可以看出，在采用了离线调度策略和TS2之后，三组基准测试工作节点间的平均数据流速率均有所下降。离线调度策略执行之后，工作节点间的数据流传输速率的均值为37 853 tuple/s、12 190 tuple/s、33 478 tuple/s，相比较于默认轮询调度策略的结果分别降低了10.58%、13.41%、11.24%；而TS2执行之后，工作节点间的数据流传输速率的均值在36 192 tuple/s、11 575 tuple/s、32 069 tuple/s，相比较于默认轮询调度策略，分别降低了14.50%、17.78%、14.97%，效果优于默认调度策略。TS2相比于默认调度策略在节点间通信开销方面平均降低了14.21%。实验结果表明，SOL的优化率明显高于WordCount和RollingCount，其原因和系统延迟时间的实验结果相同。即在拓扑中，如果使用了按域分组的流组模式，再使用TS2中数据流的数量评估任务彼此关联的紧密程度具有一定的局限性，未来将结合在线任务调度的监控手段进行调度优化的微调。

4.2.4 平均吞吐量评估

本节统计并分析在WordCount、SOL以及RollingCount三个基准测试中其节点的平均吞吐量信息。吞吐量代表着在单位时间内成功传输的元组数量，反映了系统的负载能力。由图6可知，WordCount在执行这三种调度策略时，平均吞吐量的值分别为51 877.78 tuple/s、57 518.50 tuple/s和59 578.63 tuple/s，离线调度策略的平均吞吐量比默认调度策略提高了9.81%，而TS2的平均吞吐量比默认调度策略提高了12.93%。在SOL的三种调度策略对比实验时，平均吞吐量的值分别为20 034.23 tuple/s、22 798.10 tuple/s和27 381.36 tuple/s，离线调度策略的平均吞吐量相比于默认调度策略提高了12.12%，而TS2相比于默认的调度策略的平均吞吐量提高了16.74%。RollingCount在执行Storm默认的调度策略、离线调度策略和TS2这三种调度策略时，平均吞吐量的值分别为50 726.60 tuple/s、56 445.20 tuple/s和64 852.27 tuple/s，离线调度策略的平均吞吐量相比于默认调度策略提高了10.13%，而TS2的平均吞吐量相比于默认的调度策略提高了12.96%。TS2相比于默认调度策略在吞吐量方面的优化率平均提高了14.21%。结合图5分析可知，SOL的节点间数据流速率的优化效果高于WordCount和RollingCount，这意味着在SOL中节点间通信开销降低的幅度大于WordCount和RollingCount。由于Storm集群中存在三种类型的通信开销，且由定理1通信开销最小化原则可知，在节点间通信开销降低的情况下，节点内的通信开销会有所增加。因而SOL的平均吞吐量提升幅度明显。

图6 不同任务调度策略下的平均吞吐量对比Fig. 6 Comparison of average throughput under different task scheduling strategies

5 结语

随着大数据时代的到来，对数据处理的实时性要求越来越高，流式计算已经成为大数据研究领域的一大热点。Storm作为实时性较强的开源分布式大数据流式计算平台，有着广泛的应用场景。但其采用的默认调度策略忽略了由通信方式带来的系统延迟的增加，同时也没有考虑在异构环境下工作节点之间不同的资源状况对Storm集群性能的影响。针对该问题，本文提出基于拓扑结构的任务调度策略，通过选取CPU资源较为充足且可用的节点，消除节点内进程间通信开销，同时将关联程度较为紧密的线程分配到同一个节点，优化了拓扑的任务部署。实验结果表明，本文算法可以有效减少异构环境下集群中各个工作节点之间的网络通信开销，降低系统的延迟时间，改善负载均衡的状态，提高系统吞吐量。

下一步的研究工作主要集中于将离线调度和在线调度相结合，即考虑在异构环境下，将TS2与轻量级的在线调度策略相结合，弥补TS2在调度精确性方面的不足；同时优化TS2的调度思想，使得该策略可以适用于更加复杂的业务场景。