推薦一個分布式圖數(shù)據(jù)庫Nebula Graph,萬億級數(shù)據(jù),毫秒級延時

什么是Nebula Graph

Nebula Graph 是一款開源的、分布式的、易擴展的原生圖數(shù)據(jù)庫，能夠承載包含數(shù)千億個點和數(shù)萬億條邊的超大規(guī)模數(shù)據(jù)集，并且提供毫秒級查詢

什么是圖數(shù)據(jù)庫

圖數(shù)據(jù)庫是專門存儲龐大的圖形網(wǎng)絡并從中檢索信息的數(shù)據(jù)庫。它可以將圖中的數(shù)據(jù)高效存儲為點（Vertex）和邊（Edge），還可以將屬性（Property）附加到點和邊上

圖數(shù)據(jù)庫適合存儲大多數(shù)從現(xiàn)實抽象出的數(shù)據(jù)類型。世界上幾乎所有領域的事物都有內在聯(lián)系，像關系型數(shù)據(jù)庫這樣的建模系統(tǒng)會提取實體之間的關系，并將關系單獨存儲到表和列中，而實體的類型和屬性存儲在其他列甚至其他表中，這使得數(shù)據(jù)管理費時費力。

Nebula Graph 作為一個典型的圖數(shù)據(jù)庫，可以將豐富的關系通過邊及其類型和屬性自然地呈現(xiàn)。

Nebula Graph 的優(yōu)勢

開源

Nebula Graph 是在 Apache 2.0 條款下開發(fā)的。越來越多的人，如數(shù)據(jù)庫開發(fā)人員、數(shù)據(jù)科學家、安全專家、算法工程師，都參與到 Nebula Graph 的設計和開發(fā)中來，歡迎訪問 Nebula Graph GitHub 主頁參與開源項目。

高性能

基于圖數(shù)據(jù)庫的特性使用 C++ 編寫的 Nebula Graph，可以提供毫秒級查詢。眾多數(shù)據(jù)庫中，Nebula Graph 在圖數(shù)據(jù)服務領域展現(xiàn)了卓越的性能，數(shù)據(jù)規(guī)模越大，Nebula Graph 優(yōu)勢就越大。詳情請參見 Nebula Graph benchmarking 頁面。

易擴展

Nebula Graph 采用 shared-nothing 架構，支持在不停止數(shù)據(jù)庫服務的情況下擴縮容。

易開發(fā)

Nebula Graph 提供 Java、Python、C++ 和 Go 等流行編程語言的客戶端，更多客戶端仍在開發(fā)中。詳情請參見 Nebula Graph clients。

高可靠訪問控制

Nebula Graph 支持嚴格的角色訪問控制和 LDAP（Lightweight Directory Access Protocol）等外部認證服務，能夠有效提高數(shù)據(jù)安全性。詳情請參見驗證和授權。

生態(tài)多樣化

Nebula Graph 開放了越來越多的原生工具，例如 Nebula Graph Studio、Nebula Console、Nebula Exchange 等，更多工具可以查看生態(tài)工具概覽。

此外，Nebula Graph 還具備與 Spark、Flink、HBase 等產(chǎn)品整合的能力，在這個充滿挑戰(zhàn)與機遇的時代，大大增強了自身的競爭力。

兼容 openCypher 查詢語言

Nebula Graph 查詢語言，簡稱為 nGQL，是一種聲明性的、部分兼容 openCypher 的文本查詢語言，易于理解和使用。詳細語法請參見 nGQL 指南。

面向未來硬件，讀寫平衡

閃存型設備有著極高的性能，并且價格快速下降， Nebula Graph 是一個面向 SSD 設計的產(chǎn)品，相比于基于 HDD + 大內存的產(chǎn)品，更適合面向未來的硬件趨勢，也更容易做到讀寫平衡。

靈活數(shù)據(jù)建模

用戶可以輕松地在 Nebula Graph 中建立數(shù)據(jù)模型，不必將數(shù)據(jù)強制轉換為關系表。而且可以自由增加、更新和刪除屬性。詳情請參見數(shù)據(jù)模型。

廣受歡迎

