image

導(dǎo)讀

索引是數(shù)據(jù)庫系統(tǒng)中不可或缺的一個功能麻养，數(shù)據(jù)庫索引好比是書的目錄夏志，能加快數(shù)據(jù)庫的查詢速度垒拢，其實質(zhì)是數(shù)據(jù)庫管理系統(tǒng)中一個排序的數(shù)據(jù)結(jié)構(gòu)健无。不同的數(shù)據(jù)庫系統(tǒng)有不同的排序結(jié)構(gòu)荣恐，目前常見的索引實現(xiàn)類型如 B-Tree index液斜、B+-Tree index累贤、B*-Tree index、Hash index少漆、Bitmap index臼膏、Inverted index 等等，各種索引類型都有各自的排序算法示损。

雖然索引可以帶來更高的查詢性能渗磅，但是也存在一些缺點，例如：

• 創(chuàng)建索引和維護(hù)索引要耗費(fèi)額外的時間,往往是隨著數(shù)據(jù)量的增加而維護(hù)成本增大
• 索引需要占用物理空間
• 在對數(shù)據(jù)進(jìn)行增刪改的操作時需要耗費(fèi)更多的時間,因為索引也要進(jìn)行同步的維護(hù)

Nebula Graph 作為一個高性能的分布式圖數(shù)據(jù)庫检访，對于屬性值的高性能查詢始鱼，同樣也實現(xiàn)了索引功能。本文將對 Nebula Graph的索引功能做一個詳細(xì)介紹脆贵。

圖數(shù)據(jù)庫 Nebula Graph 術(shù)語

開始之前医清，這里羅列一些可能會使用到的圖數(shù)據(jù)庫和 Nebula Graph 專有術(shù)語：

• Tag：點的屬性結(jié)構(gòu)，一個 Vertex 可以附加多種 tag卖氨，以 TagID 標(biāo)識会烙。（如果類比 SQL负懦，可以理解為一張點表）
• Edge：類似于 Tag，EdgeType 是邊上的屬性結(jié)構(gòu)柏腻，以 EdgeType 標(biāo)識纸厉。（如果類比 SQL，可以理解為一張邊表）
• Property：tag / edge 上的屬性值五嫂，其數(shù)據(jù)類型由 tag / edge 的結(jié)構(gòu)確定颗品。
• Partition：Nebula Graph 的最小邏輯存儲單元，一個 StorageEngine 可包含多個 Partition贫导。Partition 分為 leader 和 follower 的角色抛猫，Raftex 保證了 leader 和 follower 之間的數(shù)據(jù)一致性。
• Graph space：每個 Graph Space 是一個獨立的業(yè)務(wù) Graph 單元孩灯，每個 Graph Space 有其獨立的 tag 和 edge 集合闺金。一個 Nebula Graph 集群中可包含多個 Graph Space。
• Index：本文中出現(xiàn)的 Index 指 nebula graph 中點和邊上的屬性索引峰档。其數(shù)據(jù)類型依賴于 tag / edge败匹。
• TagIndex：基于 tag 創(chuàng)建的索引，一個 tag 可以創(chuàng)建多個索引讥巡。目前（2020.3）暫不支持跨 tag 的復(fù)合索引掀亩，因此一個索引只可以基于一個 tag。
• EdgeIndex：基于 Edge 創(chuàng)建的索引欢顷。同樣槽棍，一個 Edge 可以創(chuàng)建多個索引，但一個索引只可以基于一個 edge抬驴。
• Scan Policy：Index 的掃描策略炼七，往往一條查詢語句可以有多種索引的掃描方式，但具體使用哪種掃描方式需要 Scan Policy 來決定布持。
• Optimizer：對查詢條件進(jìn)行優(yōu)化豌拙，例如對 where 子句的表達(dá)式樹進(jìn)行子表達(dá)式節(jié)點的排序、分裂题暖、合并等按傅。其目的是獲取更高的查詢效率。

索引需求分析

