辛剛

（中國(guó)航空工業(yè)集團(tuán)公司西安航空計(jì)算技術(shù)研究所，陜西 西安 710065）

1 研究背景及挑戰(zhàn)

作為一種重要的數(shù)據(jù)結(jié)構(gòu)，圖具有極強(qiáng)的表示能力，能夠描述事物之間的復(fù)雜關(guān)系，被廣泛應(yīng)用于工程和社會(huì)生活的各個(gè)領(lǐng)域。比如，公路運(yùn)輸中最優(yōu)路線的確定，公共衛(wèi)生學(xué)上流行病爆發(fā)路徑的預(yù)測(cè)[1,2]。長(zhǎng)期以來(lái)，有關(guān)圖的研究一直較為活躍，覆蓋圖的存儲(chǔ)、查詢和挖掘等各個(gè)方面[3-5]。尤其近年來(lái)，伴隨互聯(lián)網(wǎng)信息類型和服務(wù)模式的不斷豐富和創(chuàng)新，一張張反映事物間復(fù)雜關(guān)系的大圖正在悄然形成。比如，反映用戶間互動(dòng)關(guān)系的社交網(wǎng)絡(luò)圖，反映概念實(shí)體間依賴關(guān)系的知識(shí)圖譜等。這些大規(guī)模、高度結(jié)構(gòu)化的圖數(shù)據(jù)在很大程度上反映真實(shí)世界中的關(guān)系，蘊(yùn)藏著重要的商業(yè)和學(xué)術(shù)價(jià)值。對(duì)這些圖數(shù)據(jù)的分析和挖掘，有望幫助人們找到認(rèn)識(shí)、分析和解決各類問(wèn)題的新途徑。

然而，當(dāng)前圖數(shù)據(jù)處理技術(shù)正面臨嚴(yán)峻挑戰(zhàn)。首先，圖數(shù)據(jù)規(guī)模急劇增長(zhǎng)。在社交網(wǎng)絡(luò)領(lǐng)域，Twitter、Facebook和新浪微博各自的用戶數(shù)量已達(dá)數(shù)億甚至數(shù)十億規(guī)模；在語(yǔ)義網(wǎng)領(lǐng)域，Linked Data已包含310億個(gè)RDF（Resource Description Framework）三元組以及超過(guò)5億個(gè)RDF鏈接；在生物信息學(xué)領(lǐng)域，人類基因組De Brujin圖最壞情況下具有420個(gè)頂點(diǎn)[6]。大規(guī)模圖數(shù)據(jù)的分析和計(jì)算已難以依靠單臺(tái)高性能的計(jì)算機(jī)來(lái)完成。其次，圖數(shù)據(jù)呈現(xiàn)出顯著的動(dòng)態(tài)演化特性，隨著時(shí)間的推移，新的頂點(diǎn)和邊不斷產(chǎn)生，原有的頂點(diǎn)和邊也可能逐漸消亡。比如，在社交網(wǎng)絡(luò)中，新用戶不斷注冊(cè)，原有用戶可能退出，用戶間互動(dòng)頻率也在不斷發(fā)生變化。傳統(tǒng)基于靜態(tài)圖的處理技術(shù)已無(wú)法滿足動(dòng)態(tài)演化圖的新需求?，F(xiàn)實(shí)中的大圖往往都是動(dòng)態(tài)演化的，后文不加以區(qū)分地使用“大圖”和“大規(guī)模動(dòng)態(tài)演化圖”兩個(gè)術(shù)語(yǔ)。

