基于密度劃分的云數(shù)據(jù)分塊存儲方法仿真

潘文標(biāo)，元文浩

(溫州醫(yī)科大學(xué)信息技術(shù)中心，浙江 溫州 325035)

1 引言

互聯(lián)網(wǎng)技術(shù)與移動互聯(lián)網(wǎng)業(yè)務(wù)迅速普及，使得在日常應(yīng)用過程中產(chǎn)生了大量數(shù)據(jù)[1]，給后續(xù)的數(shù)據(jù)存儲、分析等均帶來了極大的難度，因此，謝鵬等研究人員[2]在數(shù)據(jù)存儲的探究課題中，結(jié)合HBase分布式存儲系統(tǒng)，創(chuàng)建空間矢量數(shù)據(jù)存儲模型，期望打破存儲技術(shù)的探索瓶頸。

進(jìn)入云計(jì)算時代后，云存儲技術(shù)[3]迅猛發(fā)展，云端服務(wù)器應(yīng)運(yùn)而生，作為新型的存儲方式，該存儲形式在大數(shù)據(jù)時代得以廣泛應(yīng)用，不僅讓用戶體驗(yàn)到了極佳的數(shù)據(jù)存儲服務(wù)，也為大規(guī)模數(shù)據(jù)存儲減輕了不小的壓力。隨著云端服務(wù)器越來越普及，應(yīng)用頻率越來越高，其爆炸式的增長趨勢使云數(shù)據(jù)的存儲問題受到高度關(guān)注，相關(guān)存儲方法應(yīng)運(yùn)出現(xiàn)，比如，劉福鑫設(shè)計(jì)的Kubernetes云原生海量數(shù)據(jù)存儲系統(tǒng)[4]，取得了較好的研究成果。

我國云數(shù)據(jù)存儲技術(shù)的研究剛剛起步，仍存在很大的優(yōu)化空間。本文基于密度劃分算法，設(shè)計(jì)一種分塊存儲方法，緩解存儲壓力。根據(jù)細(xì)粒度云數(shù)據(jù)的密度不均勻?qū)傩?，設(shè)計(jì)出低敏感度的密度劃分算法，獲取高集中性的數(shù)據(jù)類別，去除無效的冗余數(shù)據(jù)，縮減存儲空間；根據(jù)密度分割點(diǎn)建立階躍函數(shù)，避免密度閾值過高導(dǎo)致聚類不精確；基于伽羅華域完成云數(shù)據(jù)分塊編碼與解碼的全部運(yùn)算，利用范德蒙矩陣編碼、解碼，簡化編解碼復(fù)雜性，降低運(yùn)算難度與復(fù)雜度，加快運(yùn)算速度。

2 基于密度劃分算法的細(xì)粒度云數(shù)據(jù)聚類

針對細(xì)粒度云數(shù)據(jù)，按照下列密度劃分算法流程，聚類所有云數(shù)據(jù)：

1)輸入細(xì)粒度云數(shù)據(jù)集合P，構(gòu)建距離矩陣D；

2)明確自然特征值λ，以距離矩陣DN*N為依據(jù)，以r為搜索范圍，遍歷各云數(shù)據(jù)的近鄰與逆近鄰[5]數(shù)據(jù)，待反向鄰域數(shù)據(jù)個數(shù)穩(wěn)定時停止，獲得的矩陣nb為全部云數(shù)據(jù)的逆近鄰數(shù)量，此時有r=λ；

3)利用云數(shù)據(jù)及其近鄰數(shù)據(jù)，建立局部鄰域集LN；

4)通過式(1)求解云數(shù)據(jù)p的局部密度

(1)

式中，Nμ(p)指代數(shù)據(jù)p的μ近鄰數(shù)據(jù)集；dist(p，x)指代云數(shù)據(jù)p及其第μ個近鄰數(shù)據(jù)x之間的歐幾里得距離[6]。其中，μ=max{nb}；

5)按局部密度值，降序排列云數(shù)據(jù)，密度值最大的云數(shù)據(jù)就是局部鄰域集LN的局部核，劃分剩下云數(shù)據(jù)至局部核的所屬類別中；

6)取得比平均密度低的最大二階導(dǎo)數(shù)，將該最大值對應(yīng)的云數(shù)據(jù)密度作為密度閾值ρt，去除每個類別內(nèi)比該閾值小的數(shù)據(jù)；

7)利用各云數(shù)據(jù)及其λ近鄰點(diǎn)，建立全局鄰域圖；

8)假設(shè)類別Ci與Cj間的跨類別邊緣數(shù)據(jù)是vi、vj，兩數(shù)據(jù)間的邊權(quán)重值為w(vi，vj)，(vi，vj)表示數(shù)據(jù)vi、vj的偏導(dǎo)數(shù)，CE(Ci，Cj)表示兩類別的聯(lián)合密度，則采用下列計(jì)算公式求解類別Ci、Cj之間的關(guān)聯(lián)度

