云計算下大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)分配算法

張華麗，楊 帆，楊華勇

(武漢科技大學(xué)城市學(xué)院,湖北 武漢 430083)

0 引 言

隨著云計算下大數(shù)據(jù)的廣泛應(yīng)用，大數(shù)據(jù)的容積逐漸增大[1]，分布式存儲在處理大數(shù)據(jù)時具有擴(kuò)展性、可維護(hù)性、可靠性，在成本估算中都有突出的表現(xiàn)[2]，在分布式的數(shù)據(jù)庫系統(tǒng)中，通常情況中它的最大特征是存在數(shù)據(jù)冗余，云計算下分布式存儲中冗余數(shù)據(jù)的分配問題，對于確保大數(shù)據(jù)安全性具有重要意義，其成為當(dāng)下相關(guān)技術(shù)人員研究的熱點問題。

以往針對大數(shù)據(jù)冗余數(shù)據(jù)集分配問題，主要以支持向量機(jī)算法為主，該種算法分配大數(shù)據(jù)中冗余數(shù)據(jù)時，僅能進(jìn)行小樣本數(shù)據(jù)中冗余數(shù)據(jù)的分配，且不能解決大數(shù)據(jù)中的冗余數(shù)據(jù)間關(guān)聯(lián)性低的問題，具有分配效率和準(zhǔn)確率較低等弊端。如文獻(xiàn)[3]提出了一種動態(tài)非冗余數(shù)據(jù)分配方法，該方法確定了碎片更新參數(shù)和動態(tài)成本參數(shù)，根據(jù)數(shù)據(jù)遷移節(jié)點的最低代價的選擇，使用參數(shù)迭代估計片段的重新分配到節(jié)點的成本，然而，該方法冗余數(shù)據(jù)間的關(guān)聯(lián)性較低。文獻(xiàn)[4]提出基于圖覆蓋的大數(shù)據(jù)全比較數(shù)據(jù)分配算法，采用理論分析把大數(shù)據(jù)全比較的數(shù)據(jù)分配問題總結(jié)成圖覆蓋問題后，獲取圖覆蓋的最優(yōu)解，依據(jù)特解分配數(shù)據(jù)，由于過程較為復(fù)雜，導(dǎo)致數(shù)據(jù)分配的效率低；文獻(xiàn)[5]提出針對多聚類中心大數(shù)據(jù)集的加速K-means聚類算法，主要采用動態(tài)類中心調(diào)整方法對大數(shù)據(jù)進(jìn)行聚類，但是由于在K-means算法中，首先需要根據(jù)初始聚類中心來確定一個初始劃分，然后對初始劃分進(jìn)行優(yōu)化。這個初始聚類中心的選擇對聚類結(jié)果有較大的影響，聚類的準(zhǔn)確率降低，后續(xù)的冗余數(shù)據(jù)的分配準(zhǔn)確度也會降低。本文提出云計算大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)分配算法，首先對云計算大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)進(jìn)行分類，再對于分類后的冗余數(shù)據(jù)片段進(jìn)行分配，提高冗余數(shù)據(jù)的分配準(zhǔn)確率與分配效率。

1 云計算下大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)分配算法

1.1 冗余數(shù)據(jù)最優(yōu)分類函數(shù)

使用局部特征分析算法，可以獲取云計算下大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)的重要特征，把獲取的重要特征設(shè)成對云計算下大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)分類時的基本數(shù)據(jù)。由于在搜集數(shù)據(jù)時云計算的網(wǎng)絡(luò)會出現(xiàn)一定程度的遲延，而該算法不受其網(wǎng)絡(luò)遲延的影響，根據(jù)冗余數(shù)據(jù)的重要特征和相鄰領(lǐng)域的數(shù)據(jù)特征值實行對比，可以體現(xiàn)冗余數(shù)據(jù)的特征。

