基于二部圖最大匹配的動態(tài)負(fù)載均衡算法①

周 磊 孟利民 周立鵬 蔣 維

(*浙江工業(yè)大學(xué)信息工程學(xué)院 杭州 310023) (**浙江樹人大學(xué)信息科技學(xué)院 杭州 310015)

0 引 言

隨著網(wǎng)絡(luò)技術(shù)的高速發(fā)展，互聯(lián)網(wǎng)服務(wù)已經(jīng)成為日常生活中不可或缺的部分。由于互聯(lián)網(wǎng)用戶的爆發(fā)式增長，服務(wù)器常常在短時間內(nèi)收到大量并發(fā)的用戶請求，若不能及時處理這些請求將影響用戶體驗，降低服務(wù)質(zhì)量。因此，單個服務(wù)器遠(yuǎn)遠(yuǎn)無法滿足大量的服務(wù)請求，聯(lián)合多個服務(wù)器的服務(wù)器集群應(yīng)運而生。如何合理地分配集群服務(wù)器的任務(wù)并滿足最大的服務(wù)需求是服務(wù)器集群需要解決的關(guān)鍵技術(shù)問題，而負(fù)載均衡是解決服務(wù)器集群難點的核心技術(shù)之一，能夠平衡集群中各個服務(wù)節(jié)點的負(fù)載，充分發(fā)揮服務(wù)器集群的性能。目前國內(nèi)外已經(jīng)提出了各種負(fù)載均衡算法[1]。其中有靜態(tài)負(fù)載均衡算法，如輪詢調(diào)度算法、加權(quán)輪詢調(diào)度算法[2]、目標(biāo)地址散列調(diào)度算法等，這類算法易于實現(xiàn)，但不考慮各個服務(wù)器節(jié)點的負(fù)載狀態(tài)，容易導(dǎo)致負(fù)載不均衡；有動態(tài)負(fù)載均衡算法[3,4]，如最小連接數(shù)算法、一致性哈希算法[5]、動態(tài)反饋算法[6]等，這類算法沒有考慮服務(wù)器間的性能差異和任務(wù)請求的大小，不能準(zhǔn)確地判斷服務(wù)器真實的負(fù)載狀態(tài)。動態(tài)負(fù)載均衡算法注重于服務(wù)器負(fù)載狀態(tài)的計算和反饋，文獻[7]提出一種基于排隊論綜合指標(biāo)評估的動態(tài)負(fù)載均衡算法，采用服務(wù)器M/M/1排隊模型，以任務(wù)的平均排隊時長和平均等待時長來計算負(fù)載，但其計算需花費較多時間，具有一定的延后性。文獻[8]提出了一種改進的流媒體集群動態(tài)負(fù)載均衡調(diào)度算法，通過集群節(jié)點任務(wù)數(shù)變化量動態(tài)修改服務(wù)器負(fù)載的反饋周期，并按服務(wù)器負(fù)載狀況進行分類，但當(dāng)反饋周期過小時，服務(wù)器將頻繁計算負(fù)載，增加服務(wù)器壓力。在異構(gòu)網(wǎng)絡(luò)應(yīng)用中，文獻[9]提出了一種基于模糊控制的負(fù)載均衡決策機制，用于避免異構(gòu)網(wǎng)絡(luò)中頻繁切換。文獻[10]提出了一種基于接入選擇和業(yè)務(wù)轉(zhuǎn)移的異構(gòu)網(wǎng)絡(luò)動態(tài)負(fù)載均衡機制，同時提高系統(tǒng)利用率和負(fù)載均衡性。還有注重任務(wù)調(diào)度的遺傳算法、模擬退火算法[11]、粒子群算法[12]等，這類算法實現(xiàn)較為復(fù)雜，且容易陷入局部最優(yōu)解。文獻[13]提出一種基于遺傳算法的負(fù)載均衡機制，引入了投資組合Mean-Variance模型來設(shè)置服務(wù)集群中節(jié)點利用率的權(quán)重，以最小化任務(wù)完成時間為條件來獲得最優(yōu)的權(quán)值向量，即為每個服務(wù)器的資源利用率分配權(quán)值從而得到更有效的組合適應(yīng)度函數(shù)，但其計算效率一般，對服務(wù)器的響應(yīng)時間有一定的影響。

