基于網(wǎng)絡(luò)聚類與自適應(yīng)概率的數(shù)據(jù)庫緩沖區(qū)替換*

賀紅艷，李光明，張慧萍

(湖北工業(yè)大學(xué) 工程技術(shù)學(xué)院，武漢 430068)

基于網(wǎng)絡(luò)聚類與自適應(yīng)概率的數(shù)據(jù)庫緩沖區(qū)替換*

賀紅艷，李光明，張慧萍

(湖北工業(yè)大學(xué) 工程技術(shù)學(xué)院，武漢 430068)

針對傳統(tǒng)替換方法存在替換不準(zhǔn)確、效率低的問題，提出模糊kohonen網(wǎng)絡(luò)聚類算法與自適應(yīng)概率相結(jié)合的大型數(shù)據(jù)庫緩沖區(qū)替換方法.采用Broder理論并基于Jaccard相似性度量對緩沖區(qū)重復(fù)數(shù)據(jù)進行消除，建立緩沖區(qū)數(shù)據(jù)檢測模型，并采用模糊kohonen網(wǎng)絡(luò)聚類算法對緩沖區(qū)數(shù)據(jù)進行聚類處理.采用復(fù)小波法提取緩沖區(qū)的特征，引入自適應(yīng)概率對大型數(shù)據(jù)庫緩沖區(qū)進行替換.結(jié)果表明，改進的緩沖區(qū)替換方法可有效的實現(xiàn)對大型數(shù)據(jù)庫緩沖區(qū)的替換，提高替換效率，增加大型數(shù)據(jù)庫存儲的整體性能.

大型數(shù)據(jù)庫；緩沖區(qū)；替換方法；改進；特征；網(wǎng)絡(luò)聚類；自適應(yīng)概率；數(shù)據(jù)存儲

隨著科學(xué)技術(shù)飛速發(fā)展，計算機得到了廣泛使用，其中計算機數(shù)據(jù)存儲問題成為計算機正常運行的關(guān)鍵，數(shù)據(jù)庫技術(shù)應(yīng)運而生[1-2].由于存儲數(shù)據(jù)規(guī)模的不斷增加，以往的小型數(shù)據(jù)庫以無法滿足數(shù)據(jù)存儲的需求，從而出現(xiàn)了大型數(shù)據(jù)庫[3-4].緩沖區(qū)是計算機最重要的組成部分之一，廣泛應(yīng)用于數(shù)據(jù)庫中，對緩沖區(qū)進行替換，可優(yōu)化I/O序列，減少用戶訪問次數(shù)，優(yōu)化存儲性能，提高使用效率[5-6].如何對大型數(shù)據(jù)庫緩沖區(qū)進行替換成為了該領(lǐng)域研究的熱點，受到了廣大學(xué)者的關(guān)注.

文獻[7]提出基于網(wǎng)絡(luò)優(yōu)化的大型數(shù)據(jù)庫緩沖區(qū)替換方法，該方法通過一種基于網(wǎng)格邊長伸展的參數(shù)化方法對大型數(shù)據(jù)庫緩沖區(qū)進行優(yōu)化，求得目標(biāo)替換數(shù)據(jù)，實現(xiàn)緩沖區(qū)的快速替換；文獻[8]提出基于OpenGL Performer的大型數(shù)據(jù)庫緩沖區(qū)替換方法，在3DMax中提取出特定緩沖區(qū)的替換特征，并使用遞歸遍歷方法減少緩沖區(qū)存在的缺陷，實現(xiàn)緩沖區(qū)替換，但該方法存在一定的替換誤差；文獻[9]提出基于支持補償?shù)拇笮蛿?shù)據(jù)緩沖區(qū)替換方法，該方法充分考慮在大型數(shù)據(jù)庫緩沖區(qū)進行替換時對緩沖區(qū)數(shù)據(jù)造成的影響，為其進行補充，提高替換效率，但是數(shù)據(jù)替換響應(yīng)較慢，不適合快速存取的情況.

