基于Storm平台的数据迁移合并节能策略

蒲勇霖，于炯，鲁亮，李梓杨，卞琛，廖彬

（1.新疆大学信息科学与工程学院，新疆 乌鲁木齐 830046；2.中国民航大学计算机科学与技术学院，天津 300300；3.广东金融学院互联网金融与信息工程学院，广东 广州 510521；4.新疆财经大学统计与信息学院，新疆 乌鲁木齐 830012）

1 引言

近年来，随着移动互联网、云计算和物联网的高速发展，数据的产生与积累已达到前所未有的速度，并推动着各行各业进入大数据时代。大数据的相关研究已成为学术界与产业界共同探讨的热点话题，其主要的处理模式为批量处理、流式处理、交互处理和图处理等[1-5]。随着大数据的飞速发展，各种处理模式不断产生，出现了高能耗、高污染的。因此如何有效解决由于新兴技术带来的高能耗，一直是广大学者共同面对的问题。据美国斯坦福大学的调查发现，全球数据中心2010年的耗电量为2 355亿kW⋅h，占据全球电力总消耗的1.3%，其中美国数据中心的耗电量占据全美国电力总消耗的2%[6]。我国数据中心的电力消耗同样惊人，截至2011年底，我国数据中心的总量达到43万个，数据中心的耗电量占据全国电力总消耗的1.5%，并且所占比例仍在逐年上升[7]。随着大数据时代的到来，海量的能源被用于数据处理，但其能效不断降低。因此如何有效提高能源的利用率，是解决大数据处理能耗问题的关键。

大数据的处理一般被分为实时处理与非实时处理，在IDC与希捷（Seagate）公司联合发布的《数据时代2025》白皮书中指出，2025年全球数据总量将达到163 ZB，比2016年创造出的数据量提高了10倍。其中实时数据所占比例超过25%[8]。由此可见，实时大数据拥有广泛的应用前景，而在大数据的处理模式中，流式处理具有很高的实时性。流式处理作为新的可容错、高性能的分布式处理平台，存在着高能耗的问题[9]，已经给产业界带来了巨大的能耗开销。因此流式处理平台的节能优化是一个亟待解决的问题。

现有流式处理平台以Apache Storm框架[10]为代表。Storm是一个开源、主从式架构、横向扩展性良好且容错能力强的分布式实时处理平台，其编程模型简单，支持包含Java在内的多种编程语言，数据处理高效。相较于不开源的Puma[11]以及社区冷淡的S4[12]，Storm拥有更广阔的发展前景；相较于目前主流的实时处理平台Flink[13]与Spark Streaming[14]，Storm的数据处理实时性能效果更佳；相较于后起之秀Heron[15]，Storm更加简单且业界的认可度与成熟度更高。目前Storm已经广泛运用到银行金融[16]、临床医疗[17]、社交网络[18]等行业进行实时大数据分析，并广泛运用到机器学习算法、分布式远程调用等领域进行理论研究[19]，被誉为“实时处理领域的Hadoop”。

在Storm集群中，一个流式作业（拓扑）通过有向无环图（DAG,directed acyclic graph）表示，且拓扑内的数据通过轮询（RR,round-robin）调度策略均匀分配到各个工作线程上，而一个工作进程包含多个工作线程。Storm集群采用轮询调度策略均匀分配数据需要符合8种流组模式，其中最重要的是随机分组（shuffle grouping）。但是随机分组存在两大弊端，致使Storm集群产生额外资源与能源的浪费。其一是数据流经工作节点时，有些线程数据处理复杂度较低，随机分组致使线程因计算资源过剩而产生浪费；其二是未考虑节能的问题，对于数据处理复杂度较低的线程，并未对存在该线程的节点进行节能处理，造成能源的浪费。因此要解决因随机分组而带来的资源与能源的浪费问题，需要综合考虑集群的路径、工作节点的计算资源、数据的匹配等各方面的因素，寻找最优的数据分配策略，从而在保证性能的前提下实现节约资源与能源的目的。本文的主要贡献如下。

1)通过分析Storm集群的拓扑结构，建立数据分配模型、路径开销模型与资源约束模型，进一步提出最优线程数据重组原则，为数据迁移合并模型的建立奠定了基础。

2)根据资源约束模型、数据迁移合并模型和节点降压原则，提出基于Storm平台的数据迁移合并节能策略（DMM-Storm,energy-efficient strategy for data migration and merging in Storm），该策略包括资源约束算法、数据迁移合并算法和节点降压算法。其中，资源约束算法验证工作节点是否允许数据迁移，数据迁移合并算法根据集群拓扑的实际情况，确定数据迁移的最优方法，并为节点降压算法提供了理论支撑。节点降压算法根据数据迁移合并算法与节点降压原则的特点，降低非关键路径上工作节点的电压以减少集群中的能耗损失。最后通过实验从多角度验证了算法的有效性。

2 相关工作

