集群服务器在混合请求下的负载均衡优化算法

申泽星，彭云建，岳喜顺

华南理工大学 自动化科学与工程学院，广州 510640

1 引言

随着互联网的高速发展，各类网络化信息系统规模越来越大，访问流量呈几何级数增长，为了满足新一代网络要求，实现B/S网页信息集成发布与交互处理，即提供更丰富的内容、更好的交互性和更高的安全性[1-3]，Web服务器采用大量的CGI、java/php/asp动态生成页面等信息密集型应用，这对服务器的工作性能提出更高要求。单个Web服务器在处理大量服务请求时会存在工作负载过大，服务请求响应时间长，反馈延迟大的问题，严重时会出现单点故障，用户体验表现较差。解决这类问题有两种基本方法：一是硬件扩展，为服务器配置计算处理能力更强大的硬件，其优点是便于服务器系统的部署、备份和恢复，维护操作也相对简单；但是计算机硬件的数据处理能力始终存在瓶颈，且高性能的配置价格昂贵，这种方法仍难以满足Web应用的需求；二是多服务器并行处理方式[4]，多台服务器通过高速局域网的连接，域名服务器和接入服务器的管理，构成单一站点（访问的域名或公网IP地址相同）的服务器集群，将用户的访问请求通过负载管理服务器分配到集群中各个服务器上[5-6]，从而增加整个站点系统的扩展能力与容错能力，提高系统响应效率与可靠性，为用户提供并发服务[7-8]，该方法成为目前部署大型信息服务系统的主要方案，为构建开放式的“云”服务系统提供完备的技术基础。Web集群的组网拓扑结构如图1所示。

图1 Web集群服务器组网的拓扑结构示意图

服务器集群中单个服务器的结构和性能存在差异，客户端访问具有随机性和突发性，访问来源与内容多样化、碎片化，造成某些服务器承受过少或过多的负载，此类非均衡的负载分配会严重降低服务器集群系统的整体性能。因此现有系统一般会配置负载均衡器[9]。负载均衡器根据单个服务器的最大处理能力和当前的负载状况，依据负载调度策略分配负载任务，合理利用每台服务器的资源而避免出现过载情况，提高了服务器集群的稳定性和响应速度。

对于Web服务器集群的负载均衡研究，从模型、算法与应用实现几个方面已有较多成果。文献[10-12]将负载均衡算法分为静态和动态两大类。静态负载均衡算法包括Random随机（RAN）算法、Round-Robin轮询（RR）算法以及静态权重轮询（SWRR）算法。该类算法将各服务器的任务分配比例作为系统参数保存在负载均衡器中，不考虑服务器负载的实时变化情况[13-14]。静态负载均衡算法属于开环负载调节方式，难以满足新一代服务器集群的性能要求。动态负载均衡算法包括最少连接（LC）算法、加权最少连接（WLC）[15]算法和动态权重轮询（DWRR）算法[16]。负载均衡器周期性收集每台服务器的负载信息，根据服务器的实时负载水平计算任务分配权重分配任务，在请求任务类型不同和工作负载差异较大的情况下，动态负载均衡算性能优于静态负载均衡算法，但动态负载均衡算法需要额外的数据处理与传输。传统的动态负载均衡算法存在着局限性，譬如，最少连接算法以连接数量衡量服务器当前的负载情况，因为服务器性能不同、动态页面访问任务消耗的服务器资源不同，连接数相同不等同于服务器承受的负载量相同[17]。服务器集群长时间运行，会出现负载误差累积情况，将导致各个服务器所承受的负载量不均衡。针对最小连接算法的问题，文献[17]提出了根据服务器的CPU、磁盘I/O、内存、网络带宽等占用率和最大处理能力以及进程数量等指标来评估服务器的负载水平，由此确定服务器的任务分配权重。但受到服务器负载参数采样周期的影响，负载量的计算和采集存在较大误差，并在一定时间内具有累积性。

针对传统负载均衡算法和文献[17]中算法的局限性，本文提出了在混合请求服务中的负载均衡优化算法，根据请求服务的数据存取与处理特点，优化处理静态和动态页面的负载量估计模型以衡量服务器实时负载率，基于动态预测方法并采用不同的方式分配服务请求任务达到负载均衡的目的。