圖處理相關(guān)的各類技術(shù)中，又以存儲(chǔ)最為基礎(chǔ)。圖的存儲(chǔ)方式直接決定圖數(shù)據(jù)的訪問(wèn)效率以及圖查詢與挖掘的效率[6]。研究大規(guī)模動(dòng)態(tài)演化圖的分布式存儲(chǔ)技術(shù)具有重要的現(xiàn)實(shí)意義。一方面，分布式存儲(chǔ)架構(gòu)支持容量靈活擴(kuò)充，能夠滿足圖數(shù)據(jù)規(guī)模不斷增長(zhǎng)的存儲(chǔ)容量需求；另一方面，分布式存儲(chǔ)降低了單臺(tái)計(jì)算機(jī)的存儲(chǔ)容量壓力，有望實(shí)現(xiàn)基于內(nèi)存的圖計(jì)算。當(dāng)前計(jì)算機(jī)的內(nèi)存容量普遍處于GB級(jí)別，當(dāng)依靠單臺(tái)計(jì)算機(jī)處理數(shù)百GB乃至TB級(jí)別的圖數(shù)據(jù)時(shí)，需要進(jìn)行頻繁的磁盤交互，訪問(wèn)性能低下。而在分布式存儲(chǔ)架構(gòu)下，圖數(shù)據(jù)被分割存儲(chǔ)至多臺(tái)計(jì)算機(jī)，每臺(tái)計(jì)算機(jī)在進(jìn)行圖計(jì)算時(shí)，可以將數(shù)據(jù)大部分甚至全部讀入內(nèi)存，極大提高了訪問(wèn)性能。

分布式存儲(chǔ)研究由來(lái)已久，但大多針對(duì)文件數(shù)據(jù)[7,8]，相關(guān)技術(shù)無(wú)法直接用于大圖數(shù)據(jù)。首先，文件數(shù)據(jù)被視作互不相干的獨(dú)立存儲(chǔ)任務(wù)，但圖數(shù)據(jù)內(nèi)部深度耦合，加大了分割難度。若在分布式存儲(chǔ)時(shí)將存在鏈接關(guān)系的大量頂點(diǎn)分開存放，則在數(shù)據(jù)訪問(wèn)階段會(huì)產(chǎn)生頻繁的網(wǎng)絡(luò)通信，嚴(yán)重影響圖數(shù)據(jù)的訪問(wèn)性能，并降低圖計(jì)算和圖處理的效率。其次，文件數(shù)據(jù)一般只會(huì)訪問(wèn)最新狀態(tài)，但圖數(shù)據(jù)要求能夠重現(xiàn)任意時(shí)刻的歷史狀態(tài)，以支持各類歷史分析和查詢應(yīng)用。比如，分析在線社交服務(wù)中的用戶互動(dòng)，比較不同時(shí)刻最具影響力人群的變化；再比如，分析網(wǎng)頁(yè)超鏈接圖的動(dòng)態(tài)結(jié)構(gòu)，獲得不同時(shí)刻網(wǎng)頁(yè)排名的變化[9]。若無(wú)特殊說(shuō)明，后文將基于圖當(dāng)前時(shí)刻的查詢稱為在線分析，而將基于圖某個(gè)歷史時(shí)刻的查詢稱為歷史分析。

基于此，大規(guī)模動(dòng)態(tài)演化圖的分布式存儲(chǔ)技術(shù)需要解決如下兩個(gè)難點(diǎn)問(wèn)題：圖的分割問(wèn)題和圖演化歷史的重現(xiàn)問(wèn)題。

2 國(guó)內(nèi)外研究現(xiàn)狀

圍繞圖的分布式存儲(chǔ)技術(shù)，研究人員開展了大量工作[10-12]。分述如下：

2.1 圖分割

圖分割一般要求各子圖規(guī)模盡可能均衡，并且子圖間交叉邊數(shù)量盡可能少（若一條邊所關(guān)聯(lián)的兩個(gè)頂點(diǎn)被分割至兩個(gè)不同的子圖，則稱該邊為交叉邊）。圖分割效果一般也通過(guò)上述兩個(gè)指標(biāo)進(jìn)行評(píng)價(jià)。

圖分割問(wèn)題已經(jīng)被證明是NP完全問(wèn)題[13]，圖論研究領(lǐng)域提出了大量解決該問(wèn)題的算法，比如，針對(duì)無(wú)權(quán)圖的二分問(wèn)題，Brunetta等人提出了基于線性規(guī)劃松弛和分離技術(shù)序列割的分支切割算法[14]；針對(duì)點(diǎn)和邊具有權(quán)值以及分割數(shù)目為任意值情況下的分割問(wèn)題，F(xiàn)erreira等人提出加權(quán)圖的k-路分割切割算法[15]。這些算法能夠獲得較為精確的分割結(jié)果，但時(shí)間復(fù)雜度較高，所能處理圖的規(guī)模一般較小。

