負(fù)載均衡技術(shù)綜述

1、負(fù)載均衡技術(shù)綜述*Supported by the * Foundation of China under Grant No.*, * (基金中文完整名稱(chēng)); the * Foundation of China under Grant No.*, * (基金中文完整名稱(chēng)) 作者簡(jiǎn)介: 殷瑋瑋(1992),女,河南舞陽(yáng)人,碩士,主要研究領(lǐng)域?yàn)榉植际接?jì)算,負(fù)載均衡. 殷瑋瑋1+ 1(南京大學(xué) 軟件學(xué)院,江蘇 南京 ) Overview of Load Balancing TechnologyYIN Wei-Wei1+1(Department of Software Institute, Nanji

2、ng University, Nanjing , China) + Corresponding author: Phn +86-*-*-*, Fax +86-*-*-*, E-mail: , Received 2000-00-00; Accepted 2000-00-00Yin WW. Overview of Load Balancing Technology. Journal of Software, 2004,15(1):00000000./1000-9825/15/0000.

3、htmAbstract:Load balance technology based on existing network structure, provides a cheap and efficient method for expanding bandwidth of the server and increase the server throughput, strengthens network data processing ability, increases network flexibility and availability. This paper introduces

4、in detail the three aspects: the classification of load balancing, load balancing and load balancing algorithm, then compares the load balancing algorithm commonly used and their advantages and disadvantages, and describes the dynamic load balancing strategy and three kinds of scheduling methods.Key

5、 words:load balancing technology; the load conditions; the static load balancing algorithm; the dynamic load balancing algorithm摘 要:負(fù)載均衡技術(shù)基于現(xiàn)有網(wǎng)絡(luò)結(jié)構(gòu)，提供了一種擴(kuò)展服務(wù)器帶寬和增加服務(wù)器吞吐量的廉價(jià)有效的方法，加強(qiáng)了網(wǎng)絡(luò)數(shù)據(jù)處理能力，提高了網(wǎng)絡(luò)的靈活性和可用性。本文從負(fù)載均衡技術(shù)的分類(lèi)、負(fù)載均衡技術(shù)和負(fù)載均衡算法三個(gè)方面對(duì)負(fù)載均衡做了詳細(xì)介紹，對(duì)常用負(fù)載均衡算法做了優(yōu)缺點(diǎn)比較，并對(duì)動(dòng)態(tài)負(fù)載均衡算法遵循的策略和三種調(diào)度方式做了闡述。關(guān)鍵詞: 負(fù)載均衡技術(shù)

6、; 負(fù)載狀況；靜態(tài)負(fù)載均衡算法；動(dòng)態(tài)負(fù)載均衡算法中圖法分類(lèi)號(hào):*文獻(xiàn)標(biāo)識(shí)碼: A 隨著大規(guī)模并行分布處理系統(tǒng)，特別是網(wǎng)絡(luò)工作站機(jī)群系統(tǒng)的廣泛應(yīng)用，如何采取有效的調(diào)度策略來(lái)平衡各結(jié)點(diǎn)(機(jī))的負(fù)載，從而提高整個(gè)系統(tǒng)資源的利用率，已成為人們的研究熱點(diǎn)。負(fù)載均衡技術(shù)基于現(xiàn)有網(wǎng)絡(luò)結(jié)構(gòu)，提供了一種擴(kuò)展服務(wù)器帶寬和增加服務(wù)器吞吐量的廉價(jià)有效的方法，加強(qiáng)了網(wǎng)絡(luò)數(shù)據(jù)處理能力，提高了網(wǎng)絡(luò)的靈活性和可用性。負(fù)載均衡的應(yīng)用，能夠有效地解決網(wǎng)絡(luò)擁塞問(wèn)題，能夠就近提供服務(wù)，實(shí)現(xiàn)地理位置無(wú)關(guān)性(異地負(fù)載均衡)。同時(shí)，這項(xiàng)技術(shù)還能提高服務(wù)器的響應(yīng)速度，提高服務(wù)器及其它資源的利用效率，避免網(wǎng)絡(luò)關(guān)鍵部位出現(xiàn)單點(diǎn)失效，從而為用戶(hù)提

7、供更好的訪(fǎng)問(wèn)質(zhì)量。1 負(fù)載均衡技術(shù)的分類(lèi) 1.1 軟件和硬件負(fù)載均衡從負(fù)載均衡采用的設(shè)備可將其分為軟件負(fù)載均衡和硬件負(fù)載均衡。軟件負(fù)載均衡解決方案是指在一臺(tái)或多臺(tái)服務(wù)器相應(yīng)的操作系統(tǒng)上安裝一個(gè)或多個(gè)附加軟件來(lái)實(shí)現(xiàn)負(fù)載均衡，如DNS(Domain Name Server) Load Balance等，它的優(yōu)點(diǎn)是基于特定環(huán)境，配置簡(jiǎn)單，使用靈活，成本低廉，可以滿(mǎn)足一般的負(fù)載均衡需求。軟件解決方案缺點(diǎn)也較多，因?yàn)槊颗_(tái)服務(wù)器上安裝額外的軟件運(yùn)行會(huì)消耗系統(tǒng)不定量的資源，越是功能強(qiáng)大的模塊，消耗得越多，所以當(dāng)連接請(qǐng)求特別大的時(shí)候，軟件本身會(huì)成為服務(wù)器工作成敗的一個(gè)關(guān)鍵；軟件可擴(kuò)展性并不是很好，受到操作系統(tǒng)

8、的限制；由于操作系統(tǒng)本身的Bug 往往會(huì)引起安全問(wèn)題。硬件負(fù)載均衡解決方案是直接在服務(wù)器和外部網(wǎng)絡(luò)間安裝負(fù)載均衡設(shè)備，這種設(shè)備我們通常稱(chēng)之為負(fù)載均衡器，由于專(zhuān)門(mén)的設(shè)備完成專(zhuān)門(mén)的任務(wù)，獨(dú)立于操作系統(tǒng)，整體性能得到大幅提高，加上多樣化的負(fù)載均衡策略，智能化的流量管理，可達(dá)到最佳的負(fù)載均衡需求1。1.2 本地和全局負(fù)載均衡負(fù)載均衡從其應(yīng)用的地理結(jié)構(gòu)上分為本地負(fù)載均衡(Local Load Balance)和全局負(fù)載均衡(Global Load Balance，也叫地域負(fù)載均衡)，本地負(fù)載均衡是指對(duì)本地的服務(wù)器群做負(fù)載均衡，全局負(fù)載均衡是指對(duì)分別放置在不同的地理位置、有不同網(wǎng)絡(luò)結(jié)構(gòu)的服務(wù)器群間做負(fù)載均

