基于Storm slot使用率低优先的动态负载均衡策略
2017-04-17 18:44黄容王贤稳
电脑知识与技术 2016年36期
关键词：负载均衡
黄容++王贤稳
摘要：Storm现有的负载均衡机制，会导致集群节点slot资源使用不均衡，而且在集群节点资源变化后，也无法动态调度各节点负载。针对该问题，该文提出基于slot使用率低优先的动态负载均衡策略。该策略在给Topology分配slot计算资源时，优先分配slot使用率低的节点；当集群可用资源变化时，对节点按照负载从高到低排序，并将高负载节点上的任务动态迁移到低负载节点上，实现动态负载均衡。实验结果表明，基于slot使用率低优先的动态负载均衡策略能够有效促进Storm集群负载均衡，提升Storm集群的计算性能。
关键词：Storm集群；实时计算；slot使用率；动态迁移；负载均衡
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）36-0008-04
Dynamic Load Balance Strategy Based on Low Priority of Slot Usage
HUANG Rong，WANG Xian-wen
（Chongqing University of Posts and Telecommunications， Chongqing 400065， China）
Abstract： The default load balance mechanism of Storm can lead to the use of cluster node slot resources is not balanced. Besides， it can not dynamically schedule each node load after the resources in the cluster nodes changes. To solve this problem， this thesis proposes a dynamic load balance strategy based on the low priority of slot usage. When distribute slot computing resources for Topology， the strategy gives priority to slot with low rate of usage. When the cluster resource availability changes， the strategy will rank the nodes according to the load from high to low， and will dynamically migrate load from high load nodes to low load nodes， achieving dynamic load balance. The experimental results show that the strategy can effectively promote the Storm cluster load balance， and enhance the performance of the Storm cluster.
Key words： Storm cluster； real-time computing； slot usage； dynamic migration； load balance
1 背景
Storm[1-3]是一款分布式的、可擴展的、容错性良好、可靠性高的开源实时计算系统，被广泛应用于实时计算、流式计算[4]、分布式RPC、机器学习、ETL等方面，受到国内外互联网企业的青睐，有成熟的商用经验。
负载均衡技术[5]是Storm集群高效率的保证，然而Storm在负载均衡方面的表现却无法令人满意，存在着较多的问题。主要表现为：Storm默认的轮询调度算法，会导致集群节点资源使用的不均衡；在集群中添加、删除节点后，或者集群中添加、删除worker进程，从而导致集群计算资源的变化，Storm也无法根据改变后的可用资源做出有效调整策略。
针对Storm现存的负载均衡问题，本文提出基于slot使用率低优先的动态迁移负载均衡策略。该策略统计集群节点slot使用率，并标记slot使用率最低的节点，优先分配该节点上的slot资源。当集群可用资源变化时，对节点按照负载从高到低排序，并将高负载节点上的负载动态迁移到低负载节点上，实现动态负载均衡。
2 相关工作
负载均衡技术是保证Storm实时计算应用高性能和高吞吐量的有效手段。Storm实时计算应用通常是计算密集型应用，负载均衡对Storm实时计算应用的执行性能起着决定性的作用。
2.1 Storm在负载均衡方面的缺陷
1）Storm默认的轮询调度算法，会导致集群节点slot资源使用的不均衡。
2）Storm集群中资源变化后，无法动态调度各节点负载。
2.2 相关研究
文献[6]提出的动态负载均衡技术，其核心思想概括如下：在执行计算任务的多个节点上，将这个计算任务包含的所有算子都进行多实例部署，当其中一个算子实例出现负载过重时，动态负载均衡技术会将该算子实例的部分负载分配给其他负载较轻的算子实例。然而，这种负载均衡技术适用于无状态的算子，而比较难适用于有状态的算子；并且一个算子存在着多个算子实例，且被分配到不同节点上运行，则参与任务计算的算子实例和备用空闲的算子实例需要共享计算资源。
关于Storm负载均衡任务调度算法方面，有的针对Storm Topology组件运行时分配角度来考虑，如文献[7]提出了一个改进的调度器——Online Scheduler，但是算法效率较低，而且缺乏实用性验证；有的研究侧重从Storm应用场景方面来考虑，如文献[8-9]，但这类算法并没有针对Storm自身的机制来做改进；还有的研究偏向从Storm资源需求角度来入手，如文献[10-11]，这类算法属于静态调度，并不一定适用于Storm集群运行时环境。总的来说，这些算法从不同角度考虑，在一定程度上提升了Storm处理性能，但都存在各自的问题。
3 slot使用率低优先策略
Storm把集群中各个节点可用的所有slot作为一个整体来调度，而没有考虑到各个节点已使用的slot的情况，导致集群slot资源使用不均匀的情况，即集群负载不均衡。针对该问题，本方案结合当前各个节点空闲的slot情况来调度，采用slot使用率低优先策略，即优先分配slot使用率低的节点，那么就可以在一定程度上使得集群的负载较为均衡。这里，我们定义slot使用率为已使用的slot数目除以总的slot数目。
slot使用率低优先策略对应的算法流程如图1所示。
图1 slot使用率低优先算法流程
4 动态迁移负载均衡算法
当Storm集群运行时间达到一定长度之后，集群中各个节点上可以使用的slot数目各不相同。某些情况下，还会进行节点的添加和删除操作。动态地添加或者删除节点，会引起集群负载变化，往往需要重新均衡负载。尤其是当新的节点加入到集群后，该节点上可用的slot资源非常丰富，而此时集群中的某些节点可能出现幾乎没有slot资源可用的情况。新加入节点上的负载与集群中现有节点上的负载明显不均衡，所以需要对集群进行负载均衡调度。算法用到的相关符号参照表如表1。
4.1 算法步骤
（1）统计集群中所有节点包含的slot的总数量，记作Ts；统计当前所有Topology已使用的slot数量，记作Us。利用Ts和Us来计算当前集群中slot的平均使用率，记作As。平均使用率所对应的计算公式如式（1）所示：
[As=Us÷Ts] （1）
（2）遍历集群中的节点，统计当前节点所包含的slot数量，记作Ns；统计当前节点已经被使用的slot数量，记作Nus。利用Ns和Nus来计算当前节点slot的平均使用率，记作Nas。当前节点slot平均使用率计算公式如式（2）所示。
[Nas=Nus÷Ns] （2）
（3） 建立slot使用情况的四个队列，分别为OverUsedNodes、AboveAvgUseNodes、BelowAvgUseNodes以及UnderUsedNodes。其中队列OverUsedNodes说明该队列内的节点，slot使用率非常高，超过阈值Th（阈值大小一般为15%，可以更改）；队列AboveAvgUseNodes说明该队列内的节点，slot使用率较高，超过了集群节点平均值；队列BelowAvgUseNodes说明该队列内的节点，slot使用率较低，小于集群节点平均值；队列UnderUsedNodes说明该队列内的节点，slot使用非常低低，远小于集群节点平均值。
（4）遍历集群中的节点，并根据以下条件将当前节点加入步骤3所对应的队列中：
1）如果当前节点slot使用率满足公式（3）
[Nas>As+Th] （3）
则将当前节点加入到队列OverUsedNodes中。
2）如果当前节点slot使用率满足公式（4）
[As 则将当前节点加入到队列AboveAvgUseNodes中。 3）如果当前节点slot使用率满足公式（5） [As-Th<=Nas 则将当前节点加入到队列BelowAvgUseNodes中。 4）如果当前节点slot使用率满足公式（6） [Nas 则将当前节点加入到队列UnderUsedNodes中。 （5）按以下步骤来调节集群节点的负载均衡： 1）将OverUsedNodes（Source）队列内节点的负载，平衡到UnderUsedNodes（Target）队列内的节点； 2）将AboveAvgUseNodes队列内节点的负载，平衡到BelowAvgUseNodes（Target）队列内的节点； （6）对于步骤5中的操作，其每一步操作的方式为： 1）分别从Source队列和Target队列选择一个节点S和节点T，组成 2）计算源节点S所需要平衡的负载量，记作Ls；计算目标节点T所能接收的负载量，记作Lt。取Ls和Lt中较小的值，记作Lb，则Lb为从源节点S平衡到目标节点T的负载量。在平衡过程中，还需要记录源节点S已平衡的负载量和目标节点T已接收的负载量。 3）最大化平衡 4）源节点和目标节点之间是多对多的关系，即一个源节点的负载，可以平衡到不同的目标节点中；而一个目标节点，也可以接收来自不同源节点的负载。 （7） 如果此时集群已经达到负载均衡状态，则负载均衡调节结束；否则，转步骤1重新开始平衡。 5 实验结果与分析 5.1 实验环境 实验环境搭建了6个节点的Storm完全分布式集群。实验平台中，每个节点的具体硬件配置如表2所示。 实验环境所对应的集群架构如图2所示。每个节点上都安装运行Ubuntu 12.04操作系统，JDK的版本为1.7.0_25，Storm安装版本为storm-0.8.1，节点之间通过10 Gbit LAN网卡相连。集群中的主节点上运行着Nimbus进程，从节点上运行这worker进程，每个从节点上配置8个slot资源。主节点配置相比于其他节点较高，因为主节点需要承担任务的接受、部署、调度，是整个Storm集群的核心。从节点采用相同的硬件配置，以消除由工作节点的异构带来的负载不均衡。
5.2 实验方案
选取不同的4个Topology来进行实验，Topology任务具体配置如表3所示。初始实验条件下，不使用集群中的从节点4和从节点5，将4个Topology依次提交到集群中计算。Topology提交完成并运行一段时间后，将从节点4和从节点5启用，增加集群可用的slot资源，做集群负载迁移实验。
5.3 实验结果
1）实验一：slot使用率低优先策略
将4个Topology依次提交到由主节点和从节点1、从节点2、从节点3组成的集群环境中，针对Storm默认的slot使用机制以及slot使用率低优先策略两种情况，分别进行30次实验，并统计实验中各从节点slot使用率，取30次实验的平均值来作为分析依据。
图3显示的是两种实验条件下集群节点slot使用率的差别。从实验结果可以看到，在Storm默认的slot机制中，从节点1的slot使用率高达65.5%，而从节点3的slot使用率仅达到12.5%，3个从节点之间slot使用率差别较大；在slot使用率低优先策略中，从节点1的slot使用率为50%，而从节点2以及从节点3的使用率都为37.5%，3个从节点之间的slot使用率较为均等。
图3 实验一slot使用率对比
实验结果表明，基于slot使用率低优先策略改進的任务分配机制，集群中各节点slot使用率较为均等，在一定程度上改善了集群负载均衡状况。
2）实验二：节点负载均衡迁移
在实验一的基础上，启用集群中的从节点4和从节点5，继续进行负载均衡迁移实验。观察实验过程中，从节点1、从节点2、从节点3上负载的迁移情况，并统计负载均衡迁移完成时所有从节点上slot使用率。
节点负载均衡迁移前后，各从节点slot使用率如图4所示。从实验结果可以看到，节点负载均衡迁移之前，从节点1和从节点2的slot使用率较高，分别达到62.5%和50%；当集群中加入新的可用节点从节点4和从节点5时，对集群进行节点负载均衡迁移后，降低了原来从节点1和从节点2的slot使用率，且集群中的5个从节点slot使用率都相等，均为25%。
图4 实验二slot使用率对比
实验结果表明，在集群中新加入节点后，利用节点负载均衡迁移机制，能够较好地将原来节点上的负载分摊到新的节点上，实现集群中节点的整体负载均衡。
6 结束语
本文针对Storm默认的轮询调度算法导致集群节点资源使用率的不均衡以及在集群中添加、删除节点后导致集群计算资源的变化而Storm无法根据改变后的可用资源做出有效调整策略的问题，提出了基于slot使用率低优先的动态迁移负载均衡策略。该策略在给Topology分配slot计算资源时，优先分配slot使用率低的节点；当集群中可用计算节点增加时，能够在节点之间动态迁移负载。实验结果表明，基于slot使用率低优先及动态迁移负载均衡策略能够有效促进Storm集群负载均衡，提升Storm集群的计算性能。
参考文献：
[1] Toshniwal A， Taneja S， Shukla A， et al. Storm@ twitter[C]//Proceedings of the 2014 ACM SIGMOD international conference on Management of data. ACM， 2014： 147-156.
[2] Simoncelli D， Dusi M， Gringoli F， Niccolini S. Scaling out the performance of service monitoring applications with BlockMon. In： Proc. of the 14th Intl Conf. on Passive and Active Measurement （PAM 2013）. Hong Kong： IEEE Press， 2013. 253?255.
[3] 孙大为， 张广艳， 郑纬民. 大数据流式计算： 关键技术及系统实例[J]. 软件学报， 2014， 25（4）： 839-862.
[4] 顾昕. 分布式流式计算框架关键技术的研究与实现[D]. 北京： 北京邮电大学， 2012.
[5] 彭书凯. 分布式流计算框架中负载管理功能的设计与实现[D]. 北京： 北京邮电大学， 2013.
[6] Collins R L， Carloni L P. Flexible filters： load balancing through backpressure for stream programs[C]// Proceedings of the seventh ACM international conference on Embedded software. ACM， 2009： 205-214.
[7] Aniello L， Baldoni R， Querzoni L. Adaptive online scheduling in storm[C]//Proceedings of the 7th ACM international conference on Distributed event-based systems. ACM， 2013： 207-218.
[8] Long Shaohang， Rao Ruonan， Miao Wangsheng， et al. An improved topology schedule algorithm for storm system[C]//Computer Science and Applications： Proceedings of the 2014 Asia-Pacific Conference on Computer Science and Applications （CSAC 2014）， Shanghai， China， 27-28 December 2014. CRC Press， 2015： 187.
[9] Cardellini V， Grassi V， Lo Presti F， et al. Distributed QoS-aware scheduling in storm[C]//Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems. ACM， 2015： 344-347.
[10] Peng B， Hosseini M， Hong Z， et al. R-Storm： Resource-Aware Scheduling in Storm[C]//ACM MIDDLEWARE '15 Proceedings of the， ACM MIDDLEWARE Conference. 2015.
[11] Sun Dawei， Zhang Guangyan， Yang Songlin， et al. Re-Stream： Real-time and energy-efficient resource scheduling in big data stream computing environments[J]. Information Sciences， 2015.