騰訊、美團、京東、快手、360 等科技巨頭都在使用 Nebula Graph。詳情請參見 Nebula Graph 官網(wǎng)。

適用場景

Nebula Graph 可用于各種基于圖的業(yè)務場景。為節(jié)約轉換各類數(shù)據(jù)到關系型數(shù)據(jù)庫的時間，以及避免復雜查詢，建議使用 Nebula Graph。

欺詐檢測

金融機構必須仔細研究大量的交易信息，才能檢測出潛在的金融欺詐行為，并了解某個欺詐行為和設備的內在關聯(lián)。這種場景可以通過圖來建模，然后借助 Nebula Graph，可以很容易地檢測出詐騙團伙或其他復雜詐騙行為。

實時推薦

Nebula Graph 能夠及時處理訪問者產(chǎn)生的實時信息，并且精準推送文章、視頻、產(chǎn)品和服務。

知識圖譜

自然語言可以轉化為知識圖譜，存儲在 Nebula Graph 中。用自然語言組織的問題可以通過智能問答系統(tǒng)中的語義解析器進行解析并重新組織，然后從知識圖譜中檢索出問題的可能答案，提供給提問人。

社交網(wǎng)絡

人際關系信息是典型的圖數(shù)據(jù)，Nebula Graph 可以輕松處理數(shù)十億人和數(shù)萬億人際關系的社交網(wǎng)絡信息，并在海量并發(fā)的情況下，提供快速的好友推薦和工作崗位查詢。

服務架構

架構總覽

Nebula Graph 由三種服務構成：Graph 服務、Meta 服務和 Storage 服務，是一種存儲與計算分離的架構。

每個服務都有可執(zhí)行的二進制文件和對應進程，用戶可以使用這些二進制文件在一個或多個計算機上部署 Nebula Graph 集群。

下圖展示了 Nebula Graph 集群的經(jīng)典架構。

Meta 服務

在 Nebula Graph 架構中，Meta 服務是由 nebula-metad 進程提供的，負責數(shù)據(jù)管理，例如 Schema 操作、集群管理和用戶權限管理等。

Graph 服務和 Storage 服務

Nebula Graph 采用計算存儲分離架構。Graph 服務負責處理計算請求，Storage 服務負責存儲數(shù)據(jù)。它們由不同的進程提供，Graph 服務是由 nebula-graphd 進程提供，Storage 服務是由 nebula-storaged 進程提供。計算存儲分離架構的優(yōu)勢如下：

易擴展

分布式架構保證了 Graph 服務和 Storage 服務的靈活性，方便擴容和縮容。

高可用

如果提供 Graph 服務的服務器有一部分出現(xiàn)故障，其余服務器可以繼續(xù)為客戶端提供服務，而且 Storage 服務存儲的數(shù)據(jù)不會丟失。服務恢復速度較快，甚至能做到用戶無感知。

節(jié)約成本

計算存儲分離架構能夠提高資源利用率，而且可根據(jù)業(yè)務需求靈活控制成本。

更多可能性

基于分離架構的特性，Graph 服務將可以在更多類型的存儲引擎上單獨運行，Storage 服務也可以為多種目的計算引擎提供服務。

Meta 服務

Meta 服務架構

Meta 服務是由 nebula-metad 進程提供的，用戶可以根據(jù)場景配置 nebula-metad 進程數(shù)量：

• 測試環(huán)境中，用戶可以在 Nebula Graph 集群中部署 1 個或 3 個 nebula-metad 進程。如果要部署 3 個，用戶可以將它們部署在 1 臺機器上，或者分別部署在不同的機器上。
• 生產(chǎn)環(huán)境中，建議在 Nebula Graph 集群中部署 3 個 nebula-metad 進程。請將這些進程部署在不同的機器上以保證高可用。

所有 nebula-metad 進程構成了基于 Raft 協(xié)議的集群，其中一個進程是 leader，其他進程都是 follower。

leader 是由多數(shù)派選舉出來，只有 leader 能夠對客戶端或其他組件提供服務，其他 follower 作為候補，如果 leader 出現(xiàn)故障，會在所有 follower 中選舉出新的 leader。