9、衡。本地負(fù)載均衡能有效地解決數(shù)據(jù)流量過(guò)大、網(wǎng)絡(luò)負(fù)荷過(guò)重的問(wèn)題，并且不需花費(fèi)昂貴開(kāi)支購(gòu)置性能卓越的服務(wù)器，充分利用現(xiàn)有設(shè)備，避免服務(wù)器單點(diǎn)故障造成數(shù)據(jù)流量的損失。其有靈活多樣的均衡策略把數(shù)據(jù)流量合理地分配給服務(wù)器群內(nèi)的服務(wù)器共同負(fù)擔(dān)。即使是再給現(xiàn)有服務(wù)器擴(kuò)充升級(jí)，也只是簡(jiǎn)單地增加一個(gè)新的服務(wù)器到服務(wù)群中，而不需改變現(xiàn)有網(wǎng)絡(luò)結(jié)構(gòu)、停止現(xiàn)有的服務(wù)。全局負(fù)載均衡主要用于在一個(gè)多區(qū)域擁有自己服務(wù)器的站點(diǎn)，為了使全球用戶(hù)只以一個(gè)IP 地址或域名就能訪(fǎng)問(wèn)到離自己最近的服務(wù)器，從而獲得最快的訪(fǎng)問(wèn)速度；也可用于子公司分散站點(diǎn)分布廣的大公司通過(guò)Intranet(企業(yè)內(nèi)部互聯(lián)網(wǎng))來(lái)達(dá)到資源統(tǒng)一合理分配的目的。1.3

10、 靜態(tài)和動(dòng)態(tài)負(fù)載均衡負(fù)載均衡包括靜態(tài)負(fù)載平衡和動(dòng)態(tài)負(fù)載平衡。只是利用系統(tǒng)負(fù)載的平均信息，而忽視系統(tǒng)當(dāng)前的負(fù)載狀況的方法被稱(chēng)為靜態(tài)負(fù)載均衡；根據(jù)系統(tǒng)當(dāng)前的負(fù)載狀況來(lái)調(diào)整任務(wù)劃分的方法被稱(chēng)為動(dòng)態(tài)負(fù)載均衡2。此內(nèi)容將在第3小節(jié)詳述。1.4 網(wǎng)絡(luò)層次上的負(fù)載均衡針對(duì)網(wǎng)絡(luò)上負(fù)載過(guò)重的不同瓶頸所在，從網(wǎng)絡(luò)的不同層次入手，我們可以采用相應(yīng)的負(fù)載均衡技術(shù)來(lái)解決現(xiàn)有問(wèn)題。隨著帶寬增加，數(shù)據(jù)流量不斷增大，網(wǎng)絡(luò)核心部分的數(shù)據(jù)接口將面臨瓶頸問(wèn)題，原有的單一線(xiàn)路將很難滿(mǎn)足需求，而且線(xiàn)路的升級(jí)又過(guò)于昂貴甚至難以實(shí)現(xiàn)，這時(shí)就可以考慮采用鏈路聚合(Trunking)技術(shù)。鏈路聚合技術(shù)(第二層負(fù)載均衡)將多條物理鏈路當(dāng)作一條單

11、一的聚合邏輯鏈路使用，網(wǎng)絡(luò)數(shù)據(jù)流量由聚合邏輯鏈路中所有物理鏈路共同承擔(dān)，由此在邏輯上增大了鏈路的容量，使其能滿(mǎn)足帶寬增加的需求。2 負(fù)載均衡技術(shù)負(fù)載均衡有兩方面的含義：首先，將大量的并發(fā)訪(fǎng)問(wèn)或數(shù)據(jù)流量分擔(dān)到多臺(tái)節(jié)點(diǎn)設(shè)備上分別處理，減少用戶(hù)等待響應(yīng)的時(shí)間；其次，單個(gè)重負(fù)載的運(yùn)算分擔(dān)到多臺(tái)節(jié)點(diǎn)設(shè)備上做并行處理，每個(gè)節(jié)點(diǎn)設(shè)備處理結(jié)束后，將結(jié)果匯總，返回給用戶(hù)，系統(tǒng)處理能力得到大幅度提高。負(fù)載均衡能夠均衡所有的服務(wù)器和應(yīng)用之間的通信負(fù)載，根據(jù)實(shí)時(shí)響應(yīng)時(shí)間進(jìn)行判斷，將任務(wù)交由負(fù)載最輕的服務(wù)器來(lái)處理，以實(shí)現(xiàn)真正的智能通信管理和最佳的服務(wù)性能。目前，負(fù)載均衡技術(shù)面臨三大問(wèn)題：服務(wù)器的負(fù)載狀況的評(píng)價(jià)、如何獲取

12、以及獲取后如何處理3。2.1 負(fù)載狀況2.1.1 負(fù)載狀況的評(píng)價(jià)負(fù)載狀況的評(píng)價(jià)由三類(lèi)組成：靜態(tài)的、統(tǒng)計(jì)類(lèi)的和動(dòng)態(tài)的。靜態(tài)的由資源決定，可以數(shù)字化評(píng)價(jià)；統(tǒng)計(jì)類(lèi)的只能作為網(wǎng)站擴(kuò)充的依據(jù)；動(dòng)態(tài)地使用探測(cè)結(jié)果來(lái)評(píng)價(jià)。2.1.2 負(fù)載狀況的獲取由于系統(tǒng)中各服務(wù)器根據(jù)所有服務(wù)器的負(fù)載情況來(lái)決定新的用戶(hù)訪(fǎng)問(wèn)請(qǐng)求的取舍，因此，各服務(wù)器必須知道其他服務(wù)器的負(fù)載狀況，這要求每個(gè)服務(wù)器必須將自己的當(dāng)前負(fù)載及時(shí)通知其他服務(wù)器。探知負(fù)載狀況的技術(shù)主要有3種：1) 利用agent技術(shù)使用網(wǎng)管協(xié)議SNMP：在需要的服務(wù)器上運(yùn)行設(shè)計(jì)的agent，定時(shí)通知分配器，從而得到服務(wù)器的確切情況。2) 第三方的軟件：有一些第三方開(kāi)發(fā)的

