动态反馈负载均衡算法

　　动态反馈负载均衡算法考虑服务器的实时负载和响应情况，不断调整服务器间处理请求的比例，来避免有些服务器超载时依然收到大量请求，从而提高整个系统的吞吐率。图4.1显示了该算法的工作环境，在负载调度器上运行Monitor Daemon进程，Monitor Daemon来监视和收集各个服务器的负载信息。Monitor Daemon可根据多个负载信息算出一个综合负载值。Monitor Daemon将各个服务器的综合负载值和当前权值算出一组新的权值，若新权值和当前权值的差值大于设定的阀值，Monitor Daemon将该服务器的权值设置到内核中的IPVS调度中，而在内核中连接调度一般采用加权轮叫调度算法或者加权最小连接调度算法。

图4.1：动态反馈负载均衡算法的工作环境

　　连接调度

　　当客户通过TCP连接访问网络访问时，服务所需的时间和所要消耗的计算资源是千差万别的，它依赖于很多因素。例如，它依赖于请求的服务类型、当前网络带宽的情况、以及当前服务器资源利用的情况。一些负载比较重的请求需要进行计算密集的查询、数据库访问、很长响应数据流；而负载比较轻的请求往往只需要读一个HTML页面或者进行很简单的计算。

　　请求处理时间的千差万别可能会导致服务器利用的倾斜（Skew），即服务器间的负载不平衡。例如，有一个WEB页面有A、B、C和D文件，其中D是大图像文件，浏览器需要建立四个连接来取这些文件。当多个用户通过浏览器同时访问该页面时，最极端的情况是所有D文件的请求被发到同一台服务器。所以说，有可能存在这样情况，有些服务器已经超负荷运行，而其他服务器基本是闲置着。同时，有些服务器已经忙不过来，有很长的请求队列，还不断地收到新的请求。反过来说，这会导致客户长时间的等待，觉得系统的服务质量差。

　　简单连接调度

　　简单连接调度可能会使得服务器倾斜的发生。在上面的例子中，若采用轮叫调度算法，且集群中正好有四台服务器，必有一台服务器总是收到D文件的请求。这种调度策略会导致整个系统资源的低利用率，因为有些资源被用尽导致客户的长时间等待，而其他资源空闲着。

　　实际TCP/IP流量的特征

　　文献说明网络流量是呈波浪型发生的，在一段较长时间的小流量后，会有一段大流量的访问，然后是小流量，这样跟波浪一样周期性地发生。文献揭示在WAN和LAN上网络流量存在自相似的特征，在WEB访问流也存在自相似性。这就需要一个动态反馈机制，利用服务器组的状态来应对访问流的自相似性。

　　动态反馈负载均衡机制

　　TCP/IP流量的特征通俗地说是有许多短事务和一些长事务组成，而长事务的工作量在整个工作量占有较高的比例。所以，我们要设计一种负载均衡算法，来避免长事务的请求总被分配到一些机器上，而是尽可能将带有毛刺（Burst）的分布分割成相对较均匀的分布。

　　我们提出基于动态反馈负载均衡机制，来控制新连接的分配，从而控制各个服务器的负载。例如，在IPVS调度器的内核中使用加权轮叫调度（Weighted Round-Robin Scheduling）算法来调度新的请求连接；在负载调度器的用户空间中运行Monitor Daemon。Monitor Daemon定时地监视和收集各个服务器的负载信息，根据多个负载信息算出一个综合负载值。Monitor Daemon将各个服务器的综合负载值和当前权值算出一组新的权值。当综合负载值表示服务器比较忙时，新算出的权值会比其当前权值要小，这样新分配到该服务器的请求数就会少一些。当综合负载值表示服务器处于低利用率时，新算出的权值会比其当前权值要大，来增加新分配到该服务器的请求数。若新权值和当前权值的差值大于设定的阀值，Monitor Daemon将该服务器的权值设置到内核中的IPVS调度中。过了一定的时间间隔（如2秒钟），Monitor Daemon再查询各个服务器的情况，并相应调整服务器的权值；这样周期性地进行。可以说，这是一个负反馈机制，使得服务器保持较好的利用率。

　　在加权轮叫调度算法中，当服务器的权值为零，已建立的连接会继续得到该服务器的服务，而新的连接不会分配到该服务器。系统管理员可以将一台服务器的权值设置为零，使得该服务器安静下来，当已有的连接都结束后，他可以将该服务器切出，对其进行维护。维护工作对系统都是不可少的，比如硬件升级和软件更新等，零权值使得服务器安静的功能很主要。所以，在动态反馈负载均衡机制中我们要保证该功能，当服务器的权值为零时，我们不对服务器的权值进行调整。

　　综合负载

　　在计算综合负载时，我们主要使用两大类负载信息：输入指标和服务器指标。输入指标是在调度器上收集到的，而服务器指标是在服务器上的各种负载信息。我们用综合负载来反映服务器当前的比较确切负载情况，对于不同的应用，会有不同的负载情况，这里我们引入各个负载信息的系数，来表示各个负载信息在综合负载中轻重。系统管理员根据不同应用的需求，调整各个负载信息的系数。另外，系统管理员设置收集负载信息的时间间隔。

