分佈式圖計算框架GraphX

簡介

Spark GraphX是一個分佈式圖處理框架，它是基於Spark平臺提供對圖計算和圖挖掘簡潔易用的而豐富的接口，極大的方便了對分佈式圖處理的需求。

GraphX的框架

GraphX的核心抽象是Resilient Distributed Property Graph，一種點和邊都帶屬性的有向多重圖。它擴展了Spark RDD的抽象，有Table和Graph兩種視圖，而只需要一份物理存儲。兩種視圖都有自己獨有的操作符，從而獲得了靈活操作和執行效率。

圖存儲模式

邊分割（Edge-Cut）：每個頂點都存儲一次，但有的邊會被打斷分到兩臺機器上。這樣做的好處是節省存儲空間；壞處是對圖進行基於邊的計算時，對於一條兩個頂點被分到不同機器上的邊來說，要跨機器通信傳輸數據，內網通信流量大。

點分割（Vertex-Cut）：每條邊只存儲一次，都只會出現在一臺機器上。鄰居多的點會被複制到多臺機器上，增加了存儲開銷，同時會引發數據同步問題。好處是可以大幅減少內網通信量。

GraphX RDD存儲Graphx借鑑PowerGraph，使用的是Vertex-Cut(點分割)方式存儲圖，用三個RDD存儲圖數據信息：

VertexTable(id, data)：id為Vertex id，data為Edge data

EdgeTable(pid, src, dst, data)：pid為Partion id，src為原定點id，dst為目的頂點id

RoutingTable(id, pid)：id為Vertex id，pid為Partion id

點分割存儲實現如下圖所示：

圖計算模式

目前基於圖的並行計算框架已經有很多，比如來自Google的Pregel、來自Apache開源的圖計算框架Giraph/HAMA以及最為著名的GraphLab，其中Pregel、HAMA和Giraph都是非常類似的，都是基於BSP（Bulk Synchronous Parallell）模式。

BulkSynchronous Parallell，即整體同步並行，它將計算分成一系列的超步（superstep）的迭代（iteration）。從縱向上看，它是一個串行模式，而從橫向上看，它是一個並行的模式，每兩個superstep之間設置一個柵欄（barrier），即整體同步點，確定所有並行的計算都完成後再啟動下一輪superstep。

每一個超步（superstep）包含三部分內容：

1.計算compute：每一個processor利用上一個superstep傳過來的消息和本地的數據進行本地計算；

2.消息傳遞：每一個processor計算完畢後，將消息傳遞個與之關聯的其它processors

3.整體同步點：用於整體同步，確定所有的計算和消息傳遞都進行完畢後，進入下一個superstep。