覃偉榮

（欽州學院資源與環(huán)境學院 欽州 535011）

1 引言

隨著計算機業(yè)務應用程序的不斷發(fā)展，數(shù)據(jù)量正在呈指數(shù)級增長，網(wǎng)絡設備的增加和互聯(lián)網(wǎng)的發(fā)展，使得數(shù)據(jù)的生成和存儲容量爆炸式增長，數(shù)據(jù)中心面臨著龐大的訪問量［1］。傳統(tǒng)的數(shù)據(jù)庫管理無法滿足數(shù)據(jù)的龐大和數(shù)據(jù)結構的復雜，進而難以實現(xiàn)數(shù)據(jù)存儲和管理要求。分布式云計算系統(tǒng)架構可以為計算資源提供更高的性能，并且優(yōu)化海量存儲資源。然而，在分布式云計算系統(tǒng)中，數(shù)據(jù)密集型計算需要處理大量的數(shù)據(jù)，在多數(shù)據(jù)中心環(huán)境中，某些數(shù)據(jù)必須放在指定的數(shù)據(jù)中心內(nèi)且不能傳輸［2］。云計算處理不可避免的引起數(shù)據(jù)中心之間的數(shù)據(jù)調度，由于數(shù)據(jù)量巨大且網(wǎng)絡帶寬有限，數(shù)據(jù)中心之間的數(shù)據(jù)調度已成為網(wǎng)絡傳輸中的巨大問題［3］。

關于分布式系統(tǒng)中的數(shù)據(jù)布局已有很多研究［4～6］，通常可以分為兩種類型：靜態(tài)數(shù)據(jù)布局［7］和動態(tài)數(shù)據(jù)布局［8］。大多數(shù)靜態(tài)數(shù)據(jù)布局算法需要完全掌握網(wǎng)絡環(huán)境負載信息，例如所有文件的存儲時間和訪問速率［9］。動態(tài)數(shù)據(jù)布局算法在線生成文件磁盤分配方案，并以此適應不同的網(wǎng)絡負載模式，進而不必對分配文件進行先驗處理。動態(tài)數(shù)據(jù)布局策略在每個請求上更新布局策略，當數(shù)據(jù)量相對較小時，Web代理緩存才會有效［10］。文獻［11］基于數(shù)據(jù)相關性建立數(shù)據(jù)布局策略，但數(shù)據(jù)相關性的定義并不滿足數(shù)據(jù)布局，且沒有提出有效的方法來減少數(shù)據(jù)中心之間的數(shù)據(jù)調度量。

為了滿足分布式云計算中數(shù)據(jù)布局的合理性，本文利用遺傳算法合理布局數(shù)據(jù)策略。通過數(shù)據(jù)中心之間的數(shù)據(jù)調度建立分布式云計算的數(shù)學模型，結合適應度函數(shù)的倒數(shù)建立目標函數(shù)來評估每個個體的適合度。在初始種群按照優(yōu)勝劣汰的原則生成后，每一代的進化產(chǎn)生更好的近似解，運用輪盤賭法則選擇具有高適合度值的適當個體，并且消除具有低適應值的個體。通過遺傳算法的交叉和變異操作改變數(shù)據(jù)集的布局位置。最終在在優(yōu)勝劣汰的原則下找到最優(yōu)個體。

2 云計算中的數(shù)據(jù)調度模型

在云計算系統(tǒng)中，數(shù)據(jù)存儲通常達到PB 級規(guī)模，復雜多樣的數(shù)據(jù)結構對數(shù)據(jù)服務類型和高級別要求的數(shù)據(jù)管理帶來了巨大壓力［12］。本文以數(shù)據(jù)中心之間的數(shù)據(jù)調度模型為基礎，并建立精確數(shù)據(jù)布局的理論基礎。

假設云計算系統(tǒng)具有l(wèi)個數(shù)據(jù)中心，依據(jù)數(shù)據(jù)中心固有屬性劃分為N個不同的數(shù)據(jù)集。根據(jù)用戶請求數(shù)據(jù)資源，將數(shù)據(jù)集不同的操作分配到M個計算中。數(shù)據(jù)調度的模型，如圖1所示。

圖1 數(shù)據(jù)中心之間數(shù)據(jù)調度的物理模型

假設云計算系統(tǒng)中的數(shù)據(jù)集合為

其中，n是數(shù)據(jù)集的數(shù)量，數(shù)據(jù)集di的大小為εi。

系統(tǒng)中的l個數(shù)據(jù)中心表示為

系統(tǒng)中的m個計算表示為

每次計算的執(zhí)行頻率可表示為

其中，μi是單位間隔內(nèi)計算ci的執(zhí)行頻率。

本文定義一個處理因子αij，其中

