基于Agent的微信平臺(tái)自適應(yīng)負(fù)載均衡算法

林 偉, 丁志剛

(上海應(yīng)用技術(shù)學(xué)院 電氣與電子工程學(xué)院, 上海 200235)

基于Agent的微信平臺(tái)自適應(yīng)負(fù)載均衡算法

林 偉, 丁志剛

(上海應(yīng)用技術(shù)學(xué)院 電氣與電子工程學(xué)院, 上海 200235)

為構(gòu)建高性能微信平臺(tái)集群系統(tǒng),以解決經(jīng)典負(fù)載均衡算法中存在的智能性不足與自適應(yīng)能力弱的問題,提出了一種基于Agent的自適應(yīng)負(fù)載均衡算法。算法思路:首先,解析到達(dá)的用戶請(qǐng)求,引入任務(wù)識(shí)別與分類思想,判斷請(qǐng)求類型；然后,依據(jù)知識(shí)庫規(guī)則與服務(wù)器負(fù)載現(xiàn)況,匹配最優(yōu)的負(fù)載均衡算法；最后,應(yīng)用了排隊(duì)模型的服務(wù)器處理用戶請(qǐng)求。結(jié)果表明,該算法極大增強(qiáng)了系統(tǒng)高并發(fā)處理能力,有效縮短了響應(yīng)時(shí)間,確保了微信平臺(tái)運(yùn)行的穩(wěn)定性。

微信平臺(tái); 負(fù)載均衡； 自適應(yīng)算法； 高并發(fā)； 響應(yīng)時(shí)間

信息技術(shù)和網(wǎng)絡(luò)科技的發(fā)展日新月異,公眾的生活與互聯(lián)網(wǎng)的聯(lián)系愈發(fā)緊密。以微信為代表的各類互聯(lián)網(wǎng)應(yīng)用,正在廣泛而深入地影響著大眾的生活方式。一方面,“互聯(lián)網(wǎng)+”行動(dòng)正式進(jìn)入政府工作報(bào)告,而另一方面,互聯(lián)網(wǎng)存量網(wǎng)民活躍度的不斷攀升與網(wǎng)民規(guī)模的日益擴(kuò)大,使得微信與大眾生活的聯(lián)系愈發(fā)緊密。相應(yīng)的微信平臺(tái)的負(fù)載也在不斷加重,高并發(fā)請(qǐng)求日益增多。如何加快響應(yīng)速度,提升工作效率與負(fù)載能力,成為互聯(lián)網(wǎng)行業(yè)面臨的一個(gè)難題。

主流的解決方案:構(gòu)建高性能集群系統(tǒng)[1],以實(shí)現(xiàn)任務(wù)的合理分配與均衡調(diào)度。針對(duì)經(jīng)典負(fù)載均衡算法智能性與自適應(yīng)性的不足,本文提出了一種基于Agent的自適應(yīng)負(fù)載均衡算法,并引入任務(wù)識(shí)別分類思想與排隊(duì)論模型,通過應(yīng)用新的算法來增強(qiáng)系統(tǒng)高并發(fā)處理能力,縮短響應(yīng)時(shí)間,提升服務(wù)器運(yùn)行的穩(wěn)定性。

1 策略研究

1.1 理論模型

圖1 基于Agent的自適應(yīng)負(fù)載均衡算法模型

Agent[2]可被廣義理解為分布式計(jì)算機(jī)系統(tǒng),Agent技術(shù)的誕生得益于人工智能技術(shù)的發(fā)展?；贏gent的自適應(yīng)負(fù)載均衡算法的模型見圖1。結(jié)合圖1,自適應(yīng)負(fù)載均衡算法的執(zhí)行邏輯如下:

(1) 用戶任務(wù)達(dá)到系統(tǒng),系統(tǒng)生成對(duì)應(yīng)的任務(wù)Agent；

(2) 系統(tǒng)解析請(qǐng)求數(shù)據(jù)包,將請(qǐng)求任務(wù)的詳細(xì)信息發(fā)送至整合模塊；

(3) 整合模塊負(fù)責(zé)數(shù)據(jù)整理,并利用預(yù)處理算法,將任務(wù)數(shù)據(jù)轉(zhuǎn)換成一致的格式；