采用最優(yōu)分類平面對云計算下大數(shù)據(jù)分布式存儲中的冗余數(shù)據(jù)實行分類操作[6]。把冗余數(shù)據(jù)分類問題轉(zhuǎn)變成最優(yōu)平面求解的問題[6]：

其中，R(β)為二次判別函數(shù)，yj·yk為兩個向量的點積；Ζ為分類閾值，Ζj以及Ζk分別表示yj和yk兩個向量的分類閾值，β為權(quán)重向量，βj以及βk分別表示yj和yk兩個向量的權(quán)重，p為最大向量，最優(yōu)分類平面求解問題必須符合以下要求：

(2)

假定云計算下大數(shù)據(jù)分布式存儲中的冗余數(shù)據(jù)內(nèi)的特征產(chǎn)生非線性轉(zhuǎn)換[7]，那么要使用內(nèi)積L(yj,yk)替換最優(yōu)分類函數(shù)內(nèi)的點積。那么最優(yōu)分類平面求解問題可得出轉(zhuǎn)換后的結(jié)果見式(3)：

設(shè)式(4)是式(3)的最優(yōu)分類函數(shù)：

其中g(shù)(y)為最優(yōu)分類函數(shù)；c′為類別屬性。通過該函數(shù)可獲取冗余數(shù)據(jù)片段。最優(yōu)分類平面算法可以對兩種具有差異性的類別實行分類，但是云計算大數(shù)據(jù)分布式存儲中的冗余數(shù)據(jù)分類屬于多類別分類[8]，所以必須先把云計算大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)分類變換成多種二分類。同時一一求解[9]，最終提取云計算下大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)的分類結(jié)果。目前對兩種分類進(jìn)行變換通常使用一對多與一對一的分類方式。因為云計算下大數(shù)據(jù)的冗余數(shù)據(jù)的分配有一定程度的難度，冗余數(shù)據(jù)的特征數(shù)值又過多，則必須使用一對一的分類方式實行云計算下大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)分類的變換操作。

1.2 基于遺傳算法的冗余數(shù)據(jù)最優(yōu)分配算法

基于上小節(jié)獲取的云計算下大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)片段[10-11]，本文采用基于遺傳算法的冗余數(shù)據(jù)分配算法對冗余數(shù)據(jù)進(jìn)行準(zhǔn)確分類。云計算下大數(shù)據(jù)分布存儲冗余數(shù)據(jù)分配流程圖用圖1描述，

圖1 云計算下大數(shù)據(jù)分布存儲冗余數(shù)據(jù)分配流程圖

本文針對上小節(jié)獲取的云計算大數(shù)據(jù)分布式存儲中某一冗余數(shù)據(jù)片段Fj的分配過程進(jìn)行求解，構(gòu)建分配策略和評估準(zhǔn)則[12]，獲取最佳冗余數(shù)據(jù)分配策略。

代價公式是綜合每項的整體信息，其可評估冗余數(shù)據(jù)的通信代價。本文使用的代價公式為：

其中，sumcost是整個數(shù)據(jù)分配策略相應(yīng)的通信代價；g(y)是上小節(jié)獲取的云計算下大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)的分類結(jié)果，cost(Fj)是數(shù)據(jù)片段(Fj)的分配策略相應(yīng)的通信代價，它的計算公式見式(7)：

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

(6)

其中Q以及U表示不同的事物，數(shù)據(jù)片段Fj的分配策略相應(yīng)的分類、通信代價用TQ(Fj)與TU(Fj)來描述，它的計算公式為

依據(jù)上述式(1)至(8)分析的云計算大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)的分類結(jié)果以及分類過程，得到本文方法實現(xiàn)冗余數(shù)據(jù)分配策略為：

(1)設(shè)置進(jìn)化參數(shù)。依據(jù)實質(zhì)問題，合理設(shè)置提前給予的冗余數(shù)據(jù)進(jìn)化參數(shù)，例如np與ng分別代表冗余數(shù)據(jù)群體大小與終止進(jìn)化代數(shù)。

