什么是圖數據庫以及應用范圍？

圖數據庫是 NoSQL 的一種，一種將關聯數據的實體作為頂點，關系作為邊來存儲的特殊類型數據庫，能夠高效地對這些點邊結構進行存儲、檢索和查詢。它的優點是可以很自然地表示現實世界。比如社交關系（可以清楚地看到共同好友）、股東關系甚至銀行賬戶流動關系。

圖片

圖片

屬性圖

從數學角度來說，圖論是研究建模對象之間關系結構的學科。但是從工業界使用的角度，通常會對基礎的圖模型進行擴展，稱為屬性圖模型。屬性圖通常由以下幾部分組成：

• 節點，即對象或實體。
• 節點之間的關系，通常簡稱為邊（Edge）。通常邊是有方向或者無方向的，以表示兩個實體之間有持續的關系。

在屬性圖模型中，每個頂點包括:

• 唯一的標識符。
• 出邊的集合。
• 入邊的集合。
• 屬性的集合 (鍵-值對)

每個邊包括 :

• 唯一的標識符。
• 邊開始的頂點(尾部頂點)
• 邊結束的頂點(頭部頂點)
• 描述兩個頂點間關系類型的標簽。
• 屬性 的集合 (鍵-值對)。

很多數據可以建模為圖。典型的例子包括 :

社交網絡

頂點是人，邊指示哪些人彼此認識 。

Web 圖

頂點是網頁，邊表示與其他頁面的 HTML 鏈接。

公路或鐵路網

頂點是交叉路口，邊表示他們之間的公路或鐵路線。

公司股權關系

點的屬性可以為股票代碼、簡稱、市值、板塊等；邊的屬性可以為股權。

有很多著名的算法可以在這些圖上運行。例如，汽車導航系統搜索道路網中任意兩點之間的最短路徑，PageRank 可以計算 Web 圖上網頁的流行度，從而確定搜索排名。

在政采云，可以有很多使用的場景，比如：

1.項目圖譜，項目、供應商、專家可以用圖中的點來表示，項目的中標供應商、評標專家可以用邊來表示。

圖片

2.商品圖譜，商品、協議可以作為頂點，商品的合規、交易可以作為邊。

圖片

3.安全風控： 業務部門有內容風控的需求，希望在專家、供應商、代理機構中通過多跳查詢來識別圍標、竄標等行為。

數據庫關系和選擇什么數據庫？

數據模型可能是開發軟件最重要的部分，它們不僅對軟件的編寫方式，而且還對如何思考待解決的問題都有深遠的影響。

大多數應用程序是通過一層一層疊加數據模型來構建的 。每一層都面臨的關鍵問題是:如何將其用下一層來表示?例如 :

1. 作為一名應用程序開發人員，觀測現實世界(其中包括人員、組織 、貨物 、行 為、資金流動、傳感器等)，通過對象或數據結構，以及操作這些數據結構的 API 來對其建模。這些數據結構往往特定于該應用。
2. 當需要存儲這些數據結構時，可以采用通用數據模型(例如 JSON 或 XML 文檔、 關系數據庫中的表或圖模型)來表示。
3. 數據庫工程師接著決定用何種內存、磁盤或網絡的字節格式來表示上述 JSON/XML/關系/圖形數據。數據表示需要支持多種方式的查詢、搜索、操作和處理數 據。

這和我們通常說的 MVC 模型也有點相似，數據層、應用層、展示層都需要接受上一層的數據模型，通過封裝和處理給下一層使用。

這里說到數據模型，主要是為了說明不同的數據關系是我們選擇不同的數據庫的原因，因為不同的數據模型對應了更適合哪種數據關系。

關系模型

現在最著名的數據模型可能是 SQL，它基于 Edgar Codd 于1970年提出的關系模型: 數據被組織成關系( relations)，在SQL中稱為表( table)，其中每個關系者J)是元組(tuples)的無序集合 (在 SQL中稱為行)。

多對多關系是不同數據模型之間的重要區別特征 。

如果數據大多是一對多關系(樹結構數據)或者記錄之間沒有關系，那么文檔模型是最合適的 。

但是，如果多對多的關系在數據中很常見呢 ?關系模型能夠處理簡單的多對多關系， 但是隨著數據之間的關聯越來越復雜，將數據建模轉化為圖模型會更加自然。

雖然關系型數據庫與文檔類型的數據庫，都可以用來描述圖結構的數據模型，但是，圖（數據庫）不僅可以描述圖結構與存儲數據本身，更著眼于處理數據之間的關聯（拓撲）關系。具體來說，圖（數據庫）有這么幾個優點：

• 圖是一種更直觀、更符合人腦思考直覺的知識表示方式。這使得我們在抽象業務問題時，可以著眼于“業務問題本身”，而不是“如何將問題描述為數據庫的某種特定結構（例如表格結構）”。
• 圖更容易展現數據的特征，例如轉賬的路徑、近鄰的社區。例如，如果要分析某個公司的股權關系，表的組織方式如下：