13、軟件可以完成這種工作，需要分配器有相應(yīng)的接口，從而可以調(diào)整分配的結(jié)果。3) 自己開(kāi)發(fā)軟件去主動(dòng)獲?。鹤詈?jiǎn)單的集成方法就是自己去開(kāi)發(fā)，由分配器去探測(cè)服務(wù)器的負(fù)載狀況。2.2 負(fù)載均衡技術(shù)根據(jù)實(shí)現(xiàn)層次不同，可將負(fù)載均衡技術(shù)分為如下幾類(lèi)：2.2.1 基于客戶(hù)端的負(fù)載均衡這種模式需要每個(gè)客戶(hù)程序均具備一定的服務(wù)器集群知識(shí)，在客戶(hù)端運(yùn)行特定的程序，該程序通過(guò)定期或不定期的收集服務(wù)器群的運(yùn)行參數(shù)：CPU占用情況、磁盤(pán)IO、內(nèi)存等動(dòng)態(tài)信息，再根據(jù)某種選擇策略，找到可以提供服務(wù)的最佳服務(wù)器，將本地的應(yīng)用請(qǐng)求發(fā)向它。整個(gè)過(guò)程對(duì)于應(yīng)用程序來(lái)說(shuō)是完全透明的，所有的工作都在運(yùn)行時(shí)處理。比如，在Berkeley研究的s

14、mart client中，服務(wù)提供一個(gè)JavaApplet在客戶(hù)方瀏覽器中運(yùn)行，Applet向各個(gè)服務(wù)器發(fā)請(qǐng)求來(lái)收集服務(wù)器的負(fù)載等信息，再根據(jù)這些信息將客戶(hù)的請(qǐng)求發(fā)到相應(yīng)的服務(wù)器；當(dāng)服務(wù)器沒(méi)有響應(yīng)時(shí)，Applet向另一個(gè)服務(wù)器轉(zhuǎn)發(fā)請(qǐng)求，實(shí)現(xiàn)高可用性。這種技術(shù)存在明顯的通用性問(wèn)題，因?yàn)槊恳粋€(gè)客戶(hù)端都要安裝這個(gè)特殊的程序；并且，為了保證應(yīng)用層的透明運(yùn)行，需要針對(duì)每一個(gè)應(yīng)用程序加以修改，要對(duì)代碼進(jìn)行重新開(kāi)發(fā)，工作量比較大，因而這種技術(shù)僅適用于特殊的應(yīng)用場(chǎng)合。2.2.2 應(yīng)用服務(wù)器的負(fù)載均衡如果將客戶(hù)端的負(fù)載均衡層移植到某一個(gè)中間平臺(tái)，形成三層結(jié)構(gòu)，則客戶(hù)端應(yīng)用可以不需要做特殊的修改，透明的通過(guò)中間層

15、應(yīng)用服務(wù)器將請(qǐng)求均衡到相應(yīng)的服務(wù)結(jié)點(diǎn)。比較常見(jiàn)的實(shí)現(xiàn)手段就是反向代理技術(shù)。通過(guò)反向代理服務(wù)器，可以將請(qǐng)求按一定的策略轉(zhuǎn)發(fā)給多臺(tái)服務(wù)器，或者可以直接將緩存的數(shù)據(jù)返回客戶(hù)端，這樣的加速模式在一定程度上可以提升客戶(hù)端的訪(fǎng)問(wèn)速度，從而達(dá)到負(fù)載均衡的目的，目前廣泛采用的有HTTP 反向代理技術(shù)。然而，反向代理技術(shù)必須為每一種服務(wù)都專(zhuān)門(mén)開(kāi)發(fā)一個(gè)反向代理服務(wù)器，這樣就限制了反向代理負(fù)載均衡技術(shù)的應(yīng)用范圍，現(xiàn)在一般都用于對(duì)Web服務(wù)器的負(fù)載均衡；隨著并發(fā)連接數(shù)量的增加，代理服務(wù)器本身的負(fù)載也會(huì)變得非常大，最后反向代理服務(wù)器本身會(huì)成為服務(wù)的瓶頸。2.2.3 基于DNS域名系統(tǒng)的負(fù)載均衡最早的負(fù)載均衡技術(shù)是通過(guò)D

16、NS輪循來(lái)實(shí)現(xiàn)的，DNS負(fù)載均衡技術(shù)是在DNS服務(wù)器中為同一個(gè)主機(jī)名配置多個(gè)IP地址，在應(yīng)答DNS查詢(xún)時(shí)，DNS服務(wù)器對(duì)每個(gè)查詢(xún)將以DNS文件中主機(jī)記錄的IP 地址按順序返回不同的解析結(jié)果，將客戶(hù)端的訪(fǎng)問(wèn)引導(dǎo)到不同的機(jī)器上去，使得不同的客戶(hù)端訪(fǎng)問(wèn)不同的服務(wù)器，從而達(dá)到負(fù)載均衡的目的。其中最為著名的是NCSA Web服務(wù)器?；贒NS的方法簡(jiǎn)單易行，沒(méi)有瓶頸問(wèn)題，但是不能考慮距離遠(yuǎn)近，減少記錄的有效期TTL易造成網(wǎng)絡(luò)信息冗余。盡管如此，它還是一種非常有效的做法，被包括Yahoo在內(nèi)的很多大型網(wǎng)站采用4。DNS負(fù)載均衡存在的缺點(diǎn)是DNS負(fù)載均衡采用的是簡(jiǎn)單的輪循負(fù)載算法，無(wú)法區(qū)分服務(wù)器的差異，不能

