1 基本概念

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

2 術語解釋

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

無向圖：若頂點 Vi 到 Vj 之間的邊沒有方向，則稱這條邊為無向邊（ Edge ），用序偶對 (Vi,Vj) 標示。

有向圖：若從頂點 Vi 到 Vj 的邊是有方向的，則成這條邊為有向邊，也稱為弧（ Arc ）。用有序對（ Vi ， Vj ）標示， Vi 稱為弧尾， Vj 稱為弧頭。如果任意兩條邊之間都是有向的，則稱該圖為有向圖。

權（ Weight ）：有些圖的邊和弧有相關的數，這個數叫做權（ Weight ）。這些帶權的圖通常稱為網（ Network ）。

圖計算：圖的分佈式或者並行處理其實是把圖拆分成很多的子圖，然後分別對這些子圖進行計算，計算的時候可以分別迭代進行分階段的計算，即對圖進行並行計算

3 詳細說明

3.1 GraphX 框架

設計 GraphX 時，點分割和 GAS 都已成熟，在設計和編碼中針對它們進行了優化，並在功能和性能之間尋找最佳的平衡點。如同 Spark 本身，每個子模塊都有一個核心抽象。 GraphX 的核心抽象是 Resilient Distributed Property Graph ，一種點和邊都帶屬性的有向多重圖。它擴展了 Spark RDD 的抽象，有 Table 和 Graph 兩種視圖，而只需要一份物理存儲。兩種視圖都有自己獨有的操作符，從而獲得了靈活操作和執行效率。

如同 Spark ， GraphX 的代碼非常簡潔。 GraphX 的核心代碼只有 3 千多行，而在此之上實現的 Pregel 模式，只要短短的 20 多行。 GraphX 的代碼結構整體下圖所示，其中大部分的實現，都是圍繞 Partition 的優化進行的。這在某種程度上說明了點分割的存儲和相應的計算優化，的確是圖計算框架的重點和難點。

3.2 GraphX 實現分析

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

GraphX 的底層設計有以下幾個關鍵點。

對 Graph 視圖的所有操作，最終都會轉換成其關聯的 Table 視圖的 RDD 操作來完成。這樣對一個圖的計算，最終在邏輯上，等價於一系列 RDD 的轉換過程。因此， Graph 最終具備了 RDD 的 3 個關鍵特性： Immutable 、 Distributed 和 Fault-Tolerant ，其中最關鍵的是 Immutable （不變性）。邏輯上，所有圖的轉換和操作都產生了一個新圖；物理上， GraphX 會有一定程度的不變頂點和邊的複用優化，對用戶透明。

兩種視圖底層共用的物理數據，由 RDD[Vertex-Partition] 和 RDD[EdgePartition] 這兩個 RDD 組成。點和邊實際都不是以表 Collection[tuple] 的形式存儲的，而是由 VertexPartition/EdgePartition 在內部存儲一個帶索引結構的分片數據塊，以加速不同視圖下的遍歷速度。不變的索引結構在 RDD 轉換過程中是共用的，降低了計算和存儲開銷。

圖的分佈式存儲採用點分割模式，而且使用 partitionBy 方法，由用戶指定不同的劃分策略（ PartitionStrategy ）。劃分策略會將邊分配到各個 EdgePartition ，頂點 Master 分配到各個 VertexPartition ， EdgePartition 也會緩存本地邊關聯點的 Ghost 副本。劃分策略的不同會影響到所需要緩存的 Ghost 副本數量，以及每個 EdgePartition 分配的邊的均衡程度，需要根據圖的結構特徵選取最佳策略。目前有 EdgePartition2d 、 EdgePartition1d 、 RandomVertexCut 和 CanonicalRandomVertexCut 這四種策略。