基于PI反馈的分布式控制系统动态负载均衡算法*
2015-02-18汤峰张平李方黄致祥
汤峰 张平 李方 黄致祥
(华南理工大学 计算机科学与工程学院, 广东 广州 510640)
基于PI反馈的分布式控制系统动态负载均衡算法*
汤峰张平†李方黄致祥
(华南理工大学 计算机科学与工程学院, 广东 广州 510640)
摘要:针对分布式控制系统由于负载不均衡、网络通信量大等引起的时延问题,文中设计了基于请求划分的任务分配模型,提出了基于实时动态比例积分(PI)反馈控制的负载均衡算法.该算法利用增量PI控制的思想,根据服务器节点性能的实时反馈值动态调节服务器节点的分配权值,通过虚拟节点转移算法局部调整虚拟节点的分配,以维护哈希空间的稳定.仿真实验结果表明,该算法实现了分布式控制系统的动态负载均衡,减小了服务器资源消耗及用于存取远程数据的通信开销,提高了控制系统的实时性,具有良好的扩展性和容错性.
关键词:分布式控制系统;负载均衡;哈希函数;反馈控制
随着计算机水平和控制需求的不断提高,实时性、分布式已成为新一代开放式控制系统发展的趋势,分布式应用将对控制系统起到越来越重要的作用[1].Akyildiz等[2]论述了分布式控制系统中分布式决策、任务分配等具有挑战性的问题,指出任务的合理、均衡调度是分布式系统的技术核心之一.采取有效的负载均衡策略能有效地利用分布式系统的计算能力,提高控制系统的实时性能,因此,对分布式控制系统负载均衡模型的研究具有重要的意义.
负载均衡算法分为静态负载均衡算法和动态负载均衡算法.静态负载均衡算法[3-8]仅根据事先规划分配任务,当节点运行时不能根据负载或性能的变化对任务分配进行调整,由于没有考虑负载的差异及各节点的性能变化,因此其资源利用率和可靠性较低,并且可能出现因节点达到性能瓶颈而使请求无法响应的状态.因此,一些动态调整负载分配的算法被陆续提出[9-10],但这些算法只根据请求差异进行负载分配,没有考虑服务器节点之间的性能差异.而动态反馈负载均衡算法能够根据各节点的性能差异及变化动态调整请求任务的分配策略[11-12],但由于存在系统采集和重分配计算,因此算法复杂、系统开销大、开发成本高、响应时间长.为了能根据节点性能动态调整请求任务的分配,并尽可能保持节点及负载的稳定性,减少不必要的系统开销,提高控制系统的实时性,文中提出了一种基于PI反馈的分布式控制系统动态负载均衡策略.
1分布式系统架构
1.1 架构设计
如图1所示的分布式系统架构采用基于请求划分的任务分配模型.负载均衡器采用基于哈希算法的负载分配策略,根据服务器性能值计算服务器节点的哈希值,确定其虚拟节点在哈希空间的分布,并对服务器节点性能进行监控以动态调整服务器节点的哈希空间分布,当节点的哈希空间有更新时,负载均衡器将服务器节点的哈希空间分布发送给服务请求端,服务请求端计算自身请求消息的哈希值,并映射到哈希空间的某个服务器节点上,将请求消息发送至该服务器节点.数据存储节点存储着系统中所有流程和服务的信息.当服务器节点需要查询的服务处理信息在本地缓存中时,将不需要访问后端存储节点,只需直接根据缓存中的服务信息对服务消息进行处理.只有当前服务对应的信息不在本地缓存上时,才需要访问后端的存储节点,从存储节点的数据库中获取服务信息并更新本地缓存上的信息表.由于数据库的访问开销远远大于本地缓存的访问开销,所以提高缓存命中率对提高分布式控制系统的实时性能有着重要的影响.
图1 分布式系统架构图Fig.1 Architecture of distributed system
由于控制系统的控制任务被封装成多个服务分布在不同的网络节点中,因此,文中控制系统属于分布式控制系统范畴.文中提出了将控制与负载均衡相分离的策略,如图2所示,负载均衡策略不是将任务集中于某个节点,而是分散到各个节点上,以减轻负载集中现象.该策略的具体步骤如下:
(1)各服务器节点计算本节点的负载均衡分配权值,权值有更新时发送给负载均衡器;
(2)负载均衡器周期性采集各服务器节点的状态信息,检测节点的可用性,并根据节点权值变化采用负载均衡算法计算各节点在哈希空间中的分布;
(3)当哈希空间有更新时负载均衡器发送更新信息给服务请求端;
(4)服务请求端根据均衡策略选择服务器节点,并直接向该服务器节点发送服务控制消息.
图2 控制与负载均衡相分离的策略Fig.2 Separation strategy for controlling and load balancing
由于控制任务中的服务控制消息不经过负载均衡器而直接发送给服务器节点,因此,该负载均衡算法并不增加控制任务的负担,即控制流程仅需由服务器节点来处理,减少了因增加负载均衡层节点转发而引起的通信开销,提高了控制系统的实时性.
1.2 通信开销分析
通信开销包括控制任务所产生的通信开销和用于节点管理的通信开销.
节点管理的通信开销跟系统采用的架构及运行状态相关.当系统不存在故障时,其通信开销主要是检测节点状态的开销,当系统发生故障时,通信开销还包括故障通知以及各节点间用于协商故障处理的开销.假设有N个服务器节点,状态信息大小为L,检测信息的发送周期为D,故障节点数为M,则文中架构在正常状态下用于管理的通信开销为NL/D,在故障情况下会增加故障处理信息通信量ML/D,正常情况下服务器节点不会收到故障处理信息.
2负载均衡策略
分布式控制系统负载均衡策略设计中的两个重要问题是控制的有序性和实时性.控制消息的乱序可能会导致整个系统的失控,为了保证控制系统的有序性以及系统的高缓存命中率,应尽量使同一流程的子服务在一个服务器节点上处理,哈希负载均衡算法可以通过对请求的哈希映射来满足这个需求.另一方面,控制系统的高实时性需求,使得在设计负载均衡算法时不宜采用复杂度太高的算法,一致性哈希的实现非常高效,平均算法复杂度为O(1),即在常量时间内就可以完成服务器节点的选择,保证了控制系统的实时性.
文献[13]所述的多重映射的加权一致性哈希算法(MMWCH)是对经典一致性哈希算法[14]的一种改进,MMWCH考虑了物理节点本身的性能以及访问的热点问题[13],但其加权调度算法的权值是静态的,权值固定可能导致节点性能与请求分配相背离,使节点处于性能瓶颈而影响请求的响应实时性.因此,需要结合实时动态调整策略对算法进行优化.但一般的动态性能分配算法是根据服务器节点的性能参数动态分配任务,反复计算降低了系统的稳定性,占用了较多的系统资源,使系统响应时间恶化.
基于系统高资源利用和高可靠性的需求,文中根据增量PI控制原理设计了实时动态PI反馈控制负载均衡策略(PIDLBA),该策略以MMWCH为基础,结合动态调整策略,根据节点性能偏差调节负载分配,并设计了虚拟节点转移算法,用于局部调整虚拟节点与物理节点的映射关系,避免因哈希空间的重映射而引起的系统开销,同时减少重映射造成的大量任务被发往不同节点的现象,提高系统的稳定性和缓存命中率,降低请求的响应时间.
2.1 基于PI反馈的服务器节点分配权值计算
服务器节点每隔一个采集周期对本节点的CPU、内存和网络带宽使用情况进行采集,并计算性能指标值,然后通过PI反馈控制算法得到该节点的分配权值,分配权值被服务器节点推送给负载均衡器以实现负载任务的分配.
(1)
式中,KP为比例系数,KI为积分系数.式(1)是一个负反馈公式,最终会使分配权值达到一个稳定点.服务器节点根据式(1)计算出k时刻的Wi(k)和ΔWi(k),并推送给负载均衡器.
2.2 负载均衡器的任务分配策略
负载均衡器启动时开启两个进程分别对服务器节点和服务请求端进行监控.服务器节点的监控进程主要完成服务器节点的哈希值映射工作:首先根据服务器节点提供的分配权值计算各物理节点的虚拟节点数,通过哈希函数计算虚拟节点哈希值,并将其映射到哈希空间上;随后每隔一个负载均衡计算周期,负载均衡器判断节点是否需要调整,若是,则采用虚拟节点转移算法对其进行动态调整.综合考虑分配的均衡性、时间消耗等因素,文中采用Toeplitz哈希[15]作为Hash函数.服务器节点监控进程如图3所示,具体过程详述如下.
图3 服务器节点监控进程Fig.3 Monitoring process of server nodes
3)若有服务器节点分配权值发生变化,则调用虚拟节点转移算法,该算法的核心是把性能较差的服务器节点的虚拟节点转移给性能较优的服务器,通过调节服务器与虚拟节点之间的映射关系来调节负载的分配.虚拟节点转移算法描述如下:
(2)计算当前k时刻比上一负载均衡周期k-1时刻服务器节点i的虚拟节点数增量ΔNv,i=Nv,i(k)-Nv,i(k-1).
(3)N个服务器节点按其虚拟节点数增量升序排列Ranknodes(ΔNv,1,ΔNv,2,…,ΔNv,N).
(4)计算虚拟节点数增量的平均值ΔNv,avg=(ΔNv,1+ΔNv,2+…+ΔNv,N)/N.
(5)计算虚拟节点数增量与其平均值之差,ΔNv,avg-ΔNv,i>0表示该服务器节点需要减少虚拟节点,ΔNv,i-ΔNv,avg>0表示该服务器节点可以增加虚拟节点.为了减少哈希值及其映射的变化,可以把需要减少的虚拟节点转移给可以增加虚拟节点的服务器节点,转移规则从请求任务量最小的虚拟节点开始转移,其伪代码如下:
{i=1;j=n;
while(ΔNv,avg-ΔNv,i>0 && ΔNv,j-ΔNv,avg>0)
if ΔNv,avg-ΔNv,i>=ΔNv,j-ΔNv,avgthen
Transmitvi(i,j,ΔNv,j-ΔNv,avg);
∥将服务器节点i的ΔNv,j-ΔNv,avg个任务量最小的虚拟节点转移给服务器节点j,并记录服务器节点i和j的虚拟节点数的变化
Upadatevi(ΔNv,i);
∥更新ΔNv,i=ΔNv,i+ΔNv,j-ΔNv,avg
j--;
∥服务器节点i的虚拟节点依次向虚拟节点数增量次高ΔNv,j-1的服务器节点转移
elseif ΔNv,avg-ΔNv,i<ΔNv,j-ΔNv,avgthen
Transmitvi(i,j,ΔNv,avg-ΔNv, j);
∥将服务器节点i的ΔNv,avg-ΔNv, j个任务量最小的虚拟节点转移给服务器节点j,并记录服务器节点i和j的虚拟节点数的变化
Upadatevi(ΔNv, j);
∥更新ΔNv, j=ΔNv,i+ΔNv, j-ΔNv,avg
i++;
∥服务器节点j还需要从虚拟节点数增量次低ΔNi+1的服务器节点获取虚拟节点
end while}
4)若虚拟节点有更新,则更新哈希环上虚拟节点分布.负载均衡器继续监听服务器节点的状态信息.
服务请求端监控进程主要实现请求任务的分配.根据服务器节点监控进程中的虚拟节点哈希值,服务请求端查找与服务请求哈希值相匹配的服务器节点.服务请求端把服务请求的元组(流程ID,服务ID,函数ID)作为Toeplitz哈希函数的键值,映射到哈希环上某个点,如果该点没有对应的服务器节点,那么沿哈希环顺时针查找,找到第1个有映射服务器节点的虚拟节点并将请求任务分配给此虚拟节点对应的服务器.
3实验与结果分析
3.1 负载均衡性测试
图4 N=10时执行105次随机流程的服务器节点负载Fig.4 Loads of server nodes after executing 105random process when N=10
表1 服务器节点的最大、最小访问量Table 1 Maximum and minimum access of server nodes
由图4可看出:轮询算法具有绝对的负载均衡性;PIDLBA 和MMWCH算法的负载均衡性远远优于取模哈希算法和随机算法;PIDLBA算法的负载均衡性稍优于MMWCH算法,这是因为当节点性能超出预期时会自动调节分配权值,使负载达到平衡.
3.2 缓存命中率测试
分布式控制系统的负载均衡算法必须具有良好的扩展性,即节点缓存命中率不能随着服务器节点数的增加而大幅下降.为分析算法的节点扩展性,文中通过调节服务器节点数,比较系统在106次随机访问下的缓存命中率,实验结果如图5所示.由图可见,PIDLBA、MMWCH和取模哈希算法都具有良好的扩展性,缓存命中率无明显的下降,而随机算法和轮询算法的缓存命中率由2个节点时的98%下降到1 000个节点时的不及5%.这是因为取模哈希算法的访问节点与数据相关,节点数量的影响不大.而PIDLBA和MMWCH算法的缓存命中率略低于取模哈希算法,主要是由于设定了多重映射.PIDLBA 算法的缓存命中率稍低于MMWCH算法,这是由于PIDLBA 算法在节点性能超出预期时会发生局部虚拟节点转移,导致其缓存命中率微降.
图5 节点扩展对缓存命中率的影响Fig.5 Effect of node expansion on the hit rate of cache
当系统架构及控制任务确定后,与控制任务相关的控制信息及用于节点管理的通信开销随之确定,文中主要分析由不同负载均衡算法引起的与缓存命中率相关的远程数据存储节点的通信开销.
设与远程数据存储节点通信传输数据包大小为256B,图6为远程数据存储节点的通信开销,从图中可见,通信开销最小的是取模哈希算法,其次是MMWCH和PIDLBA 算法,随机算法和轮询算法因缓存命中率的降低而导致其远程数据存储节点的通信开销非常大.
图6 远程数据存储节点的通信开销Fig.6 Communication overhead of the remote data storage nodes
3.3 容错性测试
为了比较各算法的容错能力,文中模拟在一个拥有100个服务器节点的分布式系统中,随机把其中一个服务器节点设为不可用(其请求数为0),并比较各算法在105次随机访问中的缓存命中率变化情况,结果如图7所示.
图7 某节点失效时的缓存命中率变化情况Fig.7 Changes of the hit rate on the cache when a node fails
由图7可见,在某个服务器节点不可用的情况下,PIDLBA、MMWCH、随机算法和轮询算法的缓存命中率都没有发生大的波动,具有良好的容错能力,只有取模哈希算法的缓存命中率几乎为0,然后随着请求数的增加不断提升到90%以上,这是因为节点数的变化影响了绝大多数数据与缓存之间的映射关系,所以出现了大量缓存不命中的情况,显然,取模哈希算法不具有良好的容错性.
3.4 系统响应时间测试
实时性是衡量控制系统性能的一个重要指标,反映控制系统对指令的响应速度和执行效率.为了测量各负载均衡算法对服务请求平均响应时间的影响,文中启动一个简单测试流程由消息发送方发送消息给4个性能相同的服务器节点进行处理,消息大小是256B,服务器节点处理完成后发送信息给消息接收端;然后改变测试流程的并发数,测试过程中给服务器节点1加1个负载干扰,使该节点性能达到0.85以上,记录各服务器节点的性能变化情况,如图8(a)所示.由图8(a)可知,服务器节点1的性能过大时,由负反馈算法减小该节点的分配权值(4个服务器节点的分配权值如图8(b)所示),使分配给该节点的负载减少,而其他节点的负载增加(4个服务器节点的负载量如图8(c)所示),因此,当节点1负载干扰取消时,其性能值略低于其他3个节点的性能,当请求负载增加到一定量时,节点性能接近极限,系统达到饱和状态.
图8 各服务器节点的性能比较Fig.8 Performance comparison of each server node
记录消息发送端的发送时间和接收端接收到消息的时间,并比较各个算法的服务请求平均响应时间,结果见图9.可以看出,PIDLBA 算法的服务请求平均响应时间变化曲线平滑递增,在服务器节点1有负载干扰时,其分配权值降低,被分配到的负载量减少,因此响应时间未受到大的影响.当请求负载增加到一定量(2 400个请求附近)时,响应时间的变化出现抖动,表明系统即将达到饱和状态.MMWCH与PIDLBA算法的服务请求平均响应时间接近,但会有较大的波动,这是因为MMWCH算法只能静态分配权值,当服务器节点遇到干扰性能发生变化时,不能及时地调整请求的分配,导致服务器节点1达到性能瓶颈,延长了其消息的响应时间.随机算法、轮询算法和取模哈希算法的服务请求平均响应时间较大,请求的分配不均衡造成了某些服务器节点性能急剧恶化,从而导致服务请求的等待和处理时间延长,其响应时间及变化波动增大.
图9 几种负载均衡算法的服务请求平均响应时间比较Fig.9 Comparison of average response time of service request among several load balancing algorithms
4结论
文中设计了基于请求划分的分布式控制系统负载均衡模型,提出了一种动态反馈式负载均衡算法PIDLBA,该算法通过PI反馈控制由服务器节点的性能偏差反映节点的分配权值,进而确定物理节点的虚拟节点变化量,然后通过虚拟节点转移算法调整服务请求的分配,实现分布式控制系统的动态负载均衡.对控制系统的扩展性、容错性、实时性的仿真实验结果表明,该模型较好地实现了负载动态平衡,具有良好的扩展性、容错性和实时性.
参考文献:
[1]Stumpfegger Thomas,Tremmel Andreas,Tarragona Christian,et al.A virtual robot control using a service-based architecture and a physics-based simulation environment [R].Augsburg:KUKA Roboter GmbH,2007.
[2]Akyildiz I F,Kasimoglu I H.Wireless sensor and actor networks:research challenges [J].Ad Hoc Networks,2004,2(4):351-367.
[3]Thanalapati T,Dandamudi S.An efficient adaptive schedu-ling scheme for distributed memory multicomputers [J]. IEEE Transactions on Parallel and Distributed Systems,2001,12(7):758-768.
[4]Rai Idris A,Alanyali Murat.Uniform weighted round robin scheduling algorithms for input queued swithes [C]∥Pro- ceedings of IEEE International Conference on Communications.Helsinki:IEEE,2001:2028-2032.
[5]Aumasson J P,Henzen L,Meier W,et al.Quark:a lightweight hash [J].Journal of Cryptology,2013,26(2):313-339.
[6]Moharil S,Lee S.Load balancing of parallel simulated annealing on a temporally heterogeneous cluster of workstation [C]∥Proceedings of the 21st International Symposium on Parallel Distributed Processing.Long Beach:IEEE,2007:1-8.
[7]Moallem A,Ludwig S.Using artificial life techniques for distributed grid job scheduling [C]∥Proceedings of ACM Symposium on Applied Computing.Honolulu:ACM,2009:1091-1097.
[8]Zomaya A,Teh Y.Observation on using genetic algorithms for dynamic load balancing [J].IEEE Transactions on Parallel and Distributed Systems,2001,12(9):899-911.
[9]Bryhni H,Klovning E,Kure O.A comparison of load ba-lancing techniques for scalable web servers [J].IEEE Network,2000,14(4):58-64.
[10]Casal icchio E,Tucci S.Static and dynamic scheduling algorithm for scalable web server farm [C]∥Procee-dings of the 9th Euromicro Worshop on Parallel and Distributed Processing.Mantova:IEEE,2001:369-376.
[11]Lin W,Wang J Z,Liang C,et al.A threshold-based dynamic resource allocation scheme for cloud computing [J].Procedia Engineering,2011,23:695-703.
[12]Song B,Hassan M M,Huh E.A novel heuristic-based task selection and allocation framework in dynamic collaborative cloud service platform [C]∥Proceedings of the 2nd IEEE International Conference on Cloud Computing Technology and Science.Indianapolis:IEEE,2010:360-367.
[13]Decandia Guiseppe,Hastorun Deniz,Jampani Madan,et al.Dynamo:Amazon’s highly available key-value store [C]∥Proceedings of the 21st ACM Symposium on Operating Systems Principles.Washington:ACM,2007:205-220.
[14]Karger David,Lehman Eric.Consistent Hashing and random trees:distributed cache protocols for relieving hot spots on the World Wide Web [C]∥Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing.New York:ACM,1997:654-663.
[15]Krawczyk H.New hash functions for message authentication [C]∥Advances in Cryptology-Eurocrypt’95.Berlin/Heidelberg:Springer,1995:301-310.
[16]Karger David,Sherman Alex,Berkheimer Andy,et al.Web caching with consistent hashing [J].Computer Networks,1999,31(11):1203-1213.
PI Feedback-Based Dynamic Load-Balancing Algorithm for Distributed Control System
TangFengZhangPingLiFangHuangZhi-xiang
(School of Computer Science and Technology, South China University of Technology, Guangzhou 510640, Guangdong, China)
Abstract:In order to solve the problem of slow response caused by the load imbalance and the communication overhead in distributed control systems, a task allocation model is constructed on the basis of the request division, and a dynamic load-balancing algorithm is proposed on the basis of the real-time dynamic proportional integral (PI) feedback control. This algorithm adopts the PI control method to dynamically adjust the allocation weight of server nodes according to the real-time feedback values of the performance of the nodes, and then employs the virtual node transfer algorithm to partially adjust the distribution of virtual nodes, so as to maintain the stability of Hash space. Simulation results show that the proposed algorithm realizes the dynamic load balancing of distributed control system, reduces the communication overhead and improves the real-time performance of the control system, and that the proposed algorithm is of a high expansion and an excellent fault tolerance.
Key words:distributed control systems; load balancing; Hash functions; feedback control
中图分类号:TP273
doi:10.3969/j.issn.1000-565X.2015.09.013
作者简介:汤峰(1979-),女,博士生,工程师,主要从事机器人控制研究.E-mail: fengtang@scut.edu.cn† 通信作者: 张平(1964-),男,博士,教授,主要从事机器人控制研究.E-mail: pzhang@scut.edu.cn
*基金项目:广东省科技计划项目(2014B090921007);广州市科技计划项目(20150810068);广州市海珠区科技计划项目(2014-cg-02)
收稿日期:2015-01-22
文章编号:1000-565X(2015)09-0081-07
Foundation item: Supported by the Science and Technology Planning Projects of Guangdong Province(2014B090921007)