leader 和 follower 的數(shù)據(jù)通過 Raft 協(xié)議保持一致，因此 leader 故障和選舉新 leader 不會導致數(shù)據(jù)不一致。更多關于 Raft 的介紹見 Storage 服務

Meta 服務功能

管理用戶賬號

Meta 服務中存儲了用戶的賬號和權限信息，當客戶端通過賬號發(fā)送請求給 Meta 服務，Meta 服務會檢查賬號信息，以及該賬號是否有對應的請求權限。

更多 Nebula Graph 的訪問控制說明，請參見身份驗證。

管理分片

Meta 服務負責存儲和管理分片的位置信息，并且保證分片的負載均衡。

管理圖空間

Nebula Graph 支持多個圖空間，不同圖空間內的數(shù)據(jù)是安全隔離的。Meta 服務存儲所有圖空間的元數(shù)據(jù)（非完整數(shù)據(jù)），并跟蹤數(shù)據(jù)的變更，例如增加或刪除圖空間。

管理 Schema 信息

Nebula Graph 是強類型圖數(shù)據(jù)庫，它的 Schema 包括 Tag、Edge type、Tag 屬性和 Edge type 屬性。

Meta 服務中存儲了 Schema 信息，同時還負責 Schema 的添加、修改和刪除，并記錄它們的版本。

更多 Nebula Graph 的 Schema 信息，請參見數(shù)據(jù)模型。

管理 TTL 信息

Meta 服務存儲 TTL（Time To Live）定義信息，可以用于設置數(shù)據(jù)生命周期。數(shù)據(jù)過期后，會由 Storage 服務進行處理，具體過程參見 TTL。

管理作業(yè)

Meta 服務中的作業(yè)管理模塊負責作業(yè)的創(chuàng)建、排隊、查詢和刪除。

Graph服務

Graph 服務主要負責處理查詢請求，包括解析查詢語句、校驗語句、生成執(zhí)行計劃以及按照執(zhí)行計劃執(zhí)行四個大步驟，本文將基于這些步驟介紹 Graph 服務。

Graph 服務架構

查詢請求發(fā)送到 Graph 服務后，會由如下模塊依次處理：

1. Parser：詞法語法解析模塊。
2. Validator：語義校驗模塊。
3. Planner：執(zhí)行計劃與優(yōu)化器模塊。
4. Executor：執(zhí)行引擎模塊。

Parser

Parser 模塊收到請求后，通過 Flex（詞法分析工具）和 Bison（語法分析工具）生成的詞法語法解析器，將語句轉換為抽象語法樹（AST），在語法解析階段會攔截不符合語法規(guī)則的語句。

例如GO FROM "Tim" OVER like WHERE properties(edge).likeness > 8.0 YIELD dst(edge)語句轉換的 AST 如下。

Validator

Validator 模塊對生成的 AST 進行語義校驗，主要包括：

校驗元數(shù)據(jù)信息

校驗語句中的元數(shù)據(jù)信息是否正確。

例如解析 OVER、WHERE和YIELD 語句時，會查找 Schema 校驗 Edge type、Tag 的信息是否存在，或者插入數(shù)據(jù)時校驗插入的數(shù)據(jù)類型和 Schema 中的是否一致。

校驗上下文引用信息

校驗引用的變量是否存在或者引用的屬性是否屬于變量。

例如語句$var = GO FROM "Tim" OVER like YIELD dst(edge) AS ID; GO FROM $var.ID OVER serve YIELD dst(edge)，Validator 模塊首先會檢查變量 var 是否定義，其次再檢查屬性 ID 是否屬于變量 var。

校驗類型推斷

推斷表達式的結果類型，并根據(jù)子句校驗類型是否正確。

例如 WHERE 子句要求結果是 bool、null 或者 empty。

校驗 * 代表的信息

查詢語句中包含 * 時，校驗子句時需要將 * 涉及的 Schema 都進行校驗。

例如語句GO FROM "Tim" OVER * YIELD dst(edge), properties(edge).likeness, dst(edge)，校驗OVER子句時需要校驗所有的 Edge type，如果 Edge type 包含 like和serve，該語句會展開為GO FROM "Tim" OVER like,serve YIELD dst(edge), properties(edge).likeness, dst(edge)。

