進程遷移自適應動態負載平衡算法的研究與實現

陳彬玫, 徐 虹

(成都信息工程學院計算機學院,四川成都610225)

0 引言

進程遷移是實現負載平衡的基礎,包括遷移機制和遷移策略兩個部分。遷移機制是指進程遷移的具體實現,遷移策略是前期的準備,包括負載向量管理和分布式調度兩部分內容。傳統的進程遷移研究大多集中于進程的遷移機制,對進程的遷移策略關注較少[1-4]。進程遷移是系統動態適應負載變化的最佳機制[1],但實現這個過程是有代價的[5-6]。例如,進程遷移開銷會加重已經過載的服務器;遷移后的進程可能離開本身具有親和性的緩存和資源;負載的瞬時變化和負載延遲擴散會造成進程遷移顛簸[6-7];短期進程[5]或者churn服務器不應作為遷移的選擇目標等。因而需要實現高效、穩定的遷移策略。

進程遷移策略的研究主要集中在負載平衡的信息、調度、位置、選擇、接受和決定等策略[1,6-8]。其中,信息策略是其他策略的依據,是整個進程遷移策略的核心和基礎。關于信息策略,已有成果主要關注于負載向量(Load Vector)的表示、收集、傳播等,很少重視信息策略中負載向量的可靠性問題,特別是對瞬時變化和采集噪聲的考量。例如,文獻[10]在負載收集過程中使用自適應雙閾值策略,有效降低了系統通信開銷。文獻[6]在遷移權衡中使用負載閾值作為進程是否需要遷移的指標,文獻[9]提出閾值和閾長結合的動態反饋調整自適應算法,但閾值策略只能對遷移決定作出有限平衡。文獻[5]使用進程剩余生命時間作為負載向量表示,由于不能反映進程的外部資源依賴,使用范圍有限。

負載信息的可靠性和準確性會嚴重影響進程遷移系統的適應性和穩定性[1,6-8]。已有系統實現在使用負載向量時大多采用延遲響應和加權負載的經驗性折中策略,例如文獻[5]使用1分鐘時間內的平均負載,文獻[8]使用當前時刻系統負載和前一時刻的系統負載的加權求和,文獻[11]使用連續兩次的負載值確定負載是否突變。而這些策略都不能很好的跟蹤系統的負載變化情況,特別是負載瞬時值在較大的峰谷之間顛簸的情況。因此,針對進程遷移策略中的負載計算問題,提出了一種自適應的動態負載平衡(Adaptive Dynamic Load Balancing,ADLB)算法,通過等比計算緩存負載分量的歷史實現均值平滑,通過平均偏差實現峰谷平滑,通過源負載曲線和目標負載曲線的平滑確定遷移關系,為遷移決策提供更準確的依據,從而實現運行時自適應智能調度。

1 進程遷移策略

區分機制和策略是一種重要的設計模式,遷移機制和遷移策略的關系如圖1所示。

進程遷移策略是遷移機制的前提和依據,包括負載向量管理和分布式調度兩部分內容[1]。負載向量管理通過對整個系統中資源進行抽象,篩選系統需要的負載向量,通過一定機制收集、計算和分發,實現全系統共享,為系統管理以及策略制定提供服務。分布式調度策略根據負載向量管理模塊通告的負載信息考慮什么時候(when)遷移哪個進程(which)到哪臺機器(where)。所以調度過程是通過兩次協調實現:首先是負載向量共享確定when、which和where的遷移關系,繼而通過發起者和接收者的協商實施遷移。遷移機制是進程遷移的具體實現,接受調度策略的指令,實施遷移。遷移過程依賴于具體的操作系統環境,需要應用程序和內核的配合、修改內核數據結構和增加系統調用,實現難度較大。

從圖1可以看出,在以進程遷移為目標的系統平臺上,負載向量的表示、收集和計算是進程遷移的起點,進程遷移策略是進程遷移的指令發出者,決定整個系統的適應性和穩定性[1,6-8]。適應性關注遷移策略對系統的影響。由于進程遷移本身就是對系統負載變化的適應,調度算法需要適應不同主機負載、網絡負載和權重參數的變化。適應性本質上是要求遷移策略對負載變化感知的靈敏性。穩定性關注系統是否具備預測下一步行動效果的能力。在分布式系統中,不穩定是絕對的,穩定是相對的。但是,不穩定性必須限制在盡量小的程度內或者穩定程度盡可能達到折中。例如進程遷移的顛簸反而對