(2)編碼成串位。把問題的答案，也就是某冗余數(shù)據(jù)片段Fj的分配策略根據(jù)二進(jìn)制的串結(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ù)據(jù)片段數(shù)目是q，那么整體系統(tǒng)冗余數(shù)據(jù)分配策略體現(xiàn)是一個q行m列的0～1矩陣，總計(2m-1)q種，且具有相應(yīng)的不一樣的通信總代價sumcost。

(3)初始化群體。計算結(jié)果與效率受冗余數(shù)據(jù)初始群體的特征所干擾。基于遺傳算法的冗余數(shù)據(jù)分配算法采用選育方式實行初始化[13]，也稱：第一步隨機(jī)組成np0個個體，第二步在其中提取相應(yīng)通信代價最小的np個個體構(gòu)成初始種群。此處理可以保障冗余數(shù)據(jù)初始群內(nèi)個體的優(yōu)異水準(zhǔn)。

(4)計算個體適應(yīng)度值。使用式(7)、(8)、(9)逐次獲取冗余數(shù)據(jù)群體內(nèi)每個個體相應(yīng)的通信代價，該代價的倒數(shù)就是此個體的適應(yīng)度的數(shù)值。

(5)選擇處理。基于遺傳算法的冗余數(shù)據(jù)分配算法把最優(yōu)儲存與數(shù)據(jù)抉擇綜合起來實行個體選取處理。

最優(yōu)保存：在子代最有個體的適應(yīng)度沒有父代的優(yōu)秀時，根據(jù)父代最優(yōu)個體代替子代最劣個體，可保障算法的收斂性。

順序選擇：為了構(gòu)建相應(yīng)穩(wěn)定的選取流程，防止某個超級個體在種群中過大，根據(jù)個體適應(yīng)度的順序?qū)x擇概率固定化，從而讓個體選擇在個體間適應(yīng)度差距不大的狀況下可以順利操作[14]。詳細(xì)流程是：第一步計算群體內(nèi)全部個體的適應(yīng)度數(shù)值同時進(jìn)行降序布列，個體的數(shù)目是np；第二步設(shè)置參數(shù)p0為1/np，使用公式(10)逐次計算有順序后每個個體的選取概率。其中每個個體的序號是j。

(6)交叉處理。GA2法使用簡單常數(shù)概率pc下的單點交叉可以增強(qiáng)算法實行效率。

(7)變異處理。沒有成熟收斂(Premature Convergence)為遺傳算法內(nèi)經(jīng)常出現(xiàn)的專有的情景。由于以往的遺傳算法內(nèi)，想要保障算法的不出現(xiàn)異常，變異概率的取值一般較小，若是產(chǎn)生早熟收斂，會難以獲取局部最優(yōu)解。所以，基于遺傳算法的冗余數(shù)據(jù)分配算法為了可以實時、自主的形成多個新個體，迅速提高冗余數(shù)據(jù)種群的多樣性，協(xié)助種群擺脫早熟，從而獲取預(yù)想的結(jié)果，使用大變異處理方法[15]，受限判別某一代群體內(nèi)個體的最大適應(yīng)度fmax和平均適應(yīng)度favg滿不滿足條件t*fmax

冗余數(shù)據(jù)的第gen代群體通過選擇、交叉、變異等處理之后，獲取(gen+1)代群體。

(8)判別滿不滿足停止準(zhǔn)則。如果目前此冗余數(shù)據(jù)種群進(jìn)化代數(shù)gen小于停止進(jìn)化代數(shù)ng，那么回到第(5)步重新進(jìn)化。否則，如果gen不小于ng，那么則會獲取冗余數(shù)據(jù)的最終群體，跳入第(9)步。

(9)解碼冗余數(shù)據(jù)的最終群體適應(yīng)度最高的個體，獲取冗余數(shù)據(jù)片段Fj的最優(yōu)分配策略。

2 實驗分析