校驗輸入輸出

校驗管道符（|）前后的一致性。

例如語句GO FROM "Tim" OVER like YIELD dst(edge) AS ID | GO FROM $-.ID OVER serve YIELD dst(edge)，Validator 模塊會校驗 $-.ID 在管道符左側是否已經(jīng)定義。

校驗完成后，Validator 模塊還會生成一個默認可執(zhí)行，但是未進行優(yōu)化的執(zhí)行計劃，存儲在目錄 src/planner 內。

Planner

如果配置文件 nebula-graphd.conf 中 enable_optimizer 設置為 false，Planner 模塊不會優(yōu)化 Validator 模塊生成的執(zhí)行計劃，而是直接交給 Executor 模塊執(zhí)行。

如果配置文件 nebula-graphd.conf中enable_optimizer 設置為 true，Planner 模塊會對 Validator 模塊生成的執(zhí)行計劃進行優(yōu)化。如下圖所示。

優(yōu)化前

如上圖右側未優(yōu)化的執(zhí)行計劃，每個節(jié)點依賴另一個節(jié)點，例如根節(jié)點 Project 依賴 Filter、Filter 依賴 GetNeighbor，最終找到葉子節(jié)點 Start，才能開始執(zhí)行（并非真正執(zhí)行）。

在這個過程中，每個節(jié)點會有對應的輸入變量和輸出變量，這些變量存儲在一個哈希表中。由于執(zhí)行計劃不是真正執(zhí)行，所以哈希表中每個 key 的 value 值都為空（除了 Start 節(jié)點，起始數(shù)據(jù)會存儲在該節(jié)點的輸入變量中）。哈希表定義在倉庫 nebula-graph 內的 src/context/ExecutionContext.cpp 中。

例如哈希表的名稱為 ResultMap，在建立 Filter 這個節(jié)點時，定義該節(jié)點從 ResultMap["GN1"] 中讀取數(shù)據(jù)，然后將結果存儲在 ResultMap["Filter2"] 中，依次類推，將每個節(jié)點的輸入輸出都確定好。

優(yōu)化過程

Planner 模塊目前的優(yōu)化方式是 RBO（rule-based optimization），即預定義優(yōu)化規(guī)則，然后對 Validator 模塊生成的默認執(zhí)行計劃進行優(yōu)化。新的優(yōu)化規(guī)則 CBO（cost-based optimization）正在開發(fā)中。優(yōu)化代碼存儲在倉庫 nebula-graph 的目錄 src/optimizer/ 內。

RBO 是一個自底向上的探索過程，即對于每個規(guī)則而言，都會由執(zhí)行計劃的根節(jié)點（示例是Project）開始，一步步向下探索到最底層的節(jié)點，在過程中查看是否可以匹配規(guī)則。

如上圖所示，探索到節(jié)點 Filter 時，發(fā)現(xiàn)依賴的節(jié)點是 GetNeighbor，匹配預先定義的規(guī)則，就會將 Filter 融入到 GetNeighbor 中，然后移除節(jié)點 Filter，繼續(xù)匹配下一個規(guī)則。在執(zhí)行階段，當算子 GetNeighbor 調用 Storage 服務的接口獲取一個點的鄰邊時，Storage 服務內部會直接將不符合條件的邊過濾掉，這樣可以極大地減少傳輸?shù)臄?shù)據(jù)量，該優(yōu)化稱為過濾下推。

Executor

Executor 模塊包含調度器（Scheduler）和執(zhí)行器（Executor），通過調度器調度執(zhí)行計劃，讓執(zhí)行器根據(jù)執(zhí)行計劃生成對應的執(zhí)行算子，從葉子節(jié)點開始執(zhí)行，直到根節(jié)點結束。如下圖所示。

每一個執(zhí)行計劃節(jié)點都一一對應一個執(zhí)行算子，節(jié)點的輸入輸出在優(yōu)化執(zhí)行計劃時已經(jīng)確定，每個算子只需要拿到輸入變量中的值進行計算，最后將計算結果放入對應的輸出變量中即可，所以只需要從節(jié)點 Start 一步步執(zhí)行，最后一個算子的輸出變量會作為最終結果返回給客戶端。

