基于预测阈值的动态权值负载均衡算法

李慧斌 何利力

摘要：为优化整个服务器集群负载，提出一种基于预测阈值的动态权值负载均衡算法。动态评估服务器性能，根据评估结果计算服务器权值，并引入反映集群负载平衡程度和状态的阈值，以避免因频繁修改权值造成服务器抖动;使用Holt-Winters对访问量进行预测，并通过结果预测阈值，实现复杂负载环境下的负载均衡，达到最优负载均衡。实验结果表明，预测阈值的动态权值负载均衡算法在低并发以及高并发时都有很好的性能表现，能够提升系统的最大吞吐量，减少响应时间，提高整个集群利用率。

关键词：Holt-Winters预测;负载均衡;服务器集群;动态负载算法

DOI：10.11907/rjdk.192093 开放科学（资源服务）标识码（OSID）：

中图分类号：TP312文献标识码：A 文章编号：1672-7800（2020）006-0085-05

0 引言

互联网用户和Web应用的爆发式增长，对服务端提出了更高要求，这需要服务器保持可靠运行且能迅速响应，可同时为大量并发客户端提供优质服务。这种高可用性和高可扩展性，对集群网络和处理能力都提出了挑战。于是，高效而廉价的服务器集群成为首选方案，在现有设备下提高整个集群性能变得更加迫切。负载调度算法决定着整个集群性能是否可以完全释放，作用重大。

现有负载均衡算法主要分成动态负载均衡技术和静态负载均衡技术两大类。静态负载均衡技术指在负载过程中根据预先设置好的策略进行任务分配，不会根据服务器实时情况进行调整，运用起来常常不如动态负载均衡效果好，但静态负载均衡算法比动态负载均衡算法更加节约服务器资源。

由于效果较好，因此动态负载均衡算法也较多。原地址哈希算法是一种很好的负载均衡算法，只要请求源地址不变，提供服务的总是同一台服务器。但由于用户活跃程度不同，可能会出现某服务器处理大量请求，而其它服务器空闲的情况，造成服务器集群负载不平衡。针对这种情况，文献提出了一种基于预测模型和独立训练节点的负载均衡算法。该算法虽然解决了上述问题，但每次都要预测响应时间，根据预测响应时间进行分配，当并发量小时，预测算法反而增加了响应时间，不利于短而快的请求。针对以上问题，文献提出了一种自适应负载指标权值的负载均衡算法。该算法很好地解决了快速转发问题，但是只根据评估集群中服务器节点状态及负载情况修改权值，容易因频繁的权值修改引起集群抖动。针对频繁修改权值的问题，文献提出了动态调节权重的负载均衡策略。在负载算法调节权值前计算一次阈值，根据阈值情况进行权值调节。但其信息都由Nginx负载节点采集，增加了负载节点压力，影响负载性能。同时，只对服务器节点进行信息收集与预测，且在集群负载出现倾斜时才作出调整。

鉴于此，本文提出基于预测阈值的负载均衡算法。算法具有以下特点：对服务器集群评估不仅仅是根据服务器的CPU、内存、磁盘I/0等参数进行服务器节点权值计算，而是将服务器集群中的每一个节点当前运行的Web项目加入评估中，通过计算每次请求对服务器节点资源的消耗情况实现综合评估。为了防止权值频繁更新造成服务器集群抖动，设定反映集群负载平衡程度和状态阈值，阈值设定保证了权值更新频率和集群稳定性。同时，增加阈值预测，在集群负载倾斜前调整集群中服务器节点权值，进一步保证服务器集群稳定。预测算法部署方式灵活，可以与负载服务器同时运行，也可以独立运行，避免了预测算法对负载服务器性能的影响。

1 集群状态动态评估

采用动态评估方法，对整个集群状态和集群中的服务器进行评估，主要分为3个部分：节点性能动态评估、节点权值计算、集群负载状态评估。①节点性能动态评估指从服务器运行项目的角度，评估集群中单服务器节点性能;②权值计算指结合节点性能评估结果，计算此节点权值;③集群负载状态指评估整个集群当前负载情况，并结合预测阈值及当前阈值对集群负载进行调整，实现动态负载。

1.1 节点性能动态评估

处理整个集群负载问题，首先要量化集群中的每一台服务器，这是Web集群负载的首要问题。使用不同的性能评估标准，对整个集群的负载能力影响很大。对此，结合服务器运行项目对资源占用情况，从CPU（Central Processing Unit）、內存（RAM）、磁盘I/0，服务器带宽（Bandwidth）这4个维度评估节点服务器性能。

设集群中有n台服务器Cluster=（serverl，Server2，……，Server_n），对其中一台服务器的性能定义为P（serverl），其衡量该服务器的服务能力。

1.2 节点权值计算