系統的穩定性帶來負面影響;在負載很高的系統中最好的辦法是無為而治。穩定性本質上是要求遷移策略對負載變化感知的遲鈍性。

總之,進程遷移策略關注進程遷移動作的實施是否有效[7]。最佳的解決方案是很難實現的,常用的策略是用一個子集來逼近整個搜索空間或利用啟發式達到次優的解決方案。

圖1 遷移機制和遷移策略關系圖

2 ADLB算法與實現

2.1 基本思想

獲得可靠負載的有效方法是對系統一定時段的歷史負載和當前負載進行加權計算。根據負載信息產生特點,時間歷史越久的負載越沒有參考意義,所占權重應該較少。當前負載是需要均衡的負載,要重點考慮,同時也要考慮瞬時的負載噪聲。在這個負載的蹺板上,歷史負載影響太重,系統響應遲鈍,當前負載影響太重,系統反應靈敏,但決策可能盲目。因此,ADLB算法通過兩個步驟獲得更為可靠的負載計算結果。

第一個步驟獲得當前時刻以前的負載狀況的加權均值。算法并不在內存中保留進程運行以來的所有歷史負載記錄,而是通過等比級數作為權重對系統運行以來所有負載值按照時間逆序加權求和作為當前負載值。加權采用等比級數方法是為了有效利用2進制數的優點。例如,歷史負載的權重為:當前負載的權重為:其中m∈N,1≤n≤2m,且可以根據系統實現需求進行調整。由此,用 Ai表示時間線上各點采集到的當前負載信息,Ti表示時間線上各點加權求和后的平滑負載值,m取3,n取1,則各個時間點的負載計算過程形成如下序列:由序列可見,加權計算存在3個關鍵:(1)負載值的影響按照時間線前進的反方向等比下降;(2)當m值確定時,n值越小,當前負載值的權重越小,歷史的權重越大,反之相反;(3)m、n可以根據需要采用不同的值。

第二個步驟仍然采用如上加權均值的方法,但計算的對象是當前采集到的瞬時負載值偏離第一步驟獲得的加權均值的程度。這需要引入負載序列的標準差和平均偏差。在工程應用上,都認為平均偏差是對標準差的一種好的逼近,并且避免了標準差的開方操作。例如,RTCP協議中抖動值的計算和TCP協議中超時重傳機制的實現都使用了平均偏差。文獻[12]也給出平均偏差(d)和標準偏差(σ)存在如下關系:σ≥d≥0,因而可以使用平均偏差代替標準偏差。標準差和平均偏差的計算公式分別為:

上述兩個步驟獲得的負載值之和即是決策依據負載。兩個步驟都是必要的,僅通過第一個步驟獲得負載值作為遷移依據,無法準確跟蹤負載當前的瞬時變化,失去負載感知的靈敏性。在第一步驟的均值中強調 n取較小的值以最大可能考慮歷史,最后的負載值使用第一步驟的均值和第二步驟的標準差之和,可以削弱瞬時高負載,補償瞬時低負載,有效保證負載統計的穩定性。

2.2 算法實現

2.2.1 歷史負載平滑

取g為影響歷史負載權重的因子,A為經過平滑的負載值,M是實際測到的負載值。計算公式為:

為了編碼實現方便,g采用2的乘方,這樣計算時只需要移位操作而不需要乘除運算。從(1)式可以看出,歷史負載值隨著時間的流逝,通過等比的關系逐漸減小,對負載平衡時總負載的計算的影響也逐漸減小。

2.2.2 峰谷負載平滑

上一步操作中,A的效果相當于平均值,M-A就是負載瞬時值的峰谷范圍。計算公式為:

然后引入峰谷負載平滑因子h和平均偏差D,如果要對負載變化敏感,可以設置較大的h,將會使得負載值快速上升。計算公式為:

2.2.3 負載計算

綜合式(1)和(3),得出的負載值計算公式如下:

2.2.4 遷移權衡