学术界与产业界针对现有大规模数据处理平台节能方面的研究主要分为4类：批量数据处理平台节能算法、流式数据处理平台节能算法、图数据处理平台节能算法和交互数据处理平台节能算法。其中批量数据处理平台节能算法的核心思想主要是以Hadoop为代表进行算法的优化，通常对框架内的磁盘区域进行划分，通过动态组件失活（dynamic component deactivation），即在一段时间内动态关闭集群硬件的部分组件或对磁盘部分区域进行休眠达到节能的目的[20-22]；图数据处理平台节能算法的核心思想主要是以Pregel为代表进行算法的优化，通常对图边缘数据的重要性进行判别，弹性调节集群的功耗达到节能的效果[23-25]；交互数据处理平台节能算法的核心思想主要是以MapReduce为代表进行算法的优化，通常以优化配置参数[26]、作业迁移调度[27]和任务完成后关闭对应节点[28]等提高能源利用率达到节能的目的[29-31]。这3种方案在一定程度上解决了大数据处理平台的能耗问题，但是对于实时性较高的数据处理模式存在着较大的局限性，无法直接作用于流式处理的平台。针对流式大数据处理模式的高能耗问题，现有学者提出从硬件[32]、软件[33]以及两者结合[34]这3个方面进行研究。

硬件的节能策略主要通过替换高能耗的电子元件[35]，以达到节能的效果。该方法节能效果显著且操作简单，但其价格高昂，不适合部署于大规模的集群当中。软件的节能策略主要通过任务调度[36]、资源迁移[37]等方法以提高集群的性能，达到节能的目的，但由于节能效果不稳定致使节能效果不佳。软件与硬件结合的节能策略是现在研究的重点，主要通过在任务完成后动态调节集群的电压或电源，实现集群电压或电源的缩放管理[38]，以达到节能的目的。Cordeschi等[39]针对流式大数据传输的不可控、不稳定以及实时数据量大等特性，在不影响响应时间约束条件的前提下，计算了最小化网络传输的总能耗。Wang等[38]通过使用动态电压调控技术（DVFS,dynamic voltage frequency scaling）调节集群CPU的电压以达到节能的目的。Panda等[40]通过引入上下文感知数据流执行模型，提高了任务执行的效率，从侧面降低了集群的能耗。综上所述，以上研究都是从流式处理自身特性的角度出发，建立合理的流式处理能耗模型。但针对Storm平台的节能策略仍具有较高的研究价值。

Sun等[9]提出一种流式大数据处理环境下的实时资源调度节能策略（Re-Stream），该策略通过建立集群响应时间、CPU占用率以及能耗之间的逻辑关系，并根据流式处理框架的基本性质，对整个集群拓扑执行的关键路径进行定义，综合利用拓扑执行关键路径上性能感知的任务调度策略，以及拓扑执行非关键路径上能耗感知的任务整合策略，使任务响应时间和集群能耗均降低到最低值。

Zong等[41]根据流式大数据处理的自身特性提出2种基于副本的调度节能算法——能量感知副本算法（EAD,energy-aware duplication）以及性能和能量均衡副本算法（PEBD,performance-energy balanced duplication），该节能算法的核心思想为集群拓扑不执行任务调度时或数据处理完成后，立刻降低集群节点的电压。该算法不仅保证了集群数据处理的快速执行，同时满足任务执行完成后节约集群能耗的思想。

蒲勇霖等[42]针对Storm平台在进行数据处理时存在高能耗的问题，提出工作节点内存电压调控节能策略（WNDVR-Storm），该策略根据Storm集群实际的数据处理及传输情况，对集群工作节点数据处理能力进行判别，并由集群数据流实际情况，通过对工作节点的内存电压进行动态调节，以达到节能的目的。该节能策略不仅有效降低了集群的能耗，而且在一定程度上对集群的负载均衡进行了优化。但是还存在以下两点不足：1)对集群工作节点内存电压进行动态调节，实现难度较高且存在一定的偶然性；2)若集群规模较大且工作节点过多，节能算法可能失效。

本文与文献[9,38-42]的不同之处主要体现在4个方面。首先，本文通过分析集群进行数据迁移时，工作节点存在资源约束（CPU、网络带宽和内存）的问题而构建资源约束模型，防止集群由于数据迁移而造成资源溢出的问题。其次，本文根据最优线程数据重组原则与节点降压原则，完成集群的数据迁移与节点降压，该过程不会影响集群的性能，并节约了集群的能耗。第三，本文不仅节约了集群的能耗，还通过数据迁移算法减少了节点之间的通信开销。最后，本文选取Intel公司[10]发布在GitHub上的基准测试而非自己定义的拓扑，因此更具代表性。

3 问题建模与分析

本节主要从Storm拓扑的数据分配模型、路径与成本模型和资源约束模型出发，分析Storm集群在节能方面存在的局限性，由此提出非关键线程中的数据迁移合并与关键线程中的数据迁移合并这2种模型，为节能策略的设计与实现提供了理论依据。

3.1 数据分配模型

