CAP＠NTU 大規模圖計算系統研究進展

CAP@NTU 大規模圖計算系統研究進展

孫鵬 I 文

摘要

「圖」是以「圖論」為基礎的對現實世界的一種抽象表達，「圖計算」則是在這種數據結構上的計算模式。相比於Hadoop、Spark這種大數據處理平台，或者TensorFlow之類的機器學習系統，許多人對圖計算系統還比較陌生。本文首先討論了當前圖計算系統的現狀，然後介紹CAP組在該領域的研究進展。

圖與圖計算

圖 (Graph) 是表示對象與對象之間的關係的數據結構。我們通常使用頂點 (Vertex) 集和邊 (Edge) 集描述一個圖：頂點表示對象，邊表示對象之間的關係。圖1展示了一個簡單的圖：它包含了5個頂點和8條邊。在這個例子中，01表示一條邊，其中0和2分別是這條邊的源點和終點。

圖1：一個簡單的圖

圖形無處不在。在社交媒體、廣告推薦、搜索引擎等場景中，我們可以把人、產品、興趣之間的關係用圖來表示，並且利用圖計算技術從中挖掘出有效信息。比如，在社交網路中識別出有影響力的人 (如圖2所示)、在電商平台中尋找廣告的投放用戶、在金融系統中進行反欺詐。

圖2：社交網路構抽象成一個大規模的圖

在實際問題中，我們面臨的圖都有相同的特點：規模超大，常常達到數億的頂點和上百億的邊。比如，ClueWeb12數據集包含1億節點、425億邊。在大規模圖上進行高效的計算面臨著巨大的挑戰。大規模圖計算在工業界和學術界中是非常熱門的話題。蘋果在2016年以2億美元的價格收購創業公司Turi，而Turi則是由圖計算領域有名的GraphLab [1] 項目孵化而來。2017年TigerGraph 完成 3100 萬美元 A 輪融資。TigerGraph的核心技術包含了一個完整的、分散式的並行圖計算平台，能夠支持網路規模數據的實時分析，其客戶包括支付寶、VISA、軟銀等知名金融公司。

當前的圖計算系統研究現狀

圖計算的特性包括：

· 由於圖數據中頂點之間依賴性強，分散式計算模式需要在各個機器之間頻繁進行數據交換；

· 由於圖數據中頂點的連接關係不規則（如圖3所示，1%的頂點可能佔了整個圖50%的邊），分散式計算模式需要特殊的負載平衡機制；

· 圖演算法（例如PageRank）需要多次迭代計算完成。

圖 3：在該圖中，1%的頂點佔了整個圖50%的邊

因此，許多面向圖計算的專有系統湧現出來，其中的代表之一就是Google於2012年提出的Pregel [2]。Google曾稱其20%的數據處理是使用Pregel進行的。

在下文中我們以數據置放和計算模式為標準，將流行的圖計算系統分為四類（如圖4所示）。

圖4：當前圖計算系統分類

從數據置放角度來看，現有的圖計算系統可分為基於內存 (In-Memory)的系統和基於磁碟 (Out-of-Core) 的系統。其中，基於內存的系統需要在計算過程中將所有的頂點、邊和中間數據保存在內存中，以最小化數據讀寫開銷。然而，在計算和存儲資源的約束下，常規伺服器和集群的內存無法存儲所有數據。因此，基於內存的系統能夠處理的圖規模往往十分有限。為了解決這一問題，基於磁碟的系統通常對圖數據進行分片，並存儲在磁碟中。在每輪迭代中，計算節點按照三個步驟依次處理每個數據分片：

· 從磁碟上讀入該數據分片；

· 在該數據分片運行圖演算法；

· 將更新後的數據分片或將中間結果寫回磁碟。

儘管基於磁碟的圖計算系統可在常規伺服器或集群上有效處理大規模圖數據，但其高昂的I/O開銷會嚴重降低其計算性能。

從計算模式來看，現有的圖計算方案可分為單機系統和分散式系統。其中，基於內存的分散式圖計算系統可以處理10億頂點規模的圖數據。然而，這些方案往往需要大規模集群（例如上百台高性能伺服器和昂貴的高速網路連接）。相比之下，基於磁碟的單機圖計算系統可以提供廉價且有競爭力的數據處理能力。以VENUS [3] 為例，在一個15億條邊的圖上運行PageRank，一個包含50台伺服器（共100 CPU）的Spark集群需要8.1分鐘，而VENUS只需要1台伺服器（8 CPU）和5分鐘。這也證明了Hadoop、Spark等通用大數據平台並不適合圖計算。

CAP@NTU 組在圖計算系統的研究進展

