基于相似度代價(jià)計(jì)算的內(nèi)存數(shù)據(jù)庫集群數(shù)據(jù)劃分

謝玉鋒+鄭祿

摘要：針對(duì)內(nèi)存數(shù)據(jù)庫集群的數(shù)據(jù)劃分，提出了基于相似度計(jì)算的內(nèi)存數(shù)據(jù)庫數(shù)據(jù)劃分算法。該算法首先根據(jù)數(shù)據(jù)相關(guān)性對(duì)數(shù)據(jù)作初步簡單劃分，然后再基于事務(wù)相似度計(jì)算，得到最佳事務(wù)相似性判斷標(biāo)準(zhǔn)，對(duì)事務(wù)進(jìn)行相關(guān)性合并，進(jìn)而進(jìn)一步劃分?jǐn)?shù)據(jù)，得到合理優(yōu)化的數(shù)據(jù)劃分結(jié)果。算法創(chuàng)新地提出根據(jù)Rough集原理計(jì)算事務(wù)相關(guān)性，去除了數(shù)據(jù)庫讀寫系數(shù)的影響，對(duì)內(nèi)存數(shù)據(jù)庫集群的數(shù)據(jù)劃分具有一定指導(dǎo)意義。

關(guān)鍵詞：內(nèi)存數(shù)據(jù)庫；相似度；代價(jià)計(jì)算；Rough集

中圖分類號(hào)：TP392

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：16727800（2017）004018203

0引言

在數(shù)據(jù)庫集群系統(tǒng)中，數(shù)據(jù)劃分和數(shù)據(jù)分布是系統(tǒng)運(yùn)行的基礎(chǔ)，做好劃分和數(shù)據(jù)分布可以有效提高系統(tǒng)運(yùn)行效率。隨著內(nèi)存數(shù)據(jù)庫以及內(nèi)存數(shù)據(jù)庫集群的出現(xiàn)，針對(duì)內(nèi)存數(shù)據(jù)庫集群的數(shù)據(jù)劃分算法也逐步出現(xiàn)，但都是基于傳統(tǒng)數(shù)據(jù)庫集群的解決方案，即僅考慮數(shù)據(jù)相關(guān)性。同時(shí)對(duì)相似性判斷標(biāo)準(zhǔn)都是基于經(jīng)驗(yàn)性判斷選擇50%為標(biāo)準(zhǔn)。本文提出基于相似度代價(jià)計(jì)算的內(nèi)存數(shù)據(jù)庫集群數(shù)據(jù)劃分策略，在數(shù)據(jù)相關(guān)性基礎(chǔ)上提出事務(wù)相關(guān)性規(guī)約，并將相似性判斷條件擴(kuò)大到40%～60%范圍內(nèi)，以更準(zhǔn)確、精細(xì)地進(jìn)行數(shù)據(jù)劃分。

1數(shù)據(jù)劃分基本概念

數(shù)據(jù)劃分又稱為數(shù)據(jù)分片或者數(shù)據(jù)分割，是數(shù)據(jù)庫集群的特征之一，是將集群的數(shù)據(jù)全集劃分為獨(dú)立的數(shù)據(jù)片段。數(shù)據(jù)劃分必須遵守3個(gè)原則：完整性、不相交性和可恢復(fù)性。 數(shù)據(jù)分片方法有3類：水平分片、豎直分片和混合分片。具體分片策略主要有Range分片算法、Round-Robin分片算法、Hybrid-Range分片算法、表達(dá)式分片算法、時(shí)間分片算法、哈希分片算法等。 目前數(shù)據(jù)劃分算法主要是針對(duì)結(jié)構(gòu)化的關(guān)系型數(shù)據(jù)處理，而且處理過程中將磁盤讀取代價(jià)作為重要參考標(biāo)準(zhǔn)，處理結(jié)果比較固定。這樣的數(shù)據(jù)劃分策略對(duì)內(nèi)存數(shù)據(jù)庫集群已不再適用。

2基于Rough集理論的相似度矩陣

在Rough集的研究中[1]，事務(wù)被表示成統(tǒng)一的信息系統(tǒng)。假定數(shù)據(jù)庫全集R={ r1，r2，r3...，rn}，ri（1≤i≤n）是數(shù)據(jù)集中的一個(gè)元數(shù)據(jù)，事務(wù)集合T={t1，t2，t3…，tm}，tj（1≤j≤m）是事務(wù)集合中的一個(gè)事務(wù)，trij表示數(shù)據(jù)ri被事務(wù)tj訪問，由此可得到事務(wù)訪問數(shù)據(jù)矩陣RT。

