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

圖片

【資料圖】

圖片

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

在屬性圖模型中，每個(gè)頂點(diǎn)包括:

每個(gè)邊包括 :

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

頂點(diǎn)是人，邊指示哪些人彼此認(rèn)識(shí) 。

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

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

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

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

在政采云，可以有很多使用的場(chǎng)景，比如：

1.項(xiàng)目圖譜，項(xiàng)目、供應(yīng)商、專(zhuān)家可以用圖中的點(diǎn)來(lái)表示，項(xiàng)目的中標(biāo)供應(yīng)商、評(píng)標(biāo)專(zhuān)家可以用邊來(lái)表示。

圖片

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

圖片

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

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

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

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

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

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

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

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

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

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

圖片

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

圖片

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

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

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

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

3.列式存儲(chǔ)，比如 HBase、Cassandra、HadoopDB

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

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

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

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

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

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

實(shí)時(shí)寫(xiě)入性能

圖片

查詢(xún)性能

圖片

在查詢(xún)和插入的性能測(cè)試方面，兩個(gè)數(shù)據(jù)庫(kù)各有優(yōu)劣，都能滿(mǎn)足我們的需求，我們最后選擇了 Dgraph 作為我們使用的圖數(shù)據(jù)庫(kù)，因?yàn)閮蓚€(gè)原因：

圖片

dgraph可以分為三個(gè)部分：ratel、alpha、zero。

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

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

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

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

每個(gè)集群將至少有一個(gè) Dgraph 零節(jié)點(diǎn)和一個(gè) Dgraph Alpha 節(jié)點(diǎn)。然后以?xún)煞N方式擴(kuò)展數(shù)據(jù)庫(kù)。

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

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

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

當(dāng)數(shù)據(jù)大小接近或超過(guò) 1 TB 時(shí)，Dgraph 數(shù)據(jù)庫(kù)通常會(huì)被分片，這樣完整的數(shù)據(jù)副本就不會(huì)保留在任何單個(gè) alpha 節(jié)點(diǎn)上。

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

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

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

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

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

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

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

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

當(dāng)通過(guò)應(yīng)用函數(shù)進(jìn)行過(guò)濾時(shí)，Dgraph 使用索引來(lái)高效地搜索潛在的大型數(shù)據(jù)集。 所有標(biāo)量類(lèi)型都可以被索引。

類(lèi)型int、float、bool、geo只有一個(gè)默認(rèn)索引，他們都只有自己的分詞器。

對(duì)于 string 類(lèi)型，支持正則表達(dá)式、fulltext、term、exact 和 hash 索引；

對(duì)于 datetime 類(lèi)型，支持按年、月、日、小時(shí)索引；

對(duì)于 geo 類(lèi)型，支持 nearby、within 等索引。

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

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

Dgraph 的查詢(xún)通常從一個(gè) uidlist 開(kāi)始，沿著邊進(jìn)行遍歷。

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

查詢(xún)的起點(diǎn)是 uid 為0xb5849 的單個(gè)對(duì)象，處理過(guò)程如下：

//查詢(xún)示例：具有dog，dogs，bark，barks，barking等的所有名稱(chēng)。停止詞the which 會(huì)被刪除掉。{  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      }  }}