17、做到為性能較好的服務(wù)器多分配請(qǐng)求。此外，為了使地址能隨機(jī)分配，保證不同的客戶(hù)計(jì)算機(jī)能均勻獲得不同的地址，就應(yīng)使刷新時(shí)間盡量短，不同地方的DNS服務(wù)器能更新對(duì)應(yīng)的地址，達(dá)到隨機(jī)獲得地址，然而將過(guò)期時(shí)間設(shè)置得過(guò)短，將使DNS流量大增，而造成額外的網(wǎng)絡(luò)問(wèn)題。2.2.4 高層協(xié)議的負(fù)載均衡高層協(xié)議負(fù)載均衡技術(shù)通常是指Web內(nèi)容交換或七層交換，該方法綜合考慮客戶(hù)請(qǐng)求的內(nèi)容，如URL名稱(chēng)、類(lèi)型、Cookies等，提供了一種對(duì)訪(fǎng)問(wèn)流量的高層控制方式。Web內(nèi)容交換技術(shù)檢查所有的HTTP報(bào)頭，根據(jù)報(bào)頭內(nèi)的信息來(lái)執(zhí)行負(fù)載均衡的決策。常見(jiàn)的技術(shù)實(shí)現(xiàn)主要是依靠HTTP協(xié)議中的重定向功能等。Web內(nèi)容交換負(fù)載均衡優(yōu)點(diǎn)

18、表現(xiàn)在如下幾個(gè)方面：1) 通過(guò)對(duì)HTTP報(bào)頭的檢查，可以檢測(cè)出HTTP400、500和600系列的錯(cuò)誤信息，因而能透明地將連接請(qǐng)求重新定向到另一臺(tái)服務(wù)器，避免應(yīng)用層故障。2) 可根據(jù)流經(jīng)的數(shù)據(jù)類(lèi)型(如判斷數(shù)據(jù)包是圖像文件、壓縮文件或多媒體文件格式等)，把數(shù)據(jù)流量引向相應(yīng)內(nèi)容的服務(wù)器來(lái)處理，增加系統(tǒng)性能。3) 能根據(jù)連接請(qǐng)求的類(lèi)型，如是普通文本、圖像等靜態(tài)文檔請(qǐng)求，還是asp.cgi等的動(dòng)態(tài)文檔請(qǐng)求，把相應(yīng)的請(qǐng)求引向相應(yīng)的服務(wù)器來(lái)處理，提高系統(tǒng)的性能及安全性。2.2.5 網(wǎng)絡(luò)接入負(fù)載均衡即第四層交換技術(shù)，很多硬件廠(chǎng)商已經(jīng)將這種技術(shù)集成在他們的交換機(jī)或路由器中，已經(jīng)被廣泛用于構(gòu)建各種服務(wù)器集群。它

19、一般采用隨機(jī)選擇、根據(jù)服務(wù)器的連接數(shù)量或者響應(yīng)時(shí)間進(jìn)行選擇的負(fù)載均衡策略來(lái)分配負(fù)載，對(duì)外提供一個(gè)一致的IP 地址，并映射為多個(gè)內(nèi)部IP地址，對(duì)每次TCP和UDP連接請(qǐng)求，根據(jù)其訪(fǎng)問(wèn)的端口號(hào)，按照即定的策略動(dòng)態(tài)選擇一個(gè)內(nèi)部地址，將數(shù)據(jù)包轉(zhuǎn)發(fā)到該地址上，達(dá)到負(fù)載均衡的目的，例如采用NAT負(fù)載均衡技術(shù)。NAT負(fù)載均衡是一種比較完善的負(fù)載均衡技術(shù)，起著NAT負(fù)載均衡功能的設(shè)備一般處于內(nèi)部網(wǎng)到外部網(wǎng)間的網(wǎng)關(guān)位置，如路由器、防火墻、四層交換機(jī)、專(zhuān)用負(fù)載均衡器等均衡算法也較靈活，如隨機(jī)選擇、最少連接數(shù)及響應(yīng)時(shí)間等來(lái)分配負(fù)載，NAT負(fù)載均衡可以通過(guò)軟件或者硬件方式來(lái)實(shí)現(xiàn)。2.2.6 傳輸鏈路負(fù)載均衡隨著高帶寬

20、應(yīng)用需求不斷增大時(shí)( 例如Web訪(fǎng)問(wèn)、文檔傳輸及VOD視頻、IP電話(huà)等)，網(wǎng)絡(luò)核心部位如交換機(jī)、服務(wù)器、路由器等的數(shù)據(jù)鏈路將產(chǎn)生瓶頸問(wèn)題，這將會(huì)導(dǎo)致客戶(hù)應(yīng)用請(qǐng)求的響應(yīng)時(shí)間大大增加，同時(shí)單一的訪(fǎng)問(wèn)鏈路不可避免的存在單點(diǎn)故障問(wèn)題，網(wǎng)絡(luò)的可靠性沒(méi)有保障。鏈路聚合技術(shù)為消除傳輸鏈路上的瓶頸與不可靠因素提供了成本低廉的解決方案。鏈路聚合技術(shù)是將多條線(xiàn)路的傳輸容量融合成一個(gè)單一的邏輯鏈路來(lái)使用，每條線(xiàn)路都用于網(wǎng)絡(luò)傳輸，擴(kuò)大了網(wǎng)絡(luò)的傳輸容量，其中的某條線(xiàn)路斷開(kāi)也不會(huì)影響到網(wǎng)絡(luò)的運(yùn)行。目前廣泛采用的鏈路聚合技術(shù)主要有以下幾種：1) IMUX反轉(zhuǎn)多路復(fù)用器工作在T1/E1的比特層，可以捆綁多個(gè)同步的DS1信道來(lái)

21、傳輸數(shù)據(jù)，實(shí)現(xiàn)負(fù)載均衡，該技術(shù)目前已經(jīng)廣泛用于廣域網(wǎng)接入。2) IMA是另外一種基于ATM的多線(xiàn)路的反向多路復(fù)用技術(shù)，能夠運(yùn)行在使用ATM路由器的平臺(tái)上。3) 基于路由器的多重鏈路PPP，又稱(chēng)MP或MLP，是應(yīng)用于使用PPP封裝數(shù)據(jù)鏈路的路由器負(fù)載平衡技術(shù)。MP可以將大的PPP數(shù)據(jù)包分解成小的數(shù)據(jù)段，根據(jù)一定策略再將其分發(fā)給平行的多個(gè)線(xiàn)路，主要用于廣域網(wǎng)鏈路的備份及廣域網(wǎng)連接帶寬的擴(kuò)展。4) 基于網(wǎng)卡的鏈路聚合，自動(dòng)負(fù)載均衡(Adaptive Load Balancing，簡(jiǎn)稱(chēng)ALB)和網(wǎng)卡冗余(Adapter Fault Tolerance，簡(jiǎn)稱(chēng)AFT)已經(jīng)在很多產(chǎn)品中實(shí)現(xiàn)，如Intel的多

