陳詩(shī)雅 劉夢(mèng)赤

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

0 引 言

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

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

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

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

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

1.1 信息網(wǎng)模型

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

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

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

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

@類(lèi)型:綜合院校,

@主頁(yè):“http://www.whu.edu.cn”,

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

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

校長(zhǎng)[@級(jí)別:副部級(jí)]:竇賢康[@上任時(shí)間:“2008-11”,@性別:男],

黨委書(shū)記[@級(jí)別:副部級(jí)]:韓進(jìn)[@上任時(shí)間:“2008-11”],

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

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

在INM模型中，關(guān)系[3-4]是一個(gè)很重要的概念，對(duì)象之間的語(yǔ)義信息正是通過(guò)各種關(guān)聯(lián)關(guān)系來(lái)表示的。一個(gè)關(guān)系一般連接著兩個(gè)對(duì)象，比如示例中的關(guān)系contain，它表示對(duì)象“武漢大學(xué)”有“學(xué)部”這個(gè)包含關(guān)系，該關(guān)系的目標(biāo)對(duì)象(target)之一為對(duì)象“工學(xué)部”，即關(guān)系contain連接著“武漢大學(xué)”和“工學(xué)部”兩個(gè)對(duì)象。除了contain關(guān)系，信息網(wǎng)模型中還有普通關(guān)系normal(默認(rèn)的關(guān)系類(lèi)型)、角色關(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)系“校長(zhǎng)”等。因此在寫(xiě)入對(duì)象“武漢大學(xué)”時(shí)，同時(shí)也會(huì)寫(xiě)入各種關(guān)系的目標(biāo)對(duì)象，比如在寫(xiě)入對(duì)象“武漢大學(xué)”時(shí)，同時(shí)也會(huì)寫(xiě)入對(duì)象“竇賢康”、“韓進(jìn)”等，而對(duì)關(guān)系的目標(biāo)對(duì)象“竇賢康”等的寫(xiě)入、更新或者查詢(xún)都需要關(guān)聯(lián)到源對(duì)象“武漢大學(xué)”。

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

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

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

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

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

2 大對(duì)象分割

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

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

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

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

例如對(duì)象O1被分割成兩個(gè)子對(duì)象sub1、sub2，子對(duì)象sub1和sub2分別存儲(chǔ)在節(jié)點(diǎn)1和節(jié)點(diǎn)2上，則表項(xiàng)中的第一項(xiàng)為大對(duì)象O1的id，第二項(xiàng)為sub1和sub2所在的節(jié)點(diǎn)號(hào)1、2。

2.2 大對(duì)象分割算法

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

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

輸入：大小超過(guò)閾值的對(duì)象O1。

輸出：分割后的子對(duì)象集合nodeset。

1標(biāo)記該對(duì)象被分割setNode(id, Max)

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

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

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

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

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

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

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

9IFinitRel有子關(guān)系

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

11ENDIF

12ENDFOR

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

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

15ENDFOR

16ENDFOR

17刪除源對(duì)象O1

2.3 子對(duì)象分布

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

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

p=(lastNode+i)%L

(1)

當(dāng)p=0時(shí)(0表示為master節(jié)點(diǎn))，p=p+1。

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

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

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

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

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

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

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

?x=0，表明該對(duì)象之前沒(méi)有被處理過(guò)，則分發(fā)到當(dāng)前操作節(jié)點(diǎn)current處理。

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

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

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

4 實(shí)驗(yàn)分析

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

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

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

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

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

create class Country

[

contain cityList *:City,

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

];

create calss Movie

[

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

@runTime : string,

];

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

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

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

即查詢(xún)對(duì)象nation0下的所有電影信息。

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

表3比較了是否進(jìn)行大對(duì)象分割后，數(shù)據(jù)寫(xiě)入所消耗的時(shí)間。通過(guò)數(shù)據(jù)對(duì)比可以看出，數(shù)據(jù)量較少的情況下，有對(duì)象分割的寫(xiě)入耗時(shí)要大，因?yàn)閿?shù)據(jù)寫(xiě)入伴隨著大對(duì)象分割的額外時(shí)間消耗。但是隨著數(shù)據(jù)量的增加，大對(duì)象被分割的子對(duì)象增多，分割后的寫(xiě)入時(shí)間比未分割的情況下要少，因?yàn)榍罢呖赏瑫r(shí)在多個(gè)節(jié)點(diǎn)上進(jìn)行部分?jǐn)?shù)據(jù)的寫(xiě)入操作，相比只有一個(gè)節(jié)點(diǎn)可寫(xiě)入而造成的任務(wù)等待，大對(duì)象分割后的寫(xiě)入耗時(shí)要小。

表3 有無(wú)對(duì)象分割下的數(shù)據(jù)寫(xiě)入時(shí)間

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

表4比較了大對(duì)象分割和不分割，查詢(xún)?cè)摯髮?duì)象的耗時(shí)對(duì)比。通過(guò)數(shù)據(jù)對(duì)比可以看出，在插入數(shù)據(jù)量較少的情況下，兩者的查詢(xún)耗時(shí)相差無(wú)幾，但是隨著數(shù)據(jù)的寫(xiě)入，數(shù)據(jù)量增大，對(duì)象分割后的查詢(xún)耗時(shí)相比之下越來(lái)越短。因?yàn)閷?duì)象被分割成幾部分分別存儲(chǔ)，查詢(xún)?nèi)蝿?wù)可以在子對(duì)象的所有存儲(chǔ)節(jié)點(diǎn)上并行執(zhí)行，并各自返回結(jié)果，所以查詢(xún)時(shí)間相對(duì)來(lái)說(shuō)會(huì)有所減少。

表4 有無(wú)對(duì)象分割下的數(shù)據(jù)查詢(xún)時(shí)間

4.3 存儲(chǔ)節(jié)點(diǎn)上的數(shù)據(jù)量變化

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

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

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

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

表6 測(cè)試用例

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

表7 兩種劃分方式下的查詢(xún)時(shí)間對(duì)比

5 結(jié) 語(yǔ)

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

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