云計算環境中三層架構的資源負載均衡研究

黎 燕

云計算環境中三層架構的資源負載均衡研究

黎 燕

福建第二輕工業學校

為了使云環境中資源能更加高效、合理地運轉，該文探求使用新的調度策略來使系統達到負載均衡，提出了一個在三層架構云計算網絡環境中的兩階段調度算法。該算法結合了隨機負載均衡算法和Min-Min負載均衡調度算法的特性，從而能更高效率地執行任務并使系統達到負載均衡。

云計算 負載均衡 兩階段調度算法

1 背景

當今時代，為了跟上互聯網的發展進度，寬帶網絡和硬件技術也在不斷進步。云計算以一種全新的計算模式向網絡用戶提供了許多的應用服務，類似于視頻、音樂等，因此，如何利用云計算的優勢使得每個任務在最短的時間內都能得到所需求的資源，成為一個非常重要的問題。

我們知道，每個調度算法都有不同的特性。隨機負載均衡算法（OLB算法）嘗試使每個節點保持忙碌狀態，不考慮每個計算機當前的負荷情況。OLB算法規定隨機順序的每個任務對當前節點有效，其優點是能很簡單地達到負載均衡，但缺點是沒有考慮每個任務的預期執行時間，因此，整體完成時效非常差。換句話說，OLB算法隨機給當前可用節點分配未完成的任務，并不考慮節點當前的負荷情況。

最小執行時間(Minimum Execution Time, MET)算法把工作隨機分配給執行最快的節點，忽略節點的當前負荷。MET試著尋找好的工作節點配對，但是因為它沒有考慮節點的當前負荷，經常導致節點間的不均衡負載，不適用于異質性計算機系統的應用。

最小完成時間(Minimum Completion Time, MCT)算法把每個任務隨機分配給完成時間期望值最小的節點。所謂的完成時間就是執行時間，但是它是一個更成功的探索，因為它同時考慮了執行時間和節點的當前負荷。

Min-Min調度算法給每個未分配的任務建立最小完成時間表，然后把帶有最小完成時間的任務分配給節點。Min-Min算法與MCT算法的機制相同。但是，Min-Min在每一次循環中都要考慮所有任務的最小完成時間，所以能全面、最小跨度地分配工作。因此，它能比MCT算法更好地使節點達到均衡。Min-Min算法的實質是每一次都是給最好的完成時間最小的分配資源。

因為OLB調度算法簡單、易于實施，并且在此算法下每臺計算機經常處于忙碌狀態。在我們的研究中，OLB算法用來在三層式云計算網絡中分配任務和將任務分割成許多子任務。此外，為了使在系統中的每個計算機負載均衡，在此次研究中還改善了Min-Min調度算法，預期能有效地減少每個節點的執行時間。

2 兩階段調度算法

目前，ZEUS提供了可用來開發新的云計算方法的網絡框架，并且已經應用到當前的研究中。根據ZEUS的網絡架構和云計算的結構性能，我們的研究框架采用了一種三層式的層次結構拓撲（如圖1所示）。服務節點用來執行子任務，第二層的是服務管理者，用來將任務分割成邏輯上獨立的子任務，第一層是需求管理者，給恰當的節點分配任務。

圖1 三層框架結構

為了在三層式云計算網絡中使每個節點達到負載均衡，減少執行時間，在此研究中將OLB和LBMM算法整合，即兩階段調度算法。所謂兩階段調度算法，即第一階段，管理者利用隨機負載均衡調度算法把任務分配給服務管理節點。第二階段，服務管理節點利用LBMM調度算法選擇合適的服務節點執行子任務。

該算法考慮了每個子任務在每個服務節點上的執行時間。通過代理在不同的服務節點上能分辨出每個子任務的執行時間。根據代理收集的信息，每個服務管理節點選擇具有最小執行時間的服務節點來執行不同的子任務，并把它記錄在最小時間數組里面。最后，每個子任務的最小執行時間都被記錄了即在某個節點上的最小執行時間。同時，服務管理節點最先選擇服務節點γ。因此，子任務α將被分配給節點γ。一旦子任務α分配給服務節點γ執行，就會從子任務隊列中刪除。同時，最小時間數組將會重組，服務節點γ放在最小時間數組的最后一個。該算法步驟如下：

步驟1: 子任務X的要求從C服務節點中選擇最小時間的服務節點，同時形成一個最小時間服務節點集合，X是子任務的總數，C是可執行子任務的服務節點總數。

步驟2: 服務節點γ，因為γ在最小時間集合中具有最小的執行時間，γ是節點標識符。

步驟3: 子任務α分配給節點γ。

步驟4: 整個子任務α從未執行任務集合中刪除，α是子任務的標識符。

步驟5: 組最小時間數組，服務節點γ放在最后一個。

步驟6: 重復步驟1到5，所有的子任務都會被執行。

3 研究方法