22、端口網(wǎng)卡，采用這些技術(shù)可以大大提高了服務(wù)器的網(wǎng)絡(luò)吞吐量及可靠性，不過(guò)這項(xiàng)技術(shù)需要操作系統(tǒng)驅(qū)動(dòng)層和網(wǎng)絡(luò)交換機(jī)的支持。3 常用負(fù)載均衡算法影響負(fù)載均衡的因素有三個(gè)，分別是算法、網(wǎng)絡(luò)拓?fù)湟约柏?fù)載均衡的粒度5，下文對(duì)負(fù)載均衡算法進(jìn)行研究。負(fù)載均衡算法包括兩種：靜態(tài)負(fù)載均衡和動(dòng)態(tài)負(fù)載均衡。3.1 靜態(tài)負(fù)載均衡算法靜態(tài)負(fù)載均衡不管各個(gè)成員服務(wù)器運(yùn)行時(shí)刻的負(fù)載情況，而只是根據(jù)預(yù)先設(shè)定的分配方案對(duì)用戶(hù)的請(qǐng)求進(jìn)行分配。輪叫調(diào)度算法（Round Robin）也是一種比較常見(jiàn)的靜態(tài)算法，即把客戶(hù)請(qǐng)求依次分派給各個(gè)成員服務(wù)器，例如，把第i個(gè)請(qǐng)求分配給服務(wù)器Sk，k = i mod N。該算法的優(yōu)點(diǎn)是其簡(jiǎn)潔性，無(wú)需記錄

23、當(dāng)前所有連接的狀態(tài)，是一種無(wú)狀態(tài)調(diào)度。輪叫調(diào)度算法假設(shè)所有服務(wù)器處理性能均相同，相對(duì)簡(jiǎn)單，但是不適用于服務(wù)器組中處理性能不一的情況，而且當(dāng)請(qǐng)求服務(wù)時(shí)間變化較大時(shí)，容易導(dǎo)致服務(wù)器間的負(fù)載不平衡6。對(duì)于異構(gòu)系統(tǒng)，也可以采用上述類(lèi)似的按處理能力比例分配的處理方法7。3.2 動(dòng)態(tài)負(fù)載均衡算法由于影響客戶(hù)訪(fǎng)問(wèn)頻率的因素很多，且難以預(yù)測(cè)，因此靜態(tài)調(diào)度往往不能令人滿(mǎn)意。此時(shí)可以根據(jù)各個(gè)服務(wù)器上任務(wù)執(zhí)行實(shí)際狀態(tài)的變化，隨時(shí)動(dòng)態(tài)地調(diào)整任務(wù)分配，使用系統(tǒng)狀態(tài)信息進(jìn)行負(fù)載調(diào)整。目前已提出了很多動(dòng)態(tài)算法，如Pick-K算法，Basic LI和Aggressive LI算法8，Pick-KX算法9等。3.2.1 典型動(dòng)

24、態(tài)負(fù)載分配算法所遵循的策略1) 啟動(dòng)策略發(fā)送者啟動(dòng)：該算法由發(fā)送者觸發(fā)負(fù)載分配。當(dāng)系統(tǒng)中的某個(gè)處理機(jī)結(jié)點(diǎn)的負(fù)載W(i)W1*，即為重載結(jié)點(diǎn)，稱(chēng)該結(jié)點(diǎn)為發(fā)送者。它主動(dòng)尋找一個(gè)負(fù)載輕的處理機(jī)結(jié)點(diǎn)來(lái)接收自己的一部分負(fù)載。顯然當(dāng)整個(gè)系統(tǒng)的平均負(fù)載為輕載時(shí)，發(fā)送者能夠容易找到負(fù)載的接收者，因此系統(tǒng)比較穩(wěn)定。但當(dāng)其為重載時(shí)，該系統(tǒng)中的大部分處理機(jī)結(jié)點(diǎn)的負(fù)載都處于重載，所以很難找到負(fù)載輕的處理機(jī)結(jié)點(diǎn)，反而使發(fā)送者結(jié)點(diǎn)的負(fù)載更加惡化，嚴(yán)重影響系統(tǒng)性能。接收者啟動(dòng)：該算法是由接收者觸發(fā)負(fù)載分配。當(dāng)系統(tǒng)中的某個(gè)處理機(jī)結(jié)點(diǎn)的負(fù)載W(i)W2*，輕載時(shí)，即稱(chēng)該結(jié)點(diǎn)為接收者。它必須主動(dòng)尋找發(fā)送者，以便接收一部分負(fù)載。當(dāng)

25、整個(gè)系統(tǒng)的平均負(fù)載處于重載時(shí)，接收者可以容易地找到一個(gè)發(fā)送者，這種情況下，它優(yōu)于發(fā)送者啟動(dòng)算法。接收者啟動(dòng)算法的主要缺點(diǎn)是，當(dāng)系統(tǒng)整體負(fù)載相對(duì)較少時(shí)，過(guò)多的任務(wù)請(qǐng)求占用了帶寬，延遲了重服務(wù)器的任務(wù)執(zhí)行。對(duì)稱(chēng)啟動(dòng)：對(duì)稱(chēng)啟動(dòng)算法是結(jié)合了接收者啟動(dòng)算法和發(fā)送者啟動(dòng)算法兩者的優(yōu)點(diǎn)。當(dāng)整個(gè)系統(tǒng)平均負(fù)載處于輕載時(shí)，用發(fā)送者啟動(dòng)算法，負(fù)載重的處理機(jī)結(jié)點(diǎn)很容易找到可以接收其負(fù)載的處理機(jī)結(jié)點(diǎn)；當(dāng)處于重載時(shí)，使用接收者啟動(dòng)算法較合適，此時(shí)負(fù)載較輕的處理機(jī)結(jié)點(diǎn)很容易找到負(fù)載重的處理機(jī)結(jié)點(diǎn)，以便接收一部分負(fù)載，這樣該算法就避免了接收者和發(fā)送者啟動(dòng)算法的缺點(diǎn)。自適應(yīng)算法：自適應(yīng)算法中，每臺(tái)處理機(jī)結(jié)點(diǎn)利用查詢(xún)過(guò)程中搜集的