(2)

若跨類別邊緣數(shù)據(jù)是vi、vj的歐幾里得距離是dist(vi，vj)，則云數(shù)據(jù)邊權(quán)重值w(vi，vj)的計(jì)算公式如下所示

(3)

通過下列公式計(jì)算類別Ci與Cj間的緊密度

(4)

求解類別間關(guān)聯(lián)度與緊密度的乘積，即得到類別Ci與Cj的相似度，數(shù)學(xué)表達(dá)式如下所示

sim(Ci，Cj)=connect(Ci，Cj)*close(Ci，Cj)2

(5)

9)根據(jù)距離閾值η，判定跨類別數(shù)據(jù)的同類性與異類性，獲取數(shù)量比例；

10)降序排列類別相似度，以類別相似度與跨類別數(shù)據(jù)的類別屬性為依據(jù)，聚類所有云數(shù)據(jù)。當(dāng)跨類別數(shù)據(jù)的同類數(shù)多于異類數(shù)時，符合聚類條件，將兩類別整合在一起[7]；獲取新的相似度與聚類條件，待不符合聚類條件時，終止聚類操作，將未完成聚類的類別云數(shù)據(jù)整合成一類[8]；

11)劃分密度閾值較低的云數(shù)據(jù)至其局部核的所屬類別。至此，實(shí)現(xiàn)所有云數(shù)據(jù)聚類。

密度劃分算法的兩個重要參數(shù)為聚合條件的判定矩陣ψ與距離閾值η[9，10]。假設(shè)集合P中含有M個云數(shù)據(jù)，其中，數(shù)據(jù)i及其第k個近鄰點(diǎn)的間距是dik，則距離閾值η的計(jì)算公式如下所示

(6)

若類別Ci、Cj的跨類別數(shù)據(jù)共有ni，j對，則將下列表達(dá)式界定為聚合條件的判定矩陣ψ

(7)

(8)

針對比平均密度小的密度曲線，取得離散的最大二階導(dǎo)數(shù)，獲得聚合條件判定矩陣ψ與距離閾值η的最優(yōu)值。

3 基于里所碼的細(xì)粒度云數(shù)據(jù)分塊存儲

將完成聚類的細(xì)粒度云數(shù)據(jù)劃分為規(guī)格相同的數(shù)據(jù)塊，任意類別中的數(shù)據(jù)塊集合為B={b0，b1，…，bm-1}，各數(shù)據(jù)塊經(jīng)里所碼分塊后，得到K個規(guī)格相同的云數(shù)據(jù)分塊集F={f0，f1，…，fK-1}，其中，m-1與K-1各指代里所碼分塊前后的云數(shù)據(jù)塊數(shù)量。為簡化編碼復(fù)雜性，利用范德蒙矩陣A編碼，獲得校驗(yàn)塊集G={g0，g1，…，gM-K-1}，該集合中含有M-K個校驗(yàn)塊。編碼處理通過下列矩陣方程實(shí)現(xiàn)

(9)

式中，范德蒙矩陣A的界定式如下所示

(10)

經(jīng)范德蒙矩陣編碼處理，儲存編碼后的細(xì)粒度云數(shù)據(jù)。為避免主節(jié)點(diǎn)產(chǎn)生大量冗余云數(shù)據(jù)，選取的節(jié)點(diǎn)只存儲一個云數(shù)據(jù)塊，根據(jù)兩者間的相關(guān)性，獲取分塊存儲的元數(shù)據(jù)。每完成一個節(jié)點(diǎn)的云數(shù)據(jù)塊存儲，元數(shù)據(jù)都將直接更新至各節(jié)點(diǎn)。綜上所述，設(shè)計(jì)出下列細(xì)粒度云數(shù)據(jù)分塊存儲算法流程：

1)假設(shè)待輸入的細(xì)粒度云數(shù)據(jù)是data，其文件名是src，通過用戶端把云數(shù)據(jù)data輸入流中；

2)數(shù)據(jù)分塊，得到B={b0，b1，…，bm-1}；

3)在主節(jié)點(diǎn)選取的節(jié)點(diǎn)上存儲云數(shù)據(jù)塊；

4)利用范德蒙矩陣進(jìn)行編碼，二次分塊細(xì)粒度云數(shù)據(jù)；

5)在所選節(jié)點(diǎn)上儲存編碼后的云數(shù)據(jù)；

6)基于各云數(shù)據(jù)塊，獲取新的元數(shù)據(jù)。迭代循環(huán)整個流程，直到?jīng)]有新的元數(shù)據(jù)生成，此時，即可實(shí)現(xiàn)所有云數(shù)據(jù)的分塊存儲。