在Storm集群中，一个流式作业由一个拓扑（topology）的有向无环图构成，其中数据源编程单元（spout）和数据处理编程单元（bolt）这2类组件（component）共同构成了数据源的顶点，且各组件之间针对不同的流组模式发送和接收数据流，进而构成了有向无环图的弧。为提高拓扑对数据流的并行运算能力，令每个组件都可同时创造多个线程（executor）。提交拓扑之后，数据将分发到集群各工作节点中，并进行数据的处理与传输。设集群工作节点集合为，线程集合为，将工作节点的数据均匀分配到集群的线程上，记工作节点分配给线程eji的数据为daj（i若线程的并行度为1，则该线程上的数据为daj），则集合DAn={daj1,daj2,…,dajn}表示工作节点分配到线程上的数据集合。图1为在3个工作节点下，Storm集群使用轮询调度策略后线程数据的分配情况。其中工作节点的集合为N={n1,n2,n3}，线程内数据可表示为

图1 线程数据分配

为了消除节点内部进程间通信开销，图1为每个工作节点仅分配一个进程（worker），因此在拓扑执行过程中只需考虑2类通信成本开销，一类为线程数据dad1与daf1之间，节点内部线程间的通信开销；另一类为线程数据dad2与daf1之间，节点间通信开销。无论工作节点如何分配数据，都满足以上2种通信开销。

此外，令线程ea与eb为线程{ec,ed1,ed2,ed3,ee}的父线程，若线程{ec,ed1,ed2,ed3}为父线程ea下的子线程，则线程{ec,ed1,ed2,ed3}内的线程互为同源线程；若线程{ed1,ed2,ed3,ee}为父线程eb下的子线程，则线程{ed1,ed2,ed3,ee}内的线程互为同源线程，以此类推，完成父线程与同源线程之间的对应关系。

3.2 路径开销模型

令一条路径p(eji,emn)为集合B(p(eji,emn))的子路径，其中顶点eji与emn表示从eji开始到emn结束。对于∃k，则bj,k∈p(eji,emn)，bk,i∈p(eji,emn)，由此对于∀bj,i∈p(eji,emn)都成立。此外，对于∀bk,l∈p(eji,emn)，如果k≠j，则∃m与bm,k∈p(eji,emn)；如果i≠j，则∃m与bl,m∈p(eji,emn)。

路径开销lp(eji,emn)表示从顶点eji到emn所有线程与有向边的开销之和，则有

令整个拓扑存在m条路径，则拓扑执行关键路径l(Gp)为

此外，在确保Storm集群性能不变的前提下，根据数据在拓扑关键路径处理及传输时间，确定位于拓扑执行关键路径上的工作节点与位于拓扑执行非关键路径上的工作节点。将位于拓扑执行关键路径上的工作节点称作关键节点，位于拓扑执行非关键路径上的工作节点称作非关键节点，位于拓扑执行关键路径上的线程称作关键线程，位于拓扑执行非关键路径上的线程称作非关键线程。

以图2为例，定义一条拓扑执行关键路径为ea→ed1→ef2→eh，则工作节点n3上的所有线程为非关键节点上的非关键线程，工作节点n1与n2上的线程分为2类：一类为关键节点上的关键线程，另一类为关键节点上的非关键线程。此外，线程ec与线程{ed1,ed2,ed3}互为同源线程，以此类推，完成非关键节点上非关键线程与关键节点上线程的对应关系。

图2 拓扑执行关键路径的数据传输及处理情况

3.3 资源约束模型

根据Storm集群进行数据迁移的特点，令工作节点分配给线程的资源集合为且计算资源主要包括CPU、内存及网络带宽3类资源的占用率。令工作节点内3类资源占用的极限为。其中表示工作节点CPU资源占用的极限，表示工作节点内存资源占用的极限，表示工作节点网络带宽资源占用的极限，原工作节点CPU资源占用为（单位为Hz），内存资源占用为（单位为B），网络带宽资源占用为（单位为bit/s）。由于Storm集群环境中数据源源不断产生，且拓扑一旦提交将持续运行下去，因此为了保证集群的高效运行，且工作节点的资源不会溢出，这3类资源需要满足如下条件，即

为了满足集群运行的可靠性，集群工作节点不能满负荷运行，本文将符合CPU资源的正常计算称为满足CPU资源临界原则，符合内存资源的正常计算称为满足内存资源临界原则，符合网络带宽资源的正常传输称为满足网络带宽资源临近原则。

当线程准备迁入数据时，该工作节点资源满足CPU资源临界原则、内存资源临界原则以及网络带宽资源临近原则时，允许线程迁入数据。即数据迁入原则tr需要满足如下条件

为了在保证拓扑高效执行的同时，提高资源的占用率，且在一定程度上优化集群的负载分配，资源约束模型为后续数据重分配原则提供了理论依据。

3.4 拓扑非关键线程中的数据迁移合并模型

根据3.3节资源约束模型，提出最优线程数据重组原则；本节针对存在关键节点上的非关键线程，提出非关键线程中的数据迁移合并模型。此外，根据集群数据传输及处理总时间，确定了拓扑执行非关键路径工作节点电压的最低值。