26、信息，將所有的處理機(jī)結(jié)點(diǎn)分為發(fā)送、接收和中立者(重載、輕載和適載)，并用3張表(發(fā)送、接收和中立者表)11分別記錄這些結(jié)點(diǎn)的處理機(jī)名。當(dāng)處理機(jī)結(jié)點(diǎn)為發(fā)送者時(shí)，啟動(dòng)發(fā)送者算法，當(dāng)處理機(jī)結(jié)點(diǎn)為接收者時(shí)，啟動(dòng)接收者算法。自適應(yīng)算法的優(yōu)點(diǎn)是：查詢(xún)時(shí)查詢(xún)結(jié)點(diǎn)和被查詢(xún)結(jié)點(diǎn)均能更新自己的3張表，真實(shí)地記錄系統(tǒng)中所有處理機(jī)結(jié)點(diǎn)的狀態(tài)信息。每個(gè)結(jié)點(diǎn)可以根據(jù)自身的3張表選擇合適的處理機(jī)結(jié)點(diǎn)發(fā)送或接收負(fù)載。顯然，當(dāng)系統(tǒng)重載時(shí)，由于處理機(jī)結(jié)點(diǎn)的接收者表多為空，從而抑制發(fā)送者啟動(dòng)算法部分，由接收者啟動(dòng)算法進(jìn)行負(fù)載分配；系統(tǒng)輕載時(shí)，由于處理機(jī)結(jié)點(diǎn)發(fā)送者表多數(shù)為空，從而抑制接收者啟動(dòng)算法部分，由發(fā)送者啟動(dòng)算法進(jìn)行負(fù)載分配。

27、其缺點(diǎn)是：系統(tǒng)中的每臺(tái)處理機(jī)結(jié)點(diǎn)均保存3張表，浪費(fèi)存儲(chǔ)空間。在該算法中主要的開(kāi)銷(xiāo)在于一個(gè)處理機(jī)結(jié)點(diǎn)對(duì)另一個(gè)處理機(jī)結(jié)點(diǎn)的查詢(xún)。由于在表中選擇處理機(jī)是隨機(jī)的，而且這3個(gè)表保存的是整個(gè)系統(tǒng)的處理機(jī)結(jié)點(diǎn)的信息，所以在表中不但不能很快選擇到合適的處理機(jī)結(jié)點(diǎn)，使系統(tǒng)資源不能被充分利用，而且還會(huì)干擾其它正在運(yùn)行中的處理機(jī)結(jié)點(diǎn)，隨著其結(jié)點(diǎn)的增多，系統(tǒng)的額外開(kāi)銷(xiāo)將會(huì)越來(lái)越多10。2) 轉(zhuǎn)移策略每臺(tái)服務(wù)器有兩個(gè)控制閥值：過(guò)載標(biāo)志（HWM）和輕載標(biāo)志（LWM）。當(dāng)服務(wù)器的負(fù)載大于HWM 時(shí)，需要將部分負(fù)載轉(zhuǎn)移出去；當(dāng)服務(wù)器的負(fù)載小于LWM 時(shí)，需要接收部分新的負(fù)載。負(fù)載轉(zhuǎn)移不是原子動(dòng)作，出現(xiàn)沖突時(shí)，可以選擇強(qiáng)制執(zhí)行

28、或重新選擇宿主服務(wù)器。3) 選擇策略啟動(dòng)服務(wù)器選擇最合適轉(zhuǎn)移，最能起平衡作用的任務(wù)發(fā)送給合適的目標(biāo)服務(wù)器。常用的策略有搶占式任務(wù)遷移和非搶占式的負(fù)載共享兩種。4) 收益性策略使用不平衡因子來(lái)評(píng)估系統(tǒng)平衡負(fù)載是否有收益。該策略的原則是轉(zhuǎn)移所產(chǎn)生的開(kāi)銷(xiāo)應(yīng)小于所產(chǎn)生的響應(yīng)時(shí)間收益。負(fù)載代價(jià)來(lái)自三個(gè)方面：服務(wù)器之間傳播的負(fù)載信息；任務(wù)轉(zhuǎn)移前的選擇決策過(guò)程；任務(wù)移植的通信延遲。5) 位置策略位置策略用來(lái)尋找合適的服務(wù)器共享負(fù)載。常用的算法有Shortest Queue、Round-Robin、Random、K-Subset 和最近鄰居等。6) 信息策略決定收集系統(tǒng)中其他服務(wù)器狀態(tài)信息的時(shí)機(jī)、收集的方位和

29、收集的信息。信息策略設(shè)計(jì)越合理，每臺(tái)服務(wù)器收集的信息就越準(zhǔn)確，信息量就越大，負(fù)載均衡效果就越好。3.2.2 動(dòng)態(tài)負(fù)載平衡調(diào)度1) 集中式調(diào)度在集中式調(diào)度中，所有任務(wù)的調(diào)度都是由一個(gè)調(diào)度服務(wù)器，即“負(fù)載均衡器”來(lái)完成的。“負(fù)載均衡器”負(fù)責(zé)搜集系統(tǒng)負(fù)載信息，并決定負(fù)載平衡調(diào)度方案。集中式調(diào)度實(shí)現(xiàn)比較簡(jiǎn)單，很容易獲得各服務(wù)器的負(fù)載信息，可以根據(jù)NodeLoadList列表進(jìn)行負(fù)載快速轉(zhuǎn)移，具有控制集中，調(diào)度有力等優(yōu)點(diǎn)。但在結(jié)點(diǎn)數(shù)較多的大規(guī)模并行分布系統(tǒng)中，由于各結(jié)點(diǎn)與調(diào)度服務(wù)器的通訊成為瓶頸，所以調(diào)度開(kāi)銷(xiāo)比較大12,13,14；另一方面，在客戶(hù)終端任務(wù)到達(dá)很密集的情況下，任務(wù)在“負(fù)載均衡器”上的排隊(duì)

