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

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

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