影響負(fù)載均衡算法性能的關(guān)鍵在于如何動態(tài)地將任務(wù)均衡地分配至各個服務(wù)器節(jié)點，因此本文提出了一種基于二部圖最大匹配的動態(tài)負(fù)載均衡算法。二部圖最大匹配[14]是指二部圖中不相鄰的邊組成的集合中含邊數(shù)最多的集合，常用于解決任務(wù)指派、資源分配[15]、數(shù)據(jù)匹配[16]等問題。在服務(wù)器集群系統(tǒng)中，管理服務(wù)器按照一定的機制將任務(wù)隊列中的任務(wù)分配給集群中的各個服務(wù)器節(jié)點，這就是可用二部圖最大匹配解決的現(xiàn)實應(yīng)用場景之一。本文算法以服務(wù)器和任務(wù)作為圖頂點的子集X和Y，先預(yù)計任務(wù)的任務(wù)量和期望完成任務(wù)所需的時間，并采用由服務(wù)器反饋得到的任務(wù)量與任務(wù)實際完成時間的比值作為服務(wù)器的負(fù)載指標(biāo)[17]，若任務(wù)預(yù)計的任務(wù)量與服務(wù)器負(fù)載指標(biāo)的比值小于期望完成任務(wù)所需的時間，則將該任務(wù)頂點與服務(wù)器頂點相連作為圖的邊，由此得到服務(wù)器與任務(wù)的二部圖，再采用Edmonds的匈牙利算法[18]求該二部圖的最大匹配，然后將任務(wù)發(fā)送給匹配到的服務(wù)器，從而動態(tài)地實現(xiàn)任務(wù)的調(diào)度和服務(wù)器的負(fù)載均衡。

1 負(fù)載均衡算法調(diào)度模型

本文提出的基于二部圖最大匹配的動態(tài)負(fù)載均衡算法的系統(tǒng)框架如圖1所示。整個系統(tǒng)主要由管理服務(wù)器和服務(wù)器集群組成。其中服務(wù)器集群中的服務(wù)器用于執(zhí)行任務(wù)，并計算自身的負(fù)載指標(biāo)返回給管理服務(wù)器。管理服務(wù)器可分為4個模塊，分別是任務(wù)分配模塊、任務(wù)預(yù)估模塊、負(fù)載指標(biāo)接收模塊和計算模塊。負(fù)載指標(biāo)接收模塊負(fù)責(zé)接收服務(wù)器反饋的負(fù)載指標(biāo)，并更新當(dāng)前保存在管理服務(wù)器的服務(wù)器集群負(fù)載信息。任務(wù)預(yù)估模塊負(fù)責(zé)預(yù)計待匹配任務(wù)的任務(wù)量和期望完成任務(wù)所需的時間。計算模塊根據(jù)各個服務(wù)器的負(fù)載指標(biāo)以及任務(wù)的任務(wù)量和期望完成時間，構(gòu)建服務(wù)器與任務(wù)之間的二部圖并求其最大匹配。任務(wù)分配模塊按照由計算模塊返回的匹配結(jié)果將任務(wù)分配給各個服務(wù)器。

圖1 基于二部圖最大匹配的動態(tài)負(fù)載均衡算法系統(tǒng)框架

服務(wù)器每執(zhí)行一個任務(wù)，將記錄該任務(wù)的任務(wù)量r，任務(wù)開始時間tstart和任務(wù)完成時間tend，并由式(1)得到服務(wù)器當(dāng)前負(fù)載指標(biāo)v。

(1)

服務(wù)器負(fù)載指標(biāo)代表服務(wù)器完成任務(wù)的速率，與常見算法采用中央處理器(CPU)空閑率、內(nèi)存空閑率等多參數(shù)計算負(fù)載指標(biāo)相比，降低了服務(wù)器負(fù)載計算的復(fù)雜度，且更直接地反映了當(dāng)前服務(wù)器的負(fù)載狀態(tài)。若v越大，則說明服務(wù)器的負(fù)載較低，能更快地完成任務(wù)；若v越小，則說明服務(wù)器的負(fù)載較大，完成任務(wù)需要消耗更多的時間。那么服務(wù)器集群的負(fù)載指標(biāo)平均值為

(2)

其中，n為集群中服務(wù)器數(shù)量。由此可以得到各個服務(wù)器負(fù)載指標(biāo)的方差σ2：

(3)

方差σ2越小，說明服務(wù)器之間的負(fù)載越均衡。