定义1最优线程数据重组原则。根据3.1节可知，E′(C)∈E(C)且E′(C)={eji,emn,…,eyz}为同源线程集合。同源线程之间数据的迁移合并可通过父线程进行数据的重分配，而非同源线程之间进行数据的迁移合并可能会出现数据不匹配问题，因此线程之间数据的迁移合并需要选择互为同源的线程。定义父线程eab传入子线程eji与emn数据大小分别为daab,ji与daab,mn，执行最优线程数据重组原则后，父线程对子线程的数据分配出现改变，类似数据由线程emn迁入线程eji，且迁入的数据大小为

由3.3节可知，线程之间数据的迁移合并，被迁入数据的线程存在工作节点的资源约束问题，则为满足资源约束条件，存在

根据最优线程数据重组原则设计数据迁移合并模型，为非关键节点的降压奠定了基础。针对是否存在关键节点上的非关键线程，提出2种线程中的数据迁移合并模型，当集群存在关键节点上的非关键线程时，集群实施拓扑非关键线程中的数据迁移合并模型，且该模型不改变集群性能；当集群不存在关键节点上的非关键线程时，集群实施拓扑关键线程中的数据迁移合并模型，且该模型对系统性能造成一定的影响需要进行相应的评估。

定义2节点降压原则。为计算集群实施节能策略后非关键节点电压的最低值，需要注意以下两点：其一，确定非关键节点电压的限制条件；其二，确定非关键节点电压的改变量。

集群实施非关键线程中的数据迁移合并模型，需要令非关键节点的集合为其中模型以不改变Storm集群性能为前提，因此不能改变拓扑执行关键路径，由此可知模型的执行存在一个限制条件，即数据传输及处理的总时间不会发生改变。根据3.3节可知，线程迁入数据存在制约条件，即线程eji迁入数据需要满足tr。由于线程迁入数据为，关键路径的时间t不发生改变，则非关键节点的电压为，此时调节电压保证关键路径的时间不发生改变，获得改变后的电压为。由此存在一个函数关系

其中，φ表示数据迁移合并过程中资源的损耗率，且0<φ<1。电压的改变过程符合贪心原则，未达到贪婪状态则无法确定电压调节的最低值，因此为计算电压调节的改变量vc，引入梯度下降的方法

其中，ε表示电压改变轨迹；表示关键路径时间不发生改变；α表示训练率，且0<α<1。当满足上述条件时，非关键节点的电压以vc为步长逐渐降低，直至达到条件改变的临界点，由此可得集群实施非关键线程中的数据迁移合并模型后，非关键节点电压的最低值。由于电压调节过程中集群关键路径不发生改变，则集群数据传输与处理的总时间不发生改变，因此集群的性能不发生改变。

3.5 拓扑关键线程中的数据迁移合并模型

本节针对不存在关键节点上的非关键线程，提出关键线程中的数据迁移合并模型。通过定义能效比（EER,energy efficiency ratio），确定集群性能与能耗之间的关系，并根据能效比，确定拓扑执行关键路径工作节点电压的最低值。

模型以不改变Storm集群的性能为前提，即不改变数据传输及处理的时间。关键线程中的数据迁移合并模型对集群数据的处理及传输造成一定的影响，因此需要对集群的性能与能耗进行评估。

定义3能效比。通过3.2节可知，集群数据处理及传输的总时间为t（单位为s），定义集群数据处理及传输的总能耗为E（单位为J），则建立能效比模型，即集群数据处理及传输总时间与总能耗乘积的倒数为能效比R（单位为（s⋅J）-1），即

其中，C表示能效比误差常数，且0

定理1Storm集群在实际拓扑执行过程中，数据处理及传输总时间与总能耗的能效比R为

证明通过定义3可知，集群数据处理及传输总时间与总能耗的比值如果将总时间划分为n等份，t为[t0,t1,…,tn-1]，则有

化简式(18)得

因此，获得

证毕。

为计算集群实施关键线程中的数据迁移合并模型后的总能耗，需要计算集群非关键节点电压的最低值。根据定义2可知，存在2个制约条件，其中实施关键线程中的数据迁移合并模型后，系统的能效比与原系统能效比之间的关系为一个制约条件。已知集群非关键节点的集合为通过3.3节可知，线程迁入数据存在制约条件，则线程数据da迁入需要满足tr。由于线程迁入数据，由定义3可知集群的能效比为R，调节此时非关键节点的电压为。同理，可获得函数为

集群实施关键线程中的数据迁移合并模型电压的改变量vc′为

其中，R(vei,da,vei+1)表示集群的能效比。当满足上述条件时，非关键节点的电压以vc′为步长逐渐降低，直至达到条件改变的临界点，由此可得集群实施关键线程中的数据迁移合并模型后非关键节点电压的最低值。

4 数据迁移合并节能策略

本节主要介绍基于Storm平台的数据迁移合并节能策略，该策略在不影响集群性能的前提下，根据非关键节点非关键线程上数据的迁移情况，对非关键节点的电压进行调节，以此达到节能的目的。节能策略主要分为以下5个步骤，其执行流程如图3所示。

步骤1通过监控器获得原系统拓扑执行关键路径的基本信息。

步骤2判断是否存在关键节点非关键线程。

步骤3计算被迁入数据的线程是否满足tr。

步骤4计算非关键节点电压的最低值。

步骤5根据不同的节能算法计算集群总能耗。

