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

在本文中，我們將介紹 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 型別：

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

類似的，對于 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 后：

1. IR Compiler 負責對 Query 進行語法檢查，對于合法 Query，IR Compiler 通過 IR Library API 對查詢語法樹進行編譯，轉換成由 IR Operator 組成的 Logical Plan，并進一步呼叫 IR Library API 生成 Physical Plan，再將 Physical Plan 分發到分布式的 Dataflow 計算框架，
2. 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 來進行查詢，示例如下：

1. 首先我們修改 Gremlin Console 的 conf/remote.yaml 組態檔，修改對應的 host 和 port;
2. 打開 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

標籤：大數據

上一篇：c 字串下標超出范圍/除錯斷言失敗

下一篇：redis服務器