权值决定负载服务器将任务分配给哪一个节点，负载服务器也是整个集群的人口。要实现集群最优负载均衡，调整权值非常必要。在实际生产环境中，服务器整体性能及服务器运行项目不会经常变动，只要预测的阈值入在正常范围内，就不调整权值。因此，权值不会频繁调整，保证了整个集群的稳定。

集群中节点权值根据集群中节点S_i的负载情况3l（S_i）及节点S_i的性能评估值计算得出，如式（4）所示。

权值评估针对每一个服务器节点，增加了项目对当前节点的资源消耗参数，这样评估出的权值更加准确。准确的权值会使集群负载更加均衡，减少权值调整次数，进一步降低抖动发生概率，增强集群稳定性。

1.3 集群整体负载状态计算

均衡的负载能够使集群释放出更好的性能，对提高集群并发量及业务处理能力有重要影响。节点服务器资源利用状态是影响整个集群的基础，其定义如下：

其中，U_i是服务器节点S_i=（i=1，2，……，n）的资源使用情况，SL（S_i）是当前节点服务器的负载情况，P（S_i）是当前节点服务器的综合性能评估。

服务器资源使用情况标准差（Standard Deviation）用σ表示，可以很好地反映出当前集群负载的离散程度。σ值越小，整个集群负载平衡程度越好;反之，σ值越大，整个集群负载越不平衡，需重新计算负载权值。

2 预测阈值的动态权值负载均衡算法设计

算法主要部分是阈值预测，通过预测阈值可以在集群负载倾斜和负载超载之前对集群进行相应调整，同时阈值可以避免权值频繁调整造成的服务器集群抖动。预测阈值通过预测CN并进一步计算得出。

2.1 预测CN（链接数）

用户请求服务会产生一个或多个链接，在链接产生前预测链接信息，对掌握服务器性能及集群性能变化具有重要意义。通过预测值（preCN）可以计算出预测阈值入，并根据预测阈值让集群提前作出相应调整。同时，也可将预测值（preCN）代人负载算法进行运算，通过负载算法输出值对当前权值进行修正，使集群性能发挥到最大。

Web服务的服务器集群中，连接数变化呈周期性规律。为使预测算法对服务器资源的消耗尽可能小、通过预测模型对结果进行预测时尽可能迅速，选择时间序列预测模型。

在Holt方法基础上增加带周期因子Holt-Winters方法。将链接到达的时间序列进行分割，整个序列有N个周期，每周期S个时隙，设其中某时隙为最小粒度。原始转移方程如下：

其中，ψ_i（i=1，2，…，T）是第i时间间隙时连接数的统计值;A_i、B_i、C_i表示Holt-Winters中基线、线性趋势和季节趋势的因子;a、b、c是平滑因子，范围是[0，1]。

2.2 阈值入计算

由于负载调度、节点信息收集等会消耗一定资源，这类资源的消耗在大量并发时微不足道，但在并发量很小时会增加负载。此时，引入一个阈值入用来反映集群负载状态和集群当前负载的平衡程度，能够使负载服务器在更加合适的时机调整集群中每个节点的负载。入定义如下：

其中，SL（S_i）是节点S_i的综合负载情况，P（Server_i）表示节点S_i的整体性能评估，相关系数k₁+k₂=1，C_d是集群负载离散程度。阈值入范围是（0，1]，该值能够反映出当前服务器集群状态。入越接近1，证明服务器集群当前负载越大;反之，则证明服务器集群当前负载较轻，如表l所示。

2.3 算法设计

集群由负载均衡服务器（LBS，Load Balance Server）负责调度。根据负载均衡服务器性能情况，具体可以分成两种形式：一种是整套算法由负载均衡服务器负责，同时整个集群中的服务器向负载均衡服务器汇报;另一种是额外增加一台负载控制服务器（Load Balance Control Server）负责负载算法，而负载均衡服务器只需负责任务分配即可。两种方式根据实际情况设置，第一种方法实现简单，同时节约成本，但是负载均衡服务器会承受更大压力，比较适合LBS性能较好的情况;第二种方法可能会增加成本，但会减轻负载均衡服务器压力，释放LBS性能，比较适合LBS性能一般的情况。

负载算法实现如下：负载控制服务器向所有节点发送查询请求，查询各服务器的CPU、内存、磁盘I/0、带宽等相关指标;同时，各节点也会向负载控制器汇报自身资源使用情况。这两项工作并不是同时进行，具体由阈值以及服务器节点的负载情况SL联合控制。当阈值较低时，说明整个集群负载较低，同时LBS负载较轻，或是有独立节点（增加单独负载控制服务器）时，由负载控制服务器向集群中的服务器节点收集信息。当集群闽值较高，且LBS负载较高时，集群中服务器定时向LBS服务器汇报，同时LBS计算阈值、负载平衡度、预测CN等，并根据结果选择是否重新计算和更新权值。