圖片

這顯然沒有圖數據庫直觀：

圖片

我們都知道關系型數據庫和 NoSQL 數據庫，目前最廣泛使用的關系型數據庫有 Mysql、Oracle 和 Postgre。NoSQL 數據庫其實不是一個合適的詞，因為它其實并不代表具體的某些技術。

NoSQL 可以分為以下幾種數據庫：

1.文檔數據庫，比如 MongoDB 和 Elasticsearch;

2.鍵值數據庫，比如 Redis。

3.列式存儲，比如 HBase、Cassandra、HadoopDB

4.最后一種就是今天要說的圖數據庫，圖數據庫以點、邊、屬性的形式存儲數據。其優點在于靈活性高，支持復雜的圖形算法，可用于構建復雜的關系圖譜。常見的圖數據庫有：NebulaGraph、Neo4j、OrientDB、 DGraph等。

圖數據庫的類型和選型

在圖數據庫的選型上我們主要考慮遺下四點：

• 項目開源，暫不考慮需付費的圖數據庫；
• 分布式架構設計，具備良好的可擴展性；
• 毫秒級的多跳查詢延遲；
• 支持千億量級點邊存儲；

現在有圖數據庫產品

我們將圖數據庫分為三類：

• 第一類：Neo4j[3]、ArangoDB[4]、Virtuoso[5]、TigerGraph[6]、RedisGraph[7]。 此類圖數據庫只有單機版本開源可用，性能優秀，但不能應對分布式場景中數據的規模增長，即不滿足選型要求
• 第二類：JanusGraph[8]、HugeGraph[9]。 此類圖數據庫在現有存儲系統之上新增了通用的圖語義解釋層，圖語義層提供了圖遍歷的能力，但是受到存儲層或者架構限制，不支持完整的計算下推，多跳遍歷的性能較差，很難滿足 OLTP 場景下對低延時的要求，即不滿足選型要求。
• 第三類：DGraph[10]、NebulaGraph[11]。 此類圖數據庫根據圖數據的特點對數據存儲模型、點邊分布、執行引擎進行了全新設計，對圖的多跳遍歷進行了深度優化，基本滿足我們的選型要求。

DGraph 是由前 Google員工 Manish Rai Jain 離職創業后，在 2016 年推出的圖數據庫產品，底層數據模型是 RDF（實際上也是屬性圖差不多），基于 Go 語言編寫，存儲引擎基于 BadgerDB 改造，使用 RAFT 保證數據讀寫的強一致性。

NebulaGraph 是由前 Facebook 員工葉小萌離職創業后，在 2019 年推出的圖數據庫產品，底層數據模型是屬性圖，基于 C++ 語言編寫，存儲引擎基于 RocksDB 改造，使用 RAFT 保證數據讀寫的強一致性。

實時寫入性能

圖片

查詢性能

圖片

在查詢和插入的性能測試方面，兩個數據庫各有優劣，都能滿足我們的需求，我們最后選擇了 Dgraph 作為我們使用的圖數據庫，因為兩個原因：

• NebulaGraph 不支持模糊查詢，需要依賴 ElasticSearch，運維成本較高，
• Dgraph 是使用RDF通用數據類型，遵守 w3c 查詢語句規范，而 NebulaGraph 的查詢是 nGQL，自己開發的一套語言，不具有通用性

Dgraph

一、架構模型

圖片

dgraph可以分為三個部分：ratel、alpha、zero。

ratel：提供用戶界面來執行數據查詢，數據修改及元數據管理。

alpha：用于管理數據（謂詞和索引），外部用戶主要都是和 alpha 進行數據交互。

zero：用于管理集群，并在 group 之間按照指定頻率去均衡數據。alpha 節點分成若干個 group，每個 group 存儲若干個數據分片。由于分片的大小是不均勻的，因此不同 group 也是不均勻的。zero 節點的任務之一就是平衡 group 之間的數據大小。具體方法是，每個 group 周期性地向 zero 報告各個數據分片的大小。zero 根據這個信息在 group 之間移動分片，使得每個 group 的磁盤利用率接近。

group：多個 alpha 組成一個 group，group 中的多個 alpha 通過 raft 協議保證數據一致性。

二、擴展、復制和分片

每個集群將至少有一個 Dgraph 零節點和一個 Dgraph Alpha 節點。然后以兩種方式擴展數據庫。

高可用性復制

為了實現高可用性，Dgraph 使用三個零和三個 alpha 運行，而不是每個一個。

對于大多數生產應用程序所需的規模和可靠性，建議使用此配置。

擁有三臺服務器既可以使整個集群的容量增加三倍，也可以提供冗余。