2 混合服务请求的负载均衡模型

负载均衡器在接收的服务请求中包含静态页面请求和动态页面请求，静态页面和动态页面在数据存储和页面内容产生上有很大的差异性，服务器的处理方式也不相同。处理静态页面的访问，服务器先查看缓存中是否缓存此静态页面，如果有，直接从缓存中读取页面数据并返回页面；否则，从磁盘中读取页面文件，并按照调度算法（如LRU算法）缓存静态页面。动态页面则是根据用户不同的请求参数，从数据库或数据文件等读取页面内容数据，基于数据处理逻辑生成信息块并组合成响应页面发送给用户。因此，动态页面一般难以完整缓存[18]。

静态页面访问产生的负载量与静态页面文件大小、读取页面的方式有关，用ρS表示：

其中，S是静态页面文件大小，λ是读取静态页面文件及处理发送的资源（包括CPU、内存、磁盘读取和网络）使用率系数，从磁盘中读取页面文件并处理时取λ=λ1，从缓存中读取静态页面文件及处理时取λ=λ2，一般的，λ1＞λ2。设服务器在时间TS内累计接收了cS个静态页面的访问，则服务器单位时间内需处理计算的静态页面负载量记为LS，计算式为：

服务器处理动态页面访问的负载量主要由两部分组成：一是服务器根据页面访问参数，查询数据和调用业务逻辑处理程序，生成视图页面，该部分是与计算性能有关的常量，用G表示；其次是缓存和发送视图页面产生的负载量。同理，单位时间内要处理动态页面的负载量记为LD，计算式：

其中cd是TD时间内需缓存与转发的动态页面访问数量，ρD是动态页面访问产生的负载量。

在混合类型服务请求中，服务器在单位时间内承受的总负载量是静态页面访问和动态页面访问产生的负载量之和，记为L：

设服务器在t时刻正在处理ns(t)个静态页面访问和nd(t)个动态页面访问，在t+Δt时刻接收新的静态与动态页面访问请求数分别为Δns(t)和Δnd(t)个，则处理过程的时序如图2所示。图中实横线表示一个动态页面访问，虚横线表示一个静态页面访问，横线的长度表示服务器完成处理页面访问的时间长短，服务器在任何时刻的负载水平由新接收的访问处理任务和之前未处理完任务的负载量累积而成，由于页面访问具有随机性，且页面文件大小与处理逻辑的计算量不同导致服务器完成负载量处理的时间不同，因此，服务器处理混合页面访问的负载率是一类典型的随机过程。如果仅考虑静态页面访问或动态页面访问的负载均衡，都会导致服务器集群负载不均衡。如图3所示，单一负载均衡会导致局部服务器承受过多或过少负载。

图2 单台服务器处理混合页面访问时序图

图3 Web集群服务器处理混合页面访问的时序图

针对处理混合服务请求中的负载均衡问题，设负载均衡器周期性采集每台服务器的负载参数为X(k T),k=1,2,…,T为采样周期，根据服务器的历史采样周期的负载量和当前负载量预测下一周期的负载率（即，服务器单位时间内承受的负载量与最大处理能力的比例），根据服务器之间的负载水平差异分配当前的页面访问任务，从而形成一类动态反馈的任务分配策略，基本方案如图4所示。

图4 动态反馈示意图

对于图4表示的反馈型混合服务请求的负载均衡算法，需要解决以下问题：

（1）对静态页面文件进行分类提高服务器缓存命中率。

（2）每台服务器需采集负载参数并计算本地机需处理的静态、动态页面负载量，并周期性地将此信息反馈给负载均衡器。

（3）负载均衡器根据每台服务器承受的历史负载和当前负载，准确预估下一周期每台服务器的负载率。

（4）负载均衡器根据预测负载率和优化模型求得合理的动态页面访问分配权重，达到负载均衡的效果。

3 混合服务请求负载均衡算法

3.1 负载均衡算法的基本流程