2 負(fù)載均衡算法流程

本文算法是基于任務(wù)隊列、服務(wù)器集群和各服務(wù)器負(fù)載指標(biāo)構(gòu)建二部圖，并根據(jù)二部圖的最大匹配結(jié)果向各服務(wù)器分配任務(wù)，其總體流程圖如圖2所示。

圖2 算法流程圖

整個算法流程主要由管理服務(wù)器和服務(wù)器集群共同工作完成。首先管理服務(wù)器中維護著一個任務(wù)隊列，任務(wù)隊列中含有一定量待執(zhí)行的任務(wù)，由集合表示為Jq={J1,J2,J3,…}。服務(wù)器集群中有n臺服務(wù)器，由集合表示為S={S1,S2,S3,…,Sn}，服務(wù)器Si主要負(fù)責(zé)接收并執(zhí)行管理服務(wù)器為其分配的任務(wù)Jm。服務(wù)器Si將在任務(wù)Jm被執(zhí)行前后記錄該任務(wù)的任務(wù)量Rm，以及執(zhí)行任務(wù)的開始時間Tmstart和結(jié)束時間Tmend，同時由式(1)計算得到當(dāng)前服務(wù)器Si的負(fù)載指標(biāo)vi，并將負(fù)載指標(biāo)vi反饋至管理服務(wù)器。

管理服務(wù)器的負(fù)載指標(biāo)接收模塊中記錄著服務(wù)器集群中各個服務(wù)器的負(fù)載指標(biāo)，由集合表示為v={v1,v2,v3,…,vn}。各個服務(wù)器的初始化負(fù)載指標(biāo)可通過管理服務(wù)器向各個服務(wù)器發(fā)送一個測試任務(wù)J0獲得，其任務(wù)量為單位任務(wù)量R0，任務(wù)復(fù)雜度為C0，任務(wù)復(fù)雜度與任務(wù)實際計算循環(huán)次數(shù)相關(guān)。

管理服務(wù)器記錄各個服務(wù)器的初始化負(fù)載指標(biāo)后，從任務(wù)隊列中按順序取出與服務(wù)器數(shù)量相等的n個任務(wù)，由集合表示為J={J1,J2,J3,…,Jn}，同時通過任務(wù)預(yù)估模塊得到對應(yīng)任務(wù)的任務(wù)量為R={R1,R2,R3,…,Rn}，期望完成任務(wù)所需時間為T={T1,T2,T3,…,Tn}。那么對于任務(wù)Jm，其任務(wù)量Rm可由式(4)得到：

(4)

其中，R0為單位任務(wù)量，C0為測試任務(wù)的復(fù)雜度，Cm為任務(wù)Jm的復(fù)雜度。任務(wù)Jm的期望完成時間Tm可由式(5)得到：

(5)

其中，T0為測試任務(wù)實際運行時間，α的取值為經(jīng)驗值。

管理服務(wù)器通過任務(wù)預(yù)估模塊得到任務(wù)量R和期望完成任務(wù)所需時間為T后，根據(jù)實時記錄的服務(wù)器負(fù)載指標(biāo)v，開始構(gòu)建二部圖。一般的圖可由G={V,E}表示，其中V為圖G的頂點集合，E為圖G的邊集合，由此管理服務(wù)器以服務(wù)器集合S和任務(wù)集合J作為圖的頂點集可得無邊圖G，如圖3所示，顯然V=S∪J，E=?。

然后管理服務(wù)器對所有服務(wù)器和任務(wù)進行遍歷，對于任意一個服務(wù)器Si和一個任務(wù)Jm，可由式(6)預(yù)估服務(wù)器Si、執(zhí)行任務(wù)Jm、實際所需時間tim：

圖3 以集合S和集合J為頂點的無邊圖G

(6)

若tim≤Tm，則表示服務(wù)器Si能夠勝任任務(wù)Jm的工作，即預(yù)計服務(wù)器Si能在任務(wù)Jm的期望時間Tm內(nèi)完成該任務(wù)，并將圖G中的頂點Si和頂點Jm相連，得到一條邊e=SiJm，將e加入圖G的邊集合中，即E=E∪e；若tim>Tm，則表示以服務(wù)器Si當(dāng)前的負(fù)載狀態(tài)無法及時地完成任務(wù)，那么圖G中的頂點Si和頂點Jm不相連。上述遍歷完成后即可得到服務(wù)器S與任務(wù)J的二部圖G，如圖4所示。對于服務(wù)器Si，若與之相連的頂點較多，表示當(dāng)前該服務(wù)器負(fù)載較低，能勝任較多的任務(wù)；若與之相連的頂點較少，表示當(dāng)前該服務(wù)器負(fù)載較高，只能勝任部分任務(wù)；若沒有與之相連的頂點，表示當(dāng)前該服務(wù)器負(fù)載較高，暫時不接收任務(wù)。

