一種多服務(wù)器集群的自適應(yīng)負(fù)載均衡算法

一種多服務(wù)器集群的自適應(yīng)負(fù)載均衡算法

0自適應(yīng)負(fù)載均衡算法根據(jù)工作量，及時(shí)調(diào)整負(fù)荷平衡算法是研究自適應(yīng)負(fù)荷平衡算法的核心內(nèi)容?？蓴U(kuò)展性及高可用性Web服務(wù)器集群負(fù)載均衡的研究工作,通常假設(shè)任務(wù)分配服從指數(shù)分布,但當(dāng)工作負(fù)載和服務(wù)流程變化較大時(shí)性能較差。分析獲得的負(fù)載請(qǐng)求分布情況,有助于平衡后續(xù)到達(dá)的請(qǐng)求在Web服務(wù)器集群中各個(gè)服務(wù)器之間的負(fù)載。但某些特殊事件可能改變Web服務(wù)器的請(qǐng)求到達(dá)率、文件流行度,服務(wù)器要花費(fèi)較大的代價(jià)進(jìn)行調(diào)整。自適應(yīng)負(fù)載均衡算法應(yīng)能根據(jù)工作負(fù)載特征的變化迅速調(diào)整其平衡參數(shù),以實(shí)現(xiàn)負(fù)載均衡調(diào)度。Web服務(wù)器集群的負(fù)載請(qǐng)求到達(dá)率具有高變異性、周期性的特點(diǎn):請(qǐng)求數(shù)量在短時(shí)間內(nèi)急劇增加的突發(fā)性訪問可導(dǎo)致服務(wù)器的瞬時(shí)超載,變異在服務(wù)過程中成為影響負(fù)載均衡性能的重要因素。到達(dá)的工作負(fù)載之間存在著關(guān)聯(lián),根據(jù)已到達(dá)的工作負(fù)載在各個(gè)服務(wù)器之間的分配情況以及在單個(gè)服務(wù)器上的執(zhí)行情況,可以預(yù)測(cè)后續(xù)工作負(fù)載的請(qǐng)求到達(dá)率和請(qǐng)求大小。針對(duì)Web服務(wù)器集群的工作負(fù)載特點(diǎn),提出了基于工作負(fù)載預(yù)測(cè)的自適應(yīng)多內(nèi)存需求多時(shí)間片輪詢負(fù)載均衡算法(RR_MMMCS-A-P):當(dāng)工作負(fù)載到達(dá)率和服務(wù)特征發(fā)生變化時(shí),負(fù)載均衡算法基于監(jiān)測(cè)工作負(fù)載的動(dòng)態(tài)變化自我調(diào)整其負(fù)載參數(shù),以適應(yīng)工作負(fù)載的變化,并根據(jù)到達(dá)的工作負(fù)載預(yù)測(cè)后續(xù)工作負(fù)載的到達(dá)率和請(qǐng)求大小,實(shí)現(xiàn)服務(wù)器集群的負(fù)載均衡。1基于累積分布函數(shù)的請(qǐng)求對(duì)比負(fù)載均衡作為實(shí)時(shí)問題,其調(diào)度算法需要根據(jù)工作負(fù)載到達(dá)率和服務(wù)需求的波動(dòng)及時(shí)調(diào)整。本文通過日志分析,研究負(fù)載特征與自適應(yīng)負(fù)載均衡算法的關(guān)系。表1是根據(jù)2008年鄭州大學(xué)網(wǎng)站的日志中2月19日0時(shí)至2月19日23時(shí)的日志分析得到的數(shù)據(jù)。從圖1可以發(fā)現(xiàn),累積分布函數(shù)(CumulativeDistributionFunction,CDF)中獨(dú)立文件和傳輸文件的特點(diǎn):大多數(shù)請(qǐng)求傳輸?shù)氖切∥募?只有小部分請(qǐng)求由大文件組成。圖2分別標(biāo)出了以小時(shí)為單位的平均請(qǐng)求到達(dá)數(shù)的分布情況:當(dāng)天到達(dá)的請(qǐng)求有兩個(gè)高峰且分別在早上和中午,在兩個(gè)高峰期,平均請(qǐng)求大小相對(duì)較小。為了分析請(qǐng)求大小變化較大時(shí)對(duì)調(diào)整算法參數(shù)的影響,引入了變異系數(shù)對(duì)請(qǐng)求大小的變化情況進(jìn)行分析。變異系數(shù)的分布情況:一天當(dāng)中請(qǐng)求的變異過程有著明顯的變化,最大可達(dá)8.2以上,但是在兩個(gè)請(qǐng)求高峰期內(nèi)變異系數(shù)較小。算法參數(shù)必須對(duì)請(qǐng)求分布的快速變化迅速作出響應(yīng),才會(huì)有較好的系統(tǒng)性能。2基于工作量預(yù)測(cè)的自適應(yīng)負(fù)載平衡算法2.1自適應(yīng)負(fù)載均衡算法在一組擁有N個(gè)服務(wù)節(jié)點(diǎn)的集群中,將請(qǐng)求大小按要求分割成N個(gè)間隔,{[s0≡0,s1),[s1,s2),…,[sN-1,sN≡∞)}(1≤n≤N),第n個(gè)區(qū)間[Sn-1,Sn]內(nèi)的請(qǐng)求被分配給符合其大小要求的服務(wù)器i。N-1個(gè)界限值s1,s2,…,sN-1,直接決定著每個(gè)服務(wù)器的負(fù)載。這些邊界在每個(gè)服務(wù)器上產(chǎn)生一個(gè)統(tǒng)一要求的降速比(一個(gè)請(qǐng)求的理想響應(yīng)時(shí)間與實(shí)際響應(yīng)時(shí)間之比),為每臺(tái)服務(wù)器提供大致相同的負(fù)載。每個(gè)服務(wù)器應(yīng)被設(shè)置為承擔(dān)請(qǐng)求總字節(jié)數(shù)ˉssˉ的1/N。自適應(yīng)負(fù)載均衡算法根據(jù)每次到達(dá)系統(tǒng)的K個(gè)請(qǐng)求的分布經(jīng)驗(yàn)建立離散數(shù)據(jù)立方圖(DiscreteDataHistogram,DDH)。自適應(yīng)負(fù)載均衡算法是一個(gè)實(shí)時(shí)算法,所以每個(gè)請(qǐng)求在固定的時(shí)間內(nèi)生成一個(gè)有效的DDH。為了實(shí)現(xiàn)這一目標(biāo),使用在一個(gè)區(qū)間內(nèi)部不間斷的數(shù)F表示的向量V來描述每個(gè)DDH,如:1≤f≤F,則有f表示V[f]所決定的總字節(jié)數(shù)由在Cf-1和Cf之間的文件大小所決定,其中C是一些大于1的常數(shù)(因?yàn)镃F必須大于所請(qǐng)求的最大文件的大小,所以使用的C值越接近1,越能體現(xiàn)DDH的代表性)。因此,邊界使用該指數(shù)表示,而不是實(shí)際文件的大小。針對(duì)工作負(fù)載,難以選擇N區(qū)間邊界,使得每一個(gè)區(qū)間[Sn-1,Sn]為總負(fù)載的1/N。本文采取以下辦法解決:用概率Pn表示相關(guān)的邊界點(diǎn)Sn(1≤n≤N),表示由服務(wù)器n來完成請(qǐng)求文件大小為Sn的服務(wù),其余1-Pn的對(duì)應(yīng)文件大小的請(qǐng)求由服務(wù)器n+1來實(shí)現(xiàn),甚至是編號(hào)更靠后的服務(wù)器來實(shí)現(xiàn)。因此,邊界用一個(gè)N-1對(duì)的序列表示,[(Sn,Pn:1≤n≤N-1)]。圖3給出了該算法分析的示意圖。2.2自適應(yīng)的控制函數(shù)算法使用過去工作負(fù)載的記錄確定將來的模糊邊界。Web服務(wù)器集群根據(jù)得到的多組請(qǐng)求數(shù)為k的請(qǐng)求數(shù)組array[k],迅速調(diào)整平衡參數(shù),進(jìn)而調(diào)整模糊邊界,實(shí)現(xiàn)集群的負(fù)載均衡。當(dāng)?shù)玫揭唤M請(qǐng)求數(shù)為k的請(qǐng)求數(shù)組array[k]時(shí),每得到一個(gè)請(qǐng)求便根據(jù)其大小S和[(S1,P1),(S2,P2),…,(SN-1,PN-1)]將這個(gè)請(qǐng)求分配到一個(gè)服務(wù)器,同時(shí)將S增加到Oi[f],直到該組的k個(gè)請(qǐng)求全部進(jìn)入適當(dāng)?shù)姆?wù)器,此時(shí)計(jì)算下次使用的DDH:Ui+1=i∑j=0αi-jΟji∑j=0αi-j=(1-α)Οi+(α-αi+1)Ui1-αi+1(1)Ui+1=∑j=0iαi?jOj∑j=0iαi?j=(1?α)Oi+(α?αi+1)Ui1?αi+1(1)根據(jù)累積權(quán)重A和Ui中總的權(quán)重B調(diào)整得到新的模糊邊界,然后再得到下一組請(qǐng)求數(shù)為k的請(qǐng)求數(shù)組array[k],以此類推。自適應(yīng)負(fù)載均衡算法的基本過程用偽碼描述如下:While(!Get-k-Null)While(R<k)GettaskRfromarray[k];S=taskR;R+=1;AssignthisrequesttoaserverbasedonSand[(S1,P1),(S2,P2),…,(SN-1,PN-1)];TheindexfsatisfyingCf-1≤S≤Cf;ComputethefislogCS<=f<=logCSC;EndwhileUi+1=((1-α)Oi+(α-αi+1)Ui)/(1-αi+1);i+=1;While(1≤f≤F)EndwhileL1:While(1≤f≤F)While(A≤n*B/N)AddthefthbinoftheusedDDHtoA:EndwhileSetboundaryforservernisSn=f;Setfractionforservern:Pn=1-(A-n*B/N)/Ui[f];L2:EndwhileEndwhile算法在執(zhí)行前需初始化整體算法中的參數(shù):估計(jì)并設(shè)置N-1模糊邊界[(S1,1),(S2,1),…,(SN-1,1)];初始化i為第一批指數(shù),i=0;初始化使用的DDH為1≤f≤F,Ui[f]=0;用一個(gè)請(qǐng)求數(shù)為K的新數(shù)組初始化計(jì)數(shù)器,初始化請(qǐng)求數(shù)R=0,R是計(jì)數(shù)器;初始化得到的DDH為1≤f≤F,Oi[f]=0;初始化服務(wù)器指數(shù)n=1;初始化累積權(quán)重A=0;初始化在Ui中的總的權(quán)重B=0。k定義一組新的請(qǐng)求數(shù)組的值,Get-k-Null表示獲得賦給k的值;當(dāng)k的值非空時(shí)執(zhí)行。K在執(zhí)行過程中為一固定值,因此算法循環(huán)執(zhí)行時(shí),不斷獲得請(qǐng)求數(shù)為k的不同批次請(qǐng)求;taskR表示從請(qǐng)求數(shù)組array[k]中獲得一個(gè)請(qǐng)求任務(wù),其中0≤R<k;S表示得到的請(qǐng)求任務(wù)大小,S=taskR表示將獲得的請(qǐng)求任務(wù)的大小賦給S;指數(shù)f滿足:Cf-1≤S≤Cf,由此推導(dǎo)出f的值:logCS≤f≤logCSC；1≤f≤F(2)logCS≤f≤logCSC；1≤f≤F(2)Oi[f]為初始化得到的DDH,其值為觀察值:Oi[f]=Oi[f]+s;1≤f≤F(3)Οi作為在第i組觀測(cè)到的DDΗ的矢量描述。故Ui+1作為DDΗ獲得的分配下一批的請(qǐng)求?是將先前觀察批次獲得權(quán)重的幾何遞減函數(shù)求和得到的(式(1)所示)系數(shù)α?0≤α≤1?對(duì)控制著過去數(shù)據(jù)減少的速率起著重要作用。α=0對(duì)應(yīng)于前面提到的算法?只有最后一組數(shù)據(jù)i被用來計(jì)算Ui+1；α=1相當(dāng)于給予所有數(shù)據(jù)同等的速率。累計(jì)權(quán)重A和Ui中總的權(quán)重B為設(shè)置模糊邊界的判定條件∶Oi作為在第i組觀測(cè)到的DDH的矢量描述。故Ui+1作為DDH獲得的分配下一批的請(qǐng)求?是將先前觀察批次獲得權(quán)重的幾何遞減函數(shù)求和得到的(式(1)所示)系數(shù)α?0≤α≤1?對(duì)控制著過去數(shù)據(jù)減少的速率起著重要作用。α=0對(duì)應(yīng)于前面提到的算法?只有最后一組數(shù)據(jù)i被用來計(jì)算Ui+1；α=1相當(dāng)于給予所有數(shù)據(jù)同等的速率。累計(jì)權(quán)重A和Ui中總的權(quán)重B為設(shè)置模糊邊界的判定條件∶B=B+Ui[f],A=A+Ui[f];1≤f≤F(4)設(shè)置部分服務(wù)器概率為Pn,pn=1-(A-n·B/N)/Ui[f];1≤f≤F(5)基于多組k請(qǐng)求的工作負(fù)載的預(yù)測(cè)有助于自適應(yīng)負(fù)載均衡算法捕捉到集群的瞬時(shí)特性。如果整個(gè)工作負(fù)載歷史的信息被用來預(yù)測(cè)以后的工作負(fù)載,有助于提高自適應(yīng)負(fù)載均衡算法的性能,在一個(gè)呈幾何遞減函數(shù)的模式下:距離現(xiàn)在較近的信息比距離現(xiàn)在較遠(yuǎn)的信息更有幫助。根據(jù)k值的大小將進(jìn)入的請(qǐng)求分割成不同的批次并且根據(jù)當(dāng)前批次的DDH更新所有的DDH。2.3自適應(yīng)負(fù)載均衡算法的基本過程前面描述的自適應(yīng)負(fù)載均衡算法僅考慮靜態(tài)請(qǐng)求的過程。然而,目前Web服務(wù)器集群也要考慮動(dòng)態(tài)請(qǐng)求的過程。這種動(dòng)態(tài)請(qǐng)求的大小未知,而且可能不在cache內(nèi),因此不能根據(jù)自適應(yīng)負(fù)載均衡算法的規(guī)則被分配給服務(wù)器。本節(jié)對(duì)前面的自適應(yīng)負(fù)載均衡算法算法進(jìn)行了改進(jìn),提出了RR_MMMCS-A-P,以同時(shí)處理靜態(tài)和動(dòng)態(tài)請(qǐng)求?？紤]到動(dòng)態(tài)文件的請(qǐng)求,自適應(yīng)負(fù)載均衡算法在每個(gè)節(jié)點(diǎn)緩存較小時(shí)較優(yōu),當(dāng)緩存較大時(shí),一個(gè)請(qǐng)求可以同時(shí)在幾個(gè)服務(wù)器上;網(wǎng)卡處的隊(duì)列長度比文件位置對(duì)性能影響更大。此時(shí),調(diào)整邊界的大小,以使每個(gè)服務(wù)器有大致相同隊(duì)列長度,有助于自適應(yīng)負(fù)載均衡算法性能的提高。用Q(n)(1≤n≤N)表示服務(wù)器上當(dāng)前隊(duì)列的長度,經(jīng)過一段時(shí)間間隔T(預(yù)期連續(xù)兩次調(diào)整之間的時(shí)間)預(yù)期的隊(duì)列長度可近似為:Q′(n)=Q(n)+L(n)-Τμfs(n)(6)Q′(n)=Q(n)+L(n)?Tμfs(n)(6)其中:L(n)是在時(shí)間間隔T內(nèi),預(yù)期分配給服務(wù)器n的請(qǐng)求數(shù)目;μ是服務(wù)率;fs(n)是在這個(gè)時(shí)間間隔內(nèi)到達(dá)的請(qǐng)求的平均大小;Tμ/fs(n)為假設(shè)服務(wù)器忙的情況下在時(shí)間T內(nèi)預(yù)計(jì)處理的請(qǐng)求數(shù)目。為了計(jì)算L(n)和fs(n)?定義向量Xi、Yi+1和正整數(shù)集合E。Xi[f](e∈E)為記錄的請(qǐng)求文件大小為[Ce-1,Ce]的第i組的數(shù)量?Yi+1[e]為預(yù)測(cè)在此范圍內(nèi)的第i+1組的數(shù)量。進(jìn)入的向量Xi被初始化為0?且是可增的。向量Yi+1和Ui+1一樣?獲得此前批次的幾何遞減函數(shù)權(quán)重總和∶為了計(jì)算L(n)和fs(n)?定義向量Xi、Yi+1和正整數(shù)集合E。Xi[f](e∈E)為記錄的請(qǐng)求文件大小為[Ce?1,Ce]的第i組的數(shù)量?Yi+1[e]為預(yù)測(cè)在此范圍內(nèi)的第i+1組的數(shù)量。進(jìn)入的向量Xi被初始化為0?且是可增的。向量Yi+1和Ui+1一樣?獲得此前批次的幾何遞減函數(shù)權(quán)重總和∶Yi+1=(1-α)Xi+(α-αi+1)Yi1-αi+1(7)Yi+1=(1?α)Xi+(α?αi+1)Yi1?αi+1(7)對(duì)自適應(yīng)負(fù)載均衡算法標(biāo)注在L1和L2之間的算法改進(jìn)后的基本過程用偽碼描述如下:L1′:While(1≤n≤N)EndwhileQmax=max{Q′(1),Q′(2),…,Q′(N)};While(Qmax>TH1and(Qmax-Qmin)>TH2)While(1≤n≤N)EndwhileWhile(e∈E)While(Z>L′(n))Setboundaryforservernis:Sn=e;Setfractionforservern:Pn=1-Z/Yi[e];EndwhileEndwhileL2′:Endwhile從Yi+1開始,可以判定:L(n)=Yi+1[sn-1]?(1-pn-1)+sn-1∑e=sn-1+1Yi+1[e]+Yi+1[sn]?pn(8)L(n)=Yi+1[sn?1]?(1?pn?1)+∑e=sn?1+1sn?1Yi+1[e]+Yi+1[sn]?pn(8)fs(n)=(Ui+1[sn-1]?(1-pn-1)+sn-1∑e=sn-1+1Ui+1[e]+Ui+1[sn]?pn))/L(n)(9)時(shí)間Τ可用先前收到的請(qǐng)求數(shù)為Κ的不同批次所需時(shí)間的幾何遞減函數(shù)權(quán)重總和預(yù)測(cè)。定義兩個(gè)閾值TH1和TH2,以避免負(fù)載輕(對(duì)所有服務(wù)器Q′(n)≤TH1)或隊(duì)列的長度相近時(shí)(對(duì)任意兩個(gè)服務(wù)器|Q′(n)-Q′(m)|≤TH2)不必要的調(diào)整。設(shè)定TH1和TH2的值,如果判定違反了兩個(gè)閾值的條件,對(duì)DDH進(jìn)行第二次掃描,使預(yù)期的長度和Q″=(Ν∑n=1Q′(n))/Ν相等。由式(9)推導(dǎo)出期望的應(yīng)該分配給服務(wù)器n的請(qǐng)求為:(10)3實(shí)驗(yàn)與分析3.1節(jié)點(diǎn)負(fù)載信息在分布式系統(tǒng)模擬器上對(duì)提出的RR_MMMCS-A-P進(jìn)行了模擬實(shí)驗(yàn),實(shí)驗(yàn)參數(shù)如表2所示。系統(tǒng)有以下的規(guī)定和假設(shè):1)每一個(gè)節(jié)點(diǎn)包含全局的負(fù)載指數(shù)數(shù)據(jù)(其他節(jié)點(diǎn)的CPU和內(nèi)存負(fù)載信息),周期性地收集其他節(jié)點(diǎn)的負(fù)載信息并分發(fā)自己的負(fù)載信息。2)定位算法用來決定一個(gè)任務(wù)遷移的目的地,從分布式系統(tǒng)中找到負(fù)載最輕的節(jié)點(diǎn)。3)當(dāng)一個(gè)任務(wù)到達(dá)時(shí),給其分配內(nèi)存空間。任務(wù)的內(nèi)存門限是其請(qǐng)求內(nèi)存大小的40%。頁失效均勻分布在任務(wù)執(zhí)行期間。當(dāng)某一節(jié)點(diǎn)中任務(wù)的內(nèi)存門限值之和等于或大于允許用戶使用的內(nèi)存空間時(shí)任務(wù)以給定速率發(fā)生頁失效。4)采用發(fā)送者觸發(fā)傳輸算法。負(fù)載較重的節(jié)點(diǎn)試圖將其負(fù)載傳輸給負(fù)載較輕的節(jié)點(diǎn)。實(shí)驗(yàn)中采用了8個(gè)日志,都是在不同的時(shí)間段從工作站上收集的任務(wù)執(zhí)行數(shù)據(jù),分布在6個(gè)工作站上。內(nèi)存需求量平均值為1MB和4MB。3.2rrmmmcs-a-p算法性能基于系統(tǒng)算法和負(fù)載狀況,以任務(wù)的平均響應(yīng)時(shí)間作為衡量系統(tǒng)性能的主要指標(biāo),分別討論系統(tǒng)在表3中所示的7種算法的性能表現(xiàn)?；谏鲜?個(gè)日志進(jìn)行了模擬實(shí)驗(yàn)。從圖4、5可以看出:RR_MMMCS-A-P算法對(duì)基于CPU和CPU-MEM的負(fù)載算法都具有更好的性能,且無論是在數(shù)據(jù)密集型負(fù)載(圖5)還是在計(jì)算密集型負(fù)載(圖4)的情況下其性能總是優(yōu)于其他的負(fù)載共享算法;與基于預(yù)測(cè)的多內(nèi)存多時(shí)間片算法相比性能也有所提高(MMMCS-P);增加了自適應(yīng)性,在工作負(fù)載瞬時(shí)超載或衰減時(shí),RR_MMMCS-A-P算法都能較好地自我調(diào)整平衡參數(shù),提高了工作負(fù)載瞬時(shí)變化時(shí)系統(tǒng)的整體性能,由圖4、5可見,系統(tǒng)整體性能變化較平穩(wěn);RR_MMMCS-A-P根據(jù)已獲得的工作負(fù)載預(yù)測(cè)后續(xù)的工作負(fù)載,使得該算法相對(duì)其他算法性能有所提高。如圖4所示,當(dāng)任務(wù)的內(nèi)存需求量不大時(shí)RR-MMMCS調(diào)度算法獲得較小的性能提高,CPU-MEM-RR-MMMCS與CPU-MEM-RR相比性能提高不大。RR_MMMCS-A-P算法較好地處理節(jié)點(diǎn)之間的任務(wù)調(diào)度:縮短任務(wù)在各個(gè)節(jié)點(diǎn)上的排隊(duì)時(shí)間和減少節(jié)點(diǎn)上任務(wù)平均內(nèi)存需求量;減少了負(fù)載較重節(jié)點(diǎn)的任務(wù)排隊(duì)時(shí)間和負(fù)載較輕節(jié)點(diǎn)系統(tǒng)資源的閑置時(shí)間,RR_MMMCS-A-P算法的優(yōu)點(diǎn)得到體現(xiàn)。在數(shù)據(jù)密集型的負(fù)載情況下,RR-MMMCS算法對(duì)系統(tǒng)性能有所改善。由于增加了預(yù)測(cè)機(jī)制,RR