摘要：內(nèi)存數(shù)據(jù)庫在最近幾年迅速發(fā)展，并在應(yīng)用中得到越來越廣泛的實踐。分布式數(shù)據(jù)分布算法具有廣泛的研究和討論，本文參照啟發(fā)式添加和刪除副本的數(shù)據(jù)分布算法，結(jié)合分布式內(nèi)存數(shù)據(jù)庫的特點并限制副本數(shù)，設(shè)計了一個實用的分布式內(nèi)存數(shù)據(jù)庫的數(shù)據(jù)分布方案。

關(guān)鍵詞：內(nèi)存數(shù)據(jù)庫；分布式；數(shù)據(jù)分配；啟發(fā)式算法

中圖分類號：TP311.13 文獻標識碼：A 文章編號：1007-9599 （2012） 23-0000-02

隨著信息化進度的加速，越來越多的數(shù)據(jù)庫系統(tǒng)使用分布式架構(gòu)。一系列的商用和開源數(shù)據(jù)庫產(chǎn)品都支持分布式應(yīng)用。數(shù)據(jù)分布是分布式數(shù)據(jù)庫一個研究的重點方向，國內(nèi)外很多學(xué)者研究并提出了一系列的數(shù)據(jù)分布方法[1][2][3][4]。然而這些方法大都是基于傳統(tǒng)的磁盤數(shù)據(jù)庫，很少對分布式內(nèi)存數(shù)據(jù)庫的數(shù)據(jù)分布進行探討。內(nèi)存數(shù)據(jù)庫一個重要特點就是受物理內(nèi)存限制，本文分析分布式內(nèi)存數(shù)據(jù)庫的特點，考慮數(shù)據(jù)節(jié)點物理內(nèi)存的影響，對傳統(tǒng)的啟發(fā)式算法進行一定的限制和修改，設(shè)計了一個適合分布式內(nèi)存數(shù)據(jù)庫的數(shù)據(jù)分布策略。

1 內(nèi)存數(shù)據(jù)庫

數(shù)據(jù)庫經(jīng)過30多年的發(fā)展，在信息應(yīng)用中越來越廣泛。根據(jù)數(shù)據(jù)存儲的介質(zhì)不同，可以分為磁盤數(shù)據(jù)庫和內(nèi)存數(shù)據(jù)庫。磁盤數(shù)據(jù)將數(shù)據(jù)保存在硬盤中，數(shù)據(jù)操作需要進行磁盤掃描和數(shù)據(jù)加載，磁盤處理成為影響數(shù)據(jù)庫性能的瓶頸。內(nèi)存數(shù)據(jù)庫將數(shù)據(jù)放在內(nèi)存中，不需要進行磁盤操作，內(nèi)存操作速度遠遠快要磁盤操作。為了實現(xiàn)海量信息的快速響應(yīng)，大型分布式內(nèi)存數(shù)據(jù)庫系受到廣泛的探討和應(yīng)用。Key-value是一種快速的數(shù)據(jù)訪問方式，在應(yīng)用中也越來越多。關(guān)系型數(shù)據(jù)庫依然還是數(shù)據(jù)庫應(yīng)用的主導(dǎo)應(yīng)用，對于稍復(fù)雜的應(yīng)用，key-value是不能夠處理的或處理代價昂貴。本文針對傳統(tǒng)的關(guān)系型數(shù)據(jù)庫進行其分布式的內(nèi)存數(shù)據(jù)分布探討和設(shè)計。

2 分布式內(nèi)存數(shù)據(jù)庫數(shù)據(jù)分布的分析

數(shù)據(jù)冗余是分布式的特點，保證了數(shù)據(jù)的高可用性。冗余是高可用性的保證，同時也增加了數(shù)據(jù)維護的工作。在考慮分布式數(shù)據(jù)的分布時，大多采用代價最小算法實現(xiàn)。對于只有一個副本的數(shù)據(jù)分布計算相對簡單，但是當系統(tǒng)允許多個副本存在時，數(shù)據(jù)分布的計算是一個NP復(fù)雜度的問題。目前對于NP問題的求解多采用啟發(fā)式算法，當目標達到一定的誤差范圍即可。

使用啟發(fā)算法進行數(shù)據(jù)分布計算時，需要一系列的統(tǒng)計值作為參考依據(jù)，收集統(tǒng)計信息進行目標模型的建立和數(shù)據(jù)分布的計算。影響數(shù)據(jù)分布的因素很多，但是在眾多統(tǒng)計信息中，有些參考值是很難獲取并且對代價影響不大的，有的是至關(guān)重要的。選取恰當?shù)慕y(tǒng)計信息對算法的實現(xiàn)具有重要意義。本文主要關(guān)心數(shù)據(jù)在有限內(nèi)存中的分配，弱化難獲取的次重要的影響因素。在本文中關(guān)心的主要因素有：數(shù)據(jù)節(jié)點處理能力，數(shù)據(jù)節(jié)點允許使用最大內(nèi)存，數(shù)據(jù)庫分片大小，事務(wù)查詢更新次數(shù)比，節(jié)點間通信代價。

3 分布式內(nèi)存數(shù)據(jù)庫數(shù)據(jù)分布設(shè)計

應(yīng)用于數(shù)據(jù)分布的啟發(fā)式算法有啟發(fā)式添加副本算法和啟發(fā)式刪除副本算法，常根據(jù)具體應(yīng)用的數(shù)據(jù)特點進行選取。