圖4 服務(wù)器S與任務(wù)J的二部圖G

管理服務(wù)器得到二部圖G后，根據(jù)深度優(yōu)先的Edmonds的匈牙利算法求二部圖G的最大匹配。遍歷頂點集合S，使頂點Si依次與集合J中的頂點進行匹配，若頂點Si與頂點Jm相連，且頂點Jm還未與集合S中的其他頂點匹配，則邊e=SiJm為一條匹配邊，并開始匹配集合S的下個頂點；若頂點Si與頂點Jm相連，但頂點Jm已經(jīng)與集合S中的其他頂點匹配，則尋找其増廣路，若找到増廣路，則將増廣路的匹配邊變成未匹配邊，而未匹配邊變成匹配邊，例如找到一條増廣路Si-J1-S1-Ji，則該増廣路匹配邊S1J1變成未匹配邊，未匹配邊SiJ1和S1Ji變成匹配邊，并開始匹配集合S的下個頂點；若找不到増廣路，則頂點Si沒有匹配邊。集合S遍歷完后，所有匹配邊的集合即為二部圖G的最大匹配M={SiJm,…}。對于M中的匹配邊SiJm，表示以服務(wù)器Si當(dāng)前的負(fù)載狀況能勝任任務(wù)Jm。

管理服務(wù)器得到構(gòu)建的二部圖G的最大匹配M后，由任務(wù)分配模塊按照M中的匹配邊SiJm，將任務(wù)Jm發(fā)送至服務(wù)器Si進行執(zhí)行。若任務(wù)集合J中存在沒有匹配邊的任務(wù)，則將該任務(wù)移至任務(wù)隊列隊首，重新進行二部圖構(gòu)建和求最大匹配流程。

在整個算法流程中，構(gòu)建二部圖需要對每個服務(wù)器與每個任務(wù)之間進行判斷，因此對于n個服務(wù)器和n個任務(wù)，其時間復(fù)雜度為O(n2)。對二部圖最大匹配采用深度優(yōu)先匈牙利算法求解時，二部圖一邊有n個點，最多找到n條増廣路，若二部圖構(gòu)建完成后有x條邊，那么每條増廣路把所有邊遍歷一遍，其時間復(fù)雜度為O(nx)。而根據(jù)二部圖構(gòu)建流程，二部圖中最多存在n2條邊，因此最壞時間復(fù)雜度為O(n3)，所以整個算法流程的最高時間復(fù)雜度為O(n3)。由于服務(wù)器集群的應(yīng)用場景中服務(wù)器個數(shù)主要為一位數(shù)或兩位數(shù)，所以管理服務(wù)器能很快計算出最大匹配。

重復(fù)上述算法流程，管理服務(wù)器即可將任務(wù)隊列中的任務(wù)分配至各個服務(wù)器中執(zhí)行，同時低負(fù)載的服務(wù)器更容易匹配到任務(wù)量較大且期望時間較短的任務(wù)，高負(fù)載的服務(wù)器更容易匹配到任務(wù)量小且期望時間較長的任務(wù)，甚至不會匹配到任務(wù)，由此可以實現(xiàn)任務(wù)并發(fā)時服務(wù)器集群中各服務(wù)器間的負(fù)載均衡。

3 算法仿真與性能分析

本文采用Java語言編寫管理服務(wù)器和服務(wù)器集群的程序，系統(tǒng)采用1個管理服務(wù)器和4個服務(wù)器組成的服務(wù)器集群，服務(wù)器配置參數(shù)如表1所示。

表1 服務(wù)器配置