分片

當數據大小接近或超過 1 TB 時，Dgraph 數據庫通常會被分片，這樣完整的數據副本就不會保留在任何單個 alpha 節點上。

通過分片，數據分布在許多節點（或節點組）中以實現更高的規模。

當需要提供大規模和理想的可靠性時，分片和高可用性相結合。

自我修復

在 Dgraph 的云產品中，Kubernetes 用于自動檢測、重啟和修復任何集群（HA、分片、兩者或兩者都不），以保持事物平穩運行并滿負荷運行。

三、數據存儲

在 Dgraph 中，數據的最小單位是一個三元組。三元組既可以表示一個屬性(subject-predicate-value)，也可以表示一條邊(subject-predicate-object)。Dgraph 為每個對象分配一個全局唯一的 id，稱為 uid。Uid 是一個 64 位無符號整數，從 1 開始單調遞增。

Dgraph 基于 predicate 進行數據分片，即所有相同 predicate 的三元組形成一個分片。在分片內部，根據 subject-predicate 將三元組進一步分組，每一組數據壓縮成一個 key-value 對。其中 key 是 <subject, predicate>，value 是一個稱為 posting list 的數據結構。

Posting list是一個有序列表。對于指向值的 predicate(如 name)，posting list 是一個值列表；對于指向對象的 predicate，posting list 是一個 uid 列表，Dgraph 對其做了整數壓縮優化。每 256 個 uids 組成一個 block，block 擁有一個基數(base)。Block 不存儲 uid 本身，而是存儲當前 uid 和上一個 uid 的差值。這個方法產生的壓縮比是 10。

Dgraph 的存儲方式非常有利于連接和遍歷，一個邊遍歷只需要一個 KV 查詢。例如，找到 X 的所有粉絲，只需要用 <follower，X> 當做 key 進行查詢，就能獲得一個 posting list，包含了所有粉絲的 uid；尋找 X 和 Y 的公共粉絲，只需要查詢 <follower, X> 和 <follower, Y> 的 posting lists，然后求兩者的交集。

如果有太多的三元組共享相同的 <subject，predicate>，posting list 就變得過大。Dgraph 的解決方法是，每當 posting list 的大小超過一個閾值，就把它分成兩份，這樣一個分割的 posting list 就會對應多個 keys。這些存儲細節都是對用戶透明的。

四、索引

當通過應用函數進行過濾時，Dgraph 使用索引來高效地搜索潛在的大型數據集。 所有標量類型都可以被索引。

類型int、float、bool、geo只有一個默認索引，他們都只有自己的分詞器。

對于 string 類型，支持正則表達式、fulltext、term、exact 和 hash 索引；

對于 datetime 類型，支持按年、月、日、小時索引；

對于 geo 類型，支持 nearby、within 等索引。

索引跟數據一樣，以 key-value 的形式存儲，區別是 key 有所不同。數據的 key 是 <predicate, uid>，而索引的 key 是 <predicate, token>。Token 是索引的分詞器從 value 中獲取的，例如 hash 索引生成的 token 就是 hash 函數所計算的 hash 值。

在定義 schema 的時候，可以給 predicate 創建一個或多個索引。對該 predicate 的每次更新會調用一個或多個分詞器來產生 tokens。更新的時候，首先從舊值的 tokens 的 posting lists 中刪除相應的 uid，然后把 uid 添加到新產生的 tokens 的 posting lists 里。

五、查詢

遍歷

Dgraph 的查詢通常從一個 uidlist 開始，沿著邊進行遍歷。

{
  movies(func: uid（0xb5849, 0x394c)) {
    uid
     m_name     
     code
     star{
         s_name
     }
  }
}

查詢的起點是 uid 為0xb5849 的單個對象，處理過程如下：

1. 查詢 <m_name,0xb5849>、<code,0xb5849> 兩個 key，分別獲得一個值(或者值列表)和一個 uidlist。
2. 對于 uidlist 中的每一個 UID，查詢 <s_name, UID>、<s_name, UID>，獲取相應的值。

函數

通常我們不知道 uid，需要根據名稱查詢

//查詢示例：具有dog，dogs，bark，barks，barking等的所有名稱。停止詞the which 會被刪除掉。
{
  movie(func:alloftext(name@en, "the dog which barks")) {
    name@en
  }
}

查詢 的處理過程是：

1. term 分詞器從"the dog which barks"字符串中獲取到 dog 和 barks 兩個 tokens。
2. 發出兩個查詢 <name, dog> 和 <name, barks>，獲得兩個 uidlist。由于使用了函數 anyofterms，所以求這兩個 uidlist 的并集，得到一個更大 uidlist。
3. 同查詢遍歷步驟。

過濾

過濾是查詢語句的主要成分之一。過濾條件也是由函數組成的。

