ＧＥＰ在磁盤負載均衡方面的應用研究

收稿日期：2007-12-05；修回日期：2008-03-24

作者簡介：倪云竹（1978- ），女，博士研究生，主要研究方向為計算機網絡與信息系統、存儲技術(ybamboo@163.com);李志蜀 (1946 -) ，男，教授，博導，主要研究方向為軟件測試、網絡與信息系統

（四川大學 計算機學院，成都 610064）

摘 要：如何提高存儲子系統的I/O性能一直以來都是計算機領域的一個研究熱點，而目前提高存儲子系統的I/O性能的一個最大障礙就是負載不均衡。提出了一種采用基因表達式編程（GEP）來實現基于分條技術的磁盤動態負載均衡的算法。該方法包括基于分條技術的文件劃分算法和為實現負載均衡的文件分配算法。該算法采用多基因家族結構的染色體編碼來表示物理磁盤組與邏輯磁盤的映射關系。在操作上，采用選擇復制、倒置和交換等特殊的搜索算子。

關鍵詞：存儲；磁盤陣列；磁盤映射；負載均衡；分條技術；基因表達式編程

中圖分類號：TP301

文獻標志碼：A

文章編號：1001-3695(2008)10-2995-03

Research of disk load balancing based on GEP

NI Yun-zhu，LI Zhi-shu

(College of Computer， Sichuan University， Chengdu 610064， China)

Abstract:With the increase of the number of disks in storage subsystems due to rapidly increasing capacity requirements，the largest performance problem of the storage is load imbalance. This paper presented a new scheme based on disk striping and GEP to solve the problem， including the file partition algorithm based on disk striping and the file allocation algorithm for load balance. This algorithm representedthe chromosome of the tree with the multigene family structure coding. And applied three combination-specific genetic operators: selection， inversion and permutation.

Key words：storage；disk array；disk mapping；load balancing；disk striping；gene expression programming

0 引言

在當今信息社會中，信息對于人們來說是越來越重要，對信息的存儲和訪問技術也因此成為IT行業的一大熱點。大型磁盤陣列內部一般采用RAID結構以提高信息存放的可靠性和I/O性能，它通常按照RAID標準將多個物理磁盤組成一個磁盤組，客戶系統所看到的磁盤并非實際的物理磁盤，而是邏輯磁盤，每個邏輯磁盤映射到某個磁盤組上的一部分。邏輯磁盤的負載是由訪問它的應用系統的I/O特征所決定，物理磁盤組的負載為映射到該磁盤組中的所有邏輯磁盤的負載之和。由于不同的邏輯盤上應用系統的I/O特征不同，很容易造成各磁盤組之間的物理磁盤的負載不均，從而降低I/O性能。可以說，目前提高存儲子系統的I/O性能的最大障礙就是負載不均衡或稱為磁盤偏移[1]。

目前解決磁盤負載不均主要有兩種技術，即動態數據存放技術和磁盤分條技術。但是，這兩種技術都是從應用程序或者文件系統的角度來考慮負載均衡，而沒有從存儲設備的角度來考慮負載均衡問題，且都是針對單個磁盤陣列的。這對于大型磁盤陣列來說往往是不夠的。于是各種新的解決方案應運而生，文獻[2]提出一種在磁盤陣列中實現數據分配和動態負載均衡的自適應方法，其基本思想是分配并合理地遷移數據使得磁盤陣列中的磁盤負載量變化減小，但這要求其負載量與具有穩態訪問特征的時間間隔的長度成比例，并且對其訪問具有周期性變化的特征。文獻[3]提出的基于遺傳算法的物理磁盤間負載均衡方法，以提高磁盤陣列的吞吐量。不過，該方法僅從存儲設備的角度來考慮，而不是從應用程序或文件的角度來考慮的，且其只限于考慮靜態數據的分配。

本文通過參考諸多文獻，提出了一種用GEP算法來實現基于分條技術的動態負載均衡的方法。

1 基于分條技術的磁盤陣列模型設計

11 基于分條技術的磁盤陣列模型

本文以RAID5結構構成的磁盤組為例考慮其負載均衡問題。在一些對I/O吞吐量和讀寫速度要求較高的實際應用中，由幾塊磁盤組成的RAID5陣列所提供的速度往往是不夠的。因此，可以建立多個具有相同結構的RAID5磁盤組。其結構組成如圖1[4]所示。