Nebula Graph 是一個圖數(shù)據(jù)庫系統(tǒng)胧卤，查詢場景一般是由一個點出發(fā)唯绍，找出指定邊類型的相關(guān)點的集合，以此類推進(jìn)行（廣度優(yōu)先遍歷）N 度查詢枝誊。另一種查詢場景是給定一個屬性值况芒，找出符合這個屬性值的所有的點或邊。在后面這種場景中侧啼，需要對屬性值進(jìn)行高性能的掃描牛柒，查出與此屬性值對應(yīng)的邊或點堪簿，以及邊或點上的其它屬性。為了提高屬性值的查詢效率皮壁，在這里引入了索引的功能椭更。對邊或點的屬性值進(jìn)行排序，以便快速的定位到某個屬性上蛾魄。以此避免了全表掃描虑瀑。

可以看到對圖數(shù)據(jù)庫 Nebula Graph 的索引要求：

• 支持 tag 和 edge 的屬性索引
• 支持索引的掃描策略的分析和生成
• 支持索引的管理，如：新建索引滴须、重建索引舌狗、刪除索引、list | show 索引等扔水。

系統(tǒng)架構(gòu)概覽

圖數(shù)據(jù)庫 Nebula Graph 存儲架構(gòu)

image

從架構(gòu)圖可以看到痛侍，每個Storage Server 中可以包含多個 Storage Engine, 每個 Storage Engine中可以包含多個Partition, 不同的Partition之間通過 Raft 協(xié)議進(jìn)行一致性同步。每個 Partition 中既包含了 data魔市，也包含了 index主届，同一個點或邊的 data 和 index 將被存儲到同一個 Partition 中。

業(yè)務(wù)具體分析

數(shù)據(jù)存儲結(jié)構(gòu)

為了更好的描述索引的存儲結(jié)構(gòu)待德，這里將圖數(shù)據(jù)庫 Nebula Graph 原始數(shù)據(jù)的存儲結(jié)構(gòu)一起拿出來分析下君丁。

點的存儲結(jié)構(gòu)

點的 Data 結(jié)構(gòu)

image

點的 Index 結(jié)構(gòu)

image

Vertex 的索引結(jié)構(gòu)如上表所示，下面來詳細(xì)地講述下字段：

PartitionId：一個點的數(shù)據(jù)和索引在邏輯上是存放到同一個分區(qū)中的将宪。之所以這么做的原因主要有兩點：

1. 當(dāng)掃描索引時绘闷，根據(jù)索引的 key 能快速地獲取到同一個分區(qū)中的點 data，這樣就可以方便地獲取這個點的任何一種屬性值较坛，即使這個屬性列不屬于本索引印蔗。
2. 目前 edge 的存儲是由起點的 ID Hash 分布，換句話說燎潮，一個點的出邊存儲在哪是由該點的 VertexId 決定的喻鳄，這個點和它的出邊如果被存儲到同一個 partition 中扼倘，點的索引掃描能快速地定位該點的出邊确封。

IndexId：index 的識別碼，通過 indexId 可獲取指定 index 的元數(shù)據(jù)信息再菊，例如：index 所關(guān)聯(lián)的 TagId爪喘，index 所在列的信息。

Index binary：index 的核心存儲結(jié)構(gòu)纠拔，是所有 index 相關(guān)列屬性值的字節(jié)編碼秉剑，詳細(xì)結(jié)構(gòu)將在本文的 #Index binary# 章節(jié)中講解。

VertexId：點的識別碼稠诲，在實際的 data 中侦鹏，一個點可能會有不同 version 的多行數(shù)據(jù)诡曙。但是在 index 中，index 沒有 Version 的概念略水，index 始終與最新 Version 的 Tag 所對應(yīng)价卤。

上面講完字段，我們來簡單地實踐分析一波：

假設(shè) PartitionId 為 100渊涝，TagId 有 tag_1 和 tag_2慎璧，其中 tag_1 包含三列 ：col_t1_1、col_t1_2跨释、col_t1_3胸私，tag_2 包含兩列：col_t2_1、col_t2_2鳖谈。

現(xiàn)在我們來創(chuàng)建索引：

• i1 = tag_1 (col_t1_1, col_t1_2) 岁疼，假設(shè) i1 的 ID 為 1；
• i2 = tag_2(col_t2_1, col_t2_2), 假設(shè) i2 的 ID 為 2缆娃；

