袁嘉立，劉夢(mèng)赤

(華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣東 廣州 510631)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，數(shù)據(jù)正以爆炸式的速度飛速增長(zhǎng)。在大數(shù)據(jù)時(shí)代[1]，傳統(tǒng)的集中式存儲(chǔ)方式由于系統(tǒng)的可用性和可擴(kuò)展性較低的缺陷無(wú)法滿足日益增長(zhǎng)的數(shù)據(jù)存儲(chǔ)需求。過(guò)去10多年，產(chǎn)生了一批構(gòu)建在集群上的分布式并行數(shù)據(jù)庫(kù)[2-4]，它們通過(guò)將數(shù)據(jù)分布在不同節(jié)點(diǎn)以及使用副本和日志等方式，提供了良好的水平擴(kuò)展性和更高的可用性。與此同時(shí)，為處理大量半結(jié)構(gòu)化、非結(jié)構(gòu)化數(shù)據(jù)，NoSQL(Not Only SQL)數(shù)據(jù)庫(kù)迅猛發(fā)展，涌現(xiàn)了大批如MongoDB、HBase、Neo4J[5]這樣的NoSQL數(shù)據(jù)庫(kù)。本文在信息網(wǎng)模型[6-8]的基礎(chǔ)上，研究并實(shí)現(xiàn)分布式信息網(wǎng)數(shù)據(jù)庫(kù)管理系統(tǒng)，并針對(duì)分布式環(huán)境下的復(fù)雜查詢?cè)O(shè)計(jì)數(shù)據(jù)動(dòng)態(tài)劃分算法。

對(duì)于分布式系統(tǒng)來(lái)說(shuō)，數(shù)據(jù)是否被合理地劃分會(huì)直接影響查詢的性能。對(duì)于數(shù)據(jù)劃分方案的選取，需要考慮到分布式系統(tǒng)的負(fù)載均衡[9]、可擴(kuò)展性等性能需求，以及劃分所帶來(lái)的時(shí)間和空間開(kāi)銷。傳統(tǒng)的數(shù)據(jù)劃分算法主要從負(fù)載均衡的角度出發(fā)，其中具有代表性的是多級(jí)劃分算法[10-11]，該算法對(duì)于相互獨(dú)立的數(shù)據(jù)具有良好的分布式性能，然而對(duì)于關(guān)聯(lián)性較高的數(shù)據(jù)，則會(huì)產(chǎn)生較大的通信開(kāi)銷。一致性哈希算法將系統(tǒng)中的物理節(jié)點(diǎn)和需要被存儲(chǔ)的數(shù)據(jù)映射到哈希環(huán)上的合適位置，根據(jù)其相對(duì)位置來(lái)選取數(shù)據(jù)的存儲(chǔ)節(jié)點(diǎn)[12]。研究者在一致性哈希方法的基礎(chǔ)上引入虛節(jié)點(diǎn)[13]，即每個(gè)物理節(jié)點(diǎn)根據(jù)其處理性能從邏輯上切分為多個(gè)虛擬節(jié)點(diǎn)，來(lái)保證各個(gè)處理節(jié)點(diǎn)間的負(fù)載均衡。但是，上述劃分方案由于其劃分的隨機(jī)性，如果數(shù)據(jù)之間相互關(guān)聯(lián)，在分布式環(huán)境中可能造成一個(gè)查詢?nèi)蝿?wù)需要在多個(gè)存儲(chǔ)節(jié)點(diǎn)上完成，同樣影響查詢效率。

在信息網(wǎng)模型中，每個(gè)現(xiàn)實(shí)世界中的實(shí)體對(duì)應(yīng)于信息網(wǎng)模型數(shù)據(jù)庫(kù)中的一個(gè)對(duì)象，對(duì)象之間通過(guò)關(guān)系進(jìn)行聯(lián)系。如果查詢需要某個(gè)對(duì)象相關(guān)聯(lián)的對(duì)象信息，則需要根據(jù)關(guān)系的指向去訪問(wèn)關(guān)聯(lián)對(duì)象的信息。當(dāng)相互關(guān)聯(lián)的2個(gè)對(duì)象存儲(chǔ)在不同節(jié)點(diǎn)上時(shí)，需要進(jìn)行跨節(jié)點(diǎn)通信，造成昂貴的通信開(kāi)銷。因此，如何進(jìn)行數(shù)據(jù)劃分使負(fù)載均衡的同時(shí)最小化通信開(kāi)銷成為一個(gè)研究難點(diǎn)。