適用于大圖分割的算法大多屬于啟發(fā)式算法，比如，Kernighan和Lin提出的啟發(fā)式交換點(diǎn)對(duì)的KL算法[16]，以及對(duì)KL算法改進(jìn)的FM算法[17]?；趩l(fā)式交換算法所能處理的圖的頂點(diǎn)數(shù)量一般在104以內(nèi)。為了處理更大規(guī)模的圖，基于多層次框架的算法被提出，比如Kumar等人提出的METIS算法[18]，其基本思想是通過(guò)粗糙化技術(shù)將大圖縮減到可接受的小圖，而后在小圖上執(zhí)行分割，最后再利用反粗糙化技術(shù)將小圖上的分割還原成原圖上的分割。基于多層次框架的算法能夠處理百萬(wàn)規(guī)模左右的圖。

近年來(lái)，又出現(xiàn)了可處理數(shù)十億頂點(diǎn)規(guī)模圖分割問(wèn)題的MLP算法[19]，該算法主要通過(guò)標(biāo)簽傳播確定圖分割結(jié)果，在標(biāo)簽傳播中，距離相近的頂點(diǎn)會(huì)被標(biāo)記為相同的標(biāo)簽。針對(duì)自然圖中頂點(diǎn)度分布極不均衡的問(wèn)題，上海交通大學(xué)陳榕等人提出PowerLyra算法[20]，該算法盡可能減少低度數(shù)頂點(diǎn)的副本數(shù)量，而只為少數(shù)高度數(shù)頂點(diǎn)存儲(chǔ)較多副本，以少量冗余數(shù)據(jù)顯著減少了交叉邊數(shù)量。

然而，上述算法只能針對(duì)靜態(tài)圖進(jìn)行處理，難以處理動(dòng)態(tài)圖。Vaquero等人提出隨著大圖結(jié)構(gòu)的不斷變化，迭代式地進(jìn)行頂點(diǎn)遷移，以保持交叉邊數(shù)量保持在合理的范圍[21]。遼寧大學(xué)陳寶燕教授團(tuán)隊(duì)針對(duì)大規(guī)模動(dòng)態(tài)演化圖的分割問(wèn)題做了大量工作，提出增量式算法對(duì)變化后的大圖進(jìn)行分割[22]。但是，二者都屬于延遲更新策略，而非實(shí)時(shí)在線分割。

目前使用的在線分割算法通常采用隨機(jī)策略或貪心策略，隨機(jī)策略以哈希方式確定新頂點(diǎn)所在的頂點(diǎn)子集合，機(jī)制簡(jiǎn)單，但可能導(dǎo)致大量交叉邊。貪心策略則選擇各頂點(diǎn)子集合中含有最多新頂點(diǎn)鄰居的子集合。事實(shí)上，新頂點(diǎn)加入時(shí)往往只會(huì)關(guān)聯(lián)少量頂點(diǎn)，但在隨后的演化過(guò)程中又可能產(chǎn)生許多新邊。僅考慮“眼前利益”的貪心策略仍會(huì)造成大量交叉邊，分割效果較差。

2.2 圖歷史查詢

快照和日志是記錄數(shù)據(jù)演變過(guò)程的兩種方法。每一次更新操作都為所有數(shù)據(jù)存儲(chǔ)一個(gè)新快照的方法會(huì)占用較多的存儲(chǔ)空間，對(duì)不斷動(dòng)態(tài)演化的大圖數(shù)據(jù)并不適用。單純記錄日志的方法可以節(jié)約存儲(chǔ)空間，但要訪問(wèn)某時(shí)刻的圖數(shù)據(jù)時(shí)，需要花費(fèi)時(shí)間進(jìn)行生成。因此，實(shí)用的方法大多屬于“快照+日志”的混合式方法，僅在某些時(shí)刻建立快照，而將兩個(gè)相鄰快照間的更新操作寫入日志。當(dāng)需要訪問(wèn)某個(gè)不存在的快照時(shí)，借助其相近時(shí)刻的已有快照和兩時(shí)刻間的日志數(shù)據(jù)臨時(shí)進(jìn)行生成。

