孫國強

摘要：數(shù)據(jù)布局策略作為數(shù)據(jù)管理的重要方面，對研究多數(shù)據(jù)中心環(huán)境下的數(shù)據(jù)布局有著重要意義。針對多數(shù)據(jù)中心的數(shù)據(jù)檢索、更新和全局負載均衡3個目標(biāo)對數(shù)據(jù)布局方案進行求解和優(yōu)化。提出一種改進的多目標(biāo)遺傳算法，該算法以降低多數(shù)據(jù)中心的數(shù)據(jù)檢索和更新代價作為優(yōu)化目標(biāo)，并結(jié)合負載均衡作為約束條件。實驗顯示該算法不僅在數(shù)據(jù)布局方面有良好性能，而且能夠獲得較高的資源利用率。

關(guān)鍵詞：海量數(shù)據(jù)；多中心；遺傳算法；多目標(biāo)優(yōu)化；數(shù)據(jù)布局

DOIDOI：10.11907/rjdk.143666

中圖分類號：TP311.5

文獻標(biāo)識碼：A 文章編號文章編號：16727800（2015）001005902

0 引言

從海量數(shù)據(jù)中挖掘有效信息，為規(guī)劃建設(shè)和生產(chǎn)提供輔助決策已成為一種趨勢。然而如何在多數(shù)據(jù)中心環(huán)境下實現(xiàn)對海量數(shù)據(jù)的有效存儲、訪問和管理變得至關(guān)重要，具體表現(xiàn)為：一方面提高數(shù)據(jù)檢索應(yīng)用的可靠性，減少由于數(shù)據(jù)檢索和更新不同步而造成的“臟數(shù)據(jù)”或“過時數(shù)據(jù)”，降低跨數(shù)據(jù)中心執(zhí)行事務(wù)數(shù)據(jù)傳輸所導(dǎo)致的時間開銷，進而提升執(zhí)行效率；另一方面合理的數(shù)據(jù)布局方案，應(yīng)在對應(yīng)用執(zhí)行效率進行優(yōu)化的前提下，兼顧多數(shù)據(jù)中心之間工作負載的均衡性，盡量提高并行處理能力。

目前，多種數(shù)據(jù)布局方法被相繼提出，但由于數(shù)據(jù)分配問題本身的復(fù)雜性，大部分都存在不足之處。為更好地解決數(shù)據(jù)布局問題， 作者在查閱大量相關(guān)文獻和論文資料的基礎(chǔ)上，提出了基于多目標(biāo)遺傳算法來解決多中心海量數(shù)據(jù)布局的目標(biāo)優(yōu)化問題。該算法以降低多數(shù)據(jù)中心的數(shù)據(jù)檢索和更新代價作為優(yōu)化目標(biāo)，并結(jié)合負載均衡作為約束條件。模擬仿真結(jié)果表明了該算法的有效性。

1 多數(shù)據(jù)中心數(shù)據(jù)布局模型

1.1 多數(shù)據(jù)中心系統(tǒng)

多數(shù)據(jù)中心系統(tǒng)，是由地理位置分散而管理和控制又需要不同程度集中的多個邏輯單位（通常是集中式數(shù)據(jù)庫系統(tǒng)）使用計算機網(wǎng)絡(luò)聯(lián)接起來，共同組成的一個統(tǒng)一的數(shù)據(jù)庫系統(tǒng)。對于多數(shù)據(jù)中心的數(shù)據(jù)分配問題，可以描述為設(shè)有一個由站點集S=（S1，S2......Sm）組成的網(wǎng)絡(luò)，其上運行一個事務(wù)集T=（T1，T2......Tq），存儲著一個片段集F=（F1，F(xiàn)2......FN），按照某個原則將每個片段Fi的不同副本分配到不同的站點Sk上的分配方案，表示為A（F，S，T），使其分配代價最優(yōu)[1]。數(shù)據(jù)分配問題對整個數(shù)據(jù)中心應(yīng)用系統(tǒng)的可靠性、可用性和數(shù)據(jù)中心的效率有很大影響。數(shù)據(jù)分配方法優(yōu)劣的度量標(biāo)準(zhǔn)通常是最小代價和性能，在優(yōu)劣的度量問題上，國內(nèi)外學(xué)者均偏向于代價優(yōu)化，提出的優(yōu)化函數(shù)也大多基于代價函數(shù)。但在分配數(shù)據(jù)時，均衡系統(tǒng)的負載也是需要慎重考慮的因素之一。