迭代分塊存儲過程中，需要調(diào)度節(jié)點(diǎn)來執(zhí)行云數(shù)據(jù)塊的處理任務(wù)，這就涉及到一個重要的步驟，即細(xì)粒度云數(shù)據(jù)的解碼處理。

假設(shè)待處理云數(shù)據(jù)塊為bα，任務(wù)執(zhí)行的節(jié)點(diǎn)為nodeα，搜尋所有儲存數(shù)據(jù)塊bα的節(jié)點(diǎn)，形成列表listα，針對其前φ個有效節(jié)點(diǎn)，取得云數(shù)據(jù)塊及其元數(shù)據(jù)，將范德蒙矩陣A與有效節(jié)點(diǎn)上儲存的云數(shù)據(jù)塊集F″={f″0，f″1，…，f″K-1，f″K}相結(jié)合，得到矩陣L及其逆矩陣L-1，建立L-1與新分塊集F′={f′0，f′1，…，f′K-1，f′K}的乘積形式，即完成云數(shù)據(jù)塊解碼處理。該解碼處理通過下列矩陣方程實(shí)現(xiàn)

(11)

式中，逆矩陣L-1的界定公式如下所示

(12)

綜上所述，構(gòu)建出下列細(xì)粒度云數(shù)據(jù)塊的解碼操作流程：

1)假設(shè)云數(shù)據(jù)的路由信息與緩沖大小各是path與size；

2)創(chuàng)建系統(tǒng)文件，根據(jù)文件名搜索元數(shù)據(jù)；

3)基于存儲待處理云數(shù)據(jù)塊的節(jié)點(diǎn)列表，完成解碼處理；

4)更新云數(shù)據(jù)塊，利用用戶端取得經(jīng)過解碼處理的云數(shù)據(jù)塊；

5)迭代循環(huán)上列步驟，直到分塊存儲完所有云數(shù)據(jù)。

本文基于伽羅華域完成云數(shù)據(jù)分塊編碼與解碼的全部運(yùn)算，且在不改變范德蒙矩陣形式的前提下，執(zhí)行編碼與解碼處理，二者均能夠在一定程度上降低運(yùn)算難度與復(fù)雜度，加快運(yùn)算速度。

4 細(xì)粒度云數(shù)據(jù)分塊存儲仿真研究

為增加實(shí)驗(yàn)可靠性，設(shè)定仿真環(huán)節(jié)為三個階段：明確里所碼編碼比例的最優(yōu)參數(shù)；分析密度劃分算法的可用性；探究分塊存儲方法的完整性、壓縮性。

4.1 基于分塊存儲的里所碼編碼比例設(shè)置

令里所碼編碼比例按等差數(shù)列取值，分析不同編碼比例下分塊存儲細(xì)粒度云數(shù)據(jù)時的開銷與帶寬，根據(jù)實(shí)驗(yàn)結(jié)果，擇優(yōu)設(shè)置里所碼編碼比例參數(shù)。

圖1 編碼比例參數(shù)相關(guān)性

從不同編碼比例參數(shù)值下分塊存儲的開銷與帶寬情況可知(見圖1)，當(dāng)里所碼編碼比例參數(shù)取值為0.5時，存儲開銷最小，且隨著運(yùn)行時間的增加呈持續(xù)大幅下降趨勢；同時帶寬一直保持最高數(shù)值，且隨著運(yùn)行時間的增加呈平緩上升趨勢。因此，設(shè)定里所碼編碼比例參數(shù)為0.5，能夠以最佳狀態(tài)展開方法驗(yàn)證試驗(yàn)，減小該參數(shù)對存儲效果的影響。

4.2 密度劃分算法可用性分析

選取細(xì)粒度云數(shù)據(jù)量不同的三個集合，分別采用正相關(guān)的純度、互相關(guān)信息熵、F1綜合指標(biāo)，評估密度劃分算法的聚類效果。各評估指標(biāo)的取值范圍均為0到1，計(jì)算方式如下所示

(13)

(14)

(15)

其中，Cn為類別n的真實(shí)聚類；θ(Cn，Ci)指代聚類結(jié)果是Ci，但實(shí)際類別是Cn的幾率，θ(Cn)與θ(Ci)各指代真實(shí)聚類為Cn的幾率與聚類結(jié)果是Ci的幾率，MCn與MCi各指代兩類別數(shù)量；F1(Ci，Cn)指代兩類別的F1綜合指標(biāo)值，計(jì)算公式如下

(16)