图3 节能策略流程

4.1 资源约束算法

根据3.3节可知，线程被迁入数据首先应该考虑工作节点是否会出现资源溢出现象，因此需要对工作节点的资源总量进行评估。

当关键节点的某类资源占用率达到极限时，将该节点设置为极限节点，表示不能再向该节点内线程迁入数据，需要重新选择关键节点，且被选节点必须满足数据迁入3条原则。针对线程被迁入数据存在节点资源约束的问题，提出算法1，确定非关键节点非关键线程上的数据可以顺利迁出。具体的算法过程如下所示。

算法1资源约束算法

算法1为工作节点的资源约束模型。当工作节点满足tr时，允许线程迁入数据。步骤1)和步骤2)表示判断节点ni是否为极限节点，若为极限节点则该节点上线程不能被迁入数据，否则需要判断工作节点数据迁入是否满足3条原则；步骤5)～步骤7)表示判断关键节点是否满足CPU资源临界原则；步骤8)～步骤10)表示在满足CPU资源临界原则后，判断关键节点是否满足内存资源临界原则；步骤11)～步骤13)表示在满足之前的两条原则后，判断关键节点是否满足网络带宽资源临近原则。

Storm集群节能策略首先需要考虑算法的时间复杂度，原集群数据的处理及传输为轮询调度算法，其时间复杂度为O(n)。首先，算法1需要判断节点是否为极限节点，其时间复杂度为O(1)；其次，算法1的本质为依次判断数据迁入节点是否满足3条原则，其时间复杂度为3O(1)；最后，由于需要循环查找满足3条原则的关键节点，类似于轮询调度算法，因此时间复杂度为O(n)。则算法1的时间复杂度T(A)为

4.2 数据迁移合并算法

根据3.4节可知，需要通过最优线程数据重组原则判断数据迁移是否对集群性能造成影响。

在满足算法1的前提下，当数据迁入线程时，首先需要判断对Storm集群的性能是否构成影响，因此线程的选择非常重要。为尽可能减少对集群性能的影响，应该考虑以下2个条件：1)由于非同源线程之间进行数据的迁移合并可能会出现数据不匹配的问题，因此应该选择非关键节点非关键线程的同源线程；2)数据迁入线程首先需要考虑对集群性能的影响，因此应尽可能查找关键节点非关键线程作为数据迁入的线程。针对数据迁入线程的选择问题，提出算法2，确定线程数据迁移的最优方法。此外，算法2根据是否存在关键节点非关键线程分为关键线程中的数据迁移合并算法（DMMCE,data migration and merging among critical executor）与非关键线程中的数据迁移合并算法（DMMNE,data migration and merging among non-critical executor），具体的算法过程如下所示。

算法2数据迁移合并算法

算法2选择数据迁入的线程。根据最优线程数据重组原则，选择最优迁入数据的线程。步骤1)判断集群是否允许进行数据迁移；步骤13)～步骤21)根据集群性能不变的前提下，完成数据迁移；步骤18)～步骤27)根据集群能效比的变化，完成数据迁移；步骤22)更新Zookeeper的配置文件，防止因拓扑路径发生改变而对集群数据传输与处理造成影响。

集群应在限制时间开销的前提下执行数据迁移合并算法。首先，算法2判断非关键节点非关键线程是否存在同源的关键节点非关键线程，其时间复杂度为O(1)；其次，若存在同源的关键节点非关键线程，则需要将数据迁移到该线程，若关键路径发生改变，则循环查找下一个同源关键节点非关键线程，其时间复杂度为O(nT)′；最后，若不存在同源的关键节点非关键线程，则需要查找同源的关键节点关键线程，并将数据迁移到该线程，在集群能效比低于原集群后，则循环查找下一个同源关键节点关键线程，其时间复杂度为O(nR)′。则算法2的时间复杂度T(B)为

其中，T′表示拓扑执行DMMNE算法后集群数据处理及传输总时间，R′表示拓扑执行DMMCE算法后集群的能效比。

4.3 节点降压算法

根据3.4节与3.5节可知，集群执行节点降压算法需要计算非关键节点电压的最低值，因此需要节点降压原则。

在满足算法1与算法2的前提下，为计算集群执行节点降压算法后非关键节点电压的最低值，需要针对不同的节点降压制约条件进行分析。其制约条件主要分为以下两点：1)在非关键节点降压过程中，集群拓扑关键路径不发生改变；2)需要针对不同的模型确定每次节点电压的改变量。针对非关键节点的降压原则，提出算法3。同理，算法3根据是否存在关键节点非关键线程分为关键线程中的数据迁移合并节能算法（EDMMCE,energy-efficient algorithm for data migration and merging among critical executor）与非关键线程中的数据迁移合并节能算法（EDMMNE,energy-efficient algorithm for data migration and merging among non-critical executor），具体的算法过程如下所示。

算法3节点降压算法

算法3根据不同的节能算法分别对非关键节点进行降压调节，达到节能的目的。步骤2)～步骤8)针对集群拓扑执行DMMNE算法后，并根据集群性能不变的前提下，计算非关键节点电压的最低值。步骤10)～步骤16)针对集群拓扑执行DMMCE算法后，并根据集群能效比，计算非关键节点电压的最低值。

