GAIA-IR: GraphScope 上的並行化圖查詢引擎

在本文中，我們將介紹 GraphScope 圖互動式查詢引擎 GAIA-IR，它支持高效的 Gremlin 語言表達的交互圖查詢，同時高度抽象了圖上的查詢計算，具有高可擴展性。 ...

在本文中，我們將介紹 GraphScope 圖互動式查詢引擎 GAIA-IR，它支持高效的 Gremlin 語言表達的交互圖查詢，同時高度抽象了圖上的查詢計算，具有高可擴展性。

背景介紹

在海量數據的分析中，圖查詢是一種重要的工具。Gremlin^[1] 是由 Apache Tinkerpop 提出並維護的工業界標準的圖查詢語言，被業界流行圖資料庫廣泛應用，例如 Neo4j^[2] 、OrientDB^[3]、JanusGraph^[4]、Microsoft Cosmos DB^[5] 以及 Amazon Neptune^[6]。而 GraphScope 中的圖查詢引擎 GAIA 則是業界首個開源的支持大規模分散式並行化 Gremlin 的系統。然而，儘管 Gremlin 語言的靈活性是它顯著的優勢，在 GAIA 系統的設計和使用中，我們也發現了一些存在的問題。

現有問題

GAIA 查詢系統主要有如下幾點弊病：

D1: Gremlin 運算元數量繁多，並且對同種語義有多種表達。這就導致為了支持豐富的 Gremlin 運算元，GAIA 中需要端到端在各個模塊中添加對應的運算元，並且運算元實現之間可能存在冗餘的計算邏輯。例如，當我們有查看屬性的需求時，Gremlin 中可以通過elementMap()、 valueMap()、values()、 select().valueMap()、 project().valueMap()等表達方式得到類似的結果，示例如下：

gremlin> g.V().elementMap() 
==>[id:1,label:person,name:marko,age:29] 
==>[id:2,label:person,name:vadas,age:27]

gremlin> g.V().valueMap('name','age') 
==>[name:[marko],age:[29]] 
==>[name:[vadas],age:[27]]

gremlin> g.V().as('a').select('a').by(valueMap('name', 'age')) 
==>[name:[marko], age:[29]] 
==>[name:[vadas], age:[27]]

gremlin> g.V().as('a').project('a').by(valueMap('name', 'age')) 
==>[a:[name:[marko], age:[29]]] 
==>[a:[name:[vadas], age:[27]]]

而為了支持這些類似的表達，GAIA 中需要定義多個冗餘運算元，並且需要在各個模塊中支持，對開發並不友好，可擴展性較差。

D2: GAIA 的語言擴展性差。GAIA 是 Gremlin 並行化查詢的定製化實現，而現如今也有很多其他常用的圖查詢語言，例如 Cypher、GSQL 等。如果未來我們需要進一步接入更多的查詢語言，則幾乎無法通過擴展 GAIA 來實現。

D3:: Gremlin 對複雜的 expression 支持不佳。例如，我們想通過以下 Gremlin 查詢語句，找到 "a" 的兩度鄰居中，滿足一定 "age" 屬性條件的人：

g.V().as("a").out().as("b").out().as("c")
 .where("c", P.lt("a").or(P.gt("a").and(P.gt("b")))).by("age")

像where() 中這樣複雜的嵌套條件過濾並不直觀，對用戶使用來說不太友好。

D4: GAIA 中沒有很好的 Gremlin 語法規範定義，也很難界定當前系統對 Gremlin 運算元及運算元組合的支持範圍，對用戶來說並不友好。

解決方案

為瞭解決以上的問題，我們進一步提出了與查詢語言無關、普適性更強的中間表示層 GAIA-IR（簡稱 IR），用來描述通用的圖查詢語義。我們抽象出的操作運算元可以分為兩類：關係型操作運算元及圖相關操作運算元。其中，關係型操作運算元主要與傳統關係型資料庫上的操作保持一致，如 Projection、 Selection、 GroupBy、 OrderBy 等；而圖相關操作運算元則是圖數據上的特有查詢，如點查詢、鄰點（邊）查詢等等。通過這層查詢語言無關的中間表示層，我們可以解決上述 GAIA 中存在的問題：

