一種基于負(fù)載預(yù)測的動態(tài)負(fù)載均衡方法

對于面向分布的實時系統(tǒng)，不同主機(jī)之間的動態(tài)排序和編程對系統(tǒng)的性能有很大影響，因此受到關(guān)注。各國研究人員對此進(jìn)行了大量的研究，提出了一系列動態(tài)負(fù)載均衡算法。所有這些方法都從某方面改進(jìn)了動態(tài)負(fù)載均衡，提高了分布式/并行系統(tǒng)的性能。但因為分布式/并行系統(tǒng)的任務(wù)在各結(jié)點動態(tài)分配生成，而各結(jié)點上的負(fù)載是不斷變化的，以上各算法多是收集結(jié)點負(fù)載的舊值或大概估計值作為任務(wù)在各結(jié)點分配的依據(jù)，不僅精確度不夠，更可能造成進(jìn)程遷移的抖動，從而導(dǎo)致算法的實用效果并不甚理想。如果能夠預(yù)先了解結(jié)點的負(fù)載變化，平衡系統(tǒng)在進(jìn)行任務(wù)分配時就有提前量，這樣可以避免因信息傳遞時延使決策信息過時而造成的某一任務(wù)在結(jié)點間來回遷移得不到執(zhí)行的情況，減少了任務(wù)再分配的發(fā)生，從而使負(fù)載均衡的性能得到較大提高。基于這一思想，我們提出了一種動態(tài)的基于負(fù)載預(yù)測的均衡方法，給出了該方法的實現(xiàn)模型和相關(guān)算法，并進(jìn)行了性能分析，最后得到了實驗結(jié)果。1基于負(fù)載時間序列模型的負(fù)載預(yù)測美國的Dinda和O’Halloran在1997年和1998年分兩次對39臺DECAlphaDUX主機(jī)進(jìn)行了長期跟蹤抽樣，獲得了大量的負(fù)載圖樣（LoadTrace）。通過對負(fù)載圖樣進(jìn)行統(tǒng)計分析，他們總結(jié)出了主機(jī)負(fù)載隨時間變化有很強(qiáng)關(guān)聯(lián)性的特性，由此Dinda和O’Halloran評估了多種線性時間序列模型應(yīng)用于大型分布式系統(tǒng)中負(fù)載預(yù)測的效果，并以此建立了RPS(ResourcePredictionSystems）。按照RPS的思想，我們構(gòu)建了HLPS(HostLoadPredictionSystem）模型，并在Linux工作站上用C++編譯實現(xiàn)了HLPS模型，這為研究基于預(yù)測的動態(tài)負(fù)載均衡提供了較好的基礎(chǔ)。2基于預(yù)測的動態(tài)負(fù)載平衡模型2.1負(fù)載均衡控制假定分布式/并行系統(tǒng)由p個結(jié)點組成，基于預(yù)測的動態(tài)負(fù)載均衡模型如圖1。人為將所有結(jié)點分為n個組，每個組固定k個結(jié)點。為了限制調(diào)度的注意點，設(shè)定組間不進(jìn)行信息交換和任務(wù)遷移。這時為了保證每個組獲得相近的處理性能，避免較大的組間不均衡現(xiàn)象，在人為分組時盡量使每個組的k個結(jié)點在整體上具有相近的處理能力。若系統(tǒng)的結(jié)點數(shù)較少，就不需要對結(jié)點進(jìn)行分組，系統(tǒng)模型從局部分布式變成了全局分布式。每個結(jié)點參加負(fù)載均衡的部分包括檢測器(sensor)、預(yù)測機(jī)和調(diào)度機(jī)。檢測器監(jiān)測主機(jī)的負(fù)載狀況(包括CPU隊列長度、自由內(nèi)存大小、磁盤可利用空間等),獲得主機(jī)的平均負(fù)載量(AverageLoad)，并定期提交負(fù)載信號給預(yù)測機(jī)。預(yù)測機(jī)結(jié)構(gòu)如圖2。抽樣器定期觸發(fā)sensor，指示其提交負(fù)載信號；它收集sensor發(fā)來的負(fù)載信號，對負(fù)載信號進(jìn)行量化抽樣處理，生成標(biāo)準(zhǔn)可衡量的負(fù)載流，并對負(fù)載流進(jìn)行緩沖。可衡量的負(fù)載流送到模型器，模型器載入預(yù)測模型模板庫，選擇合適的預(yù)測模型，生成預(yù)測器。預(yù)測器根據(jù)選定的時間間隔對負(fù)載流進(jìn)行預(yù)測，產(chǎn)生預(yù)測流送入緩沖器和評估器。評估器對送入的預(yù)測流信號和負(fù)載流信號持續(xù)進(jìn)行比較，并計算預(yù)測誤差，若預(yù)測誤差超過限定的標(biāo)準(zhǔn)誤差，評估器產(chǎn)生Refit信號給預(yù)測器。預(yù)測器通知模型器對預(yù)測模型進(jìn)行修正，并更新預(yù)測器。這種良好的反饋機(jī)制可以保證負(fù)載突變時較好的預(yù)測性能。預(yù)測信號經(jīng)輸出緩沖送往調(diào)度機(jī)，調(diào)度機(jī)對預(yù)測信號進(jìn)行閾值判斷并執(zhí)行相應(yīng)的調(diào)度操作。2.2基于響應(yīng)信號的接收在選擇調(diào)度驅(qū)動策略時，考慮一個原則：當(dāng)系統(tǒng)中各結(jié)點都處于忙碌狀態(tài)時，進(jìn)行任務(wù)轉(zhuǎn)移或進(jìn)程遷移并不能在效率上帶來好處；只要能使各結(jié)點處于忙碌狀態(tài)，就能加快系統(tǒng)中應(yīng)用程序的執(zhí)行，獲得較好的資源利用率。我們設(shè)計了改進(jìn)型接收者驅(qū)動策略，它的基本思想是：當(dāng)系統(tǒng)中某結(jié)點預(yù)測到自己將到達(dá)空閑狀態(tài)，則向組內(nèi)的所有其他成員廣播任務(wù)請求信號。組內(nèi)成員接收到請求信號后就記錄該結(jié)點到接收者表。組內(nèi)成員若預(yù)測自己將來是輕載或適載狀態(tài)，則不予回應(yīng)；若預(yù)測自己將達(dá)到重載狀態(tài)，則發(fā)回響應(yīng)信號給啟動者。接收啟動者收到響應(yīng)信號后記錄響應(yīng)結(jié)點到發(fā)送者表，并從發(fā)送者表中按照任務(wù)通信量、結(jié)點間通信時間和待分配任務(wù)數(shù)計算任務(wù)轉(zhuǎn)移的效益，選擇效益最高的發(fā)送者結(jié)點發(fā)送任務(wù)遷移請求。接收啟動者收到遷移的任務(wù)后，清除發(fā)送者表內(nèi)容，并廣播命令信號給組內(nèi)成員，指示將其從接收者表中刪除。若當(dāng)接收啟動者廣播任務(wù)請求時，組內(nèi)沒有重載結(jié)點，接收啟動者則保持等待狀態(tài)，直到接收到響應(yīng)信號。與傳統(tǒng)的接收者驅(qū)動策略和其他相關(guān)算法策略相比，我們的改進(jìn)型接收者驅(qū)動策略具有3個主要特點：(1)接收啟動者發(fā)出的任務(wù)請求不是逐一傳遞給相鄰結(jié)點，而是廣播給組內(nèi)所有的成員，這樣既避免了系統(tǒng)初啟或輕載時空閑結(jié)點對鄰結(jié)點的反復(fù)打擾，更可以使均衡調(diào)度獲得局部乃至全局最佳均衡點；(2)信息交換不是由負(fù)載狀態(tài)變化驅(qū)動，而是由接收者驅(qū)動，即只有當(dāng)系統(tǒng)中出現(xiàn)空閑結(jié)點和空閑結(jié)點接收到新任務(wù)時，空閑結(jié)點和系統(tǒng)中的重載結(jié)點才進(jìn)行信息交換，這樣大大減少了信息交換的頻度和空間，減少了對結(jié)點的打擾；(3)在定位每次均衡調(diào)度的發(fā)送者時，我們計算了組內(nèi)所有符合調(diào)度條件的結(jié)點，獲得了組內(nèi)最佳的均衡結(jié)點。3負(fù)載均衡調(diào)度該動態(tài)負(fù)載均衡算法主要包括兩部分：預(yù)測算法和調(diào)度算法。預(yù)測機(jī)調(diào)用預(yù)測算法程序?qū)ensor提交的負(fù)載信號進(jìn)行預(yù)測，得到下一抽樣時間的負(fù)載值；調(diào)度機(jī)根據(jù)該預(yù)測負(fù)載值啟動調(diào)度算法程序進(jìn)行均衡調(diào)度處理。每個結(jié)點通過設(shè)定雙閾值Lmin和Lmax來判斷自己的負(fù)載狀態(tài)。當(dāng)負(fù)載低于Lmin時，結(jié)點處于空閑狀態(tài)成為接收者；當(dāng)負(fù)載高于Lmax時，結(jié)點處于重載狀態(tài)成為發(fā)送者；若處于兩閾值之間，表明結(jié)點負(fù)載適中，不需要參與負(fù)載均衡。每個結(jié)點同時保存兩張表：接收者表和發(fā)送者表，分別保存小組中所有接收者和發(fā)送者的狀態(tài)信息，作為調(diào)度決策的依據(jù)。3.1預(yù)測器的預(yù)測值Step1預(yù)測機(jī)的抽樣器定期向檢測器發(fā)出負(fù)載抽樣命令。檢測器根據(jù)抽樣允許標(biāo)志判斷是否輸出。抽樣周期T設(shè)定為系統(tǒng)任意兩結(jié)點往返通信最小時間的2倍。Step2抽樣器收到檢測器提交的負(fù)載信號，對其進(jìn)行量化抽樣處理，獲得抽樣負(fù)載序列{Lt}t∈T。Step3抽樣序列{Lt}送往模型器和評估器。(1)模型器經(jīng)分析判斷，從模型模板庫中選取合適的預(yù)測模型，建立相應(yīng)的預(yù)測器。預(yù)測器把抽樣序列{Lt}放入其歷史空間，調(diào)用預(yù)測模型算法，產(chǎn)生下一抽樣時間的負(fù)載預(yù)測值Lp，送往評估器和輸出緩沖。(2)評估器持續(xù)比較負(fù)載預(yù)測值Lp和負(fù)載抽樣值Lt，計算預(yù)測誤差errk(t)，k表示預(yù)測模型。若預(yù)測誤差超過最大允許誤差errmax，評估器發(fā)出修正（refit）信號給預(yù)測器，指示預(yù)測器修改預(yù)測模型，重新進(jìn)行預(yù)測，跳到(1)；否則轉(zhuǎn)Step1。Step4算法結(jié)束。抽樣周期T是預(yù)測算法較難確定的因素。抽樣周期越短，結(jié)點不均衡發(fā)現(xiàn)得越早，負(fù)載均衡實施得越快，但負(fù)載均衡的開銷也越大?？紤]到從接收者發(fā)出任務(wù)請求到接收到任務(wù)，接收者和發(fā)送者之間要經(jīng)歷2次“握手”過程，而接收者收到任務(wù)后應(yīng)達(dá)到空閑狀態(tài)，所以設(shè)定抽樣周期T等于系統(tǒng)任意兩結(jié)點往返通信最小時間的2倍，以簡化算法的復(fù)雜度。預(yù)測模型目前采用了3種線性時間序列模型MR、AR、ARMR，以后可以增加ARIMA、ARFIMA以及神經(jīng)網(wǎng)絡(luò)BP、線性回歸、模糊聚類等其他相關(guān)預(yù)測模型到模型模板庫，以提高負(fù)載預(yù)測的廣度和精度。3.2任務(wù)遷移響應(yīng)面的記錄與分析Step1系統(tǒng)初始化，所有結(jié)點的接收者表和發(fā)送者表均為null。Step2檢查預(yù)測機(jī)的輸出，判斷預(yù)測負(fù)載值Lp。IfLp<Lmin結(jié)點空閑then啟動接收者處理過程(1)發(fā)送任務(wù)請求信息包給組內(nèi)所有其他成員，包括接收者地址Ra、請求的任務(wù)數(shù)量Jr;(2)向檢測器發(fā)出停止負(fù)載抽樣，置抽樣允許標(biāo)志為否；(3)系統(tǒng)轉(zhuǎn)wait狀態(tài)；(4)接收到響應(yīng)信息包，包括發(fā)送者地址Sa、待分配任務(wù)數(shù)量Jw、待分配任務(wù)與已分配任務(wù)的通信量Cs，記錄到發(fā)送者表數(shù)據(jù)結(jié)構(gòu)中。計算信號往返時間T(r,s)并記錄到發(fā)送者表；計算發(fā)送者表中所有發(fā)送者的發(fā)送效益指數(shù)(5)E=Jw/(Cs*T(r,s));(6)選擇效益指數(shù)E最高的發(fā)送者返回任務(wù)遷移指令if收到遷移的任務(wù)then向所有組內(nèi)成員發(fā)送刪除該接收者指令，跳到(7)if收到刪除發(fā)送者指令then從發(fā)送者表中刪除該結(jié)點，選擇效益指數(shù)E次高的發(fā)送者返回任務(wù)遷移指令，直到收到遷移的任務(wù)，否則按照從大到小的次序選擇E對應(yīng)的發(fā)送者返回任務(wù)遷移指令；如果沒有可選擇的發(fā)送者，則跳回(4)(7)清空發(fā)送者表；(8)啟動負(fù)載抽樣；(9)轉(zhuǎn)Step2。ifLp>=Lmax結(jié)點重載then啟動發(fā)送者處理過程(1)檢查接收者表，若接收者表不空，跳到(3)；若接收者表空，等待任務(wù)請求；(2)收到任務(wù)請求信息包，將請求包中的接收者地址Ra、請求的任務(wù)數(shù)量Jr記錄到接收者表中；(3)向接收者表中所有接收者發(fā)送響應(yīng)信息包，包括Sa、Jw、Cs;then選擇<Jr,Jw>min發(fā)送待分配任務(wù)，并向各接收者發(fā)送刪除該發(fā)送者的指令，跳到(5)(5)轉(zhuǎn)Step2。elseifLmin<=Lp<Lmax結(jié)點適載then轉(zhuǎn)Step2。Step3算法結(jié)束。調(diào)度算法主要是一個循環(huán)判斷處理過程，調(diào)度機(jī)根據(jù)預(yù)測負(fù)載值的大小啟動相應(yīng)的操作。在接收者處理過程中，接收者按照最佳原則選擇發(fā)送者，而不是按照最近響應(yīng)原則選擇發(fā)送者，這是因為負(fù)載預(yù)測機(jī)制保證了最佳發(fā)送者的可靠性，因而獲得了更高的均衡性能。4算法分析4.1通過高效的均衡調(diào)度決策信息增加了節(jié)點及接收者基于預(yù)測的局部分布式動態(tài)負(fù)載均衡算法最大的特點一是基于預(yù)測的方法獲得負(fù)載信息，二是采取了改進(jìn)型接收者驅(qū)動策略。另外，該算法還具有以下幾個突出優(yōu)點：(1)基于預(yù)測的方法獲得負(fù)載信息，使均衡調(diào)度的決策信息有提前量，不僅可以減少空閑結(jié)點等待新任務(wù)的時間，加快重載結(jié)點的任務(wù)遷移，使每次均衡調(diào)度過程縮短；更重要的是大大減少了結(jié)點探詢和任務(wù)重新轉(zhuǎn)移的次數(shù)，降低了任務(wù)遷移的抖動性，從而提高了均衡系統(tǒng)的效率。實際上任務(wù)的重復(fù)分配是影響均衡代價的最大因素。(2)以空閑結(jié)點作為接收者驅(qū)動均衡調(diào)度，可以盡快使系統(tǒng)處于忙碌狀態(tài)，使每個結(jié)點都有任務(wù)執(zhí)行，獲得較好的資源利用率。(3)接收者根據(jù)發(fā)送效益指數(shù)E選定最佳的發(fā)送者遷移任務(wù)，提高了均衡系統(tǒng)的性能。(4)負(fù)載信息交換只在接收者和發(fā)送者之間進(jìn)行，降低了均衡系統(tǒng)的開銷。4.2循環(huán)迭代的均衡我們用3臺Linux工作站（Redhat7.3、P41.6GHz、512MBRAM、100MB網(wǎng)卡）組成了一個小型分布式網(wǎng)絡(luò)，并行編程環(huán)境為PVM，采用典型的求質(zhì)數(shù)例子。求質(zhì)數(shù)程序的循環(huán)迭代相互獨立，而且每個循環(huán)的執(zhí)行時間不相同，比矩陣乘程序更能產(chǎn)生分布式計算不均衡的現(xiàn)象。我們比較了3種負(fù)載均衡下并行執(zhí)行求質(zhì)數(shù)程序的情況，分別是采用基于預(yù)測的均衡算法、文獻(xiàn)的均衡算法、無負(fù)載均衡。圖3是實驗比較情況。實驗結(jié)果顯示，在數(shù)據(jù)規(guī)模不大的情況下，3種負(fù)載均衡方法的效果沒有顯著的差別，隨著數(shù)據(jù)規(guī)模的增大，我們基于預(yù)測的負(fù)載均衡方法取得明顯更好的效果，這是因為計算的規(guī)模愈大，負(fù)載均衡帶來的額外開銷相比愈小，性能優(yōu)越的負(fù)載均衡算法可以獲得滿意的均衡效果。5負(fù)載均衡研究的展望如何提高動態(tài)負(fù)載均衡的性能，