么麗穎

(黑龍江信息技術(shù)職業(yè)學(xué)院)

一種增強(qiáng)型LVS集群的動(dòng)態(tài)反饋均衡算法*

么麗穎

(黑龍江信息技術(shù)職業(yè)學(xué)院)

介紹了LVS集群系統(tǒng)，分析了負(fù)載均衡任務(wù)調(diào)度策略，在此基礎(chǔ)上，研究并設(shè)計(jì)了一種增強(qiáng)型LVS集群系統(tǒng)動(dòng)態(tài)反饋均衡算法，提出新的算法來計(jì)算集群系統(tǒng)中服務(wù)節(jié)點(diǎn)在下一個(gè)周期所能承擔(dān)的負(fù)載增量INCLi，以達(dá)到系統(tǒng)負(fù)載均衡的目的.

集群;動(dòng)態(tài)反饋;負(fù)載均衡算法

0 引言

LVS(Linux Virtual Server)集群系統(tǒng)將一組實(shí)際網(wǎng)絡(luò)服務(wù)器通過負(fù)載均衡器匯集在一起、并使用共享的存儲服務(wù)系統(tǒng)為外部網(wǎng)絡(luò)提供靈活的、實(shí)時(shí)的、高性能的服務(wù).負(fù)載調(diào)度器是LVS集群系統(tǒng)對外部網(wǎng)絡(luò)的前端機(jī)，其任務(wù)是將外部網(wǎng)絡(luò)的客戶訪問請求合理地、均衡地分配到集群中一組實(shí)際服務(wù)器上執(zhí)行，其目標(biāo)是縮短系統(tǒng)的平均響應(yīng)時(shí)間、并能充分的利用系統(tǒng)資源.對于客戶端來說，LVS集群系統(tǒng)是一個(gè)獨(dú)立的具有唯一一個(gè)IP地址的服務(wù)器，集群系統(tǒng)的結(jié)構(gòu)及任務(wù)的分配執(zhí)行對客戶端是透明的.目前，集群負(fù)載調(diào)度器一般采用以IP負(fù)載均衡技術(shù)及基于內(nèi)容請求分發(fā)技術(shù)作為基礎(chǔ)開發(fā)的動(dòng)態(tài)負(fù)載均衡任務(wù)調(diào)度策略，目的是構(gòu)建高性能、高可用、可伸縮的實(shí)時(shí)集群系統(tǒng).

1 負(fù)載均衡任務(wù)調(diào)度策略分析

負(fù)載均衡任務(wù)調(diào)度策略的優(yōu)劣在于設(shè)計(jì)采用的負(fù)載均衡調(diào)度算法的效率，負(fù)載均衡調(diào)度算法分為靜態(tài)調(diào)度算法和動(dòng)態(tài)調(diào)度算法.目前常用的靜態(tài)調(diào)度算法有輪轉(zhuǎn)調(diào)度(Round－Robin Scheduling)、加權(quán)輪轉(zhuǎn)調(diào)度(Weighted Round－Robin Scheduling)、最少連接調(diào)度(Least－Connection Scheduling)、加權(quán)最少連接調(diào)度(Weighted Least－Connection Scheduling)、短作業(yè)優(yōu)先調(diào)度(Short Job First Schedule)、優(yōu)先級調(diào)度(Priority Schedule)、Best Fit調(diào)度及 First Fit調(diào)度等.靜態(tài)調(diào)度算法的特點(diǎn)是負(fù)載均衡器上記錄每臺真實(shí)服務(wù)器(服務(wù)節(jié)點(diǎn))的負(fù)載值，負(fù)載值的計(jì)算依據(jù)服務(wù)節(jié)點(diǎn)的部分負(fù)載指標(biāo)，如CPU占用率、內(nèi)存利用率、過去一個(gè)時(shí)間段內(nèi)的平均負(fù)載及CPU運(yùn)行隊(duì)列長度等.靜態(tài)調(diào)度算的缺點(diǎn)是其調(diào)度策略不參考系統(tǒng)運(yùn)行時(shí)系統(tǒng)各項(xiàng)指標(biāo)的實(shí)時(shí)變化，致使集群系統(tǒng)各真實(shí)服務(wù)器上的實(shí)際負(fù)載與負(fù)載均衡器上所記錄的負(fù)載值有一定的誤差，最終導(dǎo)致集群系統(tǒng)各服務(wù)節(jié)點(diǎn)負(fù)載分配的不平衡，而動(dòng)態(tài)反饋負(fù)載均衡算法可以很好地解決該問題.

動(dòng)態(tài)反饋負(fù)載均衡算法的核心思想是在集群系統(tǒng)運(yùn)行一段時(shí)間之后，通過周期性的負(fù)載信息反饋來調(diào)整調(diào)度器上的記錄.