A1: GAIA-IR 層用統一中間表示來實現 Gremlin 運算元中類似的表達。例如，我們抽象出 project 運算元，用於統一表示上述 D1 中 Gremlin 各種取屬性操作。

A2: GAIA-IR 層與查詢語言無關，這就方便了 GAIA-IR 後續可以進一步接入更多的語言。將來，我們只需要將不同語言的操作運算元翻譯到 IR 的統一中間表示層，就可以自然地實現該語言的並行化查詢，而不需要再針對每套語言去設計分散式並行化實現。

A3: GAIA-IR 還額外提供了豐富的 expression 支持，從而滿足用戶的需求。例如，對比 D3 中的例子，我們在 where() 運算元中加入 expression 的表達支持會更加直觀：

g.V().as("a").out().as("b").out().as("c")
 .where(expr("@c.age < @a.age || (@c.age > @a.age && @c.age > @b.age)"))

A4: GAIA-IR 中引入了 Antlr 工具，支持 Gremlin 語法檢查功能，並且明確了系統對 Gremlin 運算元及組合的支持範圍，對用戶使用更為友好。

IR整體設計

接下來，我們介紹 GAIA-IR 的整體設計。

概念介紹

首先，我們介紹 IR 中的一些基本概念。IR 抽象了圖數據上的基本計算，從而提供了一套統一的、簡潔的、語言無關的中間表示層。

操作運算元（IR Operator）：目前，我們將操作運算元（Graph-Relational Algebra）抽象為兩類，即關係型操作和圖相關操作。

關係型操作包含了：Projection、Selection、 Join、 Groupby、 Orderby、 Dedup、 Limit 等。這與傳統關係型資料庫上的操作保持一致。
圖相關操作包含了：GetV、 E(dge)-Join、 P(ath)-Join，分別表示圖上的取點屬性操作、取鄰點（邊）操作、以及路徑操作。

通過以上兩類運算元抽象，我們既可以表達傳統的關係型運算，又可以支持圖上特有的查詢操作。同時，該抽象運算元集合併不受查詢語言的限制，由此可以很容易地拓展到其他語言。

數據結構（GRecord）：我們定義了數據結構 GRecord，用來表示每個 IR Operator 的輸入輸出。GRecord 是一個多列的結構，每列有自己的別名（Alias）和值（Value）：

別名（Alias）：類似於SQL中的As別名。特別的，為了適配 Gremlin，我們額外提供了一個 Unique Alias -- "HEAD"，作為匿名別名，特指上一個運算元的輸出，即當前運算元的輸入。
值（Value）：值的類型分為兩種，簡單類型 CommonObject（包括 int/string/intArray/stringArray 等）以及圖數據類型 GraphObject（包括 Vertex、Edge 以及 Path）。

Gremlin查詢翻譯示例

在 Gremlin 查詢中，我們將其翻譯成 GRecord 上的一系列 IR Operator 操作，從而支持 Gremlin 的查詢語義。例如，在查詢 g.V().as('a').select('a').by(valueMap('name', 'age')) 中，g.V().as('a') 會產生如下的中間結果，別名叫做 "a"，數據類型為 Vertex 類型：

R1	Vertex { name:[marko], age:[29] }, Alias: "a"
GR2	Vertex { name:[vadas], age:[27] }, Alias: "a"

而我們會將 select('a').by(valueMap('name', 'age')) 翻譯為 Project("{a.name,a.age}")，以上述的 GR1、GR2 作為 Project 的輸入，我們可以得到輸出 GR1'、GR2'，即我們所需要的點屬性：

GR1'	CommonObject {a.name:[marko], a.age:[29] }
GR2'	CommonObject { a.name:[vadas], a.age:[27] }

類似的，對於 Gremlin 查詢 g.V().valueMap('name','age')，我們只需將 GR1、GR2 的 Alias 變為匿名的 "HEAD"，並將 valueMap('name','age') 翻譯為 Project("{HEAD.name,HEAD.age}")，便可以得到同樣的結果。由此，我們就能夠將同一語義、不同表達的 Gremlin 運算元，翻譯成統一的中間表示。更甚，對於其他語言，例如 SQL 中的取屬性操作，我們也可以很直觀的翻譯成 IR 中的 Project 運算元。由此可見，IR 是抽象出了一套更為簡潔通用、且與查詢語言無關的中間表示層。

