李昕

（陜西工業(yè)職業(yè)技術(shù)學(xué)院 陜西 咸陽 712000）

在INSS中，若寫請求到達，首先判定文件大小，當(dāng)為大文件請求時，必須先采用條帶化技術(shù)對大文件進行切分，以此來提高用戶對文件訪問的并發(fā)性，從而來提高對大文件的訪問性能，然后再將切分后數(shù)據(jù)塊存儲在同一區(qū)域多個節(jié)點上，在INSS中，需要設(shè)計一種基于負載均衡技術(shù)的數(shù)據(jù)放置策略，來避免在分配請求的任務(wù)過程中，某些服務(wù)器工作負載重，某些服務(wù)器工作負載輕。

1 負載均衡技術(shù)

分布式系統(tǒng)中的一個重要問題就是負載均衡問題[1]。分布式系統(tǒng)負載均衡的目標是根據(jù)處理機的性能來分配與其相稱的任務(wù)，以最小化應(yīng)用程序的執(zhí)行時間。對各服務(wù)器來說，就是要根據(jù)負載均衡原則，為每個節(jié)點分配與其實際處理能力相適應(yīng)的請求。這樣可以避免集群中某些服務(wù)器工作負荷重，某些服務(wù)器工作負荷輕。

根據(jù)調(diào)節(jié)策略的不同，可以分為靜態(tài)負載均衡和動態(tài)負載均衡兩類，靜態(tài)調(diào)度算法事先就己經(jīng)確定好了請求任務(wù)的分發(fā)策略，它不管每個任務(wù)的性質(zhì)、所需消耗的系統(tǒng)資源以及各個服務(wù)器運行時刻的負載情況，只是根據(jù)預(yù)先設(shè)定的分配方案對用戶的請求進行分配。

根據(jù)任務(wù)調(diào)度模型的不同，我們又將動態(tài)負載均衡分為集中式控制與分布式控制集中式控制就是在負載均衡系統(tǒng)中設(shè)置一臺中央控制服務(wù)器，我們把它叫做負載調(diào)度器。

2 靜態(tài)負載均衡算法

2.1 輪轉(zhuǎn)調(diào)度算法

輪轉(zhuǎn)調(diào)度（Round Robin Scheduling RR）算法就是以輪轉(zhuǎn)的方式依次將請求務(wù)調(diào)度到不同的服務(wù)器。將所有的服務(wù)器組成一個循環(huán)隊列，當(dāng)請求任務(wù)到達時，每次選取隊頭的服務(wù)器來響應(yīng)當(dāng)前請求任務(wù)，即調(diào)度器調(diào)度執(zhí)行j=（i+1）mod n，選取第J臺服務(wù)器來響應(yīng)當(dāng)前請求任務(wù)，i表示響應(yīng)上一個請求任務(wù)的服務(wù)器[2]。如圖1所示。

圖1 輪轉(zhuǎn)調(diào)度Fig.1 Round-robin scheduling

輪轉(zhuǎn)調(diào)度算法是一種理想狀況下的調(diào)度算法，無需考慮當(dāng)前所有服務(wù)器的連接狀態(tài)，采用無狀態(tài)調(diào)度，固有處理能力相當(dāng)因此屬于靜態(tài)調(diào)度算法。它假定各服務(wù)器是同構(gòu)的，即所有的服務(wù)器，也不考慮各臺服務(wù)器當(dāng)前實際負載，中各服務(wù)器處理性能不一的情況，只使用于同構(gòu)服務(wù)器。這種算法不適用于異構(gòu)服務(wù)器事實上對于實際應(yīng)用中的服務(wù)器絕大多數(shù)都是異構(gòu)的，處理能力千差萬別，而且各請求任務(wù)所消耗的時間以及各服務(wù)器的當(dāng)前實際負載各不相同。

2.2 加權(quán)輪轉(zhuǎn)調(diào)度算法