基于本文算法，通過向管理服務(wù)器分別發(fā)送500、1 000、1 500個任務(wù)的任務(wù)隊列，運行20 s后每隔5 s記錄服務(wù)器的負(fù)載指標(biāo)，比較不同取值對本文算法的影響，結(jié)果如圖5所示。由圖5可知，當(dāng)向管理服務(wù)器發(fā)送500個任務(wù)時，α取0.667的負(fù)載指標(biāo)方差大部分時間都低于其他取值的負(fù)載指標(biāo)方差；當(dāng)向管理服務(wù)器發(fā)送1 000個任務(wù)時，α取0.667的負(fù)載指標(biāo)方差大部分時間都低于或接近其他取值的負(fù)載指標(biāo)方差；當(dāng)向管理服務(wù)器發(fā)送1 500個任務(wù)時，20～50 s內(nèi)4種取值的負(fù)載指標(biāo)方差都變化較大，50 s后α取0.667和0.833的大部分時間都低于其他取值的負(fù)載指標(biāo)方差。

服務(wù)器分別完成500、1 000、1 500個任務(wù)所消耗的時間如表2所示。由表2可知，當(dāng)α取0.667時，服務(wù)器完成所有任務(wù)消耗時間較少。綜合圖5和表2，當(dāng)本文算法的α值取0.667時，服務(wù)器擁有較好的負(fù)載均衡度，且完成任務(wù)消耗時間較少。

表2 不同α值服務(wù)器完成任務(wù)消耗時間

以下實驗本文算法的α值均取0.667。通過向管理服務(wù)器發(fā)送500、1 000、1 500個任務(wù)的任務(wù)隊列，對常見的加權(quán)輪詢調(diào)度算法、最小連接數(shù)算法和

(a) 500個任務(wù)

(b) 1 000個任務(wù)

基于排隊論綜合指標(biāo)評估的動態(tài)負(fù)載均衡算法(以下簡稱排隊論算法)與本文算法進行仿真分析，運行20 s后每隔5 s記錄服務(wù)器的負(fù)載指標(biāo)，通過負(fù)載指標(biāo)的方差評估服務(wù)器的負(fù)載均衡情況，實驗結(jié)果如圖6所示。由圖6可知，在3個不同任務(wù)隊列的情況下，運行20 s后本文算法負(fù)載指標(biāo)的方差大部分時間都低于加權(quán)輪詢調(diào)度算法、最小連接數(shù)算法和排隊論算法，說明采用本文算法的服務(wù)器集群負(fù)載均衡度更好。

(a) 500個任務(wù)

(b) 1 000個任務(wù)

(c) 1 500個任務(wù)

3種算法完成500、1 000、1 500個任務(wù)所消耗的時間如表3所示。根據(jù)表3數(shù)據(jù)，當(dāng)任務(wù)數(shù)量較少時，由于加權(quán)輪詢算法未考慮服務(wù)器實時的負(fù)載狀態(tài)，最小連接數(shù)算法和本文算法均優(yōu)于加權(quán)輪詢算法，但此時本文算法和最小連接數(shù)算法差距不大；當(dāng)任務(wù)數(shù)量逐漸增大時，本文算法逐漸優(yōu)于最小連接數(shù)算法，消耗的時間更少。

表3 完成隊列所有任務(wù)消耗的時間

4 結(jié) 論

針對服務(wù)器集群系統(tǒng)中管理服務(wù)器調(diào)度任務(wù)的場景，本文提出了一種基于二部圖最大匹配的動態(tài)負(fù)載均衡算法，以二部圖的匹配結(jié)果作為管理服務(wù)器的調(diào)度方案。仿真實驗結(jié)果表明，該算法與加權(quán)輪詢調(diào)度算法、最小連接數(shù)算法和基于排隊論綜合指標(biāo)評估的動態(tài)負(fù)載均衡算法相比，能使服務(wù)器擁有更好的負(fù)載均衡度；而且對于相同數(shù)量的任務(wù)隊列，采用該算法的服務(wù)器集群能更快地完成所有任務(wù)。

由于通過二部圖求出的最大匹配不一定是完美匹配，于是就存在取出的任務(wù)未匹配到服務(wù)器的情況，本文算法將該任務(wù)放回任務(wù)隊列，容易導(dǎo)致該任務(wù)的響應(yīng)時間過長，今后可以在這類任務(wù)的處理上對算法進行改進和優(yōu)化；本文算法求解二部圖最大匹配的計算復(fù)雜度與服務(wù)器數(shù)量相關(guān)，當(dāng)服務(wù)器規(guī)模較大時，算法效率將下降，因此對求二部圖最大匹配的匈牙利算法的改進也是本文算法的重要優(yōu)化方向之一。