因此，可以得到計算集C和數(shù)據(jù)集D的關聯(lián)矩陣表示為

在本文中，數(shù)據(jù)副本不在考慮之列。同樣，本文定義了一個布局因子βjk，其中

由數(shù)據(jù)集D和數(shù)據(jù)中心S之間的關聯(lián)矩陣（布局矩陣）可以表示為

關聯(lián)矩陣（布局矩陣）B用于表示數(shù)據(jù)中心S中存儲數(shù)據(jù)集D的狀態(tài)。其中，依據(jù)權重原則矩陣B中每行的元素之和為1：

其中，第k列的元素總和是數(shù)據(jù)中心Sk中存儲數(shù)據(jù)集的數(shù)量，當數(shù)據(jù)集放入數(shù)據(jù)中心Sk時，存儲的數(shù)據(jù)應滿足Sk的基本容量，則

定義矩陣Z表示為

假設

則矩陣Z=[zik]m×l，zik是數(shù)據(jù)中心一次計算ci時處理的數(shù)據(jù)集的數(shù)量。每個列中的元素的總和表示為，它是在所有的計算被執(zhí)行一次時在數(shù)據(jù)中心Sk中處理的數(shù)據(jù)集的數(shù)目。定義一個函數(shù)u(zik)表示為

計算ci執(zhí)行過程中訪問的數(shù)據(jù)中心數(shù)量為計算c執(zhí)行一次的數(shù)據(jù)調度次數(shù)為i當布局矩陣為B時，在單位區(qū)間內(nèi)系統(tǒng)中所有計算的執(zhí)行期間的數(shù)據(jù)調度總數(shù)可以表示為

本文的目標是找到最佳的數(shù)據(jù)布局解決方案B*最小化Γ(B)：

3 遺傳算法

3.1 算法選擇

在大數(shù)據(jù)布局問題中，由于B矩陣稀疏分布，則解空間非常龐大。傳統(tǒng)的優(yōu)化算法有窮舉搜索算法、蒙特卡洛算法、遺傳算法、模擬退火算法等。

窮舉搜索算法［13］是搜索最優(yōu)布局矩陣的直接方法。它計算出所有可能的數(shù)據(jù)布局B矩陣，然后遍歷找到最小的Γ(B) ，此時布局矩陣是最優(yōu)解。然而窮舉搜索算法的計算復雜度很高，近似于(ln)。在分布式云計算系統(tǒng)中，數(shù)據(jù)集n的數(shù)量使得計算復雜度對系統(tǒng)求解更加困難。此外，還存在一些約束條件，如存儲容量限制和無副本限制使得布局問題成為NP 難問題。因此，只有當數(shù)據(jù)集的數(shù)量很小時，才能使用窮舉搜索算法。

蒙特卡洛算法［14］利用概率論和統(tǒng)計方法。在數(shù)據(jù)布局中，通過隨機生成一定數(shù)量的B矩陣作為樣本，計算每個樣本矩陣B上的數(shù)據(jù)中心之間的數(shù)據(jù)調度，并找出具有最小數(shù)據(jù)調度的布局矩陣。與窮舉搜索算法相比，蒙特卡洛算法的計算復雜度有所提高，但B矩陣在解空間中稀疏分布，蒙特卡洛算法的搜索效率仍然不高。它在生成布局矩陣時具有很強的規(guī)律性和約束條件。

遺傳算法通過問題狀態(tài)空間進行定向搜索，其比隨機搜索算法［15］、枚舉法［16］或演算進化算法［17］更加有效。因此，利用遺傳算法可以解決大數(shù)據(jù)中的數(shù)據(jù)布局問題。

3.2 算法應用

遺傳算法針對優(yōu)化問題的候選解決方案群體（稱為個體），每個個體適應環(huán)境的程度由適應度來表示，在每一代中，對種群中每個個體的適應值進行評估，從當前種群中隨機選擇具有較高適應值的個體，然后進行交叉和變異算子操作來形成新一代，最后在算法的下一次迭代中使用新一代候選解決方案［18］。

1）編碼

數(shù)據(jù)中心的數(shù)據(jù)集由矩陣B表示可以表示遺傳算法的數(shù)據(jù)布局，結合矩陣的字符串結構直接將布局矩陣作為基因型進行編碼。

2）個體和種群

個體作為種群搜索空間中的點，數(shù)據(jù)布局的搜索空間由布局矩陣的集合組成。種群構成整個搜索空間的子集。

3）適應度函數(shù)

適應度函數(shù)在遺傳算法的數(shù)據(jù)布局問題中，目標函數(shù) Γ(B) 可以作為目標函數(shù)的倒數(shù)，即F=1/Γ(B)。

4）遺傳算子

