集群技術及負載均衡調度算法研究

摘 要： 集群(cluster)技術是一種較新的技術，通過集群技術，可以在付出較低成本的情況下獲得在性能、可靠性、靈活性等方面相對較高的收益。任務調度是集群系統(tǒng)中的核心技術。文章對集群的定義、分類、優(yōu)點及各種常見的負載均衡調度算法進行了詳細歸納。

關鍵詞： 集群； 負載均衡； 調度算法

中圖分類號：TP393 文獻標志碼：A 文章編號：1006-8228(2012)08-37-02

0 引言

集群以其較強的能力、靈活的結構和可以提供像個人計算機那樣方便的人機界面而具有良好的推廣應用價值；集群的研究已經成為超級計算機和并行計算研究開發(fā)的一個重要方向。本文著重介紹了集群的概念、分類及其優(yōu)點，并對集群系統(tǒng)中的各種常見的負載均衡調度算法[1-4]進行了分類和詳細探討。

1 集群介紹

1.1 集群的定義

通常來說，集群(Cluster)是指利用高速通信網絡將一組相互獨立的計算機按某種結構連接起來，在并行程序設計及可視化人機交互集成開發(fā)環(huán)境支持下，統(tǒng)一調度，協(xié)調處理，實現(xiàn)高效并行處理的系統(tǒng)。簡單地說，集群就是一組相互獨立的、通過高速網絡互聯(lián)的計算機，它們構成了一個組，并以單一系統(tǒng)的模式進行管理?？蛻襞c集群相互作用時，集群像是一個獨立的服務器。

1.2 集群的分類

一般按照解決問題的不同而將集群分為以下三個層次[5]。

⑴ 科學集群(Scientific clusters)。由主服務器運行一個控制程序，將一個大規(guī)模的計算分成若干個子任務分配到網絡中的每個節(jié)點，由該節(jié)點計算出相應的結果后提交給主服務器。該方案主要解決并行計算的問題。

⑵ 負載均衡集群(Load Balance Clusters)。由兩臺負載均衡調度器和后臺實際服務器組成。負載均衡調度器接收用戶的請求，并根據(jù)后臺實際服務器負載的狀況將任務分配到相應節(jié)點進行運算。該方案主要解決大規(guī)模計算的問題。

⑶ 高可用性集群(High—availability clusters)。由兩個以上或兩個以上的節(jié)點構成，可簡單、經濟地確保重要的商務應用軟件、服務器和數(shù)據(jù)的持續(xù)可用性。通過系統(tǒng)監(jiān)控、服務監(jiān)控、IP自動遷移等技術實現(xiàn)在整個應用中無單點故障。

在實際的使用中，集群的這種三種類型可相互交融，如高可用性集群也可以在其節(jié)點之間均衡用戶負載。同樣，也可以從要編寫應用程序的集群中找到一個并行集群，它可以在節(jié)點之間執(zhí)行負載均衡。從這個意義上講，這種集群類別的劃分是一個相對的概念，不是絕對的。

1.3 集群的優(yōu)點

集群是通過高速通信網絡將一組相互獨立的計算機按某種結構連接起來的系統(tǒng)，它具有以下優(yōu)點。

⑴ 高性能：傳統(tǒng)服務器的硬件和軟件資源有一定上限，當工作負載超過一定限度時，服務器將難以承擔巨大負載，而集群服務器通過多臺主機的組合，可以承擔巨大的負載，獲得很高的整體性能。

⑵ 高性價比：組成集群的服務器可以采用普通PC服務器，價格低，具有較高的性能/價格比。

⑶ 可伸縮性：集群系統(tǒng)中節(jié)點數(shù)目可以增長到幾千個，乃至上萬個，其伸縮性運超過單臺超級計算機。

⑷ 高可用性：在硬件和軟件上都有冗余，通過檢測軟硬件的故障，將故障屏蔽，由存活節(jié)點提供服務，可以實現(xiàn)高可用性。

