分布式圖計算如何實現(xiàn)？帶你一窺圖計算執(zhí)行計劃

2023-08-02 10:14 作者:GeaFlow 0人讀過 | 我要投稿

GeaFlow(品牌名TuGraph-Analytics) 已正式開源，歡迎大家關(guān)注?。?！歡迎給我們 Star 哦!

GitHub?? https://github.com/TuGraph-family/tugraph-analytics

更多精彩內(nèi)容，關(guān)注我們的博客 https://geaflow.github.io/

圖的遍歷

我們一般說的的圖算法是指在圖結(jié)構(gòu)上進行迭代計算的計算過程，例如有最短路徑算法、最小生成樹算法、PageRank算法等。這些算法往往用于解決圖上的特定一類問題。例如最短路徑算法主要用于尋找兩個節(jié)點之間的最短路徑，PageRank算法則可以給節(jié)點重要性排序。

然而，還有一類被廣泛使用的'圖算法'，它們也通過迭代計算處理，且在實際應用中有著廣泛的應用，如金融風險管理、社交網(wǎng)絡分析等。

它們就是圖遍歷，又被稱之為Traversal。圖Traversal解決遍歷圖中節(jié)點的問題，通過可控的順序訪問圖中節(jié)點和邊，以便對圖進行處理或收集信息。

一般的圖遍歷算法可以分為兩種主要類型：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）。手工實現(xiàn)算法只有既定的走圖遍歷模式，很難解決特定的圖查詢問題。

舉例來說，在這個簡單示例圖中，如果要查找所有的'人創(chuàng)建軟件'的模式，無論DFS還是BFS都需要實現(xiàn)復雜的計算邏輯，無法直觀取得結(jié)果。

因此，基于圖查詢中的多元化走圖需要，圖查詢語言自然產(chǎn)生。人們希望使用諸如 ?(:person)-[:created]->(:software) ?的描述來達成需求。

圖查詢語言GQL

主流的圖查詢語言有Gremlin和GQL等，其中Gremlin是直接命令式語言，每一個調(diào)用都明確地聲明了下一步走圖的方向。對于命令語言，查詢本身就是執(zhí)行計劃，計算機容易理解，但人類學習成本較高，理解困難。

GQL則是聲明式語言，簡單直觀，例如'(:person)-[:created]->(:software)'就表示了我們要查找人創(chuàng)建軟件的模式。'Return person.name, software.name;'就可以立即獲得作者和軟件的名稱，大大降低了人理解語言的成本，學習成本接近于零。

然而聲明式語言的缺點是描述不直接反應計算機執(zhí)行的過程，因此需要執(zhí)行平臺將其'翻譯'為計算機可以理解的執(zhí)行計劃來處理。

分布式圖遍歷執(zhí)行計劃
圖數(shù)據(jù)的規(guī)模往往十分龐大，例如Github交互的圖規(guī)模可以到達數(shù)百TB規(guī)模，金融交易數(shù)據(jù)的規(guī)?？梢赃_到萬億規(guī)模。如此復雜的圖無法通過單機完成遍歷計算。

因此分布式圖計算引擎需要的是可以分布式執(zhí)行的計劃，這對執(zhí)行計劃的效率、可擴展性、負載均衡性提出了極高要求。

我們來看幾個常見GQL語句的執(zhí)行計劃，一探究竟。這里以螞蟻集團開源的圖計算系統(tǒng)GeaFlow(品牌名為TuGraph-Analytics)為例，感興趣的同學文末有開源地址。

走圖
以示例圖為例，我們要查看人與人之間的好友關(guān)系時，可以使用如下GQL描述。

該描述非常直觀，表示了查詢兩個人a, b之間類型為knows的邊，要求b的id不能為1，返回三個結(jié)果字段作為結(jié)果表。

由于查詢并不復雜，其產(chǎn)生的執(zhí)行計劃也不復雜，只有6個步驟。

StepSource表示讀取圖，數(shù)字表示步驟的標識ID。MatchVertex步驟表示匹配對應類型的點，例如點a被聲明為person類型，則必須把其他類型的點過濾掉。

MatchEdge步驟表示匹配對應類型的邊，BOTH表示邊的方向不限，因為好友關(guān)系是一種相互的關(guān)系。

StepFilter步驟對應了GQL查詢中的b.id != 1條件，類似SQL語言的WHERE語句，會被翻譯成一個特定步驟。StepEnd步驟表示執(zhí)行計劃結(jié)束。

關(guān)注細節(jié)的同學可能發(fā)現(xiàn)了，在MatchEdge(e)和MatchVertex(b)之間被標記為不能串聯(lián)。

這實際對應了走圖的Shuffle過程，匹配點和邊都可以在一個點原地完成，這在物理上對應了一臺機器。如果我們從出邊走到其對端點，則對端點可能并不存儲在這臺機器上，因此會產(chǎn)生數(shù)據(jù)Shuffle過程，相當于DFS/BFS算法中的深度+1，在執(zhí)行計劃上反映為兩個單步不可串聯(lián)。

聚合

簡單的走圖過程幾乎可以被BFS/DFS算法的實現(xiàn)所替代，例如上面走圖的簡單例子，可以轉(zhuǎn)化為2輪迭代的遍歷完成。

但實際上，隨著圖研發(fā)的深入，走圖需求會越來越復雜，相應地GQL查詢會越來越長，執(zhí)行計劃也會變得復雜。一旦執(zhí)行計劃復雜到一定程度，人工實現(xiàn)就變得不現(xiàn)實了。

來看這個點上聚合的例子，當我們從點a走到點b后，發(fā)起一個聚合子查詢，該查詢過濾了b點創(chuàng)建軟件的數(shù)量，要求該數(shù)量為0。待子查詢返回后，根據(jù)其結(jié)果，我們可以按照條件過濾路徑，然后輸出結(jié)果所需的a, b對。

該查詢產(chǎn)生的執(zhí)行計劃如圖。這個執(zhí)行計劃包含了一個嵌套關(guān)系，在步驟14進入子查詢1。子查詢1在步驟13返回，根據(jù)返回結(jié)果我們才能繼續(xù)執(zhí)行步驟15。

多么的復雜！我相信沒有人愿意手工實現(xiàn)這個圖算法的。

細心的同學不難發(fā)現(xiàn)，COUNT()算子被翻譯為點上聚合步驟，且分為了局部聚合(步驟10)和全局聚合(步驟12)。這是分布式計算的考慮，如果在每個點上，把本地的結(jié)果計數(shù)，提前產(chǎn)生COUNT值的中間結(jié)果，再發(fā)送到全局加和，就能夠降低通信和計算的開銷。

循環(huán)

好了！我們已經(jīng)學會了圖計算執(zhí)行計劃的思路，讓我們實現(xiàn)更多的查詢吧。

這個是社交分析的一個例子，來自LDBC測試集的BI03測試。

在該查詢中我們處理了一個循環(huán)'<-[:replyOf]-{0,}'，從而遞歸地獲取博文post的所有回復。這對應著執(zhí)行計劃中的步驟15的LoopUtil算子。