与算法1与算法2相同，集群执行节点降压算法同样需要注意算法的时间复杂度。首先，算法3需要判断集群拓扑是否执行DMMNE，其算法时间复杂度为O(1)；其次，根据集群拓扑数据处理及传输时间不变的前提下，计算非关键节点电压的最低值，其算法时间复杂度为O(1)+O(nT′)；最后，根据集群能效比，计算非关键节点电压的最低值，其算法时间复杂度为O(1)+O(nR′)。则算法3的时间复杂度T(C)为

此外，根据算法评估可以看出，算法3包括这2个算法，即EDMMNE与EDMMCE。且必须在满足算法1与算法2的前提下，集群拓扑才能执行这2个算法。因此集群拓扑执行EDMMNE的时间复杂度为

集群拓扑执行EDMMCE的时间复杂度为

4.4 能耗模型

Storm集群在执行拓扑时的能耗一般分为2类，分别为基础能耗与动态能耗，其中基础能耗为物理机的待机能耗，一般来说，同一种类型物理机的基础能耗是一个固定常量。动态能耗表示集群执行拓扑时数据处理及传输的能耗，一般根据任务的不同，产生的能耗也不相同，因此动态能耗是一个变量。定义在一段时间t内基础能耗为，动态能耗为，则Storm集群在执行拓扑时的总能耗Et为

其中，Pdynamic表示集群在执行拓扑时的功耗，定义集群未执行节能策略时的能耗为，执行节能策略后的能耗为，则执行节能策略后节约的能耗为

将式(30)代入式(29)，化简得到集群执行DMM-Storm节约的能耗为

其中，P1表示集群执行EDMMNE后集群的功耗，P2表示集群执行EDMMCE 后集群的功耗，M表示集群数据量。根据式(30)可知，集群拓扑执行2种算法后节约的能耗为

根据3.2节可知，集群数据处理及传输总时间等于集群路径总开销，因此将式(4)代入式(32)化简得

其中，式(33)中的相关参数与式(4)、式(32)相同，表示集群拓扑执行2种算法后节约的总能耗。

5 实验与评价

本文实验的目的为验证数据迁移合并节能策略的有效性。其主要的评估指标包括集群的吞吐量、CPU资源占用率、内存资源占用率、能耗与能效比等，实验选取Intel公司发布在GitHub上的基准测试[10]，最后对实验结果进行评估和分析。

5.1 实验环境

为验证DMM-Storm的有效性，实验需要将Storm集群部署在19台普通PC机上，且每台PC机的网卡统一为100 Mbit/s LAN，内存统一为8 GB。根据不同节点的运行状况，具体硬件配置如表1所示。

表1 Storm集群配置

其中，控制台节点UI、关联节点Zookeeper1（Leader）与主控节点Nimbus运行在同一台物理机上。从节点Supervisor1～Supervisor16与关联节点Zookeeper2、Zookeeper3（Follower）分别部署在18台不同PC机上。此外，随机从16台包含工作节点的PC机上选定3台进行nmon测试监控，记录CPU占用率、网络带宽占用率及内存占用率等信息。各节点软件配置如表2所示。

表2 Storm集群软件配置

为全面测试DMM-Storm在各类不同资源开销下的有效性，实验选取4组基准测试，分别是CPU敏感型（CPU-Sensitive）的WordCount、网络带宽敏感型（Network-Sensitive）的Sol、内存敏感型（Memory-Sensitive）的RollingSort和Storm在真实场景下的应用RollingCount。各基准测试运行时工作进程数量与当前所需的工作节点数量保持一致（即一个工作节点对应一个工作进程），具体的参数配置如表3所示。

表3 基准测试参数配置

表3中，component.xxx_num表示该基准测试组件并行度，SOL中的topology.level表示拓扑的层次，需要设置为大于或等于2的整数，这里设置为3，结合component.xxx_num的配置参数来看，表示一个spout组件运行着60个实例，2个bolt组件运行着120个实例。此外，4组基准测试统一设置topology.works为16，表示各基准测试运行时一个工作节点内仅分配一个工作进程；统一设置topology.acker.executors为16，表示保证线程间数据流的可靠传输；为防止元组传输因超时而重传，通过多次实验结果统一设置 topology.max.spout.pending为200；最后，统一设置每个message.size等于一个tuple的大小。

为验证DMM-Storm的效果，本文还与WNDVR-Storm[42]进行了对比。该策略的核心思想为通过动态调节工作节点内存电压实现节能的目的。该节能策略为流式处理节能策略的代表，且包括关键路径节能（DVRCP,DRAM voltage regulation on critical path）与非关键路径节能（DVRNP,DRAM voltage regulation on non-critical path）2个算法。表4列举了WNDVR-Storm在基准测试RollingCount上的配置参数。表4中的β与γ分别表示工作节点CPU使用率与数据传输量的阈值，表4内的结果都是通过对RollingCount进行采样获得。component.spout_num与component.bolt_num分别为60与120，topology.works与topology.acker.executors都是16，是为了与本文的策略保持一致，保证在同等条件下验证策略的有效性。