針對(duì)數(shù)據(jù)劃分中的通信開(kāi)銷問(wèn)題，很多圖分割算法在維護(hù)數(shù)據(jù)單元之間的關(guān)聯(lián)關(guān)系，減少查詢?nèi)蝿?wù)跨節(jié)點(diǎn)帶來(lái)的通信開(kāi)銷方向提出了解決方案，如K-balanced圖分割算法[14]。K-balanced圖分割算法在均衡數(shù)據(jù)分布的同時(shí)，最大程度減少了節(jié)點(diǎn)間的通信開(kāi)銷。文獻(xiàn)[15]證明了K-balanced圖分割算法是一個(gè)NP難問(wèn)題。研究者們提出了很多近似算法以及多層次啟發(fā)式算法，例如最小切邊算法[16-18]從最小化切邊數(shù)出發(fā)減少通信開(kāi)銷。但是隨著數(shù)據(jù)量不斷增大，算法本身實(shí)現(xiàn)過(guò)于復(fù)雜，使得算法本身開(kāi)銷抵消了減少的通信開(kāi)銷，在實(shí)際開(kāi)發(fā)中不具備實(shí)用性。此外，研究者們發(fā)現(xiàn)流式圖數(shù)據(jù)分區(qū)方法能夠在有限的資源下擴(kuò)展到非常大的圖，進(jìn)而提出了如Taper[19]、WARP[20]、Peng[21]等數(shù)據(jù)分區(qū)算法。然而，上述方法沒(méi)有考慮到工作負(fù)載和圖數(shù)據(jù)特征，導(dǎo)致節(jié)點(diǎn)負(fù)載的不平衡和節(jié)點(diǎn)間的通信開(kāi)銷增加，從而降低查詢性能。文獻(xiàn)[22]提出一種工作負(fù)載自適應(yīng)流數(shù)據(jù)分區(qū)器WASP。其重新分配策略是動(dòng)態(tài)的而非一次性的，并將主要的元數(shù)據(jù)信息保持在內(nèi)存里以保證快速存儲(chǔ)和訪問(wèn)。

為解決并行系統(tǒng)中請(qǐng)求本身差異帶來(lái)的負(fù)載不均衡，文獻(xiàn)[23]提出一種基于日志的動(dòng)態(tài)數(shù)據(jù)調(diào)整算法。該算法通過(guò)歷史信息預(yù)估下一周期的查詢速度，并根據(jù)統(tǒng)計(jì)的負(fù)載差異進(jìn)行數(shù)據(jù)動(dòng)態(tài)調(diào)整，進(jìn)而解決因請(qǐng)求差異導(dǎo)致的負(fù)載不均衡問(wèn)題。

結(jié)合文獻(xiàn)[22]和文獻(xiàn)[23]中考慮實(shí)際環(huán)境動(dòng)態(tài)變化的設(shè)計(jì)思想，本文提出一種基于信息網(wǎng)模型的關(guān)系特性和查詢的動(dòng)態(tài)數(shù)據(jù)調(diào)整算法。該算法利用信息網(wǎng)模型的強(qiáng)弱關(guān)系特征和歷史關(guān)系調(diào)整信息，得到數(shù)據(jù)對(duì)象之間的初始對(duì)象關(guān)聯(lián)值。再通過(guò)歷史查詢信息結(jié)合對(duì)象間的初始關(guān)聯(lián)值，將相互間關(guān)聯(lián)度較高的數(shù)據(jù)動(dòng)態(tài)調(diào)整到一個(gè)處理節(jié)點(diǎn)上，進(jìn)而減少因數(shù)據(jù)劃分不合理導(dǎo)致的通信開(kāi)銷。算法引入對(duì)象關(guān)聯(lián)值的概念，用于表示2個(gè)對(duì)象之間的關(guān)聯(lián)度。在關(guān)系的動(dòng)態(tài)調(diào)整中，若2個(gè)對(duì)象之間的關(guān)系為強(qiáng)關(guān)系，則這一對(duì)數(shù)據(jù)對(duì)象擁有更大的初始關(guān)聯(lián)值，側(cè)面反映信息網(wǎng)模型中強(qiáng)關(guān)系相比弱關(guān)系在對(duì)象之間有更大的關(guān)聯(lián)度。當(dāng)查詢過(guò)程中產(chǎn)生跨節(jié)點(diǎn)跳對(duì)象操作，則動(dòng)態(tài)修正2個(gè)對(duì)象之間的關(guān)聯(lián)值，進(jìn)一步減少通信開(kāi)銷。同時(shí)還引入關(guān)系對(duì)占比的概念，用于表示一個(gè)節(jié)點(diǎn)內(nèi)有關(guān)系對(duì)象的對(duì)數(shù)占總對(duì)象對(duì)數(shù)的比值，側(cè)面反映一個(gè)節(jié)點(diǎn)內(nèi)不同對(duì)象之間的關(guān)聯(lián)度。在數(shù)據(jù)動(dòng)態(tài)調(diào)整的同時(shí)，不僅要考慮集群內(nèi)節(jié)點(diǎn)之間數(shù)據(jù)量的負(fù)載均衡，還要考慮節(jié)點(diǎn)之間關(guān)系對(duì)占比的負(fù)載均衡，進(jìn)而使得集群長(zhǎng)期查詢保持穩(wěn)定。

1 信息網(wǎng)模型

信息網(wǎng)模型不同于關(guān)系模型[24]，是一種基于對(duì)象[25]、角色模型[26]的語(yǔ)義數(shù)據(jù)模型，可以表示現(xiàn)實(shí)世界復(fù)雜的語(yǔ)義關(guān)聯(lián)。在信息網(wǎng)模型中，現(xiàn)實(shí)中的實(shí)體被抽象成類，實(shí)例則是類的實(shí)例化對(duì)象。該模型通過(guò)引入各種不同的關(guān)系類型以及關(guān)聯(lián)層次，實(shí)現(xiàn)對(duì)于復(fù)雜語(yǔ)義的支持。一個(gè)關(guān)系一般連接著2個(gè)對(duì)象，以如下語(yǔ)句為例，其描述了“大學(xué)”類下的一個(gè)實(shí)例化對(duì)象“華南師范大學(xué)”。該對(duì)象具有“級(jí)別”等屬性和“校領(lǐng)導(dǎo)”等關(guān)聯(lián)關(guān)系。其中關(guān)系contain，它表示對(duì)象“華南師范大學(xué)”有“學(xué)院”這個(gè)包含關(guān)系，該關(guān)系的目標(biāo)對(duì)象之一為對(duì)象“計(jì)算機(jī)學(xué)院”，即關(guān)系contain連接著“華南師范大學(xué)”和“計(jì)算機(jī)學(xué)院”2個(gè)對(duì)象。除了contain關(guān)系，信息網(wǎng)模型中還有普通關(guān)系normal(默認(rèn)關(guān)系類型)、角色關(guān)系role等多種關(guān)聯(lián)關(guān)系。