系統架構

接下來，我們給出 GAIA-IR 目前對 Gremlin 的並行化計算架構，如下圖所示。

總體來說，我們相容了官方的 Gremlin Console 以及 Gremlin SDK 的查詢方式。在用戶提交 Gremlin Query 後：

IR Compiler 負責對 Query 進行語法檢查。對於合法 Query，IR Compiler 通過 IR Library API 對查詢語法樹進行編譯，轉換成由 IR Operator 組成的 Logical Plan，併進一步調用 IR Library API 生成 Physical Plan，再將 Physical Plan 分發到分散式的 Dataflow 計算框架。
Dataflow 框架會在服務拉起階段預先拉起圖數據分區，建立執行計算的線程池。在接收到 IR Compiler 分發過來的物理執行計劃後，IR Runtime 負責解析 Physical Plan，並構建引擎可執行的 Execution Plan。同時對於每個 IR Operator，IR Runtime 負責生成其對應的引擎可理解的 UDF，從而實現具體 IR Operator 的計算語義。完成計算後，IR Runtime 將結果返回給 IR Compiler，由 IR Compiler 進一步解析並返回給客戶端。

如何使用 IR

在介紹完 GAIA-IR 的整體設計後，我們介紹如何使用 GAIA-IR 引擎進行查詢。

服務部署：在 GraphScope之前的文章中，我們介紹瞭如何部署 GraphScope。GAIA-IR 作為 GraphScope 中 GIE 的重要實現，整體的拉起方式與 GraphScope 保持一致。我們以 Helm 部署 GraphScope 為例，只需要在安裝過程中，指定引擎選項為 GAIA，便可以順利拉起 GAIA-IR，安裝命令示例如下：

helm repo add graphscope https://graphscope.oss-cn-beijing.aliyuncs.com/charts/
helm install [RELEASE_NAME] --set executor=gaia graphscope/graphscope-store

更多詳細的部署操作可以參考官方文檔^[7]。

Gremlin 查詢：在成功拉起服務後，我們可以通過 Gremlin Server host 和 port 來進行查詢。以 Gremlin Console 查詢為例，在服務順利拉起並且導入數據（具體數據導入步驟可參考官方文檔^[8]）之後，我們便可以通過配置 Gremlin Console 來進行查詢。示例如下：

首先我們修改 Gremlin Console 的 conf/remote.yaml 配置文件，修改對應的 host 和 port;
打開 Gremlin Console，給定 remote.yaml 的配置，便可以開始查詢：

gremlin> :remote connect tinkerpop.server conf/remote.yaml
==>Configured localhost/127.0.0.1:8182
gremlin> :remote console
==>All scripts will now be sent to Gremlin Server - [localhost/127.0.0.1:8182] - type ':remote console' to return to local mode
gremlin> g.V().valueMap('name','age') 
==>[name:[marko],age:[29]] 
==>[name:[vadas],age:[27]]

結語

本文簡述了 GAIA-IR 的設計初衷和總體架構，以及如何使用 GAIA-IR 引擎進行查詢。在 GAIA-IR 的目錄^[9]可以找到 GitHub 上的當前發佈版本。GAIA-IR 作為 GraphScope 的圖查詢引擎，提供高效的 Gremlin 並行化查詢實現。同時，在 IR 的統一中間表示上，我們也會引入更多的等價變換、優化實現，支持例如 Pattern Match 等重要場景。在後續的文章中，我們也會介紹更多的技術細節。我們也將持續完善 GAIA-IR 的實現，同時非常歡迎與期待社區的反饋和貢獻。

參考資料

[1]Gremlin: http://tinkerpop.apache.org/

[2]Neo4j: https://neo4j.com/

[3]OrientDB: https://www.orientdb.org/

[4]JanusGraph: https://janusgraph.org/

[5]Microsoft Cosmos DB: https://azure.microsoft.com/en-us/services/cosmos-db/

[6]Amazon Neptune: https://aws.amazon.com/neptune/

[7]官方文檔: https://graphscope.io/docs/persistent_graph_store.html

[8]官方文檔: https://graphscope.io/docs/persistent_graph_store.html

[9]GAIA-IR 的目錄: https://github.com/alibaba/GraphScope/tree/main/research/query_service/ir