系統中遷移源節點和遷移目標節點之間定義了一對遷移關系。進入遷移臨界窗口的節點,在遷移窗口內變化幅度(絕對值)之和最大的節點作為一對潛在遷移關系。為了平滑遷移關系,源節點取當前負載值和平滑負載值的最小值,目標節點取當前負載值和平滑負載值的最大值。計算公式為:

雖然負載值已經經過平滑,但還可以引入遷移臨界窗口規定系統必須遷移之前處于高負載的最長時間和系統可以接受遷移進程之前處于低負載的最長時間。當然,遷移權衡要結合其他策略,例如,節點和進程的生命時間作為權重是必須考慮的,系統的遷移臨界點可以使用閾值和閾長結合策略[9]等。

2.3 平滑證明

設相鄰兩次負載為:

兩次負載的比值為:

隨著因子g、h的增大,兩次負載的比值接近1。

兩次負載的差值為:

隨著因子g、h的增大,兩次負載的差值接近0。

綜上,隨著 g、h的增大,負載曲線趨于直線。

2.4 算法偽代碼描述

(1)float load=0;//表示平滑后的負載均值

(2)floatmdev=0;//表示平滑后的負載峰谷

(3)接受新得到的負載測量值m

(4)If(采樣值m有誤) then

(5)m=1;/*異常處理*/

(6)Endif

(7)If(不是第一個負載采樣) then

(8)m-=load;

(9)If(m＜0) then

(10)load+=(m ＞＞1);//放大

(11)m=-m;/*m取絕對值*/

(12)Else

(13)load+=(m ＞＞3);//縮小

(14)Endif

(15)m＞＞=2;

(16)mdev-=(mdev＞＞2);

(17)mdev+=m;

(18)Else/*第一個采樣*/

(19)load=m;/*設置初值*/

(20)mdev=0;

(21)Endif

根據上述代碼,load與mdev之和即為平滑后的整體負載。

3 系統模型及性能分析

3.1 系統軟件模塊棧

系統基于linux同構集群平臺,采用從下到上分層的棧結構組織進程遷移的主要功能模塊,在節點之間存在3條主要消息通信分別對應棧結構的3個主要層次。各個模塊的主要功能如圖2所示。

負載管理模塊區分負載向量的內容、權重和粒度。根據任務的性質,負載向量的內容為3種類型:CPU密集型、內存密集型和I/O密集型,I/O類應用又分為磁盤I/O和網絡I/O。磁盤I/O通過分布式文件系統實現,包括:文件共享、文件復制、文件遷移等,采用的負載分量包括磁盤利用率和磁盤空間大小,文件描述符打開的對象區分網絡(NFS)還是磁盤(RAID)等。網絡I/O以軟中斷為主要指標,包括消息請求和數據傳輸,通過注冊數據端口和服務端口區分,采用的負載分量包括網絡流量、網絡帶寬和軟中斷頻率等。管理員可以根據應用需求設定各個應用的權重,也可以通過系統統計負載歷史感知應用主要依賴的資源,還可以預測進程和節點的剩余生命時間,自適應的調整權重分配。另外,針對前述負載分量,系統分別統計節點和進程兩個粒度的負載信息。

圖2 系統軟件模塊棧

表1 典型負載變化測試數據

負載向量收集和傳播的方式主要有周期性和事件觸發兩種,事件包括:進程創建、終止、遷移。在設計的實現方案中,負載向量傳播內容認為是固定的數據結構,傳播策略采用周期加事件觸發的方式,周期時間較長。為了既能及時在系統的各個節點之間傳遞信息,又平衡收集開銷,引入負載更改閾值[10],當負載的變化超過該值時,觸發負載推送到各個節點。當負載的變化不超過該值時,信任已有負載值,不收集負載。系統在遷移權衡時使用兩個主要的閾值,遷移臨界點和遷移臨界窗口。遷移臨界點采用閾值和閾長[9]表示系統需要轉移負載的臨界范圍。遷移臨界窗口則表示系統必須遷移之前處于高負載的最長時間和系統可以接受遷移進程之前處于低負載的最長時間。另外,系統對進程適合遷移以及節點適合遷出和遷進進程的最小運行時間也給出了閾值。