由于輪轉(zhuǎn)調(diào)度算法不適用與異構(gòu)系統(tǒng)，人們提出了它的改進算法一加權(quán)輪轉(zhuǎn)調(diào)度（Weighted Round-Robin Scheduling}算法。為了處理各服務(wù)器處理性能不一的情況，加權(quán)輪轉(zhuǎn)調(diào)度算法在輪轉(zhuǎn)調(diào)度算法的基礎(chǔ)上為各服務(wù)器增加了一個能代表該服務(wù)器固有處理能力的權(quán)值，請求任務(wù)分配時根據(jù)這個權(quán)值所確定的比例分配相對數(shù)量的請求任務(wù)，權(quán)值越大的服務(wù)器將會優(yōu)先被調(diào)度到，而且調(diào)度次數(shù)也比權(quán)值小的服務(wù)器多，因此權(quán)值高的服務(wù)器較之權(quán)值低的服務(wù)器能接受更多的請求任務(wù)。

假設(shè)有 n 臺服務(wù)器 S={S1，S2，L，Sn}，服務(wù)器 Si的當(dāng)前調(diào)度權(quán)值為 W（Si），max（W（Si））表示所有服務(wù)器的最大權(quán)值，gcd（W（Si））表示所有服務(wù)器當(dāng)前權(quán)值的最大公約數(shù)。如有請求任務(wù)到達，加權(quán)輪轉(zhuǎn)調(diào)度算法將該請求任務(wù)分配給Sk，當(dāng)且僅當(dāng) W（Sk）=max（W（Si）），Sk接受調(diào)度后，W（Sk）=W（Sk）-gcd（W（Si））。

Step1初始化權(quán)值表，根據(jù)固有處理能力為每個服務(wù)器設(shè)置合適的權(quán)值；

Step2若有請求任務(wù)到達，選擇權(quán)值最大的服務(wù)器來響應(yīng)該請求任務(wù)；

Step3 更新權(quán)值表，W（Sk）=W（Sk）-gcd（W（Si））；

Step4 若 W（Si）=0，從調(diào)度隊列中退出。

3 動態(tài)負載均衡

3.1 最小連接調(diào)度算法

最小連接調(diào)度（Least Connections Scheduling）算法是選擇當(dāng)前各服務(wù)器中請求任務(wù)連接數(shù)最小的服務(wù)器作為下一個請求任務(wù)分配的目的地。這種算法考慮了各個服務(wù)器當(dāng)前的負載信息，將連接數(shù)作為服務(wù)器當(dāng)前的實際負載，連接數(shù)少的服務(wù)器實際負載較輕，較之連接數(shù)多的服務(wù)器具備相對多的剩余處理能力，能更快的響應(yīng)并處理新到達的請求任務(wù)，因此選擇連接數(shù)最小的服務(wù)器來響應(yīng)下一個請求任務(wù)。最小連接調(diào)度算法利用動態(tài)反饋機制，周期性地跟蹤各個服務(wù)器的當(dāng)前連接數(shù)，將其記錄在調(diào)度器內(nèi)的負載表中，在當(dāng)前周期內(nèi)，請求任務(wù)被調(diào)度到當(dāng)前連接數(shù)最小的服務(wù)器[3]，當(dāng)下一個周期達到時，查詢各服務(wù)器新的當(dāng)前連接數(shù)，刷新調(diào)度器上負載表。

算法流程如下：

假設(shè)有n臺服務(wù)器 S={S1，S2，L，Sn}， 其當(dāng)前連接數(shù)為 L={L1，L2，L，Ln}，在當(dāng)前周期內(nèi)達到的請求任務(wù)數(shù)為 Ф，最小連接調(diào)度算法將這Ф個請求任務(wù)數(shù)分配到服務(wù)器Sk上，當(dāng)且僅當(dāng) Lk=min{L1，L2，L，Ln}。

Step1初始化負載表；

