基于信息網(wǎng)模型的動態(tài)數(shù)據(jù)劃分策略

陳詩雅 劉夢赤

(武漢大學(xué)計算機學(xué)院 湖北 武漢 430072)

0 引 言

互聯(lián)網(wǎng)的快速發(fā)展，導(dǎo)致數(shù)據(jù)爆炸式的增長，同時對于數(shù)據(jù)存儲的要求也不斷提高，傳統(tǒng)的集中式數(shù)據(jù)庫的缺陷日益顯露：系統(tǒng)可用性和可靠性較低，可擴展性差，導(dǎo)致系統(tǒng)無法滿足日益增長的數(shù)據(jù)的存儲需求。因此構(gòu)建在集群上，甚至不同數(shù)據(jù)中心間的分布式并行數(shù)據(jù)庫[1-2]成為全新的解決方案，它們透明地把數(shù)據(jù)分散存儲到服務(wù)器集群中的不同節(jié)點上，采用并行數(shù)據(jù)處理框架高效應(yīng)對不斷增長的大數(shù)據(jù)，提供更好的水平擴展性和更高的可用性。因此項目組基于信息網(wǎng)模型[3-4]設(shè)計并開發(fā)了分布式并行數(shù)據(jù)庫管理系統(tǒng)，系統(tǒng)能夠通過水平擴展集群節(jié)點數(shù)量來獲得更大的存儲容量和更高的并發(fā)訪問量。

對于分布式系統(tǒng)來說，合理地將整體數(shù)據(jù)分散到多臺存儲機上，可以有效提高系統(tǒng)的存儲效率。而對于數(shù)據(jù)劃分方案的選取，需要考慮到系統(tǒng)可擴展性、負載均衡等性能需求，存儲數(shù)據(jù)的結(jié)構(gòu)，以及劃分算法的時間空間開銷。比如部分分布式系統(tǒng)為了系統(tǒng)的高擴展性選取簡單的基于數(shù)據(jù)的關(guān)鍵值進行劃分的方式，Apache Hbase[5]根據(jù)行鍵(row key)的范圍將Hbase表分割為多個region，然后由HMaster將每個region分配給相應(yīng)的RegionMaster進行管理。一致性哈希算法[6]由于其實現(xiàn)簡單，對大規(guī)模數(shù)據(jù)集劃分性能較好，且易于擴展，得到了廣泛的運用。算法將系統(tǒng)中的物理節(jié)點和需要被存儲的數(shù)據(jù)映射到哈希環(huán)上的合適位置，根據(jù)其相對位置來選取數(shù)據(jù)的存儲節(jié)點[7]。而且有學(xué)者在一致性哈希方法的基礎(chǔ)上引入虛節(jié)點[8]的概念，即每個物理節(jié)點根據(jù)其處理性能從邏輯上切分為多個虛擬節(jié)點，來保證各個處理節(jié)點間的負載均衡。文獻[9]提出根據(jù)處理節(jié)點的異質(zhì)性將一致性哈希和基于范圍的方式相結(jié)合，即機器集群被分為k個節(jié)點集合，一致性哈希算法用于k個集合之間的數(shù)據(jù)劃分，基于范圍的方式用于每個節(jié)點集合中的m臺機器間的數(shù)據(jù)劃分。但是，上述這些劃分方案由于其劃分的隨機性，對于彼此之間相互獨立的數(shù)據(jù)具有較好的劃分效果，但是如果數(shù)據(jù)之間相互關(guān)聯(lián)，在分布式環(huán)境中以任意的方式將這些數(shù)據(jù)劃分到集群中，可能會造成在一個查詢?nèi)蝿?wù)不能在一個存儲節(jié)點上完成的情況，影響數(shù)據(jù)的查詢分析效率。

