基于机器学习的动态负载均衡模型研究

王春波

(黑龙江财经学院 财经信息工程系,哈尔滨 150025)

负载均衡(Load Balance)是指通过特定的算法将操作分摊到多个操作单元上进行执行，它建立在现有网络结构之上，提供了一种廉价有效透明的方法扩展网络设备和服务器的带宽、增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性。负载均衡算法是考量负载均衡性能的重要指标，现有的负载均衡算法主要分为静态和动态两类。笔者分析了现有负载均衡的优缺点，结合动态算法与静态算法的优点，引入机器学习预测算法与并行计算技术，重构负载均衡策略。该策略既兼顾静态算法的快速，又兼顾动态算法实时反馈性能，充分挖掘后端服务器的最大性能，提高整个系统的吞吐量，在实际项目中得到了良好的验证。

1 负载均衡算法的现状与问题

目前，现有的负载均衡算法主要分为静态和动态两类，静态负载均衡算法主要以轮询、加权轮询、随机和哈希算法为主，这类算法以固定的概率分配任务，不考虑服务器的状态信息；动态负载均衡算法以最小连接数、加权最小连接数和最短响应时间算法为代表,这类算法会根据服务器的实时负载状态信息来决定任务的分配。

动态算法和静态算法都有自身的优缺点，静态算法稳定、快速，但不能针对服务器负载能力进行调整，不利于效能的最大化；动态负载均衡算法一定程度上弥补了静态算法的不足，但仅仅关注连接数，忽略了后端服务器的负载响应，无法监控服务器性能,导致负载分配过于盲目化。

2 基于机器学习的动态负载均衡模型

综合动态算法和静态算法自身的优缺点，笔者考虑将两种算法结合起来，取长补短，并引入机器学习算法，设计出一个能够自我优化配置参数的负载均衡算法[1]。

简单来说，负载均衡是一个接收请求、按照策略转发请求的过程，图1中的经典模型对这个过程进行了很好地阐述。通过演进，得出图1中的改进模型，该模型与经典模型的区别在于：

图1 负载均衡模型演进

1)增加信息收集模块。该模块异步收集客户端发来的请求及其响应时间，并记录在本地日志中。

2)增加基于机器学习的预测模块。按一定频率获取日志中的内容数据，采用线性回归算法对未来的权重值进行预测，并将结果输出到策略转发模块。

3)改进加权轮询策略。接收预测结果，使其能根据预测结果动态调整权重值。

3 动态负载均衡模型流程、核心算法描述

改进后的负载均衡服务的调度部分由3个模块组成，分别是信息收集模块、权重预测模块和策略转发模块，3个模块独立并行工作，通过通讯接口进行信息交互。现假设有N台主机S={S1,S2,…,Sn}，服务启动后，调度部分的3个模块开始按照既定流程和算法开始工作。

3.1 信息收集模块流程

信息收集模块将收集到的信息进行整理，以文本形式存贮到磁盘上的指定目录，每行记录分别包含主机信息、请求开始时间戳和请求结束时间戳，信息之间用逗号进行分隔，例如：“S1,1604281068526,1604281068728”表示某请求在S1主机上的响应时间为202 ms。输出的每个文件记录数不超过10 000条，达到最大值时则关闭当前文件并创建新的文件，文件命名格式为DIS+时间，例如DIS20201102093022.log。完整的日志文件如图2所示。

图2 日志文件示例

3.2 权重预测模块

权重预测模块负责对收集到的信息统计整理，并使用机器学习算法进行权重预测[2]，步骤如下：

步骤1:初始化计时器Time，使其每隔一段时间触发，假设触发周期为T。

步骤2:计时器到达采样周期时，启动日志扫描分析程序，并预测实例主机的响应时间。

1)对样本集数据按主机编码进行分类，然后计算出每一时刻t请求所耗费的时间(1≤t≤n)，整理过程如图3所示。

图3 日志整理过程

2)对样本数据进行整理，计算出每个主机从t1至tn时刻每个时间点的响应时长，并将其绘制在二维平面上。图4展示了主机S1,S2响应时长的样本分布[3]。

图4 主机S1,S2的t1至tn时刻响应时长分布