對(duì)“快照+日志”的混合式方法而言，快照和日志數(shù)據(jù)的排布方式非常關(guān)鍵，直接影響已有快照的訪問(wèn)效率以及生成新快照的效率。日志數(shù)據(jù)的每條記錄關(guān)聯(lián)快照數(shù)據(jù)的某個(gè)部分，若在數(shù)據(jù)排布時(shí)未能考慮這種關(guān)聯(lián)性，則會(huì)影響新快照生成的性能。此外，新的快照生成之后，后續(xù)分析亦可能需要對(duì)其進(jìn)行分割。若忽略各快照間的聯(lián)系，將每一個(gè)快照視作獨(dú)立的靜態(tài)圖，則可以通過(guò)現(xiàn)有靜態(tài)圖分割算法對(duì)其分割。但是，這種方式時(shí)間開銷很大，影響歷史分析的性能。

針對(duì)快照和日志數(shù)據(jù)的排布問(wèn)題，中國(guó)科學(xué)技術(shù)大學(xué)陳恩紅和沈向洋教授團(tuán)隊(duì)做了大量工作，提出了一種副本相異數(shù)據(jù)排布方案，即一些副本采用時(shí)間維度優(yōu)先策略，而另一些副本采用空間維度優(yōu)先策略[23]。無(wú)論時(shí)間維度優(yōu)先還是空間維度優(yōu)先，都針對(duì)的是數(shù)據(jù)在單個(gè)磁盤上的排布方式。該方案沒(méi)有討論快照和日志數(shù)據(jù)在分布式存儲(chǔ)系統(tǒng)不同計(jì)算機(jī)間如何排布的問(wèn)題。

針對(duì)新生成快照的分割問(wèn)題，遼寧大學(xué)陳寶燕教授團(tuán)隊(duì)提出一種增量式算法[22]。但該算法本質(zhì)上屬于集中式算法，難以借助分布式計(jì)算實(shí)現(xiàn)并行化工作。

2.3 其它方面

除圖分割和圖歷史重現(xiàn)兩個(gè)問(wèn)題之外，容錯(cuò)問(wèn)題也是大規(guī)模動(dòng)態(tài)演化圖分布式存儲(chǔ)系統(tǒng)必須解決的基本問(wèn)題。目前主要沿用傳統(tǒng)分布式文件存儲(chǔ)系統(tǒng)中的容錯(cuò)方法，即將圖存儲(chǔ)系統(tǒng)中的各類數(shù)據(jù)（含最新大圖數(shù)據(jù)、快照數(shù)據(jù)和日志數(shù)據(jù)）統(tǒng)統(tǒng)看作普通數(shù)據(jù)進(jìn)行多副本存儲(chǔ)[24]?？煺蘸腿罩緮?shù)據(jù)自身所具有的容錯(cuò)性沒(méi)有被有效用于容錯(cuò)算法的優(yōu)化。

3 存在的問(wèn)題與未來(lái)研究方向

盡管研究人員已經(jīng)圍繞大圖的分布式存儲(chǔ)技術(shù)開展了大量研究工作，當(dāng)前大圖分布式存儲(chǔ)系統(tǒng)仍然無(wú)法有效滿足各類大圖應(yīng)用的實(shí)際需求，主要表現(xiàn)如下：

(1)大圖在線分析結(jié)果的實(shí)時(shí)性較差。在線分析需要訪問(wèn)圖數(shù)據(jù)最新時(shí)刻的狀態(tài)，然而，由于圖數(shù)據(jù)更新操作需要重新計(jì)算圖分割，現(xiàn)有技術(shù)大多采用延遲更新策略，即僅將更新操作記錄下來(lái)，積累一段時(shí)間后集中進(jìn)行更新。延遲更新策略影響在線分析結(jié)果的實(shí)時(shí)性。在很多商業(yè)領(lǐng)域中，數(shù)據(jù)分析結(jié)果的實(shí)時(shí)性往往對(duì)人們作出正確決策具有至關(guān)重要的作用。