本文算法流程如图5所示，系统初始化阶段计算服务器的最大处理能力，确定访问页面的类型参数。其次，根据负载均衡器哈希表分配静态页面访问，计算处理静态和动态页面的负载量。最后，通过计算平均预测负载率与各台服务器负载率的最小偏差和求出最优分配权重动态分配处理页面访问的任务。

图5 服务器集群负载分配流程图

3.2 负载均衡优化模型

根据文献[6，19]，单台服务器最大处理能力主要用5个指标表示：CPU数量μ，CPU频率 f(GHz)，内存容量 M(GB)，磁盘I/O速率 D(MB⋅s-1)，网络吞吐量N(MB⋅s-1)。设各指标对服务器最大处理能力的影响系数为k1～k4，服务器的最大处理能力C由下式计算：

不同类型的服务器ki不同，比如FTP服务器侧重网络吞吐量和磁盘I/O速率，而HTTP服务器侧重CPU数量和频率[19]。一般情况下，各指标的影响系数可取k={0.2,0.3,0,0.5}[19-21]。对于有n台服务器组成的集群，各台服务器最大处理能力计算矩阵公式：

其中，Ci是第i台服务器的最大处理能力。

在处理静态页面访问时，为了提高缓存命中率，将静态页面文件按照大小分类。在t时刻服务器需处理的静态页面负载LSi()t由下式可得：

其中，Sj是第 j类静态页面的大小，ρSj是访问第 j类静态页面产生的负载，cj()t为t时刻服务器处理的第 j类静态页面数量。

设t时刻第i台服务器第 j类静态文件访问数量为ci,j(t)，第i台服务器在t时刻需处理的静态页面负载记为LSi(t)：

为了加速负载均衡器查找静态页面访问分配的服务器记录，构建一张哈希表，键为静态页面文件大小范围类型，值为该类型静态页面访问被分配到服务器的最新历史记录。静态页面类型数少，哈希表所占用的内存容量有限，不会影响负载均衡器接收和分配访问请求的性能，其结构见表1。

表1 负载均衡器哈希表

当负载均衡器收到第 j类静态页面访问时，查找该类页面已被分配的服务器记录ij(1 ≤i≤n )。若服务器ij还可以对页面访问提供服务，则将此类静态页面访问分配给该服务器；若服务器ij承受的负载接近其最大处理能力，则将页面访问分配给负载率最小的服务器，并更新第j类静态页面访问分配的服务器记录。

在处理动态页面访问时，服务器不会缓存动态页面，故将此时刻负载均衡器接收到的动态页面访问作为一个待分配的负载整体，为达到负载均衡，负载均衡器需在本周期内为每台服务器分配动态页面访问的权重。设t时刻第i台服务器要处理的动态页面负载记为LDi(t)，由t时刻前未完成动态页面负载量和t时刻接收到的动态页面访问产生的负载组成：

其中，cD(t)是t时刻负载均衡器持有的动态页面访问数量，Gi是第i台服务器生成动态页面的性能常数，wi(k T )是在第k个周期内负载均衡器分配给第i台服务器动态页面访问的权重，因为负载均衡器接收数据的周期性，wi(k T )与k相关，一个周期内服务器拥有的分配权重不会改变。

为了计算动态页面访问分配权重wi(k T )，用负载率η(t)表示t时刻服务器消耗本机资源的程度，根据每台服务器最大处理能力C、t时刻服务器承受的总负载量L可得：

在t时刻第i台服务器负载率ηi()t如下：

为了均衡各服务器的负载量，需使每台服务器的负载率相近。各类静态页面类型访问数量和存储方式已知，可估计每台服务器单位时间内要处理的静态页面负载量；对动态页面访问任务的分配，需要估计动态负载量并确定分配权重w。页面访问存在局部性[22]和随机性，ηi(t)是一个随机处理过程，选择时间序列预测算法—指数平滑法[23]预测集群服务器的负载率分布，求出合理的分配权重w，确定处理页面访问的任务。设一次指数平滑预测法预测第i台服务器第k个周期的负载率为与k相关：