Step2測試當(dāng)前周期內(nèi)各個服務(wù)器的當(dāng)前連接數(shù)，更新負載表，若在規(guī)定時間內(nèi)未收到某臺服務(wù)器的當(dāng)前連接數(shù)，將其所對應(yīng)負載表的記錄標為+∞，表示該服務(wù)器無法到達；

Step3若有新的請求任務(wù)，從負載表中選取當(dāng)前連接數(shù)最小的記錄所對應(yīng)的服務(wù)器，將其分配給該服務(wù)器；

Step4若下一個周期達到，刷新負載表；若收到前一周期負載表中記錄為+∞所對應(yīng)服務(wù)器的當(dāng)前連接數(shù)，更新該記錄。

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

最小連接調(diào)度算法將當(dāng)前連接數(shù)作為衡量服務(wù)器負載的標準，加權(quán)最小連接調(diào)度算法為每臺服務(wù)器增加了一個權(quán)值作為服務(wù)器的固有處理能力，將當(dāng)前服務(wù)器的請求任務(wù)連接數(shù)目與該權(quán)值的比值作為服務(wù)器的負載權(quán)值，該比值小說明服務(wù)器的負載小，其剩余處理能力強，因此分配請求任務(wù)時，將請求任務(wù)分配給連接數(shù)與權(quán)值比值最少的服務(wù)器。最小連接調(diào)度算法同樣也采用動態(tài)反饋機制，周期性監(jiān)控各服務(wù)器的連接數(shù)，當(dāng)下一個周期到達時，刷新負載表。算法執(zhí)行流程如圖6所示[4-5]。

而在每一周期內(nèi)，Lsum為常值，所以可簡化為：

Step 1初始化負載表；

Step2測試當(dāng)前周期內(nèi)各個服務(wù)器的當(dāng)前連接數(shù)，計算比值Li/W（Si），更新負載表，若在規(guī)定時間內(nèi)未收到某臺服務(wù)器的當(dāng)前連接數(shù)，將其所對應(yīng)負載表的記錄標為+∞，表示該服務(wù)器無法到達；

Step3 若有請求任務(wù)達到，找出 min（Li/W（Si））記錄所對應(yīng)的服務(wù)器，將其分配給該服務(wù)器；

Step4若下一個周期達到，刷新負載表。

3.3 最小負載優(yōu)先算法

最小負載優(yōu)先算法就是將請求任務(wù)分配到負載最小的服務(wù)器上，它是一個動態(tài)負載均衡算法[6]，需要周期性地更新負載信息來不斷地修正調(diào)度器內(nèi)的負載表，而負載表中記錄了各個服務(wù)器在當(dāng)前周期內(nèi)的負載信息，調(diào)度器利用這些負載信息計算出一個綜合負載來表示各個服務(wù)器的負載狀況，綜合負載大的服務(wù)器負載較重，綜合負載小的服務(wù)器負載輕。算法流程如下：

Step 1：初始化負載表；

Step 2：若負載表為空，利用輪轉(zhuǎn)調(diào)度算法，依次選擇子區(qū)域，直至更新周期到達；否則轉(zhuǎn)第四步；

Step3：若更新周期達到，節(jié)點利用心跳算法將負載信息包發(fā)送至調(diào)度器，如果在規(guī)定時間內(nèi)未收到某節(jié)點的數(shù)據(jù)包，認為其不可達到，取消其響應(yīng)資格，若在下個更新周期到達時，調(diào)度器收到了該節(jié)點的負載信息，更新周期表；

Step4：調(diào)度器根據(jù)負載信息計算每個綜合負載的Li，選擇服務(wù)器K作為響應(yīng)服務(wù)器。