在信息網(wǎng)模型中，現(xiàn)實世界中的每個實體對應(yīng)于信息網(wǎng)模型數(shù)據(jù)庫中的一個對象，實體自身的所有信息保存在一個INM對象之中，而對象之間通過關(guān)系進行聯(lián)系。如果想查詢和某個對象相關(guān)聯(lián)的對象信息，則需要根據(jù)關(guān)系的指向去訪問關(guān)聯(lián)對象的信息。因此，當這些關(guān)聯(lián)對象存儲在不同節(jié)點上時，查詢?nèi)蝿?wù)無法在一個節(jié)點上完成，需要和存儲關(guān)聯(lián)對象的其他節(jié)點進行通信，造成大量的通信開銷。因此考慮通過減少不必要的通信開銷來提高查詢效率。很多圖分割算法在維護數(shù)據(jù)單元之間的關(guān)聯(lián)關(guān)系，減少查詢?nèi)蝿?wù)跨分區(qū)進行帶來的通信開銷方面提出解決方法。比如針對小規(guī)模圖的靜態(tài)劃分方法KL[10]、FM[11]?；趉-balanced的圖分割算法旨在保持劃分均衡的同時，減少節(jié)點之間的通信開銷。文獻[12]證明此類方法是一個NP難問題，不具備實用性，因此也產(chǎn)生了很多近似算法以及多層次啟發(fā)式算法[13-16]。文獻[16]提出將圖分割問題轉(zhuǎn)化成尋找高質(zhì)量大型子圖的問題，通過去除一些問題節(jié)點，尋找劃分效果較好的大型子圖，并根據(jù)對子圖的劃分優(yōu)化圖分割問題。通過最小化切割的邊數(shù)[17-19]來減少各個分區(qū)之間的通信，從而減少任務(wù)跨分區(qū)的情況，文獻[20]提出一種最小切邊算法，實現(xiàn)了距離常規(guī)有向圖以及強規(guī)則有向圖的有效劃分。

事實上大多數(shù)圖分割方法由于其自身時間和空間復(fù)雜性的限制，在實際應(yīng)用中并不被采用。而且考慮到信息網(wǎng)模型的模型特點，除了需要關(guān)注整體數(shù)據(jù)的劃分方式，還要對一些具有豐富關(guān)聯(lián)關(guān)系和屬性信息的INM大對象單獨進行分割。因為在實際操作時發(fā)現(xiàn)，與這些大對象關(guān)聯(lián)的其他對象較多，使得在大量寫語句并發(fā)時以及查詢此類對象時開銷較大，影響整個系統(tǒng)的性能。因此本文提出了一種基于大對象分割的動態(tài)數(shù)據(jù)劃分方法，從水平方向和垂直方面對數(shù)據(jù)進行分割，保證系統(tǒng)的可擴展性，并提高數(shù)據(jù)的查詢分析效率。

1 系統(tǒng)架構(gòu)

1.1 信息網(wǎng)模型

信息網(wǎng)模型INM是課題組提出的一種語義型數(shù)據(jù)模型，通過對象間各種關(guān)聯(lián)關(guān)系來表達對象之間豐富的語義性。

信息網(wǎng)模型將現(xiàn)實中的實體抽象為類，并將實體之間可能產(chǎn)生的關(guān)系、類和關(guān)系所具備的特性都集成到類中，實例[3-4]則是類的實例化對象。比如：