30、等待時(shí)間就會(huì)大大增加任務(wù)處理總時(shí)間。所以，除非結(jié)點(diǎn)數(shù)目較少，或者在底層硬件系統(tǒng)中采取比如超級(jí)集線(xiàn)器這樣的一些特殊實(shí)現(xiàn)措施15，否則在分布存儲(chǔ)的并行系統(tǒng)中不大采用集中式平衡調(diào)度方法16。2) 分布式調(diào)度在分布式調(diào)度中，沒(méi)有負(fù)載均衡器，任務(wù)被分配給所有服務(wù)節(jié)點(diǎn)，通過(guò)服務(wù)器間的交互，每臺(tái)服務(wù)器都有其他服務(wù)器的負(fù)載信息，即都有NodeLoadList 列表，由本服務(wù)器完成任務(wù)的調(diào)度，當(dāng)負(fù)載飽和時(shí)可以將一部分任務(wù)轉(zhuǎn)移到其他輕載服務(wù)器。分布式調(diào)度的最大優(yōu)點(diǎn)在于具有良好的可擴(kuò)放性，具有很強(qiáng)的容錯(cuò)能力，不會(huì)出現(xiàn)集中式負(fù)載均衡那樣瓶頸問(wèn)題。目前常用的分布式負(fù)載平衡調(diào)度方法主要有基于隨機(jī)選擇任務(wù)移動(dòng)結(jié)點(diǎn)的概率調(diào)度

31、算法17、根據(jù)負(fù)載變化差額而基于梯度(Gradient)模型的調(diào)度算法18以及自適應(yīng)的近鄰契約算法19等。但是在分布式調(diào)度算法中，每臺(tái)服務(wù)器都需定時(shí)向其他服務(wù)器廣播其負(fù)載信息，發(fā)送負(fù)載信息總數(shù)為：N=n(n-1),其中n 為服務(wù)器總數(shù)目，N 為系統(tǒng)負(fù)載更新信息數(shù)。因此，服務(wù)器之間的交互信息量N 隨著服務(wù)器數(shù)目的增加而成倍增加，將會(huì)占用大量的網(wǎng)絡(luò)資源，從而導(dǎo)致系統(tǒng)性能下降。其次，由于所有服務(wù)器都具有相同的負(fù)載信息表，所有重服務(wù)器都會(huì)把負(fù)載轉(zhuǎn)移到同一臺(tái)輕服務(wù)器，從而導(dǎo)致輕服務(wù)器負(fù)載急劇增大，很快變?yōu)橹胤?wù)器，如此反復(fù)，導(dǎo)致任務(wù)不能及時(shí)處理。3) 混合/層次調(diào)度為了最小化負(fù)載均衡開(kāi)銷(xiāo)，一些負(fù)載均衡方

32、法重在研究如何根據(jù)層次拓?fù)浣Y(jié)構(gòu)來(lái)構(gòu)建一個(gè)層次樹(shù)的問(wèn)題。HBM20利用層次樹(shù)進(jìn)行多級(jí)負(fù)載均衡，根據(jù)層次化的網(wǎng)絡(luò)結(jié)構(gòu)將處理器劃分為多個(gè)組(均衡域)，由這些均衡域組織成一個(gè)層次結(jié)構(gòu)。在層次結(jié)構(gòu)中的每一層，相鄰的域間進(jìn)行負(fù)載均衡，并且從底層至上層，在每層執(zhí)行相同的域間負(fù)載均衡過(guò)程,最后在根節(jié)點(diǎn)完成全局的負(fù)載均衡?；旌喜呗?HybridLB)21類(lèi)似于傳統(tǒng)的層次負(fù)載均衡策略，將處理器劃分為多個(gè)獨(dú)立的、自治的組，并將這些組按層次結(jié)構(gòu)進(jìn)行組織。每層中的每個(gè)子樹(shù)的根節(jié)點(diǎn)與其所有子節(jié)點(diǎn)形成一個(gè)負(fù)載均衡組，根節(jié)點(diǎn)充當(dāng)該均衡組的頭節(jié)點(diǎn)，控制負(fù)載均衡組內(nèi)的負(fù)載均衡過(guò)程，充當(dāng)類(lèi)似集中式策略中央節(jié)點(diǎn)的功能。第i層的根處理

33、器參與由第i+1層(層的序號(hào)由底至上遞增)的頭節(jié)點(diǎn)控制的負(fù)載均衡過(guò)程，但第i層各節(jié)點(diǎn)的子節(jié)點(diǎn)不參與第i+1層的負(fù)載均衡過(guò)程。與HBM不同的是，HybridLB可在不同的層采用不同的策略，并最小化任務(wù)傳輸?shù)木嚯x和數(shù)量以?xún)?yōu)化負(fù)載均衡的通訊開(kāi)銷(xiāo)22。論文22中列舉以上三種調(diào)度常用算法和算法性能比較，此處不再詳述。4 總結(jié)本文通過(guò)負(fù)載均衡技術(shù)分類(lèi)方式、負(fù)載均衡技術(shù)和負(fù)載均衡算法三個(gè)方面對(duì)負(fù)載均衡做了介紹。其中，DLB(動(dòng)態(tài)負(fù)載均衡)是現(xiàn)在應(yīng)用最廣泛的一種方式，隨著新興的多/眾核相關(guān)技術(shù)和應(yīng)用的出現(xiàn)及進(jìn)一步發(fā)展，DLB技術(shù)的重要性日益凸顯。但是現(xiàn)有的動(dòng)態(tài)負(fù)載平衡算法不盡完善，比如有些DLB算法每次運(yùn)行只