大學(xué) 華南師范大學(xué)[

@級(jí)別{“211工程院校”，其它}，

@類型:綜合型院校，

@主頁(yè) https://www.scnu.edu.cn/，

normal校訓(xùn) “艱苦奮斗、嚴(yán)謹(jǐn)治學(xué)、求實(shí)創(chuàng)新”，

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

校長(zhǎng)[@級(jí)別:正廳級(jí)]:王恩科[@上任時(shí)間:“2017-9”，@性別:男]，

contain學(xué)院:{計(jì)算機(jī)學(xué)院，心理學(xué)院，外國(guó)語(yǔ)言文化學(xué)院，馬克思主義學(xué)院}];

在信息網(wǎng)模型中，對(duì)象中包含對(duì)應(yīng)實(shí)體的屬性信息以及與其它對(duì)象之間的關(guān)聯(lián)信息。當(dāng)從一個(gè)源對(duì)象出發(fā)想要查詢目標(biāo)對(duì)象的內(nèi)容時(shí)，只需要從源對(duì)象出發(fā)沿著指定的路徑跳入目標(biāo)對(duì)象進(jìn)而獲取到最終的查詢結(jié)果。例如查詢“華南師范大學(xué)計(jì)算機(jī)學(xué)院的人員情況”，此時(shí)需要從“華南師范大學(xué)”這個(gè)對(duì)象出發(fā)，沿著“學(xué)院”//“計(jì)算機(jī)學(xué)院”這個(gè)關(guān)聯(lián)路徑跳入到目標(biāo)對(duì)象中，查詢其“人員情況”對(duì)應(yīng)的內(nèi)容，并最終返回查詢結(jié)果。由此可知，在分布式環(huán)境中，如果一個(gè)查詢涉及復(fù)雜的關(guān)聯(lián)路徑，對(duì)象往往分布在多個(gè)處理節(jié)點(diǎn)之中，處理節(jié)點(diǎn)之間頻繁的跳對(duì)象操作會(huì)導(dǎo)致大量的通信開(kāi)銷。

在分布式環(huán)境中，減少不同節(jié)點(diǎn)之間通信開(kāi)銷的一個(gè)常見(jiàn)思路是使一個(gè)查詢盡可能在一個(gè)處理節(jié)點(diǎn)上完成。本文從該思路出發(fā)，同時(shí)考慮信息網(wǎng)模型的關(guān)系特性，結(jié)合歷史關(guān)系信息和查詢信息，研究數(shù)據(jù)動(dòng)態(tài)調(diào)整策略，使相互間關(guān)聯(lián)度高的數(shù)據(jù)盡可能被劃分到同一個(gè)處理節(jié)點(diǎn)上，進(jìn)而實(shí)現(xiàn)一個(gè)查詢?cè)谝粋€(gè)處理節(jié)點(diǎn)上執(zhí)行，在一個(gè)調(diào)整周期內(nèi)減少?gòu)?fù)雜查詢的通信開(kāi)銷，并在多個(gè)調(diào)整周期內(nèi)保證查詢的穩(wěn)定性。

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

本章主要介紹分布式信息網(wǎng)數(shù)據(jù)庫(kù)管理系統(tǒng)的整體架構(gòu)，并結(jié)合此架構(gòu)說(shuō)明動(dòng)態(tài)數(shù)據(jù)調(diào)整的實(shí)現(xiàn)機(jī)制。

如圖1所示，集群中的節(jié)點(diǎn)分為3類：主節(jié)點(diǎn)、處理節(jié)點(diǎn)和配置節(jié)點(diǎn)。其中主節(jié)點(diǎn)主要進(jìn)行任務(wù)計(jì)劃和數(shù)據(jù)劃分，處理節(jié)點(diǎn)負(fù)責(zé)任務(wù)的具體執(zhí)行和數(shù)據(jù)的具體調(diào)整，配置節(jié)點(diǎn)則是負(fù)責(zé)元數(shù)據(jù)管理。

