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

圖片

【資料圖】

圖片

從數(shù)學(xué)角度來說，圖論是研究建模對象之間關(guān)系結(jié)構(gòu)的學(xué)科。但是從工業(yè)界使用的角度，通常會對基礎(chǔ)的圖模型進行擴展，稱為屬性圖模型。屬性圖通常由以下幾部分組成：

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

每個邊包括 :

很多數(shù)據(jù)可以建模為圖。典型的例子包括 :

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

頂點是網(wǎng)頁，邊表示與其他頁面的 HTML 鏈接。

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

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

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

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

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

圖片

2.商品圖譜，商品、協(xié)議可以作為頂點，商品的合規(guī)、交易可以作為邊。

圖片

3.安全風(fēng)控：業(yè)務(wù)部門有內(nèi)容風(fēng)控的需求，希望在專家、供應(yīng)商、代理機構(gòu)中通過多跳查詢來識別圍標、竄標等行為。

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

大多數(shù)應(yīng)用程序是通過一層一層疊加數(shù)據(jù)模型來構(gòu)建的 。每一層都面臨的關(guān)鍵問題是:如何將其用下一層來表示?例如 :

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

這里說到數(shù)據(jù)模型，主要是為了說明不同的數(shù)據(jù)關(guān)系是我們選擇不同的數(shù)據(jù)庫的原因，因為不同的數(shù)據(jù)模型對應(yīng)了更適合哪種數(shù)據(jù)關(guān)系。

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

多對多關(guān)系是不同數(shù)據(jù)模型之間的重要區(qū)別特征。

如果數(shù)據(jù)大多是一對多關(guān)系(樹結(jié)構(gòu)數(shù)據(jù))或者記錄之間沒有關(guān)系，那么文檔模型是最合適的 。

但是，如果多對多的關(guān)系在數(shù)據(jù)中很常見呢 ?關(guān)系模型能夠處理簡單的多對多關(guān)系， 但是隨著數(shù)據(jù)之間的關(guān)聯(lián)越來越復(fù)雜，將數(shù)據(jù)建模轉(zhuǎn)化為圖模型會更加自然。

雖然關(guān)系型數(shù)據(jù)庫與文檔類型的數(shù)據(jù)庫，都可以用來描述圖結(jié)構(gòu)的數(shù)據(jù)模型，但是，圖（數(shù)據(jù)庫）不僅可以描述圖結(jié)構(gòu)與存儲數(shù)據(jù)本身，更著眼于處理數(shù)據(jù)之間的關(guān)聯(lián)（拓撲）關(guān)系。具體來說，圖（數(shù)據(jù)庫）有這么幾個優(yōu)點：

圖片

這顯然沒有圖數(shù)據(jù)庫直觀：

圖片

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

NoSQL 可以分為以下幾種數(shù)據(jù)庫：

1.文檔數(shù)據(jù)庫，比如 MongoDB 和 Elasticsearch;

2.鍵值數(shù)據(jù)庫，比如 Redis。

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

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

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

現(xiàn)在有圖數(shù)據(jù)庫產(chǎn)品

我們將圖數(shù)據(jù)庫分為三類：

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

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

實時寫入性能

圖片

查詢性能

圖片

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

圖片

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

ratel：提供用戶界面來執(zhí)行數(shù)據(jù)查詢，數(shù)據(jù)修改及元數(shù)據(jù)管理。

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

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

group：多個 alpha 組成一個 group，group 中的多個 alpha 通過 raft 協(xié)議保證數(shù)據(jù)一致性。

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

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

對于大多數(shù)生產(chǎn)應(yīng)用程序所需的規(guī)模和可靠性，建議使用此配置。

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

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

通過分片，數(shù)據(jù)分布在許多節(jié)點（或節(jié)點組）中以實現(xiàn)更高的規(guī)模。

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

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

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

Dgraph 基于 predicate 進行數(shù)據(jù)分片，即所有相同 predicate 的三元組形成一個分片。在分片內(nèi)部，根據(jù) subject-predicate 將三元組進一步分組，每一組數(shù)據(jù)壓縮成一個 key-value 對。其中 key 是 ，value 是一個稱為 posting list 的數(shù)據(jù)結(jié)構(gòu)。

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

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

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

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

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

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

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

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

索引跟數(shù)據(jù)一樣，以 key-value 的形式存儲，區(qū)別是 key 有所不同。數(shù)據(jù)的 key 是 ，而索引的 key 是 。Token 是索引的分詞器從 value 中獲取的，例如 hash 索引生成的 token 就是 hash 函數(shù)所計算的 hash 值。

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

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

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

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

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

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

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