基于Agent的微信平台自适应负载均衡算法

林 伟, 丁志刚

(上海应用技术学院 电气与电子工程学院, 上海 200235)

基于Agent的微信平台自适应负载均衡算法

林 伟, 丁志刚

(上海应用技术学院 电气与电子工程学院, 上海 200235)

为构建高性能微信平台集群系统,以解决经典负载均衡算法中存在的智能性不足与自适应能力弱的问题,提出了一种基于Agent的自适应负载均衡算法。算法思路:首先,解析到达的用户请求,引入任务识别与分类思想,判断请求类型；然后,依据知识库规则与服务器负载现况,匹配最优的负载均衡算法；最后,应用了排队模型的服务器处理用户请求。结果表明,该算法极大增强了系统高并发处理能力,有效缩短了响应时间,确保了微信平台运行的稳定性。

微信平台; 负载均衡； 自适应算法； 高并发； 响应时间

信息技术和网络科技的发展日新月异,公众的生活与互联网的联系愈发紧密。以微信为代表的各类互联网应用,正在广泛而深入地影响着大众的生活方式。一方面,“互联网+”行动正式进入政府工作报告,而另一方面,互联网存量网民活跃度的不断攀升与网民规模的日益扩大,使得微信与大众生活的联系愈发紧密。相应的微信平台的负载也在不断加重,高并发请求日益增多。如何加快响应速度,提升工作效率与负载能力,成为互联网行业面临的一个难题。

主流的解决方案:构建高性能集群系统[1],以实现任务的合理分配与均衡调度。针对经典负载均衡算法智能性与自适应性的不足,本文提出了一种基于Agent的自适应负载均衡算法,并引入任务识别分类思想与排队论模型,通过应用新的算法来增强系统高并发处理能力,缩短响应时间,提升服务器运行的稳定性。

1 策略研究

1.1 理论模型

图1 基于Agent的自适应负载均衡算法模型

Agent[2]可被广义理解为分布式计算机系统,Agent技术的诞生得益于人工智能技术的发展。基于Agent的自适应负载均衡算法的模型见图1。结合图1,自适应负载均衡算法的执行逻辑如下:

(1) 用户任务达到系统,系统生成对应的任务Agent；

(2) 系统解析请求数据包,将请求任务的详细信息发送至整合模块；

(3) 整合模块负责数据整理,并利用预处理算法,将任务数据转换成一致的格式；

(4) 共享知识库为系统决策提供支持,负责维护请求任务列表,调度策略列表和服务器负载列表；

(5) 在任务管理与调度模块中,完成任务的分类与负载策略的调度；

(6) 任务管理与调度的决策由执行模块接收,再依据服务器负载信息,将用户任务分配给真实的服务器执行；

(7) 实时数据采集模块负责收集真实服务器的负载信息状况,并将最新数据同步至共享知识库。

1.2 排队论与线程池技术

算法中利用了排队模型与线程池技术[3-4]。本文在经典M/M/C单队列模型的基础上,提出了不同请求等级和绝对优先级的M/M/C多队列模型。多队列模型中对系统性能有影响的主要因素有:

(1) 服务器数量,记作C。

(2) 队列数,记作q,表示请求排队时的队列数目。

(3) 平均等待队长,记作Xe,表示处于等待状态的请求数。

用户请求任务数不同,则处理线程数也不同。若频繁地进行线程操作,会造成系统资源的消耗。算法线程池技术的思路:预先创建一批线程放在池中,按需取出,处理完成后放回池中。

文献[5]给出了系统最优性能、并发数和线程数的关系:

其中,c1表示创建一条线程的开销,c2表示管理单条线程的开销,N表示并发请求数,n表示线程数。采用这种做法可以极大地避免不必要的线程操作,并有效提高系统高并发下的性能。

2 模型分析

2.1 内核设计

Agent的内核[6]设计采用组件式结构,如图2所示。

