辛剛

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

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

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

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

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

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

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

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

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

2.1 圖分割

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

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

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

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

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

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

2.2 圖歷史查詢

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

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

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

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

2.3 其它方面

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

3 存在的問題與未來研究方向

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

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

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

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

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

參考文獻:

[1]祝園園，秦璐，于旭．圖匹配問題的應用和研究[J]．中國計算機學會通訊，2012，8(11)：21-27．

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

[3]施佺，肖仰華，魯軼奇，陳垚亮，王恒山．基于K2樹的大圖存儲優(yōu)化研究[J]．計算機應用研究，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]馮國棟，肖仰華．大圖的分布式存儲[J]．中國計算機學會通訊，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]．沈陽：遼寧大學，2014．

[23]苗又山．大規(guī)模動態(tài)演化圖的存儲與分析系統(tǒng)研究[D]．中國博士學位論文，中國科學技術(shù)大學，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．