圖處理系統綜述

08-16

圖處理系統綜述

來自專欄圖計算7 人贊了文章

1.BackGround

現有的圖數據可以分為以下三個方面。分別是社交媒體圖，廣告圖和Web圖。社交媒體圖主要包括微博、Twitter、FaceBook。人與人之間的關係也是一種圖結構，微博點贊也是一種圖結構。然後就是廣告圖以及Web圖結構。

隨著時間的推移，圖結構數據成幾何的指數增長，目前的圖結構已經達到TB級別的數據量。這麼大的數據量，如何對這麼巨大的圖數據進行高效的處理成為一個巨大的挑戰。

圖(Graph)是由頂點的有窮非空集合和頂點之間邊的集合組成，表示為G(V, E)。其中G表示一個圖，V是圖G中頂點的集合Vertices，E是圖G中邊的集合Edges。

大規模圖數據的特徵：

數據：大規模圖數據普遍存在的問題就是：數據量規模大（億級圖）
冪律圖：頂點的度數分配不均勻。高度頂點較多，低度頂點較少

圖計算中主要的系統有OSDI12 PowerGraph、OSDI12 GraphChi、OSDI14 GraphX、PPOPP15 Polymer、OSDI16 Gemin等等。

2. 圖處理系統

圖處理系統最初是並行單機圖處理系統，隨著圖數據規模的不斷增加。圖處理系統引出了這四個維度進行圖計算加速，第一個維度就是分散式圖處理系統：利用集群資源對圖計算進行並行加速，這個維度圖處理系統最大的瓶頸就是網路通信。第二個維度就是核外圖處理系統：利用外部存儲磁碟和內存進行不斷地交互，解決內存裝不下整個圖數據的問題。這個維度的圖處理系統最大的瓶頸問題就是磁碟空間大小。第三個維度就是NUMA-aware架構的圖處理系統：利用新型NUMA架構加速圖計算的過程，每個NUMA 節點都有自己的核以及內存。這個維度圖處理系統最大的問題就是圖很難被分區。最後一個維度就是新型硬體加速的圖處理系統：利用新型硬體加速圖處理的過程，這個新型硬體可以有GPU加速、RDMA加速、PIM 指令集卸載。下面我們重點介紹分散式圖處理系統。

3.分散式圖處理系統

筆者認為分散式圖處理系統主要可以分為以下三個方面。第一是基於MapReduce的大圖處理系統，利用MapReduce任務加速圖計算，最典型的就是GraphX。第二個就是基於Message Passing（消息通信）的大圖處理系統，其中最典型的就是Pregel 基於BSP的大圖處理系統，比如Pregelix和Pregel。第三個就是基於Shared Memory（共享內存）的大圖處理系統。其中包括PowerGraph和PowerLyra以及PowerSwitch 之前的文章中提到過。

4. Out of Core圖處理系統

此類圖計算系統單機運行，但是將存儲層次由RAM拓展到外部存儲器如SSD，Flash，SAS，HDD等，使其所能處理的圖規模增大。但受限於單機計算能力和核外存儲系統的數據交換的帶寬限制也無法在可接受的情形下處理超大規模的圖數據。典型的圖計算系統有 GraphChi[12], TurboGraph[13], X-Stream[14], PathGraph[15],GridGraph[16]和FlashGraph[17]。

這些系統在最大化磁碟順序讀寫，選擇調度和同非同步計算模式等方面做出了重要探索。TurboGraph和FlashGraph主要採用分頁方式分割圖來提高內外存的數據交換性能。其中GraphChi採用了傳統的以頂點為中心的編程模型，計算模式為隱式GAS。它使用了名為shard的核外數據結構來存儲邊，而將頂點劃分為多個連續的區間。提出了一種基於並行滑動窗口（PSW）模型達到對存儲在磁碟上的圖數據最大的順序讀寫性能。但是構建shard是需要對邊按源頂點排序，這樣耗費了大量的預處理時間，PWS對計算密集型的演算法更有利。另外在構建子圖時出現大量的隨機訪存現象，通過順序地更新子圖內有共享邊頂點來避免數據爭用問題。

X-Stream則介紹了一種以邊為中心的編程模型。在scatter階段以流的形式處理每條邊和產生傳播頂點狀態更新集，在gather階段它以流的形式處理每一個更新並應用到對應的頂點上。自然圖中頂點集遠遠大於邊集，所以X-Stream把頂點存儲在高速存儲設備（Cache對於RAM，RAM對於SSD/Disk）中表現為隨機讀寫，把邊集和更新集存於低速存儲設備中表現為最大程度的順序讀寫。X-Stream流式訪問圖數據，其流劃分相比於GraphChi無需對shard內的邊進行排序大大縮短了預處理時間，並使用work-stealing避免Scatter-Gather導致的線程間負載不均衡的問題。但是X-Stream在計算過程中，每輪迭代產生的更新集非常龐大，接近於邊的數量級；而且需要對更新集中的邊進行shuffle操作；缺乏選擇調度機制，產生了大量的無用計算。

GridGraph將頂點劃分為P個頂點數量相等的chunk，將邊放置在以P*P的網格中的每一個block中，邊源頂點所在的chunk決定其在網格中的行，邊目的頂點所在的chunk決定其在網格中的列。它對Cache/RAM/Disk進行了兩層級的網格劃分，採用了Stream vertices andedges的圖編程模型。計算過程中的雙滑動窗口（DualSliding Windows）大大減少了I/O開銷，特別是寫開銷。以block為單位進行選擇調度，使用原子操作對保證線程安全的方式更新頂點，消除了X-Stream的更新集和shuffle階段。其折線式的邊block遍歷策略不能達到最大化的Cache/Memory命中率。