在云計算系統中存在一些異構節點，即每個節點執行任務的能力有所不同，因此，在選擇執行任務節點時只考慮到節點的剩余CPU是不夠的。所以，在云計算網絡中怎樣選擇有效節點來執行任務是非常重要的。

由于任務在用戶執行時可能有不同的特征，它可能需要一些特定的資源。例如，在實施有機序列組裝時，它可能對可用內存有很高的要求。并且，在執行子任務時，為了達到最高的效率，我們會針對任務性能采取不同的條件決策變量，通常根據任務的資源要求來確定決策變量。

在此次研究中，通過代理的方法收集云計算系統中每個節點的相關信息，比如剩余CPU能力，可用內存，傳輸速率。V1=剩余CPU能力；V2=可用內存；V3=傳輸速率。在所有的這些信息收集之后，他們就會被供應給管理者，并協助它實現系統的負載均衡。

為了能使管理者有效地選擇合適節點，系統中所有的節點（包括服務管理節點和服務節點）都會被進行閾值估測，閾值由執行任務時資源需求量派生。通過服務管理節點閾值的服務管理節點會被認為是有效的。

3.1 服務管理節點的閾值

云計算環境由異構節點組成，每個節點的性能可能會有很大區別，并且在忙碌狀態下，每個節點的可用資源會不同。從任務完成時間的角度看，CPU可用能力、內存可用大小和傳輸速率是任務執行時間的三個決定性因素。因此，在我們的研究中，剩余CPU可利用率，剩余內存大小和傳輸速率會被作為估測服務管理節點閾值的數值。一個具體事例如下：

剩余CPU利用率≥500s

剩余內存≥21578kB

Transmission Rate≥8.18MB/s

3.2 服務節點閾值

當一個服務管理節點通過任務要求的閾值后，它所管理的服務節點就能夠執行此任務。然而，在云計算環境中，節點的位置是動態的，在任何時間每個節點都可能進入忙碌狀態，這樣就增加了任務的執行時間，導致節點性能的降低。因此，服務節點的閾值用來選擇更好的服務節點。該過程分成如下四步：

步驟一：計算每個子任務的平均執行時間；

步驟二：如果一個子任務要求的執行時間小于或等于平均執行時間，就立即取出該子任務并執行；

步驟三：如果子任務要求的執行時間大于平均執行時間，就把該任務的執行時間設置為∞（執行時間太長以至于忽略不計），另外已經執行過任務的節點重新進入系統，參與子任務的執行。

步驟四：重復步驟一到步驟四，直到所有的子任務都完全執行。

在我們的研究中，通過提出的整合調度算法，任務能被迅速地分配執行，并且在三層式云計算網絡中能通過閾值有效地選擇服務節點。

我們提出的兩階段調度算法結合了OLB和LBMM算法的特性，協助選擇有效的服務節點。首先，管理者用隊列存儲需要執行的任務（N0），然后，在第二層，用帶有服務管理節點閾值的隨機負載均衡算法分配任務給服務管理節點（N1，N2，N3，N4，N5）。然而，每個委托節點執行任務有不同的特點，所以，選擇節點的約束也不同。代理用來收集節點的相關信息。根據每個任務的性能，每個節點的閾值已得到估測，任務將會分配給某個節點。但是，為了避免某些節點的執行時間過長從而影響系統性能，服務節點閾值用來選擇最合適的服務節點來執行子任務。

4 算法實例

現給出一個有5個任務待完成的例子，討論在三層式云計算網絡中兩階段調度算法的應用。

假定該算法的特點有：①傳輸時間可知；②每個任務執行時間可預測；③每個任務能分成幾個獨立的子任務，每個子任務能在分配的服務節點上完全執行；④服務節點的數目大于等于子任務的數目。

步驟1：收集待完成任務A、B、C、D、E，管理者N0把任務存進工作隊列，如圖2所示。代理收集每個節點的相關信息，如表1所示。針對每個任務的特性，管理者用服務管理節點閾值來估測每個節點。

圖 2 工作隊列

表1 每個節點的相關信息

步驟2：根據服務管理節點閾值，管理節點利用OLB調度算法把待執行任務分配給合適的服務管理節點。因此，任務A能分配給N1，N2，N3，N4或者N5。同樣，任務B也能分配給這5個節點（除已經分配執行任務A的服務管理節點）。

步驟3：假設任務A的服務管理節點閾值如下所示：

剩余CPU計算能力≥500MB/s

剩余內存≥256MB/s

傳輸速率≥20MB/s

根據代理收集的信息，如表1所示，任務A將被分配給節點N1執行。

步驟4：當任務分配給服務管理節點之后，將會被分成幾個獨立的子任務邏輯單元。例如，任務A被分成4個子任務。

步驟5：服務管理節點利用LBMM算法計算每個子任務在不同節點上的執行時間，如表2所示。假設子任務A1在服務節點N12上有最小實行時間，則最小時間=（A1，N12）=13s記錄進去。Min-Time數組用來存儲最小時間集合，如等式（1）所示。