大學(xué) 武漢大學(xué)[

@級別:{“985工程院校”,“211工程院?！?教育部高校},

@類型:綜合院校,

@主頁:“http://www.whu.edu.cn”,

normal 校訓(xùn):“自強弘毅 求是拓新”,

role 校領(lǐng)導(dǎo)[@任期:4]-> {

校長[@級別:副部級]:竇賢康[@上任時間:“2008-11”,@性別:男],

黨委書記[@級別:副部級]:韓進[@上任時間:“2008-11”],

contain 學(xué)部:{工學(xué)部(武漢大學(xué)),信息學(xué)部(武漢大學(xué)),文理學(xué)部(武漢大學(xué)),醫(yī)學(xué)部(武漢大學(xué))}];

“大學(xué)”是一個類，而“武漢大學(xué)”即為該類的一個實例化對象。該對象具有“級別”等屬性和“校領(lǐng)導(dǎo)”等關(guān)聯(lián)關(guān)系。

在INM模型中，關(guān)系[3-4]是一個很重要的概念，對象之間的語義信息正是通過各種關(guān)聯(lián)關(guān)系來表示的。一個關(guān)系一般連接著兩個對象，比如示例中的關(guān)系contain，它表示對象“武漢大學(xué)”有“學(xué)部”這個包含關(guān)系，該關(guān)系的目標對象(target)之一為對象“工學(xué)部”，即關(guān)系contain連接著“武漢大學(xué)”和“工學(xué)部”兩個對象。除了contain關(guān)系，信息網(wǎng)模型中還有普通關(guān)系normal(默認的關(guān)系類型)、角色關(guān)系role、基于角色的關(guān)系role-based等多種關(guān)聯(lián)關(guān)系。關(guān)系還可能具有層次性，比如“武漢大學(xué)”有以“校領(lǐng)導(dǎo)”為根的角色關(guān)系層次，“校領(lǐng)導(dǎo)”有角色子關(guān)系“校長”等。因此在寫入對象“武漢大學(xué)”時，同時也會寫入各種關(guān)系的目標對象，比如在寫入對象“武漢大學(xué)”時，同時也會寫入對象“竇賢康”、“韓進”等，而對關(guān)系的目標對象“竇賢康”等的寫入、更新或者查詢都需要關(guān)聯(lián)到源對象“武漢大學(xué)”。

基于信息網(wǎng)模型的查詢特性，在存儲對象時，要盡量將具有關(guān)聯(lián)關(guān)系的對象如“武漢大學(xué)”、“竇賢康”、“韓進”等放在一個存儲節(jié)點上，避免查詢時去跨越多個其他節(jié)點來獲取相關(guān)對象，造成額外的通信開銷。而且有些INM對象可能有幾十萬個target，不論是對這些對象本身的讀寫，又或是對其關(guān)聯(lián)對象的讀寫，都會產(chǎn)生不可忽視的時間開銷，從而影響系統(tǒng)性能，因此還需要對這類對象單獨進行處理。

1.2 分布式系統(tǒng)架構(gòu)

分布式并行信息網(wǎng)數(shù)據(jù)庫管理系統(tǒng)(DPINM)的設(shè)計理念之一是具有高度可擴展性，因此系統(tǒng)采用一個主節(jié)點(master)，多個子節(jié)點(slave)的架構(gòu)，如圖1所示。

圖1 DPINMDB系統(tǒng)架構(gòu)

集群中的機器節(jié)點分為兩類：主節(jié)點master和處理節(jié)點slave。其中處理節(jié)點主要進行任務(wù)分發(fā)、數(shù)據(jù)的初始劃分和元數(shù)據(jù)管理，處理節(jié)點則進行數(shù)據(jù)的具體操作。大對象分割即在處理節(jié)點slave上完成。為了快速有效地定位數(shù)據(jù)所在的處理節(jié)點，master節(jié)點上會動態(tài)維護兩張表：Id-Node表和Node-Set表，表示數(shù)據(jù)對象存儲的位置，具體的表內(nèi)容將在劃分方法中介紹。

2 大對象分割

信息網(wǎng)模型中存在部分實例對象，具有龐大的屬性信息和關(guān)聯(lián)關(guān)系，比如對象“美國”，其所具有的關(guān)系“電影”連接了幾十、上百萬個電影對象，那么在寫入、更新或者查詢對象“美國”的相關(guān)信息時，都需要把這個龐大的對象取出來寫進去，耗時較大。而且在寫入大量“美國”拍攝的“電影”時，每個寫任務(wù)都需要等待前一個寫任務(wù)的完成。因此不論是對大對象本身的存取復(fù)雜度，還是其關(guān)聯(lián)的對象，都可能影響系統(tǒng)的性能。因此采取一種策略，對該類對象進行分割。

2.1 存儲結(jié)構(gòu)

大對象被分割后的子對象分布在不同節(jié)點上，為了定位這些子對象所在的節(jié)點，需要保存對象及其子對象所在的節(jié)點信息。因此設(shè)計了Node-Set表來保存對象被分割后的子對象存儲在哪些節(jié)點上。在大對象分割的過程中會生成表項信息?？紤]到將Node-Set表放在各個處理節(jié)點上不利于維護該表的一致性，可能存在不同步的情況，因此將Node-Set表存放在master節(jié)點上統(tǒng)一進行維護。Node-Set表結(jié)構(gòu)如表1所示。