根據(jù)Rough集理論，可以將事務(wù)訪問數(shù)據(jù)矩陣對(duì)應(yīng)到信息系統(tǒng)中。假設(shè)分配到內(nèi)存數(shù)據(jù)庫集群的數(shù)據(jù)集合R={r1，r2，r3...，r8}，事務(wù)集合T={t1，t2，t3，t4}，構(gòu)造事務(wù)訪問數(shù)據(jù)矩陣，事務(wù)訪問了元數(shù)據(jù)記為1，未訪問記為0，假設(shè)訪問情況如表1所示。

根據(jù)數(shù)據(jù)劃分基本原理，即數(shù)據(jù)之間的相關(guān)性，初步對(duì)數(shù)據(jù)進(jìn)行劃分，可得到元數(shù)據(jù)r1、r4相關(guān)性比較強(qiáng)，可以作為一個(gè)劃分，r2、r8作為一個(gè)劃分，其余作為獨(dú)立劃分，得到劃分結(jié)果如表2所示。

再根據(jù)事務(wù)之間的相關(guān)性，將事務(wù)進(jìn)行合并。之前的研究都是確定一個(gè)相似度標(biāo)準(zhǔn)，基于粒計(jì)算的數(shù)據(jù)分片算法[23]中標(biāo)準(zhǔn)一般為同時(shí)訪問相同元數(shù)據(jù)不小于50%。50%是一個(gè)經(jīng)驗(yàn)值，被普遍認(rèn)為是一個(gè)劃分值，在實(shí)際部署中，尤其是在內(nèi)存數(shù)據(jù)庫集群部署中，50%作為一個(gè)相似度劃分標(biāo)準(zhǔn)并不一定合理。由于內(nèi)存數(shù)據(jù)庫的讀取效率成幾何倍數(shù)提高，可以適當(dāng)增加數(shù)據(jù)劃分?jǐn)?shù)量，即提升相似度劃分標(biāo)準(zhǔn)。所以提出首先根據(jù)不同相似度標(biāo)準(zhǔn)所付出的代價(jià)作為劃分依據(jù)對(duì)事務(wù)進(jìn)行劃分，然后對(duì)數(shù)據(jù)進(jìn)行第二次劃分，以得到更精確的數(shù)據(jù)劃分結(jié)果。 假設(shè)通過代價(jià)計(jì)算，得到事務(wù)相似性劃分標(biāo)準(zhǔn)為不小于60%，此時(shí)t2和t3事務(wù)可以合并，合并之后結(jié)果如表3所示。 再根據(jù)數(shù)據(jù)相關(guān)性，對(duì)數(shù)據(jù)進(jìn)一步劃分，此時(shí)r2、r5和r8可以歸為同一個(gè)劃分，得到劃分結(jié)果如表4所示。 經(jīng)過劃分之后，得到劃分結(jié)果為R={（r1，r4），（r2，r5，r8），（r3），（r6），（r7）}。

3代價(jià)計(jì)算劃分算法

上文提到的代價(jià)計(jì)算，在數(shù)據(jù)進(jìn)行第二次劃分時(shí)，假設(shè)一個(gè)集群中有n個(gè)數(shù)據(jù)劃分，數(shù)據(jù)庫總訪問值記為D，單位為千次/s，第i個(gè)數(shù)據(jù)劃分在時(shí)間t內(nèi)的數(shù)據(jù)訪問值為Di。Di來自兩方面，數(shù)據(jù)庫的讀和寫，分別記為Dri和Dwi。Dri和Dwi是兩個(gè)單位時(shí)間內(nèi)的累計(jì)值，設(shè)Dri的變化函數(shù)為ri（t），Dwi的變化函數(shù)記為wi（t）?？梢缘玫剑?/p>