可见，ηi(k T )与的差值越小，负载均衡效果越好。因此，确定各台服务器在第k个周期时刻的权重使得总负载率偏差最小，且满足如下约束条件：

其中

单台服务器负载率 ηi(t) 应低于0.9[17]，若 ηi(t)大于0.9，说明服务器承受的负载量接近饱和，不应该对该服务器再分配请求任务。根据柯西不等式：

对式（13）得：

当且仅当

即在第k个周期时刻各台服务器负载率相等时，等号成立，此时取得最小值，可得方程组：

由此可解第k个周期内第i台服务器权重wi(k T)。如果不存在符合条件的解，需通过实验找到合适的wi(k T )使得目标函数值尽可能小。

确定服务器第k个周期的任务分配权重wi(k T)后，根据公式（9）可知t时刻负载均衡器对第i台服务器分配的动态页面访问数量为并根据公式（10）求出第k个周期第i台服务器实际负载率 ηi(k T )，为预测第(k +1) 个周期的提供数据。在第(k +1)个周期分配新的页面访问请求时，根据计算分配权重wi(( k+1) T)。

4 服务器集群的负载均衡仿真与结果分析

选择15台性能不同的服务器组成一个Web服务器集群，模拟采用不同的负载均衡算法处理混合页面访问的过程，计算各个服务器在不同时刻的负载率，从而评估负载均衡的效果。每台服务器的计算性能参数见表2，按照Web访问的静态页面按文件大小分为4类，见表3，动态页面大小在50～100 KB。

负载模拟仿真分两种情况进行：（1）采用文献[17]中负载均衡算法，各服务器的实时负载率分布如图6所示。（2）采用本文提出的基于预测负载率的负载均衡优化算法，各服务器的实时负载率分布如图7所示。图6和图7中x轴为服务器编号（15台），y轴为仿真时间（取20个时间周期），z轴为各服务器的负载率。图6中各个服务器的初始负载率基本一致，在若干个任务分配周期后服务器之间的负载率差距变大。图7中，负载率曲面表明本文的负载均衡优化算法使得各台服务器处理页面访问的负载率均衡增加，没有出现图6中的曲面大波动，服务器之间在同一时间的负载率相差不超过0.1。图6和图7的负载率曲面对比直观地反映了本文算法在混合请求类型下能够有效调节服务器的负载分配，使集群中每台服务器均衡地增加负载量，负载率不会出现大抖动，相比文献[17]的算法，本算法具更理想的负载均衡效果并且稳定地保持这种状态。

表2 群组服务器的性能参数表

表3 静态页面大小分类表

图6 文献[17]中算法的集群服务器负载率周期分布曲面

图7 基于预测负载率的集群服务器负载率周期分布曲面

其次，将仿真（2）中集群服务器处理页面访问的负载率偏差和的最小值、预期平均负载率和实际平均负载率的变化曲线绘制在图8中。可以看出，实际负载率随着预期平均负载率上下波动，并逐步收敛于预期平均负载率，说明本文算法求出的预期平均负载率有效地引导实际平均负载率的变化趋势，成为调节服务器负载的依据，从而出现图7所示的负载均衡。同时，负载率总偏差最小值保持在较小范围（0～0.03）内，且相对稳定，说明服务器整体的实际负载情况与预测期望负载率基本一致，进一步说明了本文负载均衡优化算法的正确性和有效性。

图8 实际平均负载率与预测平均负载率曲线变化图

5 结束语

本文提出了集群服务器在混合服务请求下的一类负载均衡优化算法，建立了混合负载量动态模型，对于静态页面访问，将同一类的静态页面访问分配给同一台服务器，提高缓存命中率和响应性；对于动态页面访问，使用一次指数平滑预测法预测下一周期各个服务器的负载率，避免使用实时测量数据而造成分配负载的滞后性和误差累积性，通过计算各台服务器分配动态页面访问后的负载率与预期负载率的偏差之和在约束条件下取得最小值，求出每台服务器的分配权重，并根据此权重对动态页面访问进行分配。仿真结果表明，本文提出的通过分类页面访问和预测引导负载分配的算法在均衡集群中各个服务器的负载具有更理想的效果。