表1 Node-Set表結(jié)構(gòu)

例如對象O1被分割成兩個子對象sub1、sub2，子對象sub1和sub2分別存儲在節(jié)點1和節(jié)點2上，則表項中的第一項為大對象O1的id，第二項為sub1和sub2所在的節(jié)點號1、2。

2.2 大對象分割算法

首先要考慮的是如何盡可能地均勻分割大對象，如果分成的子對象本身大小相差較大的話，則達不到大對象分割的目的。造成對象太大的主要原因是和該對象關(guān)聯(lián)的數(shù)據(jù)對象太多，如果按關(guān)系類型分割是否可行呢？事實上并不可行，因為每個關(guān)系的目標對象數(shù)目可能差距較大，比如對象武漢大學(xué)的normal關(guān)系“校訓(xùn)”只有一個目標對象，而contain關(guān)系“學(xué)部”有四個目標對象，這樣即使拆分之后，子對象之間的大小也有明顯的不均衡。因此按照關(guān)系的目標對象數(shù)目分割是目前最合理的方案，如此分割出來的子對象之間除了關(guān)系的目標對象不同之外，其他信息基本一致。

大對象閾值objSize設(shè)置在配置文件中，因此在對象存儲到底層之前，先讀取配置文件中的閾值和對象大小n進行比較，如果超過閾值則可能分割成num個子對象(num=n/objSize)。如果對象符合分割條件則按以下算法進行分割，得到子對象集合nodeset。大對象分割算法如下：

輸入：大小超過閾值的對象O1。

輸出：分割后的子對象集合nodeset。

1標記該對象被分割setNode(id, Max)

2新建子對象集合subSet，將源對象O1的基礎(chǔ)信息如id、name等拷貝到subSet中的每一個對象subi

3FOR源對象O1的每個關(guān)系reli

4新建關(guān)系rel的子對象集合vecRel

5 統(tǒng)計關(guān)系rel的所有目標對象數(shù)目tgtNum，計算aveTgt=(tgtNum/num)+(tgtNum%num)

6FORvecRel中的每一個關(guān)系initRel

7 拷貝關(guān)系rel的基礎(chǔ)信息(version、name等)和屬性到initRel

8 拷貝aveTgt個關(guān)系rel的target到initRel

9IFinitRel有子關(guān)系

10 重復(fù)8-10的操作

11ENDIF

12ENDFOR

13FOR集合vecRel的每一個關(guān)系reli

14 將關(guān)系reli添加到subi

15ENDFOR

16ENDFOR

17刪除源對象O1

2.3 子對象分布

由于子對象分布在不同處理節(jié)點上，在master節(jié)點上進行數(shù)據(jù)的初始劃分時候很難抉擇應(yīng)該選取哪個節(jié)點作為存儲節(jié)點。如果子對象隨意分發(fā)到某些slave節(jié)點，會出現(xiàn)兩個問題：一是某個處理節(jié)點可能已經(jīng)存儲過這個對象了，將子對象發(fā)送到該節(jié)點則要進行對象合并，而且合并后的對象可能又成一個大對象；二是master節(jié)點在對分割過的對象進行劃分的時候任意選取的話，會造成各個節(jié)點上存儲的子對象大小在動態(tài)變化的過程中逐漸出現(xiàn)較大差距，違背了子對象大小盡量均勻的原則。所以選擇此前沒有存儲過該對象的節(jié)點作為子對象接收節(jié)點，能夠有效避免對象拆分之后又合并，且各節(jié)點上的子對象大小要盡量保持動態(tài)均衡，避免頻繁的維護子對象大小的均衡。

因此本文中提出的子對象分發(fā)策略為：按照節(jié)點號順序選擇，即子對象集合中的第一個子對象存儲在當前操作節(jié)點current上，子對象subi發(fā)到節(jié)點p進行存儲，p的計算如式(1)所示：