為了驗證本文算法的有效性，本文使用配置了酷睿Intel i5雙核@2.48 GHz，RAM為8 GB的個人電腦，使用仿真軟件matlab7.1建立實驗環(huán)境，進(jìn)行仿真實驗，設(shè)定云計算大數(shù)據(jù)分布式存儲數(shù)據(jù)庫內(nèi)全部數(shù)據(jù)的數(shù)量為1000000個，冗余數(shù)據(jù)的種類數(shù)量是200種。

若冗余數(shù)據(jù)種類很少的狀況內(nèi)，使用不一樣的算法實行10次冗余數(shù)據(jù)分類，把實驗過程內(nèi)的數(shù)據(jù)實行歸納研究，獲取到的結(jié)果用表1來描述：

通過表1可以看出，當(dāng)云計算下大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)的種類少時，支持向量機(jī)算法、小波變換算法以及數(shù)據(jù)增益算法對冗余數(shù)據(jù)的分類準(zhǔn)確度都沒有超過95%，甚至于出現(xiàn)低于90%的情況出現(xiàn)，而本文算法的分類準(zhǔn)確度一致保持在95%之上，本文算法在冗余數(shù)據(jù)種類少的時候分類準(zhǔn)確度高。

表1 冗余數(shù)據(jù)種類較少時分類對比數(shù)據(jù)表

當(dāng)冗余數(shù)據(jù)種類較多的狀況中，使用不同算法實行10次冗余數(shù)據(jù)分類，對在實驗過程內(nèi)的數(shù)據(jù)實行歸納研究，獲取的對比結(jié)果用表2來描述：

表2 冗余數(shù)據(jù)種類較多時分類對比數(shù)據(jù)表

由表2可知，當(dāng)云計算下大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)種類多時，支持向量機(jī)算法、小波變換算法以及數(shù)據(jù)增益算法對冗余數(shù)據(jù)的分類準(zhǔn)確度都沒有超過90%，且隨著實驗次數(shù)的增多，準(zhǔn)確度逐漸降低，數(shù)據(jù)增益算法分類的準(zhǔn)確度最低下跌至41%，而本文算法的準(zhǔn)確率沒有下降至93%，本文算法的分類準(zhǔn)確度高。

本文算法可以避免由于數(shù)據(jù)庫內(nèi)的冗余數(shù)據(jù)間關(guān)聯(lián)性差的情況出現(xiàn)。增強(qiáng)了分布式存儲中冗余數(shù)據(jù)分類的效率，為接下來的冗余數(shù)據(jù)分配打下了良好的基礎(chǔ)。

為了可以提高對冗余數(shù)據(jù)分配的效率，分配的工作站點S的數(shù)量設(shè)定為小于5，屆時冗余數(shù)據(jù)分配的解空間縮小，可以直接求取最優(yōu)解。綜合云計算下大數(shù)據(jù)分布存儲冗余數(shù)據(jù)分配流程圖，假定數(shù)據(jù)片段F為6個、檢索事務(wù)Q為7項、革新事務(wù)U和工作站點S10個，并且當(dāng)中設(shè)定六個城市分別為S1～3(一城)、S4(二城)、S5(三城)、S6(四城)、S7～8(五城)、S9～10(六城)。設(shè)此六城處于不一樣的城市的網(wǎng)絡(luò)單元格中。單位數(shù)據(jù)在相同網(wǎng)絡(luò)單元局域網(wǎng)內(nèi)傳遞的延遲和干擾較小，同時假定本地訪問的通信代價系數(shù)是0.1。根據(jù)以上設(shè)置模擬實驗環(huán)境Ⅰ。

在實驗時，本文算法的每項參數(shù)的值設(shè)成：群體大小np為11；停止進(jìn)化代數(shù)ng是50；群體初始化時待選個體數(shù)值np0是50；交叉概率pc為0.9；大變異處理時，一般變異概率pm是0.05，大變異概率pmax為0.4，設(shè)定密集因子為t∈[0.8,0.9]，同時伴隨進(jìn)化代數(shù)gen的增多其會減少，它的取值方法見公式(10)：