針對上述問題，本文提出模糊kohonen網(wǎng)絡(luò)聚類算法與自適應(yīng)概率相結(jié)合的大型數(shù)據(jù)庫緩沖區(qū)替換方法.通過Broder理論并基于Jaccard相似性度量，對緩沖區(qū)重復(fù)數(shù)據(jù)進行消除，建立了緩沖區(qū)數(shù)據(jù)檢測模型，并以此為基礎(chǔ)，采用模糊kohonen網(wǎng)絡(luò)聚類算法對緩沖區(qū)數(shù)據(jù)進行聚類處理，引入自適應(yīng)概率實現(xiàn)對大型數(shù)據(jù)庫緩沖區(qū)的替換.根據(jù)實驗結(jié)果可知，改進的緩沖區(qū)替換方法可有效實現(xiàn)對大型數(shù)據(jù)庫緩沖區(qū)的替換，提高了替換效率.

1 重復(fù)數(shù)據(jù)消除及檢測模型的建立

1.1 重復(fù)數(shù)據(jù)消除

重復(fù)數(shù)據(jù)消除也叫容量優(yōu)化技術(shù)或者智能壓縮，是一種經(jīng)過自動搜索并檢測重復(fù)數(shù)據(jù)，只保留冗余數(shù)據(jù)唯一一個物理存儲的算法.重復(fù)數(shù)據(jù)消除使重復(fù)副本被指向單一存儲的指針?biāo)鎿Q，可達到消除冗余數(shù)據(jù)(即重復(fù)數(shù)據(jù))，降低數(shù)據(jù)中心存儲及傳輸壓力的目的.將損失的數(shù)據(jù)量定義為

loss=wOsize

(1)

式中：w為緩沖區(qū)數(shù)據(jù)的共享度；Osize為緩沖區(qū)數(shù)據(jù)的大小.

緩沖區(qū)數(shù)據(jù)的共享度w越高，重復(fù)數(shù)據(jù)消除操作的數(shù)據(jù)縮減比率越大，相應(yīng)的緩沖區(qū)數(shù)據(jù)因丟失引起的數(shù)據(jù)損失量也越大.由于重復(fù)數(shù)據(jù)消除時需要通過消除數(shù)據(jù)冗余來節(jié)省存儲空間，因此，為了提高數(shù)據(jù)可靠性，需要降低數(shù)據(jù)冗余度和數(shù)據(jù)可靠性.假設(shè)每一個緩沖區(qū)數(shù)據(jù)的副本數(shù)目k是一個關(guān)于緩沖區(qū)數(shù)據(jù)共享度w的函數(shù)，則其數(shù)據(jù)表達式為

k=min(max(2，a+blog2w)，kmaxloss)

(2)

式中：a和b為空間使用率及魯棒性，通常為常數(shù)；kmax為緩沖區(qū)最大數(shù)據(jù)副本數(shù)閾值.由式(2)可知，每個緩沖區(qū)數(shù)據(jù)至少維持兩個副本，最多不超過kmax個副本，緩沖區(qū)數(shù)據(jù)的副本數(shù)和共享度的對數(shù)成線性關(guān)系.假設(shè)有一個安全性函數(shù)H產(chǎn)生的緩沖區(qū)數(shù)據(jù)長度為β，存儲空間為Θ，則Θ共包含2β個不同的數(shù)據(jù)特征.Ω為不同緩沖數(shù)據(jù)塊組成的集合，基于哈希算法得到指紋并進行匹配，則緩沖區(qū)數(shù)據(jù)分配函數(shù)表示為

(3)

當(dāng)M?Ω，為緩沖區(qū)數(shù)據(jù)塊的集合時，則緩沖區(qū)數(shù)據(jù)發(fā)生的索引表達式為

L=Pr(h(A)=h(B)，?A，B∈M)