上述代價(jià)計(jì)算是基于內(nèi)存數(shù)據(jù)庫的數(shù)據(jù)庫讀寫代價(jià)，在之前的傳統(tǒng)數(shù)據(jù)劃分中，基于代價(jià)計(jì)算的D值都引入了讀寫系數(shù)Vrwc，即要考慮主存與磁盤之間的I/O代價(jià)[5]。但是因?yàn)閮?nèi)存數(shù)據(jù)庫在運(yùn)行過程中，數(shù)據(jù)都加載到了內(nèi)存，讀和寫操作損耗時(shí)間大大減少，因而數(shù)據(jù)庫的讀寫損耗可以忽略。 數(shù)據(jù)進(jìn)行初步劃分之后，D值計(jì)算依據(jù)是在不同事務(wù)相似度標(biāo)準(zhǔn)下的不同值，之前會(huì)簡單地將這一標(biāo)準(zhǔn)選擇為超過50%。但是通過研究，這一標(biāo)準(zhǔn)并不一定是最佳標(biāo)準(zhǔn)，所以本文將計(jì)算標(biāo)準(zhǔn)限定在40%～60%，分別計(jì)算不同標(biāo)準(zhǔn)下的D值。通過比較D值變化趨勢(shì)，得到最佳判定標(biāo)準(zhǔn)，并依據(jù)該標(biāo)準(zhǔn)對(duì)事物進(jìn)行合并，最后再將數(shù)據(jù)進(jìn)行相關(guān)性劃分，進(jìn)而得到最佳的數(shù)據(jù)劃分。具體步驟如下： 第一步：簡單數(shù)據(jù)關(guān)聯(lián)度劃分，以數(shù)據(jù)同時(shí)被相同一組事務(wù)訪問為依據(jù)，判斷數(shù)據(jù)是否相關(guān)，如果相關(guān)則刪除矩陣中被相同事務(wù)訪問的數(shù)據(jù)節(jié)點(diǎn)，算法描述如下：〖HT5"〗算法1 //輸入：事務(wù)訪問數(shù)據(jù)矩陣 //輸出：去除相同事務(wù)訪問的節(jié)點(diǎn)行的事務(wù)訪問數(shù)據(jù)矩陣 數(shù)組tri[n]臨時(shí)存放第i行事務(wù)訪問數(shù)據(jù)記錄 數(shù)組trj[n]臨時(shí)存放第j行事務(wù)訪問數(shù)據(jù)記錄 1：for（i=1；i≤m；i++） 2：for（j=i+1；j≤m；j++） 3：tri[i-1]=trin//依次掃描得到第i行事務(wù)訪問數(shù)據(jù)記錄 4：trj[j-1]=trjn//依次掃描得到第j行事務(wù)訪問數(shù)據(jù)記錄 5： if （tri[n]==trj[n]） then 6：delete trj[n]//合并關(guān)聯(lián)度較強(qiáng)的獨(dú)立元數(shù)據(jù) 7：end if 8：end for 9：end for〖HT〗由以上操作得到經(jīng)過初步數(shù)據(jù)關(guān)聯(lián)性劃分的事務(wù)訪問數(shù)據(jù)矩陣RT。 第二步：代價(jià)計(jì)算，事務(wù)相關(guān)性劃分基于第一步的數(shù)據(jù)訪問矩陣RT，根據(jù)事務(wù)同時(shí)訪問數(shù)據(jù)的相似程度，計(jì)算事務(wù)相關(guān)性，根據(jù)代價(jià)計(jì)算公式得到合理的相似值為C，常數(shù)A=0，B=0。算法描述如下：〖HT5"〗算法2 //輸入：事務(wù)訪問數(shù)據(jù)矩陣 //輸出：去除相同事務(wù)訪問的節(jié)點(diǎn)行的事務(wù)訪問數(shù)據(jù)矩陣 數(shù)組tri[n]臨時(shí)存放第i行事務(wù)訪問數(shù)據(jù)記錄 數(shù)組trj[n]臨時(shí)存放第j行事務(wù)訪問數(shù)據(jù)記錄 1：for（k=1；k≤n；k++）： 2：for（l=k+1；l≤n；l++） 3：trk[m]=trmk//臨時(shí)記錄第k列數(shù)據(jù)被事務(wù)tr訪問的m個(gè)值 4：trj[m]=trlk//記錄第l列數(shù)據(jù)被事務(wù)tr訪問的m個(gè)值 5：trk[a]∪trl[a]=1，A++；（a取值為0，1，2…m） 6：trk[a]∩trl[a]=1，B++；（a取值為0，1，2…m） 7：if（B/A≥C）then 8：trk[a]=trk[a]∪trl[a]； //對(duì)相似事務(wù)進(jìn)行合并 9：delete trl[m]； 7：end if 8：end for 9：end for〖HT〗上一步算法結(jié)束之后，根據(jù)第一步算法對(duì)矩陣再次進(jìn)行數(shù)據(jù)相關(guān)性劃分，算法結(jié)束。