最小負載優(yōu)先算法也有著加權(quán)最小連接調(diào)度算法的缺點，由于總是將新到的請求發(fā)送到綜合負載最小的節(jié)點上，特別是當(dāng)?shù)竭_的請求任務(wù)分布比較密集的時候，這種調(diào)度算法可能會使得某一個節(jié)點在一個周期內(nèi)接受了大量請求，從而使得負載不均衡，系統(tǒng)性能下降。

3.4 隨機負載均衡算法

前面的負載均衡算法都是以固定的轉(zhuǎn)發(fā)模式分配請求任務(wù)，但是由于請求任務(wù)的到達具有隨機性，而且負載調(diào)度器在更新周期到達時收集的負載信息對于周期內(nèi)請求任務(wù)的分配是過時的信息，所有的請求任務(wù)仍然分配到很有可能己不是最小負載的服務(wù)器上，從而導(dǎo)致負載不均衡，固定轉(zhuǎn)發(fā)有一定的局限性，因此人們依據(jù)請求的隨機性在算法中引入一定的隨機性如正態(tài)分布或泊松分布等來改善系統(tǒng)的性能，而且研究表明，引入一定的隨機性可以改善系統(tǒng)的整體性能。

4 INSS負載均衡模型

在智能網(wǎng)絡(luò)存儲系統(tǒng)中，當(dāng)Iro請求到達時，必須先判定是讀請求還是寫請求，若為讀請求，判斷該讀請求的數(shù)據(jù)是否存在副本，存在副本的情況下，元數(shù)據(jù)服務(wù)器根據(jù)當(dāng)前周期負載記錄找出擁有副本的節(jié)點中負載最低的來響應(yīng)；否則，元數(shù)據(jù)服務(wù)器根據(jù)其所保存的數(shù)據(jù)庫信息，直接從擁有該數(shù)據(jù)的節(jié)點中直接讀取。若為寫請求，首先判定文件大小，當(dāng)為大文件請求時，必須先采用條帶化技術(shù)對大文件進行切分，以此來提高用戶對文件訪問的并發(fā)性，從而來提高對大文件的訪問性能，然后再利用 TLDF（TwoLevel Dynamic Feedback）算法將切分后數(shù)據(jù)塊存儲在同一區(qū)域多個節(jié)點上，而小文件不利于條帶化，所以一般是采用將單個文件存儲在單個數(shù)據(jù)服務(wù)器上的策略，同樣利用TLDF算法將小文件存儲在某個區(qū)域的一個節(jié)點上。文中的負載均衡主要考慮的是寫請求，因此TLDF算法在智能網(wǎng)絡(luò)存儲系統(tǒng)中實際上是利用負載均衡技術(shù)的一種數(shù)據(jù)放置策略[7]。

對于大文件和小文件的寫請求，我們有如下規(guī)定：

大任務(wù)：一個大文件的寫請求；

請求任務(wù)：未切分的小文件和大文件切分后的數(shù)據(jù)塊所對應(yīng)的任務(wù)。

負載均衡調(diào)度器主要工作是:周期性地監(jiān)測并收集存儲層中各個節(jié)點的負載信息，根據(jù)當(dāng)前周期T內(nèi)各節(jié)點的負載信息按照第一級負載均衡策略選擇合適的子區(qū)域N，再根據(jù)第二級負載均衡策略將請求任務(wù)分配至況中的某些節(jié)點。圖3是負載均衡調(diào)度器的基本框架，主要3個模塊:負載收集模塊、調(diào)度模塊以及執(zhí)行模塊。

圖2 負載均衡調(diào)度器的基本框架Fig.2 Basic framework of load balancing scheduler maps

在INSS系統(tǒng)中，甚至在所有的分布式系統(tǒng)中，對請求任務(wù)進行負載均衡調(diào)度，首先必須評估系統(tǒng)中所有節(jié)點的負載，因此負載收集是進行負載均衡調(diào)度的基本前提，負載收集模塊進行的主要工作是:

1）對節(jié)點的負載信息進行周期性地收集、統(tǒng)計和存儲；