圖1不僅表示了RAID5磁盤組的組成結構，同時也顯示了邏輯磁盤與物理磁盤組之間的映射關系。其中，由物理磁盤組成的磁盤組的集合表示為P={P1，P2，…，PN}，N表示磁盤組個數，Pi(1≤i≤N)表示第i號磁盤組。將映射到所有磁盤組上的文件（可以看做是一個邏輯磁盤）進行統一編號，產生一個具有M個邏輯磁盤的集合L={L1，L2，…，LM}。其中：M表示邏輯磁盤的個數；Li(1≤i≤M)為第i號邏輯磁盤。為簡化算法，假定N能夠被M整除。當每一個邏輯磁盤映射到某一物理磁盤組時，即將邏輯磁盤上的數據進行劃分，并采用磁盤分條技術[5]分配到該物理磁盤組中的多個磁盤上。

12 數據模型的定義

通過文獻[4]的分析，筆者可以定義如下數據模型[4]：

a） 由物理磁盤組成的磁盤組的集合定義為P={P1，P2，…，PN}。其中：N表示磁盤組個數；Pi(1≤i≤N)為第i號磁盤組。

b） 表示數據文件的邏輯磁盤的集合定義為L={L1，L2，…，LM}。其中：M表示邏輯磁盤的個數；Li(1≤i≤M)為第i號邏輯磁盤。

c） 各個邏輯磁盤在k時間段的熱度的集合定義為LH={LH(1，k)，LH(1，k)，…，PH(i，k)，…，PH(M，k)}。其中：PH(i，k)表示第i個邏輯磁盤在k時間段的熱度。

d） 各個磁盤組在k時間段的熱度（負載）的集合定義為PH={PH(1，k)，PH(2，k)，…，PH(i，k)，…，PH(N，k)}。其中：PH(i，k)表示第i個磁盤組在k時間段的熱度，其值為所有映射到磁盤組Pi上的邏輯磁盤的熱度之和。

e） 物理磁盤組在某種映射方案下在T時間內總的熱度變換值（相對于平均值的均方差）定義為（S表示一種映射方案）：σ(S，T)=（1/N）∑Ni=1(PH(T)-PH(i，T)）²(1)其中：PH(T)=（1/N）∑Ni=1PH(i，T)（2）

本文的目標就是尋找一種解S，使得σ(S，T)滿足預定的熱度約束條件，從而實現磁盤陣列的負載均衡。對于解S，可以通過GEP進行搜索。

2 基因表達式算法

染色體(chromosome)和表達式樹(expression tree， ET)是GEP技術中最重要的概念。染色體作為承載遺傳信息的基因型實體，參與遺傳操作；表達式樹作為信息的表現型，表達遺傳實體中的信息編碼。染色體和表達式樹結構簡單清晰，通過簡單的編碼和解碼規則可無歧義地互換。GEP將這兩者分別作為獨立個體，對GA和GP的優點分別加以繼承，使遺傳操作易于實施，結果方便表達。染色體由若干個基因(gene)通過連接運算符連接組成。

Gene由頭部(head) 和尾部(tail) 組成， head 包含了函數(functions)和終結符(terminals) ， tail只含有terminals。頭部長度為h，尾部長度為t，函數中的最大目數為n，則良好定義的表達式滿足關系t=h(n-1)+1。

3 用GEP實現磁盤陣列負載均衡

31 編碼表示

在多基因系統中，GEP染色體通常由多個長度相等的基因組成，即多基因染色體包含多個ORF(open reading frames)，每個ORF解碼為結構和功能上獨立的子表達式樹。各個子表達式樹有獨立的適應度，由多個子表達式樹組成復雜的表達式樹。子表達式樹既是一個獨立實體，也是一個復雜整體的一部分。

另一些用于解決特殊問題的結構和功能不同的染色體，如最簡單的染色體只含單個終結符。該染色體可用于合成復雜染色體，在組成多基因族（multigene families，MGFs）時特別有用。在MGF中每個基因為一個終結點或代表一項任務。

如一個簡單的指派問題可以用如圖2所示的多基因族表示。其對應的表達式樹如圖3所示。其中，共有兩個MGF，分別用數字和英文字母表示。每個MGF中，每個元素編碼一棵子表達式樹。

基于本文所提出的磁盤陣列模型，本文采用一種改進的多基因家族結構的染色體編碼來表示物理磁盤組與邏輯磁盤的映射關系。

編碼如下：每一種映射方案表示成一個多基因家族結構的染色體。該染色體由兩個多基因家族（MGFs）構成：一個MGF表示物理磁盤組，由N個字母表示，每個字母表示一個物理磁盤組；另一個MGF表示邏輯磁盤，由M個數字表示，每個數字表示一個邏輯磁盤。

例如，假設有4個物理磁盤組，12個邏輯磁盤，其某一映射方案如圖4所示。其中：字母A、B、C、D分別表示4個物理磁盤組；數字1~12分別表示12個邏輯磁盤。要將12個邏輯磁盤分配給4個物理磁盤組，那么每個物理磁盤組分配3個邏輯磁盤，因此其對應關系就是從表示邏輯磁盤的MGF的第一個基因開始依次從左到右數3個基因（即數字1、2、3）對應A物理磁盤組。同理，邏輯磁盤4、5、6對應物理磁盤組B，7、8、9對應C，10、11、12對應D。

32 生成初始種群

對種群的初始化，本文主要采取生成多基因家族結構染色體的方法。首先對一個多基因家族結構染色體進行如下定義：a）該染色體是由物理磁盤組和邏輯磁盤兩集合中的元素構成。b）該染色體的前一個多基因家族（MGF）表示物理磁盤組節點。c）該染色體的后一個多基因家族（MGF）表示邏輯磁盤節點。

生成一個染色體的原則是使該染色體能滿足給定的負載均衡條件或使其能夠通過基因操作產生出較優良的后代，這就要求它本身也是較優良的個體。因此生成物理磁盤組與邏輯磁盤之間對應關系時，可以按照以下分配方法進行分配：

a)先設定與每個物理磁盤組相映射的邏輯磁盤數為q(q=M/N)。