(4)

式中，h(A)和h(B)分別為數(shù)據(jù)A和B在緩沖區(qū)出現(xiàn)的次數(shù).假設(shè)緩沖區(qū)中有q個不一樣的數(shù)據(jù)塊(D1，D2，…，Dq)是依據(jù)順數(shù)串存儲到緩沖區(qū)的，并假設(shè)副本分布區(qū)數(shù)據(jù)ej(j=1，2，…，q)與前面存儲的數(shù)據(jù)發(fā)生碰撞時，寫入新的數(shù)據(jù)，并重新再磁盤上進行分布，則分布表達式為

(5)

式中，s為緩沖區(qū)分布系數(shù).本文使用數(shù)據(jù)內(nèi)容而非數(shù)據(jù)位置來消除緩沖區(qū)重復(fù)數(shù)據(jù)，假設(shè)有兩個數(shù)據(jù)集合S1、S2，則進行重復(fù)數(shù)據(jù)消除后，緩沖區(qū)數(shù)據(jù)分配函數(shù)為

Pr(S)=[minh(S1)+minh(S2)]=

(6)

由式(6)可知，若S1和S2具有很高的相似度，則h(S1)，h(S2)里最小元素相同的概率也很高，即對緩沖區(qū)重復(fù)數(shù)據(jù)進行消除的效果越好.重復(fù)數(shù)據(jù)消除策略結(jié)構(gòu)圖如圖1所示.

圖1 重復(fù)數(shù)據(jù)消除策略結(jié)構(gòu)Fig.1 Structure of strategy for eliminating repeated data

1.2 數(shù)據(jù)檢測模型的建立

在對緩沖區(qū)重復(fù)數(shù)據(jù)消除的基礎(chǔ)上，需對緩沖區(qū)數(shù)據(jù)進行檢測，建立緩沖區(qū)數(shù)據(jù)檢測模型，詳細(xì)的建模步驟如下：

1) 選取一個正確的緩沖區(qū)數(shù)據(jù)樣本為Y={Y1，Y2，…，YN}，其中，緩沖區(qū)數(shù)據(jù)樣本中含有樣本數(shù)為N，每個樣本向量是一個p維矢量，設(shè)定緩沖區(qū)數(shù)據(jù)樣本初始值c(1≤c≤N)和數(shù)據(jù)樣本特征距離(即歐式距離).

2) 在設(shè)定環(huán)境后，初始化檢測緩沖區(qū)數(shù)據(jù)中心向量Z=(Z1，Z2，…，Zc)，在中心向量集合中每個向量同樣是p維矢量.另外初始化檢測次數(shù)T=0，最大檢測次數(shù)為Tmax，令隸屬度初始加權(quán)冪指數(shù)為K0(K0>1)，設(shè)定迭代的終止誤差為ε>0.

3) 計算輸入時各個緩沖區(qū)數(shù)據(jù)樣本屬于第i(2≤i≤c)類的隸屬度，其計算式為

(7)

式中：τ為均值常數(shù)；Yk為緩沖區(qū)數(shù)據(jù)樣本總體特征；Zi，Zj分別為緩沖區(qū)數(shù)據(jù)樣本i和j的特征.

隸屬度rik計算完成后，利用此隸屬度計算權(quán)值迭代更新檢測率，即

(8)

λ=K0-T(K0-1)/Tmax

(9)

當(dāng)T=Tmax時，λ=1.

4) 調(diào)整緩沖區(qū)數(shù)據(jù)樣本中心向量，依據(jù)前一次的特征量和檢測率對緩沖區(qū)數(shù)據(jù)進行檢測，檢測式為

(10)

通過上述檢測可以看出，檢測結(jié)果主要依賴輸入向量和不斷檢測更新的檢測率.假如輸入模式里有一個樣本屬于某一類隸屬度的可能性比較大，則這類輸入模式向量對緩沖區(qū)數(shù)據(jù)樣本中心向量檢測的影響就更大，符合實際情況.

