基于遺傳算法的分布式數(shù)據(jù)庫數(shù)據(jù)分配策略研究

袁 旭，孫紀(jì)敏

(中國電子科技集團(tuán)公司第五十四研究所，河北 石家莊050081)

基于遺傳算法的分布式數(shù)據(jù)庫數(shù)據(jù)分配策略研究

袁 旭，孫紀(jì)敏

(中國電子科技集團(tuán)公司第五十四研究所，河北 石家莊050081)

為進(jìn)一步提升分布式數(shù)據(jù)庫系統(tǒng)的訪問效率，對數(shù)據(jù)分配問題進(jìn)行分析，并結(jié)合實(shí)際應(yīng)用構(gòu)建出相應(yīng)的數(shù)學(xué)模型。在現(xiàn)有以遺傳算法求解該問題的研究基礎(chǔ)上，重新優(yōu)化了遺傳算法，如采取選育措施得到優(yōu)良初始種群、以順序選擇和最佳保存相結(jié)合的手段進(jìn)行個(gè)體選擇、利用大變異操作拓寬算法搜索廣度等，進(jìn)而提出了一種新的數(shù)據(jù)分配策略。仿真結(jié)果表明，與其他分配方法相比，運(yùn)用該策略能夠求得更為理想的數(shù)據(jù)分配方案。

數(shù)據(jù)分配；遺傳算法；分布式數(shù)據(jù)庫；數(shù)據(jù)存儲(chǔ)

0 引言

隨著企業(yè)信息化的逐步深入，業(yè)務(wù)數(shù)據(jù)高速增長、日益龐大，對數(shù)據(jù)存儲(chǔ)的要求不斷提高[1]，傳統(tǒng)集中式數(shù)據(jù)庫的弊端愈加凸顯。而分布式數(shù)據(jù)庫則以其擴(kuò)展能力強(qiáng)、成本優(yōu)勢大以及使用效果優(yōu)等諸多特點(diǎn)[2]贏得了廣闊的發(fā)展空間。分布式系統(tǒng)中，數(shù)據(jù)存儲(chǔ)主要包括數(shù)據(jù)分片與數(shù)據(jù)分配兩部分[3]。數(shù)據(jù)分片是指將全局?jǐn)?shù)據(jù)在邏輯上劃分成多個(gè)數(shù)據(jù)片段，數(shù)據(jù)分配則指的是將這些數(shù)據(jù)片段在物理上分配到系統(tǒng)各個(gè)工作站點(diǎn)上。作為分布式數(shù)據(jù)庫核心設(shè)計(jì)環(huán)節(jié)，數(shù)據(jù)分配影響著系統(tǒng)效率和性能，是系統(tǒng)優(yōu)化改進(jìn)所需要考慮的關(guān)鍵性問題之一[4]。

對于數(shù)據(jù)分配問題，不同學(xué)者研究角度不同，得到的見解也不盡相同，例如文獻(xiàn)[5-6]二者的觀點(diǎn)也存在著差異。本文研究則面向數(shù)據(jù)處理局部性，是以減少各站點(diǎn)間的通信總代價(jià)為主要目標(biāo)的。該方向上，有關(guān)學(xué)者給出了多種分配策略，如非冗余分配最佳適宜法、冗余分配添加副本法、啟發(fā)式試消副本法[7]、基于數(shù)據(jù)片段訪問特性的分配策略[8]、基于遺傳算法的數(shù)據(jù)分配策略[9-11](本文稱之為“GA1法”)等等。本文在GA1法的基礎(chǔ)上進(jìn)行研究，重新優(yōu)化了遺傳算法，提出了改良后的數(shù)據(jù)分配策略，即GA2法。

1 數(shù)據(jù)分配問題的數(shù)學(xué)模型

1.1 應(yīng)用需求及問題描述

由6個(gè)位于不同城市的網(wǎng)絡(luò)單元組成一個(gè)工作場景，每個(gè)網(wǎng)絡(luò)單元中存在一個(gè)或多個(gè)工作站點(diǎn)，其內(nèi)部信息交換是基于如圖1所示的網(wǎng)絡(luò)而實(shí)現(xiàn)的。在該工作場景的信息化建設(shè)中，很有必要采用分布式的數(shù)據(jù)存儲(chǔ)方式。此時(shí)，數(shù)據(jù)分配問題需要充分考慮。