可以看到雖然 tag_1 中有 col_t1_3 這列五续，但是建立索引的時候并沒有使用到 col_t1_3，因為在圖數(shù)據(jù)庫 Nebula Graph 中索引可以基于 Tag 的一列或多列進(jìn)行創(chuàng)建龄恋。

插入點

// VertexId = hash("v_t1_1")疙驾，假如為 50 
INSERT VERTEX tag_1(col_t1_1, col_t1_2, col_t1_3), tag_2(col_t2_1, col_t2_2) \
   VALUES hash("v_t1_1"):("v_t1_1", "v_t1_2", "v_t1_3", "v_t2_1", "v_t2_2");

從上可以看到 VertexId 可由 ID 標(biāo)識對應(yīng)的數(shù)值經(jīng)過 Hash 得到，如果標(biāo)識對應(yīng)的數(shù)值本身已經(jīng)為 int64郭毕，則無需進(jìn)行 Hash 或者其他轉(zhuǎn)化數(shù)值為 int64 的運(yùn)算它碎。而此時數(shù)據(jù)存儲如下：

此時點的 Data 結(jié)構(gòu)

image

此時點的 Index 結(jié)構(gòu)

image

說明：index 中 row 和 key 是一個概念，為索引的唯一標(biāo)識显押；

邊的存儲結(jié)構(gòu)

邊的索引結(jié)構(gòu)和點索引結(jié)構(gòu)原理類似扳肛，這里不再贅述。但有一點需要說明乘碑，為了使索引 key 的唯一性成立挖息，索引的 key 的生成借助了不少 data 中的元素，例如 VertexId兽肤、SrcVertexId套腹、Rank 等，這也是為什么點索引中并沒有 TagId 字段（邊索引中也沒有 EdgeType 字段）资铡，這是因為** IndexId 本身帶有 VertexId 等信息可直接區(qū)分具體的 tagId 或 EdgeType**电禀。

邊的 Data 結(jié)構(gòu)

image

邊的 Index 結(jié)構(gòu)

image

Index binary 介紹

image

Index binary 是 index 的核心字段，在 index binary 中區(qū)分定長字段和不定長字段笤休，int尖飞、double、bool 為定長字段，string 則為不定長字段政基。由于** index binary 是將所有 index column 的屬性值編碼連接存儲**贞铣，為了精確地定位不定長字段，Nebula Graph 在 index binary 末尾用 int32 記錄了不定長字段的長度沮明。

舉個例子：

我們現(xiàn)在有一個 index binary 為 index1咕娄，是由 int 類型的索引列1 c1、string 類型的索引列 c2珊擂，string 類型的索引列 c3 組成：

index1 (c1:int, c2:string, c3:string)

假如索引列 c1圣勒、c2、c3 某一行對應(yīng)的 property 值分別為：23摧扇、"abc"圣贸、"here"，則在 index1 中這些索引列將被存儲為如下（在示例中為了便于理解扛稽，我們直接用原值吁峻，實際存儲中是原值會經(jīng)過編碼再存儲）：

• length = sizeof("abc") = 3
• length = sizeof("here") = 4

image

所以 index1 該 row 對應(yīng)的 key 則為 23abchere34；

回到我們 Index binary 章節(jié)開篇說的 index binary 格式中存在 Variable-length field lenght 字段在张，那么這個字段的的具體作用是什么呢用含？我們來簡單地舉個例：

現(xiàn)在我們又有了一個 index binary，我們給它取名為 index2帮匾，它由 string 類型的索引列1 c1啄骇、string 類型的索引列 c2，string 類型的索引列 c3 組成：

index2 (c1:string, c2:string, c3:string)

假設(shè)我們現(xiàn)在 c1瘟斜、c2缸夹、c3 分別有兩組如下的數(shù)值：

• row1 : ("ab", "ab", "ab")
• row2: ("aba", "ba", "b")

image

可以看到這兩行的 prefix（上圖紅色部分）是相同，都是 "ababab"螺句，這時候怎么區(qū)分這兩個 row 的 index binary 的 key 呢虽惭？別擔(dān)心，我們有 Variable-length field lenght 蛇尚。

image

