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

2020-09-18 11:44:02孟利民周立鵬

高技術(shù)通訊 2020年8期

周磊孟利民周立鵬蔣維

(*浙江工業(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ù)

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ù)。