负载均衡技术综述(4)

3.2.2 动态负载平衡调度

1) 集中式调度

在集中式调度中，所有任务的调度都是由一个调度服务器，即“负载均衡器”来完成的。“负载均衡器”负责搜集系统负载信息，并决定负载平衡调度方案。集中式调度实现比较简单，很容易获得各服务器的负载信息，可以根据NodeLoadList列表进行负载快速转移，具有控制集中，调度有力等优点。但在结点数较多的大规模并行分布系统中，由于各结点与调度服务器的通讯成为瓶颈，所以调度开销比较大[12,13,14]；另一方面，在客户终端任务到达很密集的情况下，任务在“负载均衡器”上的排队等待时间就会大大增加任务处理总时间。所以，除非结点数目较少，或者在底层硬件系统中采取比如超级集线器这样的一些特殊实现措施[15]，否则在分布存储的并行系统中不大采用集中式平衡调度方法[16]。

2) 分布式调度

在分布式调度中，没有负载均衡器，任务被分配给所有服务节点，通过服务器间的交互，每台服务器都有其他服务器的负载信息，即都有NodeLoadList 列表，由本服务器完成任务的调度，当负载饱和时可以将一部分任务转移到其他轻载服务器。分布式调度的最大优点在于具有良好的可扩放性，具有很强的容错能力，不会出现集中式负载均衡那样瓶颈问题。目前常用的分布式负载平衡调度方法主要有基于随机选择任务移动结点的概率调度算法[17]、根据负载变化差额而基于梯度(Gradient)模型的调度算法[18]以及自适应的近邻契约算法[19]等。但是在分布式调度算法中，每台服务器都需定时向其他服务器广播其负载信息，发送负载信息总数为：N=n(n-1),其中n 为服务器总数目，N 为系统负载更新信息数。因此，服务器之间的交互信息量N 随着服务器数目的增加而成倍增加，将会占用大量的网络资源，从而导致系统性能下降。其次，由于所有服务器都具有相同的负载信息表，所有重服务器都会把负载转移到同一台轻服务器，从而导致轻服务器负载急剧增大，很快变为重服务器，如此反复，导致任务不能及时处理。

3) 混合/层次调度

为了最小化负载均衡开销，一些负载均衡方法重在研究如何根据层次拓扑结构来构建一个层次树的问题。HBM[20]利用层次树进行多级负载均衡，根据层次化的网络结构将处理器划分为多个组(均衡域)，由这些均衡域组织成一个层次结构。在层次结构中的每一层，相邻的域间进行负载均衡，并且从底层至上层，在每层执行相同的域间负载均衡过程,最后在根节点完成全局的负载均衡。混合策略(HybridLB)[21]类似于传统的层次负载均衡策略，将处理器划分为多个独立的、自治的组，并将这些组按层次结构进行组织。每层中的每个子树的根节点与其所有子节点形成一个负载均衡组，根节点充当该均衡组的头节点，控制负载均衡组内的负载均

衡过程，充当类似集中式策略中央节点的功能。第i层的根处理器参与由第i+1层(层的序号由底至上递增)的头节点控制的负载均衡过程，但第i层各节点的子节点不参与第i+1层的负载均衡过程。与HBM不同的是，HybridLB可在不同的层采用不同的策略，并最小化任务传输的距离和数量以优化负载均衡的通讯开销[22]。

论文[22]中列举以上三种调度常用算法和算法性能比较，此处不再详述。

4 总结

本文通过负载均衡技术分类方式、负载均衡技术和负载均衡算法三个方面对负载均衡做了介绍。其中，DLB(动态负载均衡)是现在应用最广泛的一种方式，随着新兴的多/众核相关技术和应用的出现及进一步发展，DLB技术的重要性日益凸显。但是现有的动态负载平衡算法不尽完善，比如有些DLB算法每次运行只选择一个符合条件( 负载最轻[23]、距离最近[24]、其他约束条件[25]) 的轻载节点作为负载迁移的目标节点，负载迁移后, 若重载节点仍过载，则再次运行算法，直至负载平衡，增加了负载平衡的时空开销和系统对任务的平均响应时间。针对此问题，论文[26]中将多个轻载节点作为负载迁移目标节点的多目标迁移机制，对DLB的性能做了改善。未来对于DLB研究主要集中在以下几个层面：在系统层次上，通过考虑拓扑结构来优化通讯可提高DLB 策略的性能[27, 28, 29, 30]；在节点组层面上进行通讯开销优化：考虑到节点内的通讯速度远快于节点间通讯的事实[31]，研究如何将更多的节点间通讯密集的任务划分到同一节点内可进一步优化通讯性能；在节点层面上研究细粒度划分与数据依赖性对性能的影响，设计适应于统一多核计算模型和异构体系结构的负载均衡策略来提高策略的计算性能、可扩展性和可移植性，为提高并行性引入的同步开销代价大于收益以及计算具有较大粒度并行性和依赖度的问题时，需要多少处理器节点才是恰当的等问题。

致谢 在此，感谢给予本文支持的所有著作的作者，尤其要感谢南京大学软件学院葛季栋副教授对本论文的指导。

References:

[1] Liu XH. Research on Load Balancing Technology. Science & Technology Information, 2007, No12:173~174(in Chinese with

English abstract).

[2] Sun JC, Zhang LB, Chi XB, eds. Network parallel computing and distributed programming environment. Beijing: Science press,

2003.30~36.

[3] Xue J, Li ZZ, Wang YL. The development of load balancing [J]. Mini micro computer system, 2003, 24(12):2100~2103.

[4] Xiao JB, Wang Y. Application of DNS to achieve load balancing Web cluster service [J]. Computing Systems, 2003(10):59~62.

[5] Hu ZA, Wang L. The relationship between Algorithm, network topology with scheduling frequency and dynamic load balancing

[J].Computer engineering and science,2000,22(1):104~107.

[6] Yin F. Distributed system dynamic load distribution algorithm research [J].Microcomputer information, 2009 (18): 91~93.

[7] Wang S, Xiu BX, Xiao WD. The Web server cluster load balancing algorithms [J]. Computer engineering, 2004, 40(25):78~80.

[8] Dahlin M.Interpreting Stale Load Information[C].In: Proc of the 19th Intl Conf on Distributed Computing Systems, 1999-05.

[9] Mitzenmacher M.How Useful is Old Information[C].In: Proc of the 15th Annual ACM.

[10] Mao M, Pan J. Dynamic Load Balancing Self-adapting Algorithm in Multi-Processor Systems and Its Improvements [J]. Power of

百度搜索“yundocx”或“云文档网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，云文档网，提供经典医药卫生负载均衡技术综述(4)在线全文阅读。