本文引入對(duì)象關(guān)聯(lián)值Rij(Rij≥1)來(lái)表示對(duì)象i和對(duì)象j的關(guān)聯(lián)程度。對(duì)象關(guān)聯(lián)值越大，表示對(duì)象間的關(guān)聯(lián)性越強(qiáng)，即查詢時(shí)更容易從一個(gè)對(duì)象跳入另一個(gè)對(duì)象。數(shù)據(jù)的動(dòng)態(tài)劃分包含2個(gè)階段:數(shù)據(jù)的初始劃分和數(shù)據(jù)的動(dòng)態(tài)調(diào)整。本文采用一致性哈希作為數(shù)據(jù)的初始劃分策略，并在初次劃分的同時(shí)將有關(guān)系的每對(duì)對(duì)象的關(guān)系類型和初始對(duì)象關(guān)聯(lián)值更新到Id-Relation表中。系統(tǒng)在配置節(jié)點(diǎn)中動(dòng)態(tài)地維護(hù)了Id-Node表與Id-Relation表。Id-Node表用于存儲(chǔ)任意一個(gè)已經(jīng)存在的數(shù)據(jù)對(duì)象所在的處理節(jié)點(diǎn)。如表1所示，Id-Relation表由一對(duì)文檔對(duì)象、對(duì)象之間的關(guān)系類型以及對(duì)象關(guān)聯(lián)值組成。在信息網(wǎng)模型中，對(duì)象間關(guān)系類型越強(qiáng)，其關(guān)聯(lián)性往往越強(qiáng)，因此Rij根據(jù)對(duì)象關(guān)系表中對(duì)象i和對(duì)象j之間的關(guān)系類型來(lái)定義不同的初始值。若關(guān)系類型為弱關(guān)系類型normal，對(duì)象關(guān)聯(lián)值為初始值1。若關(guān)系類型為強(qiáng)關(guān)系類型role或contain，對(duì)象關(guān)聯(lián)值的初始值為2。

表1 Id-Relation表結(jié)構(gòu)

例如對(duì)象O1和對(duì)象Oi之間的關(guān)系類型為弱關(guān)系，其初始對(duì)象關(guān)聯(lián)值為1，當(dāng)前關(guān)聯(lián)值為1。對(duì)象O2和對(duì)象Oj之間的關(guān)系類型為強(qiáng)關(guān)系，其初始對(duì)象關(guān)聯(lián)值為2，當(dāng)前關(guān)聯(lián)值為2。

數(shù)據(jù)的動(dòng)態(tài)調(diào)整并行地分為關(guān)系動(dòng)態(tài)調(diào)整和查詢動(dòng)態(tài)調(diào)整。當(dāng)用戶發(fā)出一個(gè)任務(wù)請(qǐng)求時(shí)，主節(jié)點(diǎn)通過(guò)Id-Node表獲取請(qǐng)求對(duì)象所在的處理節(jié)點(diǎn)并將任務(wù)下發(fā)。若該任務(wù)請(qǐng)求涉及對(duì)象間的關(guān)系更新，處理節(jié)點(diǎn)則會(huì)在接受任務(wù)進(jìn)行處理的同時(shí)，在配置節(jié)點(diǎn)的表1中根據(jù)關(guān)系的動(dòng)態(tài)調(diào)整策略更新對(duì)象之間的關(guān)系。若是查詢?nèi)蝿?wù)，處理節(jié)點(diǎn)則會(huì)在接受任務(wù)進(jìn)行處理的同時(shí)，記錄處理過(guò)程中產(chǎn)生的通信開(kāi)銷，并結(jié)合配置節(jié)點(diǎn)中的表1的關(guān)系類型，在配置節(jié)點(diǎn)的表1中動(dòng)態(tài)更新數(shù)據(jù)對(duì)象之間的關(guān)聯(lián)度，具體的策略在查詢的動(dòng)態(tài)調(diào)整中介紹。關(guān)系動(dòng)態(tài)調(diào)整算法的具體描述如下。

算法1 關(guān)系動(dòng)態(tài)調(diào)整算法。

輸入:各個(gè)處理節(jié)點(diǎn)的關(guān)系調(diào)整統(tǒng)計(jì)信息。

輸出:Id-Relation表。

過(guò)程:

1)根據(jù)修改的統(tǒng)計(jì)信息，篩選出關(guān)系信息發(fā)生變動(dòng)的數(shù)據(jù)對(duì)象對(duì)。

2)依次處理關(guān)系信息發(fā)生變動(dòng)的每對(duì)數(shù)據(jù)對(duì)象。

3)判斷對(duì)象之間關(guān)系是否修改或新增為S(強(qiáng)關(guān)系role、contain)，是就將Id-Relation表中該對(duì)對(duì)象的對(duì)象關(guān)聯(lián)值修改為2后，跳轉(zhuǎn)到步驟2，否則跳轉(zhuǎn)到步驟4。

4)判斷對(duì)象之間關(guān)系是否修改或新增為W(弱關(guān)系normal)，是就將Id-Relation表中該對(duì)對(duì)象的關(guān)聯(lián)值修改為1后，跳轉(zhuǎn)到步驟2，否則跳轉(zhuǎn)到步驟5。

5)判斷對(duì)象之間關(guān)系是否刪除，是就將Id-Relation表中該對(duì)對(duì)象刪除后，跳轉(zhuǎn)到步驟2，否則直接跳轉(zhuǎn)到步驟2。

6)得到更新后的Id-Relation表。

3 動(dòng)態(tài)數(shù)據(jù)調(diào)整算法

3.1 對(duì)象相關(guān)值的動(dòng)態(tài)維護(hù)