2 負載均衡調度算法

負載均衡是指集群中各處理節(jié)點的負載信息通過某代理軟件傳遞給均衡器，由均衡器做出決策并對負載進行動態(tài)分配，從而使集群中各處理節(jié)點的負載相對趨于平衡。集群系統(tǒng)構建的核心是負載均衡調度算法的選擇和使用。負載均衡調度算法是集群技術中的關鍵技術。負載均衡調度算法可分為靜態(tài)調度算法、動態(tài)調度算法和動靜結合調度算法。

2.1 靜態(tài)調度算法

所謂靜態(tài)調度算法就是調度策略事先已經確定，而不考慮系統(tǒng)運行時的狀態(tài)。目前常見的靜態(tài)調度算法有：輪叫調度、加權輪叫調度、目標地址散列調度和源地址散列調度。由于當客戶通過TCP/UDP連接訪問服務器時，服務所需的時間和所要消耗的計算資源千差萬別，因此靜態(tài)調度算法無法保證系統(tǒng)內服務器真正地實現(xiàn)均衡負載。同時，采用靜態(tài)調度算法要求系統(tǒng)在運行過程不能執(zhí)行其他任務，如果有其他的任務在此期間占用了集群系統(tǒng)資源，將很有可能導致調度策略的失敗。

2.1.1 輪叫調度

輪叫調度[6]算法就是以輪詢的方式依次請求調度不同的服務器[1]，即每次執(zhí)行i=(i+1)mod n，并選出第i臺服務器。該算法是所有調度算法中最簡單也是最容易實現(xiàn)的一種方法，其優(yōu)點是簡單，即它無需記錄當前所有連接的狀態(tài)，所以是一種無狀態(tài)調度。輪詢調度總是假設所有服務器處理性能均相同，不管服務器的當前連接數(shù)和響應時間。該算法不適用于服務器處理性能不一的情況，而且當請求服務時間變化比較大時，輪詢調度算法容易導致服務器間的負載不平衡。

2.1.2 加權輪叫調度

加權輪叫調度算法可以解決服務器間性能不一的情況，它用相應的權值表示服務器的處理性能，服務器的缺省權值為1。該算法是按權值的高低和輪詢方式分配請求到各服務器[3，4]。權值高的服務器比權值低的服務器先收到連接，并能處理更多的連接，相同權值的服務器處理相同數(shù)目的連接數(shù)。加權輪詢調度算法比較簡單和高效，當連接請求的服務時間變化很大時，單獨的加權輪詢調度算法依然會導致服務器間的負載不平衡。

2.1.3 目標地址散列調度

該算法先根據(jù)請求的目標IP地址，作為散列鍵從靜態(tài)分配的散列表找出對應的服務器，若該服務器是可用的且未超載，將請求發(fā)送到該服務器，否則返回空。

2.1.4 源地址散列調度

該算法根據(jù)請求的源IP地址，作為散列鍵從靜態(tài)分配的散列表找出對應的服務器，若該服務器是可用的且未超載，將請求發(fā)送到該服務器，否則返回空。

2.2 動態(tài)調度算法

所謂動態(tài)調度算法就是指負載平衡系統(tǒng)利用系統(tǒng)各結點運行時的全部(或部分)信息，作出實時負載調度決策。動態(tài)調度算法適用于單用戶/多用戶共享集群環(huán)境，它在運行期間對系統(tǒng)資源實時監(jiān)視，并以此作為調度的依據(jù)，故對于系統(tǒng)不可預測的變化能夠及時作出反應從而保證系統(tǒng)良好的性能。目前常見的動態(tài)調度算法有：最小連接調度、加權最小連接調度、最少等待隊列調度和最少利用率調度。

2.2.1 最小連接調度

