分布式系统中负载平衡算法分析_分布式负载均衡算法
分布式系统中负载平衡算法分析由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“分布式负载均衡算法”。
摘要：该文简单描述了负载平衡算法提出的原因，负载平衡算法的分类以及动态平衡算法的需求。详细分析了动态负载平衡中的接受者驱动、发送者驱动和双向驱动算法以及双向驱动算法的改进算法，并对各算法的优缺点进行了分析。
关键词：分布式系统 动态负载平衡
1．引言
分布式系统是由多台分散的计算机连接而成的系统，其中各个资源单元（物理的或逻辑的）既互相协同又高度自治，能在全系统范围内实现资源管理，动态地进行任务分配或功能分配，并能并行地运行分布式程序。分布式系统具有良好的可用性、可扩展性、可靠性和健壮性，并为用户提供透明方便的用户界面。因此，近年来随着一些高速网络的兴起，分布式计算机系统日益得以广泛的应用并受到人们的重视。经过研究发现，影响处理系统性能的因素包括处理机间的通信开销和分配的负载平衡等，但减少处理机的通信开销和均衡负载是相互冲突的两个因素，它们左右着任务分配策略。如负载均衡可以提高整个系统的吞吐量，因为它试图将模块尽可能均等地分配给处理机，但减少处理机的通信开销又迫使分配策略不得不尽可能地把较多的模块分配给尽可能少的处理机。由于一些并行任务之间的互相依赖关系和通讯量的大小很难在编译时就进行确定，所以人们更多地倾向于动态负载平衡的研究。随着研究的深入进行，人们注意到在一个由网络所连接起来的多个计算机系统环境中，在某一时刻，一些计算机系统的负载很重而另外一些计算机系统的负载却很轻，影响了整个系统资源的利用率。由此，我们应该采用有效的负载平衡策略，即在减少处理机通信开销的基础上，提出行之有效的算法，提高整个系统资源的利用率。
1.1 减少处理机通信开销
系统管理站设计一个信息区，各模块每通信一次，节点累加器自动累加一次，最终将通信的模块信息和累加的次数一起存储到系统管理站的信息区。待系统下次运行时，系统管理站会根据信息区中以前模块信息通信的高低次数排序，按信息区的记录情况将通信频繁的模块安排到同一个节点，从而减少处理机的通信开销。1.2 负载平衡算法 1.2.1概述
负载平衡也称负载共享，是指对系统中的负载情况进行动态调整，以尽量消除或减少系统中各站点负载不均匀的现象。因此，如何准确地评估各节点的工作负载能力并且分配新的请求任务到每个节点，成为分布式系统取得负载平衡的关键。
1.2.2 负载平衡算法的需求
（1）最小化客户请求的派发时间，使客户请求能够迅速地被派发给相应的服务副本，而不会因为低效的副本选择导致延迟。
（2）最小化客户请求响应时间和最大化系统的吞吐量，使系统能够获得最高的性能和最大的资源利用率，最小化资源的空闲时间。
（3）客户请求的响应时间具有可预期性。
（4）保证副本间负载分配的平衡，从而降低发生过载的可能性，确保服务的可用性和系统的可靠性，同时能够在一定程度上抵御负载峰值的冲击。
（5）具有好的可扩展性，不依赖于某种特定的资源或结构，也不对系统中结点或副本的数目做出任何假设。
（6）最小化系统的通信开销。
1.2.3 负载平衡算法的分类
负载平衡算法可分为动态算法和自适应算法两大类。
动态算法是根据系统状态对可以接受任务的站点进行分析，可以将任务迁移到空闲站点，甚至可以将正在执行的任务迁移到其他空闲站点，但要注意的是，信息的收集、分析及作出决定要造成额外开销，不可小视。
自适应算法是通过动态改变参数甚至策略来调整自身的行为，以适应正在改变的系统状态。如，某种负载平衡算法在A情况下的性能优于其他算法，而另一种算法在B情况下更优，自适应算法能够根据系统状态的变化选择合适的算法。在无法通过任务迁移提高系统性能的情况下，自适应算法是很好的选择。对按一次局部负载平衡调度的启动者来说，又可分为接收者主动和发送者主动两种。其中，在发送者主动算法中，当一个站点超载时，它就尝试将任务发送给一个轻载站点，整个算法的思想是负载较重的节点试图甩掉超额的工作。接收者主动算法与发送者主动算法相反，当一个站点的任务队列长度小于阀值时，它就尝试从重载站点接收一个任务。综合以上算法，本文针对考虑节点工作负载能力、请求负载差异的和配置相对简单的因素，在减少处理机的通信开销基础上提出了双向主动均衡算法。
2.动态负载平衡算法
2.1发送者主动算法
发送者主动算法的思想是：当进程被创建时，它就运行在创建它的节点上，除非该节点过载了。过载节点的度量可能涉及太多的进程、过大的工作集或者其他度量。如果过载了，该节点任意选择另一个节点并询问它的负载情况（使用同样的度量）。如果被探查的节点负载低于某些阀值，就将新的进程发送到该节点上。如果不是，则选择另一个机器探查。该策略需要交换处理器的负载信息，一个节点有多种方法 向邻接节点通知它的负载情况，如定期询问、每当任务数发生变化、接收到执行任务请求、响应请求或者当任务数超过一定阈值时。
启动时，所有节点开始执行任务。在一段时间以后，节点开始检查自身是否是重载节点，如果是，它就试图在相关域中均匀的分布任务。具体来说，设该重载节点的负载为lp，相关域中有K个节点，其负载分别为l1，l2，···，lk，则平均负载Lavg为：
Lavg=(1/(K+1))(lp+l1+l2+···+lk)为达到任务的均匀分布，应求得重载节点传递给每个相关域中节点的负载量，因此引入权值hk以避免任务被迁移到负载更重的重载节点。如果Lavg>lk，则hk=Lavg-lk，否则hk=0。因此mk为：mk=(lp-Lavg)hk/(h1+h2+···+hk)然后该节点就可以按照向各个相关节点发送任务。下图为发送者主动算法流程。
图2-1 发送者主动算法（OL为任务队列长度，OLi为站点i的任务队列长度，T为阀值）
2.2接收者主动算法
接收者主动算法与发送者主动算法相反，把所有节点按照阀值M划分为轻载节点和重载节点，所有当前负载t>M的节点称为重载节点，t
启动时，所有节点开始执行任务。在一段时间以后，节点开始检查自身是否是重轻载节点，如果是，它就试图在相关域中找到重载节点，并请求该节点上的任务。具体来说，设该轻载节点的负载为lp，相关域中有K个节点，其负载分别为l1，l2，···，lk，则平均负载Lavg为：Lavg=(1/(K+1))(lp+l1+l2+···+lk)为达到任务的均匀分布，应求得相关域中重载节点应该传递给该节点的负载量mk，因此引入权值hk以避免任务从负载更轻的轻载节点迁移过来。如果Lavg
图2-2 接受者主动算法（OL为任务队列长度，OLi为站点i的任务队列长度，T为阀值）
2.3双向主动算法
在双向主动算法中，发送者和接收者都能转移任务。在系统负载较低时，本算法中的发送者主动容易发现轻载站点，在系统负载较高时，接收者主动容易找到重载站点。所以，在系统中，我们应该合理地设置均值，在系统高负载时采用接收者主动，在系统低负载时采用发送者主动。
在系统中，每个节点根据自身的硬件配置不同而具备不同的负载能力。另外，系统管理站会根据各个节点的负载能力值统计出整个系统的负载总能力值，并设置一个系统负载能力均值。由于系统管理站是在采集时刻进行负载计算的，经过实验证明，以此反映出来各个节点的负载信息会出现剧烈的抖动，从而无法准确地捕捉各节点真实的负载变化趋势。因此解决这些问题，要适当地调整采集负载信息的周期，一般控制在五秒至十秒。还有，每个负载都存在一个负载上限值和负载下限值，如果实时负载值计算结果大于或等于负载上限值（即LOADmax），则说明此节点开始处于负载超载状况；如果实时负载值低于负载下限值（即LOADmin），说明此节点开始处于空闲状态。当然在实际使用中，我们会发现所有节点的实时负载值都大于或等于它们的负载上限值，则说明当前整个系统处于超载状态，这时需要加入新的节点到集群中来处理部分负载；反之，若所有节点的实时负载值低于负载下限值，则说明当前系统的负载都比较轻。
若系统管理站确认系统处于高负载时期则采用接收者主动，即在系统处于高负载时期时，各节点在执行完负载数处理算法之后根据自己的负载上限值和负载下限值判别自己的负载情况，当自己的负载低于下限时，该节点就会按一定方式查询系统的状态，请求某个重载节点迁移一个尚未开始运行的任务给自己。若此时该重载节点尚无这样的任务存在，则轻载节点同它进行一次“预约”，要求一旦有新创建的或到达的任务，就将它迁移给自己。
若系统管理站确认系统处于低负载时期则采用发送者主动，即在系统处于低负载时期时，各节点在执行完负载数处理算法之后根据自己的负载上限值和负载下限值判别自己的负载情况，当自己的负载高于上限时，该节点向系统广播一个“请求迁移出负载”的请求消息。接收到这一请求消息的节点根据自己的状态决定是否参与投标。若参与，则向请求者发送一个标书（含可以接收的负载量），该重载节点对接收到的标书进行筛选，选出其中负载最少的节点并把其希望迁移的负载迁移给它。
综上所述，双向主动算法的步骤分析如下：
第一步骤：查询系统任务接收器，查看是否有新任务，若无新任务，且各节点负载为空，则系统为初始状态，处于等待情况；若有新任务提交，转到第二步骤；
第二步骤：系统管理站分析系统负载状况，此时情况讨论如下：（1）若系统管理站确认系统处于高负载时期则采用接收者主动。（2）若系统管理站确认系统处于低负载时期则采用发送者主动。
所以以下几步骤根据第一步骤的分析分为高负载时期和低负载时期情况进行。当系统处于高负载时期时，转到以下第三步骤；
第三步骤：此时轻载节点按一定方式查询系统的状态，请求某个重载节点迁移一个尚未开始运行的任务给自己。若此时重载节点迁移一个未开始运行的任务给轻载节点，则转入第四步骤；如果该重载节点尚无这样的任务存在，则转入第五步骤；
第四步骤：轻载节点运行迁移的负载，完成重载节点迁移的所有任务转入第五步骤。第五步骤：轻载节点对重载节点进行“预约”，一旦有新创建的或到达的任务，就将它迁移给自己，然后转入第四步骤，否则直到系统节点完成所有任务转入第六步骤；
第六步骤：退出程序。
当系统处于轻负载时期时，转到以下第三步骤；
第三步骤：此时重载节点向系统广播一个“请求迁移出负载”的请求消息，转入第四步骤；
第四步骤：接收到这一请求消息的节点根据自己的状态决定是否参与投标；若参与，则向请求者发送一个标书（含可以接收的负载量），转入第五步骤； 第五步骤：该重载节点对接收到的标书进行筛选，选出其中负载最少的节点并把其希望迁移的负载迁移给它。
第六步骤：轻载节点完成重载节点迁移的负载，若还有重载节点向系统广播一个“请求迁移出负载”的请求消息，转入第四步骤，否则直到系统节点完成所有任务转入第七步骤；
第七步骤：退出程序。
以上各个步骤是在各个节点上并行同步进行的，负载空闲与否的判断，负载数处理算法的执行等都是动态进行的。因为在该平衡算法中，各个节点根据系统的负载状况选择发送者主动还是接收者主动，所以该算法命名为双向主动算法。
3．算法性能分析
3.1 算法特点
发送者主动的主要优点是：没有过重负载的忙节点，不会被空闲邻接节点所打扰。这一点在系统整个负载较低时尤为重要。
发送者主动的主要缺点是：负载过重的忙节点还要额外增加处理负载平衡调度的负担。接受者主动主要优点是：不需要相互交换负载信息；对于大规模并行计算问题，当每个节点均处于忙状态时，几乎不需要额外调度开销；负载平衡的许多工作由空闲节点来完成，没有给忙节点增加许多额外负担。
接受者主动的主要缺点是：在开始和结束阶段时任务数相对较少，许多任务请求会延迟忙节点的执行。
双向主动算法的最大特点是结合了发送者主动和接收者主动两者的优点，经过研究发现，双向主动策略有以下几个优点：（1）当系统处于重载状态时，负载平衡的许多工作有空闲节点来完成，没有给忙节点增加额外的负担。（2）当系统处于轻载状态时，重载节点能容易地发现轻载节点，从而快速地将重载节点的负载迁移到轻载节点，提高负载的迁移效率。
3.2 性能分析
通过参考资料，分析到了各种情况，负载能力高的节点比负载能力低的节点处理点更多的任务，相同负载能力的节点处理相同份额的任务，任务的平衡是按照各节点负载能力占各节点总的负载能力的比例来进行的。4．总结
综合分析，如果系统的算法较简单，则整体性能可能略低，可靠性不高；而如果算法较复杂，则系统资源可能占用较多，开销较大，因此采用何种算法应结合具体应用而定。对于任务间通信量不大或要求不高的系统可采用较简单的自适应动态负载平衡算法，而对于通信量较大且要求高的系统，应采用较复杂的自适应动态负载平衡算法，从而保证整个系统的稳定、可靠运行。