數(shù)據(jù)的查詢動(dòng)態(tài)調(diào)整分為2個(gè)階段：對(duì)象關(guān)聯(lián)值的維護(hù)和節(jié)點(diǎn)之間對(duì)象的轉(zhuǎn)移。在第1階段中，根據(jù)查詢進(jìn)行動(dòng)態(tài)調(diào)整。當(dāng)查詢過(guò)程中涉及跨節(jié)點(diǎn)跳對(duì)象操作，則對(duì)應(yīng)的Rij進(jìn)行增加操作。根據(jù)配置節(jié)點(diǎn)中Id-Node表，若關(guān)系類型為弱關(guān)系，則進(jìn)行加1操作。為確保在相同查詢頻率下強(qiáng)關(guān)系類型的對(duì)象關(guān)聯(lián)值高于弱關(guān)系類型的對(duì)象關(guān)聯(lián)值，若關(guān)系類型為強(qiáng)關(guān)系，則進(jìn)行加2操作。進(jìn)入第2階段，對(duì)象的動(dòng)態(tài)調(diào)整算法根據(jù)第1階段得到的Rij進(jìn)行對(duì)象的動(dòng)態(tài)調(diào)整。

在數(shù)據(jù)調(diào)整的過(guò)程中，會(huì)統(tǒng)計(jì)上一次對(duì)象動(dòng)態(tài)調(diào)整到目前為止數(shù)據(jù)操作帶來(lái)的通信開(kāi)銷Ototal，其中由于節(jié)點(diǎn)內(nèi)通信開(kāi)銷相比于跨節(jié)點(diǎn)通信開(kāi)銷可以忽略不計(jì)，因此只統(tǒng)計(jì)跨節(jié)點(diǎn)通信開(kāi)銷Obe。當(dāng)Ototal超過(guò)預(yù)設(shè)的閾值Omax時(shí)，啟動(dòng)對(duì)象動(dòng)態(tài)調(diào)整。為了防止對(duì)象以及對(duì)象關(guān)系類型調(diào)整過(guò)于頻繁，根據(jù)統(tǒng)計(jì)情況設(shè)置最小調(diào)整周期Tmin，即在最小調(diào)整周期內(nèi)，即使Ototal已經(jīng)超過(guò)了閾值，也不會(huì)馬上進(jìn)行調(diào)整，而是延遲一段時(shí)間進(jìn)行。

3.2 數(shù)據(jù)的動(dòng)態(tài)調(diào)整

當(dāng)某個(gè)周期內(nèi)Ototal超過(guò)預(yù)設(shè)的閾值Omax時(shí)，Id-Relation表停止更新，處理節(jié)點(diǎn)根據(jù)當(dāng)前Id-Relation表和查詢調(diào)整策略進(jìn)行數(shù)據(jù)調(diào)整。在數(shù)據(jù)的動(dòng)態(tài)調(diào)整過(guò)程中，優(yōu)先處理Ototal較大的節(jié)點(diǎn)，因此，首先將各個(gè)節(jié)點(diǎn)按照Ototal降序排列，然后按照順序依次處理。

為說(shuō)明方便，此處引入一個(gè)新概念:查詢貢獻(xiàn)值。前文介紹了對(duì)象關(guān)聯(lián)值Rij，用來(lái)量化對(duì)象i和對(duì)象j的關(guān)聯(lián)程度。對(duì)象的動(dòng)態(tài)調(diào)整是指將對(duì)象Oij從節(jié)點(diǎn)nodei移動(dòng)到另一個(gè)節(jié)點(diǎn)nodej上。對(duì)象Oij的查詢貢獻(xiàn)度量化了由于對(duì)象Oij從節(jié)點(diǎn)nodei移動(dòng)到另一個(gè)節(jié)點(diǎn)nodej后集群整體減少的通信開(kāi)銷，記為Cdec。Cdec計(jì)算公式如下：

(1)

其中dj是nodej上的任意對(duì)象，RdjOij表示nodej的任意對(duì)象dj與對(duì)象Oij的對(duì)象關(guān)聯(lián)值。Cdec表示了對(duì)象Oij從源節(jié)點(diǎn)nodei移動(dòng)到處理節(jié)點(diǎn)nodej為集群減少的通信開(kāi)銷量。

針對(duì)每個(gè)待處理的節(jié)點(diǎn)，篩選出產(chǎn)生跨節(jié)點(diǎn)通信的對(duì)象，并按照對(duì)應(yīng)的查詢貢獻(xiàn)值降序排列，按照查詢貢獻(xiàn)值從高到底依次處理。如果查詢貢獻(xiàn)值大于0，則請(qǐng)求節(jié)點(diǎn)移動(dòng)對(duì)集群整體的通信消耗是減少的。另外，考慮到節(jié)點(diǎn)間對(duì)象個(gè)數(shù)的負(fù)載均衡，各個(gè)處理節(jié)點(diǎn)上的對(duì)象個(gè)數(shù)應(yīng)滿足以下條件:

ni≤σ(N/p)

(2)

其中，ni表示處理節(jié)點(diǎn)i的對(duì)象個(gè)數(shù)；N表示總的對(duì)象個(gè)數(shù)；p表示集群中的節(jié)點(diǎn)總數(shù)；σ為節(jié)點(diǎn)間對(duì)象個(gè)數(shù)的調(diào)整因子，側(cè)面反映對(duì)節(jié)點(diǎn)間對(duì)象個(gè)數(shù)負(fù)載不均衡的容忍程度，其值越大，表示容忍程度越高，并根據(jù)統(tǒng)計(jì)信息獲取。

