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

關(guān)鍵詞： 集群； 負載均衡； 調(diào)度算法

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

0 引言

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

1 集群介紹

1.1 集群的定義

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

1.2 集群的分類

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

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

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

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

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

1.3 集群的優(yōu)點

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

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

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

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

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

2 負載均衡調(diào)度算法

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

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

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

2.1.1 輪叫調(diào)度

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

2.1.2 加權(quán)輪叫調(diào)度

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

2.1.3 目標地址散列調(diào)度

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

2.1.4 源地址散列調(diào)度

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

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

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

2.2.1 最小連接調(diào)度

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

2.2.2 加權(quán)最小連接調(diào)度

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

2.2.3 最少等待隊列調(diào)度

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

2.2.4 最少利用率調(diào)度

該算法比較服務(wù)器各資源利用率的大小，把任務(wù)分配到資源利用率最少的服務(wù)器上。調(diào)度算法主要有：最少CPU利用率調(diào)度，最少內(nèi)存利用率調(diào)度等。

2.3 動靜結(jié)合調(diào)度算法

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

2.3.1 閾值(加權(quán))輪轉(zhuǎn)調(diào)度

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

3 結(jié)束語

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

參考文獻：

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

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

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

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

[5] 黃愷，徐志偉.可擴展并行計算技術(shù)結(jié)構(gòu)與編程[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] 曾東海，劉海等.集群負載調(diào)度算法性能評價[J].計算機工程，2006.32(11):78-79