啟發(fā)式添加副本算法適用查詢多于更新的應(yīng)用，其首先采用一定方法獲得一個無冗余的數(shù)據(jù)分布并計算其代價，然后計算在添加一個新副本時系統(tǒng)的最小代價，當其代價小于增加副本前的代價則添加該副本。啟發(fā)式刪除副本算法適用更新多于查詢的應(yīng)用，其初始分布時將所有數(shù)據(jù)分布到各個節(jié)點再進行調(diào)整，當刪除一個副本可能實現(xiàn)整體代價減少則進行副本刪除。啟發(fā)算法都需要經(jīng)過迭代去控制其運算，通常設(shè)定一個比較小的誤差值，在迭代得到的代價差小于誤差值時認為分布已經(jīng)達到一個滿意的結(jié)果并結(jié)束迭代。

完成數(shù)據(jù)分布需要進行數(shù)據(jù)分布初始化和調(diào)整。使用啟發(fā)式添加算法進行初始化分布時需要進行大量計算，本文重點放在分布式數(shù)據(jù)分布調(diào)整上，使用啟發(fā)式添加算法進行數(shù)據(jù)初始化分布。對于數(shù)據(jù)調(diào)整，在數(shù)據(jù)節(jié)點的查詢更新比大于1時，使用啟發(fā)式添加副本算法，查詢更新比小于1時，使用啟發(fā)式刪除副本方法。在數(shù)據(jù)調(diào)整時，先判斷是否達到副本設(shè)定的上限或下限，當副本已經(jīng)達到了其限定值，將不再進行調(diào)整，直接退出算法。當算法中需要添加副本的數(shù)據(jù)節(jié)點內(nèi)存不能再容納副本時，也結(jié)束本次調(diào)整計算。通過節(jié)點內(nèi)存容量的限制和數(shù)據(jù)副本的控制，加快了數(shù)據(jù)分布的調(diào)整，雖然不是最優(yōu)的分布方案，但提高了數(shù)據(jù)分布計算的效率。

本文將添加副本的上限設(shè)置為3，刪除副本的下限設(shè)置為2，因此在完成分布后的調(diào)整中最多只進行一個副本的添加和刪除，不需要進行迭代運算，節(jié)約了計算時間。通過設(shè)計一張維護數(shù)據(jù)片段的分布表去記錄片段已經(jīng)分布次數(shù)，在試探副本的添加和刪除時需要參照分片數(shù)據(jù)分配表。副本限制在2和3之間，系統(tǒng)運行一定時間，將趨于一個優(yōu)化的分布，并且副本的添加和刪除將相對較少，可快速的進行數(shù)據(jù)分布調(diào)整，具有一定的實用性。

假設(shè) 表示將添加的分片， 表示第 個數(shù)據(jù)節(jié)點當前容量， 表示第 個數(shù)據(jù)節(jié)點最大容量，由于內(nèi)存的限制，必須滿足下面公式。

（1）

假設(shè)所有的節(jié)點能夠容納3份完整的數(shù)據(jù)，數(shù)據(jù)分片為n個，節(jié)點個數(shù)為w個，調(diào)整后的數(shù)據(jù)分布算法如下。

（1）初始化數(shù)據(jù)分布完成無冗余的數(shù)據(jù)分布。

（2）取 分片，判斷節(jié)點 是否擁有和能夠容納 ，如果 不擁有并且能夠容納 ，計算添加 到 的代價，否則記代價為無窮大。

（3）按照步驟（2）的判斷條件，計算將 添加到 （2，…w）的代價，選取最小的代價并進行分配。

（4）取 （2，…n），按照步驟2，3進行計算，完成冗余度為2的分布。

（5）再運行步驟2，3，4完成3個冗余度分布。

（6）判斷應(yīng)用的查詢更新比，當查詢更新比小于1時，試著刪除 （1，…w）上的 （1，..n），判斷新的代價，若代價小于刪除前則進行相應(yīng)數(shù)據(jù)分片的刪除。當查詢更新比大于1時，試著計算在 （1，…w）上添加 （1，..n）的代價，按照最小代價進行分配。

4 結(jié)論

啟發(fā)式添加刪除副本方法是一種簡單有效的數(shù)據(jù)分布算法，為了達到最優(yōu)的數(shù)據(jù)分布，其算法的計算量較大。在啟發(fā)算法中加入內(nèi)存使用限制因素，并限制副本數(shù)量，能夠減少算法計算量，能夠得到一個有效的分布式內(nèi)存數(shù)據(jù)庫數(shù)據(jù)的分布方案。

參考文獻：

[1]YIN FU HUANG，JYH HER CHEN “Fragment Allocation in Distributed Database Design”，JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 17，491-506（2001）

[2]Ajit M，Tamhankar，Sudha Ram，“Database Fragmentation and Allocation： An Integrated Methodology and Case Study”， IEEE TRANSACTIONS ON SYSTEMS， MAN， AND CYBERNETICS-PART A： SYSTEM AND HUMANS， VOL.28， NO. 3， pp. 288-305， MAY 1998.

[3]王同于，陳臨強.一種優(yōu)化的分布式數(shù)據(jù)庫數(shù)據(jù)分布模型[J].杭州電子工業(yè)學(xué)報，1994.12第4期 43-50.

[4]王同于.一種分布式數(shù)據(jù)分布的啟發(fā)式算法[J].計算機時代，1995，（4）.

本文得到國家科技支撐計劃課題支持：2011BAH21B02，2011BAH21B03