(4) 共享知識(shí)庫為系統(tǒng)決策提供支持,負(fù)責(zé)維護(hù)請(qǐng)求任務(wù)列表,調(diào)度策略列表和服務(wù)器負(fù)載列表；

(5) 在任務(wù)管理與調(diào)度模塊中,完成任務(wù)的分類與負(fù)載策略的調(diào)度；

(6) 任務(wù)管理與調(diào)度的決策由執(zhí)行模塊接收,再依據(jù)服務(wù)器負(fù)載信息,將用戶任務(wù)分配給真實(shí)的服務(wù)器執(zhí)行；

(7) 實(shí)時(shí)數(shù)據(jù)采集模塊負(fù)責(zé)收集真實(shí)服務(wù)器的負(fù)載信息狀況,并將最新數(shù)據(jù)同步至共享知識(shí)庫。

1.2 排隊(duì)論與線程池技術(shù)

算法中利用了排隊(duì)模型與線程池技術(shù)[3-4]。本文在經(jīng)典M/M/C單隊(duì)列模型的基礎(chǔ)上,提出了不同請(qǐng)求等級(jí)和絕對(duì)優(yōu)先級(jí)的M/M/C多隊(duì)列模型。多隊(duì)列模型中對(duì)系統(tǒng)性能有影響的主要因素有:

(1) 服務(wù)器數(shù)量,記作C。

(2) 隊(duì)列數(shù),記作q,表示請(qǐng)求排隊(duì)時(shí)的隊(duì)列數(shù)目。

(3) 平均等待隊(duì)長,記作Xe,表示處于等待狀態(tài)的請(qǐng)求數(shù)。

用戶請(qǐng)求任務(wù)數(shù)不同,則處理線程數(shù)也不同。若頻繁地進(jìn)行線程操作,會(huì)造成系統(tǒng)資源的消耗。算法線程池技術(shù)的思路:預(yù)先創(chuàng)建一批線程放在池中,按需取出,處理完成后放回池中。

文獻(xiàn)[5]給出了系統(tǒng)最優(yōu)性能、并發(fā)數(shù)和線程數(shù)的關(guān)系:

其中,c1表示創(chuàng)建一條線程的開銷,c2表示管理單條線程的開銷,N表示并發(fā)請(qǐng)求數(shù),n表示線程數(shù)。采用這種做法可以極大地避免不必要的線程操作,并有效提高系統(tǒng)高并發(fā)下的性能。

2 模型分析

2.1 內(nèi)核設(shè)計(jì)

Agent的內(nèi)核[6]設(shè)計(jì)采用組件式結(jié)構(gòu),如圖2所示。

圖2 Agent的內(nèi)核設(shè)計(jì)框圖

本文設(shè)計(jì)的完整的Agent內(nèi)核包含:郵箱、執(zhí)行機(jī)構(gòu)、黑板、數(shù)據(jù)庫、協(xié)作引擎、規(guī)劃機(jī)構(gòu)和其他相關(guān)的功能模塊。郵箱負(fù)責(zé)與外部進(jìn)行通信,執(zhí)行機(jī)構(gòu)負(fù)責(zé)控制各相關(guān)功能模塊,黑板負(fù)責(zé)內(nèi)部通信,數(shù)據(jù)庫負(fù)責(zé)記錄自身的數(shù)據(jù)信息,協(xié)作引擎負(fù)責(zé)多Agent間的協(xié)同工作,規(guī)劃機(jī)構(gòu)負(fù)責(zé)用戶請(qǐng)求的規(guī)劃。規(guī)劃機(jī)構(gòu)涉及到多Agent間的合作與任務(wù)分解,是內(nèi)核設(shè)計(jì)的關(guān)鍵部分。規(guī)劃機(jī)構(gòu)的工作原理如下:

(1) 解析請(qǐng)求,將目標(biāo)任務(wù)分解為較小的子任務(wù)；

(2) 讀取黑板中記錄的信息,將子任務(wù)分配給對(duì)應(yīng)的功能模塊；

(3) 若某個(gè)子任務(wù)該Agent無法執(zhí)行,則通知協(xié)作引擎啟用多Agent協(xié)作[4]求解機(jī)制。

規(guī)劃機(jī)構(gòu)的代碼設(shè)計(jì)如下:

