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

袁 旭，孫紀(jì)敏

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

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

袁 旭，孫紀(jì)敏

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

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

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

0 引言

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

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

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

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

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

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

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

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

1.2 統(tǒng)計信息

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

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

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

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

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

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

1.3 代價公式

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

(1)

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

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

(2)

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

(3)

(4)

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

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

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

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

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

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

圖2 遺傳算法流程圖

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

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

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

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

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

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

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

(5)

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

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

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

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

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

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

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

3 仿真實驗及結(jié)果分析

3.1 仿真實驗及運算結(jié)果

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

結(jié)合網(wǎng)絡(luò)場景簡圖1，假設(shè)有6個數(shù)據(jù)片段F、7項檢索事務(wù)Q、7項更新事務(wù)U以及10個工作站點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ù)為0.1。據(jù)此模擬出實驗環(huán)境I的各項統(tǒng)計信息(取相對值)如圖3所示。

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

(6)

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

[3] 岳立營.淺談分布式數(shù)據(jù)庫的數(shù)據(jù)存儲[J].科技創(chuàng)新導(dǎ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é)報,2012,27(2):102-105.

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

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

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

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

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

[16] 龔 純,王正林.精通MATLAB最優(yōu)化計算(第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

國家部委基金資助項目

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

TP311

A

1003-3114(2017)01-39-5