代碼結構

Nebula Graph 的代碼層次結構如下：

|--src
   |--context    //校驗期和執(zhí)行期上下文
   |--daemons
   |--executor   //執(zhí)行算子
   |--mock
   |--optimizer  //優(yōu)化規(guī)則
   |--parser     //詞法語法分析
   |--planner    //執(zhí)行計劃結構
   |--scheduler  //調度器
   |--service
   |--util       //基礎組件
   |--validator  //語句校驗
   |--visitor

Storage服務

Nebula Graph 的存儲包含兩個部分，一個是 Meta 相關的存儲，稱為 Meta 服務，在前文已有介紹。

另一個是具體數(shù)據(jù)相關的存儲，稱為 Storage 服務。其運行在 nebula-storaged 進程中。本文僅介紹 Storage 服務的架構設計。

優(yōu)勢

• 高性能（自研 KVStore）
• 易水平擴展（Shared-nothing 架構，不依賴 NAS 等硬件設備）
• 強一致性（Raft）
• 高可用性（Raft）
• 支持向第三方系統(tǒng)進行同步（例如全文索引）

Storage 服務架構

Storage 服務是由 nebula-storaged 進程提供的，用戶可以根據(jù)場景配置 nebula-storaged 進程數(shù)量，例如測試環(huán)境 1 個，生產(chǎn)環(huán)境 3 個。

所有 nebula-storaged 進程構成了基于 Raft 協(xié)議的集群，整個服務架構可以分為三層，從上到下依次為：

Storage interface 層

Storage 服務的最上層，定義了一系列和圖相關的 API。API 請求會在這一層被翻譯成一組針對分片的 KV 操作，例如：

• getNeighbors：查詢一批點的出邊或者入邊，返回邊以及對應的屬性，并且支持條件過濾。
• insert vertex/edge：插入一條點或者邊及其屬性。
• getProps：獲取一個點或者一條邊的屬性。

正是這一層的存在，使得 Storage 服務變成了真正的圖存儲，否則 Storage 服務只是一個 KV 存儲服務。

Consensus 層

Storage 服務的中間層，實現(xiàn)了 Multi Group Raft，保證強一致性和高可用性。

Store Engine 層

Storage 服務的最底層，是一個單機版本地存儲引擎，提供對本地數(shù)據(jù)的get、put、scan等操作。相關接口存儲在KVStore.h和KVEngine.h文件，用戶可以根據(jù)業(yè)務需求定制開發(fā)相關的本地存儲插件。

KVStore

Nebula Graph 使用自行開發(fā)的 KVStore，而不是其他開源 KVStore，原因如下：

• 需要高性能 KVStore。
• 需要以庫的形式提供，實現(xiàn)高效計算下推。對于強 Schema 的 Nebula Graph 來說，計算下推時如何提供 Schema 信息，是高效的關鍵。
• 需要數(shù)據(jù)強一致性。

基于上述原因，Nebula Graph 使用 RocksDB 作為本地存儲引擎，實現(xiàn)了自己的 KVStore，有如下優(yōu)勢：

• 對于多硬盤機器，Nebula Graph 只需配置多個不同的數(shù)據(jù)目錄即可充分利用多硬盤的并發(fā)能力。
• 由 Meta 服務統(tǒng)一管理所有 Storage 服務，可以根據(jù)所有分片的分布情況和狀態(tài)，手動進行負載均衡。
• 定制預寫日志（WAL），每個分片都有自己的 WAL。
• 支持多個圖空間，不同圖空間相互隔離，每個圖空間可以設置自己的分片數(shù)和副本數(shù)。

數(shù)據(jù)存儲格式

圖存儲的主要數(shù)據(jù)是點和邊，Nebula Graph 將點和邊的信息存儲為 key，同時將點和邊的屬性信息存儲在 value 中，以便更高效地使用屬性過濾。

點數(shù)據(jù)存儲格式

相比 Nebula Graph 2.x 版本，3.x 版本的每個點多了一個不含 TagID 字段并且無 value 的 key，用于支持無 Tag 的點。

邊數(shù)據(jù)存儲格式