圖1 某工作場景網(wǎng)絡(luò)簡圖

結(jié)合上述，對數(shù)據(jù)分配問題描述如下：

分布式系統(tǒng)中存在一個(gè)存儲(chǔ)著數(shù)據(jù)片段集F=(F1,F2,F3,F4,…,Fq)的站點(diǎn)集合S=(S1,S2,S3,S4,…,Sm)，其各站點(diǎn)由計(jì)算機(jī)網(wǎng)絡(luò)連接起來。系統(tǒng)內(nèi)運(yùn)行著檢索事務(wù)集Q=(Q1,Q2,Q3,…,Qn1)和更新事務(wù)集U=(U1,U2,U3,…,Un2)。按照一定的方式將每個(gè)片段F(或副本)合理地分配到不同的站點(diǎn)S上能使整個(gè)系統(tǒng)的網(wǎng)絡(luò)通信總代價(jià)最小，分配方案記為FAT。

1.2 統(tǒng)計(jì)信息

實(shí)際應(yīng)用中系統(tǒng)通信代價(jià)的影響因素紛繁龐雜，在量化研究過程中只能對相關(guān)信息進(jìn)行有所依據(jù)的選取和簡化處理，以降低問題的復(fù)雜性。最終采用的統(tǒng)計(jì)信息如下：

① 數(shù)據(jù)片段大小(size_f，行向量)，體現(xiàn)各數(shù)據(jù)片段中的數(shù)據(jù)量；

② 訪問控制信息：檢索訪問矩陣(rm)和更新訪問矩陣(um)，分別體現(xiàn)檢索事務(wù)與更新事務(wù)(行項(xiàng))對數(shù)據(jù)片段(列項(xiàng))的訪問需求。其中數(shù)字1表示需要訪問，0表示無需訪問；

③ 訪問選擇信息：檢索選擇矩陣(sel_r)和更新選擇矩陣(sel_u)，分別體現(xiàn)檢索事務(wù)與更新事務(wù)的訪問選擇性，即不同事務(wù)(行項(xiàng))對不同數(shù)據(jù)片段(列項(xiàng))的數(shù)據(jù)訪問量與該片段大小的百分比；

④ 事務(wù)頻率信息：檢索頻率矩陣(freq_r)和更新頻率矩陣(freq_u)，分別體現(xiàn)各檢索事務(wù)與更新事務(wù)(行項(xiàng))在不同工作站點(diǎn)(列項(xiàng))上發(fā)生的頻率；

⑤ 網(wǎng)絡(luò)傳輸信息：通信代價(jià)系數(shù)矩陣(delay)，體現(xiàn)系統(tǒng)中單位數(shù)據(jù)于不同站點(diǎn)(行項(xiàng)、列項(xiàng))之間進(jìn)行傳輸?shù)木W(wǎng)絡(luò)延時(shí)，且假設(shè)delay(Si,Sj)=delay(Sj,Si)。

1.3 代價(jià)公式

代價(jià)公式結(jié)合各項(xiàng)統(tǒng)計(jì)信息，建立起分配方案與其評價(jià)指標(biāo)——通信代價(jià)之間的代數(shù)關(guān)系，是數(shù)學(xué)模型的重要組成部分。本文所采用的代價(jià)公式如下：

(1)

式中，sumcost為某一整體數(shù)據(jù)分配方案所對應(yīng)的通信總代價(jià)；cost(Fj)為某數(shù)據(jù)片段Fj的某一分配方案所對應(yīng)的通信代價(jià)，其計(jì)算公式為：

cost(Fj)=TQ(Fj)+TU(Fj),

(2)

式中，TQ(Fj)、TU(Fj)分別為數(shù)據(jù)片段Fj的分配方案所對應(yīng)的檢索、更新事務(wù)通信代價(jià)，其計(jì)算公式為式(3)和式(4)。

(3)

(4)