CAP@NTU小組從2015年開始進行圖計算系統的研究，並取得了一定的技術突破。

如上表所示，面向傳統的靜態圖計算任務，我們開發了單機圖計算系統（GraphMP）與兩代分散式圖計算系統（GraphH、GraphPS）。面向實時圖計算任務，我們正在開發一個分散式流式圖計算系統GraphStream。全部系統開源於https://github.com/cap-ntu。

與現有的系統相比，我們選擇的突破點是如何有效地管理大規模圖計算系統的內存資源，並且解決了兩個核心問題：

· 當伺服器或集群的內存資源足以容納圖計算任務中全部的頂點、邊、和中間數據時，GraphMP、GraphH、GraphPS能夠自適應進入內存計算狀態，並且計算性能能匹配現有的單機、分散式內存計算系統（如GraphMat、Pregel）。

· 當伺服器或集群的內存資源不足以管理全部的頂點、邊、和中間數據時，GraphMP、GraphH、GraphPS能進入磁碟計算狀態，並且能通過緩存技術最大化內存資源利用率，有效降低磁碟I/O開銷，使其計算性能比傳統的基於磁碟的系統（如GraphChi、Chaos）有上百倍的提升。

圖5：GraphH與GraphPS的系統架構

如圖5所示，GraphH與GraphPS是GraphMP的分散式版本。在每台伺服器上，一個核心部件是 Edge Cache。通過它，GraphMP，GraphH和GraphPS能夠自適應改變其計算模式，並降低磁碟I/O。為了進一步降低磁碟I/O開銷，Edge Cache採取了自適應壓縮緩存策略：將圖數據中的靜態數據採用不同的壓縮演算法降低其數據大小，將壓縮後的數據緩存，並在使用時解壓縮。

如上表所示，在使用了zlib-3壓縮演算法後，包含近100 億邊的EU-2015數據大小僅為62GB。儘管在計算中系統需要額外的解壓縮時間，這種額外的計算開銷遠小於昂貴的磁碟I/O開銷。在Edge Cache中，我們通過歷史數據進行計算，使系統能夠選取最合適的壓縮演算法，在最小化磁碟I/O開銷的同時，降低解壓縮的計算開銷。

另外值得注意的是，GraphPS（如圖6所示）是根據參數伺服器（Parameter Server）架構設計的。了解大規模機器學習的同學可能了解，當前火熱的深度學習平台（如TensorFlow）的分散式實現很多都採用了參數伺服器架構。根據這種架構，我們設計了 GraphPS作為CAP@NTU的第二代分散式圖計算系統，並在處理性能上得到了提升。更長遠的影響是：分散式深度學習與分散式圖計算可以由一個架構完成，那麼未來這兩個大數據處理任務有可能會有一個系統統一完成。

圖6：GraphPS架構

CAP@NTU 組在圖計算系統研究的未來工作

在2018年，CAP@NTU組將會著重於GraphStream的設計與開發。與傳統的靜態圖計算系統相比，流式圖計算面臨著更多的挑戰：

· 流式計算的負載均衡；

· 增量計算模式在流數據上匹配；

· 結果準確性與延時的平衡。

GraphStream將基於Apache Flink開發，並解決以上問題。

參考文獻

[1] Low Yucheng, Danny Bickson, Joseph Gonzalez, Carlos Guestrin, Aapo Kyrola, and Joseph M. Hellerstein. "Distributed GraphLab: a framework for machine learning and data mining in the cloud." Proceedings of the VLDB Endowment 5, no. 8 (2012): 716-727.

[2] Malewicz, Grzegorz, Matthew H. Austern, Aart JC Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. "Pregel: a system for large-scale graph processing." In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pp. 135-146. ACM, 2010.

[3] Cheng, Jiefeng, Qin Liu, Zhenguo Li, Wei Fan, John CS Lui, and Cheng He. "VENUS: Vertex-centric streamlined graph computation on a single PC." In Data Engineering (ICDE), 2015 IEEE 31st International Conference on, pp. 1131-1142. IEEE, 2015.

[4] Sun Peng, Yonggang Wen, Ta Nguyen Binh Duong, and Xiaokui Xiao. "GraphMP: An Efficient Semi-External-Memory Big Graph Processing System on a Single Machine." arXiv preprint arXiv:1707.02557 (2017).

[5] Sun Peng, Yonggang Wen, Ta Nguyen Binh Duong, and Xiaokui Xiao."GraphH: High Performance Big Graph Analytics in Small Clusters." arXiv preprint arXiv:1705.05595 (2017).

本文版權歸作者所有。

新加坡南洋理工CAP組

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！