屬性說明

Nebula Graph 使用強類型 Schema。

對于點或邊的屬性信息，Nebula Graph 會將屬性信息編碼后按順序存儲。由于屬性的長度是固定的，查詢時可以根據(jù)偏移量快速查詢。在解碼之前，需要先從 Meta 服務中查詢具體的 Schema 信息（并緩存）。同時為了支持在線變更 Schema，在編碼屬性時，會加入對應的 Schema 版本信息。

數(shù)據(jù)分片

由于超大規(guī)模關系網(wǎng)絡的節(jié)點數(shù)量高達百億到千億，而邊的數(shù)量更會高達萬億，即使僅存儲點和邊兩者也遠大于一般服務器的容量。因此需要有方法將圖元素切割，并存儲在不同邏輯分片（Partition）上。Nebula Graph 采用邊分割的方式。

切邊與存儲放大

Nebula Graph 中邏輯上的一條邊對應著硬盤上的兩個鍵值對（key-value pair），在邊的數(shù)量和屬性較多時，存儲放大現(xiàn)象較明顯。邊的存儲方式如下圖所示。

上圖以最簡單的兩個點和一條邊為例，起點 SrcVertex 通過邊 EdgeA 連接目的點 DstVertex，形成路徑(SrcVertex)-[EdgeA]->(DstVertex)。這兩個點和一條邊會以 6 個鍵值對的形式保存在存儲層的兩個不同分片，即 Partition x 和 Partition y 中，詳細說明如下：

• 點 SrcVertex 的鍵值保存在 Partition x 中。
• 邊 EdgeA 的第一份鍵值，這里用 EdgeA_Out 表示，與 SrcVertex 一同保存在 Partition x 中。key 的字段有 Type、PartID（x）、VID（Src，即點 SrcVertex 的 ID）、EdgeType（符號為正，代表邊方向為出）、Rank（0）、VID（Dst，即點 DstVertex 的 ID）和 PlaceHolder。SerializedValue 即 Value，是序列化的邊屬性。
• 點 DstVertex 的鍵值保存在 Partition y 中。
• 邊 EdgeA 的第二份鍵值，這里用 EdgeA_In 表示，與 DstVertex 一同保存在 Partition y 中。key 的字段有 Type、PartID（y）、VID（Dst，即點 DstVertex 的 ID）、EdgeType（符號為負，代表邊方向為入）、Rank（0）、VID（Src，即點 SrcVertex 的 ID）和 PlaceHolder。SerializedValue 即 Value，是序列化的邊屬性，與 EdgeA_Out 中該部分的完全相同。

EdgeA_Out 和 EdgeA_In 以方向相反的兩條邊的形式存在于存儲層，二者組合成了邏輯上的一條邊 EdgeA。EdgeA_Out 用于從起點開始的遍歷請求，例如(a)-[]->()；EdgeA_In 用于指向目的點的遍歷請求，或者說從目的點開始，沿著邊的方向逆序進行的遍歷請求，例如例如()-[]->(a)。

如 EdgeA_Out 和 EdgeA_In 一樣，Nebula Graph 冗余了存儲每條邊的信息，導致存儲邊所需的實際空間翻倍。因為邊對應的 key 占用的硬盤空間較小，但 value 占用的空間與屬性值的長度和數(shù)量成正比，所以，當邊的屬性值較大或數(shù)量較多時候，硬盤空間占用量會比較大。

如果對邊進行操作，為了保證兩個鍵值對的最終一致性，可以開啟 TOSS 功能，開啟后，會先在正向邊所在的分片進行操作，然后在反向邊所在分片進行操作，最后返回結果。

分片算法

分片策略采用靜態(tài) Hash 的方式，即對點 VID 進行取模操作，同一個點的所有 Tag、出邊和入邊信息都會存儲到同一個分片，這種方式極大地提升了查詢效率。

創(chuàng)建圖空間時需指定分片數(shù)量，分片數(shù)量設置后無法修改，建議設置時提前滿足業(yè)務將來的擴容需求。

多機集群部署時，分片分布在集群內的不同機器上。分片數(shù)量在 CREATE SPACE 語句中指定，此后不可更改。