1.2 數(shù)據(jù)布局?jǐn)?shù)學(xué)模型

適應(yīng)度是個體優(yōu)劣的評價標(biāo)準(zhǔn)，在遺傳過程中適應(yīng)度低的個體將被淘汰[2]。本文使用參考文獻[1]中的代價公式作為適應(yīng)度評價的標(biāo)準(zhǔn)。其中，適應(yīng)度函數(shù)為Min（Tota1Cost）。

TotalCost=TQ+TU（1）

其中， TQ 表示所有事務(wù)的檢索數(shù)據(jù)量，TU表示所有事務(wù)的更新數(shù)據(jù)量。對于所有站點上發(fā)生的所有事務(wù)，其總的檢索數(shù)據(jù)量TQ和總的更新數(shù)據(jù)量TU分別為：

TQ=∑S∑T∑FVtran（Sk，Sf）FRE_Q（Ti，Sk）SEL_Q（Ti，F(xiàn)j）Size（Fj）（2）

TU=∑S∑T∑FVtran（Sk，Sf）FRE_U（Ti，Sk）SEL_U（Ti，F(xiàn)j）Size（Fj）（3）

其中，Ti為事務(wù)，F(xiàn)j為數(shù)據(jù)片段，Sf為站點，Sk為在站點Sk上的事務(wù)Ti所訪問的數(shù)據(jù)片段Fj的副本所在的站點，若站點Sk本地有數(shù)據(jù)片段Fj的副本，則Sf等于Sk，否則為Sf使Vtran（Sk，Sf）達到最小值的站點；Vtran（Sk，Sf）為站點Sk與站點Sf間的通信代價系數(shù)，F(xiàn)RE_Q（Ti，Sk）為由站點Sk發(fā)出的事務(wù)Ti執(zhí)行檢索操作的頻率，SEL_Q（Ti，F(xiàn)j）為事務(wù)Ti對數(shù)據(jù)片段Fj的檢索訪問百分比，Size（Fj）為數(shù)據(jù)片段Fj的大??；Sf為在站點Sk上的事務(wù)Ti所訪問的數(shù)據(jù)片段Fj的任一副本所在站點，即所有擁有數(shù)據(jù)片段Fj副本的站點，F(xiàn)RE_U（Ti，Sk）為由站點Sk發(fā)出的事務(wù)Ti執(zhí)行更新操作的頻率，SEL_U（Ti，F(xiàn)j）為事務(wù)Ti對數(shù)據(jù)片段Fj的更新訪問百分比。

交叉概率和變異概率是遺傳算法中影響算法收斂性的重要參數(shù)，是控制算法搜索速度和求解質(zhì)量的關(guān)鍵[2]。本文采用自適應(yīng)調(diào)節(jié)策略，其中自適應(yīng)交叉算子和自適應(yīng)變異算子，分別如式（4）和式（5）[3]。

Pm=Pm1-（Pm1-Pm2）（Fmax-Fm）Fmax-Favg Fc≥Favg Pm1 Fc

Pc=Pc1-（Pc1-Pc2）（Fc-Favg）Fmax-Favg Fm≥Favg Pc1 Fm

其中，Pc1 =0.9，Pc2=0.6， Fc是參與交叉操作的兩個個體中較大的適應(yīng)度；Pm1 =0.1，Pm2=0.001，F(xiàn)max和Favg是上一代群體中最大適應(yīng)度和平均適應(yīng)度，F(xiàn)m是變異個體的適應(yīng)度。

1.3 分配策略流程圖

遺傳算法具有高度的并行性和魯棒性等優(yōu)良性能。算法的思想簡單，運行方式和實現(xiàn)步驟規(guī)范，能夠在深度優(yōu)先搜索和廣度優(yōu)先搜索之間維持很好的平衡[4]。因此，本文的分配策略有較高的執(zhí)行效率和較強的求全局最優(yōu)解的能力，且易于實現(xiàn)。求解流程如圖1所示。

圖1 分配策略基本流程

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

2.1 染色體編碼

二進制編碼方案具有編碼、解碼操作簡單易行，選擇、交叉和變異等遺傳操作便于實現(xiàn)，符合最小符號集編碼原則，便于利用模式定理對算法進行理論分析的優(yōu)點[5]。因此，對每個個體采用二進制編碼，編碼長度等于數(shù)據(jù)中心的個數(shù)n，編碼順序與其順序相對應(yīng)，1表示將該數(shù)據(jù)片段分配給相應(yīng)位置的數(shù)據(jù)中心，0則相反。以6個站點為例說明，編碼為001100的個體表示將數(shù)據(jù)片段分配給中間兩個數(shù)據(jù)中心，這樣，每個數(shù)據(jù)片段的分配方案就可以用一個二進制編碼的個體表示。