2 LVS集群系統(tǒng)動(dòng)態(tài)負(fù)載均衡算法的設(shè)計(jì)

在此，筆者研究與設(shè)計(jì)LVS集群的動(dòng)態(tài)負(fù)載均衡算法，而LVS集群系統(tǒng)采用的是集中式的負(fù)載均衡系統(tǒng)結(jié)構(gòu)，集中式的負(fù)載均衡系統(tǒng)是相對分布式負(fù)載均衡系統(tǒng)而言的.分布式負(fù)載均衡系統(tǒng)中，每個(gè)系統(tǒng)節(jié)點(diǎn)均作為負(fù)載均衡器，接收其它節(jié)點(diǎn)的負(fù)載信息，負(fù)載均衡算法的實(shí)現(xiàn)方式很靈活，但技術(shù)實(shí)現(xiàn)上相對復(fù)雜.集中式的負(fù)載均衡系統(tǒng)結(jié)構(gòu)是在前端負(fù)載調(diào)度器上實(shí)現(xiàn)調(diào)度策略的.在設(shè)計(jì)LVS集群的動(dòng)態(tài)反饋負(fù)載均衡算法之前，首先要分析和解決以下三點(diǎn)問題.

2.1 集群系統(tǒng)負(fù)載指標(biāo)研究

根據(jù)集群系統(tǒng)的應(yīng)用需求，研究服務(wù)節(jié)點(diǎn)的各項(xiàng)負(fù)載信息，最終確定部分負(fù)載信息作為負(fù)載均衡算法的負(fù)載指標(biāo)來計(jì)算負(fù)載值.外部網(wǎng)絡(luò)的客戶訪問消耗集群系統(tǒng)資源的多少和所需時(shí)間依賴于訪問的服務(wù)類型、當(dāng)前集群系統(tǒng)各服務(wù)節(jié)點(diǎn)的資源利用的情況等.負(fù)載信息主要分為兩類:系統(tǒng)輸入指標(biāo)和服務(wù)器負(fù)載指標(biāo).輸入指標(biāo)即為周期時(shí)間內(nèi)系統(tǒng)的平均負(fù)載量，可從負(fù)載調(diào)度器上獲得，在負(fù)載調(diào)度器的計(jì)數(shù)器上記錄著每個(gè)服務(wù)節(jié)點(diǎn)的連接數(shù)，例如對于服務(wù)節(jié)點(diǎn)Ni，可以收集到在T1和T2兩個(gè)時(shí)刻的連接數(shù)Ci1和Ci2，因此，可以計(jì)算得到在周期時(shí)間間隔T2－T1時(shí)間段內(nèi)Ni的連接數(shù)與集群內(nèi)n個(gè)服務(wù)節(jié)點(diǎn)收到的平均連接數(shù)的比值，即為輸入指標(biāo)Ii，如公式(1):

服務(wù)器負(fù)載指標(biāo)是指各服務(wù)節(jié)點(diǎn)的負(fù)載信息，例如CPU利用率、CPU就緒隊(duì)列長度、內(nèi)存使用情況、系統(tǒng)調(diào)用率、CPU進(jìn)程切換率等等.如何理想地選取負(fù)載信息是整個(gè)算法的基礎(chǔ)，它是任務(wù)分配優(yōu)劣的關(guān)鍵，決定著集群系統(tǒng)的性能.前人通過大量實(shí)驗(yàn)，分別提出了各自觀點(diǎn).鑒于CPU、內(nèi)存、磁盤等是系統(tǒng)的主要競爭資源，為LVS集群系統(tǒng)選取了包括服務(wù)器CPU利用率Ci，內(nèi)存使用情況Mi，磁盤使用情況Di，運(yùn)行態(tài)進(jìn)程數(shù)量Pi，1 min內(nèi)系統(tǒng)的平均負(fù)載量Ii五個(gè)負(fù)載指標(biāo).

不同負(fù)載信息對集群系統(tǒng)的影響程度是不同的，例如FTP服務(wù)對CPU處理能力及磁盤I/O速率要求較高，而HTTP服務(wù)對CPU利用率和內(nèi)存使用率要求較高，如何更好地反映負(fù)載情況，引入一組系數(shù)ki來調(diào)整不同負(fù)載指標(biāo)對系統(tǒng)的重要程度，k={0.3，0.3，0.2，0.1，0.1}，其中∑ki=1.系統(tǒng)綜合負(fù)載可以通過公式(2)計(jì)算獲得.

在系統(tǒng)運(yùn)行過程中，可以根據(jù)系統(tǒng)性能的優(yōu)劣，動(dòng)態(tài)地調(diào)整集群系統(tǒng)的配置文件來合理修正系數(shù)ki的值.

2.2 反饋調(diào)節(jié)系統(tǒng)的設(shè)計(jì)