4實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)在30臺(tái)虛擬機(jī)上模擬內(nèi)存數(shù)據(jù)庫集群，模擬數(shù)據(jù)中有200個(gè)事務(wù)和1 000個(gè)獨(dú)立元數(shù)據(jù)。經(jīng)過第一步算法劃分之后合并為800個(gè)數(shù)據(jù)源，在進(jìn)行代價(jià)計(jì)算時(shí)，得到訪問代價(jià)跟事務(wù)相似性關(guān)系如圖1所示。 由圖1結(jié)果可以得到，當(dāng)事務(wù)相似度標(biāo)準(zhǔn)不小于0.52時(shí)，較為合理，在該標(biāo)準(zhǔn)下合并事務(wù)，事務(wù)合并為132個(gè)，再次對(duì)數(shù)據(jù)進(jìn)行關(guān)聯(lián)性劃分，得到640個(gè)數(shù)據(jù)劃分。通過該算法可以合理劃分?jǐn)?shù)據(jù)，有效降低集群訪問代價(jià)。

5結(jié)語

本文通過對(duì)傳統(tǒng)數(shù)據(jù)庫集群數(shù)據(jù)劃分算法進(jìn)行分析，基于Rough集的新應(yīng)用[6]，提出了針對(duì)內(nèi)存數(shù)據(jù)庫集群的數(shù)據(jù)劃分算法。該算法有兩次數(shù)據(jù)劃分過程，第一次是普通的根據(jù)數(shù)據(jù)相關(guān)性進(jìn)行數(shù)據(jù)劃分，第二次首先對(duì)訪問數(shù)據(jù)的事務(wù)進(jìn)行相關(guān)性劃分。傳統(tǒng)劃分是直接以同時(shí)訪問數(shù)據(jù)超過50%為標(biāo)準(zhǔn)，本文創(chuàng)新地提出針對(duì)內(nèi)存數(shù)據(jù)庫的訪問代價(jià)計(jì)算方法，對(duì)事務(wù)進(jìn)行規(guī)約，同時(shí)針對(duì)內(nèi)存數(shù)據(jù)庫的特點(diǎn)，忽略磁盤I/O代價(jià)。該算法能夠合理地劃分?jǐn)?shù)據(jù)，有效降低集群訪問代價(jià)。 不過本文所提出的代價(jià)計(jì)算40%～60%也是一個(gè)經(jīng)驗(yàn)值，沒有計(jì)算和論證在此范圍外的情況。此外數(shù)據(jù)庫訪問代價(jià)值D是一個(gè)整體值，可能會(huì)出現(xiàn)單個(gè)節(jié)點(diǎn)的Di很高，而整體D值較低的情況，使單個(gè)節(jié)點(diǎn)可能超出了負(fù)載能力[7]，導(dǎo)致整個(gè)集群效率下降。以上兩個(gè)問題將作為以后研究的重點(diǎn)。

參考文獻(xiàn)：

[1]劉清，孫輝，王洪發(fā).粒計(jì)算研究現(xiàn)狀及基于Rough邏輯語義的粒計(jì)算研究[J].計(jì)算機(jī)學(xué)報(bào)，2008（4）：543555.

[2]于磊，羅謙，張林林.基于粒計(jì)算的數(shù)據(jù)分片算法的問題發(fā)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2011（6）：3235.

[3]吳潤秀，吳水秀，劉清.基于粒計(jì)算的數(shù)據(jù)分片算法[J].計(jì)算機(jī)應(yīng)用，2007（6）：13881391.

[4]楊晶，劉天時(shí)，馬剛.分布式數(shù)據(jù)庫數(shù)據(jù)分片與分配[J].現(xiàn)代電子技術(shù)，2006（18）：119121，125.

[5]楊小虎，王新宇，毛明.基于數(shù)據(jù)劃分的分布式模型及其負(fù)載均衡算法[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2008（4）：602607，681.

[6]LIN TY.Granular fuzzy sets：a view from rough set and probability theories[J].International Journal of Fuzzy Systems，2001（2）：373381.

[7]TABIRCA T，TABIRCA S，F(xiàn)REEMAN L，et al.Astatic workload balance scheduling algorithm[C].Proceedings of ICPP，2002：235239.

（責(zé)任編輯：黃健）