34、選擇一個(gè)符合條件( 負(fù)載最輕23、距離最近24、其他約束條件25) 的輕載節(jié)點(diǎn)作為負(fù)載遷移的目標(biāo)節(jié)點(diǎn)，負(fù)載遷移后, 若重載節(jié)點(diǎn)仍過(guò)載，則再次運(yùn)行算法，直至負(fù)載平衡，增加了負(fù)載平衡的時(shí)空開(kāi)銷(xiāo)和系統(tǒng)對(duì)任務(wù)的平均響應(yīng)時(shí)間。針對(duì)此問(wèn)題，論文26中將多個(gè)輕載節(jié)點(diǎn)作為負(fù)載遷移目標(biāo)節(jié)點(diǎn)的多目標(biāo)遷移機(jī)制，對(duì)DLB的性能做了改善。未來(lái)對(duì)于DLB研究主要集中在以下幾個(gè)層面：在系統(tǒng)層次上，通過(guò)考慮拓?fù)浣Y(jié)構(gòu)來(lái)優(yōu)化通訊可提高DLB 策略的性能27, 28, 29, 30；在節(jié)點(diǎn)組層面上進(jìn)行通訊開(kāi)銷(xiāo)優(yōu)化：考慮到節(jié)點(diǎn)內(nèi)的通訊速度遠(yuǎn)快于節(jié)點(diǎn)間通訊的事實(shí)31，研究如何將更多的節(jié)點(diǎn)間通訊密集的任務(wù)劃分到同一節(jié)點(diǎn)內(nèi)可進(jìn)一步優(yōu)化通訊

35、性能；在節(jié)點(diǎn)層面上研究細(xì)粒度劃分與數(shù)據(jù)依賴(lài)性對(duì)性能的影響，設(shè)計(jì)適應(yīng)于統(tǒng)一多核計(jì)算模型和異構(gòu)體系結(jié)構(gòu)的負(fù)載均衡策略來(lái)提高策略的計(jì)算性能、可擴(kuò)展性和可移植性，為提高并行性引入的同步開(kāi)銷(xiāo)代價(jià)大于收益以及計(jì)算具有較大粒度并行性和依賴(lài)度的問(wèn)題時(shí)，需要多少處理器節(jié)點(diǎn)才是恰當(dāng)?shù)牡葐?wèn)題。致謝 在此，感謝給予本文支持的所有著作的作者，尤其要感謝南京大學(xué)軟件學(xué)院葛季棟副教授對(duì)本論文的指導(dǎo)。References:1 Liu XH. Research on Load Balancing Technology. Science & Technology Information, 2007, No12:173174(in

36、 Chinese with English abstract).2 Sun JC, Zhang LB, Chi XB, eds. Network parallel computing and distributed programming environment. Beijing: Science press, 2003.3036.3 Xue J, Li ZZ, Wang YL. The development of load balancing J. Mini micro computer system, 2003, 24(12):21002103.4 Xiao JB, Wang Y. Ap

37、plication of DNS to achieve load balancing Web cluster service J. Computing Systems, 2003(10):5962.5 Hu ZA, Wang L. The relationship between Algorithm, network topology with scheduling frequency and dynamic load balancing J.Computer engineering and science,2000,22(1):104107.6 Yin F. Distributed syst

38、em dynamic load distribution algorithm research J.Microcomputer information, 2009 (18): 9193.7 Wang S, Xiu BX, Xiao WD. The Web server cluster load balancing algorithms J. Computer engineering, 2004, 40(25):7880.8 Dahlin M.Interpreting Stale Load InformationC.In: Proc of the 19th Intl Conf on Distri

39、buted Computing Systems, 1999-05.9 Mitzenmacher M.How Useful is Old InformationC.In: Proc of the 15th Annual ACM.10 Mao M, Pan J. Dynamic Load Balancing Self-adapting Algorithm in Multi-Processor Systems and Its Improvements J. Power of intelligence, 2002(2): 5558.11 Zhu SP. A new way of dynamic loa

40、d balancing algorithm design J. Computer engineering, 1995,16(3):2628.12 Hesham El-Rewini, Theodore G Lewis, Hesham H Ali. Task scheduling. Englewood Cliffs, New Jersey: PTR Prentice Hall, 1994.13 Joosen W, Pollet J.The efficient management of task clusters in a dynamic load balancer. In: Proceeding

41、s of the International Conference94 on Parallel Distributed Systems. Hsinchu, Taiwan, Dec. 1994. 1921.14 Feng MD, Yuen CK. Dynamic load balancing on a distributed system. In: Proceeding s of the 6th Symposium on Parallel and Distributed Processing. Dallas, Texas, Oct. 1994. 2629.15 Gene Eu Jan, Ming

42、-Bo Lin. Effective load balancing on highly parallel multicomputers based on super concentrators. In: Proceedings of the International Conference94 on Parallel Distributed Systems. Hsinchu, Taiwan, Dec. 1994. 1921.16 Chen HP, Ji YC, Chen GL.A general model of distributed dynamic load balancing sched

43、uling J. Journal of software, 1998, 9(1): 2529.17 Soumen Chakrabartietal. Randomized load balancing for tree-structured computation. In: Proceedings of the International Conference 94 on Parallel Distributed Systems. Hsinchu, Taiwan, Dec. 1994. 1921.18 Lin F C H, Keller R M. The gradient model load

44、balancing method. IEEE Transactions on Software Engineering, 1987, SE-13: 3238.19 Shu W, Kale L V. A dynamic scheduling strategy for the Chare-Kernei system. In: Proceedings of Supercomputing89.Reno, Nevada, Nov. 1989. 389398.20 M H Willebeek-LeMair, eds. Strategies for dynamic load balancing on hig

45、hly parallel computers J. IEEE T Parall Distrib, 1993, 4(9):979- 993.21 G B Zheng. Achieving High Performance on Extremely Large Parallel Machines: Performance Prediction and Load BalancingD. Urbana: UIUC, 2005.22 Yang JX, Tan GZ, Wang RS. Review of Parallel and distributed system dynamic load balan

46、cing strategy were J. Journal of electronic, 2010, 38(5): 11221130.23 BAHIJM, CONTASSOTIVIER S, COUTURIER R. Coupling dynamic load balancing with a synchronism in iterative algorithms on the computational gridC.Proceedings of the 17th International Parallel and Distributed Processing Symposium. Nice

47、, France, 2003.24 YANMAZE, TONGUZOK. Location dependent dynamic load balancingC.IEEE Global Telecommunications Conference. St Louis, USA, 2005.25 Wang YB, HYATTR. An improved algorithm of two choices in randomized dynamic load balancing C.Proceedings of the Fifth International Conference on Algorithms and Architectures for Paral