負(fù)載調(diào)度器是周期性通過廣播信號收集各個(gè)服務(wù)節(jié)點(diǎn)的負(fù)載信息，所以負(fù)載調(diào)度器所記錄的各服務(wù)節(jié)點(diǎn)的負(fù)載信息是前一個(gè)周期的負(fù)載，而不是系統(tǒng)的當(dāng)前負(fù)載，這種“過時(shí)”的負(fù)載信息很可能導(dǎo)致系統(tǒng)負(fù)載分配的不均衡.例如，集群系統(tǒng)在某一時(shí)刻t0，負(fù)載調(diào)度器收集了各服務(wù)節(jié)點(diǎn)的負(fù)載信息，并計(jì)算得到系統(tǒng)綜合負(fù)載.如果負(fù)載調(diào)度器在下一個(gè)收集負(fù)載信息時(shí)刻t0+T到來之前的另一時(shí)刻t1(t0＜t1＜t0+T)，到達(dá)了多個(gè)訪問請求，此時(shí)系統(tǒng)只能依據(jù)負(fù)載調(diào)度器在t0時(shí)刻所收集的負(fù)載信息來分配新到達(dá)的請求，那么負(fù)載調(diào)度器會(huì)將這些請求相繼發(fā)送給t0時(shí)刻負(fù)載最輕的同一個(gè)服務(wù)節(jié)點(diǎn)上，導(dǎo)致負(fù)載分配的不均衡.

在負(fù)載調(diào)度器中記錄著各節(jié)點(diǎn)的負(fù)載信息，包括節(jié)點(diǎn)序號N、節(jié)點(diǎn)的當(dāng)前負(fù)載LOADi、節(jié)點(diǎn)剩余負(fù)載能力INCLi、節(jié)點(diǎn)權(quán)值Wi等，其中節(jié)點(diǎn)序號N和節(jié)點(diǎn)權(quán)值Wi按照降序存放在負(fù)載信息隊(duì)列中，而節(jié)點(diǎn)剩余負(fù)載能力INCLi等降序存放在冗余信息隊(duì)列中，以便于任務(wù)分配時(shí)被使用，達(dá)到負(fù)載均衡的目的.

2.2.1 通過Wi調(diào)整系統(tǒng)的負(fù)載均衡

需要對服務(wù)節(jié)點(diǎn)設(shè)定初始化權(quán)值DEFWi，通過服務(wù)節(jié)點(diǎn)的權(quán)值Wi可以調(diào)整集群的負(fù)載均衡性.

(1)負(fù)載調(diào)度器的負(fù)載查詢模塊周期地查詢節(jié)點(diǎn)權(quán)值，若不為零，則收集該節(jié)點(diǎn)的各項(xiàng)負(fù)載信息，并通過公式(2)計(jì)算出其綜合負(fù)載值;若為零，則不會(huì)收集節(jié)點(diǎn)的負(fù)載信息，負(fù)載調(diào)度器將不會(huì)分配新的任務(wù)請求到該服務(wù)節(jié)點(diǎn).LVS集群系統(tǒng)可以通過將Wi置零的方法來處理出現(xiàn)異常的節(jié)點(diǎn)，在該服務(wù)節(jié)點(diǎn)有響應(yīng)之后，再重新設(shè)置其權(quán)值.

(2)集群系統(tǒng)還可以通過加權(quán)負(fù)載均值來獲得集群的使用率，加權(quán)負(fù)載均值A(chǔ)veL可以通過公式(3)計(jì)算得到.

當(dāng)負(fù)載均值A(chǔ)veL處于70% ～85%之間時(shí)，集群系統(tǒng)的使用率高，且性能好;當(dāng)AveL小于70%時(shí)，可以適度地減少服務(wù)節(jié)點(diǎn)，節(jié)省系統(tǒng)資源;當(dāng)AveL大于85%時(shí)，必須增加服務(wù)節(jié)點(diǎn)的數(shù)目擴(kuò)大集群的規(guī)模，避免系統(tǒng)過載，以提高系統(tǒng)的性能.

(3)可以通過負(fù)載均值來調(diào)節(jié)各服務(wù)節(jié)點(diǎn)的負(fù)載均衡性，服務(wù)節(jié)點(diǎn)權(quán)值越大，分配的任務(wù)請求越多.定義公式(4)來實(shí)現(xiàn)在負(fù)載調(diào)度器上調(diào)整負(fù)載權(quán)值.

其中，k為調(diào)整步長，且0＜k＜1.通過公式(4)可以不斷調(diào)整負(fù)載均值，最終使集群系統(tǒng)負(fù)載均衡.

2.2.2 改進(jìn)算法來設(shè)定服務(wù)節(jié)點(diǎn)的處理能力