当请求抵达时，负载节点依据权值进行调度。同时，负载控制器记录该请求相关信息，如：处理时间、处理请求的服务器节点、服务器节点当前请求数CN_i等。如果某節点长时间不响应，控制服务器则将其设置为请求不可达。如果某节点已经过载，控制服务器则将其设置成过载态，负载调度时会越过此服务器，直到所有服务器都到达过载态。如果长时间处于这种状态，则说明整个集群的服务器节点性能需要提高。

负载算法步骤如下：

（1）整个集群节点初始化，评估集群中的服务器，计算出初始P（Server_i），并初始化权值。

（2）控制服务器计算权值，并修改负载服务器的权值列表。

（3）收集服务器信息，统计CN_i并上报给控制服务器，每收集一定数量的数据控制服务器便更新R系数，重载P（serverl）。

（4）控制服务器每隔一段时间进行CN预测，得出preCN，进行模拟负载，得出预测集群离散度，并预测阈值入。如果入值在合理范围内转步骤（5），入值异常则转步骤（2）。

（5）有新的请求到达时，负载服务器根据权值分配任务，任务下发前判断当前节点负载状态，如果超载，则跳过当前节点。下发成功后将结果上报给控制服务器。

（6）控制服务器接收或查询整个集群中节点负载状态，计算SL（serverl）并将结果传给负载服务器。同时，计算集群当前离散度及阈值入，如果需要更新权值，则转步骤（2），否则转步骤（3）。当整个集群一直处于中低负载运行时，控制服务器将着重判断集群离散度C_d。如果所有集群都处于超载状态，控制服务器将通知负载服务器请求等待，直到有服务器退出超载状态。

3 实验验证

3.1 仿真实验平台搭建

为了验证算法，用8台云主机搭建仿真实验环境，分别是5台业务逻辑节点，2台数据库节点，1台负载服务器节点，并在该环境中对预测阈值的动态权值负载算法进行验证分析。本文采用PTS（Performance Testing Service）性能壓测工具，它面向云化和分布式设计，更加适合现行主流技术架构。PTS可以模拟出大量用户访问业务的真实情景。

为了有效测出算法性能，采取并发模式进行施压，同时使用设置上限每次增加10%的自动递增模式，所有压力采用国内公网IP进行压测，最大程度地模拟真实环境。

由于控制服务器和负载服务器在同一台机器上，因此采用由服务器节点向上汇报的方式，服务器节点根据当前节点负载变化频率分为3个等级，最短5。汇报一次，最长15s向上汇报，如一个服务器超过20s没有汇报，控制服务器将其设置成不可达。服务器集群中各节点配置如表2所示。

3.2 实验结果分析

基于预测模型和独立训练节点的负载均衡算法（实验组1）在处理负载均衡问题上具有较好效果，因此将本文算法（实验组2）与其作对照实验。同时，为了更加清晰地显示实验结果，还增加了普通的加权轮询算法作为对照组

实验过程中，在搭建好的仿真实验平台上分别运行本文预测阈值动态权值负载均衡算法与两种对照算法。通过PTS压测工具以每秒增加50的并发量进行压测，每一次压测5分钟，每隔4s统计一次平均响应时间和当前集群状态。结果如图1所示。

从图1可以看出，并发量提高，平均响应时间随之上升。当并发量不是很高时，普通加权轮询算法（对照组）与本文算法相差无几，但是本文算法稍低于对照组，原因在于普通加权算法是凭借经验设置权值，而本文是根据服务器状态计算R值，并通过R值评估服务节点性能后计算权值。但是基于预测模型和独立训练节点的负载均衡算法（实验组1）平均响应时间略高于本文算法和对照组，这是由于实验组1的算法全程都有负载调度器参与，在低并发时，复杂算法增加了额外开销。而本文算法由于增加了预测阈值入，在低并发时控制服务器并不参与，避免了额外的系统开销，提升了响应速度。

在高并发时，对照组权值固定，每种请求对资源的需求不同，造成负载不均，使得响应时间增大。而实验组1由于负载调度器的参与让整个集群负载更加均衡从而使响应时间低于对照组。而本文算法由于权值是请求到达之前就已经确定好，因此在请求到来时避免了控制服务器运算，提升了平均响应时间。

4 结语

本文对复杂环境下的负载问题进行了深人研究，考虑到不同项目对资源占用情况不同和集群节点性能差异，提出了一种基于预测阈值的动态权值负载均衡算法。算法中的权值结合了项目对节点资源的消耗情况，通过负载离散度控制，保证了整个集群负载最优，又通过阈值对算法进行调节，综合考虑了高并发和低并发两种不同情况。最后的模拟实验显示，本文算法能减少响应时间，使整个集群负载更加平衡，负载效果较好。后续可分析不同任务对资源的消耗程度，将其进行量化，并结合任务访问频率作进一步研究。