p=(lastNode+i)%L

(1)

當p=0時(0表示為master節(jié)點)，p=p+1。

式中：L表示集群節(jié)點數(shù)目。lastNode初始值為current，對象分割后會先去master節(jié)點上按照對象id查找Node-Set表，如果查找到的Node-Set表中的相應(yīng)表項不為NULL(說明此對象被分割過，存在一個節(jié)點位置集合nodeset)，則lastNode置為nodeset中的最后一個node號，即上一次子對象分發(fā)所發(fā)送到的節(jié)點號q，設(shè)置lastNode=q，那么本次選取q的下一個節(jié)點q+1作為起始接收節(jié)點。同時還要將新的node信息順序添加到nodeset中，并更新到master節(jié)點上的Node-Set表。

事實上，在數(shù)據(jù)量足夠多的情況下，通過random()函數(shù)隨機選取nodeset中的后兩個node號(上一次對象分割后子對象的接收節(jié)點)中的某一個作為對象的劃分節(jié)點，可以使得兩個節(jié)點上的子對象大小保持一定的動態(tài)均衡，也就是說如果其中一個節(jié)點上的子對象大小達到臨界值，另一個節(jié)點上的對象大小也是在臨界值附近，不會有太大的差距。因此在分割后的子對象分發(fā)過程中無需再考慮之前已經(jīng)操作過的所有節(jié)點(即nodeset中的所有node值)。

3 基于大對象分割的動態(tài)數(shù)據(jù)劃分方法

系統(tǒng)對插入語句進行處理時，會將每個INM對象及其信息提取出來，并為其分配全局id號。為了快速有效地定位數(shù)據(jù)所在的處理節(jié)點，master節(jié)點會動態(tài)維護一張Id-Node表，一個對象id對應(yīng)一個節(jié)點號，表明該對象存儲在哪個節(jié)點上。表2給出了Id-Node表結(jié)構(gòu)。

表2 Id-Node表結(jié)構(gòu)

因此基于大對象分割的分布式數(shù)據(jù)劃分方案如下：

IQL語句在經(jīng)過詞法語法分析之后得到對象集合。對于對象集合中的對象O1，需要先根據(jù)對象id查詢master節(jié)點上的Id-Node表，然后主節(jié)點master根據(jù)返回的值x決定選取哪個slave節(jié)點作為接收節(jié)點：

?x=0，表明該對象之前沒有被處理過，則分發(fā)到當前操作節(jié)點current處理。

?x=1，…，L-1，表明集群中節(jié)點x上已經(jīng)存儲了對象O1，則分發(fā)到x值對應(yīng)的slave節(jié)點處理。

?x=MAX(MAX為一個大于集群節(jié)點數(shù)目的常量值)，說明此id的對象曾經(jīng)被分割，該對象id對應(yīng)一個node集合，則先讀取存儲在master節(jié)點上的Node-Set表，根據(jù)對象O1的id獲取相應(yīng)的子對象所在節(jié)點集合nodeset。通過random()函數(shù)從集合nodeset中的最后兩個值中隨機選取一個節(jié)點作為接收節(jié)點。

而且，集群中的每臺機器都會被設(shè)置一個負載閾值load，當活躍節(jié)點current(當前進行數(shù)據(jù)存儲的slave節(jié)點)的數(shù)據(jù)量達到load之后，將選擇集群節(jié)點編號中的下一個slave節(jié)點作為活躍節(jié)點，因此將該方法命名為Load Partition數(shù)據(jù)劃分方式。此方法雖然操作簡單，但是能夠較好地滿足系統(tǒng)水平可擴展的需求。而且基于系統(tǒng)對于數(shù)據(jù)寫入操作處理的特性，一條寫入語句會生成多個具有關(guān)聯(lián)關(guān)系的對象，每個對象具有順序的唯一確定的全局對象id，Load Partition劃分方法可以保證這些關(guān)聯(lián)對象在一定時間之內(nèi)能夠存儲在同一個節(jié)點上。對于可能成為系統(tǒng)性能瓶頸大對象，將其分割后分開存儲，在有大量寫任務(wù)并發(fā)的情況下可以提高系統(tǒng)效率。