观察样本数据，会发现数据样本集中在一定范围内上下震动，符合线性回归模型的数据特征[4]，同时考虑到应尽量使用计算量不大、计算不复杂的模型以减少对负载均衡主机算力的消耗，因而采用典型的线性回归模型进行预测，其训练模型y=wx+b，x∈t(1≤t≤n)为模型自变量，y为模型因变量，w为权重，b为偏置值。现需要通过样本数据的训练来获取w和b的值。通过数学知识可知平面上2个点即可确定一条直线，因此,这个样本集可确定无数条直线。为了在这些直线中找到最佳的拟合直线，通常引入一个损失函数(又称代价函数)作为衡量标准，其数学表达式为

(1)

式(1)的直观解释是：n个样本的预测值(wxi+b)与实际值yi之间欧式距离最小。满足这个条件的直线是拟合最好的直线，所以求取w和b值的问题转变为w和b取何值时损失函数Loss最小的问题。由于损失函数是一个凸函数，因而采用梯度下降法进行求解，其求解步骤如下[5]：

①加载训练数据集，以及设置算法运行超参数，设置如下：

训练数据集X={x1,x2,xi,…,xn};

X对应的目标值y={y1,y2,yi,…,yn};

权重值w=随机数(例如0.1);

偏置值b=随机数(例如0.1)；

学习速率η=0.000 01(经验值);

迭代次数its=100(经验值)。

②执行迭代for i in range(0,its):

计算第i个训练数据的权重w和偏置b相对于损失函数的梯度，参考式(2)和式(3)。

(2)

(3)

使用式(2)和式(3)计算得到梯度，更新每个样本的权重值和偏置值，参考式(4)和式(5)。

(4)

(5)

将得到的w和b代入式(6)，用集合运算方法算出每个样本的预测值。

pred=w×X+b.

(6)

计算均方误差，参考式(1)。

当均方误差值满足精度要求或达到最大迭代次数时，记录w和b，并退出循环。

③退出算法并返回w和b。

3)将已确定的w和b代入y=wx+b即可计算出tn+1起至下一个采样周期内该实例机器大致响应时间。

步骤3:根据步骤2预测出的响应时间调整每个实例的权重值。

计算出的响应时间越短说明机器负载能力越强，权重越大。可采用最大公倍数法计算每一个机器的权重，计算方式参考式(7)，结果保留一位小数。

(7)

步骤4:将计算出的每一个实例机器的权重传送至策略转发模块。

步骤5:计算下一次触发时间。

(8)

3.3 策略转发模块

策略转发模块负责将前端请求根据权重配比平滑地转发到后端实例机器，设有N台实例主机 S = {S1,S2,Si,…,Sn}，现做如下变量设置：

配置权重W={W1,W2,Wi,…,Wn}；

有效权重CW={CW1,CW2,CWi,…,CWn}。

以上为每个实例Si除了存在一个配置权重Wi外，还存在一个当前有效权重CWi，且令CWi初始化为Wi，即CWi=Wi。

指示变量currentPos=-1，表示当前选择的实例id初始化为-1。

配置权重和weightSum=W1+W2+Wi+…+Wn。

策略转发模块的调度过程描述如下：

1)变量初始化。由于无法准确知道后端每个实例的负载能力，可简单地根据硬件配置情况配置权重初始值，以硬件配置最低的实例为参考基准，设置为1。

2)选出当前有效权重最大的实例，将当前有效权重CWi减去所有实例的权重和weightSum，且变量 currentPos 指向此位置。

i=MAX(CW);

CW={CWi-weightSum};

currentPos=Index(i).

3)将每个实例i的当前有效权重CWi都加上配置权重Wi。

CW=CW+W.

4)取到变量currentPos指向的实例,向该实例主机转发请求。

5)判断当前有效权重CW是否为{0,0,…,0}，且是否已经进行(2n-1)次有效转发(n为后端主机数)。

①满足转发条件则进一步检查是否有权重预测模块传过来的权重值。如果有，则更新权重与有效权重配置，否则继续。

②不满足转发条件则继续执行。

6)每次调度重复上述步骤2)、3)、4)和5)。

4 算法分析

调度模块主要涉及到两个算法，分别是权重预测模块的预测算法和策略转发模块的调度算法。

4.1 权重预测模块算法

权重预测模块是对传统负载均衡服务的补充，主要有以下几个特点[6]：

1)预测算法采用经典线性回归模型进行预测，计算过程成熟稳定，且是定时触发，对主机算力消耗较小。