表2 任務A的每個子任務分配之前在不同服務節點的執行時間(第一次)

步驟6：服務管理節點計算每個子任務的閾值，然后與每個子任務的執行時間比較。在本例中，子任務A1的閾值13（≤24）,執行時間小于服務節點的閾值，子任務能被正常執行。子任務A2的閾值11（≤17）, 執行時間小于服務節點的閾值，子任務能被正常執行。

步驟7：服務管理節點在Min-Time數組中尋找子任務的最小執行時間。相應子任務A2 ，與之對應的服務節點N12，所以，子任務A2就分配給節點N12執行。子任務A2 從待執行任務集合中刪除，并更新剩余子任務執行時間數組。如表3所示。

表3 任務A的每個子任務分配之前在不同服務節點的執行時間(第二次)

步驟8：在步驟7執行之后，子任務A2從子任務集合中刪除，服務節點N12排列到最后一個。當其他所有節點都已分配工作后，所有的節點重新進入系統。現在，服務管理節點重新將每個子任務的最小執行時間與之閾值相比較。得到服務節點與子任務最小時間集合，如等式（2）所示。例如（A1，N11），相應子任務A1，服務節點N11，子任務A1從待執行任務集合中刪除，剩余子任務的執行時間集合更新，如表4所示。

表4 任務A的每個子任務分配之前在不同服務節點的執行時間(第三次)

步驟9：步驟8完成之后，子任務A1從子任務集合中刪除，服務節點N11排列到最后一個。另外，服務管理節點再次比較每個子任務的最小執行時間和閾值。發現子任務A3超過了服務節點閾值（43>41），因此，A3 的最小執行時間將被設置為∞，表示不能在最佳時間內完成。服務節點與最小時間集合如等式(3)所示，找到（A4 ，N13），子任務A4從待執行子任務集合中刪除，更新剩余子任務執行時間集合，如表5所示。

表5 任務A的每個子任務分配之前在不同服務節點的執行時間(第四次)

步驟10：第9步之后，子任務A4從子任務集合中刪除，服務節點N13排列到最后一個，當子任務A3 的最小執行時間超過服務節點閾值之后，所有的服務節點重新進入系統，如表6所示。最終，服務節點N12執行子任務A3。

表6 任務A的每個子任務分配之前在不同服務節點的執行時間(第五次)

為了維持云計算系統的負載均衡，該兩階段負載均衡算法有更高的利用效率。

5 實驗結果

在本次實驗中采用了Hadoop環境進行模擬實驗。本實驗在Hadoop環境下，隨機生成100個任務及100個節點，設置各節點計算能力隨機分布在[1000,2000](MB/S)區間范圍，任務需求隨機分布在[1000000,1500000](MB)區間范圍，同時忽略節點間通行能耗及時間開銷，為盡可能減小誤差，三個算法分別反復進行10次并取平均值作為實驗的最終結果，實驗結果如圖3所示（圖中黑色柱條表示平均完成時間，白色柱條表示最小完成時間）。

圖3 平均完成時間與最小完成時間對比圖

從圖3可見，雖然本文提出的兩階段負載均衡算法在最小完成時間上不如MCT，但是在平均完成時間上本文的算法能得到更好的效果，從而可以看出本文提出的算法在任務分配的時候能夠更好地考慮負載的均衡，使得完成所有任務所需的時間盡量少，不僅提高了任務的整體完成效率，而且可以減少資源的消耗，提高了資源的利用效率。

6 結束語

云計算代表著未來計算機與通信技術的發展方向, 作為一種最能體現互聯網精神的計算模型，云計算必將在不遠的將來展示出強大的生命力，而以分布式文件系統為代表的云存儲是云計算中的重要組成部分，其中負載均衡技術是云存儲的核心技術之一 , 本文提出一個在三層架構云計算網絡環境中的兩階段調度算法。這個算法結合了隨機負載均衡算法(Opportunistic Load Balancing, OLB)和Min-Min負載均衡(Load Balance Min-Min, LBMM)調度算法，能更高效率地執行任務并使系統達到負載均衡，從而為其他組合優化問題提供了進一步的研究思路。

[1] 劉鵬．云計算[M]．北京：電子工業出版社，2010．

[2] ZXTM for Cloud Hosting Providers[EB/OL]. http://www.zeus.com/c1oud_ computing/for_cloud_providers.html, January 2010.

[3] Load Balancing, Load Balancer[EB/OL]. http://www.zeus.com/products/ zxtmlb/index.html, January 2010.

[4] A. Vouk. Cloud Computing-Issues, Research and Implementations[J]. Information Technology Interfaces, 2008(6): 31-40.

[5] F.M. Aymerich, G. Fenu, S. Surcis. An Approach to a Cloud Computing Network[C]. The First International Conference on the Applications of Digital Information and Web Technologies, 2008: 113-118.