1.4 數(shù)學(xué)模型的構(gòu)建與求解

在數(shù)據(jù)分配問題中，假設(shè)工作站點(diǎn)S的數(shù)量為m，則某片段Fj的分配方案可以用一個(gè)長度為m的二進(jìn)制串結(jié)構(gòu)數(shù)據(jù)來表示。若Fj被分配到站點(diǎn)Sk上，則該串結(jié)構(gòu)數(shù)據(jù)第k個(gè)數(shù)位上的數(shù)字為1，反之為0。由此易知，片段Fj共有(2m-1)種分配方案，分別對應(yīng)著不同的通信代價(jià)cost (Fj)。假設(shè)數(shù)據(jù)片段數(shù)量為q，則整個(gè)系統(tǒng)數(shù)據(jù)分配方案可表示為一個(gè)q行m列的0～1矩陣，共有(2m-1)q種，對應(yīng)著不同的通信總代價(jià)sumcost。

數(shù)據(jù)分配問題的實(shí)質(zhì)是一個(gè)典型的NP組合優(yōu)化問題，其數(shù)學(xué)模型的目標(biāo)函數(shù)為min(sumcost)，其求解過程就是從其由(2m-1)q個(gè)q行m列的0～1矩陣組成的解空間中找出一個(gè)最優(yōu)解(或滿意解)，即能使sumcost取最小(或近似最小)值的矩陣。

2 基于遺傳算法的數(shù)據(jù)分配改良策略

遺傳算法(Genetic Algorithm，GA)是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來的隨機(jī)搜索技術(shù)[12-13]，具有獨(dú)特的算法形式與運(yùn)行機(jī)理，是求解非線性復(fù)雜優(yōu)化問題的有力工具[14]。此前，已有學(xué)者嘗試?yán)眠z傳算法來求解數(shù)據(jù)分配問題并提出了GA1法。而本文所提出的GA2法同樣基于遺傳算法，宏觀運(yùn)算框架也與GA1法相似，仍不考慮各數(shù)據(jù)片段之間的關(guān)聯(lián)，依次對數(shù)據(jù)片段集合中每一個(gè)數(shù)據(jù)片段的分配問題利用遺傳算法分別求解，再進(jìn)行整合得到最終的數(shù)據(jù)分配方案。但在對遺傳算法的改進(jìn)手法上，GA2法卻有自己的特點(diǎn)。

現(xiàn)結(jié)合遺傳算法運(yùn)算流程，如圖2所示，對某一數(shù)據(jù)片段Fj分配問題的求解過程進(jìn)行簡要說明。

圖2 遺傳算法流程圖

① 設(shè)定進(jìn)化參數(shù)。根據(jù)實(shí)際問題，適當(dāng)設(shè)定需要預(yù)先給出的進(jìn)化參數(shù)，如群體大小np，終止進(jìn)化代數(shù)ng等。

② 編碼成串位。將問題的解即某數(shù)據(jù)片段Fj的分配方案用二進(jìn)制的串結(jié)構(gòu)數(shù)據(jù)來表示，具體編碼規(guī)則見1.4節(jié)。

③ 初始化群體。初始群體的特性對計(jì)算結(jié)果和計(jì)算效率均有重要影響[15]。GA2法采取選育措施來進(jìn)行初始化，即：首先隨機(jī)生成女排np0個(gè)個(gè)體，然后從中選取所對應(yīng)通信代價(jià)最低的np個(gè)個(gè)體組成初始種群。這樣操作能夠在一定程度上保證初始種群中個(gè)體的優(yōu)良程度。

④ 計(jì)算個(gè)體適應(yīng)度值。利用式(2)、式(3)和式(4)依次求得群體中各個(gè)個(gè)體所對應(yīng)的通信代價(jià)，此代價(jià)的倒數(shù)即該個(gè)體的適應(yīng)度值。

⑤ 選擇操作。GA2法將最優(yōu)保存和順序選擇相結(jié)合來進(jìn)行個(gè)體選擇操作。

最優(yōu)保存，當(dāng)子代最優(yōu)個(gè)體的適應(yīng)度不及父代時(shí)，以父代最優(yōu)個(gè)體取代子代最差個(gè)體，是算法收斂性的一個(gè)重要保證條件[15]。