　　输入指标主要是在单位时间内服务器收到新连接数与平均连接数的比例，它是在调度器上收集到的，所以这个指标是对服务器负载情况的一个估计值。在调度器上有各个服务器收到连接数的计数器，对于服务器Si，可以得到分别在时间T1和T2时的计数器值Ci1和Ci2，计算出在时间间隔T2-T1内服务器 Si收到新连接数Ni = Ci2 - Ci1。这样，得到一组服务器在时间间隔T2-T1内服务器Si收到新连接数{Ni}，服务器Si的输入指标INPUTi为其新连接数与n台服务器收到平均连接数的比值，其公式为

　　服务器指标主要记录服务器各种负载信息，如服务器当前CPU负载LOADi、服务器当前磁盘使用情况Di、当前内存利用情况Mi和当前进程数目 Pi。有两种方法可以获得这些信息；一是在所有的服务器上运行着SNMP（Simple Network Management Protocol）服务进程，而在调度器上的Monitor Daemon通过SNMP向各个服务器查询获得这些信息；二是在服务器上实现和运行收集信息的Agent，由Agent定时地向Monitor Daemon报告负载信息。若服务器在设定的时间间隔内没有响应，Monitor Daemon认为服务器是不可达的，将服务器在调度器中的权值设置为零，不会有新的连接再被分配到该服务器；若在下一次服务器有响应，再对服务器的权值进行调整。再对这些数据进行处理，使其落在[0, ∞)的区间内，1表示负载正好，大于1表示服务器超载，小于1表示服务器处于低负载状态。获得调整后的数据有DISKi、MEMORYi和 PROCESSi。

　　另一个重要的服务器指标是服务器所提供服务的响应时间，它能比较好地反映服务器上请求等待队列的长度和请求的处理时间。调度器上的Monitor Daemon作为客户访问服务器所提供的服务，测得其响应时间。例如，测试从WEB服务器取一个HTML页面的响应延时，Monitor Daemon只要发送一个“GET /”请求到每个服务器，然后记录响应时间。若服务器在设定的时间间隔内没有响应，Monitor Daemon认为服务器是不可达的，将服务器在调度器中的权值设置为零。同样，我们对响应时间进行如上调整，得到RESPONSEi。

　　这里，我们引入一组可以动态调整的系数Ri来表示各个负载参数的重要程度，其中ΣRi = 1。综合负载可以通过以下公式计算出：

　　例如，在WEB服务器集群中，我们采用以下系数{0.1, 0.3, 0.1, 0.1, 0.1, 0.3}，认为服务器的CPU负载和请求响应时间较其他参数重要一些。若当前的系数Ri不能很好地反映应用的负载，系统管理员可以对系数不断地修正，直到找到贴近当前应用的一组系数。

　　另外，关于查询时间间隔的设置，虽然很短的间隔可以更确切地反映各个服务器的负载，但是很频繁地查询（如1秒钟几次）会给调度器和服务器带来一定的负载，如频繁执行的Monitor Daemon在调度器会有一定的开销，同样频繁地查询服务器指标会服务器带来一定的开销。所以，这里要有个折衷（Tradeoff），我们一般建议将时间间隔设置在5到20秒之间。
权值计算

　　当服务器投入集群系统中使用时，系统管理员对服务器都设定一个初始权值DEFAULT_WEIGHTi，在内核的IPVS调度中也先使用这个权值。然后，随着服务器负载的变化，对权值进行调整。为了避免权值变成一个很大的值，我们对权值的范围作一个限制[DEFAULT_WEIGHTi, SCALE*DEFAULT_WEIGHTi]，SCALE是可以调整的，它的缺省值为10。

　　Monitor Daemon周期性地运行，若DEFAULT_WEIGHTi不为零，则查询该服务器的各负载参数，并计算出综合负载值AGGREGATE_LOADi。我们引入以下权值计算公式，根据服务器的综合负载值调整其权值。

　　在公式中，0.95是我们想要达到的系统利用率，A是一个可调整的系数（缺省值为5）。当综合负载值为0.95时，服务器权值不变；当综合负载值大于0.95时，权值变小；当综合负载值小于0.95时，权值变大。若新权值大于SCALE*DEFAULT_WEIGHTi，我们将新权值设为 SCALE*DEFAULT_WEIGHTi。若新权值与当前权值的差异超过设定的阀值，则将新权值设置到内核中的IPVS调度参数中，否则避免打断 IPVS调度的开销。我们可以看出这是一个负反馈公式，会使得权值调整到一个稳定点，如系统达到理想利用率时，权值是不变的。

　　在实际使用中，若发现所有服务器的权值都小于他们的DEFAULT_WEIGHT，则说明整个服务器集群处于超载状态，这时需要加入新的服务器结点到集群中来处理部分负载；反之，若所有服务器的权值都接近于SCALE*DEFAULT_WEIGHT，则说明当前系统的负载都比较轻。

　　一个实现例子

　　我们在RedHat集群管理工具Piranha中实现了一个简单的动态反馈负载均衡算法。在综合负载上，它只考虑服务器的CPU负载（Load Average），使用以下公式进行权值调整：

　　服务器权值调整区间为[DEFAULT_WEIGHTi, 10*DEFAULT_WEIGHTi]，A为DEFAULT_WEIGHTi /2，而权值调整的阀值为DEFAULT_WEIGHTi /4。1是所想要达到的系统利用率。Piranha每隔20秒查询各台服务器的CPU负载，进行权值计算和调整。

欢迎访问最专业的网吧论坛,无盘论坛,网吧经营,网咖管理,网吧专业论坛https://bbs.txwb.com

关注天下网吧微信,了解网吧网咖经营管理，安装维护: