基于信息網模型的動態數據劃分策略

陳詩雅 劉夢赤

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

0 引 言

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

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

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

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

1 系統架構

1.1 信息網模型

信息網模型INM是課題組提出的一種語義型數據模型，通過對象間各種關聯關系來表達對象之間豐富的語義性。

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

大學 武漢大學[

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

@類型:綜合院校,

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

normal 校訓:“自強弘毅 求是拓新”,

role 校領導[@任期:4]-> {

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

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

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

“大學”是一個類，而“武漢大學”即為該類的一個實例化對象。該對象具有“級別”等屬性和“校領導”等關聯關系。

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

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

1.2 分布式系統架構

分布式并行信息網數據庫管理系統(DPINM)的設計理念之一是具有高度可擴展性，因此系統采用一個主節點(master)，多個子節點(slave)的架構，如圖1所示。

圖1 DPINMDB系統架構

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

2 大對象分割

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

2.1 存儲結構

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

表1 Node-Set表結構

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

2.2 大對象分割算法

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

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

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

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

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

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

3FOR源對象O1的每個關系reli

4新建關系rel的子對象集合vecRel

5 統計關系rel的所有目標對象數目tgtNum，計算aveTgt=(tgtNum/num)+(tgtNum%num)

6FORvecRel中的每一個關系initRel

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

8 拷貝aveTgt個關系rel的target到initRel

9IFinitRel有子關系

10 重復8-10的操作

11ENDIF

12ENDFOR

13FOR集合vecRel的每一個關系reli

14 將關系reli添加到subi

15ENDFOR

16ENDFOR

17刪除源對象O1

2.3 子對象分布

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

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

p=(lastNode+i)%L

(1)

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

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

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

3 基于大對象分割的動態數據劃分方法

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

表2 Id-Node表結構

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

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

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

?x=1，…，L-1，表明集群中節點x上已經存儲了對象O1，則分發到x值對應的slave節點處理。

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

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

4 實驗分析

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

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

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

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

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

create class Country

[

contain cityList *:City,

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

];

create calss Movie

[

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

@runTime : string,

];

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

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

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

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

4.1 大對象分割對數據寫入效率的影響

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

表3 有無對象分割下的數據寫入時間

4.2 大對象分割對數據查詢效率的影響

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

表4 有無對象分割下的數據查詢時間

4.3 存儲節點上的數據量變化

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

表5 不同數據量下存儲節點的存儲量

4.4 動態數據劃分方法的性能

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

表6 測試用例

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

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

5 結 語

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

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