5) 在對緩沖區(qū)數(shù)據(jù)進行檢測后，采用加權(quán)平均的方法建立緩沖區(qū)數(shù)據(jù)檢測模型，模型計算式為

(11)

式中：cur_t為檢測緩沖區(qū)數(shù)據(jù)所需時間；rec_t為申請檢測所需時間；exp_t為預(yù)計執(zhí)行該檢測任務(wù)所持續(xù)的時間；ω，γ均為可調(diào)常數(shù).中心向量則需要滿足

(12)

當(dāng)檢測次數(shù)大于初始設(shè)定的最大檢測次數(shù)Tmax，則會導(dǎo)致檢測終止.

2 數(shù)據(jù)庫緩沖區(qū)替換方法

在進行大型數(shù)據(jù)庫緩沖區(qū)數(shù)據(jù)檢測的基礎(chǔ)上，采用模糊kohonen網(wǎng)絡(luò)聚類算法對緩沖區(qū)數(shù)據(jù)進行聚類處理，再引入自適應(yīng)概率法對緩沖區(qū)進行替換.假設(shè)X=(x1，x2，…，xn)為包含n個數(shù)據(jù)對象的緩沖區(qū)數(shù)據(jù)集，每個緩沖區(qū)數(shù)據(jù)對象具有m個屬性，用A1，A2，…，Am表示，數(shù)據(jù)對象xi可表示成[xi1，xi2，…，xim].通過最小化特定目標(biāo)成本函數(shù)將緩沖區(qū)數(shù)據(jù)集X進行劃分，劃分式為

(13)

式中：uil為劃分緩沖區(qū)數(shù)據(jù)矩陣Un×k的元素，表示緩沖區(qū)數(shù)據(jù)對象i是否屬于第l個簇；Qlj為屬性j在簇l里的中心數(shù)據(jù)；d(·)為計算緩沖區(qū)數(shù)據(jù)對象間或數(shù)據(jù)對象和簇中心間的距離函數(shù)；sj為屬性j的權(quán)重值，權(quán)重值滿足

(14)

式中，Dj為屬性j的簇內(nèi)距離和.由式(14)可知，對簇內(nèi)距離之和小的緩沖區(qū)數(shù)據(jù)屬性，需要分配一個大的屬性權(quán)重值；反之，則需分配一個小的屬性權(quán)重值.特定的目標(biāo)函數(shù)表達式為

(15)

假如緩沖區(qū)數(shù)據(jù)對象i屬于簇l，則uil為1，反之為0.采用模糊kohonen網(wǎng)絡(luò)聚類算法對緩沖區(qū)數(shù)據(jù)進行聚類，計算式表示為

(16)

(17)

式中，G(n)為復(fù)小波法提取的緩沖區(qū)特征.

綜上所述，采用模糊kohonen網(wǎng)絡(luò)聚類算法對緩沖區(qū)數(shù)據(jù)進行聚類處理，利用復(fù)小波法提取緩沖區(qū)的特征，并以此為基礎(chǔ)引入自適應(yīng)概率，可實現(xiàn)對大型數(shù)據(jù)庫緩沖區(qū)數(shù)據(jù)的高效替換.

3 實驗結(jié)果分析

為了驗證改進的大型數(shù)據(jù)庫緩沖區(qū)替換方法的有效性及可行性，采用實驗進行分析.實驗的硬件環(huán)境為Intel(R)Core(TM)i6-10GHzCPU和4GBitDDR2內(nèi)存，操作系統(tǒng)為Windows7，并在Flash-DBSim平臺上進行操作.采用的參數(shù)配置模擬器為一個128Mbit的NAND固態(tài)盤，其詳細(xì)參數(shù)如表1所示.

表1 NAND固態(tài)盤特性參數(shù)Tab.1 Characteristic parameters for NADA solid state disk