表4 WNDVR-Storm参数配置

5.2 执行节能策略的电压选择

为便于观测，以下测试均设置metrics.poll为5 000 ms，metrics.time为300 000 ms，即每组实验每5 s进行一次采样，时长为5 min。

5.2.1 数据迁移测试

为了集群内数据迁移能够正常执行，现对集群关键节点各类资源的占用率进行测试，并统计集群执行数据迁移合并算法后关键节点各类资源的占用率，具体的结果如图4所示。

图4为RollingCount下各类资源的占用率对比，同理可得，WordCount、Sol与RollingSort这3个基准测各类资源的占用率对比。为观察集群执行数据迁移合并算法的具体效果，表5统计了各类资源占用情况的平均值。

图4 集群执行RollingCount后，各类资源的占用率对比

表5 集群执行不同基准测试各类资源的占用率

根据图4与表5可知，集群执行数据迁移合并算法后关键节点各类资源的占用率急剧上升，数据迁移合并算法效果明显，且执行DMMNE与DMMCE的资源占用基本相同。此外，由图4可知，策略对集群3类资源的占用率的影响时长在第45～65 s，共耗时约20 s，资源占用率急速上升，其原因为集群拓扑执行数据迁移合并算法，数据迁移过程中，集群资源消耗巨大。65 s后集群资源占用率趋于稳定，由此，非关键节点线程上的数据顺利迁出，并可通过节点降压原则降低非关键节点电压，从而实现节能的效果。

5.2.2 节点降压测试

根据3.4节可知，节点降压原则存在2个制约条件，即非关键节点电压的限制条件与非关键节点电压的改变量，其中执行EDMMNE算法，非关键节点电压的限制条件为集群性能；执行EDMMCE算法，非关键节点电压的限制条件为集群能效比。集群性能可通过单位时间内数据的传输及处理速率表示，集群能效比可通过单位时间内的集群功耗表示。非关键节点电压的改变量可通过式(15)与式(22)确定。则原集群5 min内集群吞吐量以及功耗可通过图5表示。

图5 原集群吞吐量与功耗

由图5可知，通过使用DVFS[38]技术，集群执行EDMMNE，规定单位时间内数据的传输与处理速率不发生改变，则可每次以vc为步长降低非关键节点电压；集群执行EDMMCE，规定集群能效比不低于原集群，则可每次以vc′为步长降低非关键节点电压。图6为RollingCount下，集群执行2种算法非关键节点电压的改变情况。

图6 集群执行RollingCount后，2种算法非关键节点电压的改变情况

由图6可知，集群执行EDMMNE非关键节点电压的最低值为1.01 V，集群执行EDMMCE非关键节点电压的最低值为1.03 V。同理可得，WordCount后，集群执行EDMMNE非关键节点电压的最低值为1.06 V；集群执行EDMMCE非关键节点电压的最低值为1.05 V。Sol后，集群执行EDMMNE非关键节点电压的最低值为1.04 V；集群执行EDMMCE非关键节点电压的最低值为1.05 V。RollingSort后，集群执行EDMMNE非关键节点电压的最低值为1.03 V；集群执行EDMMCE非关键节点电压的最低值为1.02 V。

此外，该实验通过降低电压带来的集群拓扑数据处理及传输延迟的问题，但由于集群的关键路径不发生改变，因此在这里不做过多的叙述说明。

5.3 数据迁移合并节能策略实验结果分析

本节首先讨论在Storm默认的调度策略与DMM-Storm下，分别对WordCount、Sol与RollingSort进行功耗测试，具体实验结果如图7所示。

由图7可知，45 s前Storm默认的调度策略与DMM-Storm的功耗基本相同，而45～65 s，共耗时约20 s，集群执行DMM-Storm的功耗急剧上升，其原因为集群在此期间执行数据迁移合并算法，集群资源占用率消耗巨大，因此集群功耗急剧上升。之后70～90 s，共耗时约25 s，集群执行默认的调度策略与DMM-Storm的功耗又逐渐接近，其原因为执行数据迁移合并算法并不改变集群的功耗。95～115 s，共耗时约20 s，集群执行DMM-Storm的功耗缓慢降低，其原因为集群在此期间执行节点降压算法。120 s之后集群功耗趋于稳定，集群执行DMM-Storm的功耗明显低于原系统。集群120 s后的功耗结果如表6所示。

表6 集群稳定后的功耗统计

根据表6可知，集群执行DMM-Storm的功耗远低于原集群功耗。此外由于不同的基准测试集群的拓扑并不相同，因此为检测策略在真实环境下的节能效果，需要对RollingCount进行测试。

RollingCount作为Storm平台下的一个大数据经典应用程序，广泛应用到各类大数据需求的实时应用场景。本实验采用RollingCount对集群真实环境中的功耗进行统计，并计算其实际的能耗。此外，引入WNDVR-Storm与Storm默认的调度策略以及DMM-Storm作对比，其中WNDVR-Storm的配置参数与表4相同。图8为RollingCount在不同节能策略下的功耗及能耗对比。