順序選擇[16]利用個(gè)體適應(yīng)度的排序?qū)⑦x擇概率固定化，從而建立起相對穩(wěn)定的選擇過程，避免個(gè)別超級(jí)個(gè)體獨(dú)霸種群的同時(shí)，也使得個(gè)體選擇在個(gè)體間適應(yīng)度相差不大的情況下仍能有效進(jìn)行。其具體步驟為：首先計(jì)算群體中所有個(gè)體(數(shù)量為np)的適應(yīng)度值并降序排列；再令參數(shù)p0取1/np，根據(jù)式(5)依次計(jì)算出排序后各個(gè)體(序號(hào)為j)的選擇概率。

(5)

⑥ 交叉操作。為提高算法執(zhí)行效率，GA2法采用簡單常數(shù)概率pc下的單點(diǎn)交叉。

⑦ 變異操作。未成熟收斂(Premature Convergence，PC)是遺傳算法中特有現(xiàn)象，且十分常見[15]。傳統(tǒng)遺傳算法中，為保證算法穩(wěn)定性，變異概率取值通常很小，一旦出現(xiàn)早熟收斂，將很難跳出局部最優(yōu)解。因此，GA2法采用了大變異操作[16]以便能夠及時(shí)隨機(jī)、獨(dú)立地產(chǎn)生許多新個(gè)體，快速增加種群多樣性，有效幫助種群脫離早熟，進(jìn)而求得更為理想的解。其具體過程為：

i.判斷某一代群體中個(gè)體的最大適應(yīng)度fmax與平均適應(yīng)度favg是否滿足條件t*fmax

ii.當(dāng)步驟i中滿足條件時(shí)，以一個(gè)比通常概率pm大5倍以上的大變異概率pmax執(zhí)行變異操作，否則仍以通常概率pm執(zhí)行變異操作。其中，pmax越大，算法越穩(wěn)定，但這是以犧牲收斂速度為代價(jià)的。若pmax取0.5，則大變異操作就近似蛻化成了隨機(jī)搜索。

另，第gen代群體經(jīng)過選擇、交叉、變異等操作后，得到第(gen+1)代群體。

⑧ 判斷是否滿足終止準(zhǔn)則。若當(dāng)前該種群進(jìn)化代數(shù)gen不大于終止進(jìn)化代數(shù)ng，則轉(zhuǎn)到第⑤步，繼續(xù)進(jìn)化。反之，若gen大于ng，則確定得到最終群體，進(jìn)入第⑨步；

⑨ 解碼最終群體適應(yīng)度最高的個(gè)體，得到片段Fj的最優(yōu)(或近似最優(yōu))分配方案。

3 仿真實(shí)驗(yàn)及結(jié)果分析

3.1 仿真實(shí)驗(yàn)及運(yùn)算結(jié)果

在實(shí)驗(yàn)中，工作站點(diǎn)S的數(shù)量不超過5，此時(shí)問題的解空間較小，完全能夠以全遍歷法直接求取最優(yōu)解，采用其他方法的意義不大。因此，本文實(shí)驗(yàn)中的工作站點(diǎn)數(shù)量取值適當(dāng)?shù)卦龃蟆?/p>

結(jié)合網(wǎng)絡(luò)場景簡圖1，假設(shè)有6個(gè)數(shù)據(jù)片段F、7項(xiàng)檢索事務(wù)Q、7項(xiàng)更新事務(wù)U以及10個(gè)工作站點(diǎn)S，且其中S1～3(A城)、S4(B城)、S5(C城)、S6(D城)、S7～8(E城)、S9～10(F城)分別位于不同城市的網(wǎng)絡(luò)單元內(nèi)。單位數(shù)據(jù)在同一網(wǎng)絡(luò)單元局域網(wǎng)中傳輸?shù)臅r(shí)延及其影響都很小，且設(shè)本地訪問的通信代價(jià)系數(shù)為0.1。據(jù)此模擬出實(shí)驗(yàn)環(huán)境I的各項(xiàng)統(tǒng)計(jì)信息(取相對值)如圖3所示。