2.2 適應(yīng)度函數(shù)設(shè)計

適應(yīng)度是反映個體所代表的分配方案優(yōu)劣的標(biāo)準(zhǔn)[6]。在本文中更新檢索總代價越大的分配方案中的個體適應(yīng)度就越高。其中，檢索代價公式如式（6），更新代價計算公式如式（7）。

TQ=∑S∑TVtran（Sk，Sf）FRE_Q（Ti，Sk）SEL_Q（Ti，F(xiàn)j）Size（Fj）（6）

TU=∑S∑TVtran（Sk，Sf）FRE_U（Ti，Sk）SEL_U（Ti，F(xiàn)j）Size（Fj）（7）

TQ+TU代表了個體的更新檢索總代價，顯然，總代價越小表示其適應(yīng)度越高。個體的適應(yīng)度為：

Fi=1TQ+TU（8）

2.3 遺傳操作

為維持算法收斂性和群體中個體多樣性二者之間的平衡，采用上文提及的交叉概率為Pc的自適應(yīng)交叉算子和變異概率為Pm的自適應(yīng)變異算子對個體進行操作。為保證子代群體中適應(yīng)度最高的個體優(yōu)于父代群體中適應(yīng)度最高的個體，采用適應(yīng)度比例和最優(yōu)保存策略相結(jié)合的選擇機制，最優(yōu)保存策略是算法收斂性的基本保障。最優(yōu)保存策略[7]將當(dāng)代群體中適應(yīng)度最佳的個體記錄下來，保留到下一代。這不僅能防止其被遺傳操作破壞，還能提高群體平均適應(yīng)度值和最優(yōu)個體適應(yīng)度值。對進行交叉和變異操作產(chǎn)生的新個體，計算每個個體的適應(yīng)度，選出適應(yīng)度最小的個體，用前面所記錄的最優(yōu)個體代替，這樣就產(chǎn)生了進入下一代的群體。

2.4 約束/終止條件

為保證數(shù)據(jù)中心的正常運轉(zhuǎn)，算法將負載失衡值作為個體的約束條件。本文設(shè)計的負載均衡值為各數(shù)據(jù)中心使用率的標(biāo)準(zhǔn)差，該值越小，負載越均衡。

Load=∑mi=1（Numi-nm）2（9）

通過預(yù)先設(shè)立的閾值，在進化過程中，個體的負載失衡值必須小于該閾值，才能保留到下一代。如果數(shù)據(jù)中心的使用率超過該閾值，則認(rèn)為該數(shù)據(jù)中心處于超負荷狀態(tài)。若初始數(shù)據(jù)布局方案和子代數(shù)據(jù)布局方案使至少一個數(shù)據(jù)中心在事務(wù)開始執(zhí)行前已處于超負荷狀態(tài)，則視為無效解。

遺傳算法的終止條件一般是適應(yīng)度達到了要求的值，或是進化到了一定的代數(shù)。算法一旦終止，便選擇當(dāng)前種群中的最優(yōu)個體為最終結(jié)果[8]。

3 結(jié)語

在多種環(huán)境下的測試中，用本文算法進行求解，得到的解大多等于或者接近于最優(yōu)解。通過采用自適應(yīng)的交叉算子和變異算子，算法的全局搜索能力得到很好的體現(xiàn)。通過把數(shù)據(jù)中心的負載失衡值作為算法執(zhí)行的約束條件，明顯提高了數(shù)據(jù)中心的利用率。

本文提出的一種基于雙適應(yīng)度的遺傳算法的數(shù)據(jù)布局算法，不僅將多數(shù)據(jù)中心的數(shù)據(jù)檢索和更新的代價作為一個重要的判斷標(biāo)準(zhǔn)，而且對求解過程各階段的布局方案進行優(yōu)化，即基于一定的約束條件生成較優(yōu)的方案，提高了求解質(zhì)量。但由于研究時間和實驗條件有限，還存在一些問題有待改進，比如文中有一些統(tǒng)計信息不夠全面，沒有考慮到事務(wù)與片段訪問之間的聯(lián)系等，這些因素可能對最后結(jié)果造成一定影響，因此需要進一步研究。