{  
  me(func: anyofterms(name, "Julie Baker"))@filter(eq(sex, "female")){
    pred_A  
    pred_B {  
      pred_B1  
      pred_B2  
    }
  } 
}

深度查詢

這是一個查詢 4 度關注的語句。通過 A 的 uid 可以查詢到 E 的 name

A<-B<-C<-D<-E

{
  find_follower(func: uid(A_UID)) @recurse(depth: 4) {
    name
    age
    follows{
       name
      }
  }
}

圖數據庫的業務實踐

一、業務背景

1.知識圖譜

知識圖譜是應客戶要求直觀的展示項目信息，包括招投標供應商、采購單位、代理機構、評標專家、預警、違規信息、公告信息，這些數據量在五百萬到千萬級別，后期甚至可能到上億，查詢條件復雜、數據量較大，如果使用普通的關系數據庫，難以應對低延遲、數據量大的查詢需求。現改用 Dgraph 圖數據庫，則可以輕松查詢千萬級數據。

2.機構股權關系展示

不同于市面上的股權展示，客戶要求能展示多個公司的股權關系，包括有無共同股東。核心數據在 30萬 左右，總數據量在 500萬 左右，邊關系約有 1800萬。此需求的數據量不是特別大，但是假設股權關系復雜，理論上一家公司的股權關系可以無限套娃，舉個例子：假如 A 持有 B 股權，B 持有 C 股權，C 持有 D 股權，要查詢 D 公司的股權，則遍歷三次，深度每加一層，數據量呈指數級上升，會導致查詢時間久、甚至超時的現象。圖數據庫特有的物理索引和數據存儲模型，對圖的多跳遍歷進行了深度優化，可以滿足大數據量和多跳查詢，經測試 Dgraph 滿足我們的性能要求。

二、解決方案

總體架構圖

dgraph客戶端（SDK）

目標

封裝對圖數據庫（例如：Dgraph、nebula graph）客戶端連接、查詢、寫入等操作，對外提供透明的操作接口，方便接入方低成本高效接入，減少其他團隊學習 Graph 的成本。

設計

客戶端的設計參照 Mybatis 查詢的半自動模版配置模式，即在模版中寫半自動的 Dgraph 語句，在代碼中將參數、條件等寫入，目前已經完成通用模版的配置，調用方無需自己寫 Dgraph 語句，只需調用接口，構造查詢條件，SDK 即可生成 Graphql 語句并執行查詢，返回查詢結果。

圖片

設計框架圖

圖片

Dgrpah數據生產

目標

不管是現有的數據還是以后實時產生的數據，原來的業務數據都是存儲在各個業務方的關系數據庫，我們都需要將歷史數據和實時增量數據導入到 Dgraph 數據庫。

設計

業務數據由大數據部門統一收集，再通過 Kfaka 消息發送給我們，我們再通過 Dgraph 的 java 客戶端寫入到 Graph。由于數據量較大，時間較緊，我們采取批量接受 Kafka 消息，經過轉換數據，再批量寫入數據到 Dgraph 的方式提高導入數據效率，在測試環境，每萬條數據只需要數秒時間，生產環境應當更快。

設計框架

圖片

總結和展望

本文一開始介紹了圖數據庫的概念和優點，后面說明了數據模型、數據關系是誕生和選擇圖數據庫重要原因，中間主要是介紹 Dgraph 及其他圖數據庫的特點，對比各個圖數據庫和選擇 Dgraph 的原因；最后一部分是在公司業務的實踐應用，比如解決大數據量查詢帶來的查詢緩慢的痛點；深度查詢帶來的難點，在使用方面做出的優化，包括 sdk 的封裝和數據的導入。

圖數據庫的應用，遠遠不止簡單的查詢。在智能問答、安全風控、商品圖譜、數據挖掘等各方面的應用都可以使用圖數據庫。圖數據庫在很多方面都優于關系數據庫，更快速、更靈活、更直觀，可以預見，將來圖數據庫會更普及，根據 verifiedmarketresearc, fnfresearch, marketsandmarkets, 以及 gartner 等智庫的統計和預測，圖數據庫市場（包括云服務）規模在 2019 年大約是 8 億美元，將在未來 6 年保持 25% 左右的年復合增長(CAGR)至 30-40 億美元，這大約對應于全球數據庫市場 5-10% 的市場份額。

參考資料

https://dgraph.io/docs/dgraph-overview/

https://dgraph.io/docs/dql/dql-syntax/dql-query/

https://docs.nebula-graph.com.cn/3.5.0/1.introduction/0-0-graph/

https://docs.nebula-graph.com.cn/3.5.0/1.introduction/0-1-graph-database/#_6

https://docs.nebula-graph.com.cn/3.5.0/1.introduction/0-2.relates/

https://tech.meituan.com/2021/04/01/nebula-graph-practice-in-meituan.html