智能網絡存儲系統負載均衡算法研究

李昕

（陜西工業職業技術學院 陜西 咸陽 712000）

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

1 負載均衡技術

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

根據調節策略的不同，可以分為靜態負載均衡和動態負載均衡兩類，靜態調度算法事先就己經確定好了請求任務的分發策略，它不管每個任務的性質、所需消耗的系統資源以及各個服務器運行時刻的負載情況，只是根據預先設定的分配方案對用戶的請求進行分配。

根據任務調度模型的不同，我們又將動態負載均衡分為集中式控制與分布式控制集中式控制就是在負載均衡系統中設置一臺中央控制服務器，我們把它叫做負載調度器。

2 靜態負載均衡算法

2.1 輪轉調度算法

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

圖1 輪轉調度Fig.1 Round-robin scheduling

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

2.2 加權輪轉調度算法

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

假設有 n 臺服務器 S={S1，S2，L，Sn}，服務器 Si的當前調度權值為 W（Si），max（W（Si））表示所有服務器的最大權值，gcd（W（Si））表示所有服務器當前權值的最大公約數。如有請求任務到達，加權輪轉調度算法將該請求任務分配給Sk，當且僅當 W（Sk）=max（W（Si）），Sk接受調度后，W（Sk）=W（Sk）-gcd（W（Si））。

Step1初始化權值表，根據固有處理能力為每個服務器設置合適的權值；

Step2若有請求任務到達，選擇權值最大的服務器來響應該請求任務；

Step3 更新權值表，W（Sk）=W（Sk）-gcd（W（Si））；

Step4 若 W（Si）=0，從調度隊列中退出。

3 動態負載均衡

3.1 最小連接調度算法

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

算法流程如下：

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

Step1初始化負載表；

Step2測試當前周期內各個服務器的當前連接數，更新負載表，若在規定時間內未收到某臺服務器的當前連接數，將其所對應負載表的記錄標為+∞，表示該服務器無法到達；

Step3若有新的請求任務，從負載表中選取當前連接數最小的記錄所對應的服務器，將其分配給該服務器；

Step4若下一個周期達到，刷新負載表；若收到前一周期負載表中記錄為+∞所對應服務器的當前連接數，更新該記錄。

3.2 加權最小連接調度算法

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

而在每一周期內，Lsum為常值，所以可簡化為：

Step 1初始化負載表；

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

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

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

3.3 最小負載優先算法

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

Step 1：初始化負載表；

Step 2：若負載表為空，利用輪轉調度算法，依次選擇子區域，直至更新周期到達；否則轉第四步；

Step3：若更新周期達到，節點利用心跳算法將負載信息包發送至調度器，如果在規定時間內未收到某節點的數據包，認為其不可達到，取消其響應資格，若在下個更新周期到達時，調度器收到了該節點的負載信息，更新周期表；

Step4：調度器根據負載信息計算每個綜合負載的Li，選擇服務器K作為響應服務器。

最小負載優先算法也有著加權最小連接調度算法的缺點，由于總是將新到的請求發送到綜合負載最小的節點上，特別是當到達的請求任務分布比較密集的時候，這種調度算法可能會使得某一個節點在一個周期內接受了大量請求，從而使得負載不均衡，系統性能下降。

3.4 隨機負載均衡算法

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

4 INSS負載均衡模型

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

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

大任務：一個大文件的寫請求；

請求任務：未切分的小文件和大文件切分后的數據塊所對應的任務。

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

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

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

1）對節點的負載信息進行周期性地收集、統計和存儲；

2）判斷系統中節點是否失效。

請求任務的負載均衡調度中最核心的模塊是調度模塊，它作為整個框架中的“大腦”，調度模塊中算法設計的好壞決定了一個調度算法性能的優劣[8]，調度模塊主要解決的問題是:根據負載收集模塊提供的負載信息，再結合負載均衡算法，計算出各節點的負載權值，為執行模塊提供分配權值。

執行模塊的主要任務是:當請求任務到達時，按照分配權值來執行分配策略，通知元數據服務器和客戶端，該請求任務應分配至哪些節點，并將具體的分配信息存儲在位于元數據服務器的數據庫內，以方便元數據服務器對節點的管理。

5 結束語

詳細探討了幾種經典的負載均衡調度算法，介紹了它們的算法流程及其優缺點，說明對于INSS系統的數據放置策略需要一個更為有效的負載均衡算法，最后根據INSS存儲系統結構模型及其I/O請求流程，提出了一種二級動態反饋負載均衡模型。

[1]蔣從鋒.基于網格計算的大規模分布式動態虛擬環境仿真研究[D].武漢：華中科技大學，2007.

[2]馬丹.任務間相互依賴的并行作業調度算法研究[D].武漢：華中科技大學，2007.

[3]龔衛華.數據庫集群系統的關鍵技術研究[D].武漢：華中科技大學，2006.

[4]周云霞，趙躍龍，楊希.智能網絡磁盤存儲系統的容災研究[J].計算機研究與發展，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]魏祥麟，陳鳴，張國敏.一種綜合的結構化P2P系統負載均衡機制[J].北京郵電大學學報，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]張漢.無線傳感網中基于負載均衡的EAMCT-G優化算法研究[D].鄭州：鄭州大學，2012.

[7]李彥君，鐘求喜，陳誠，等.多核平臺入侵檢測系統負載均衡算法設計與實現[J].計算機應用研究，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].陜西電力,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.