共計 9556 個字符，預計需要花費 24 分鐘才能閱讀完成。
本篇內容介紹了“Spark GraphX 怎么使用”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓丸趣 TV 小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！
GraphX 簡介
在 Spark 年幼的時候，0.5 版本就已經帶了一個 Bagel 小模塊，提供了類似 Pregel 的功能，當然，這個版本還非常的原始，性能和功能都比較弱，屬于實驗型產品。到 0.8 版本的時候，鑒于業界對分布式圖計算的需求日益見漲，Spark 開始獨立一個分支：Graphx-Branch，做為獨立的圖計算模塊，借鑒 GraphLab，開始設計開發 GraphX。在 0.9 版本中，這個模塊被正式集成到主干，雖然是 alpha 版本，但是已經可以開始進行試用，小面包圈 Bagel 告別舞臺。1.0 版本，GraphX 正式投入生產使用。
值得留意的是，GraphX 目前依然處于快速發展中，從 0.8 的分支，到 0.9 和 1.0，每個版本代碼都有不少的改進和重構，并根據觀察，在沒有改任何代碼邏輯和運行環境，只是升級版本，切換接口和重新編譯的情況下，每個版本能夠有 10-20% 的性能提升。雖然和 GraphLab 的性能還有一定的差距，但是憑借著 Spark 整體的一體化流水線處理，社區熱烈的活躍度以及快速改進速度，使得它具有強大的競爭力。
分布式圖計算
在正式介紹 GraphX 之前，先看看通用的分布式圖計算框架。簡單來說，分布式圖計算框架的目的，就是將對于巨型圖的各種操作，包裝為簡單的接口，讓分布式存儲，并行計算等復雜問題對上層透明。從而使得復雜網絡和圖算法的工程師，可以更加聚焦在圖相關的模型設計和使用上，而不用關心底層的分布式細節。為了實現該目的，需要解決兩個通用的問題。
1. 圖存儲模式
巨型圖的存儲總體上有邊分割和點分割兩種存儲方式。2013 年 GraphLab2.0 推出，將其存儲方式由邊分割變為點分割，在性能上取得重大提升，目前基本上被業界廣泛接受并使用。
邊分割（Edge Cut）
每個頂點都存儲一次，但是有的邊會被打斷，被分到了兩臺機器上。這樣做的好處是節省存儲空間，壞處是對于圖進行基于邊的計算時，對于一條兩個頂點被分到不同機器上的邊來說，要跨機器通信傳輸數據，內網通信流量大。
點分割（Vertex Cut）
每個邊都只存儲一次，都只會出現在一臺機器上。鄰居多的點會被復制到多臺機器上，增加存儲開銷，同時會引發數據同步的問題。好處是可以大幅減少內網通信量可以大大降低。
原本兩種方法互有利弊，但現在是點分割占上風，各種分布式圖計算框架，都把自己底層的存儲形式變成了點分割。主要原因有 2 個：
磁盤的價格下降，存儲空間不是問題了，但是內網的通信資源沒有突破性進展，集群計算時內網帶寬是寶貴的，時間比磁盤更珍貴，這點就類似于常見的空間換時間的策略。
在當前的應用場景中，絕大多數網絡都是“無尺度網絡”，遵循冪律分布，不同點的鄰居數量非常懸殊，邊分割會使得那些多鄰居的點所相連的邊大多數都會被分到不同的機器上，這樣的數據分布會使得內網帶寬更加捉襟見肘，于是邊分割的存儲方式就被漸漸拋棄了
2. 圖計算模型
目前的圖計算框架，基本上都是遵循 BSP 計算模式。BSP 全稱 Bulk Synchronous Parallell，由哈佛大學 Leslie Valiant 和牛津大學 Bill McColl 提出。在 BSP 中，一次計算過程由一系列全局超步組成，每一個超步由并發計算，通訊，柵欄同步三個步驟組成。同步完成，標志著該一個超步的完成，以及下一個超步的開始。
BSP 模式很簡潔，基于 BSP 模式，目前有 2 種比較成熟的圖計算模型：
Pregel 模型——“像頂點一樣思考”
2010 年，Google 的新的三架馬車 Caffeine、Pregel、Dremel 發布。伴隨著 Pregel，BSP 模型被廣為人知。據說 Pregel 的名字是為了紀念歐拉的七橋問題，那七座橋所在的河流，就是叫 Pregel。
Pregel 借鑒 MapReduce 的思想，提出了 像頂點一樣思考（Think Like A Vertex）的圖計算模式，讓用戶無需考慮并行分布式計算的細節，只需要實現一個頂點更新函數，讓框架在遍歷頂點時進行調用即可。
常見的代碼模板如下所示：
void Compute(MessageIterator* msgs) {
// 遍歷由頂點入邊傳入的消息列表
for (; !msgs- Done(); msgs- Next())
doSomething()
// 生成新的頂點值
*MutableVertexValue() = ...
// 生成沿頂點出邊發送的消息
SendMessageToAllNeighbors(...);
}
這個模型雖然簡潔，但是很容易發現它的缺陷。對于鄰居數很多的頂點，它需要處理的消息非常龐大，而在這個模式下，它們是無法被并發處理的。所以對于符合冪律分布的自然圖，這種計算模型下，很容易發生假死或者崩潰。
GAS 模型——鄰居更新模型
相比于 Pregel 模型的消息通信范式，GraphLab 的 GAS 模型更偏向共享內存風格。它允許用戶的自定義函數訪問當前頂點的整個鄰域，可以抽象成 Gather，Apply，Scatter 這三個階段，常被簡稱為 GAS。相應用戶需要實現的三個獨立的函數：gather、apply 和 scatter。
常見的代碼模板如下所示：
// 從鄰居點和邊收集數據
Message gather(Vertex u, Edge uv, Vertex v) {
Message msg = ...
return msg
}
// 匯總函數
Message sum(Message left, Message right) {
return left+right
}
// 更新頂點 Master
void apply(Vertex u, Message sum) {
u.value = ...
}
// 更新鄰邊和鄰居點
void scatter(Vertex u, Edge uv, Vertex v) {
uv.value = ...
if ((|u.delta| ε) Active(v)
}
由于 gather/scatter 函數是以單條邊為操作粒度，那么對于一個頂點的眾多鄰邊，可以分別由相應的 worker 獨立地調用 gather/scatter 函數。這一設計主要是為了適應點分割的圖存儲模式，從而避免 Pregel 模型會遇到的問題。
GraphX 的框架
在 GraphX 設計的時候，點分割和 GAS 都已經成熟了，所以 GraphX 一開始就站在了巨人的肩膀上，并在設計和編碼中，針對這些問題進行了優化，在功能和性能之間尋找最佳的平衡點。
每個 Spark 子模塊，如同 Spark 本身一樣，都有一個核心的抽象。GraphX 的核心抽象是 Resilient Distributed Property Graph，一種點和邊都帶屬性的有向多重圖。它擴展了 Spark RDD 的抽象，擁有 Table 和 Graph 兩種視圖，而只需要一份物理存儲。而兩種視圖都有自己的獨有的操作符，從而獲得靈活操作和執行效率。
如同 Spark 一樣，GraphX 的代碼依然非常簡潔。核心的 GraphX 代碼只有 3 千多行，而在此之上實現的 Pregel 模型，只要短短的二十多行。GraphX 的代碼結構整體如下：
整體還是很清晰明了，其中大部分的 impl 包的實現，都是圍繞著 Partition 而優化和進行。這種某種程度上說明了，點分割的存儲和相應的計算優化，的確是圖計算框架的重點和難點。
GraphX 的設計要點
GraphX 的底層設計有幾個關鍵點
對 Graph 視圖的所有操作，最終都會被轉換成其關聯的 Table 視圖的 RDD 操作來完成。這樣對一個圖的計算，最終在邏輯上，等價于一系列 RDD 的轉換過程。因此，其實 Graph 最終是具備了的 RDD 的 3 個關鍵特性：Immutable，Distributed，Fault-Tolerant。其中最關鍵的是不可變（Immutable）性，所有圖的轉換和操作，邏輯上都是產生了一個新圖，物理上，Graphx 會有一定程度的不變頂點和邊的復用優化，對用戶透明。
兩種視圖底層共用的物理數據，由 RDD[VertexPartition] 和 RDD[EdgePartition] 這兩個 RDD 組成。點和邊實際都不是以表 Collection[tuple] 的形式存儲的，而是由 VertexPartition/EdgePartition，在內部存儲一個帶索引結構的分片數據塊，以加速不同視圖下的遍歷速度。不變的索引結構在 RDD 轉換過程中是共用的，降低了計算和存儲開銷。
圖的分布式存儲采用點分割模式，而且使用 partitionBy 方法，由用戶指定不同的劃分策略（PartitionStrategy）。劃分策略會將邊分配到各個 EdgePartition，頂點 Master 分配到各個 VertexPartition，EdgePartition 也會緩存本地邊的關聯點的 Ghost 副本。劃分策略的不同會影響到所需要緩存的 Ghost 副本數量，以及每個 EdgePartition 分配的邊的均衡程度，需要根據圖的結構特征進行選取最佳的 Strategy。目前有 EdgePartition2d，EdgePartition1d，RandomVertexCut，CanonicalRandomVertexCut 這 4 種策略。目前試驗的結果，在淘寶大部分場景下，EdgePartition2d 效果最好。
GraphX 的圖運算符
如同 Spark 一樣，GraphX 的 Graph 類，提供了豐富的圖運算符，大致結構如下：
具體每個方法的說明和用法，可以在官方的 GraphX Programming Guide 找到每個函數的詳細說明，就不一一列舉。重點講幾個需要注意的方法：
圖的 cache
由于一個圖，是由 3 個 RDD 組成的，所以會占用更多的內存。相應圖的 cache，unpersist 和 checkpoint，更需要留意使用技巧。出于最大限度的復用邊的理念，GraphX 的默認接口，只提供了 unpersistVertices 的方法，如果要釋放邊，需要自己調用 g.edges.unpersist() 方法才能釋放，這個給用戶帶來了一定的不便，但是卻給 GraphX 的優化，提供便利和空間。
參考 Graphx 的 Pregel 代碼，對一個大圖，目前最佳的實踐是：
var g=...
var prevG: Graph[VD, ED] = null
while(...){
prevG = g
g = g.(………………)
g.cache()
prevG.unpersistVertices(blocking=false)
prevG.edges.unpersist(blocking=false)
}
大體之意，就是根據 GraphX 中 graph 的不變性，對 g 做了操作并賦回給 g 之后，g 已經不是原來的 g 了，而且會在下一輪迭代使用，所以必須 cache。另外，你必須先用 prevG，保留住對原來的圖的引用，并在新圖產生之后，快速的將舊圖徹底的釋放掉。否則一個大圖，幾輪迭代下來，就會有內存泄漏的問題，很快耗光作業內存。
mrTriplet——鄰邊聚合
mrTriplets 的全稱是 mapReduceTriplets，它是 GraphX 中最核心和強大的一個接口。Pregel 也基于它而來，所以對它的優化，能很大程度上影響整個 GraphX 的性能。
mrTriplets 運算符的簡化定義是：
def mapReduceTriplets[A](
map: EdgeTriplet[VD, ED] = Iterator[(VertexId, A)],
reduce: (A, A) = A)
: VertexRDD[A]
它的計算過程如下：
map：應用于每一個 triplet 上，生成一個或者多個消息，消息以 triplet 關聯的兩個頂點中的任意一個或兩個為目標頂點
reduce：應用于每一個 Vertex 上，把發送給每一個頂點的消息合并起來
mrTriplets 最后返回的是一個 VertexRDD[A]，它包含了每一個頂點聚合之后的消息（類型為 A），沒有接收到消息的頂點不會包含在返回的 VertexRDD 中。
在最近的版本，GraphX 針對它進行了如下幾個優化，這些優化，對于 Pregel 以及所有上層算法工具包的性能，都有著重大的影響。其中包括：
Caching for Iterative mrTriplets Incremental Updates for Iterative mrTriplets
在很多圖分析算法中，不同點的收斂速度變化很大。在迭代的后期，只有很少的點會有更新。因此對于沒有更新的點，下一次 mrTriplets 計算時 EdgeRDD 無需更新相應點值的本地緩存，能夠大幅降低通信開銷。
Indexing Active Edges
沒有更新的頂點在下一輪迭代時就不需要向鄰居重新發送消息。因此 mrTriplets 遍歷邊時，如果一條邊的鄰居點值在上一輪迭代時沒有更新，可以直接跳過，避免了大量無用的計算和通信。
Join Elimination
一個 triplet 是由一條邊和其兩個鄰居點組成的三元組，操作 triplet 的 map 函數常常只需訪問其兩個鄰居點值中的一個。例如在 PageRank 計算中，一個點值的更新只和其源頂點的值有關，而其所指向的目的頂點的值無關。那么在 mrTriplets 計算中，就不需要 VertexRDD 和 EdgeRDD 的 3 -way join，而只需要 2 -way join。
所有的這些優化，都使得 GraphX 的性能，逐漸逼近 GraphLab。雖然還有一定的差距，但是一體化的流水線服務，和豐富的編程接口，可以彌補性能的稍微差距。
進化的 Pregel 計算模型
Graphx 中的 Pregel 接口，并不嚴格遵循 Pregel 的模型，它是一個參考 GAS 改進的 Pregel 模型。定義如下：
def pregel[A](initialMsg: A, maxIterations: Int, activeDirection: EdgeDirection)(
vprog: (VertexID, VD, A) = VD,
sendMsg: EdgeTriplet[VD, ED] = Iterator[(VertexID,A)],
mergeMsg: (A, A) = A)
: Graph[VD, ED]
這種基于 mrTrilets 方法的 Pregel 模型，和標準的 Pregel 的最大區別是，它的第 2 段參數體，接受的是 3 個函數參數，而不接受 messageList。它不會在單個頂點上進行消息遍歷，而是會將頂點的多個 ghost 副本收到的消息聚合后，發送給 master 副本，再使用 vprog 函數來更新點值。消息的接收和發送，都是被自動并行化處理的，無需擔心超級節點的問題。
常見的代碼模板如下所示：
// 更新頂點
vprog(vid: Long, vert: Vertex, msg: Double): Vertex = {
v.score = msg + (1 - ALPHA) * v.weight
}
// 發送消息
sendMsg(edgeTriplet: EdgeTriplet[…]): Iterator[(Long, Double)]
(destId, ALPHA * edgeTriplet.srcAttr.score * edgeTriplet.attr.weight)
}
// 合并消息
mergeMsg(v1: Double, v2: Double): Double = {
v1+v2
}
可以看到，GraphX 設計這個模型的用意。它綜合了 Pregel 和 GAS 兩者的優點，即接口相對簡單，又保證性能，可以應對點分割的圖存儲模式，勝任符合冪律分布的自然圖的大型計算。另外值得注意的是，官方的 Pregel 版本是最簡單的一個版本，對于復雜的業務場景，根據這個版本擴展一個定制的 Pregel，是很常見的做法。
圖算法工具包
GraphX 也提供了一套圖算法，方便用戶對圖進行分析。目前最新版本，已經支持 PageRank，數三角形，最大連通圖，最短路徑等 6 種經典的圖算法，這些算法的代碼實現，目的和重點在于通用性。如果要獲得最佳性能，可以參考其實現，進行修改和擴展，可以滿足業務需求。另外研讀這些代碼，也是理解 GraphX 編程的 Best Practice 的好方法，建議有興趣深入研究分布式圖算法開發的同學都通讀一遍。
GraphX 在淘寶 1. 圖譜體檢平臺
基本上，所有的關系，都可以從圖的角度來看待和處理，但是到底一個關系的價值多大？健康與否？適合用于什么場景？很多時候是靠運營和產品憑感覺來判斷和評估。如何將各種圖的指標精細化，規范化，對于產品和運營的構思進行數據上的預研指導，提供科學決策的依據，是圖譜體檢平臺設計的初衷和出發點。
基于這樣的出發點, 借助 GraphX 豐富的接口和工具包, 針對淘寶內部林林總總的圖業務需求, 我們開發一個圖譜體檢平臺。目前主要進行下列指標的檢查：
度分布
度分布是一個圖最基礎的指標，也是非常重要的一個指標。度分布檢測的目的，主要是了解圖中 超級節點 的個數和規模，以及所有節點度的分布曲線。超級節點的存在，對各種傳播算法，都會有重大的影響，不論是正面助力還是反面的阻力，所以要預先對于這些數據量有個預估。借助 GraphX 的最基本的圖信息接口：degrees: VertexRDD[Int]，包括 inDegrees 和 outDegrees，這個指標可以輕松地計算出來，并進行各種各樣的統計。
二跳鄰居數
對于大部分社交關系來說，只獲得一跳的度分布是遠遠不夠的，另一個重要的指標是二跳鄰居數。例如秘密 App 中，好友的好友的秘密，傳播的范圍更廣，信息量更豐富。因此二跳鄰居數的統計，是圖譜體檢中很重要的一個指標。二跳鄰居的計算 GraphX 沒有給出現成的接口，需要自己設計和開發。目前使用的方法是：
第一次遍歷，所有點往鄰居點傳播一個帶自身 Id，生命值為 2 的消息
第二次遍歷，所有點將收到的消息，往鄰居點再轉發一次，生命值為 1
最終統計所有點上，接收到的生命值為 1 的 Id，并進行分組匯總，得到所有點的二跳鄰居
值得注意的是，進行這個計算之前，需要借助度分布，將圖中的超級節點去掉，不納入二跳鄰居數的計算。否則這些超級節點一來會出現在第一輪傳播后，收到過多的消息而爆掉，二來它們參與計算，會影響和它們有一跳鄰居關系的頂點，導致它們不能得到真正有效的二跳鄰居數。所以必須先篩選掉。
連通圖
檢測連通圖的目的，是弄清一個圖有幾個連通部分，以及每個連通部分有多少頂點。這樣可以將一個大圖分割為多個小圖，并去掉零碎的連通部分，從而可以在多個小子圖上，進行更加精細的操作。目前 GraphX 提供了 ConnectedComponents 和 StronglyConnectedComponents 算法，使用它們可以快速的計算出相應的連通圖。
連通圖可以進一步演化，變成社區發現算法，而該算法優劣的評判標準之一，是計算模塊的 Q 值，來查看所謂的 modularity 情況。但是 GraphX 中還是沒有對于 Q 值計算的函數，我們已經實現了一個，后續會將這個實現提交到社區。
更多的指標，例如 Triangle Count 和 K -Core，無論是借助 GraphX 已有的函數，還是自己從頭開發，都陸續在進行中。目前這個圖譜體檢平臺已經初具規模，通過平臺的建立和推廣，圖相關的產品和業務，逐漸走上“無數據，不討論，用指標來預估效果”的數據化運營之路，有效提高溝通效率，為各種圖相關的業務開發走上科學化和系統化之路做好準備。
2. 多圖合并工具
在圖譜體檢平臺的基礎上，我們可以了解到各種各樣關系的特點。不同的關系，都會有自己的強項和弱項，例如有些關系圖譜連通性好些，而有些關系圖譜的社交性好些，所以往往我們需要使用關系 A 來豐富關系 B。為此，在圖譜體檢平臺之上，借助 GraphX，我們開發了一個多圖合并工具，提供類似于圖的并集的概念，可以快速的對指定的 2 個不同關系圖譜，進行合并，產生一個新的關系圖譜。
以用基于 A 關系的圖來擴充基于 B 關系的圖，生成擴充圖 C 為例，融合算法基本思路如下：
若圖 B 中某邊的兩個頂點都在圖 A 中，則將該邊加入 C 圖 (如 BD 邊)
若圖 B 中某邊的一個頂點在圖 A 中，另外一個頂點不在，則將該邊和另一頂點都加上 (如 CE 邊和 E 點)
若圖 A 中某邊的兩個頂點都不在圖 B 中，則舍棄這條邊和頂點 (如 EF 邊)
使用 GraphX 的 outerJoinVertices 等圖運算符，可以很簡單地完成上述的操作。另外，在考慮圖合并的時候，也可以考慮給不同的圖的邊加上不同的權重，綜合考慮點之間的不同關系的重要性。新產生的圖，會再進行一輪圖譜體檢，通過前后三個圖各個體檢指標的對比，可以對于業務上線之后效果有個預估和判斷。如果不符合期望，可以嘗試重新選擇擴充方案。
3. 能量傳播模型
加權網絡上的能量傳播是經典的圖模型之一，可用于用戶信譽度預測。模型的思路是：物以類聚，人以群分。常和信譽度高的用戶進行交易的，信譽度自然較高，常和信譽度差的用戶有業務來往的，信譽度自然較低。模型不復雜，但淘寶全網有上億的用戶點和幾十億關系邊，要對如此規模的巨型圖進行能量傳播，并對邊的權重進行精細的調節，對圖計算框架的性能和功能都是巨大的考驗。借助 GraphX，我們在這兩點之間取得了平衡，成功實現了該模型。
流程如圖 4，先生成以用戶為點、買賣關系為邊的巨型圖 initGraph，對選出種子用戶，分別賦予相同的初始正負能量值 (TrustRank BadRank)，然后進行兩輪隨機游走，一輪好種子傳播正能量（tr），一輪壞種子傳播負能量（br），然后正負能量相減得到 finalRank，根據 finalRank 判斷用戶的好壞。邊的初始傳播強度是 0.85，這時 AUC 很低，需要再給每條邊，帶上一個由多個特征（交易次數，金額……）組成的組合權重。每個特征，都有不同的獨立權重和偏移量。通過使用 partialDerivativeAUC 方法，在訓練集上計算 AUC，然后對 AUC 求偏導，得到每個關系維度的獨立權重和偏移量，生成新的權重調節器（WeightAdjustor），對圖上所有邊上的權重更新，然后再進行新一輪大迭代，這樣一直到 AUC 穩定時，終止計算。
在接近全量的數據上進行 3 輪大迭代，每輪 2 + 6 次 Pregel，每次 Pregel 大約 30 次小迭代后，最終的 AUC 從 0.6 提升到 0.9，達到了不錯的用戶預測準確率。訓練時長在 6 個小時左右，無論在性能還是準確率上，都超越業務方的期望。
未來圖計算的前景
經過半年多的嘗試，對于 GraphX 可以勝任的圖計算的規模和性能，目前我們都已經心中有數。之前一些想做，但因為沒有足夠的計算能力而不能實現的圖模型，現已經不是問題。我們將會進一步將越來越多的圖模型，在 GraphX 上實現。
這些模型應用于用戶網絡的社區發現、用戶影響力、能量傳播、標簽傳播等，可以提升用戶粘性和活躍度；而應用到推薦領域的標簽推理，人群劃分、年齡段預測、商品交易時序跳轉，則可以提升推薦的豐富度和準確性。復雜網絡和圖計算的天地廣闊無垠，有更多的未知等待我們去探索和實踐，借助 Spark GraphX，未來我們可以迎接更大挑戰。
“Spark GraphX 怎么使用”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注丸趣 TV 網站，丸趣 TV 小編將為大家輸出更多高質量的實用文章！