4 實驗分析

實驗主要分析大對象分割方案對于系統(tǒng)數(shù)據(jù)插入和查詢的效率影響，并對比使用較廣泛的一致性哈希算法和基于大對象分割的動態(tài)數(shù)據(jù)劃分方案下的數(shù)據(jù)查詢時間。

系統(tǒng)分布式集群包括一個主節(jié)點node0和五個處理節(jié)點node1…node5。由于系統(tǒng)底層使用berkeleyDB進行數(shù)據(jù)存儲，因此將大對象閾值objSize設(shè)置為一個BDB大頁大小，即16 384 Byte(16 KB)。鑒于大對象的特殊性，實驗數(shù)據(jù)選定為大約100萬條格式如下所示的電影數(shù)據(jù)：

Insert Movie “name”(“year”)[countryList:“nation”];

Insert Movie “1971 World Series”(“1971”)[countryList:“USA”];

該插入語句在進行詞法語法分析時，會生成兩個對象”Movie”和”Country”，其所對應(yīng)的部分模式語句分別為：

create class Country

[

contain cityList *:City,

normal movieList(M:N):Movie(inverse countryList)

];

create calss Movie

[

＄@languages*:{“English”,“Italian”,“French”},

@runTime : string,

];

類Country中的normal關(guān)系movieList和類Movie以countryList互為逆關(guān)系，因此在插入電影數(shù)據(jù)的時候，其countryList關(guān)系中target(比如“USA”)的movieList關(guān)系也會不斷進行更新。因此利用本文提出的方法對這類數(shù)據(jù)進行處理。

由于大對象一般是隨著插入數(shù)據(jù)的增多逐漸出現(xiàn)的，因此為了方便統(tǒng)計數(shù)據(jù)大小，實驗將一條“Movie”插入語句作為一個數(shù)據(jù)大小，數(shù)據(jù)查詢測試用例如下所示：

query＄x=nation0/movieList:＄y construct＄y;

即查詢對象nation0下的所有電影信息。

4.1 大對象分割對數(shù)據(jù)寫入效率的影響

表3比較了是否進行大對象分割后，數(shù)據(jù)寫入所消耗的時間。通過數(shù)據(jù)對比可以看出，數(shù)據(jù)量較少的情況下，有對象分割的寫入耗時要大，因為數(shù)據(jù)寫入伴隨著大對象分割的額外時間消耗。但是隨著數(shù)據(jù)量的增加，大對象被分割的子對象增多，分割后的寫入時間比未分割的情況下要少，因為前者可同時在多個節(jié)點上進行部分數(shù)據(jù)的寫入操作，相比只有一個節(jié)點可寫入而造成的任務(wù)等待，大對象分割后的寫入耗時要小。

表3 有無對象分割下的數(shù)據(jù)寫入時間

4.2 大對象分割對數(shù)據(jù)查詢效率的影響

表4比較了大對象分割和不分割，查詢該大對象的耗時對比。通過數(shù)據(jù)對比可以看出，在插入數(shù)據(jù)量較少的情況下，兩者的查詢耗時相差無幾，但是隨著數(shù)據(jù)的寫入，數(shù)據(jù)量增大，對象分割后的查詢耗時相比之下越來越短。因為對象被分割成幾部分分別存儲，查詢?nèi)蝿?wù)可以在子對象的所有存儲節(jié)點上并行執(zhí)行，并各自返回結(jié)果，所以查詢時間相對來說會有所減少。

表4 有無對象分割下的數(shù)據(jù)查詢時間

4.3 存儲節(jié)點上的數(shù)據(jù)量變化