b)按照邏輯磁盤集合L中各磁盤的熱度計算出各邏輯磁盤的選擇概率p（p=單個邏輯磁盤的熱度/所有邏輯磁盤的熱度之和）。

c)根據概率p將各邏輯磁盤分配給各物理磁盤組節點P1~PN中當前熱度值（即當前所映射的邏輯磁盤的熱度之和）最小的節點以形成初始染色體后一個MGF的一個節點。這樣可使具有較大熱度的邏輯磁盤被選中的概率較大，同時也使具有較小熱度的邏輯磁盤也有被選中的機會。

33 確定適應度函數

在自然界中，個體的適應值即是它的繁殖能力，將直接關系到后代的數量。而在GEP中，適應度函數是用來衡量種群中個體優劣的標準，它將直接反映個體的性能，性能好的個體適應度函數值大，性能差的適應度函數值小。根據適應度函數值的大小，決定某些個體是繁殖還是消亡。因此，適應度函數是驅動GEP的動力。

本文算法的適應度函數定義為f(S，T)=1/（A+B*fH）(3)fH=Φ(σ(S，T)-σ0)， Φ(X)=1， X≤0

r， X＞0(4)

其中：A、B是加權系數，其值可根據具體應用來設定; σ0表示實現磁盤負載均衡所能允許的熱度變化值約束，該值可以預先設定;函數σ(S，T)表示磁盤組在T時間內實際的熱度變化值，該函數在前面已經詳細介紹過;Φ(x)為懲罰函數，當個體滿足其相應約束時，其值為1，否則其值分別為r，在實驗中，可以設定r=1.5。

34 制定選擇策略

選擇就是指根據適者生存原則選擇下一代的個體。選擇策略對算法性能的影響通常起到舉足輕重的作用。不同的選擇策略將導致不同的選擇壓力，即下一代中父代個體的復制數目的不同分配關系。

本文算法主要采用的是基于適應值比例的選擇策略。

a)根據前面提出的適應度函數f(Si，T)計算出當前種群中個體的適應值，再采用擇優策略的方法，將計算出的適應值最高的個體（即最佳個體）直接保留到子代種群中，即GEP中的復制算子。

b)根據各個體的適應值，按下式計算出其相對適應值，作為該個體的選擇概率。psi=f(Si，T)/∑Di=1f(Si，T)（5）其中：f(Si，T)表示種群中第i個成員的適應值；D是種群規模。

c)采用轉盤式選擇策略對個體進行選擇。在這種方法下，即使具有較小適應值的個體也有被選擇的機會。

35 倒置操作（inversion）

倒置操作是指將選出的父代染色體，將其倒置點設定在某一多基因家族中，即在某一MGF中選中其中一基因串，將其排列順序顛倒。在特殊組合的基因操作中，倒置操作的搜索能力是最強的。甚至只對父代染色體進行修改，倒置操作也能夠使種群以很高的效率進化。

由于本文所采用的特殊的多基因家族結構的染色體編碼，不能使用常見的變異、重組等基因操作，必須根據具體問題設計專門的倒置操作和交換操作。

本文設計的倒置操作基本過程如下：

a) 按轉盤式選擇算法隨機地從種群中選擇一個父代染色體T。

b) 只選中染色體中第二個MGF2。

c) 在第二個MGF的基因編號中隨機產生兩個倒置點。

d) 將兩倒置點從小到大排列，找到對應的MGF2中基因串。

e) 將基因串的排列順序進行顛倒。

f) 重復上述五個步驟直到生成了要求數量的后代個體，并且這些后代個體是各不相同的。