(2)大圖歷史分析的性能較低。歷史分析需要訪問(wèn)某一時(shí)刻或某些時(shí)刻的圖數(shù)據(jù)?？紤]到存儲(chǔ)效率問(wèn)題，不可能為任意時(shí)刻的圖存儲(chǔ)快照?，F(xiàn)有方法大多以“快照+日志”的方式記錄圖的演變歷史[24]，即僅在某些時(shí)刻建立快照，并將兩個(gè)相鄰快照間的更新操作寫入日志。當(dāng)歷史分析涉及訪問(wèn)某個(gè)不存在的快照時(shí)，借助相近時(shí)刻的快照和兩時(shí)刻間的日志數(shù)據(jù)臨時(shí)生成該快照。受限于快照和日志數(shù)據(jù)的排布方式，現(xiàn)有方法生成新快照的時(shí)間較長(zhǎng)，嚴(yán)重影響了歷史分析的性能。

(3)容錯(cuò)成本存在極大浪費(fèi)。分布式存儲(chǔ)系統(tǒng)必須具備容忍各類故障的能力，需要在故障發(fā)生時(shí)，仍然保證數(shù)據(jù)的可用性。副本是分布式存儲(chǔ)系統(tǒng)最常用的容錯(cuò)技術(shù)，比如，分布式文件存儲(chǔ)系統(tǒng)GFS[25]通常采用三副本容錯(cuò)。若將這種容錯(cuò)技術(shù)直接應(yīng)用于大規(guī)模動(dòng)態(tài)演化圖的分布式存儲(chǔ)系統(tǒng)，則會(huì)造成存儲(chǔ)資源和成本的極大浪費(fèi)。如前文所述，大圖分布式存儲(chǔ)系統(tǒng)除了存儲(chǔ)大圖最新時(shí)刻的狀態(tài)之外，還會(huì)存儲(chǔ)多個(gè)快照數(shù)據(jù)以及用以記錄大圖更新操作的日志數(shù)據(jù)。事實(shí)上，不同于分布式文件存儲(chǔ)系統(tǒng)中的普通文件數(shù)據(jù)，快照和日志數(shù)據(jù)自身就具有一定的容錯(cuò)性。比如，快照B可以借助快照A和記錄了兩快照A、B間更新操作的日志數(shù)據(jù)來(lái)產(chǎn)生，只要快照A和相關(guān)日志數(shù)據(jù)可用，快照B的丟失不會(huì)降低數(shù)據(jù)的可用性。充分利用數(shù)據(jù)自身的容錯(cuò)性，有望獲得更優(yōu)化的容錯(cuò)方法，在保證數(shù)據(jù)可用性的前提下，降低存儲(chǔ)系統(tǒng)的成本。

由上述分析可知，大圖分布式存儲(chǔ)技術(shù)未能有效解決如下問(wèn)題：大規(guī)模動(dòng)態(tài)演化圖的在線分割問(wèn)題、大圖快照的快速生成問(wèn)題以及圖存儲(chǔ)的容錯(cuò)優(yōu)化問(wèn)題。未來(lái)可以圍繞上述問(wèn)題開展進(jìn)一步的研究工作。

參考文獻(xiàn):

[1]祝園園，秦璐，于旭．圖匹配問(wèn)題的應(yīng)用和研究[J]．中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊，2012，8(11)：21-27．

[2]于戈，谷峪，鮑玉斌，王志剛．云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)[J]．計(jì)算機(jī)學(xué)報(bào)，2011，34(10)：1753-1767.

[3]施佺，肖仰華，魯軼奇，陳垚亮，王恒山．基于K2樹的大圖存儲(chǔ)優(yōu)化研究[J]．計(jì)算機(jī)應(yīng)用研究，2011，28(7)：2488-2491．

[4]X.Yan，P.S.Yu，and J．Han，Substructure sim ilarity search in graph databases，in SIGMOD Coriference，2005．

