基于相似度代價計算的內存數據庫集群數據劃分

謝玉鋒+鄭祿

摘要：針對內存數據庫集群的數據劃分，提出了基于相似度計算的內存數據庫數據劃分算法。該算法首先根據數據相關性對數據作初步簡單劃分，然后再基于事務相似度計算，得到最佳事務相似性判斷標準，對事務進行相關性合并，進而進一步劃分數據，得到合理優化的數據劃分結果。算法創新地提出根據Rough集原理計算事務相關性，去除了數據庫讀寫系數的影響，對內存數據庫集群的數據劃分具有一定指導意義。

關鍵詞：內存數據庫；相似度；代價計算；Rough集

中圖分類號：TP392

文獻標識碼：A

文章編號：16727800（2017）004018203

0引言

在數據庫集群系統中，數據劃分和數據分布是系統運行的基礎，做好劃分和數據分布可以有效提高系統運行效率。隨著內存數據庫以及內存數據庫集群的出現，針對內存數據庫集群的數據劃分算法也逐步出現，但都是基于傳統數據庫集群的解決方案，即僅考慮數據相關性。同時對相似性判斷標準都是基于經驗性判斷選擇50%為標準。本文提出基于相似度代價計算的內存數據庫集群數據劃分策略，在數據相關性基礎上提出事務相關性規約，并將相似性判斷條件擴大到40%～60%范圍內，以更準確、精細地進行數據劃分。

1數據劃分基本概念

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

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

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

根據Rough集理論，可以將事務訪問數據矩陣對應到信息系統中。假設分配到內存數據庫集群的數據集合R={r1，r2，r3...，r8}，事務集合T={t1，t2，t3，t4}，構造事務訪問數據矩陣，事務訪問了元數據記為1，未訪問記為0，假設訪問情況如表1所示。

根據數據劃分基本原理，即數據之間的相關性，初步對數據進行劃分，可得到元數據r1、r4相關性比較強，可以作為一個劃分，r2、r8作為一個劃分，其余作為獨立劃分，得到劃分結果如表2所示。

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

3代價計算劃分算法

上文提到的代價計算，在數據進行第二次劃分時，假設一個集群中有n個數據劃分，數據庫總訪問值記為D，單位為千次/s，第i個數據劃分在時間t內的數據訪問值為Di。Di來自兩方面，數據庫的讀和寫，分別記為Dri和Dwi。Dri和Dwi是兩個單位時間內的累計值，設Dri的變化函數為ri（t），Dwi的變化函數記為wi（t）。可以得到：

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

4實驗結果分析

實驗在30臺虛擬機上模擬內存數據庫集群，模擬數據中有200個事務和1 000個獨立元數據。經過第一步算法劃分之后合并為800個數據源，在進行代價計算時，得到訪問代價跟事務相似性關系如圖1所示。 由圖1結果可以得到，當事務相似度標準不小于0.52時，較為合理，在該標準下合并事務，事務合并為132個，再次對數據進行關聯性劃分，得到640個數據劃分。通過該算法可以合理劃分數據，有效降低集群訪問代價。

5結語

本文通過對傳統數據庫集群數據劃分算法進行分析，基于Rough集的新應用[6]，提出了針對內存數據庫集群的數據劃分算法。該算法有兩次數據劃分過程，第一次是普通的根據數據相關性進行數據劃分，第二次首先對訪問數據的事務進行相關性劃分。傳統劃分是直接以同時訪問數據超過50%為標準，本文創新地提出針對內存數據庫的訪問代價計算方法，對事務進行規約，同時針對內存數據庫的特點，忽略磁盤I/O代價。該算法能夠合理地劃分數據，有效降低集群訪問代價。 不過本文所提出的代價計算40%～60%也是一個經驗值，沒有計算和論證在此范圍外的情況。此外數據庫訪問代價值D是一個整體值，可能會出現單個節點的Di很高，而整體D值較低的情況，使單個節點可能超出了負載能力[7]，導致整個集群效率下降。以上兩個問題將作為以后研究的重點。

參考文獻：

[1]劉清，孫輝，王洪發.粒計算研究現狀及基于Rough邏輯語義的粒計算研究[J].計算機學報，2008（4）：543555.

[2]于磊，羅謙，張林林.基于粒計算的數據分片算法的問題發現[J].計算機技術與發展，2011（6）：3235.

[3]吳潤秀，吳水秀，劉清.基于粒計算的數據分片算法[J].計算機應用，2007（6）：13881391.

[4]楊晶，劉天時，馬剛.分布式數據庫數據分片與分配[J].現代電子技術，2006（18）：119121，125.

[5]楊小虎，王新宇，毛明.基于數據劃分的分布式模型及其負載均衡算法[J].浙江大學學報：工學版，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，FREEMAN L，et al.Astatic workload balance scheduling algorithm[C].Proceedings of ICPP，2002：235239.

（責任編輯：黃?。?