若遇到 where c1 == "ab" 這樣的條件查詢語句芽唇，在 Variable-length field length 中可直接根據(jù)順序讀取出 c1 的長度，再根據(jù)這個長度取出 row1 和 row2 中 c1 的值取劫，分別是 "ab" 和 "aba" 匆笤，這樣我們就精準(zhǔn)地判斷出只有 row1 中的 "ab" 是符合查詢條件的。

索引的處理邏輯

Index write

當(dāng) Tag / Edge中的一列或多列創(chuàng)建了索引后勇凭，一旦涉及到 Tag / Edge 相關(guān)的寫操作時疚膊，對應(yīng)的索引必須連同數(shù)據(jù)一起被修改义辕。下面將對索引的write操作在storage層的處理邏輯進(jìn)行簡單介紹：

INSERT——插入數(shù)據(jù)

當(dāng)用戶產(chǎn)生插入點/邊操作時虾标，insertProcessor 首先會判斷所插入的數(shù)據(jù)是否有存在索引的 Tag 屬性 / Edge 屬性。如果沒有關(guān)聯(lián)的屬性列索引，則按常規(guī)方式生成新 Version璧函，并將數(shù)據(jù) put 到 Storage Engine傀蚌；如果有關(guān)聯(lián)的屬性列索引，則通過原子操作寫入 Data 和 Index蘸吓，并判斷當(dāng)前的 Vertex / Edge 是否有舊的屬性值善炫，如果有，則一并在原子操作中刪除舊屬性值库继。

DELETE——刪除數(shù)據(jù)

當(dāng)用戶發(fā)生 Drop Vertex / Edge 操作時箩艺，deleteProcessor 會將 Data 和 Index（如果存在）一并刪除，在刪除的過程中同樣需要使用原子操作宪萄。

UPDATE——更新數(shù)據(jù)

Vertex / Edge 的更新操作對于 Index 來說艺谆，則是 drop 和 insert 的操作：刪除舊的索引，插入新的索引拜英，為了保證數(shù)據(jù)的一致性静汤，同樣需要在原子操作中進(jìn)行。但是對應(yīng)普通的 Data 來說居凶，僅僅是 insert 操作虫给，使用最新 Version 的 Data 覆蓋舊 Version 的 data 即可。

Index scan

在圖數(shù)據(jù)庫 Nebula Graph 中是用 LOOKUP 語句來處理 index scan 操作的侠碧，LOOKUP 語句可通過屬性值作為判斷條件抹估，查出所有符合條件的點/邊，同樣 LOOKUP 語句支持 WHERE 和 YIELD 子句弄兜。

LOOKUP 使用技巧

正如根據(jù)本文#數(shù)據(jù)存儲結(jié)構(gòu)#章節(jié)所描述那樣棋蚌，index 中的索引列是按照創(chuàng)建 index 時的列順序決定。

舉個例子挨队，我們現(xiàn)在有 tag (col1, col2)谷暮，根據(jù)這個 tag 我們可以創(chuàng)建不同的索引，例如：

• index1 on tag(col1)
• index2 on tag(col2)
• index3 on tag(col1, col2)
• index4 on tag(col2, col1)

我們可以對 clo1盛垦、col2 建立多個索引湿弦，但在 scan index 時，上述四個 index 返回結(jié)果存在差異腾夯，甚至是完全不同颊埃，在實際業(yè)務(wù)中具體使用哪個 index，及 index 的最優(yōu)執(zhí)行策略蝶俱，則是通過索引優(yōu)化器決定班利。

下面我們再來根據(jù)剛才 4 個 index 的例子深入分析一波：

lookup on tag where tag.col1 ==1  # 最優(yōu)的 index 是 index1
lookup on tag where tag.col2 == 2 # 最優(yōu)的 index 是index2
lookup on tag where tag.col1 > 1 and tag.col2 == 1 
# index3 和 index4 都是有效的 index，而 index1 和 index2 則無效

在上述第三個例子中榨呆，index3 和 index4 都是有效 index罗标，但最終必須要從兩者中選出來一個作為 index，根據(jù)優(yōu)化規(guī)則，因為 tag.col2 == 1 是一個等價查詢闯割，因此優(yōu)先使用 tag.col2 會更高效彻消，所以優(yōu)化器應(yīng)該選出 index4 為最優(yōu) index。

實操一下圖數(shù)據(jù)庫 Nebula Graph 索引

