一種實(shí)用的負(fù)載均衡算法

在自動系統(tǒng)維護(hù)和故障恢復(fù)支持技術(shù)方面，整個系統(tǒng)都有故障檢測設(shè)備來完成故障檢測和修復(fù)任務(wù)。實(shí)時收集系統(tǒng)狀態(tài)信息，為評估系統(tǒng)性能、確定和修復(fù)系統(tǒng)故障時的操作提供依據(jù)。因此，故障檢測設(shè)備可以進(jìn)行集中管理。集中管理有很多優(yōu)點(diǎn)：簡單、高效、容易實(shí)施，可以引用許多實(shí)際應(yīng)用。然而，由于系統(tǒng)的強(qiáng)大問題，這是中央管理難以避免的瓶頸。當(dāng)中央管理系統(tǒng)中只有一個管理者，如果經(jīng)理出現(xiàn)故障，整個系統(tǒng)的功能就會喪失。事實(shí)上，大多數(shù)系統(tǒng)都是易于損壞系統(tǒng)和要求高可靠的系統(tǒng)。為了盡可能地確保系統(tǒng)的不同功能正常運(yùn)行，并盡量減少錯誤的影響，以便在集中系統(tǒng)中引入分布式機(jī)制。要在集中式管理系統(tǒng)中引入分布式機(jī)制,就必須解決兩個問題——選舉和負(fù)載均衡.選舉(Election)是分布式系統(tǒng)中的一種常用的計(jì)算類型,它從進(jìn)程集中選出一個進(jìn)程執(zhí)行特別的任務(wù).應(yīng)用到具體系統(tǒng)中,利用選舉算法,在集中式管理者出現(xiàn)故障時,選舉產(chǎn)生系統(tǒng)中性能最優(yōu)的節(jié)點(diǎn)替代管理者.負(fù)載均衡(LoadBalancing)是分布式調(diào)度策略中的重要部分,負(fù)責(zé)通過進(jìn)程遷移在處理機(jī)間分配系統(tǒng)工作負(fù)載,負(fù)載均衡的目標(biāo)是為處理機(jī)透明地分配負(fù)載,以達(dá)到最好的計(jì)算性能并能滿足用戶性能期望.為了實(shí)現(xiàn)在故障檢測設(shè)備失效后將故障檢測設(shè)備上的任務(wù)均衡到分布式系統(tǒng)中的其他節(jié)點(diǎn)上,繼續(xù)完成故障檢測與修復(fù)任務(wù),本文提出了一種負(fù)載均衡算法.1負(fù)載平衡簡要描述1.1負(fù)載平衡分類負(fù)載均衡分為靜態(tài)負(fù)載均衡和動態(tài)負(fù)載均衡兩大類.任務(wù)分配原則根據(jù)系統(tǒng)先驗(yàn)知識做出決策,而忽略系統(tǒng)當(dāng)前的負(fù)載狀況,經(jīng)常用于任務(wù)比較確定的情況.它的算法目標(biāo)是調(diào)度一個任務(wù)集合,使它們在目標(biāo)處理機(jī)上有最小的執(zhí)行時間,過程中要考慮計(jì)算開銷和通信開銷.在綜合各種因素的基礎(chǔ)上,進(jìn)行合理的任務(wù)劃分和任務(wù)分配.動態(tài)負(fù)載均衡并不考慮靜態(tài)負(fù)載均衡,一個是測定一個負(fù)載均衡時一個過程根據(jù)系統(tǒng)當(dāng)前的負(fù)載狀態(tài)進(jìn)行負(fù)載分配策略,主要用于任務(wù)不確定的情況.相對于靜態(tài)負(fù)載均衡,它有更大的靈活性和針對性,可根據(jù)當(dāng)前的負(fù)載狀態(tài)有目的的進(jìn)行負(fù)載分配,臨時決定每個任務(wù)的執(zhí)行過程.但收集,存儲,分析系統(tǒng)的狀態(tài)信息帶來一定的額外開銷.1.2負(fù)載均衡算法負(fù)載均衡系統(tǒng)由兩部分組成:負(fù)載均衡遠(yuǎn)程執(zhí)行設(shè)備和負(fù)載均衡算法.負(fù)載均衡依賴于遠(yuǎn)程執(zhí)行,即將本地機(jī)器上的作業(yè)遷移到遠(yuǎn)程輕載機(jī)器上執(zhí)行,這依賴于遠(yuǎn)程執(zhí)行設(shè)備的支持.負(fù)載均衡算法使用系統(tǒng)狀態(tài)信息(各節(jié)點(diǎn)上的負(fù)載)進(jìn)行負(fù)載分配決策.其組成包含四個部分:(1)轉(zhuǎn)移策略:決定節(jié)點(diǎn)是否處于適合參加任務(wù)轉(zhuǎn)移的狀態(tài).即決定節(jié)點(diǎn)是任務(wù)的發(fā)送者還是任務(wù)的接收者.(2)選擇策略:決定哪個任務(wù)應(yīng)該轉(zhuǎn)移.(3)定位策略:決定把選擇的作業(yè)轉(zhuǎn)移到哪個節(jié)點(diǎn)上執(zhí)行.(4)信息策略:負(fù)責(zé)收集系統(tǒng)的狀態(tài)信息.1.3影響負(fù)荷平衡的主要因素(1)分布式遠(yuǎn)程執(zhí)行主機(jī)的選擇需要考慮基地作業(yè)遠(yuǎn)程執(zhí)行時,它進(jìn)入系統(tǒng)的節(jié)點(diǎn)是基地節(jié)點(diǎn).為了維持遠(yuǎn)程執(zhí)行時的透明性,一個作業(yè)遠(yuǎn)程執(zhí)行時,需要訪問基地節(jié)點(diǎn)的文件系統(tǒng),對于有大量文件操作的作業(yè),性能將要大大降低.(2)小進(jìn)程和短域監(jiān)控系統(tǒng)性能比較大部分分布式系統(tǒng)使用CPU隊(duì)列長度作為負(fù)載指標(biāo),但該指標(biāo)沒有區(qū)分進(jìn)程的性質(zhì)和大小.一個大進(jìn)程對資源的占用量及運(yùn)行時間可能比幾個小進(jìn)程占用的總和還多,而且CPU類作業(yè)和I/O類作業(yè)對資源的使用情況也大不相同,長的I/O類作業(yè)占用很少的CPU周期,而一個短的CPU類作業(yè)可能占用全部CPU.(3)混合類監(jiān)控類從進(jìn)程占用資源來看,進(jìn)程可分為三類:CPU類和I/O類,還有混合類(CPU類加I/O類),負(fù)載均衡需要遷移大量占用CPU資源的作業(yè).短作業(yè)的遷移是無效的,而且浪費(fèi)大量的轉(zhuǎn)移開銷.2新的負(fù)載補(bǔ)償算法2.1混合式負(fù)載均衡算法此算法是對故障檢測設(shè)備的任務(wù)模塊集進(jìn)行負(fù)載均衡,因?yàn)楣收蠙z測設(shè)備的任務(wù)集是一個確定的集合,所以本算法有靜態(tài)負(fù)載均衡特征.但參與任務(wù)分配的各個節(jié)點(diǎn)的狀態(tài)是時刻在變化的,所以本算法又含有動態(tài)負(fù)載均衡的特性.因此,本系統(tǒng)的負(fù)載均衡算法為混合式負(fù)載均衡算法.2.2該算法的主要內(nèi)容2.2.1n-#設(shè)定n,r本系統(tǒng)的網(wǎng)絡(luò)模型是一個星型,故障檢測設(shè)備和各節(jié)點(diǎn)機(jī)通過交換機(jī)互聯(lián),故障檢測設(shè)備是系統(tǒng)的領(lǐng)導(dǎo)者,采用集中式管理方式.所以提出一個含有控制中心(CtrlCenter)的系統(tǒng)概念模型,定義如下:ControlCenter(N,R)其中:N是具有相同特性的數(shù)據(jù)元素的集合,若N只有一個數(shù)據(jù)元素,則R為空集,否則R是N上某個二元關(guān)系H的集合.H描述如下:(1)在任意時刻,N中總是存在唯一的稱為控制中心的數(shù)據(jù)元素CtrlCenter,它在關(guān)系H下無前驅(qū).(2)若N-{CtrlCenter}≠?,則存在N-{CtrlCenter}的一個劃分N1,N2,…,Nm(m>0),對任意一對j,k(j≠k),(1≤j,k≤m),有Nj∩Nk=?且對于任意的i(1≤i≤m),唯一存在數(shù)據(jù)元素Xi∈Ni,有<CtrlCenter,Xi>∈H.2.2.2負(fù)載指數(shù)的量化(1)定義故障檢測設(shè)備性能集N={Ni|p(Ni)}其中:p(Ni)=TURE表示Ni是具有故障檢測設(shè)備能力的節(jié)點(diǎn).b.定義任務(wù)集T={Tk|Tk為故障檢測設(shè)備中獨(dú)立的任務(wù)模塊}.c.定義性能集Fk={Fm|Fm為Tk模塊所采集的性能數(shù)據(jù)元素}.Fk∈T(即每個任務(wù)塊中包含多個性能數(shù)據(jù)元).(2)基于量化的負(fù)載均衡算法負(fù)載指標(biāo)是負(fù)載的度量標(biāo)準(zhǔn),即用什么去度量節(jié)點(diǎn)機(jī)的負(fù)載.負(fù)載指標(biāo)的選定,是動態(tài)負(fù)載均衡中應(yīng)該首先解決的問題.目前已被研究和使用的主要負(fù)載指標(biāo)有:資源隊(duì)列長度,資源利用率,進(jìn)程剩余時間,可用內(nèi)存大小,上下文切換的頻率,進(jìn)程的通信量及上述指標(biāo)的組合.由于本系統(tǒng)中的節(jié)點(diǎn)集N和任務(wù)集T都是已知的,這樣,使用量化的方法就可以確定系統(tǒng)和任務(wù)的負(fù)載情況.用定量的方法表示系統(tǒng)和任務(wù)的負(fù)載,通過數(shù)字的比較來實(shí)現(xiàn)負(fù)載均衡算法中的轉(zhuǎn)移策略.(3)節(jié)點(diǎn)系統(tǒng)負(fù)載能力量化量化單位(λ):將最小任務(wù)(Tmin)經(jīng)量化函數(shù)f變換后可得到,即f(Tmin)=λ任務(wù)集T的量化:f(T)=f(T1)+f(T2)+…+f(Tk)=A*λ(定值)節(jié)點(diǎn)i整體負(fù)載能力量化:f(Ni)=Ri*λ(定值)節(jié)點(diǎn)i當(dāng)前負(fù)載情況量化:f(Fi1,Fi2,…,Fim)=αi*λ(隨時間變化而變化)節(jié)點(diǎn)i當(dāng)前負(fù)載能力量化:LC(Ni)=Riλ-αiλ=(Ri-αi)λ全系統(tǒng)當(dāng)前負(fù)載能力量化:LC=Σ(Ri-αi)λ2.2.3負(fù)載均衡控制程序(1)負(fù)載均衡過程(見圖1)①故障檢測設(shè)備崩潰,調(diào)用選舉算法(Election),選出控制中心ContrlCenter(Nc).Nc接替故障檢測設(shè)備的工作,作為系統(tǒng)集中式管理的領(lǐng)導(dǎo)者.②Nc執(zhí)行負(fù)載均衡初始化程序(LB_INIT_proc()).該程序檢測領(lǐng)導(dǎo)者是否能執(zhí)行全部任務(wù)集T.如果能就一次性分配給它讓它執(zhí)行,不能則按其能力分配一部分給它,其他任務(wù)均衡到有能力執(zhí)行的節(jié)點(diǎn)上執(zhí)行.③執(zhí)行通用負(fù)載均衡算法程序(CLBA).采用循環(huán)判斷機(jī)制,每隔一個周期T,檢測系統(tǒng)各節(jié)點(diǎn)的負(fù)載情況,對已分配任務(wù)的超載節(jié)點(diǎn)進(jìn)行負(fù)載均衡.通過系統(tǒng)負(fù)載的量化值,并結(jié)合定位策略實(shí)現(xiàn)負(fù)載均衡.④異常情況處理程序.為了提高系統(tǒng)的健壯性,在通用負(fù)載均衡算法執(zhí)行期間,要對出現(xiàn)的異常情況進(jìn)行處理,保證算法的正確性和健壯性.異常處理情況:a.領(lǐng)導(dǎo)者(CtrlCenter)崩潰:啟動選舉算法,同時結(jié)束所有已分配任務(wù)節(jié)點(diǎn)上的任務(wù),再執(zhí)行負(fù)載均衡算法.b.執(zhí)行任務(wù)Tk的節(jié)點(diǎn)崩潰:領(lǐng)導(dǎo)者根據(jù)時延,可以判斷出某個已分配任務(wù)的節(jié)點(diǎn)崩潰,根據(jù)系統(tǒng)狀態(tài)表中的信息,選出一個節(jié)點(diǎn)執(zhí)行任務(wù)Tk.c.全系統(tǒng)大部分節(jié)點(diǎn)超載:即全系統(tǒng)負(fù)載能力(LC)低于任務(wù)集T要求的負(fù)載時(即∑(Ri-αi)λ<A*λ),可以先通過硬件發(fā)出警報(bào),然后啟動一個最小的最能體現(xiàn)計(jì)算機(jī)負(fù)載能力的任務(wù)Tk.等到全系統(tǒng)負(fù)載能力高于任務(wù)集T要求的負(fù)載時,再根據(jù)各節(jié)點(diǎn)的負(fù)載情況啟動剩下的任務(wù).2.3不同策略的實(shí)現(xiàn)方法(1)接收節(jié)點(diǎn)的任務(wù)均衡根據(jù)系統(tǒng)各負(fù)載的量化值確定閾值,當(dāng)系統(tǒng)負(fù)載超過自身閾值時,就將其上分配的任務(wù)均衡到其他節(jié)點(diǎn)上,但要保證接收節(jié)點(diǎn)執(zhí)行遷移過來的任務(wù)后系統(tǒng)負(fù)載不超過自身閾值.通過這種方式來確定接受者和發(fā)送者.(2)任務(wù)集的生成可以選擇大任務(wù)也可以選擇小任務(wù).如選擇大任務(wù)遷移,則此系統(tǒng)在接下來的一段時間內(nèi)應(yīng)該是比較穩(wěn)定的.如轉(zhuǎn)移小任務(wù),則此系統(tǒng)在未來的一段時間內(nèi)有可能再次需要負(fù)載均衡.一種簡單的方法是,在設(shè)計(jì)任務(wù)集T時,使各個任務(wù)模塊的負(fù)載值相當(dāng),這樣就可以隨機(jī)遷移任務(wù),簡化算法.(3)分布式分散式方案也就是搜索策略,即搜索適合執(zhí)行遷移的任務(wù)節(jié)點(diǎn).有兩種策略可選:集中式和分散式.在集中式方案中,負(fù)載均衡的任務(wù)盡量集中在某一個或幾個節(jié)點(diǎn)上,這樣有利于任務(wù)集的集中管理,但這幾個節(jié)點(diǎn)的負(fù)載相對較重,可能引起頻繁負(fù)載遷移.在分散式方案中任務(wù)盡量分配在系統(tǒng)中的各個節(jié)點(diǎn)上,這樣每個節(jié)點(diǎn)的額外負(fù)載相對較輕,不會引起頻繁的負(fù)載遷移.(4)負(fù)載信息交換t負(fù)載信息交換的頻率是要考慮的,有周期性的和異步的兩種方式.異步的又可以分為按需求驅(qū)動和按變化驅(qū)動.由于本系統(tǒng)有一個控制中心(CtrlCenter)集中管理,所以采用周期性的負(fù)載信息交換方式,即每隔周期T各個任務(wù)將采集的系統(tǒng)節(jié)點(diǎn)性能值發(fā)送給控制中心.所以信息交換的頻率也是考慮的重點(diǎn).周期過短,會產(chǎn)生大量無用的信息交換,占用網(wǎng)絡(luò)資源.周期過長,則有可能錯過負(fù)載均衡的最佳時期.2.4節(jié)點(diǎn)復(fù)雜度分析假設(shè)負(fù)載均衡算法的周期是T,有N個節(jié)點(diǎn),n個任務(wù)元,且每個任務(wù)元的執(zhí)行時間均為t.由以上假設(shè)可知:T>nt+τ(τ為負(fù)載均衡執(zhí)行時間)時間復(fù)雜度:T(n)=Ο(f(n))(f(n)依據(jù)任務(wù)元在節(jié)點(diǎn)集中的分布來確定,最大為n)空間復(fù)雜度:S(n)=Ο(N)由于控制中心需要每隔T(s)記錄各個節(jié)點(diǎn)的性能指標(biāo)值,即要在存儲器中對N個節(jié)點(diǎn)進(jìn)行記錄,所以空間復(fù)雜度與節(jié)點(diǎn)個數(shù)成正比.3模擬練習(xí)3.1opnet的程序網(wǎng)絡(luò)仿真軟件通過在計(jì)算機(jī)上建立一個虛擬的網(wǎng)絡(luò)平臺,來實(shí)現(xiàn)真實(shí)網(wǎng)絡(luò)環(huán)境的模擬,網(wǎng)絡(luò)技術(shù)開發(fā)人員在這個平臺上不僅能對網(wǎng)絡(luò)通信、網(wǎng)絡(luò)設(shè)備、協(xié)議、以及網(wǎng)絡(luò)應(yīng)用進(jìn)行設(shè)計(jì)研究,還能對網(wǎng)絡(luò)的性能進(jìn)行分析和評價(jià).另外,仿真軟件所提供的仿真運(yùn)行和結(jié)果分析功能使開發(fā)人員能快速、直觀的得到網(wǎng)絡(luò)性能參數(shù),為優(yōu)化設(shè)計(jì)或決策提供更便捷、有效的手段.因此,運(yùn)用網(wǎng)絡(luò)仿真軟件對網(wǎng)絡(luò)協(xié)議、算法等進(jìn)行仿真已經(jīng)成為計(jì)算機(jī)網(wǎng)絡(luò)通信研究中必不可少的一部分.OPNET是一種優(yōu)秀的網(wǎng)絡(luò)仿真和建模的工具,支持面向?qū)ο蟮慕７绞?并提供圖形化的編輯界面,更便于用戶使用.它強(qiáng)大的功能和全面性幾乎可以模擬任何網(wǎng)絡(luò)設(shè)備、支持各種網(wǎng)絡(luò)技術(shù),除了能夠模擬固定通信模型外,OPNET的無線建模器還可用于建立分組無線網(wǎng)和衛(wèi)星通信網(wǎng)的模型.同時,OPNET在新網(wǎng)絡(luò)的設(shè)計(jì)以及對現(xiàn)有網(wǎng)絡(luò)的分析方面都有卓越表現(xiàn).它為通信協(xié)議和路由算法的研究提供與真實(shí)網(wǎng)絡(luò)相同的環(huán)境.此外,功能完善的結(jié)果分析器為網(wǎng)絡(luò)性能的分析提供了有效又直觀的工具.3.2節(jié)點(diǎn)負(fù)載模擬(1)系統(tǒng)建模:本仿真過程為通用負(fù)載均衡算法(CLBA).初始狀況為leader全部執(zhí)行任務(wù)集,當(dāng)系統(tǒng)負(fù)載超過99時進(jìn)行負(fù)載均衡.見圖2.(2)系統(tǒng)各節(jié)點(diǎn)負(fù)載模擬:使用均值為40的Poisson分布加上概率為0.005的Bernoulli分布.見圖3.(3)任務(wù)集模擬:任務(wù)集中有4個任務(wù),每個任務(wù)