（1）選擇：輪盤賭選擇是遺傳算法中用于選擇潛在重組方案的遺傳算子，更高的適合度的染色體更容易被選擇。輪盤賭選擇的步驟如下：

步驟1：在種群中獲得N個個體的適應度值f(i)。

步驟2：假設存在個體k，其被選擇的概率為p(k)：

步 驟 4：生 成 隨 機 數(shù)r(0 ≤r＜1) ，如 果q(k-1)＜r＜q(k)，則選擇個體k。

（2）交叉：假設B1與B2配對，產(chǎn)生兩個隨機數(shù)r1、r2(0 ＜r1＜r2＜n)作為交叉點，則交換這兩個點之間的基因產(chǎn)生子代。在布局矩陣上進行兩點交叉算子的4×3布局矩陣，如圖2所示。

圖2 兩點交叉算子布局矩陣示意圖

（3）變異：對于二進制字符串，染色體變異一個或多個基因。如果基因組位是1，則改變?yōu)?，反之亦然。當在布局矩陣中使用變異算子時，生成隨機數(shù)r1（0 ≤r1＜n），改變數(shù)據(jù)集的位置，然后生成兩個隨機數(shù)r2、r3(0 ≤r2≠r3＜l)，如果為1，則將其從1 變?yōu)?，從 0 變?yōu)?1；如果為0，則將其從0變?yōu)?，同時將同一行中的另一個1從1更改為0，以確保每行只有一個1，從而改變數(shù)據(jù)集dr1在數(shù)據(jù)中心的布局。在布局矩陣上進行兩點交叉算子的4×3布局矩陣變異，如圖3所示。

圖3 在布局矩陣上進行變異算子

4 基于遺傳算法的數(shù)據(jù)布局過程

步驟1：根據(jù)實際情況確定人口規(guī)模（G），交叉率（Pc）和變異率（Pm）。

步驟2：生成初始種群：初始種群BG(0)由G種位矩陣組成。矩陣的所有元素都設置為0，然后生成n個隨機數(shù) {r1，...，ri，...，rn} ，(0 ≤ri＜l)，進而生成矩陣Bi，隨機數(shù)ri表示數(shù)據(jù)集di被放入數(shù)據(jù)中心，然后布局因子從0 變?yōu)?，如果生成的矩陣不滿足式（10）中的約束條件，則放棄它并生成新的矩陣。

步驟3：計算種群BG(t)中每個個體的適合度MaxGen：通過矩陣乘法得到矩陣Z，即Z=A·B。矩陣Z中行i的非零元素的數(shù)目是計算ci期間訪問所有數(shù)據(jù)中心的次數(shù)，當計算ci執(zhí)行一次時，數(shù)據(jù)調度的數(shù)量為然后，可以計算出來在單位間隔內(nèi)執(zhí)行系統(tǒng)中所有計算期間B中的數(shù)據(jù)調度總數(shù)，即：

步驟4：計算種群BG(t)中每個個體的數(shù)據(jù)調度 Γ(Bt)的數(shù)量，Bt的適應值表示為F=1/Γ(Bt)。在計算每個人的適合度值和所選擇的概率之后，通過輪盤賭從BG(t)中選擇G個個體。

步驟5：利用交叉率Pc作為交叉操作的染色體百分比，對選定的布局矩陣執(zhí)行交叉算子。

步驟6：利用變異率Pm作為參與變異操作的染色體百分比，對所選擇的布局矩陣上執(zhí)行變異算子。如果群體的大小是G并且每個個體具有n個基因，則待變異的基因數(shù)量為G·n·Pm。因此，可以生成隨機數(shù)r(0 ≤r≤1)，如果r＜Pm，則相應的基因將發(fā)生變異。

步驟8：根據(jù)式（7）中的布局因子βjk的定義，在找到近似最優(yōu)解B*之后，數(shù)據(jù)集dj的布局可以通過B*中的布局因子βjk來確定。

5 仿真實驗

5.1 仿真環(huán)境

為了驗證本文所提出的基于遺傳算法的數(shù)據(jù)布局策略，構建了面向“Digital city”的數(shù)據(jù)存儲和訪問平臺。該平臺由20 個Dell Power Edge T410 服務器組成，每個都有8 個英特爾Intel Xeon E5606 CPU（2.13 GHz），16G DDR3 內(nèi)存和 3TB SATA 磁盤組成。通過在數(shù)據(jù)中心部署獨立的Hadoop 分布式文件系統(tǒng)和VMware，因此將每個服務器都充當數(shù)據(jù)中心。在千兆以太網(wǎng)環(huán)境下，用戶可以通過Flex 4.5 開發(fā)的數(shù)字城市應用演示系統(tǒng)提交數(shù)據(jù)并進行計算。