[5]U．Kang，D．H．Chau，and C．Faloutsos，M ining large graphs：Algorithms，inference，and discoveries，in ICDE，2011．

[6]馮國(guó)棟，肖仰華．大圖的分布式存儲(chǔ)[J]．中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊，2012，8(11)：12-16．

[7]M acCorm ick J，Murphy N，Ramasubramanian V，etal.Kinesis：A new approach to replica placement in distributed storage systems[J]． ACM Transactions On Storage(TOS)，2009，4(4)：11．

[8]Thereska E，Donnelly A，Narayanan D．Sierra：practical power-proportionality for data center storage[C]．Proceedings of the 6th ACM conference on Computer systems，2011：169-182．

[9]Yang L，Q i L，Zhao Y P，et al．Link analysis using time series of web graphs[C]．Proceedings of the 16th ACM conference on Information and Know ledge Management，2007：1011-1014．

[10]Low Y，Bickson D，Gonzalez J，et al．Distributed GraphLab：a framework for machine learning and datamining in the cloud[J]．Proceedingsof the VLDB Endowment，2012，5(8)：716-727．

[11]Malew icz G，Austern M H，Bik A JC，etal．Pregel：a system for large-scale graph processing[C]．Proceedingsof the ACM International Conference on Management of Data(SIGMOD)，2010：135-146．

[12]C.Mayer，M.A.Tariq，C.Li，etal.GrapH：heterogeneity-aware graph computation w ith adaptive partitioning.Proceedingsof IEEE InternationalConference of Distributed Computing Systems(ICDCS)，2016：118-128．

[13]Garey M R，Johnson D S，Stockmeyer L．Some simplified NP-complete graph problems[J]．Theoretical Computer Science，1976，1(3)：237-267．

[14]Brunetta L，ConfortiM，R inaldiG．A branch-andcut algorithm for the equicut problem[J]．Mathematical Programming，1997，78(2)：243-263．

[15]Ferreira C E，Maritin A，de Souza C C，et al．The node capacitated graph partitioning problem：A computational study[J]．MathematicalProgramm ing，1998，81(2)：229-256．

[16]Kernighan BW，Lin S．An efficient heuristic procedure for partitioning graphs[J]． Bell system technical journal，1970，49(2)：291-307．

[17]Fiduccia C M，MattheysesR M．A linear-time heuristic for improving network partitions[C]．Proceedings of the 19th IEEEConference on Design Automation，1982：175-181．

[18]Karypis G，Kumar V．Multilevelk-way partitioning scheme for irregular graphs[J]．Journalof Paralleland Distributed computing，1998，48(1)：96-129．

[19]W ang L，Xiao Y，Shao B，et al．How to partition a billion-node graph[C]．Proceedingsof the 30th IEEE InternationalConference on Data Engineering(ICDE)，2014：568-579.

[20]Chen R，Shi J，Chen Y，et al.Powerlyra：Differentiated graph computation and partitioning on skewed graphs[C]．Proceedings of the 10th European Conference on Computer Systems．ACM，2015：1．

[21]Vaquero L，Cuadrado F，Logothetis D，et al．Adaptive partitioning for large-scale dynam ic graphs[C]．Proceedings of the 34th IEEE International Conference on Distributed Computing Systems(ICDCS)，2014：144-153．

[22]單曉歡．大規(guī)模演化圖的分割技術(shù)研究[D]．沈陽(yáng)：遼寧大學(xué)，2014．

[23]苗又山．大規(guī)模動(dòng)態(tài)演化圖的存儲(chǔ)與分析系統(tǒng)研究[D]．中國(guó)博士學(xué)位論文，中國(guó)科學(xué)技術(shù)大學(xué)，2015．

[24]M iao Y，Han W，Li K，et al．ImmortalGraph：a system for storage and analysis of temporal graphs[J]．ACM Transactionson Storage(TOS)，2015，11(3)：14．

[25]Ghemawat S，Gobioff H，Leung S-T．The Google file system[C]．In：Proc．of the 19th Symposium on Operating SystemsPrinciples．2003：29-43．