2）判斷系統(tǒng)中節(jié)點是否失效。

請求任務(wù)的負載均衡調(diào)度中最核心的模塊是調(diào)度模塊，它作為整個框架中的“大腦”，調(diào)度模塊中算法設(shè)計的好壞決定了一個調(diào)度算法性能的優(yōu)劣[8]，調(diào)度模塊主要解決的問題是:根據(jù)負載收集模塊提供的負載信息，再結(jié)合負載均衡算法，計算出各節(jié)點的負載權(quán)值，為執(zhí)行模塊提供分配權(quán)值。

執(zhí)行模塊的主要任務(wù)是:當(dāng)請求任務(wù)到達時，按照分配權(quán)值來執(zhí)行分配策略，通知元數(shù)據(jù)服務(wù)器和客戶端，該請求任務(wù)應(yīng)分配至哪些節(jié)點，并將具體的分配信息存儲在位于元數(shù)據(jù)服務(wù)器的數(shù)據(jù)庫內(nèi)，以方便元數(shù)據(jù)服務(wù)器對節(jié)點的管理。

5 結(jié)束語

詳細探討了幾種經(jīng)典的負載均衡調(diào)度算法，介紹了它們的算法流程及其優(yōu)缺點，說明對于INSS系統(tǒng)的數(shù)據(jù)放置策略需要一個更為有效的負載均衡算法，最后根據(jù)INSS存儲系統(tǒng)結(jié)構(gòu)模型及其I/O請求流程，提出了一種二級動態(tài)反饋負載均衡模型。

[1]蔣從鋒.基于網(wǎng)格計算的大規(guī)模分布式動態(tài)虛擬環(huán)境仿真研究[D].武漢：華中科技大學(xué)，2007.

[2]馬丹.任務(wù)間相互依賴的并行作業(yè)調(diào)度算法研究[D].武漢：華中科技大學(xué)，2007.

[3]龔衛(wèi)華.數(shù)據(jù)庫集群系統(tǒng)的關(guān)鍵技術(shù)研究[D].武漢：華中科技大學(xué)，2006.

[4]周云霞，趙躍龍，楊希.智能網(wǎng)絡(luò)磁盤存儲系統(tǒng)的容災(zāi)研究[J].計算機研究與發(fā)展，2012（7）：75-75.

ZHOU Yun-xia，ZHAO Yue-long，YANG Xi[J].Disaster research on intelligent network disk storage system[J].Research and Development of Computer，2012（7）：75-75.

[5]魏祥麟，陳鳴，張國敏.一種綜合的結(jié)構(gòu)化P2P系統(tǒng)負載均衡機制[J].北京郵電大學(xué)學(xué)報，2012（3）：36.

WEI Xiang-lin，CHEN Ming，ZHANG Guo-min.Load balancing mechanism of a comprehensive structured P2P system[J].Journal of Beijing University of Posts and Telecommunications，2012（3）：36.

[6]張漢.無線傳感網(wǎng)中基于負載均衡的EAMCT-G優(yōu)化算法研究[D].鄭州：鄭州大學(xué)，2012.

[7]李彥君，鐘求喜，陳誠，等.多核平臺入侵檢測系統(tǒng)負載均衡算法設(shè)計與實現(xiàn)[J].計算機應(yīng)用研究，2012（4）：11-12.

LIYan-jun，ZHONG Qiu-xi，CHEN Cheng，etal.Load equalization algorithm design and implementation of multicore platform intrusion detection system [J].Computer Application，2012（4）：11-12.

[8]何達，吳明.Ada-BP神經(jīng)網(wǎng)絡(luò)改進算法在電力負荷預(yù)測中的應(yīng)用研究[J].陜西電力,2012（12）：21-24.

HE Da，WU Ming.Probe into application of Ada-BP neural network improved algorithm in electric power load forecasting[J].Shaanxi Electric Power，2012（12）：21-24.