在集群系統(tǒng)中，每個(gè)服務(wù)節(jié)點(diǎn)的處理能力會(huì)影響著節(jié)點(diǎn)的負(fù)載變化，所以即使在各節(jié)點(diǎn)負(fù)載相對均衡的情況下，各節(jié)點(diǎn)可接收的任務(wù)請求的能力也會(huì)有區(qū)別.可以通過節(jié)點(diǎn)的剩余處理能力來衡量某一時(shí)刻各服務(wù)節(jié)點(diǎn)還可以接收的任務(wù)請求的負(fù)載.

負(fù)載調(diào)度器通過公式(5)可以來預(yù)測在下一個(gè)時(shí)刻每個(gè)服務(wù)節(jié)點(diǎn)可能接收到的任務(wù)請求負(fù)載.

其中，n為服務(wù)節(jié)點(diǎn)i的當(dāng)前連接數(shù).

為了達(dá)到系統(tǒng)的負(fù)載均衡，必須獲得節(jié)點(diǎn)的在下一個(gè)周期能夠承擔(dān)的最大負(fù)載增量，以防止系統(tǒng)過載.

首先，系統(tǒng)通過公式(6)計(jì)算出節(jié)點(diǎn)i在某個(gè)周期中響應(yīng)第k個(gè)任務(wù)請求時(shí)能夠提供的最大負(fù)載maxLoadk.

其中，Dk是第k個(gè)任務(wù)請求的數(shù)據(jù)量，Δtk是第k個(gè)任務(wù)請求的響應(yīng)時(shí)間，而 max(Ck，Mk，Dk，Pk，Ik)是該請求占用的最大負(fù)載利用率.

根據(jù)公式(7)可以進(jìn)一歩得到節(jié)點(diǎn)i在一個(gè)周期內(nèi)的最大平均負(fù)載利用率maxL.

其中，k取值為某一周期內(nèi)任務(wù)請求的序列號，即t≤k≤n.

從而可以求出節(jié)點(diǎn)i在下一個(gè)周期能夠承擔(dān)的負(fù)載增量，如公式(8).

由此，得出在下一個(gè)周期內(nèi)節(jié)點(diǎn)i所能承擔(dān)的最大負(fù)載增量必須小于INCLi，否則會(huì)造成該節(jié)點(diǎn)過載.

3 結(jié)論

LVS集群服務(wù)器目前應(yīng)用廣泛，其利用動(dòng)態(tài)反饋算法來達(dá)到負(fù)載均衡，以提高系統(tǒng)的整體性能.該論文在分析和研究LVS集群系統(tǒng)及動(dòng)態(tài)反饋算法的基礎(chǔ)之上，研究并設(shè)計(jì)了動(dòng)態(tài)反饋算法，并提出新的算法來計(jì)算集群系統(tǒng)中服務(wù)節(jié)點(diǎn)在下一個(gè)周期所能承擔(dān)的負(fù)載增量INCLi來設(shè)定服務(wù)節(jié)點(diǎn)的處理能力，以達(dá)到系統(tǒng)負(fù)載均衡的目的.

［1］吳培飛.用VMware構(gòu)建Linux實(shí)驗(yàn)環(huán)境.中國教育信息化:高教職教，2011(8):56 －59.

［2］馬萬濤.基于Linux服務(wù)器集群安全的探討.電腦與電信，2009(10):38－41.

［3］譚保華，查純，張德強(qiáng).基于虛擬技術(shù)和大型機(jī)硬件平臺的LINUX服務(wù)器系統(tǒng)實(shí)現(xiàn).計(jì)算機(jī)工程與設(shè)計(jì)，2009，30(5):43－45.

［4］張昊，廖建新，朱曉民.增強(qiáng)型動(dòng)態(tài)反饋隨機(jī)分發(fā)負(fù)載均衡算法.計(jì)算機(jī)工程，2007，33(4):97 －99.

［5］王曉川，葉超群，金士堯.一種基于分布式調(diào)度機(jī)制的集群體系結(jié)構(gòu).計(jì)算機(jī)工程，2002，28(3):131－133.

Dynamic Feedback Balancing Scheduling of an Advanced LVS

Yao Liying
(Heilongjing Infotech Profession College)

In this paper，the server cluster system to LVS is introduced，and task scheduling strategy of load balancing are analyzed.Based on it，the dynamic feedback balancing scheduling of an advanced LVS is designed.The new algorithm of calculating been able to bear load increment(INCLi)of the server node in cluster system at the next cycle is put forward，its purpose is getting load balancing to system.

Cluster;Dynamic feedback;The scheduling of load balancing

2011－05－11

*黑龍江省教育廳2010年度科學(xué)技術(shù)研究(指導(dǎo))項(xiàng)目“基于Linux的校園網(wǎng)服務(wù)器集群系統(tǒng)研究”的部分研究成果(11555093)

(責(zé)任編輯:季春陽)