【负载均衡调度算法的仿真与比较】 nginx负载均衡算法

　　摘要 随着计算机技术和网络的飞速发展，用户对于网络和计算机的服务功能有了更强的依赖性。这也意味着对计算机和网络的整体性能有了更高的要求。然而单台计算机硬件性能的提升存在一些问题，到达了一个瓶颈期，所以利用多台计算机组成一个虚拟的计算机系统来响音用户请求成为了主流解决方案。本文从请求的调度算法进行分析，实现调度算法，并比较其性能的差异。
　　关键词 负载均衡；调度算法；轮转算法；最小连接数算法
　　中图分类号TN915 文献标识码A 文章编号 1674-6708（2010）33-0251-02
　　0 引言
　　用户对于服务性能的要求，使得单台服务器已经无法满足高并发度的用户请求。所以需要组成一个虚拟的计算机系统来响应用户的服务请求，即一个有一定组织结构的服务器群组。既然这个群组内有多个单独的能独立处理服务器请求的计算机，那如何充分利用这个群组内的每个独立的计算机，使之利用率达到最大，就是人们选择提高服务器群组整体性能的首选之路。其中，最关键的当然是请求的分配均衡问题。我们的目标是所有的请求能较为均衡的分配到各个服务器单体上进行处理。
　　针对这个目标，人们设计了一系列请求调度算法来使得用户请求均衡化，即决定集群如何选择下一个集群节点，将新的服务请求转发给它。
　　本文在研究了这些算法的基础上，通过编写算法模拟程序，比较各个调度算法的响应率。
　　1 负载均衡算法描述
　　1.1轮转（Round Robin）算法[1]
　　轮转算法是一个简单经典的算法，对每一个集群中的节点都一致对待，即假定所有服务器的处理能力都是相同的，对新发起的请求，按照i=（i+1）mod n调度第i台服务器。其中i为上一次被调度的服务器，n为服务器的数量。此算法不适合服务器性能不一致的集群，其最小调度粒度是请求，所以当请求持续的时间变化较大的时候，会出现负载不均衡的情况。
　　1.2加权轮转（Weighted Round Robin）算法[2]
　　加权轮转算法是在轮转算法上演变而来，不过对每一台服务器节点都有新增了权值，来代表每一台服务器的处理能力，也可以说是优先级。权值越大的服务器将会更多的被调度到。先找出权值最高的那几台服务器进行轮转调度，然后减去所有权值的最小公倍数，找出所有大于等于这个权值所对应的服务器，以此循环，直到没有更低权值的服务器存在。例如，有服务器A、B、C，权值分别为3、2、1，则在一次调度中，调度的顺序为AABABC，然后重复这个顺序。加权轮转算法解决了传统轮转算法中性能不一致的时候的负载不均衡，但是没有解决当请求持续时间方差较大的时候，负载不均衡的情况。
　　1.3最小连接数（Least Connetions）算法[3]
　　假设所有服务器的处理能力是相同的。通过服务器所处理的连接的多少，来估计服务器负载。调度控制器需要记录所有服务器节点正在响应的连接数。当有新的请求到达的时候，总是调度处理连接最少的那个服务器来进行响应。这样就能最大化的把负载平滑到所有服务器上。每当一个TCP连接断开或者超时的时候，调度控制器中相应的连接数也会减一。但是问题也同样存在，在服务器性能不同时，其调度的效果就不理想，会把更多的连接调度给处理能力差的服务器。
　　1.4加权最小连接数（Weighted Least Connections）算法[4]
　　在最小连接数算法上发展而来，如果加权轮转算法一样，是在给每一个服务器加一个权值，表示此台服务器处理数据的能力。加权最小连接调度在调度新连接时，尽可能使服务器已建立的连接个数和其权值成比例。当前的新连接请求会被发送服务器i，当且仅当服务器i满足以下条件
　　1.5基于局部性的最少连接调度（LBLC）[5]
　　此算法是针对Cache系统而设计的。负责均衡器负责调度目的IP相同的请求到同一台服务器上，这样就可以让Cache的命中率更高。使得Cache的使用更多，从而加强性能。
　　基于局部性的最少连接调度算法先根据请求的目标IP地址找出该目标IP地址最近使用的服务器，若该服务器是可用的且没有超载，将请求发送到该服务器；若服务器不存在，或者该服务器超载且有服务器处于其一半的工作负载，则用“最少连接”的原则选出一个可用的服务器，将请求发送到该服务器。
　　2 算法仿真
　　2.1 流程设计
　　在页面中开辟内存，新建选定算法的对象，然后再读入Xml中的参数，用这些参数初始化对象，不断执行选定的算法，当处理完所有请求以后，显示结果，显示被处理的请求数，和进入服务器队列的请求数。一旦进入服务器队列，则认为，此请求遭遇网络堵塞，将产生延迟，假设一旦产生延迟，此请求将被认为未被相应。最后计算每一次进入队列的请求数量，取其平均值，在页面显示。
　　BaseInfo为所有算法类中公用的属性所组成的基类，所有算法类都继承与这个类。其InitBaseInfo方法，可以对BaseInfo中的属性进行初始化。
　　每一个算法类中都有ClintRequestCount属性，此属性表示初始化请求的数量。没当算法成功被执行一次后，ManagedRequest会加一，ResaultList中被分配到的服务器处理请求的数量也会加一，ConnCount中相对应的服务器连接数也会增加一。
　　在每一个算法类中都设计有ListResaultList，其中保存所有服务器节点已经处理过的请求数。
　　AlgorithmType是一个枚举类，枚举的是算法的名称。
　　ClassHelper是一个静态类。类中的方法都是各种被页面或者类重复调用的函数。比如Gcd方法返回的就是输入数组的最大公约数；ReadXmlFile方法，返回的XmlNode，用于读取Xml文件中的内容。如果类型不匹配，则会提示Xml不合法。
　　每一个算法类都有一个Execute()方法，调用此方法，就相当于使用此算法分配了一个请求。
　　加权算法会调用ClassHelper中的ReleseConnections()方法，是随机释放连接的方法，产生随机数，根据随机数来随机释放某几个服务器上某几个连接。
　　2.3 测试结果
　　2.4 结果分析
　　轮转算法性能没有最小连接数算法性能高，进入队列的请求更多。
　　加权比不加权的算法性高，在权值不相同的时候，比权值相同加权算法更能体现其优点，更好的分配请求，平滑连接到各个服务器上，减少服务器响应队列长度。在权值相同的时候，不加权算法和加权算法性能差异不明显。
　　相同的算法，在服务器权值相同的时候有更好的分配结果，队列长度相对较少。
　　局部最小连接数算法拥有最好的性能，有最小的队列长度。
　　综上所述，流媒体服务器组所适合的负载均衡技术是，基于直接路由技术的负载均衡，因为下行流量为流媒体，长时间持续的连接，不通过调度器可以提高性能。因此，适合流媒体服务器是基于局部性的最小连接，因为他支持Cache，可以有效提高缓存的使用效率，并且可以有效把连接分配到集群中的服务器上。
　　3 结论
　　通过对以上5种调度算法的分析仿真比较，我们得到，在流媒体服务器组中相对比较适用的是基于局部性的最小连接算法。他能有效的平衡用户的请求，同时它支持cache，可以有效提高缓存的利用率。
　　
　　参考文献
　　[1]向建军，白欣，左继章.一种用于实时集群的多任务负载均衡算法[J].计算机工程，2003(12).
　　[2]余科军，郑芸芸.分布式实时任务分配算法的设计与实现[J].福建电脑，2007(9).
　　[3]王力共，杨志新.电子政务平台服务器集群负载调度算法分析[J].湘南学院学报，2006(5).
　　[4]马超.网络负载平衡系统的设计与实现[D].大连理工大学软件工程学位论文，2005.
　　[5]吕丽平，臧国轻.基于LVS服务器集群的研究[J].电脑知识与技术，2010(21).
　　
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文