為說(shuō)明方便，此處引入一個(gè)新的概念:關(guān)系對(duì)占比。除了考慮節(jié)點(diǎn)對(duì)象個(gè)數(shù)的負(fù)載均衡，針對(duì)信息網(wǎng)模型的關(guān)系特性，還需要考慮節(jié)點(diǎn)間強(qiáng)弱關(guān)系占比的負(fù)載均衡。例如節(jié)點(diǎn)i有ni個(gè)對(duì)象，則該節(jié)點(diǎn)互有關(guān)系的對(duì)象對(duì)最多為(ni-1)!個(gè)。由配置節(jié)點(diǎn)的Id-Node表可以獲取節(jié)點(diǎn)i的對(duì)象個(gè)數(shù)，由配置節(jié)點(diǎn)的Id-Relation表可以獲取節(jié)點(diǎn)i當(dāng)前互有關(guān)系的對(duì)象對(duì)個(gè)數(shù)，即關(guān)系對(duì)的個(gè)數(shù)，因此可以得到節(jié)點(diǎn)i的初始關(guān)系對(duì)占比。另外，由于信息網(wǎng)模型的強(qiáng)弱關(guān)系特性，還需考慮強(qiáng)關(guān)系相比于弱關(guān)系對(duì)于對(duì)象之間更高的關(guān)聯(lián)度。在滿足式(2)的前提下，各個(gè)處理節(jié)點(diǎn)上的關(guān)系占比應(yīng)滿足以下條件：

(3)

對(duì)象的動(dòng)態(tài)調(diào)整過(guò)程中，會(huì)先對(duì)不同對(duì)象產(chǎn)生的通信開(kāi)銷制定對(duì)象的調(diào)整計(jì)劃，計(jì)劃制定完成后，為保證節(jié)點(diǎn)對(duì)象個(gè)數(shù)間的負(fù)載均衡，必須對(duì)式(2)進(jìn)行驗(yàn)證，在滿足的前提下還需保證節(jié)點(diǎn)強(qiáng)弱關(guān)系占比的負(fù)載均衡，再對(duì)式(3)進(jìn)行驗(yàn)證，驗(yàn)證通過(guò)則執(zhí)行調(diào)整計(jì)劃，否則修正調(diào)整計(jì)劃。對(duì)于所有需要處理的分片重復(fù)上述過(guò)程，直至所有的分片都處理結(jié)束，至此一次數(shù)據(jù)的動(dòng)態(tài)調(diào)整過(guò)程結(jié)束。分布式信息網(wǎng)數(shù)據(jù)庫(kù)管理系統(tǒng)重新執(zhí)行用戶請(qǐng)求，對(duì)象之間的Rij值重新從Id-Relation表中獲取，并繼續(xù)按照查詢進(jìn)行動(dòng)態(tài)維護(hù)，循環(huán)上述過(guò)程。

對(duì)象的動(dòng)態(tài)調(diào)整策略在減少通信開(kāi)銷的基礎(chǔ)上，盡可能地使得劃分結(jié)果具有較好的負(fù)載均衡性。動(dòng)態(tài)調(diào)整算法的具體描述如下。

算法2 動(dòng)態(tài)調(diào)整算法。

輸入:各個(gè)處理節(jié)點(diǎn)上的查詢統(tǒng)計(jì)信息。

輸出:對(duì)象動(dòng)態(tài)調(diào)整計(jì)劃過(guò)程。

過(guò)程:

1)根據(jù)通信開(kāi)銷對(duì)各個(gè)處理節(jié)點(diǎn)進(jìn)行降序排列。

2)依次處理排序后的每個(gè)處理節(jié)點(diǎn)。

3)根據(jù)查詢的記錄信息，篩選出產(chǎn)生跨節(jié)點(diǎn)通信開(kāi)銷的請(qǐng)求對(duì)象，并按查詢貢獻(xiàn)值進(jìn)行降序排列(優(yōu)先處理查詢貢獻(xiàn)值較大的對(duì)象)。

4)依次處理排序后的每個(gè)請(qǐng)求對(duì)象。

5)判斷該請(qǐng)求查詢貢獻(xiàn)值是否大于0(整體通信開(kāi)銷減少)，是就將該對(duì)象加入轉(zhuǎn)移列表中，轉(zhuǎn)到步驟4，否則轉(zhuǎn)到步驟6。

6)判斷是否滿足節(jié)點(diǎn)間對(duì)象個(gè)數(shù)的負(fù)載均衡條件，即條件式(2)，是就轉(zhuǎn)到步驟2，否則轉(zhuǎn)到步驟7。

7)判斷是否滿足節(jié)點(diǎn)間強(qiáng)弱關(guān)系占比的負(fù)載均衡條件，即條件式(3)，是就跳轉(zhuǎn)到步驟2，否則跳轉(zhuǎn)到步驟4。

8)得到對(duì)象調(diào)整計(jì)劃。

4 實(shí)驗(yàn)結(jié)果與分析

本文利用實(shí)驗(yàn)對(duì)比分析使用較廣泛的一致性哈希算法，結(jié)合在線查詢的動(dòng)態(tài)工作負(fù)載特性的自適應(yīng)流數(shù)據(jù)分區(qū)器WASP，以及綜合考慮信息網(wǎng)模型關(guān)系特性及查詢信息的動(dòng)態(tài)調(diào)整算法，測(cè)試用例的短期通信開(kāi)銷以及長(zhǎng)期的查詢穩(wěn)定性。