本文實驗環(huán)境不僅設(shè)置實驗環(huán)境Ⅰ，同時還設(shè)定了站點數(shù)量是15與20的兩種實驗環(huán)境Ⅱ與Ⅲ進(jìn)行對比實驗。實驗對三種不同實驗環(huán)境下支持向量機(jī)算法、小波變換算法、數(shù)據(jù)增益算法與本文算法，進(jìn)行云計算大數(shù)據(jù)分布式存儲冗余數(shù)據(jù)分配時的總代價運算，計算結(jié)果也就是最終使用的分配策略相應(yīng)的通信總代價的數(shù)目級是105，數(shù)值最小的為最佳分配方案，實驗結(jié)果用表3來描述：

表3 三種實驗環(huán)境下不同分配算法的總代價計算結(jié)果(105)

通過表3可知，三種分配方案的對比下，本文算法的通信總代價最小，可以得出本文算法進(jìn)行云計算大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)分配的成本最低。

為了進(jìn)一步驗證本文算法的優(yōu)越性，在相同實驗環(huán)境中分別采用不同算法，對云計算下大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)進(jìn)行分配，對四種算法的分配用時以及準(zhǔn)確率進(jìn)行對比，詳情見圖2與圖3：

圖2 相同實驗環(huán)境中不用算法對冗余數(shù)據(jù)分配的用時對比圖

圖3 相同實驗環(huán)境中相同實驗次數(shù)不同算法的冗余數(shù)據(jù)分配準(zhǔn)確率對比圖

通過圖2可以看出，在云計算下大數(shù)據(jù)分布式存儲的相同實驗環(huán)境中支持向量機(jī)算法對冗余數(shù)據(jù)的分配耗時最多接近于70 s，效率低，小波變換算法與數(shù)據(jù)增益算法的耗時相近，都接近于50 s，而本文算法耗時最低，即使經(jīng)過10次實驗，本文算法在對云計算下大數(shù)據(jù)分布式式存儲中冗余數(shù)據(jù)分配時耗費的時間仍保持在10 s。說明本文算法在進(jìn)行云計算下大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)分配時用時短，效率高。

通過圖3可以看出在云計算下大數(shù)據(jù)分布式存儲的相同實驗環(huán)境的前提下，支持向量機(jī)算法對冗余數(shù)據(jù)的分配準(zhǔn)確率上下波動不大但是只保持在85%以內(nèi)，分配準(zhǔn)確率相對欠缺；小波變換算法對冗余數(shù)據(jù)的分配準(zhǔn)確率隨著實驗次數(shù)的增多，準(zhǔn)確率卻有輕微的下降，只保持在85%上下；數(shù)據(jù)增益算法對冗余數(shù)據(jù)的分配準(zhǔn)確率隨著次數(shù)的增多明顯看出在下降，準(zhǔn)確率最低；本文算法對冗余數(shù)據(jù)的分配隨著實驗次數(shù)的增多基本保持平穩(wěn)，始終接近于100%，說明本文算法在分配云計算下大數(shù)據(jù)分布式存儲中的冗余數(shù)據(jù)時的準(zhǔn)確率高。

3 結(jié) 語

本文提出云計算下大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)分配算法，對冗余基本數(shù)據(jù)使用一對一的分類方式變換成二分類數(shù)據(jù)，采用最優(yōu)分類平面對變換后冗余基本數(shù)據(jù)進(jìn)行分類獲取冗余數(shù)據(jù)片段，通過基于遺傳算法的冗余數(shù)據(jù)分配算法，獲取冗余數(shù)據(jù)片段的最優(yōu)分配策略，實現(xiàn)對云計算大數(shù)據(jù)分布式存儲中冗余數(shù)據(jù)的最優(yōu)分配。