2)基于预测的方法获得负载信息，使得均衡调度的决策信息有提前量，不仅可以减少空闲节点等待新任务的时间，而且加快重载节点的任务迁移，使得每次均衡调度过程缩短，降低了任务迁移的抖动性，从而提高了均衡系统的效率。

3)算法使用了动态更新采样周期频率的方法，降低了负载均衡服务器的计算量。前期由于后端负载权重分配不合理会频繁触发预测机制进行负载权重估算，当权重值趋于合理化时，采样周期会越来越长,因而也会大大降低负载均衡服务器的计算量[7]。

4.2 策略转发模块算法

策略转发模块改进了传统加权轮询算法过于依赖经验判断的弊端，减少了人为干预，便于自动运维[8]。

1)策略转发算法精准定位更新权重值时机，有效避免了随意更新权重值时带来的抖动，保证了算法整体的平滑性。

2)策略转发主体算法避免了传统加权轮询算法一个明显的缺陷，即在某些特殊的权重下，加权轮询调度会生成不均匀的实例序列，这种不平滑的负载可能会使某些实例出现瞬时高负载的现象，导致系统存在宕机的风险。改进后的算法可平滑地加权轮询，从而进行有效调度。现假设有3个服务，其服务端口和权重配置如表1所示，根据表1的内容计算出配置权重和(weightSum)为 7，调度过程如表2所示。

表1 主机服务端口及权重配置

表2 调度过程

通过表2的示例过程可看出上述调度序列分散是非常均匀的，且第 8 次调度时，当前有效权重值又回到 {0,0,0}，实例的状态同初始状态一致，此时可判断是否有新的权重配置。

5 实验结果分析

为了验证基于机器学习的动态负载均衡模型是否能够到达预期效果，笔者按照以下步骤做验证。

1)准备验证环境。使用4个Linux工作站组成一个局域网，工作站的用途和配置情况如表3所示。

表3 工作站配置及用途

2)编写验证脚本。笔者使用开源的网站压力测试工具pylot对主机N1进行压力测试，用于模拟客户端对web服务的请求。主机N1接到请求后，则根据负载均衡策略开始向后端主机转发请求。首先配置测试用例，其部分内容见图5。

图5 测试用例

其对应的验证脚本部分内容如下[9]：

echo “压力测试脚本开始运行”

cd%～dp0bin

::开启200个并发线程持续1 h

python run.py-a 200-d 3600

...

python run.py-a 10000-d 1800

python run.py-a 8000-d 2000

...

python run.py-a 5000-d 3600

python run.py-a 1000-d 3600

echo “压力测试脚本运行结束”

验证脚本的思路是初始化并发量为200线程，持续一段时间后并发量逐渐递增至峰值100 000，在峰值处，压力测试持续一段时间后，并发量逐渐下降至稳定值1 000。整个压力测试过程持续5 h。

3)启动负载均衡服务并记录权重变化的数值。观察表3，可知主机S1与S2配置相当，主机S3配置好一些，根据经验配置S1,S2,S3的权重比为1∶1∶2。按照这个配置，S3要承担的负载分别是S1或S2的2倍，虽然S3配置好，但也承担了除Web服务以外的数据库服务工作，此时S3的实际负载能力根据经验就不好配置了。为了验证模型学习能力，设置3台主机的初始权重均为1。负载均衡服务运行后，权重预测模块会在磁盘生成日志文件predicted.log,其格式如下：

时间 进程编号 日志等级 {S1:“权重”，S2:“权重”，S3:“权重”}

4)可视化展示。日志redicted.log文件以JSON结构记录了权重数值的变化情况，使用制图工具，将数值变化情况绘制成权重变化趋势见图6。

图6 权重变化趋势

从图6可看出，程序运行之初，权重值抖动比较剧烈，随着时间的推移，权重变化相对平稳且变化幅度不大，权重值的调整符合预期效果[10]。

6 结束语

如何合理有效地配置负载均衡参数，提高负载

均衡的性能，充分挖掘负载机器的性能，一直是网络计算人员研究的一个热点。笔者结合动态算法与静态算法的优点，使用机器学习算法准实时预测调整权重，重构了负载均衡策略。使得负载均衡的配置大大降低了人为的干预，参数更加合理，充分挖掘后端服务器的最大性能，提高了整个系统的吞吐量[11]。