遷移協商采用兩階段的方式,需要遷移雙方對遷移的開始和完成分別作出確認。另外啟動策略采用對稱啟動方式,并限制一對節點運行時只能有一對遷移關系。為了避免進程遷移泛濫和掠奪[8]的群聚效應(Herd Effect),在遷移開始之前把確定的遷移關系傳播給系統內其他節點。

遷移實施主要基于linux環境下checkpoint-restart實現。

3.2 測試方案

根據系統實際運行過程中的負載變化,考慮4種典型的負載變化趨勢:(1)負載持續遞增:模擬了適應訪問人數逐漸增多的互聯網應用;(2)負載持續遞減:模擬適應訪問人數逐漸減少的互聯網應用;(3)負載以類似正弦的方式波動變化:模擬典型的周期運行daemon進程負載變化;(4)負載隨機變化:模擬系統負載隨機變化的情況。

分別在上述4種情況下對系統負載平滑效果進行測試,統計實際值和平滑值的情況。測試數據如表1所示,上述4種情況分別對應表中1、2、3、4項。圖3～6分別直觀的顯示4組數據中負載值的平滑情況。由4種測試結果可以看出,算法有效的跟蹤了負載變化,并實現了負載平滑。進程遷移是有開銷的,因此應當采用盡量不遷移的原則。例如,只有負載持續遞增的主機,在遷移關系的選擇時才會被選中,偶然一次的高負載并不會引起其上的進程遷出。相應的,只有負載持續遞減的主機,才能成為其他過載主機的遷入目標。

圖3 負載遞增實驗數據

圖4 負載遞減實驗數據

圖5 負載正弦波動實驗數據

圖6 負載隨機變化實驗數據

4 總結

針對進程遷移中負載信息計算的可靠性問題,提出ADLB算法,有效的解決了負載變化抖動問題。系統在運行時采集并計算平滑負載,自適應系統負載的變化,并結合其他權重因素,動態遷移進程。

負載向量的管理不是進程遷移所特有,也不專用于遷移調度,幾乎所有實現動態負載平衡和任務調度的系統中都要涉及。負載向量的計算方法也可以用于其他計算環境,并可以根據不同目標,收集不同的負載分量。由于算法的通用性,對于其他平臺也有借鑒意義。

下一步工作是在目前工作的基礎之上研究多目標(I/O、MEM、CPU)調度決策問題。

[1] Dejan S Milojici,Fred Douglis,Yves Paindaveine,et al.Process migration[J].ACM,2000,32(3):241-299.

[2] Balazs Gerofi,Hajime Fujita,Yutaka Ishikawa.An Efficient Process Live Migration Mechanism for Load Balanced Distributed Virtual Environments[C].Cluster 2010;IEEE International Conference on Cluster Computing,2010.

[3] Amirreza Zarrabi.A Generic Process Migration Algorithm[J].International Journal of Distributed and Parallel Systems(IJDPS),2012,5(3):29-37.

[4] Chandu D Vaidya,M B Chandak.Efficient Parallel Process Migration Algorithm Using Statistical Approach[C].Fourth International Conference on Computational Intelligence and Communication Networks,2012.

[5] 張永坤,金海,唐丹.一種基于進程剩余運行時間總和的集群動態負載平衡算法[J].計算機工程與科學,2005,27(5):63-65.

[6] 蔣江.異構集群系統中基于進程遷移機制的負載平衡算法的研究[D].長沙:國防科技大學研究生院,2002.

[7] 韓海軍.無中心集群下基于進程遷移的負載平衡研究[D].沈陽:沈陽理工大學,2007.

[8] 遲忠惠.基于進程遷移的負載均衡算法的研究[D].青島:中國海洋大學,2005.

[9] 周佳祥,鄭緯民,楊廣文.一種基于進程遷移的自適應雙閾值動態負載平衡系統[J].清華大學學報,2000,40(3):121-125.

[10] 胡金柱,徐松.分布式系統中一種負載平衡的動態反饋調整自適應算法[J].小型微型計算機系統,2003,24(8):1510-1515.

[11] 劉學偉.基于linux進程遷移的設計與應用實踐[D].成都:電子科技大學,2008.

[12] 韓兆洲,楊林濤.極差、平均差和標準差之間測度關系研究[J].統計與信息論壇,2008,23(4):5-8.