該算法是把新的連接請求分配到當前連接數(shù)最小的服務器。最小連接調度是一種動態(tài)調度算法，它通過服務器當前所活躍的連接數(shù)來估計服務器的負載情況。調度器需要記錄各個服務器已建立連接的數(shù)目，當一個請求被調度到某臺服務器，其連接數(shù)加1；當連接中止或超時，其連接數(shù)減1。該算法的缺陷是只用當前連接數(shù)來衡量服務器的負載情況，沒有全面考慮服務器的負載情況，當某些用戶請求所需的系統(tǒng)資源比較多的情況下，盡管集群中連接數(shù)平衡了，也會使得集群系統(tǒng)的負載不均衡。另外，該算法也未考慮集群中各個服務器處理能力的不同。

2.2.2 加權最小連接調度

該算法是最小連接調度的超集，各個服務器用相應的權值表示其處理性能。服務器的缺省權值為1，系統(tǒng)管理員可以動態(tài)地設置服務器的權值，在調度新連接時盡可能使服務器的已建立連接數(shù)和其權值成比例。該算法雖然考慮了集群中各節(jié)點處理能力的不同，但仍然以當前連接數(shù)來衡量服務器的負載情況，無法反映出服務器的真實負載情況。另外，加權最小連接調度沒有考慮連接請求的服務時間，也沒能根據(jù)服務器當時的響應情況動態(tài)地自動調整服務器的權值，所以該算法依然會導致服務器間的負載不平衡。

2.2.3 最少等待隊列調度

該算法比較服務器資源等待隊列的大小，把任務分配到等待隊列最少的服務器上。調度算法主要有：最少CPU等待隊列調度、最少I/O請求等待隊列調度、最少連接等待隊列調度、最少連接隊列等待時間調度等等。

2.2.4 最少利用率調度

該算法比較服務器各資源利用率的大小，把任務分配到資源利用率最少的服務器上。調度算法主要有：最少CPU利用率調度，最少內存利用率調度等。

2.3 動靜結合調度算法

所謂動靜結合調度算法就是將靜態(tài)調度算法和動態(tài)調度算法融合在一起，兼顧這兩種算法而形成的一種負載均衡調度算法。目前常見的動靜結合調度算法有閾值(加權)輪轉調度[7]。

2.3.1 閾值(加權)輪轉調度

該算法先為各個服務器資源負載指定一個閾值，來表示各個服務器資源負載性能。其主要思想是：比較服務器資源負載與給定的資源負載閾值的大小，對小于給定資源負載閾值的服務器再進行（加權）輪轉調度。

3 結束語

集群作為當前世界上并行處理的熱點和主流，具有許多其他系統(tǒng)不可替代的優(yōu)勢：性價比高、可擴展性好、高可用性和高能用性。因此，作為多數(shù)研究及應用機構都能承受得起的一種超級計算資源，集群系統(tǒng)必將對許多大挑戰(zhàn)的計算問題及國民經濟產生積極影響。

參考文獻：

[1] 劉侃，李俊等.一種共享存儲視頻服務器集群的請求調度策略[J].小型微型計算機系統(tǒng)，2009.30(4):666-670

[2] 李永喜，陳小平等.一種基于內容的Web服務器集群調度算法[J].計算機應用與軟件，2008.25(3):215-216

[3] 黃穎，謝忠等.有效的WebGIS地圖服務器場負載均衡算法[J].計算機工程，2009.35(4):10-12

[4] 李顯寧，鐘誠等.異構集群系統(tǒng)的可分負載多輪調度算法[J].計算機應用研究，2008.25(4):1028-1032

[5] 黃愷，徐志偉.可擴展并行計算技術結構與編程[M].機械工業(yè)出版社，2003.

[6] Katz E D， Butler M， McGrath R. A Scalable HTTP Server: The NCSA Prototype[J]. Computer Networks and ISDN Systems，1994.8(5):155-163

[7] 曾東海，劉海等.集群負載調度算法性能評價[J].計算機工程，2006.32(11):78-79