實(shí)驗(yàn)使用的分布式集群包括8個(gè)相同的處理節(jié)點(diǎn)、1個(gè)主節(jié)點(diǎn)以及1個(gè)配置節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)使用主頻為3.60 GHz的Intel(R) Core(TM)9700的8核處理器，其內(nèi)存大小為16 GB，硬盤大小為1 TB，節(jié)點(diǎn)間通信使用1000 Mbit/s以太網(wǎng)。集群所有節(jié)點(diǎn)均使用Linux64-bit CentOS操作系統(tǒng)，本文系統(tǒng)的所有代碼均用C++語(yǔ)言實(shí)現(xiàn)。實(shí)驗(yàn)基于WatDiv標(biāo)準(zhǔn)合成數(shù)據(jù)集，該數(shù)據(jù)集為RDF數(shù)據(jù)集[27]。WatDiv是一個(gè)標(biāo)準(zhǔn)的RDF合成數(shù)據(jù)集[28]，允許用戶自定義自己的數(shù)據(jù)集并生成不同大小的數(shù)據(jù)集，本文將數(shù)據(jù)轉(zhuǎn)換為信息網(wǎng)模型的數(shù)據(jù)格式(也就是WatDiv40M，將RDF數(shù)據(jù)集中的400萬(wàn)個(gè)頂點(diǎn)轉(zhuǎn)為信息網(wǎng)模型中的400萬(wàn)個(gè)數(shù)據(jù)對(duì)象)。

表2給出了實(shí)驗(yàn)中要使用的測(cè)試用例。Q1～Q4語(yǔ)句和Q5～Q8語(yǔ)句涉及的對(duì)象個(gè)數(shù)逐漸增加，其中，Q1和Q5比較特殊，用于查詢一個(gè)具體對(duì)象的內(nèi)容，不涉及節(jié)點(diǎn)之間的通信。Q1和Q5的設(shè)計(jì)主要用于測(cè)試不同時(shí)刻網(wǎng)絡(luò)環(huán)境差異等客觀因素對(duì)查詢速度等指標(biāo)的影響，對(duì)其它查詢起到一個(gè)參考作用。Q2～Q4和Q6～Q8涉及的節(jié)點(diǎn)間通信次數(shù)逐漸增加。Q2～Q4和Q6～Q8的設(shè)計(jì)旨在測(cè)試短期內(nèi)動(dòng)態(tài)調(diào)整算法對(duì)不同數(shù)據(jù)請(qǐng)求的優(yōu)化能力。此外，Q5～Q8涉及的查詢對(duì)象范圍不同于Q1～Q4，且實(shí)驗(yàn)將Q1～Q4和Q5～Q8的查詢請(qǐng)求放在2個(gè)不同的周期內(nèi)，測(cè)試動(dòng)態(tài)調(diào)整算法對(duì)系統(tǒng)長(zhǎng)期查詢穩(wěn)定性的優(yōu)化能力。

表2 測(cè)試用例

4.1 算法性能比較

表3給出了3個(gè)調(diào)整周期T1～T3內(nèi)對(duì)8個(gè)查詢請(qǐng)求Q1～Q8在一致性哈希算法、查詢調(diào)整算法和動(dòng)態(tài)調(diào)整算法下的查詢時(shí)間與通信開(kāi)銷。對(duì)Q2～Q4和Q6～Q8簡(jiǎn)單分析可知，隨著復(fù)雜查詢帶來(lái)的跨節(jié)點(diǎn)通信次數(shù)的增加，查詢時(shí)間也在增長(zhǎng)。當(dāng)通信開(kāi)銷太大時(shí)，通信造成的時(shí)間開(kāi)銷成為了影響查詢速度的首要因素，因此，通信次數(shù)的減少會(huì)間接加快查詢速度。分析實(shí)驗(yàn)數(shù)據(jù)可知，動(dòng)態(tài)調(diào)整算法可以使得通信次數(shù)減少35%～55%，同時(shí)查詢時(shí)間減少35%左右，因此，該調(diào)整策略可以在周期內(nèi)較大程度提高查詢性能。此外，將T3內(nèi)的錯(cuò)序查詢與T1和T2內(nèi)的查詢對(duì)比可知，只根據(jù)頻繁查詢模式和圖拓?fù)涮卣鱽?lái)管理節(jié)點(diǎn)重新分配的WASP動(dòng)態(tài)調(diào)整算法，在一個(gè)調(diào)整周期內(nèi)將有潛在關(guān)聯(lián)的數(shù)據(jù)盡可能存放在同一個(gè)處理節(jié)點(diǎn)上，雖然在短期內(nèi)查詢性能有所提升，但沒(méi)有考慮到信息網(wǎng)模型給數(shù)據(jù)之間帶來(lái)的關(guān)聯(lián)，隨著時(shí)間的增加，在其它周期內(nèi)重新進(jìn)行相關(guān)對(duì)象的查詢會(huì)有較大性能波動(dòng)。實(shí)驗(yàn)結(jié)果表明，動(dòng)態(tài)調(diào)整算法即使在不同周期內(nèi)的同一個(gè)查詢，其查詢時(shí)間也在5%～10%的波動(dòng)區(qū)間內(nèi)，因此該策略保證了系統(tǒng)長(zhǎng)期查詢的穩(wěn)定性。

表3 3種調(diào)整算法下的通信開(kāi)銷與查詢時(shí)間對(duì)比

