覃偉榮

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

本文定義一個(gè)處理因子αij，其中

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

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

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

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

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

定義矩陣Z表示為

假設(shè)

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

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

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

3 遺傳算法

3.1 算法選擇

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

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

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

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

3.2 算法應(yīng)用

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

1）編碼

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

2）個(gè)體和種群

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

3）適應(yīng)度函數(shù)

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

4）遺傳算子

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

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

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

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

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

圖2 兩點(diǎn)交叉算子布局矩陣示意圖

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

圖3 在布局矩陣上進(jìn)行變異算子

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

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

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

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

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

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

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

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

5 仿真實(shí)驗(yàn)

5.1 仿真環(huán)境

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

5.2 仿真結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)語

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