基于遺傳算法的多中心海量數(shù)據(jù)布局研究

孫國(guó)強(qiáng)

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

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

DOIDOI：10.11907/rjdk.143666

中圖分類(lèi)號(hào)：TP311.5

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2015）001005902

0 引言

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

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

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

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

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

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

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

TotalCost=TQ+TU（1）

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

交叉概率和變異概率是遺傳算法中影響算法收斂性的重要參數(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是參與交叉操作的兩個(gè)個(gè)體中較大的適應(yīng)度；Pm1 =0.1，Pm2=0.001，F(xiàn)max和Favg是上一代群體中最大適應(yīng)度和平均適應(yīng)度，F(xiàn)m是變異個(gè)體的適應(yīng)度。

1.3 分配策略流程圖

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

圖1 分配策略基本流程

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

2.1 染色體編碼

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

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

適應(yīng)度是反映個(gè)體所代表的分配方案優(yōu)劣的標(biāo)準(zhǔn)[6]。在本文中更新檢索總代價(jià)越大的分配方案中的個(gè)體適應(yīng)度就越高。其中，檢索代價(jià)公式如式（6），更新代價(jià)計(jì)算公式如式（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代表了個(gè)體的更新檢索總代價(jià)，顯然，總代價(jià)越小表示其適應(yīng)度越高。個(gè)體的適應(yīng)度為：

Fi=1TQ+TU（8）

2.3 遺傳操作

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

2.4 約束/終止條件

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

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

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

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

3 結(jié)語(yǔ)

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

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