實(shí)驗(yàn)過程中，GA2法遺傳算法的各項(xiàng)參數(shù)取值分別為：群體大小np=11；終止進(jìn)化代數(shù)ng=50；群體初始化時(shí)預(yù)選個(gè)體數(shù)np0=50；交叉概率pc=0.9；大變異操作時(shí)，通常變異概率pm=0.05，大變異概率pmax=0.4，密集因子t∈[0.8,0.9]，且隨進(jìn)化代數(shù)gen增加而逐漸減小，其取值如式(6)所示：

(6)

圖3 實(shí)驗(yàn)環(huán)境I中統(tǒng)信息

除實(shí)驗(yàn)環(huán)境I外，本文還模擬了站點(diǎn)數(shù)量分別為15和20的兩個(gè)實(shí)驗(yàn)環(huán)境II和III。限于篇幅，其統(tǒng)計(jì)信息及相關(guān)參數(shù)不再列出。

在3種實(shí)驗(yàn)環(huán)境I、II、III下，分別運(yùn)用非冗余分配最佳適宜法(簡稱“最佳法”)，冗余分配添加副本法(簡稱“添加法”)，啟發(fā)式試消副本法(簡稱“試消法”)，基于數(shù)據(jù)片段訪問特性的分配策略(簡稱“特性法”)、GA1法及GA2法在Matlab工具上進(jìn)行求解運(yùn)算。其中GA1法、GA2法的運(yùn)算結(jié)果具有隨機(jī)性，此處取若干次運(yùn)算的平均值，且相同環(huán)境下GA1法與GA2法種群大小及遺傳終止代數(shù)取值相等。運(yùn)算結(jié)果，即所得最終分配方案對應(yīng)的通信總代價(jià)(數(shù)量級(jí)為105，越小越好)如表1所示。

表1 3種實(shí)驗(yàn)環(huán)境下不同分配策略的運(yùn)算結(jié)果

3.2 實(shí)驗(yàn)結(jié)果分析及GA2法優(yōu)越性的總結(jié)

3.1節(jié)中3種實(shí)驗(yàn)環(huán)境下的最佳分配方案都有一定的冗余度，采用非冗余分配最佳適宜法得到的方案自然不夠理想；使用冗余分配添加副本法、試消副本法及基于片段訪問特性的分配策略時(shí)，所得分配方案相對較好，但鑒于搜索廣度有限，多數(shù)情況下仍存在可進(jìn)一步優(yōu)化的空間；由GA1法得到分配方案的質(zhì)量最差，在實(shí)驗(yàn)環(huán)境II、III下甚至不如非冗余分配最佳適宜法；而GA2法在時(shí)耗不超過GA1法的前提下，所求得的分配方案對應(yīng)的通信總代價(jià)最低。因此，相比其他策略，GA2法擁有更加優(yōu)越的特性。

與同樣基于遺傳算法的GA1法相比，GA2法的優(yōu)越性主要體現(xiàn)在以下幾個(gè)方面：① 育種獲得高質(zhì)量的初始種群，使得搜索過程擁有較好的起點(diǎn)；② 順序選擇與最優(yōu)保存相結(jié)合的選擇機(jī)制在保證算法收斂性的同時(shí)，也促使選擇操作更加穩(wěn)定、有效；③ 大變異操作根據(jù)當(dāng)前種群特征，及時(shí)補(bǔ)充種群多樣性，提高了算法全局搜索能力。

4 結(jié)束語

在大型復(fù)雜工作場景的信息化建設(shè)中，本文基于改進(jìn)遺傳算法的數(shù)據(jù)分配策略能夠?yàn)闃I(yè)務(wù)數(shù)據(jù)的分布式存儲(chǔ)提供理論上的參考與支持。且相比于其他策略，以該策略為指導(dǎo)來解決數(shù)據(jù)分配問題更有利于系統(tǒng)整體訪問效率的提高。但該策略只是一種靜態(tài)的分配策略，仍有需要完善的地方，比如構(gòu)建數(shù)學(xué)模型時(shí)為降低問題復(fù)雜度而忽略了一些次要影響因素，算法中部分參數(shù)的取值仍有待優(yōu)化等等。這些問題將在后續(xù)研究中做進(jìn)一步分析。