4.2 負(fù)載均衡測(cè)試

動(dòng)態(tài)調(diào)整算法調(diào)整前后各個(gè)處理節(jié)點(diǎn)上的對(duì)象個(gè)數(shù)如圖2所示?？梢钥闯觯瑒?dòng)態(tài)調(diào)整算法調(diào)整過(guò)后集群中各個(gè)節(jié)點(diǎn)的對(duì)象個(gè)數(shù)與采用一致性哈希算法進(jìn)行初次劃分的結(jié)果較為接近，仍屬于相對(duì)均衡的狀態(tài)。實(shí)驗(yàn)結(jié)果表明，動(dòng)態(tài)數(shù)據(jù)調(diào)整算法在根據(jù)對(duì)象之間關(guān)聯(lián)性動(dòng)態(tài)調(diào)整數(shù)據(jù)的同時(shí)，可使各個(gè)處理節(jié)點(diǎn)的數(shù)據(jù)量處于相對(duì)均衡的狀態(tài)。

WASP調(diào)整算法與動(dòng)態(tài)調(diào)整算法在調(diào)整后各個(gè)處理節(jié)點(diǎn)上的關(guān)系對(duì)占比如圖3所示。由于WASP調(diào)整算法未考慮信息網(wǎng)模型的關(guān)系特征，各個(gè)節(jié)點(diǎn)的關(guān)系對(duì)占比差距很大。而動(dòng)態(tài)調(diào)整算法中考慮了節(jié)點(diǎn)對(duì)象的強(qiáng)弱關(guān)系占比，在調(diào)整后保證集群整體數(shù)據(jù)量負(fù)載均衡的同時(shí)，也使各個(gè)節(jié)點(diǎn)上的關(guān)系對(duì)占比達(dá)到了相對(duì)均衡的狀態(tài)。

5 結(jié)束語(yǔ)

本文基于信息網(wǎng)模型的關(guān)系特性，考慮對(duì)復(fù)雜查詢效率可能產(chǎn)生影響的因素，設(shè)計(jì)了一種基于信息網(wǎng)模型查詢的動(dòng)態(tài)數(shù)據(jù)劃分方案。該算法利用歷史關(guān)系信息和信息網(wǎng)強(qiáng)弱關(guān)系特性得到數(shù)據(jù)對(duì)象之間的初始對(duì)象關(guān)聯(lián)值，再結(jié)合歷史查詢信息調(diào)整對(duì)象關(guān)聯(lián)值，進(jìn)而將關(guān)聯(lián)程度較高的數(shù)據(jù)對(duì)象動(dòng)態(tài)調(diào)整到一個(gè)處理節(jié)點(diǎn)上，減少因跨節(jié)點(diǎn)導(dǎo)致的節(jié)點(diǎn)間通信開(kāi)銷。實(shí)驗(yàn)結(jié)果表明，與一致性哈希算法相比，該算法可減少單個(gè)周期內(nèi)35%～55%的查詢時(shí)間，多個(gè)周期的相同查詢效率波動(dòng)降至5%～10%，在加快周期內(nèi)查詢速度的同時(shí)，保證了系統(tǒng)長(zhǎng)期查詢的穩(wěn)定性。同時(shí)集群中的各個(gè)處理節(jié)點(diǎn)之間擁有相比WASP算法更均衡的關(guān)系對(duì)占比，優(yōu)化了分布式環(huán)境的整體性能。

考慮到實(shí)現(xiàn)的復(fù)雜程度，本文中最初的數(shù)據(jù)劃分基于一致性哈希算法實(shí)現(xiàn)，并在劃分過(guò)程中記錄了每對(duì)數(shù)據(jù)對(duì)象之間的關(guān)系信息。一致性哈希算法使得數(shù)據(jù)均勻隨機(jī)地被劃分到各個(gè)處理節(jié)點(diǎn)上，導(dǎo)致相互關(guān)聯(lián)的數(shù)據(jù)極大可能不在同一個(gè)處理節(jié)點(diǎn)上，因此，數(shù)據(jù)動(dòng)態(tài)調(diào)整算法將會(huì)伴隨大量的數(shù)據(jù)交換。此外，當(dāng)前方案的負(fù)載均衡策略基于固定的處理節(jié)點(diǎn)數(shù)目。當(dāng)集群中的數(shù)據(jù)總量過(guò)大或過(guò)小時(shí)，節(jié)點(diǎn)的數(shù)量需要手動(dòng)修改，涉及多次初始數(shù)據(jù)劃分及大量數(shù)據(jù)交換。因此，下一步將研究如何結(jié)合信息網(wǎng)模型的特點(diǎn)，設(shè)計(jì)初始數(shù)據(jù)劃分算法，使得相互關(guān)聯(lián)的數(shù)據(jù)在初始階段就被劃分到同一個(gè)處理節(jié)點(diǎn)上，并在后續(xù)的數(shù)據(jù)調(diào)整過(guò)程中能根據(jù)數(shù)據(jù)量動(dòng)態(tài)調(diào)整集群中處理節(jié)點(diǎn)的數(shù)目，同時(shí)保證數(shù)據(jù)量和關(guān)系對(duì)占比的負(fù)載均衡，使分布式信息網(wǎng)數(shù)據(jù)庫(kù)管理系統(tǒng)達(dá)到更好的處理性能。