图7 3种基准测试下集群的功耗情况

图8 RollingCount下集群的功耗与能耗

根据图8(a)可知，集群功耗随着时间的上升不断增加，其中Storm默认的调度策略与WNDVR-Storm在50 s之后趋于稳定，而DMM-Storm则在115 s后趋于稳定，其原因为在40～115 s，共耗时75 s，集群执行数据迁移合并算法与节点降压算法。集群功耗趋于稳定后，DMM-Storm与WNDVR-Storm的功耗都远低于Storm默认的调度策略，执行EDMMNE的平均功耗为915.76 W，执行EDMMCE的平均功耗为922.81 W，执行DVRNP的平均功耗为928.13 W，执行DVRCP的平均功耗为851.43 W，Storm默认的调度策略的平均功耗为1 054.58 W。此外虽然执行WNDVR-Storm的平均功耗低于DMM-Storm，但是执行WNDVR-Storm的功耗波动较大，非常不稳定，且策略实现较为困难，不适合在大规模集群范围内使用。根据图8(a)计算集群能耗获得图8(b)，由图8(b)可知，30 s之前集群的能耗相同，其原因为2个节能策略中的算法并未触发。集群执行DMM-Storm在190 s之前低于Storm默认的调度策略，其原因为DMM-Storm触发了数据迁移合并算法与节点降压算法致使集群能耗增加。此外根据图8(b)可知，120 s之后DMM-Storm的功耗趋于稳定，而WNDVR-Storm上升幅度不断变化且逐渐变高，其原因为随着集群数据量的不断增大，数据量始终超过额定阈值，导致WNDVR-Storm基本失效。集群执行EDMMNE与EDMMCE分别与原集群能耗作对比，执行EDMMNE将原系统的能耗降低了28.1%，执行EDMMCE将原系统的能耗降低了27.6%。综上所述，DMM-Storm取得了较为理想的节能效果。

5.4 实验规模局限性与有效性评估

由于缺少更多的物理节点，实验选择通过虚拟机建立更多的虚拟节点对集群规模的局限性进行评估，实验分别建立32、48、64、80个工作节点与原集群16个工作节点进行对比，检验大规模集群下节能策略的有效性，具体结果如图9所示。

图9 扩大节点规模后2种算法的效果

由图9可知，随着节点数的增加，2种算法节能效果并未受到影响。由于随着节点数总量的增加，非关键节点的数量也在不断增加，2种算法都是降低非关键节点电压而达到节能的效果，因此并不受集群规模的影响。但策略并未考虑集群规模对性能的影响，现根据节点数的增加计算集群性能，具体的实验结果如图10所示。

由图10可知，随着集群规模的扩大，执行EDMMNE的性能基本不受影响，而执行EDMMCE集群性能随节点数的增加不断下降，且集群性能的下降符合线性关系，因此，根据图10可得出EDMMCE的理论函数为

由式(35)可知，执行EDMMCE因节点数增加而对集群性能造成一定的影响，因此DMM-Storm存在一定的局限性。

图10 扩大节点规模后2种算法对集群性能的影响

流式大数据处理的节能策略首先应该关注其对集群性能的影响，根据图10可知，执行EDMMNE对集群的性能基本不造成影响，在此不作考虑，而执行EDMMCE对集群的性能造成一定的影响，需要对该模型进行评估，在此引入能效比的概念，具体结果如图11所示。

图11 能效比

由图11可知，执行EDMMNE后的能效比与原集群的能效比基本相等，则执行EDMMNE对集群的性能并不构成影响，但由于式(17)内的常数C存在误差，且不同节点间的能耗不相等，因此测量结果并不相同。进过反复实验测量，误差常数C的取值范围为[0.81,0.96]，则原集群平均能效比为0.0741(s⋅J)-1，执行EDMMNE后的集群能效比为0.0781(s⋅J)-1。综上所述，EDMMNE是完全可行的。

6 结束语

目前，大数据技术飞速发展，各种分布式平台应运而生，其中流式大数据平台因其强大的实时性深受学术界与产业界的关注，而Storm平台作为最重要的流式大数据平台之一，在业界具有强大的影响力。但是由于Storm平台在最初设计时并未考虑能耗的问题，导致其在执行任务时产生的高能耗问题亟待解决。针对这一问题，本文通过分析Storm平台的基本框架，建立了数据分配、路径开销与资源约束3个基本模型，并在此基础上提出了资源约束算法、数据迁移合并算法与节点降压算法。此外，根据节点降压算法，确定了非关键节点电压的最小值，以此降低了非关键节点电压，达到了节能的效果。最后通过4个基准测试验证了策略的有效性。

下一步的研究工作主要包括以下三方面：1)提高Storm平台的计算能力，增强其任务执行的效率，做到提高性能的同时节约能耗，如利用图形处理器（GPU,graphics processing unit）提高集群的计算能力；2)减少集群节点间的通信，增加集群线程间与进程间的通信，通过减少其部分通信开销，缩短任务的执行时间，以达到节能的效果；3)减少部分电子元件的内部时延，提高电子元件的高效性，进而提升集群的整体性能，以至从侧面降低集群能耗。