分布式環(huán)境中高效動態(tài)負載均衡策略研究

分布式環(huán)境中高效動態(tài)負載均衡策略研究

1負載均衡策略隨著計算機和網(wǎng)絡(luò)技術(shù)的發(fā)展，分布式網(wǎng)絡(luò)系統(tǒng)為用戶提供了豐富的資源集合，這使得它越來越受用和廣泛。隨著研究的深入,人們注意到在一個由網(wǎng)絡(luò)所連接起來的多計算機的分布式環(huán)境中,在某一時刻,一些計算機的負載極重,許多任務(wù)都處于等待狀態(tài),而另外一些計算機卻極為空閑。所以,采取有效的策略來平衡各節(jié)點(分布式環(huán)境中的節(jié)點機)的負載,提高整個系統(tǒng)資源的利用率及系統(tǒng)運行效率,已成為人們的研究熱點。通常,負載均衡策略由四部分組成:(1)信息收集,收集和維護系統(tǒng)負載狀態(tài)等信息;(2)選擇,哪些任務(wù)由哪一個節(jié)點來完成;(3)均衡發(fā)起,包括源主動/服務(wù)器主動策略;(4)協(xié)商,分布式系統(tǒng)中的節(jié)點間需要通過協(xié)商決定負載遷移等問題。這幾部分可以總結(jié)為四個關(guān)鍵問題,即負載的分配、負載狀況的定義、負載探測以及均衡策略。其中均衡策略尤為關(guān)鍵,它決定整個均衡負載操作的效果,從而決定整個分布式系統(tǒng)的計算效率、快速響應(yīng)能力和系統(tǒng)吞吐能力的高低。2節(jié)點生成及負載均衡負載均衡策略可以分為資源負載均衡策略和發(fā)送者、接收者啟動策略等。資源負載均衡策略中包括Bryant和Finkel提出的動態(tài)局部物理分布策略,這個策略采用啟發(fā)式方法達到負載均衡,但這種方法每個節(jié)點都要對其他節(jié)點進行遍歷,會導(dǎo)致大量系統(tǒng)內(nèi)部通信,請求消息的復(fù)雜度為O(n2);Barak和Shiloh提出的全局動態(tài)負載均衡策略,這個策略屬于協(xié)調(diào)算法,每個節(jié)點維護其他節(jié)點的負載信息,隨時更新,某一節(jié)點A負載過大時,向估計響應(yīng)時間最小的節(jié)點B遷移負載。這個策略是全局最優(yōu)的,需要獲得全局的信息,通信量依然較大,而且當(dāng)采集到過時信息時,該策略失效。發(fā)送者啟動策略是由D.L.Eager等人提出的,這個策略由創(chuàng)建任務(wù)的節(jié)點來執(zhí)行節(jié)點間的任務(wù)調(diào)度分配。至于分配給哪個鄰接節(jié)點,則主要取決于鄰接節(jié)點的負載狀態(tài),因此,該策略需要交換節(jié)點的負載信息。使用該策略時,系統(tǒng)在運行時不會被空閑節(jié)點所打擾,這一點在系統(tǒng)整個負載較低時尤其重要。但是負載過重的忙節(jié)點還要額外增加處理負載平衡調(diào)度的負擔(dān),就這一點來說顯然不太合理。M.Livny等人提出的接收者啟動策略是由空閑節(jié)點逐個向鄰接節(jié)點請求任務(wù),如果請求到任務(wù),則終止請求,否則繼續(xù)詢問下一個相鄰節(jié)點。如果所有相鄰節(jié)點都沒有滿足請求,則請求節(jié)點等待,過一段時間后再向相鄰節(jié)點發(fā)出任務(wù)請求。該策略不需要相互交換負載信息;對于大規(guī)模并行計算問題,當(dāng)每個節(jié)點均處于忙狀態(tài)時,幾乎不需要額外調(diào)度開銷;負載均衡的許多工作由空閑節(jié)點來完成,沒有給忙節(jié)點增加許多額外負擔(dān)。但是在開始和結(jié)束階段時任務(wù)數(shù)相對較少,許多任務(wù)請求會延遲忙節(jié)點的執(zhí)行,而且逐個地請求任務(wù)會給相鄰節(jié)點帶來一定的干擾。資源動態(tài)負載均衡策略雖然簡單,但是系統(tǒng)內(nèi)部通信量大,且計算復(fù)雜度比較高。發(fā)送者啟動策略適用于整個系統(tǒng)負載較低的情況下,而接受者啟動策略正好與發(fā)送者啟動策略相反,比較適合在大規(guī)模并行計算等負載較高的系統(tǒng)中使用,這些問題都可能成為提高整個分布式系統(tǒng)運行效率的瓶頸。3常態(tài)負載均衡策略針對上述問題,提出一種新的策略,即基于啟動者動態(tài)改變和閾值自適應(yīng)的動態(tài)負載均衡策略,簡稱SRLB策略。下面從分布式系統(tǒng)的結(jié)構(gòu)、動態(tài)負載均衡模型、閾值的自適應(yīng)方法以及啟動者動態(tài)改變策略四方面來解決基于SRLB策略的負載的分配、負載狀況的定義、負載探測以及均衡策略的相關(guān)問題。3.1基于道德風(fēng)險的負載探測技術(shù)分布式系統(tǒng)的結(jié)構(gòu)可以分為兩種:集中式結(jié)構(gòu)和分布式結(jié)構(gòu)。集中式結(jié)構(gòu)是由一個中心節(jié)點來收集所有節(jié)點的負載信息,每個節(jié)點都向中心節(jié)點提交負載信息,中心節(jié)點響應(yīng)各消息,因此中心節(jié)點不可避免地由于頻繁上下文切換、中斷的分發(fā)與處理而成為系統(tǒng)瓶頸。而分布式結(jié)構(gòu)不存在這樣的問題,但是分布式調(diào)度中沒有全局的負載信息,不利于進行負載的探測。由于發(fā)送者啟動策略適用于整個系統(tǒng)負載較輕的情況,需要進行均衡調(diào)度操作的概率相對較小,因此比較適合采用集中式結(jié)構(gòu),而接受者啟動策略適用于整個系統(tǒng)負載較重的情況,需要頻繁地進行均衡調(diào)度,一般使用分布式結(jié)構(gòu)。SRLB策略采用啟動者動態(tài)改變方法,即根據(jù)整個系統(tǒng)當(dāng)前的負載狀態(tài)來決定使用接受者啟動策略或發(fā)送者啟動策略,為適應(yīng)這種啟動者動態(tài)改變的方法,采用的分布式系統(tǒng)結(jié)構(gòu)綜合了集中式和分布式結(jié)構(gòu),稱之為MIXS結(jié)構(gòu),如圖1所示。MIXS結(jié)構(gòu)擁有一個集中式結(jié)構(gòu)式的總調(diào)度中心,并且它將所有節(jié)點進行分組,每一組中都包含一個組調(diào)度中心,總調(diào)度中心只與組調(diào)度中心進行負載信息的交互,而各節(jié)點向自己所屬的組調(diào)度中心提交負載信息,因此總調(diào)度中心只需要維護所有組調(diào)度中心的信息,組調(diào)度中心只需要維護本組節(jié)點的信息,需要維護的信息量大大降低了;MIXS結(jié)構(gòu)擁有信息集散節(jié)點——調(diào)度中心和組中心節(jié)點,能夠方便地進行負載的探測;為了均衡各組的負載,將N個節(jié)點分成lbN組,盡量將負載小的節(jié)點與負載大的節(jié)點劃分為一組。3.2組調(diào)度中心信息交互動態(tài)負載均衡模型是整個分布式系統(tǒng)進行負載分配、負載探測和負載調(diào)度的總藍圖。SRLB策略的動態(tài)負載均衡模型如圖2所示。在圖2的模型中,設(shè)置了通信模塊,通信模塊并不是唯一的,每一組節(jié)點都擁有一個通信模塊,各個通信模塊之間相互獨立?？傉{(diào)度中心通過通信模塊與各組的組調(diào)度中心進行信息交互。通信模塊擔(dān)當(dāng)總調(diào)度中心和組調(diào)度中心之間進行信息傳輸時的緩沖器角色,當(dāng)總調(diào)度中心將任務(wù)分配和調(diào)度信息發(fā)送給組調(diào)度中心時,如果此刻組調(diào)度中心處在忙狀態(tài),不能及時響應(yīng)總調(diào)度中心的消息,總調(diào)度中心就先將有效信息存入該節(jié)點組的通信模塊,這樣就將總調(diào)度中心需要完成的任務(wù)進行了分流,將需要等待一段時間才能完成的工作由通信模塊來完成。在總調(diào)度中心和組調(diào)度中心中含有的全局知識庫和組知識庫,它們是系統(tǒng)運行期間,對各個組和組中的各個節(jié)點的負載能力進行學(xué)習(xí)而建立起來的,如表1和表2所示。知識庫中存儲了一些通過學(xué)習(xí)得到的數(shù)據(jù),如某個時間段某個節(jié)點處理任務(wù)的速率與能力,這對提高系統(tǒng)的效率有很大的幫助。任務(wù)等待隊列是等待節(jié)點執(zhí)行的任務(wù)。當(dāng)節(jié)點的負載超過了一個閾值時,節(jié)點就將一部分任務(wù)轉(zhuǎn)到任務(wù)轉(zhuǎn)發(fā)隊列中,然后通過組調(diào)度中心節(jié)點將任務(wù)轉(zhuǎn)發(fā)給其他空閑或負載較輕的節(jié)點去執(zhí)行。3.3常用的自適應(yīng)策略在一個分布式系統(tǒng)中,任何節(jié)點都可以用一種方式來抽象地描述其處理能力,例如用P來代表該節(jié)點的能力值,而閾值是一個臨界值,令其為L(L<P),在當(dāng)前節(jié)點的實際負載E比L大時,判定為超載節(jié)點,反之為輕載節(jié)點,E與L之間存在如下函數(shù)關(guān)系:函數(shù)F(Lue0a8Eue0a8λ)表明了在超載、輕載和負載適中三種情況下L和E之間的關(guān)系,函數(shù)中λ(λ<1)為影響因子,因為在系統(tǒng)實際運行中,有一些系統(tǒng)必須運行的任務(wù),如操作系統(tǒng)的運行和網(wǎng)絡(luò)信息的維護等,這些任務(wù)也是節(jié)點實際負載的一部分,所以節(jié)點真正的任務(wù)負載小于實際負載E。當(dāng)負載閾值采用動態(tài)方法確定時,稱為自適應(yīng)方法。因為SRLB策略采用的均衡策略為動態(tài)改變的策略,所以閾值的自適應(yīng)方法不能根據(jù)均衡策略來實現(xiàn)。所以這里的閾值自適應(yīng)方法根據(jù)節(jié)點機各項資源的利用率進行分層自適應(yīng)改變,這些資源分別為CPU、內(nèi)存(Mem)、網(wǎng)絡(luò)帶寬(T)、I/O、緩沖區(qū)(SC)。稱該方法為資源分層閾值自適應(yīng)方法。分層結(jié)構(gòu)如表3所示,該分層方式以及硬件使用率是依據(jù)組成計算機的各個主要硬件之間不同的性能標(biāo)準(zhǔn)制定的。由于該標(biāo)準(zhǔn)是硬件生產(chǎn)廠商指定的統(tǒng)一標(biāo)準(zhǔn),所以使用該標(biāo)準(zhǔn)能夠保證實驗的結(jié)果精確性和準(zhǔn)確性。表3中α為閾值動態(tài)改變因子,閾值是整個系統(tǒng)處理任務(wù)的平均能力值,α的值是通過對節(jié)點某一時間段各項資源的利用率進行綜合計算得到的。設(shè)CPU、內(nèi)存、網(wǎng)絡(luò)帶寬、I/O、緩沖區(qū)的平均利用率分別為C1、C2、C3、C4、C5,則α為:公式(1)中hk和hp分別表示當(dāng)前節(jié)點的負載量和整個系統(tǒng)的平均負載量,表3中α值是在設(shè)hk=hp的情況下得到的。α的值不能小于10%,因為α≈0?L≈0,這使得hk>L的概率幾乎為100%,系統(tǒng)頻繁地進行均衡操作,將引起緩沖區(qū)負載抖動現(xiàn)象和大量的內(nèi)部通信。通過公式(1)便實現(xiàn)了閾值變化因子α的動態(tài)改變。而通過α的動態(tài)改變可以給出節(jié)點負載狀況的定義,即表3中的State字段值,分別為:LRL(Lighter-load)、LL(Light-load)SL(Strong-load)、SRL(Stronger-load)和FL(Full-load)。根據(jù)這五種狀態(tài),動態(tài)決定采用哪一種啟動者策略。3.4作者的動態(tài)改變策略3.4.1基于主動索引方式任務(wù)的分配策略采用主動索取與調(diào)度中心發(fā)送相結(jié)合的方式。當(dāng)有一批需要完成的任務(wù)到達總調(diào)度中心時,總調(diào)度中心給每一個組調(diào)度中心發(fā)送一個任務(wù)到達的標(biāo)識F,組調(diào)度中心將F與自身的MAC地址捆綁后作為標(biāo)識G傳遞給組成員,組成員得到G后根據(jù)節(jié)點自身狀態(tài)自主決定采用主動索取方式還是調(diào)度中心發(fā)送方式。如果采用主動索引方式,就是由節(jié)點發(fā)出請求,請求的任務(wù)量由節(jié)點決定,只有在節(jié)點多次進行任務(wù)處理的任務(wù)量大小差距比較大,知識庫中學(xué)習(xí)到的數(shù)據(jù)不是很穩(wěn)定的情況下采用這種方式。如果采用調(diào)度中心發(fā)送方式,須在發(fā)送之前通過知識庫計算出每個節(jié)點機的負載潛力,計算公式如下:公式(2)中的R為平均任務(wù)量(如果將總?cè)蝿?wù)平均分配給所有節(jié)點的任務(wù)量),S為知識庫中處理能力的平均值,當(dāng)知識庫在Ti時間段的處理速率為Vi,在的情況下,令其中n為知識庫中分的時間段的數(shù)量。公式(2)中的(R/S)2表示將當(dāng)前系統(tǒng)的平均任務(wù)量作為一個影響節(jié)點負載潛力因子,因為當(dāng)總?cè)蝿?wù)量很大時,負載潛力也必須相應(yīng)地變大。δ是一個隨機小數(shù),0.8￡δ<1,作用是稍微降低節(jié)點的負載潛力,因為S的值并不是真正處理任務(wù)的能力,它還包括處理操作系統(tǒng)的進程和維持網(wǎng)絡(luò)連接等其他任務(wù),所以要稍微降低節(jié)點的負載潛力。3.4.2總調(diào)度中心優(yōu)化分配策略根據(jù)D.L.Eager等模擬實驗結(jié)果表明,當(dāng)整個任務(wù)負載較重時,接收者啟動策略效率更高,反之發(fā)送者啟動策略更高。所以SRLB采用動態(tài)的啟動者策略,設(shè)定一個資源利用率監(jiān)視器,當(dāng)整個系統(tǒng)資源利用率高時,說明系統(tǒng)的負載較重,采用接收者啟動策略,反之采用發(fā)送者啟動策略,如表3所示。策略的變換完全由總調(diào)度中心來發(fā)起,總調(diào)度中心通過對各個組調(diào)度中心發(fā)送來的資源利用率數(shù)據(jù)進行綜合分析,將分析結(jié)果與表3中的標(biāo)準(zhǔn)進行對比,從而確定系統(tǒng)是否改變策略。具體步驟如下:(1)總調(diào)度節(jié)點在分配任務(wù)時,根據(jù)任務(wù)量決定初始啟動者策略。(2)當(dāng)系統(tǒng)發(fā)生任務(wù)遷移,總調(diào)度中心給各個組調(diào)度中心發(fā)送資源利用率監(jiān)測信號,組調(diào)度中心接收信號并轉(zhuǎn)發(fā)給組成員。(3)組成員接收到信號后將各項資源的利用率發(fā)送給組調(diào)度中心,組調(diào)度中心將接收到的各個組成員的資源利用率進行匯總與分析,得到一個平均值發(fā)送給總調(diào)度中心。(4)總調(diào)度中心根據(jù)各組的資源利用率決定啟動者策略。4pc機群的劃分與任務(wù)為了得到穩(wěn)定實驗結(jié)果,在一個局域網(wǎng)環(huán)境中,由12臺不同配置(為了產(chǎn)生任務(wù)的遷移)的PC機組成的計算機機群進行實驗,其中有6臺PC機的CPU為2.0GHz,內(nèi)存大小為512MB,其中5臺作為總調(diào)度中心和組調(diào)度中心,有2臺PC機的CPU為1.7GHz,內(nèi)存大小為512MB,2臺PC機的CPU為1.7GHz,內(nèi)存大小為256MB,剩下的2臺PC機的CPU為1.0GHz,內(nèi)存大小為256MB。將PC機群分為4組,各組的PC機數(shù)量分別為4臺、3臺、2臺、2臺。實驗分3次進行,每次實驗均提交100個相互獨立的子任務(wù)。每次實驗的子任務(wù)內(nèi)容如表4所示。實驗采用發(fā)送者啟動策略、接受者啟動策略和啟動者動態(tài)改變策略分別進行,得到的實驗結(jié)果如圖3所示。由實驗結(jié)果可知,當(dāng)任務(wù)負載量適中時,三種策略的效率基本相同;當(dāng)任務(wù)負載較輕時,發(fā)送者啟動策略與啟動者動態(tài)改變策略要優(yōu)于接受者啟動策略;當(dāng)任務(wù)負載較重時,接受者啟動策略與啟動者動態(tài)改變策略要優(yōu)于發(fā)送者啟動策略?？梢?啟動