表5給出了不同寫入數(shù)據(jù)量下，執(zhí)行大對象分割后各個處理節(jié)點上的數(shù)據(jù)量。為了方便統(tǒng)計，節(jié)點上的數(shù)據(jù)量以存儲的數(shù)據(jù)對象的個數(shù)表示。由于數(shù)據(jù)采用逐節(jié)點寫入的方式，并非每個節(jié)點上都會存儲數(shù)據(jù)，因此表中某些節(jié)點上的數(shù)據(jù)對象為0。對表中數(shù)據(jù)進行分析，由于大對象分割的進行，縮小了數(shù)據(jù)對象之間的大小差距，因此每個節(jié)點上的數(shù)據(jù)對象數(shù)目能夠穩(wěn)定在30萬個左右。但是對于已經(jīng)存儲過數(shù)據(jù)的節(jié)點集合，其中最后一個節(jié)點上的數(shù)據(jù)量可能和其他節(jié)點上的數(shù)據(jù)量相差較大，因為這些節(jié)點上存儲的大部分可能都是其他數(shù)據(jù)對象的子對象。

表5 不同數(shù)據(jù)量下存儲節(jié)點的存儲量

4.4 動態(tài)數(shù)據(jù)劃分方法的性能

該部分實驗用于測試基于大對象分動態(tài)數(shù)據(jù)劃分方法的性能。考慮到信息網(wǎng)模型數(shù)據(jù)的特性，以及哈希方法被使用的廣泛性和合理性，實驗將選取一致性哈希算法和本文提出的方法在本系統(tǒng)上進行性能對比。實驗基于一個包含大約120萬個對象的數(shù)據(jù)集，數(shù)據(jù)集中的數(shù)據(jù)從各所高校的網(wǎng)頁中抽取獲得，并根據(jù)信息網(wǎng)模型的格式轉(zhuǎn)換生成。表6給出了實驗所需的測試用例，Q1是查詢一個對象的信息，不涉及跨對象的情況，Q2和Q3涉及到不同對象之間的查詢跳轉(zhuǎn)。

表6 測試用例

表7給出了兩種劃分方式下的查詢時間對比，通過分析可知，隨著查詢復(fù)雜度的增大，查詢過程中對象跳轉(zhuǎn)次數(shù)也隨之增加，查詢時間越來越大。相比于一致性哈希算法的隨機劃分，本文提出的動態(tài)劃分算法由于能夠保證具有關(guān)聯(lián)關(guān)系的對象盡可能的處在同一節(jié)點，減少查詢過程中跨節(jié)點的情況，再加之大對象分割減少了此類對象的時間消耗，從而大大降低整個查詢的耗時。

表7 兩種劃分方式下的查詢時間對比

5 結(jié) 語

本文基于信息網(wǎng)模型的特點，考慮了對系統(tǒng)性能可能產(chǎn)生影響的因素，設(shè)計了一種基于大對象分割的分布式數(shù)據(jù)劃分方案。一方面將大小超過所設(shè)大對象閾值objSize的對象分割成多個子對象，且子對象分布在不同的存儲節(jié)點上，實驗證明對大對象進行分割可以提高數(shù)據(jù)存儲和查詢的效率。另一方面在主節(jié)點上根據(jù)Id-Node表的信息對數(shù)據(jù)對象進行初始劃分，集群中的每個存儲節(jié)點均設(shè)置了負載閾值load，在數(shù)據(jù)動態(tài)增加的過程中如果存儲的數(shù)據(jù)量超過該節(jié)點的負載閾值，則選取一臺新的服務(wù)器作為存儲節(jié)點。本文提出的劃分方法能夠滿足系統(tǒng)水平可擴展性的需求，且在一定程度上保證了具有關(guān)聯(lián)關(guān)系的對象集中存儲，提高分布式環(huán)境下的查詢效率。

方案目前對于大對象的拆分只考慮了關(guān)系的目標對象，對于部分對象屬性太大的情況則沒有做出相應(yīng)處理。雖然此方案可以保證子對象在一定程度上保持大小動態(tài)平衡，但是隨著一些數(shù)據(jù)更新、刪除操作的進行，各個子對象的大小會發(fā)生一些變動，因此還需要關(guān)注分割后的子對象的大小情況。對于一些小的子對象還需要進行合并或者標記之后等待后續(xù)處理，本文提出的方案目前對這種情況沒有做出很好的處理，在進一步優(yōu)化的過程中會定時去檢查子對象的大小，并做出相應(yīng)的調(diào)整。