在這部分我們就不具體講解某個語句的用途是什么了宙拉，如果你對語句不清楚的話可以去圖數(shù)據(jù)庫 Nebula Graph 的官方論壇進(jìn)行提問：https://discuss.nebula-graph.io/

CREATE——索引的創(chuàng)建

(user@127.0.0.1:6999) [(none)]> CREATE SPACE my_space(partition_num=3, replica_factor=1);
Execution succeeded (Time spent: 15.566/16.602 ms)

Thu Feb 20 12:46:38 2020

(user@127.0.0.1:6999) [(none)]> USE my_space;
Execution succeeded (Time spent: 7.681/8.303 ms)

Thu Feb 20 12:46:51 2020

(user@127.0.0.1:6999) [my_space]> CREATE TAG lookup_tag_1(col1 string, col2 string, col3 string);
Execution succeeded (Time spent: 12.228/12.931 ms)

Thu Feb 20 12:47:05 2020

(user@127.0.0.1:6999) [my_space]> CREATE TAG INDEX t_index_1 ON lookup_tag_1(col1, col2, col3);
Execution succeeded (Time spent: 1.639/2.271 ms)

Thu Feb 20 12:47:22 2020

DROP——刪除索引

(user@127.0.0.1:6999) [my_space]> DROP TAG INDEX t_index_1;
Execution succeeded (Time spent: 4.147/5.192 ms)

Sat Feb 22 11:30:35 2020

REBUILD——重建索引

如果你是從較老版本的 Nebula Graph 升級上來宾尚，或者用 Spark Writer 批量寫入過程中（為了性能）沒有打開索引，那么這些數(shù)據(jù)還沒有建立過索引谢澈，這時可以使用 REBUILD INDEX 命令來重新全量建立一次索引撕瞧。這個過程可能會耗時比較久邪驮，在 rebuild index 完成前，客戶端的讀寫速度都會變慢。

REBUILD {TAG | EDGE} INDEX <index_name> [OFFLINE]

LOOKUP——使用索引

需要說明一下独令，使用 LOOKUP 語句前官套，請確保已經(jīng)建立過索引（CREATE INDEX 或 REBUILD INDEX）派撕。

(user@127.0.0.1:6999) [my_space]> INSERT VERTEX lookup_tag_1(col1, col2, col3) VALUES 200:("col1_200", "col2_200", "col3_200"),  201:("col1_201", "col2_201", "col3_201"), 202:("col1_202", "col2_202", "col3_202");
Execution succeeded (Time spent: 18.185/19.267 ms)

Thu Feb 20 12:49:44 2020

(user@127.0.0.1:6999) [my_space]> LOOKUP ON lookup_tag_1 WHERE lookup_tag_1.col1 == "col1_200";
============
| VertexID |
============
| 200      |
------------
Got 1 rows (Time spent: 12.001/12.64 ms)

Thu Feb 20 12:49:54 2020

(user@127.0.0.1:6999) [my_space]> LOOKUP ON lookup_tag_1 WHERE lookup_tag_1.col1 == "col1_200" YIELD lookup_tag_1.col1, lookup_tag_1.col2, lookup_tag_1.col3;
========================================================================
| VertexID | lookup_tag_1.col1 | lookup_tag_1.col2 | lookup_tag_1.col3 |
========================================================================
| 200      | col1_200          | col2_200          | col3_200          |
------------------------------------------------------------------------
Got 1 rows (Time spent: 3.679/4.657 ms)

Thu Feb 20 12:50:36 2020

索引的介紹就到此為止了废麻，如果你對圖數(shù)據(jù)庫 Nebula Graph 的索引有更多的功能要求或者建議反饋，歡迎去 GitHub：https://github.com/vesoft-inc/nebula issue 區(qū)向我們提 issue 或者前往官方論壇：https://discuss.nebula-graph.io/ 的 Feedback 分類下提建議 ??

作者有話說：Hi列林，我是 bright-starry-sky瑞你，是圖數(shù)據(jù) Nebula Graph 研發(fā)工程師，對數(shù)據(jù)庫存儲有濃厚的興趣希痴，希望本次的經(jīng)驗分享能給大家?guī)韼椭呒祝缬胁划?dāng)之處也希望能幫忙糾正，謝謝~

image