大圖分布式存儲關鍵技術淺析

辛剛

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

1 研究背景及挑戰

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

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

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

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

基于此，大規模動態演化圖的分布式存儲技術需要解決如下兩個難點問題：圖的分割問題和圖演化歷史的重現問題。

2 國內外研究現狀

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

2.1 圖分割

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

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

適用于大圖分割的算法大多屬于啟發式算法，比如，Kernighan和Lin提出的啟發式交換點對的KL算法[16]，以及對KL算法改進的FM算法[17]。基于啟發式交換算法所能處理的圖的頂點數量一般在104以內。為了處理更大規模的圖，基于多層次框架的算法被提出，比如Kumar等人提出的METIS算法[18]，其基本思想是通過粗糙化技術將大圖縮減到可接受的小圖，而后在小圖上執行分割，最后再利用反粗糙化技術將小圖上的分割還原成原圖上的分割。基于多層次框架的算法能夠處理百萬規模左右的圖。

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

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

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

2.2 圖歷史查詢

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

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

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

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

2.3 其它方面

除圖分割和圖歷史重現兩個問題之外，容錯問題也是大規模動態演化圖分布式存儲系統必須解決的基本問題。目前主要沿用傳統分布式文件存儲系統中的容錯方法，即將圖存儲系統中的各類數據（含最新大圖數據、快照數據和日志數據）統統看作普通數據進行多副本存儲[24]。快照和日志數據自身所具有的容錯性沒有被有效用于容錯算法的優化。

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

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

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

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

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

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

參考文獻:

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

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

[3]施佺，肖仰華，魯軼奇，陳垚亮，王恒山．基于K2樹的大圖存儲優化研究[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]單曉歡．大規模演化圖的分割技術研究[D]．沈陽：遼寧大學，2014．

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