public void planningAgency(Target t) {

ArrayListlistTarget=KnowledgeDB.parse(t);//解析請(qǐng)求

BlackBoardblackboard =new BlackBoard();//創(chuàng)建黑板類,用于讀取信息

for(i=0;i

{

string strTask=listTarget.get(i);//讀取子任務(wù)

string strModule=blackboard.seek(strTask);//查詢對(duì)應(yīng)的功能模塊

if (strModule!= null)

{

//獲取服務(wù)器

RemoteServerserver =ServiceLocator.getServer(strModule);server.execute(strTask);//服務(wù)器執(zhí)行任務(wù)

}

else

CoopEngine.handle(strTask); //協(xié)作引擎介入處理

}

}

2.2 算法分析

假設(shè),系統(tǒng)有C個(gè)后臺(tái)服務(wù)器,各服務(wù)器之間的工作互不影響,各服務(wù)器的平均服務(wù)率為μ,則整個(gè)系統(tǒng)的平均服務(wù)率為C·μ。用戶請(qǐng)求的到達(dá)強(qiáng)度用λ表示,文獻(xiàn)[7]已證明,當(dāng)λ/(C·μ)<1時(shí),系統(tǒng)平穩(wěn)分布。系統(tǒng)的狀態(tài)集為E={0,1,2,…C}。

若系統(tǒng)狀態(tài)k滿足0≤k≤C,意味著k個(gè)服務(wù)器正在處理用戶請(qǐng)求任務(wù),(C-k)個(gè)服務(wù)器空閑；若k>C,則意味著C個(gè)服務(wù)器處于忙狀態(tài),而(k-C)個(gè)用戶請(qǐng)求處于排隊(duì)狀態(tài)。

當(dāng)系統(tǒng)處于平衡狀態(tài)時(shí),可得系統(tǒng)的K氏方程如下:

(1)

(2)

可得量化參數(shù)如下:

任務(wù)平均等待隊(duì)長為

(3)

任務(wù)排隊(duì)等待的概率為

(4)

任務(wù)隊(duì)長均值為

(5)

3 仿真與應(yīng)用

3.1 算法仿真

集群系統(tǒng)性能[7-8]的最直觀的2個(gè)參數(shù)分別為響應(yīng)時(shí)間和吞吐量。

任務(wù)隊(duì)列用q表示,初始標(biāo)識(shí)M0的所有可達(dá)標(biāo)識(shí)集合為S,狀態(tài)標(biāo)識(shí)M的穩(wěn)定狀態(tài)概率用P[M]表示,則平均任務(wù)數(shù)量D(q)可表示為

(6)

服務(wù)器sj處理任務(wù)ri的響應(yīng)時(shí)間RTij可表示為

RTij=D(qij)/TH(sij)

(7)

式中TH(sij)為穩(wěn)定狀態(tài)下任務(wù)變更的吞吐量

請(qǐng)求任務(wù)ri的響應(yīng)時(shí)間為

(8)

TH(sij)可表示為

(9)

請(qǐng)求任務(wù)ri的吞吐量THi可表示為

(10)

整個(gè)服務(wù)器系統(tǒng)的吞吐量TH為

(11)

傳統(tǒng)負(fù)載均衡算法中,加權(quán)最小連接算法[9]較為常見。選取加權(quán)最小連接算法與本文算法進(jìn)行比較。使用WAS(Web應(yīng)用壓力工具)進(jìn)行仿真測試,模擬真實(shí)的用戶訪問[10]。

圖3為應(yīng)用自適應(yīng)負(fù)載均衡算法和加權(quán)最小連接算法處理用戶請(qǐng)求時(shí)的響應(yīng)時(shí)間的比較。

圖3 響應(yīng)時(shí)間的對(duì)比

圖4為應(yīng)用自適應(yīng)負(fù)載均衡算法和加權(quán)最小連接算法處理用戶請(qǐng)求時(shí)的吞吐量的比較。

圖4 吞吐量的對(duì)比

仿真結(jié)果表明:大量客戶端并發(fā)訪問的情況下,自適應(yīng)負(fù)載均衡算法優(yōu)于傳統(tǒng)負(fù)載均衡算法。

3.2 實(shí)際應(yīng)用

基于自適應(yīng)負(fù)載均衡算法,為企業(yè)微信公眾號(hào)設(shè)計(jì)了后臺(tái)系統(tǒng)。企業(yè)公眾號(hào)有近40萬的關(guān)注用戶,頁面瀏覽量的峰值為25萬戶。應(yīng)用傳統(tǒng)負(fù)載均衡算法和自適應(yīng)負(fù)載均衡算法得到的企業(yè)微信推送秒殺活動(dòng)的服務(wù)器內(nèi)存利用率分別見圖5和圖6(除應(yīng)用的負(fù)載均衡算法不同,其余參數(shù)均接近)?？芍庇^地看出,高并發(fā)請(qǐng)求下,自適應(yīng)負(fù)載均衡算法可有效節(jié)省系統(tǒng)資源,提高服務(wù)器工作效率。

不同時(shí)刻服務(wù)器負(fù)載狀況的對(duì)比見表1。

圖5 應(yīng)用傳統(tǒng)負(fù)載均衡算法服務(wù)器實(shí)時(shí)內(nèi)存利用率

圖6 應(yīng)用自適應(yīng)負(fù)載均衡算法服務(wù)器實(shí)時(shí)內(nèi)存利用率

算法平均負(fù)載任務(wù)必須排隊(duì)的概率任務(wù)等待的隊(duì)長傳統(tǒng)算法0.570.282.8自適應(yīng)算法0.390.08320.0253

由表1可見,應(yīng)用了自適應(yīng)負(fù)載均衡算法的系統(tǒng)擁有顯著的優(yōu)勢。

4 結(jié)論

本文提出的基于Agent的自適應(yīng)負(fù)載均衡算法,引入任務(wù)識(shí)別分類思想與排隊(duì)論模型[11],幫助企業(yè)構(gòu)建了高性能微信平臺(tái)集群系統(tǒng),實(shí)現(xiàn)了任務(wù)的合理分配與均衡調(diào)度[12-13],解決了傳統(tǒng)算法智能性與自適應(yīng)能力的不足。通過該算法的應(yīng)用增強(qiáng)了系統(tǒng)高并發(fā)處理能力,縮短了響應(yīng)時(shí)間,提升了服務(wù)器運(yùn)行的穩(wěn)定性。

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的集群負(fù)載均衡模型及其實(shí)驗(yàn)研究[D].長春：吉林大學(xué),2014.

[3] 孫秀斌,李云敏. 基于線程池技術(shù)的云閃定位遠(yuǎn)程控制軟件設(shè)計(jì)[J]. 測控技術(shù),2014,33(11):100-103.

[4] 孟凡彥,陳嘉. 基于線程池技術(shù)DHCP服務(wù)器的設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用研究,2005,22(12):258-260.

[5] 崔慎智,陳志泊.基于多代理和多優(yōu)先隊(duì)列的短信實(shí)時(shí)并發(fā)算法[J].計(jì)算機(jī)工程,2011,37(3):278-283.

[6] 鄭嘯,羅軍舟,宋愛波.基于Agent和蟻群算法的分布式服務(wù)發(fā)現(xiàn)[J].軟件學(xué)報(bào),2010,21(8):1795-1809.

[7] 徐傳福,車永剛,王正華,等.基于并行模擬的多核集群系統(tǒng)性能預(yù)測和分析[J].國防科技大學(xué)學(xué)報(bào),2010,32(5):62-68.

[8] 朱曉敏,陸佩忠. 異構(gòu)集群系統(tǒng)中安全關(guān)鍵實(shí)時(shí)應(yīng)用調(diào)度研究[J]. 計(jì)算機(jī)學(xué)報(bào),2010,33(12):2364-2377.

[9] 李軍鋒,何明昕.高并發(fā)Web航空票務(wù)秒殺系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(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] 李炯,羅光春,陳浩然. 基于排隊(duì)理論的自適應(yīng)負(fù)載均衡算法的研究[J]. 四川大學(xué)學(xué)報(bào):自然科學(xué)版,2009,46(4):929-933.

[12] 皇甫寧.基于內(nèi)容的負(fù)載均衡技術(shù)的研究與實(shí)現(xiàn)[D].廣州:華南理工大學(xué),2013.

[13] 戴藝,蘇金樹,孫志剛,等.基于流映射的負(fù)載均衡調(diào)度算法研究[J].計(jì)算機(jī)學(xué)報(bào),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—)，男，上海，碩士，講師，研究方向?yàn)樾盘?hào)采集與處理、智能儀器儀表檢測技術(shù)等.

TP301.6

A

1002-4956(2015)12- 0063- 03