在緩沖區(qū)容量一定的情況下，將改進方法與基于網(wǎng)絡(luò)優(yōu)化的大型數(shù)據(jù)庫緩沖區(qū)替換方法、基于支持補償?shù)拇笮蛿?shù)據(jù)緩沖區(qū)替換方法進行命中率方面對比實驗分析.參照文獻[9]中命中率的計算方法得到不同算法替換大型數(shù)據(jù)緩沖區(qū)的命中率，結(jié)果如圖2所示.

圖2 不同算法的命中率比較Fig.2 Comparison in hit rate between different algorithms

由圖2可知，采用基于網(wǎng)絡(luò)優(yōu)化方法時，其命中率會隨著緩沖容量的增加而增加，但其命中率相對較低；采用基于支持補償方法時，其隨著緩沖區(qū)容量的增加，命中率會相應(yīng)出現(xiàn)波動，穩(wěn)定性較差；采用改進的替換方法時，其命中率隨著緩沖區(qū)容量的增加而增加，穩(wěn)定性較好，而且其命中率相比其他兩種算法均有所提高.

為了進一步驗證改進方法的有效性，在緩沖區(qū)容量一定的情況下，將改進方法與基于網(wǎng)絡(luò)優(yōu)化的大型數(shù)據(jù)庫緩沖區(qū)替換方法、基于支持補償?shù)拇笮蛿?shù)據(jù)緩沖區(qū)替換方法進行運行時間方面的對比實驗，結(jié)果如圖3所示.

圖3 不同算法的運行時間對比Fig.3 Comparison in running time between different algorithms

由圖3可知，3種方法的運行時間均隨緩沖區(qū)容量的增加而減少，但采用改進的替換方法時，其平均運行時間約為2 s，且到50 Mbit后算法的運行時間趨于穩(wěn)定，是3種算法中運行時間最少的、數(shù)據(jù)處理效率最好的.

4 結(jié) 論

針對傳統(tǒng)替換方法存在替換不準(zhǔn)確、效率低的問題，提出模糊kohonen網(wǎng)絡(luò)聚類算法與自適應(yīng)概率相結(jié)合的大型數(shù)據(jù)庫緩沖區(qū)替換方法.采用Broder理論并基于Jaccard相似性對緩沖區(qū)重復(fù)數(shù)據(jù)進行消除，建立緩沖區(qū)數(shù)據(jù)檢測模型，并以此為基礎(chǔ)，采用模糊kohonen網(wǎng)絡(luò)聚類算法對緩沖區(qū)數(shù)據(jù)進行聚類處理.采用復(fù)小波法提取緩沖區(qū)的特征引入自適應(yīng)概率，實現(xiàn)對大型數(shù)據(jù)庫緩沖區(qū)的替換.根據(jù)實驗結(jié)果可知，采用改進的緩沖區(qū)替換方法可有效實現(xiàn)對大型數(shù)據(jù)庫緩沖區(qū)的替換，提高替換效率，增加大型數(shù)據(jù)庫存儲的整體性能.

[1] Xiao J，Ehinger K A，Hays J.Exploring a large collection of scene categories [J].International Journal of Computer Vision，2016，119(1)：3-22.

[2] 敖建華.基于閃存的數(shù)據(jù)庫緩沖區(qū)替換算法優(yōu)化研究 [J].電腦知識與技術(shù)，2014(20)：4631-4633.

(AO Jian-hua.Research on optimization of database buffer replacement algorithm based on flash memory [J].Computer Knowledge and Technology，2014(20)：4631-4633.)

[3] Cao C，Weng Y，Zhou S，et al.A 3D facial expression database for visual computing [J].IEEE Transactions on Visualization & Computer Graphics，2014，20(3)：413-425.

[4] 徐旭，劉偉.線目標(biāo)緩沖區(qū)生成的矢柵混合算法研究 [J].計算機工程與應(yīng)用，2014，50(4)：152-156.

