摘要
在討論某個數(shù)據(jù)庫時，存儲 ( Storage ) 和計算 ( Query Engine ) 通常是討論的熱點拯钻，也是愛好者們了解某個數(shù)據(jù)庫不可或缺的部分伞剑。每個數(shù)據(jù)庫都有其獨有的存儲、計算方式怒允，今天就和圖圖來學習下圖數(shù)據(jù)庫 Nebula Graph 的存儲部分柑潦。
Nebula 的 Storage 包含兩個部分享言， 一是 meta 相關(guān)的存儲， 我們稱之為 Meta Service 渗鬼，另一個是 data 相關(guān)的存儲担锤， 我們稱之為 Storage Service。 這兩個服務是兩個獨立的進程乍钻，數(shù)據(jù)也完全隔離肛循，當然部署也是分別部署铭腕， 不過兩者整體架構(gòu)相差不大，本文最后會提到這點多糠。 如果沒有特殊說明累舷，本文中 Storage Service 代指 data 的存儲服務。接下來夹孔，大家就隨我一起看一下 Storage Service 的整個架構(gòu)被盈。 Let's go~
Architecture
圖一 storage service 架構(gòu)圖
如圖1 所示，Storage Service 共有三層搭伤，最底層是 Store Engine只怎，它是一個單機版 local store engine，提供了對本地數(shù)據(jù)的 get / put / scan / delete 操作怜俐，相關(guān)的接口放在 KVStore / KVEngine.h 文件里面身堡，用戶完全可以根據(jù)自己的需求定制開發(fā)相關(guān) local store plugin，目前 Nebula 提供了基于 RocksDB 實現(xiàn)的 Store Engine拍鲤。
在 local store engine 之上贴谎，便是我們的 Consensus 層，實現(xiàn)了 Multi Group Raft季稳，每一個 Partition 都對應了一組 Raft Group擅这，這里的 Partition 便是我們的數(shù)據(jù)分片。目前 Nebula 的分片策略采用了 靜態(tài) Hash 的方式景鼠，具體按照什么方式進行 Hash仲翎，在下一個章節(jié) schema 里會提及。用戶在創(chuàng)建 SPACE 時需指定 Partition 數(shù)铛漓，Partition 數(shù)量一旦設(shè)置便不可更改溯香，一般來講，Partition 數(shù)目要能滿足業(yè)務將來的擴容需求票渠。
在 Consensus 層上面也就是 Storage Service 的最上層逐哈，便是我們的 Storage interfaces芬迄，這一層定義了一系列和圖相關(guān)的 API问顷。 這些 API 請求會在這一層被翻譯成一組針對相應 Partition 的 kv 操作。正是這一層的存在禀梳，使得我們的存儲服務變成了真正的圖存儲杜窄，否則，Storage Service 只是一個 kv 存儲罷了算途。而 Nebula 沒把 kv 作為一個服務單獨提出塞耕，其最主要的原因便是圖查詢過程中會涉及到大量計算，這些計算往往需要使用圖的 schema嘴瓤，而 kv 層是沒有數(shù)據(jù) schema 概念扫外，這樣設(shè)計會比較容易實現(xiàn)計算下推莉钙。
Schema & Partition
圖存儲的主要數(shù)據(jù)是點和邊，但 Nebula 存儲的數(shù)據(jù)是一張屬性圖筛谚，也就是說除了點和邊以外磁玉，Nebula 還存儲了它們對應的屬性，以便更高效地使用屬性過濾驾讲。
對于點來說蚊伞，我們使用不同的 Tag 表示不同類型的點，同一個 VertexID 可以關(guān)聯(lián)多個 Tag吮铭，而每一個 Tag 都有自己對應的屬性时迫。對應到 kv 存儲里面，我們使用 vertexID + TagID 來表示 key, 我們把相關(guān)的屬性編碼后放在 value 里面谓晌，具體 key 的 format 如圖2 所示：
圖二 Vertex Key Format
-
Type: 1 個字節(jié)掠拳，用來表示 key 類型，當前的類型有 data, index, system 等 -
Part ID: 3 個字節(jié)扎谎，用來表示數(shù)據(jù)分片 Partition碳想，此字段主要用于 Partition 重新分布(balance) 時方便根據(jù)前綴掃描整個 Partition 數(shù)據(jù) -
Vertex ID: 4 個字節(jié)， 用來表示點的 ID -
Tag ID: 4 個字節(jié), 用來表示關(guān)聯(lián)的某個 tag -
Timestamp: 8 個字節(jié)毁靶，對用戶不可見胧奔，未來實現(xiàn)分布式事務 ( MVCC ) 時使用
在一個圖中，每一條邏輯意義上的邊预吆，在 Nebula Graph 中會建模成兩個獨立的 key-value龙填，分別稱為 out-key 和in-key。out-key 與這條邊所對應的起點存儲在同一個 partition 上拐叉，in-key 與這條邊所對應的終點存儲在同一個partition 上岩遗。通常來說，out-key 和 in-key 會分布在兩個不同的 Partition 中凤瘦。
兩個點之間可能存在多種類型的邊宿礁，Nebula 用 Edge Type 來表示邊類型。而同一類型的邊可能存在多條蔬芥，比如梆靖，定義一個 edge type "轉(zhuǎn)賬"，用戶 A 可能多次轉(zhuǎn)賬給 B笔诵， 所以 Nebula 又增加了一個 Rank 字段來做區(qū)分返吻，表示 A 到 B 之間多次轉(zhuǎn)賬記錄。 Edge key 的 format 如圖3 所示：
圖三 Edge Key Format
-
Type: 1 個字節(jié)乎婿，用來表示 key 的類型测僵，當前的類型有 data, index, system 等。 -
Part ID: 3 個字節(jié)谢翎，用來表示數(shù)據(jù)分片 Partition捍靠，此字段主要用于 Partition 重新分布(balance) 時方便根據(jù)前綴掃描整個 Partition 數(shù)據(jù) -
Vertex ID: 4 個字節(jié)沐旨， 出邊里面用來表示源點的 ID， 入邊里面表示目標點的 ID榨婆。 -
Edge Type: 4 個字節(jié), 用來表示這條邊的類型希俩，如果大于 0 表示出邊，小于 0 表示入邊纲辽。 -
Rank: 8 個字節(jié)颜武，用來處理同一種類型的邊存在多條的情況。用戶可以根據(jù)自己的需求進行設(shè)置拖吼，這個字段可存放交易時間鳞上、交易流水號、或某個排序權(quán)重 -
Vertex ID: 4 個字節(jié), 出邊里面用來表示目標點的 ID吊档， 入邊里面表示源點的 ID篙议。 -
Timestamp: 8 個字節(jié)，對用戶不可見怠硼，未來實現(xiàn)分布式做事務的時候使用鬼贱。
針對 Edge Type 的值，若如果大于 0 表示出邊香璃，則對應的 edge key format 如圖4 所示这难；若 Edge Type 的值小于 0，則對應的 edge key format 如圖5 所示
圖4 出邊的 Key Format
圖5 入邊的 Key Format
對于點或邊的屬性信息葡秒，有對應的一組 kv pairs姻乓，Nebula 將它們編碼后存在對應的 value 里。由于 Nebula 使用強類型 schema眯牧，所以在解碼之前蹋岩，需要先去 Meta Service 中取具體的 schema 信息。另外学少，為了支持在線變更 schema剪个，在編碼屬性時，會加入對應的 schema 版本信息版确，具體的編解碼細節(jié)在這里不作展開扣囊，后續(xù)會有專門的文章講解這塊內(nèi)容。
OK阀坏，到這里我們基本上了解了 Nebula 是如何存儲數(shù)據(jù)的如暖，那數(shù)據(jù)是如何進行分片呢笆檀？很簡單忌堂，對 Vertex ID 取模 即可。通過對 Vertex ID 取模酗洒，同一個點的所有出邊士修，入邊以及這個點上所有關(guān)聯(lián)的 Tag 信息都會被分到同一個 Partition枷遂，這種方式大大地提升了查詢效率。對于在線圖查詢來講棋嘲，最常見的操作便是從一個點開始向外 BFS（廣度優(yōu)先）拓展酒唉，于是拿一個點的出邊或者入邊是最基本的操作，而這個操作的性能也決定了整個遍歷的性能沸移。BFS 中可能會出現(xiàn)按照某些屬性進行剪枝的情況痪伦，Nebula 通過將屬性與點邊存在一起，來保證整個操作的高效雹锣。當前許多的圖數(shù)據(jù)庫通過 Graph 500 或者 Twitter 的數(shù)據(jù)集試來驗證自己的高效性网沾，這并沒有代表性，因為這些數(shù)據(jù)集沒有屬性蕊爵，而實際的場景中大部分情況都是屬性圖辉哥，并且實際中的 BFS 也需要進行大量的剪枝操作。
KVStore
為什么要自己做 KVStore攒射，這是我們無數(shù)次被問起的問題醋旦。理由很簡單，當前開源的 KVStore 都很難滿足我們的要求：
- 性能会放，性能饲齐，性能：Nebula 的需求很直接：高性能 pure kv；
- 以 library 的形式提供：對于強 schema 的 Nebula 來講咧最，計算下推需要 schema 信息箩张，而計算下推實現(xiàn)的好壞，是 Nebula 是否高效的關(guān)鍵窗市；
- 數(shù)據(jù)強一致：這是分布式系統(tǒng)決定的先慷；
- 使用 C++實現(xiàn)：這由團隊的技術(shù)特點決定；
基于上述要求咨察，Nebula 實現(xiàn)了自己的 KVStore论熙。當然，對于性能完全不敏感且不太希望搬遷數(shù)據(jù)的用戶來說摄狱，Nebula 也提供了整個KVStore 層的 plugin脓诡，直接將 Storage Service 搭建在第三方的 KVStore 上面，目前官方提供的是 HBase 的 plugin媒役。
Nebula KVStore 主要采用 RocksDB 作為本地的存儲引擎祝谚，對于多硬盤機器，為了充分利用多硬盤的并發(fā)能力酣衷，Nebula 支持自己管理多塊盤交惯，用戶只需配置多個不同的數(shù)據(jù)目錄即可。分布式 KVStore 的管理由 Meta Service 來統(tǒng)一調(diào)度，它記錄了所有 Partition 的分布情況席爽，以及當前機器的狀態(tài)意荤，當用戶增減機器時，只需要通過 console 輸入相應的指令只锻，Meta Service 便能夠生成整個 balance plan 并執(zhí)行玖像。（之所以沒有采用完全自動 balance 的方式，主要是為了減少數(shù)據(jù)搬遷對于線上服務的影響齐饮，balance 的時機由用戶自己控制捐寥。）
為了方便對于 WAL 進行定制，Nebula KVStore 實現(xiàn)了自己的 WAL 模塊祖驱，每個 partition 都有自己的 WAL上真，這樣在追數(shù)據(jù)時，不需要進行 wal split 操作羹膳， 更加高效睡互。 另外，為了實現(xiàn)一些特殊的操作陵像，專門定義了 Command Log 這個類別就珠，這些 log 只為了使用 Raft 來通知所有 replica 執(zhí)行某一個特定操作，并沒有真正的數(shù)據(jù)醒颖。除了 Command Log 外妻怎，Nebula 還提供了一類日志來實現(xiàn)針對某個 Partition 的 atomic operation，例如 CAS泞歉，read-modify-write, 它充分利用了Raft 串行的特性逼侦。
關(guān)于多圖空間（space）的支持：一個 Nebula KVStore 集群可以支持多個 space，每個 space 可設(shè)置自己的 partition 數(shù)和 replica 數(shù)腰耙。不同 space 在物理上是完全隔離的榛丢，而且在同一個集群上的不同 space 可支持不同的 store engine 及分片策略。
Raft
作為一個分布式系統(tǒng)挺庞，KVStore 的 replication晰赞，scale out 等功能需 Raft 的支持。當前选侨，市面上講 Raft 的文章非常多掖鱼，具體原理性的內(nèi)容，這里不再贅述援制，本文主要說一些 Nebula Raft 的一些特點以及工程實現(xiàn)戏挡。
Multi Raft Group
由于 Raft 的日志不允許空洞，幾乎所有的實現(xiàn)都會采用 Multi Raft Group 來緩解這個問題晨仑，因此 partition 的數(shù)目幾乎決定了整個 Raft Group 的性能褐墅。但這也并不是說 Partition 的數(shù)目越多越好：每一個 Raft Group 內(nèi)部都要存儲一系列的狀態(tài)信息拆檬，并且每一個 Raft Group 有自己的 WAL 文件，因此 Partition 數(shù)目太多會增加開銷掌栅。此外，當 Partition 太多時码泛， 如果負載沒有足夠高猾封，batch 操作是沒有意義的。比如噪珊，一個有 1w tps 的線上系統(tǒng)單機晌缘，它的單機 partition 的數(shù)目超過 1w，可能每個 Partition 每秒的 tps 只有 1痢站，這樣 batch 操作就失去了意義磷箕，還增加了 CPU 開銷。
實現(xiàn) Multi Raft Group 的最關(guān)鍵之處有兩點阵难，** 第一是共享 Transport 層岳枷，因為每一個 Raft Group 內(nèi)部都需要向?qū)?peer 發(fā)送消息，如果不能共享 Transport 層呜叫，連接的開銷巨大空繁；第二是線程模型**，Mutli Raft Group 一定要共享一組線程池朱庆，否則會造成系統(tǒng)的線程數(shù)目過多盛泡，導致大量的 context switch 開銷。
Batch
對于每個 Partition來說娱颊，由于串行寫 WAL傲诵，為了提高吞吐，做 batch 是十分必要的箱硕。一般來講拴竹，batch 并沒有什么特別的地方，但是 Nebula 利用每個 part 串行的特點剧罩，做了一些特殊類型的 WAL殖熟，帶來了一些工程上的挑戰(zhàn)。
舉個例子斑响，Nebula 利用 WAL 實現(xiàn)了無鎖的 CAS 操作菱属，而每個 CAS 操作需要之前的 WAL 全部 commit 之后才能執(zhí)行，所以對于一個 batch舰罚，如果中間夾雜了幾條 CAS 類型的 WAL, 我們還需要把這個 batch 分成粒度更小的幾個 group纽门，group 之間保證串行。還有营罢，command 類型的 WAL 需要它后面的 WAL 在其 commit 之后才能執(zhí)行赏陵，所以整個 batch 劃分 group 的操作工程實現(xiàn)上比較有特色饼齿。
Learner
Learner 這個角色的存在主要是為了 應對擴容 時，新機器需要"追"相當長一段時間的數(shù)據(jù)蝙搔，而這段時間有可能會發(fā)生意外缕溉。如果直接以 follower 的身份開始追數(shù)據(jù)，就會使得整個集群的 HA 能力下降吃型。 Nebula 里面 learner 的實現(xiàn)就是采用了上面提到的 command wal证鸥，leader 在寫 wal 時如果碰到 add learner 的 command， 就會將 learner 加入自己的 peers勤晚，并把它標記為 learner枉层，這樣在統(tǒng)計多數(shù)派的時候，就不會算上 learner赐写，但是日志還是會照常發(fā)送給它們鸟蜡。當然 learner 也不會主動發(fā)起選舉。
Transfer Leadership
Transfer leadership 這個操作對于 balance 來講至關(guān)重要挺邀，當我們把某個 Paritition 從一臺機器挪到另一臺機器時揉忘，首先便會檢查 source 是不是 leader，如果是的話端铛，需要先把他挪到另外的 peer 上面癌淮；在搬遷數(shù)據(jù)完畢之后，通常還要把 leader 進行一次 balance沦补，這樣每臺機器承擔的負載也能保證均衡乳蓄。
實現(xiàn) transfer leadership， 需要注意的是 leader 放棄自己的 leadership夕膀，和 follower 開始進行 leader election 的時機虚倒。對于 leader 來講，當 transfer leadership command 在 commit 的時候产舞，它放棄 leadership魂奥；而對于 follower 來講，當收到此 command 的時候就要開始進行 leader election易猫， 這套實現(xiàn)要和 Raft 本身的 leader election 走一套路徑耻煤，否則很容易出現(xiàn)一些難以處理的 corner case。
Membership change
為了避免腦裂准颓，當一個 Raft Group 的成員發(fā)生變化時哈蝇，需要有一個中間狀態(tài)， 這個狀態(tài)下 old group 的多數(shù)派與 new group 的多數(shù)派總是有 overlap攘已，這樣就防止了 old group 或者新 group 單方面做出決定炮赦，這就是論文中提到的 joint consensus 。為了更加簡化样勃，Diego Ongaro 在自己的博士論文中提出每次增減一個 peer 的方式吠勘，以保證 old group 的多數(shù)派總是與 new group 的多數(shù)派有 overlap性芬。 Nebula 的實現(xiàn)也采用了這個方式，只不過 add member 與 remove member 的實現(xiàn)有所區(qū)別剧防，具體實現(xiàn)方式本文不作討論植锉，有興趣的同學可以參考 Raft Part class 里面 addPeer / removePeer 的實現(xiàn)。
Snapshot
Snapshot 如何與 Raft 流程結(jié)合起來峭拘，論文中并沒有細講俊庇，但是這一部分我認為是一個 Raft 實現(xiàn)里最容易出錯的地方，因為這里會產(chǎn)生大量的 corner case棚唆。
舉一個例子暇赤，當 leader 發(fā)送 snapshot 過程中心例，如果 leader 發(fā)生了變化宵凌，該怎么辦？ 這個時候止后，有可能 follower 只接到了一半的 snapshot 數(shù)據(jù)瞎惫。 所以需要有一個 Partition 數(shù)據(jù)清理過程，由于多個 Partition 共享一份存儲译株，因此如何清理數(shù)據(jù)又是一個很麻煩的問題瓜喇。另外，snapshot 過程中歉糜，會產(chǎn)生大量的 IO乘寒，為了性能考慮，我們不希望這個過程與正常的 Raft 共用一個 IO threadPool匪补，并且整個過程中伞辛，還需要使用大量的內(nèi)存，如何優(yōu)化內(nèi)存的使用夯缺，對于性能十分關(guān)鍵蚤氏。由于篇幅原因，我們并不會在本文對這些問題展開講述踊兜，有興趣的同學可以參考 SnapshotManager 的實現(xiàn)竿滨。
Storage Service
在 KVStore 的接口之上，Nebula 封裝有圖語義接口捏境，主要的接口如下：
-
getNeighbors: 查詢一批點的出邊或者入邊于游，返回邊以及對應的屬性，并且需要支持條件過濾垫言； -
Insert vertex/edge: 插入一條點或者邊及其屬性曙砂； -
getProps: 獲取一個點或者一條邊的屬性；
這一層會將圖語義的接口轉(zhuǎn)化成 kv 操作骏掀。為了提高遍歷的性能鸠澈，還要做并發(fā)操作柱告。
Meta Service
在 KVStore 的接口上，Nebula 也同時封裝了一套 meta 相關(guān)的接口笑陈。Meta Service 不但提供了圖 schema 的增刪查改的功能际度，還提供了集群的管理功能以及用戶鑒權(quán)相關(guān)的功能。Meta Service 支持單獨部署涵妥，也支持使用多副本來保證數(shù)據(jù)的安全乖菱。
總結(jié)
這篇文章給大家大致介紹了 Nebula Storage 層的整體設(shè)計， 由于篇幅原因蓬网， 很多細節(jié)沒有展開講窒所， 歡迎大家到我們的微信群里提問，加入 Nebula Graph 交流群帆锋，請聯(lián)系 Nebula Graph 官方小助手微信號：NebulaGraphbot吵取。
相關(guān)閱讀
附錄
Nebula Graph：一個開源的分布式圖數(shù)據(jù)庫。