5.2 仿真結果與分析

本文在數(shù)據(jù)布局中應用遺傳算法對布局策略進行綜合性能測試。為了驗證遺傳算法在數(shù)據(jù)布局中的可行性，比較了遺傳算法和窮舉搜索算法求解數(shù)據(jù)中心之間的數(shù)據(jù)調度，在數(shù)據(jù)集的數(shù)量很小時，不同數(shù)量的最小數(shù)據(jù)調度數(shù)和關系數(shù)據(jù)集之間的關系由折線圖表示。為了比較數(shù)據(jù)集數(shù)量發(fā)生變化時，不同算法搜索的數(shù)據(jù)中心之間的數(shù)據(jù)調度。通過對3個數(shù)據(jù)中心進行400次測試計算。在遺傳算法中，蒙特卡洛算法的迭代次數(shù)為106次，初始種群的規(guī)模設置為200，最大迭代次數(shù)設置為1000，交叉率和變異率分別為0.6和0.01。

數(shù)據(jù)中心之間的數(shù)據(jù)調度的算法對比，如圖4所示。從圖4 中，可以發(fā)現(xiàn)隨著數(shù)據(jù)集的數(shù)量變化，三種算法的結果在每種情況下都是相同的。通過遍歷得到窮舉搜索算法的結果，相應的結果是最優(yōu)的數(shù)據(jù)布局矩陣，因此，利用遺傳算法和蒙特卡洛算法也可以找到最優(yōu)的數(shù)據(jù)布局矩陣。

數(shù)據(jù)調度的最小次數(shù)，如圖5 所示。數(shù)據(jù)調度的最小次數(shù)隨著生成代數(shù)的增加而減小，并且優(yōu)化結果更加接近最優(yōu)解。其中，當數(shù)據(jù)集數(shù)量為8 個時，產(chǎn)生代數(shù)的收斂拐點在400。

圖4 三種算法在不同數(shù)據(jù)集的數(shù)據(jù)中心之間的數(shù)據(jù)調度

圖5 數(shù)據(jù)調度的最小次數(shù)

在數(shù)據(jù)集數(shù)量較大的情況下，將遺傳算法搜索的近似最優(yōu)解數(shù)據(jù)中心的數(shù)據(jù)調度與蒙特卡羅算法搜索的結果進行了比較，并比較了各算法的優(yōu)化時間。通過隨機測試計算2500 次不同數(shù)據(jù)集的數(shù)據(jù)中心。在遺傳算法中，蒙特卡洛算法的迭代次數(shù)為109次，初始種群的大小設定為5×103，最大代數(shù)設置為2000，交叉率和變異率分別為0.5和0.05。

從圖6 和圖7 中，可以看到數(shù)據(jù)集或數(shù)據(jù)中心的增加導致數(shù)據(jù)中心之間的數(shù)據(jù)調度的增長。通過對數(shù)據(jù)的比較，發(fā)現(xiàn)在遺傳算法中近似最優(yōu)數(shù)據(jù)布局矩陣的數(shù)據(jù)中心之間的數(shù)據(jù)調度總是小于蒙特卡洛算法。因此，對于數(shù)據(jù)布局問題，在大數(shù)據(jù)集的情況下，遺傳算法的搜索結果優(yōu)于蒙特卡羅算法。

圖6 不同數(shù)據(jù)集之間的數(shù)據(jù)調度

圖7 數(shù)據(jù)中心之間的數(shù)據(jù)調度

圖8 給出了不同數(shù)量的數(shù)據(jù)集的最小數(shù)據(jù)調度數(shù)與子代之間的關系。在實驗中，數(shù)據(jù)中心的數(shù)量固定為5 個。數(shù)據(jù)集的數(shù)量固定為60 時，在30個數(shù)據(jù)中心上隨機運行了2500次測試計算，如圖9所示。隨著子代的增加，數(shù)據(jù)調度次數(shù)變小，優(yōu)化結果更接近最優(yōu)解。

圖8 數(shù)據(jù)調度的最小次數(shù)

圖9 數(shù)據(jù)中心中數(shù)據(jù)調度的最小次數(shù)

6 結語

在分布式云計算的環(huán)境中，將數(shù)據(jù)布局到合適的數(shù)據(jù)中心已經(jīng)成為一個關鍵問題。本文建立了數(shù)據(jù)集、數(shù)據(jù)中心和計算之間的數(shù)學模型。利用三種不同的算法來搜索近似最優(yōu)數(shù)據(jù)布局矩陣，通過將遺傳算法與窮舉搜索算法和蒙特卡洛算法進行比較可得，遺傳算法可以找到最優(yōu)的數(shù)據(jù)布局矩陣。