如果需要將某些點放置在相同的分片（例如在一臺機器上），可以參考公式或代碼。

下文用簡單代碼說明 VID 和分片的關系。

// 如果 ID 長度為 8，為了兼容 1.0，將數(shù)據(jù)類型視為 int64。
uint64_t vid = 0;
        if (id.size() == 8) {
        memcpy(static_cast<void*>(&vid), id.data(), 8);
        } else {
        MurmurHash2 hash;
        vid = hash(id.data());
        }
        PartitionID pId = vid % numParts + 1;

簡單來說，上述代碼是將一個固定的字符串進行哈希計算，轉換成數(shù)據(jù)類型為 int64 的數(shù)字（int64 數(shù)字的哈希計算結果是數(shù)字本身），將數(shù)字取模，然后加 1，即：

pId = vid % numParts + 1;

示例的部分參數(shù)說明如下。

例如有 100 個分片，VID為 1、101 和 1001 的三個點將會存儲在相同的分片。分片 ID 和機器地址之間的映射是隨機的，所以不能假定任何兩個分片位于同一臺機器上。

Raft

關于 Raft 的簡單介紹

分布式系統(tǒng)中，同一份數(shù)據(jù)通常會有多個副本，這樣即使少數(shù)副本發(fā)生故障，系統(tǒng)仍可正常運行。這就需要一定的技術手段來保證多個副本之間的一致性。

基本原理：Raft 就是一種用于保證多副本一致性的協(xié)議。Raft 采用多個副本之間競選的方式，贏得”超過半數(shù)”副本投票的（候選）副本成為 Leader，由 Leader 代表所有副本對外提供服務；其他 Follower 作為備份。當該 Leader 出現(xiàn)異常后（通信故障、運維命令等），其余 Follower 進行新一輪選舉，投票出一個新的 Leader。Leader 和 Follower 之間通過心跳的方式相互探測是否存活，并以 Raft-wal 的方式寫入硬盤，超過多個心跳仍無響應的副本會認為發(fā)生故障。

因為 Raft-wal 需要定期寫硬盤，如果硬盤寫能力瓶頸會導致 Raft 心跳失敗，導致重新發(fā)起選舉。硬盤 IO 嚴重堵塞情況下，會導致長期無法選舉出 Leader。

讀寫流程：對于客戶端的每個寫入請求，Leader 會將該寫入以 Raft-wal 的方式，將該條同步給其他 Follower，并只有在“超過半數(shù)”副本都成功收到 Raft-wal 后，才會返回客戶端該寫入成功。對于客戶端的每個讀取請求，都直接訪問 Leader，而 Follower 并不參與讀請求服務。

故障流程：場景 1：考慮一個配置為單副本（圖空間）的集群；如果系統(tǒng)只有一個副本時，其自身就是 Leader；如果其發(fā)生故障，系統(tǒng)將完全不可用。場景 2：考慮一個配置為 3 副本（圖空間）的集群；如果系統(tǒng)有 3 個副本，其中一個副本是 Leader，其他 2 個副本是 Follower；即使原 Leader 發(fā)生故障，剩下兩個副本仍可投票出一個新的 Leader（以及一個 Follower），此時系統(tǒng)仍可使用；但是當這 2 個副本中任一者再次發(fā)生故障后，由于投票人數(shù)不足，系統(tǒng)將完全不可用。

Raft 多副本的方式與 HDFS 多副本的方式是不同的，Raft 基于“多數(shù)派”投票，因此副本數(shù)量不能是偶數(shù)。

Multi Group Raft

由于 Storage 服務需要支持集群分布式架構，所以基于 Raft 協(xié)議實現(xiàn)了 Multi Group Raft，即每個分片的所有副本共同組成一個 Raft group，其中一個副本是 leader，其他副本是 follower，從而實現(xiàn)強一致性和高可用性。Raft 的部分實現(xiàn)如下。

由于 Raft 日志不允許空洞，Nebula Graph 使用 Multi Group Raft 緩解此問題，分片數(shù)量較多時，可以有效提高 Nebula Graph 的性能。但是分片數(shù)量太多會增加開銷，例如 Raft group 內部存儲的狀態(tài)信息、WAL 文件，或者負載過低時的批量操作。