根據(jù)圖2所示的各集合評價指標(biāo)結(jié)果可以看出，對于不同大小數(shù)據(jù)量的實(shí)驗(yàn)樣本，密度劃分算法始終具有較好的聚類效果，即便面對海量細(xì)粒度云數(shù)據(jù)，該算法通過深入探討判定矩陣與距離閾值兩個關(guān)鍵參數(shù)，憑借近鄰與逆近鄰數(shù)據(jù)構(gòu)成的局部鄰域集與全局鄰域圖優(yōu)勢，精準(zhǔn)完成聚類，具備良好的可用性，對分塊存儲的干擾幾乎可以忽略不計(jì)。

圖2 不同數(shù)據(jù)量的聚類效果示意圖

4.3 細(xì)粒度云數(shù)據(jù)分塊存儲效果分析

利用本文方法分塊存儲某細(xì)粒度云數(shù)據(jù)集，將得到的實(shí)驗(yàn)結(jié)果分別與HBase模型及Kubernetes系統(tǒng)的存儲效果作比較，驗(yàn)證本文方法的優(yōu)越性與實(shí)踐性。

4.3.1 分塊存儲完整性

以500GB的云數(shù)據(jù)量集為檢驗(yàn)對象，設(shè)定主節(jié)點(diǎn)所選節(jié)點(diǎn)的存儲量為50個數(shù)據(jù)塊，待完成所有云數(shù)據(jù)塊存儲后，根據(jù)各節(jié)點(diǎn)上存儲的數(shù)據(jù)塊數(shù)量，分析不同方法在存儲數(shù)據(jù)過程中發(fā)生的數(shù)據(jù)丟失情況。任意選取其中十個節(jié)點(diǎn)，其數(shù)據(jù)塊存儲結(jié)果如圖3所示。

圖3 數(shù)據(jù)塊存儲數(shù)量示意圖

由十個節(jié)點(diǎn)的數(shù)據(jù)塊存儲量可以看出，本文方法結(jié)合密度劃分算法與里所碼技術(shù)，大幅提升細(xì)粒度云數(shù)據(jù)塊的聚類與劃分精度，確保各云數(shù)據(jù)都得到分類處理，盡可能不遺漏數(shù)據(jù)塊，因此，僅有節(jié)點(diǎn)5、8各丟失一個數(shù)據(jù)塊，相較于文獻(xiàn)方法的多次、多塊丟失情況，具有更理想的存儲完整性。

4.3.2 分塊存儲壓縮性

就分塊存儲壓縮性能，利用輸入、輸出數(shù)據(jù)的大小比值(即壓縮因子指標(biāo))客觀評估，該指標(biāo)值與壓縮效果呈正相關(guān)性。三種存儲方法的壓縮因子指標(biāo)數(shù)值如表1所示。

表1 不同存儲方法的壓縮因子數(shù)值

根據(jù)表1中的壓縮因子參數(shù)值可以看出，本文方法的壓縮因子值幾乎是文獻(xiàn)方法的二倍，壓縮優(yōu)勢顯著，實(shí)現(xiàn)了分塊存儲目標(biāo)。這是因?yàn)樵摲椒ǜ鶕?jù)類別相似度，準(zhǔn)確聚類所有云數(shù)據(jù)，為數(shù)據(jù)分塊奠定基礎(chǔ)，利用多個適配度較高的節(jié)點(diǎn)，分塊存儲云數(shù)據(jù)，極大程度減緩存儲壓力，令壓縮性能得到更好發(fā)揮。

5 結(jié)論

大數(shù)據(jù)與云時代的來臨，在為用戶提供便利的同時，導(dǎo)致云數(shù)據(jù)規(guī)模暴增，這一發(fā)展趨勢對存儲技術(shù)提出了巨大挑戰(zhàn)，其中，以細(xì)粒度數(shù)據(jù)的存儲難度最大。為此，針對細(xì)粒度云數(shù)據(jù)，提出分塊存儲方法，通過實(shí)驗(yàn)證明，方法取得較好效果。所以，在接下來研究中，為拓展方法應(yīng)用領(lǐng)域，進(jìn)一步提升存儲效果，將以下幾點(diǎn)作為重點(diǎn)研究方向：數(shù)據(jù)類型多種多樣，應(yīng)就多元化的數(shù)據(jù)種類，不斷檢驗(yàn)本文方法的存儲效果；針對編碼語義的可擴(kuò)展性，驗(yàn)證復(fù)雜情況下能否實(shí)現(xiàn)數(shù)據(jù)的統(tǒng)一編碼；需利用經(jīng)典的加密算法，提升分析存儲安全性；改進(jìn)密度劃分算法的離線處理局限性，令其對實(shí)時的數(shù)據(jù)流也具備較好的處理能力；應(yīng)在真實(shí)場景中開展實(shí)驗(yàn)活動，令方法更契合實(shí)際應(yīng)用。