图2 Agent的内核设计框图

本文设计的完整的Agent内核包含:邮箱、执行机构、黑板、数据库、协作引擎、规划机构和其他相关的功能模块。邮箱负责与外部进行通信,执行机构负责控制各相关功能模块,黑板负责内部通信,数据库负责记录自身的数据信息,协作引擎负责多Agent间的协同工作,规划机构负责用户请求的规划。规划机构涉及到多Agent间的合作与任务分解,是内核设计的关键部分。规划机构的工作原理如下:

(1) 解析请求,将目标任务分解为较小的子任务；

(2) 读取黑板中记录的信息,将子任务分配给对应的功能模块；

(3) 若某个子任务该Agent无法执行,则通知协作引擎启用多Agent协作[4]求解机制。

规划机构的代码设计如下:

public void planningAgency(Target t) {

ArrayListlistTarget=KnowledgeDB.parse(t);//解析请求

BlackBoardblackboard =new BlackBoard();//创建黑板类,用于读取信息

for(i=0;i

{

string strTask=listTarget.get(i);//读取子任务

string strModule=blackboard.seek(strTask);//查询对应的功能模块

if (strModule!= null)

{

//获取服务器

RemoteServerserver =ServiceLocator.getServer(strModule);server.execute(strTask);//服务器执行任务

}

else

CoopEngine.handle(strTask); //协作引擎介入处理

}

}

2.2 算法分析

假设,系统有C个后台服务器,各服务器之间的工作互不影响,各服务器的平均服务率为μ,则整个系统的平均服务率为C·μ。用户请求的到达强度用λ表示,文献[7]已证明,当λ/(C·μ)<1时,系统平稳分布。系统的状态集为E={0,1,2,…C}。

若系统状态k满足0≤k≤C,意味着k个服务器正在处理用户请求任务,(C-k)个服务器空闲；若k>C,则意味着C个服务器处于忙状态,而(k-C)个用户请求处于排队状态。

当系统处于平衡状态时,可得系统的K氏方程如下:

(1)

(2)

可得量化参数如下:

任务平均等待队长为

(3)

任务排队等待的概率为

(4)

任务队长均值为

(5)

3 仿真与应用

3.1 算法仿真

集群系统性能[7-8]的最直观的2个参数分别为响应时间和吞吐量。

任务队列用q表示,初始标识M0的所有可达标识集合为S,状态标识M的稳定状态概率用P[M]表示,则平均任务数量D(q)可表示为

(6)

服务器sj处理任务ri的响应时间RTij可表示为

RTij=D(qij)/TH(sij)

(7)

式中TH(sij)为稳定状态下任务变更的吞吐量

请求任务ri的响应时间为

(8)

TH(sij)可表示为

(9)

请求任务ri的吞吐量THi可表示为

(10)

整个服务器系统的吞吐量TH为

(11)

传统负载均衡算法中,加权最小连接算法[9]较为常见。选取加权最小连接算法与本文算法进行比较。使用WAS(Web应用压力工具)进行仿真测试,模拟真实的用户访问[10]。

图3为应用自适应负载均衡算法和加权最小连接算法处理用户请求时的响应时间的比较。

图3 响应时间的对比

图4为应用自适应负载均衡算法和加权最小连接算法处理用户请求时的吞吐量的比较。

图4 吞吐量的对比

仿真结果表明:大量客户端并发访问的情况下,自适应负载均衡算法优于传统负载均衡算法。

3.2 实际应用

基于自适应负载均衡算法,为企业微信公众号设计了后台系统。企业公众号有近40万的关注用户,页面浏览量的峰值为25万户。应用传统负载均衡算法和自适应负载均衡算法得到的企业微信推送秒杀活动的服务器内存利用率分别见图5和图6(除应用的负载均衡算法不同,其余参数均接近)。可直观地看出,高并发请求下,自适应负载均衡算法可有效节省系统资源,提高服务器工作效率。

不同时刻服务器负载状况的对比见表1。

图5 应用传统负载均衡算法服务器实时内存利用率

图6 应用自适应负载均衡算法服务器实时内存利用率

算法平均负载任务必须排队的概率任务等待的队长传统算法0.570.282.8自适应算法0.390.08320.0253

由表1可见,应用了自适应负载均衡算法的系统拥有显著的优势。

4 结论

本文提出的基于Agent的自适应负载均衡算法,引入任务识别分类思想与排队论模型[11],帮助企业构建了高性能微信平台集群系统,实现了任务的合理分配与均衡调度[12-13],解决了传统算法智能性与自适应能力的不足。通过该算法的应用增强了系统高并发处理能力,缩短了响应时间,提升了服务器运行的稳定性。

References)

