本发明涉及服务器集群负载均衡技术的算法领域，特别涉及一种基于加权一致性哈希算法的改进负载均衡算法。
背景技术：
随着互联网技术的普及和发展，互联网用户快速增加，同时新媒体不断涌现，更多的人开始使用互联网来观看视频或直播、进行网络会议、视频互动等。传统视频直播和会议软件采用c/s架构，近年来随着以html5为代表的web技术的高速发展，基于web浏览器的b/s架构直播日渐兴起。
webrtc(webreal-timecommunication,网页实时通信)是一种不必使用插件就可以在浏览器之间进行实时通信的开源技术.目前大多数主流浏览器(例如chrome、firefox、safari等)都已支持webrtc功能，webrtc建立实时通信主要包括两个步骤:信令交互和媒体传输。信令交互方面开发者可以根据需要选用合适的协议(json、sip等)；媒体传输常用p2p方式传输媒体流，当用户量较高而p2p不能满足并发需求时，则采用媒体服务器转发方式扩展并发量。
kurentomediaserver是一个开源的webrtc媒体服务器,提供了一系列api简化webrtc应用程序开发流程。单台kurento媒体服务器满足实时通信要求的最大并发量是175,当用户量超过175时,就会出现明显的卡顿现象。
为了提高并发量，必须采取媒体服务器集群的方式，在现有的服务器集群方案中，常用nginx、lvs等作为负载均衡器分配用户请求到后台服务器。其中nginx中自带的经典负载均衡算法有轮询法(roundrobin)、基于ip的哈希法(ip_hash)、基于url的哈希法(url_hash)、最小响应时间法(fair)等，前4种算法都可根据服务器节点的处理能力而对服务器节点分配不同权值，进行静态加权或动态加权。
静态加权以服务器处理能力固定权值，当并发量较高时，服务器节点的实时剩余负载能力并不能以初始权值来判断，可能会导致负载分配的不均衡。动态分配权值算法一般以任务请求数、cpu利用率、内存利用率、带宽利用率和其他参数等作为负载参数，每个固定周期读取当前服务器节点负载，综合计算后根据节点总负载量来实时分配权值,具有较好的负载均衡能力，但是也存在着一定的不足，比如当瞬时负载较高时，用户请求会大量分配给权值较高的服务器，降低该服务器节点的处理能力，但因为未达到周期值，服务器权值并未更新，该服务器节点依然大量接收请求，无法满足实时性负载均衡的需求。
技术实现要素：
为了解决存在的上述问题，本发明提供了一种动态周期的加权一致性哈希的负载均衡改进算法，利用二次指数平滑法，通过请求量的历史数据，预测下个周期的任务请求量，从而计算下一个周期的周期值。此方法是在nginx负载均衡器自带的负载算法基础上，实现加权一致性哈希算法，将权值映射为哈希环中虚拟节点的个数，通过模拟退火算法来动态调整，能够满足用户将同群组客户端转发到同一台服务器节点上，保持session一致性的需求。
为了实现以上目的，本发明主要通过以下技术方案实现：
一种动态周期的媒体服务器负载均衡算法，其特点是，包括如下步骤：
(1)收集服务器节点的初始处理能力，参数包括服务器的cpu、内存、带宽。计算出节点的初始权重k0,初始化负载均衡服务；
(2)每个周期内，通过负载均衡器收集服务器节点的负载信息，参数包括cpu利用率、内存利用率、带宽利用率，任务请求数；
(3)根据步骤(2)中收集到的负载信息，进行加权平均，计算出每个服务器节点的总负载l(i),其中i为当前节点，取值为1-n，n是服务器节点总个数；
(4)采用二次指数平滑法，以任务请求数作为负载参数，通过预测下个周期的并发量，来动态调整周期值：二次指数平滑法是将历史数据进行加权平均，预测未来结果，距离越近，影响权重越高。它拥有计算简单、样本要求量少、结果稳定等优点。为避免计算过长影响延迟，取最近的前5个周期内每秒任务请求数作为样本，对5个数据依次进行平滑，利用二次指数平滑模型预测出下个周期的结果。根据该预测请求量，计算下个周期的周期长度。
(5)nginx中实现自定义负载均衡算法模块,实现加权一致性哈希算法：
一致性哈希算法是将服务器节点通过哈希函数映射到一个值域为[0,232–1]的环上,同时将请求也映射到环上,顺时针寻找最近的服务器节点。一致性哈希算法添加或删除节点时，只影响前面或后面的节点，不影响整个集群的稳定性。
一致性哈希算法可通过在哈希环上添加虚拟节点的方式来配置节点的权重，权重高的服务器可配置多个虚拟节点。通过consul和nginx中的开源模块nginx-upsync-module来实现权重的动态调整，nginx-upsync-module是nginx实现动态配置的第三方模块，通过拉取consul上游数据，实现无需重新加载nginx.conf，即可动态修改配置中后端服务器属性(weight，max_fails，fail_timeout等)。利用http命令在服务端将权重动态写入consul配置，nginx周期性从consul中读取配置信息来动态改变当前权重；
(6)动态调整加权一致性哈希算法的权值向量，更新算法中的服务器节点权值：
动态权值算法采用经典启发式算法模拟退火算法，模拟退火算法是从一足够高的初始温度出发，逐渐降温，在初始解的基础上扰动产生新解，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，有效避免陷入局部最优并最终趋于全局最优。
其中解向量为权值向量k0，目标函数为服务器集群中的节点总负载之和l_all；
算法的输入值为初始解、初始温度、每个温度下的迭代次数、终止温度、阈值，输出值为使目标函数最低的新解。
(7)nginx负载均衡器根据加权一致性哈希算法寻找后端可用服务器节点，将任务请求分配到可用节点进行并发处理。
本发明与现有技术相比，具有以下优点：
本发明实现了周期的动态变化，相比目前的固定周期动态权值算法，提高了权值更新的效率。以任务请求量的历史数据作为样本，利用时序预测算法二次指数平滑法，有效预测下个周期的负载变化，实现了服务器集群对实时负载状况的良好自适应调整。
本发明实现的加权一致性哈希算法是基于传统哈希算法的改进，添加或删除节点时，只影响前面或后面的节点，不影响整个集群的稳定性。做到了将同一个ip地址的请求转发到同一台服务器节点上，保持session一致性的同时，可随时修改服务器节点的个数。
本发明的动态权值算法不同于只根据负载信息计算动态权值，而是采用启发式算法模拟退火，输入权值向量作为初始解，求得能使服务器集群总负载量降低的新解，并概率性跳出局部最优解，迭代降温并最终趋于全局最优。实现了服务器集群良好的负载均衡。
附图说明
图1是本发明实施例中的负载均衡总步骤流程图；
图2是本发明实施例中的动态权值调整算法流程图；
具体实施方式
初始化负载均衡服务：
读取服务器节点配置文件，将服务器的cpu、内存、带宽等原始静态参数作为负载能力，计算出初始权值向量k0。
k0＝[k(1)k(2)......k(n)]
k(k)＝α×p_cpu(i) β×p_mem(i) γ×p_net(i)
其中i是指当前服务器节点，取值为1到n，n为服务器节点总个数。p_cpu(i)为当前服务器节点的cpu参数、p_mem(i)为内存参数、p_net(i)为带宽参数。α、β、γ为权重系数。α取值为0.4，β取值为0.2，γ取值为0.4。
其中，
nginx集群配置中的负载均衡方法设置为：consistent_hash。通过consul和nginx-upsync-module来实现权重的动态调整。在consul配置中添加后端服务器的ip地址及初始权重，后续权重调整利用http命令curl-xput-d向consul配置中动态写入后端服务器的ip地址以及新权重；将consul服务器ip和配置文件路径配置到nginx.conf中的upsync系列参数中，实现nginx周期性从consul中读取配置信息来动态改变权重。初始化权重之后，周期t0开始，前5个周期时长初始默认为8s。
根据初始权值向量，负载均衡器nginx调用加权一致性哈希算法，将任务请求按照权值分配给服务器节点处理，相同ip的请求分配到同一台服务器上，保证用户的session一致性。
每个周期结束时，获取当前各个节点的负载信息，参数包括cpu利用率、内存利用率、带宽利用率，任务请求数。前5个周期结束后，利用二次指数平滑法，通过每秒任务请求数的历史数据，预测下个周期的每秒任务请求数，从而计算下一个周期的周期长度，当预测请求数较高时，周期缩短；预测请求数较低时，周期延长。
步骤1：对所有数据进行一次指数平滑，一次平滑公式为：
其中
步骤2：结合步骤1中一次指数平滑结果，对数据进行二次指数平滑，二次指数平滑公式为：
其中st(2)是周期t时任务请求数的二次平滑值；
步骤3：取步骤1中获得的一次指数平滑值
yt 1＝at bt
at和bt为平滑模型的参数变量，yt 1即为周期t 1内的任务请求数预测值。
步骤4：根据任务请求数的预测值与理想并发量的比值，以初始周期8s为基础，计算出下个周期的周期长度pt 1：
其中y为理想并发量，即理想情况下的每秒请求数。为避免周期过大过小，pt 1取值范围为[6，15]以内的整数，非整数向下取整，低于6s时取值为6s，高于15s时取值为15s。
根据cpu利用率、内存利用率、带宽利用率计算出各个节点负载能力l(i)。
l(i)＝α×l_cpu(i) β×l_mem(i) γ×l_net(i)
其中l_cpu(i)为当前服务器节点的cpu利用率、l_mem(i)为内存利用率、l_net(i)为带宽利用率。α、β、γ为权重系数，cpu利用率的权重系数α取值为0.4，内存利用率权重系数β取值为0.2，带宽利用率权重系数γ取值为0.4。
调用模拟退火动态权值算法修正权值，初始解为权值向量x＝k0，目标函数为f(x)＝l_all。
步骤1：输入初始参数，计算目标函数初始值。在本实施例中，根据模拟退火算法常用取值，算法输入值中初始温度t0取值为100，每个温度下的迭代次数j取值为100次、终止温度取值为1×10-8。因所有节点总权值之和为1，故阈值b取值为0.2，含义为当权值变化量大于20％时，更新权值。
步骤2：在k0的基础上，随机上下扰动产生新解k_new：
k_new＝[k_new(1)k_new(2)……k_new(n)]
其中random(-0.5，0.5)为产生一个取值范围在(-0.5，0.5)之间的随机数，i为当前服务器节点，取值为1-n，n是服务器节点总个数。
步骤3：计算新解的目标函数f(k_new)，对比初始值f(k0)得到变化量δf＝f(k_new)-f(k0)，判断目标函数的值是否降低了，降低则k0接受新解，否则概率接受新解。
当δf<0时，接受新的解k_new作为当前解，将向量k_new赋予向量k0继续循环。
当δf>0时，一定概率下接受新的解k_new，概率函数为：
温度越低，接受新解的概率越低；新旧目标函数值差值越大，接受新解的概率越低。
步骤4：此温度下迭代j次，重复步骤2、3，直到达到迭代次数，输出新解。
步骤5：此温度下迭代完成，降温，新温度t_new＝a×t0,a为降温系数，取值为0.98。新温度下继续重复步骤2、3、4，当温度低于终止温度1×10-8时，降温结束，返回当前最优解k_new。
步骤6：为避免因变动较小更新权值时会降低效率，提高延迟，设置阈值b。只有当权值变化量δk大于预设阈值时，才会更新负载均衡器中服务器节点的权值参数，否则变动较小，不必更新权值，继续开始下一轮周期。
更新权值之后，任务请求通过nginx中加权一致性负载均衡算法，分配到各个服务器节点处理，实现了nginx对后端服务器的负载实时掌控。
1.一种动态周期的媒体服务器负载均衡算法，其特征在于，包括如下步骤：
(1)收集服务器节点的初始处理能力，参数包括服务器的cpu、内存、带宽；计算出节点的初始权重k0，初始化负载均衡服务；
(2)每个周期内，通过负载均衡器收集服务器节点的负载信息，参数包括包括cpu利用率、内存利用率、带宽利用率、任务请求数；
(3)根据步骤(2)中收集到的负载信息，进行加权平均，节点权值之和为1，计算出每个服务器节点的总负载l(i)，其中i为当前节点，取值为1-n，n是服务器节点总个数；
(4)根据负载参数动态调整周期值，实现周期随负载变化的动态更新；
(5)nginx中实现自定义负载均衡算法模块，实现加权一致性哈希算法；
(6)动态调整加权一致性哈希算法的权值向量，更新算法中的服务器节点权值；
(7)nginx负载均衡器根据加权一致性哈希算法寻找后端可用服务器节点，将任务请求分配到可用节点进行并发处理。
2.根据权利要求1所述的一种动态周期的媒体服务器负载均衡算法，其特征在于，所述步骤(4)中，周期值的调整方法为：利用二次指数平滑法，通过每秒任务请求数的历史数据，预测下个周期的每秒任务请求数，从而计算下一个周期的周期长度，当预测请求数较高时，周期缩短；预测请求数较低时，周期延长；所述的周期长度pt 1为：
其中周期长度pt 1以初始周期8s为基础，取值范围为[6，15]以内的整数，非整数向下取整，低于6s时取值为6s，高于15s时取值为15s；y为理想并发量，yt 1为通过二次指数平滑模型预测出的周期t 1内的请求数。
3.根据权利要求2所述的一种动态周期的媒体服务器负载均衡算法，其特征在于，预测请求数yt 1的计算过程为：
yt 1＝at bt
其中
4.根据权利要求1所述的一种动态周期的媒体服务器负载均衡算法，其特征在于，所述步骤(3)中，所述节点负载能力l(i)为：l(i)＝a×l_cpu(i) β×l_mem(i) λ×l_net(i)；
其中i为当前服务器节点，取值为1-n，n是服务器节点总个数；l_cpu(i)为当前服务器节点的cpu利用率、l_mem(i)为内存利用率、l_net(i)为带宽利用率；α、β、λ为权重系数；所述cpu利用率的权重系数α取值为0.4，内存利用率权重系数β取值为0.2，带宽利用率权重系数λ取值为0.4。
5.根据权利要求1所述的一种动态周期的媒体服务器负载均衡算法，其特征在于，所述步骤(6)中，动态权值调整采用模拟退火算法，步骤为：
(1)输入初始参数，计算目标函数初始值；输入参数包括初始解、初始温度、每个温度下的迭代次数、终止温度、阈值；
初始解向量x＝k0＝[k(1)k(2)......k(n)]，目标函数值为集群中所有节点负载能力的总和，计算公式为：
其中l(i)为权利要求4中所述的节点负载能力，k(i)为第i个服务器节点的权值；
(2)在初始解向量k0的基础上，随机上下扰动产生新解向量k_new：
k_new＝[k_new(1)k_new(2)......k_new(n)]；
其中random(-0.5，0.5)为产生一个取值范围在(-0.5，0.5)之间的随机数，t0为步骤(1)中输入的初始温度；
(3)计算新解的目标函数f(k_new)，对比初始值f(k0)得到变化量δf＝f(k_new)-f(k0)，判断目标函数的值是否降低了，降低则接受新解为当前解，将向量k_new赋予向量k0继续循环，否则概率接受新解，概率函数为：
(4)内循环：此温度下重复步骤(2)、(3)，直到循环次数满足步骤(1)中初始参数要求，输出新解；
(5)外循环：此温度下迭代完成，降温，新温度t_new＝a×t0，a为降温系数，取值为0.98；新温度下继续重复步骤(2)、(3)、(4)，当满足步骤(1)中输入的终止温度时，降温结束，返回当前最优解k_new；
(6)当权值变化量δk大于步骤(1)中输入的阈值时，更新负载均衡器中服务器节点的权值参数，否则继续开始下一轮周期；所述权值变化量δk计算公式为：
其中i为当前服务器节点，取值为1-n，n是服务器节点总个数。
技术总结