[1] 李琳琳,王慶超,姚 超,等.云存儲(chǔ)中的數(shù)據(jù)冗余策略研究[J].無線電工程,2013,43(9): 1-3,32.

[2] 齊 磊.大數(shù)據(jù)分析場景下分布式數(shù)據(jù)庫技術(shù)的應(yīng)用[J].移動(dòng)通信,2015,39(12):58-62.

[3] 岳立營.淺談分布式數(shù)據(jù)庫的數(shù)據(jù)存儲(chǔ)[J].科技創(chuàng)新導(dǎo)報(bào),2011(6):112.

[4] 南菊松.分布式數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)分配算法的研究[D].武漢:華中科技大學(xué),2013.

[5] Tamer O M,Patriek V.Principles of Distributed Database Systems(Second Edition)[M].北京:清華大學(xué)出版社,2002.

[6] Huang Y F,Chen J H.Fragment Allocation in Distributed Database Design[J].Journal of Information Science & Engineering,2001,17(3):491-506.

[7] 楊 藝.分布式數(shù)據(jù)庫中數(shù)據(jù)分配方法的研究[D].重慶:重慶大學(xué),2004.

[8] 楊 洲.分布式數(shù)據(jù)庫中數(shù)據(jù)分配策略的研究[D].哈爾濱:哈爾濱工程大學(xué),2007.

[9] 李 想.分布式數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)分配策略的研究[D].大連:大連理工大學(xué),2009.

[10] 王三虎.基于遺傳算法的分布式數(shù)據(jù)庫數(shù)據(jù)分配研究[J].西安石油大學(xué)學(xué)報(bào),2012,27(2):102-105.

[11] 張德生.基于遺傳算法的大型數(shù)據(jù)庫的數(shù)據(jù)分配策略算法[J].科技通報(bào),2015,31(1):162-165.

[12] 彭 璐，何加銘.基于遺傳算法的多約束QoS單播路由算法[J].移動(dòng)通信，2015，39(6)：76-81.

[13] 王小平,曹立明.遺傳算法—理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,2002.

[14] 談 敏,蔡 鈞.基于改進(jìn)遺傳算法的雙頻濾波器自動(dòng)設(shè)計(jì)[J].無線電工程,2012,42(10):48-50.

[15] 雷英杰,張善文.遺傳算法工具箱及應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2014.

[16] 龔 純,王正林.精通MATLAB最優(yōu)化計(jì)算(第2版)[M].北京:電子工業(yè)出版社,2012.

Research of Data Allocation Strategy in DDB Based on Genetic Algorithm

YUAN Xu,SUN Ji-min

(The 54th Research Institute of CETC,Shijiazhuang Hebei 050081,China)

In order to improve further the accessing efficiency of DDBS,this paper analyzes the data allocation problem and builds a corresponding mathematical model in consideration of practical application.Based on the existing research of solving this problem with genetic algorithm,new measures are adopted to improve the genetic algorithm,for examples,an excellent original population is created by selective breeding in the initialization phase,the individuals are chosen by a rule which combines order selection and elitist selection during the evolutionary process,the big mutation is utilized to broaden the searching extent of the algorithm,and so on.Then a new data allocation strategy is put forward.The simulation results show that this strategy can be used to get a better data allocation scheme compared with other methods.

data allocation;genetic algorithm;distributed database;data storage

10.3969/j.issn.1003-3114.2017.01.10

袁 旭,孫紀(jì)敏.基于遺傳算法的分布式數(shù)據(jù)庫數(shù)據(jù)分配策略研究[J].無線電通信技術(shù)，2017，43(1):39-43.

2016-09-19

國家部委基金資助項(xiàng)目

袁 旭(1991—)，男，碩士研究生，主要研究方向：分布式數(shù)據(jù)庫。孫紀(jì)敏(1963—)，女，研究員，主要研究方向：軟件工程、計(jì)算機(jī)應(yīng)用。

TP311

A

1003-3114(2017)01-39-5