(XU Xu，LIU Wei.Research on vector-raster mixed algorithm of linear buffer generation [J].Computer Engineering and Applications，2014，50(4)：152-156.)

[5] 鹿婷婷，鹿璐.基于分區(qū)替換概率的閃存數(shù)據(jù)庫緩沖區(qū)自適應(yīng)替換算法 [J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2014(11)：152-155.

(LU Ting-ting，LU Lu.Based on adaptive probability of flash database partition to replace buffer replacement algorithm [J].Network Security Technology & Application，2014(11)：152-155.)

[6] 任艷.微信息大數(shù)據(jù)粗糙集的近似約簡 [J].沈陽工業(yè)大學(xué)學(xué)報，2016，38(3)：122-125.

(REN Yan.Approximate reduction of micro-message big data rough set [J].Journal of Shenyang University of Technology，2016，38(3)：122-125.)

[7] 孫新軒，呂蓬，李磊.利用最小二乘法檢測緩沖區(qū)海岸線變化研究 [J].信息工程大學(xué)學(xué)報，2014，15(1)：12-16.

(SUN Xin-xuan，Lü Peng，LI Lei.Research on detecting buffer shoreline using the least squares method [J].Journal of Information Engineering University，2014，15(1)：12-16.)

[8] 杜田田，李芳，武超然.求解有限緩沖區(qū)流水線調(diào)度問題的混合蝙蝠算法 [J].計算機應(yīng)用與軟件，2015(6)：232-235.

(DU Tian-tian，LI Fang，WU Chao-ran.Hybrid bat algorithm for solving permutation flow-shop scheduling problem with limited buffers [J].Computer Applications and Software，2015(6)：232-235.)

[9] 林子雨，賴明星，鄒權(quán)，等.基于替換概率的閃存數(shù)據(jù)庫緩沖區(qū)替換算法 [J].計算機學(xué)報，2013，36(8)：1568-1581.

(LIN Zi-yu，LAI Ming-xing，ZOU Quan，et al.Probability-based buffer replacement algorithm for flash-based databases [J].Chinese Journal of Computers，2013，36(8)：1568-1581.)

Databasebufferreplacementbasedonnetworkclusteringandadaptiveprobability

HE Hong-yan, LI Guang-ming, ZHANG Hui-ping

(Engineering and Technology College, Hubei University of Technology, Wuhan 430068, China)

Aiming at the inaccurate replacement and low efficiency existing in the traditional replacement method, a large database buffer replacement method in combination with both fuzzy kohonen network clustering algorithm and adaptive probability was proposed.Through adoptingBroder theory and based on Jaccard similarity measurement, the repeated data in the buffer were eliminated, and the buffer data detection model was established.In addition, the buffer data were clustered with the fuzzykohonen clustering algorithm.The buffer features were extracted with the complex wavelet method, and the adaptive probability was introduced to replace the large database buffer.The results show that the improved buffer replacement method can effectively realize the replacement of large database buffer, increase the replacement efficiency, and enhance the overall performance of large database storage.

large database; buffer; replacement method; improvement; feature; network clustering; adaptive probability; data storage

2016-08-14.

湖北省教育廳科研計劃資助項目(2014277)；湖北工業(yè)大學(xué)工程技術(shù)學(xué)院項目(X201328).

賀紅艷(1978-)，女，湖北武漢人，講師，碩士，主要從事計算機應(yīng)用技術(shù)等方面的研究.

* 本文已于2017-10-25 21∶12在中國知網(wǎng)優(yōu)先數(shù)字出版.網(wǎng)絡(luò)出版地址：http：//kns.cnki.net/kcms/detail/21.1189.T.20171025.2112.012.html

10.7688/j.issn.1000-1646.2018.01.12

TP 311

A

1000-1646(2018)01-0065-05

景 勇 英文審校：尹淑英)