例如，選中的父代染色體（其映射關系見圖4），假設在MGF2的基因編號中隨機產生的兩個數是2和9，其對應的基因串為3~10，將此串進行顛倒，得到一個新的個體。其過程如圖5所示。

對于此染色體，其磁盤的新的映射關系為: 邏輯磁盤1、2、10對應A物理磁盤組；邏輯磁盤9、8、7對應B物理磁盤組；邏輯磁盤6、5、4對應C物理磁盤組；邏輯磁盤3、11、12對應D物理磁盤組。

36 交換操作

限制性交換操作是指隨機選中一個父代染色體，在某一個MGF中，隨機選定兩個基因，將這兩個基因進行交換。

本文設計的交換操作描述如下：

a）隨機地選擇要進行交換的個體;

b）在該個體中隨機選擇一個MGF;

c) 在選中的MGF的基因編號中隨機產生兩個交換點;

d）將兩個交換點對應的兩個基因進行對換。

37 算法的終止條件

GEP計算的本質在于它永遠不停地進化。然而在實用時，一旦某個終止條件滿足，進化過程應立即停止。由于本文的目標是尋找一種解，使得磁盤組的熱度變化滿足預定的熱度約束條件，從而實現磁盤陣列的負載均衡。本算法的終止條件就是在種群中存在一個滿足熱度約束條件的染色體。

4 結束語

在數據模型的建立上，本文采用了基于分條技術的磁盤陣列數據模型。該模型能夠很好地顯示邏輯磁盤與物理磁盤組之間的映射關系，同時也制定出了下一步的求解目標。

在使用基因表達式編程算法時，本文拋棄了傳統的單基因染色體編碼方案，而采用了多基因家族結構的染色體編碼表示法。在制定選擇策略時，主要采用的是基于適應值比例的選擇策略。在這種方法下，即使具有較小適應值的個體也有被選擇的機會。在搜索算子的設計上，本文也沒有采用常見的變異、重組、插串等操作，而是采用了倒置操作和交換操作這兩種進化操作，根據分析，這兩種操作更適合本文提出的特殊結構的染色體。

該方法將磁盤分條技術與基因表達式編程算法結合起來，采用分條技術對文件進行劃分，而采用GEP對文件進行分配。這樣可以充分發揮兩者優勢，更好地實現磁盤負載均衡。

參考文獻：

[1]KIM M.Synchronized disk interleaving[J]. IEEE Trans on Computers， 1986，35(11):978-988.

[2]董歡慶，李站懷. 基于遺傳算法的RAID磁盤陣列中磁盤負載均衡方法[J]. 計算機工程與應用，2003，39(16): 41-42，93.

[3]SCHEUERMANN P， WEIKUM G， ZABBACK P.Adaptive load ba-lancing in disk arrays[C]//Proc of the 4th International Conference on Foundations of Data Organization and Algorithms. London: Sprin-ger-Verlag， 1993：345-360.

[4]倪云竹，呂光宏，黃彥輝. 用遺傳算法解決基于分條技術的磁盤負載均衡問題[J]. 計算機學報， 2006，11: 1995-2001.

[5]CHEN P M， LEE E K. Striping in a RAID level 5 disk array[C]// Proc of ACM SIGMETERICS Conference on Measurement and Mode-ling of Computer Systems. New York: ACM press，1995:136-145.

[6]GANGER G R， WORTHINGTON B L，PATT R Y H.Disk subsystem load balancing: disk striping vs. conventional data placement[C]//Proc of International Conference on System Sciences. Hawaii:[s.n.] 1993:40-49.

[7]GANGER G R.System-oriented evaluation of I/O subsystem perfor-mance， CSE-TR-243-95[R]. Ann Arbor， MI:Department of EECS， University of Michigan，1995.

[8]唐常杰，彭京，張歡，等. 基于基因表達式編程的知識發現的三項新技術[J].計算機應用，2005，25(9):1978-1981.

[9]GANGER G R， WORTHINGTON B L， PART R YH. Disk arrays， high-performance， high-reliability storage subsystems[J]. IEEE Computer，1994:27(3):30-36.

[10]SCHEUERMANN P， WEIKUM G， ZABBACK P. Data partitioning and load balancing in parallel disk systems[J]. The VLDB Journal， 1998，7(1): 48-66.

[11]MOGI K， KITSUREGAWA M.Dynamic parity stripe reorganizations for RAID5 disk arrays[C]//Proc of the 3rd International Conference on Parallel and Distributed Information Systems. Los Alamitos， CA: IEEE Computer Society Press， 1994: 17-26.

[12]CHEN P M， PATTERSON D A.Maximizing performance in a striped disk array[C]//Proc of ISCA. New York: ACM Press， 1990: 322-331.