實現(xiàn) Multi Group Raft 有 2 個關鍵點：

• 共享 Transport 層

每一個 Raft group 內部都需要向對應的 peer 發(fā)送消息，如果不能共享 Transport 層，會導致連接的開銷巨大。

• 共享線程池

如果不共享一組線程池，會造成系統(tǒng)的線程數(shù)過多，導致大量的上下文切換開銷。

批量（Batch）操作

Nebula Graph 中，每個分片都是串行寫日志，為了提高吞吐，寫日志時需要做批量操作，但是由于 Nebula Graph 利用 WAL 實現(xiàn)一些特殊功能，需要對批量操作進行分組，這是 Nebula Graph 的特色。

例如無鎖 CAS 操作需要之前的 WAL 全部提交后才能執(zhí)行，如果一個批量寫入的 WAL 里包含了 CAS 類型的 WAL，就需要拆分成粒度更小的幾個組，還要保證這幾組 WAL 串行提交。

leader 切換（Transfer Leadership）

leader 切換對于負載均衡至關重要，當把某個分片從一臺機器遷移到另一臺機器時，首先會檢查分片是不是 leader，如果是的話，需要先切換 leader，數(shù)據(jù)遷移完畢之后，通常還要重新均衡 leader 分布。

對于 leader 來說，提交 leader 切換命令時，就會放棄自己的 leader 身份，當 follower 收到 leader 切換命令時，就會發(fā)起選舉。

成員變更

為了避免腦裂，當一個 Raft group 的成員發(fā)生變化時，需要有一個中間狀態(tài)，該狀態(tài)下新舊 group 的多數(shù)派需要有重疊的部分，這樣就防止了新的 group 或舊的 group 單方面做出決定。為了更加簡化，Diego Ongaro 在自己的博士論文中提出每次只增減一個 peer 的方式，以保證新舊 group 的多數(shù)派總是有重疊。Nebula Graph 也采用了這個方式，只不過增加成員和移除成員的實現(xiàn)有所區(qū)別。具體實現(xiàn)方式請參見 Raft Part class 里 addPeer/removePeer 的實現(xiàn)。

與 HDFS 的區(qū)別

Storage 服務基于 Raft 協(xié)議實現(xiàn)的分布式架構，與 HDFS 的分布式架構有一些區(qū)別。例如：

• Storage 服務本身通過 Raft 協(xié)議保證一致性，副本數(shù)量通常為奇數(shù)，方便進行選舉 leader，而 HDFS 存儲具體數(shù)據(jù)的 DataNode 需要通過 NameNode 保證一致性，對副本數(shù)量沒有要求。
• Storage 服務只有 leader 副本提供讀寫服務，而 HDFS 的所有副本都可以提供讀寫服務。
• Storage 服務無法修改副本數(shù)量，只能在創(chuàng)建圖空間時指定副本數(shù)量，而 HDFS 可以調整副本數(shù)量。
• Storage 服務是直接訪問文件系統(tǒng)，而 HDFS 的上層（例如 HBase）需要先訪問 HDFS，再訪問到文件系統(tǒng)，遠程過程調用（RPC）次數(shù)更多。

總而言之，Storage 服務更加輕量級，精簡了一些功能，架構沒有 HDFS 復雜，可以有效提高小塊存儲的讀寫性能。

參考文章

• https://docs.nebula-graph.com.cn/3.0.1/

文章收錄于 GitHub倉庫JavaDeveloperBrain [Java工程師必備+學習+知識點+面試]：包含計算機網(wǎng)絡知識、JavaSE、JVM、Spring、Springboot、SpringCloud、Mybatis、多線程并發(fā)、netty、MySQL、MongoDB、Elasticsearch、Redis、HBASE、RabbitMQ、RocketMQ、Pulsar、Kafka、Zookeeper、Linux、設計模式、智力題、項目架構、分布式相關、算法、面試題文章來源地址http://www.zghlxwxcb.cn/news/detail-742756.html

到了這里，關于Nebula Graph開源分布式圖數(shù)據(jù)庫,萬億級數(shù)據(jù),毫秒級延時的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！