[1] Chunyong Yang, Shaoping Cheng. Routing Optimization for Network load Balance Based on Improved Ant Colony Algorithm[J]. Computer Engineering, 3010,36(8):4-6.

[2] 尤天舒.基于Agent的集群负载均衡模型及其实验研究[D].长春：吉林大学,2014.

[3] 孙秀斌,李云敏. 基于线程池技术的云闪定位远程控制软件设计[J]. 测控技术,2014,33(11):100-103.

[4] 孟凡彦,陈嘉. 基于线程池技术DHCP服务器的设计与实现[J]. 计算机应用研究,2005,22(12):258-260.

[5] 崔慎智,陈志泊.基于多代理和多优先队列的短信实时并发算法[J].计算机工程,2011,37(3):278-283.

[6] 郑啸,罗军舟,宋爱波.基于Agent和蚁群算法的分布式服务发现[J].软件学报,2010,21(8):1795-1809.

[7] 徐传福,车永刚,王正华,等.基于并行模拟的多核集群系统性能预测和分析[J].国防科技大学学报,2010,32(5):62-68.

[8] 朱晓敏,陆佩忠. 异构集群系统中安全关键实时应用调度研究[J]. 计算机学报,2010,33(12):2364-2377.

[9] 李军锋,何明昕.高并发Web航空票务秒杀系统的设计与实现[J].计算机工程与设计,2013,34(3):778-782.

[10] Mao Xinjun, Chang Zhiming. Agent-Orient Software Design Patterns[J]. ComputerEngineering and Science, 2011,33(2):72-78.

[11] 李炯,罗光春,陈浩然. 基于排队理论的自适应负载均衡算法的研究[J]. 四川大学学报:自然科学版,2009,46(4):929-933.

[12] 皇甫宁.基于内容的负载均衡技术的研究与实现[D].广州:华南理工大学,2013.

[13] 戴艺,苏金树,孙志刚,等.基于流映射的负载均衡调度算法研究[J].计算机学报,2012,35(2):218-228.

Adaptive load balancing algorithm of WeChat platform based on Agent

Lin Wei, Ding Zhigang

(School of Electrical and Electronic Engineering, Shanghai Institute of Technology, Shanghai 200235, China)

In order to build a high-performance WeChat platform cluster system and solve weakness of classical load balancing algorithm in intelligence and adaptivity, an adaptive load balancing algorithm based on Agent is proposed. Algorithm ideas are in the following: firstly, parsing arrived users’ requests; introducing ideas of identification and classification, judging the type of request; then, matching the optimal load balancing algorithm based on knowledge rules and server loading status; finally, using server which is deployed with queuing model to process users’ requests. Results show that the new algorithm can enhance system’s high concurrent processing capability greatly, shorten response time and ensure the stability of system.

WeChat platform; load balancing; adaptive algorithm; high concurrency; response time

2015- 07- 20 修改日期：2015- 08- 02

林伟(1967—)，男，上海，硕士，讲师，研究方向为信号采集与处理、智能仪器仪表检测技术等.

TP301.6

A

1002-4956(2015)12- 0063- 03