如何設計一個高性能的圖 Schema

語言: CN / TW / HK

本文整理自青藤雲安全工程師——文洲在青藤雲技術團隊內部分享,分享視頻參考:https://www.bilibili.com/video/BV1r64y1R72i

圖數據庫的性能和 schema 的設計息息相關,但是 NebulaGraph 官方本身對圖 schema 的設計其實沒有一個定論,唯一的共識就是是面向性能去做 schema 設計。 而 Neo4j 在它的書籍上則闡述希望用户能夠尊重本身業務領域實體的關係進行設計,這次的分享主要是為了解答下面這些問題:

  • 什麼時候用圖數據庫,什麼時候用圖計算
  • 什麼時候建實體,什麼時候建關係
  • 什麼時候建實體,什麼時候添加屬性
  • 什麼時候屬性加索引
  • 什麼時候屬性加到圖
  • 圖數據庫最佳實踐

希望能從原理上能夠解釋一下,如果當中有任何不妥當的地方歡迎一起交流。

背景知識

先來講解下存儲背景,再講 Schema 設計中會遇到的問題,最後講下實踐過程中我們能達成一致的最佳實踐。

在使用圖數據庫之前,先了解下圖數據庫這個 NoSQL 數據庫同關係型數據庫不一樣的地方。

關係型數據庫存儲結構

如何設計一個高性能的 schema

以上圖為例,存一個 ID 作為一個主鍵,然後它有個特徵 k,我們對 k 創建索引進行查詢,對於左下角這份列表數據,內存中存儲的話,會以一個 B+ 樹進行存儲(上圖右側):一個主索引 ID 和一個從索引 k。舉個例子,現在我們要查詢 k=3 的數據,它就先查詢 ID=100 然後經過回表後回到具體的值。

這體現了關係型數據庫的一個特點,如果你要查詢速度快,那就需要創建一個索引。假如你不創建索引,那數據庫就會掃全表。

我們再來看下寫過程。數據一般先寫到內存 Mem(這是一個常規的優化減小磁盤壓力),寫到一定程度再同步到磁盤中,這個過程我們叫原位刷盤,刷盤就是説找到這個地方的數據,然後修改掉數據,即原位修改。

如何設計一個高性能的 schema

如果你之前熟悉 MySQL 或者是其他關係型數據庫,這套原理應該是比較熟悉的。

而相對應的,用傳統的數據庫來實現圖功能的話,代價比較大,下圖便展示了它的實現弊端:

如何設計一個高性能的 schema

現在有個場景,現在我們有某個人(上圖 Person 表),我們要找朋友的朋友(上圖的 PersonFriend 表),在關係型數據庫中便是兩級索引,先查 Person 表索引找到 Person ID,再查 PersonFriend 表通過 ID 找到對應的人,就是一個 JOIN 查詢過程。如果這裏使用的是 B+ 樹,那麼程序複雜度便是 O(logn);如果是這裏的多級大小表,在笛卡爾積上即 O(n*m),都加索引有一定程度優化,但查詢這種多級關係的話,到了一定程度會遇到系統“爆炸”,無法進行相關查詢。

LSM 存儲模型

本文主題是圖的高性能設計,主要基於 NebulaGraph 來講解。這裏部分存儲細節同 Neo4j 會略有不同。

NebulaGraph 存儲模型採用了 LSM 存儲模型,同上面我們講的原位修改不同,LSM 模型是先寫內存,寫到一定程度之後再寫入到對應磁盤中,每次都是增量順序寫。LSM 模型是一個多級模型,第一層是 L0,第二層是 L1,一般默認是 7 層。

這裏引用網圖來講解下 LSM 層級結構:

如何設計一個高性能的 schema

上圖的 L0 層其實有重複數據,像上圖的 1-68 的 key 在 L0 層的 2-37,以及 23-48,其實這兩部數據是存在重疊的;但L1 層的數據就不存在重疊情況了,1-12、15~25…要最大地發揮圖性能的話,先得了解它的寫入過程。LSM 模型的寫是順序寫,即不會進行上文説到的原位修改。不管是寫入新數據還是更新原來數據,永遠是在後面插入新的數據(參考上圖右側深藍色數據)。這樣設計的好處在於,寫入數據就不需要找之前的數據,一旦涉及查找數據就會慢,這樣設計提升了寫速度。

但這也會帶來一個問題:我們寫入重複的數據,或是寫入的數據越來越多,查詢會不會受影響呢?我們來看看 LSM 是如何查數據的。LSM 進行數據查詢時,先查內存,內存裏沒有數據再查不可變區域(Immutable Memtable),沒有的話,再往下一級級地查(參考上圖左側部分)。所以,重複的數據越多,或者磁盤數據越多,便會越慢。

所以為了保證寫入和查詢性能,無論我們設計屬性還是其他 schema,都要控制寫入量,也就是 LSM 的寫入不能是無限制追加,它有一個定時的合併操作,定期地將重複數據進行合併,叫做 Compaction。

Compaction 過程也需要控制。合併數據能減小數據量,但同時 Compaction 會帶來磁盤壓力,磁盤壓力過大,讀操作速度也會變慢。綜合來看,Compaction 是一個寫入平衡的過程。

NebulaGraph 存儲結構和索引

下面再來了解下 NebulaGraph 本身的存儲結構和索引。

如何設計一個高性能的 schema

NebulaGraph 本身是分佈式數據庫,因為便於理解這裏剔除了相關的分佈式結構。簡單來了解下 NebulaGraph 的結構,上面提到過的 LSM 其實是 kv(key value)存儲,所以我們圖裏存儲點、邊、索引在磁盤上都是 kv 結構。我們可以看到上圖左側(紫色部分)有個 vid 帶着出邊(out)和入邊(in)以及相關屬性。再看下上圖右側部分(紫色部分),可以看到一條邊的兩個點是存儲在一起的,對應的點屬性序列化保存。相當於説,kv 結構中的 key 便是我們的點的 vid,然後 value 便是屬性的序列化結構。因為是序列化的結構,所以你的屬性名是什麼便會存成什麼,比如這裏原始數據 name 字段,它改命名為 family_name,實際存儲就是序列化後的 family_name,也就是屬性名越長,存儲量越大。除了屬性名之外,其實屬性值也會導致存儲量增大。舉個例子,現在有個人(點),他的生平介紹要不要放在屬性裏進行存儲?答案是:不應該。因為你的生平介紹會很長,這就會導致 LSM 的存儲壓力會很大。無論是 Compaction 還是讀寫,都會有很大的壓力。類似比如存儲進程實體,對應的進程描述文本也較大,會帶來較大存儲壓力。

再來説下我們的邊,NebulaGraph 中出邊和入邊保存在一個 kv 結構中(參考上圖右側橙色部分)。NebulaGraph 中有個詞叫做前綴掃描,具體來説便是現在要查找某個 vid 對應的邊,它是如何查找的呢?先按照 vid 來前綴掃描,在內存中這個過程是個二分查找,所以 NebulaGraph 查詢快就是在這裏。在 Neo4j 裏面這種叫做“免索引鄰接”。像上面的朋友的朋友的場景,傳統數據庫是通過索引進行查找的,而在這裏直接掃描找尋某個人便可。在物理存儲這塊,點(人和相關的人)都是存儲在一起的,找到了某個人便找到了他的朋友。查詢上速度非常快,這也是原生圖數據庫帶來的好處。

除了上面的存儲結構,索引也是高性能 schema 設計的一個作用因素。像上圖的右側部分,上面的紫色部分存儲着點,這裏有 2 個點:第一個點是 vid1,name 是 wen,age 是 20;另外一個是 vid2,name 是 wei,age 是 20。這裏我們創建了 2 個索引,一個是針對 name,一個是針對 age。這兩個索引的存儲結構參考上圖右側下方的白色部分,查找 name 為 wen 的數據時,按照上面我們科普過的會進行二分查找,掃描到對應的 name 索引的 wen 數據,然後再從索引數據中找到對應的點(vid1)數據,再借助 vid 數據來找尋它的相關信息。這裏 vid 找關聯數據的原理同上面的存儲結構描述。

小結

小結下 NebulaGraph 存儲結構和索引,在這裏關係是一等公民,索引輔助查詢(並非用來提速),重要的是抽象關係。

Schema 設計

進入本文的重點——Schema 的設計,Schema 設計的三大基本原則:

  • 尊重領域實體關係
  • 以性能為目標
  • 考慮可視化分析

而三者並不衝突,上面三點其中某一點做得很好,另外兩點也會做的不錯。

Talking is cheap,下面我們來結合具體的例子來了解下三大原則。這些 case 圖主要引用自 Neo4j,但是對於 NebulaGraph 相關的 schema 設計也有參考意義。

實體和關係的選擇

如何設計一個高性能的 schema

上圖是 Neo4j 圖數據庫書籍中的示例圖。簡單描述下這個場景,Bob 和 Charlie 等人在發郵件。那你設計這麼一個場景的 Schema 是否很自然就會將發郵件變成關係邊?因為 Bob 同 Charlie 發郵件,不是很明顯就是發郵件關係嗎?那我們來回顧下上面説的三大原則第一點:尊重領域實體關係。Bob 和 Charlie 建立聯繫自然不是通過發郵件這個行為,而是通過郵件本身來建立聯繫,所以這裏便缺少了一個實體。在考慮可視化分析原則這邊,你要分析實體之間的關係,你思考它們是通過什麼來建立的聯繫。這時候就會發生之前提到過的發郵件設置為邊的情況(把郵件放置在邊上),單看 Bobo 的話(左圖),我們可以清楚地看到發郵件這個動作。左圖上面部分,Bobo Emailed Charlie。但如果這時候,要查看這個郵件抄送給了誰,還有這封郵件有哪些相關人,像左圖的 schema 就不能很好地進行查詢。因為缺少了 Email 這個實體。而上圖右側部分便能可以方便地找尋相關信息。

下面再來講下如何進行實體和屬性選擇。

實體和屬性選擇

如何設計一個高性能的 schema

在這個部分,我將結合青藤雲的情況來講一個我們的 case——進程之間的父子關係。

如上圖左側所示,md5 為 1 的 pid 100 進程起了一個 pid 102 的子進程,這個子進程的 md5 是 2。同時,md5 也為 1 的 pid 101 也起了進程,pid 為 103、md5 為 3。按照我們之前的實現方法,是在 md5 上創建索引,繼而建立起跟 pid 102、pid 103 的聯繫。但這種做法,上面講過性能並不高,免索引複雜是 O(1),而這種做法的複雜度是 O(logn)。所以説,我們這時候應該基於 ProcessFile 進程文件 md5 來建立關係(進程間是基於 md5 聯繫起來的):我們先抽取 md5 建立一個名叫 ProcessFile 的實體,屬性是 md5。如果我們要查詢指定進程所關聯的進程,很直觀地去找尋和這個 ProcessFile 關聯的進程就可以分析出來我們要的結果。舉個例子,pid 102 的進程是一個木馬,我想找尋是哪個父進程釋放的它,或者是同它父進程同 md5 文件的進程,該怎麼找?

上圖的展示了兩種形式,第一種(左側)的話就需要找索引;第二種(右側)通過 CREATE_PROCESS 就可以直接找到 pid 102 的父進程 pid 100,再通過 PFILE_OF 關係你可以找到它同 md 文件的進程 pid 101。

好的,簡單結合 Schema 設計三大原則來回顧下這個 case:

  1. 屬性上創建索引會影響寫入,此外屬性放在 ProcessFile 還是放在 Process 中,存儲性能是不一樣的。這裏主要涉及到寫入量,因為 Process 進程是一直可以不停地啟動,但是 md5 文件可能本身並不多。如果是放在 Process 中,進程起得越多,數據寫入量也就會越大,進而查詢壓力也會增大查詢變慢。
  2. 可視化探索這塊主要和不定需求有關。因為一開始我們設計 schema 的時候可能並沒有全方位考量,或者説像是一些安全、防作弊規則並未擬定,不知道它會是什麼樣。而這時你要根據這種不確定來設計 Schema,就需要將圖“釋放”給相關業務人員,讓他在圖裏點擊,設計他的關係,所以相對應的我們就不能通過索引來實現這種需求,因為業務人員可能沒有相關的技術背景。

添加屬性

如何設計一個高性能的 schema

上圖左邊描述文字截自 v2.0 的官方文檔:https://docs.nebula-graph.com.cn/2.0/3.ngql-guide/1.nGQL-overview/2.graph-modeling/#_3

在合理設置邊屬性的第二部分提到,“為邊創建屬性時請勿使用長字符串”。這個和我們之前提到過的,屬性名和屬性值都應該短,不應該長是一個意思。像上圖右側部分,很明顯可以看到 vid 重複寫多次的話,每次寫就是重複的流量和存儲,這會大大增大內存佔用和磁盤容量。如果我們把 session_guid 變成 sid 會節約很多存儲。而後面的描述信息,也有兩種處理方式。第一種,直接刪除描述;第二種,將過長的描述存儲在外部,比如放置在 Elasticsearch,然後將 ES 存儲這塊內容的 eid 存儲在上圖的 value 中。這樣也可以大大減少存儲量,提升寫入 / 查詢性能。

除了這點之外,我們還要注意合理設置分組標籤。青藤雲暫時沒遇到類似 case,所以這裏講下這句話什麼意思。簡單來説,就是寫入這邊需要做一個 tag 的區分,結合上文提到的二分查找,你就比較好理解了。舉個簡單例子,這裏有個人,他的公司相關信息,或者年齡相關的信息,或者是個人喜好之類的信息用相關的 tag 區分開,這樣查詢時可以更快地找到對應的信息。

最後回到文檔「合理設置邊屬性」中第一部分中的“深度圖遍歷的性能較低,為了減少遍歷深度,請使用點屬性代替邊。例如,模型 a 包括姓名、年齡、眼睛顏色三種屬性,建議您創建一個標籤 person,然後為它添加姓名、年齡、眼睛顏色的屬性。”,按照官方的舉的例子,固然是這樣的。但實際應用中,並非一定要遵循這一原則——屬性用點屬性而不是用邊,該用實體的時候還是得用實體。所以我這裏下面備註寫了:描述實體本身特性。像實體本身的特性 age / status,邊的 time / count 這些屬性會變成相對應的屬性,這樣能更好地描述本質特性,也能起到比較好的輔助效果。

添加索引

如何設計一個高性能的 schema

藉助之前我們的實踐經驗,來講下索引這塊內容。在 NebulaGraph 的官方文檔中提及了:儘量少用索引。那麼問題來了,到底什麼時候應該用索引呢?我們先從原理上來解釋下索引。在上圖的例子中,value 中存儲了 2 樣東西:一個是 status,狀態;另外一個是 ip。右側的表格是對應的 kv 存儲結構,key 是個點結構。給點加索引之後,它便會變成左側表格的結構,idx-x-vid1。如果我們要查詢 status 等於 0 的這列值的時候,由於加了索引之後數據結構是以 0(status)為前綴,vid 放在 0 後面;如果我們要查詢 ip 的話,存儲結構則將 ip 變成前綴,vid 存儲在後面。這樣會產生何種問題呢?status 如果只有 1 和 0,現在你有 1 萬億的點,這樣添加索引是沒有意義的。而且,因為 NebulaGraph 的查找是二分查找,複雜度收斂到 O(n),相當於有多少數據就查多少數據。即便你添加了一個 limit,但是在 NebulaGraph 這邊(注:本次分享時,NebulaGraph 的最新版本為 v2.0.1)limit 並沒有下推,所以所有數據會先撈上來到計算層,在內存中使用 limit 進行數據過濾。

正是由於這種情況,所以在 v2.5 之前的 NebulaGraph 用户會經常在論壇反饋 OOM 問題,其實就是內存爆炸。

所以説,索引應該是儘可能和業務相關的標識。

細粒度關係和通用關係

如何設計一個高性能的 schema

通過上面的 Neo4j 這個 case 我們來講解下顆粒度問題。

像上面的人有 2 個地址,一個是收件地址,另外一個是付款地址。如果此時,我們想找尋這個人的地址,如果沒有 ADDRESS 這個通用標籤的話,DELIVERY_ADDRESSBILLING_ADDRESS 這兩個關係都得查下。這時候如果用的是二分查找,如果這堆關係本身存儲在一起還好,可以一次性查找出來;但,如果關係不在一起,就需要分 2 次查詢,這會降低它的查詢速率。

因此,我們可以再創建一個通用標籤,但是要注意的是,標籤的建立是基於對某個業務有強需求。像上面的例子,需要知道用户的所有地址,也要知道他的單獨地址,比如:收件地址。這種情況下,建立一個通用標籤才是一個加速的方法,但注意要謹慎使用。同樣的,通用標籤設計時,也需要考慮可視化的情況。

加速查詢

如何設計一個高性能的 schema

之前我們講過一個發郵件的例子,但是現在場景有所變化了,我現在不關心發郵件這個事情,我只關心人和人之間的關係,比如,wen 這個人的聯繫關係,有誰和他聯繫過,而這個聯繫方式可能是 Email,也可能是手機(Phone),或者是微信。這時候我應該如何設計 schema 呢?當然之前的設計是可以沿用的,但為了加速查詢,滿足業務上的需求。這裏加了 CONTACT 屬性,用來加速查找。

小結 Schema 設計

講到這裏,我們總結下上面的例子,其實我們的例子都是圍繞着三大原則來展開的,即:性能、可視化、領域關係。

典型 Schema 設計

下面來我們來講下有些典型場景下的 Schema 設計。

時間設計

如何設計一個高性能的 schema

現在有個場景,有一堆發生過的事件,現在想查詢在某個月,或者是某個時間段內,發生了哪些事件,我們該如何設計 Schema 呢?也許我們可以在時間屬性上創建個索引,把這個時間當作索引來存儲,但這樣的話,查詢速度不會很快,尤其是數據量較大的情況下。那我們應該怎麼做呢?Neo4j 給了一種設計思路叫做時間樹,就是説時間本身是有層級關係的。如上圖所示,時間有個層級,想要查詢某個事件同時間段內的其他事件,可以通過這個層級快速找到。

上圖右側則是一個時序關係,可以快速找尋某事件發生的時間前後有哪些事情發生,而在 NebulaGraph 中,你可以通過 rank 來實現時序圖功能。

上面的例子只是給大家一個參考,並不代表會應用在青藤雲實際業務中。

地址設計

如何設計一個高性能的 schema

上面這個是地址的設計,可能大家都會遇到。假如,現在我們要查詢北京朝陽太陽宮在發生事件 A 時,同一個地理位置有多少用户 / IP 在這。傳統的設計方法中,添加屬性是無法滿足該業務需求的。那怎麼實現呢?其實這些地址劃分可以作為實體,而且地址之間是有關係的。以上述的物流為例,上面的例子:中國-北京-朝陽-太陽宮,就可以通過集散中心-派送點-派送區域-派送段形式進行查詢。如果你要查詢同一個街道或者是同個市,也可以按照這個關係快速進行查詢。

像我們遇到的地址位置,或者是網絡層問題,都可以參考這種設計。之前在 BOSS 直聘(分享嘉賓曾就職 BOSS 直聘)中,我們就是參考了類似的實現來找尋某個區域的相關用户。

圖最佳實踐

上面講述的內容主要是圍繞 Schema 設計,下面這塊當作補充資料,主要講的是圖的最佳實踐。

命名規範

如果你要編寫一個比較長的語句,不知道你有沒有注意過,這個語句該如何快速區分哪些是實體,哪些是關係,哪些又是屬性。所以,這裏就要提一下命名規範問題。一旦命名規範了,一條長查詢語句也可能快速辨別實體、關係、屬性。

你可以參考下面的命名規範:

  1. 實體採用駝峯方式,例如:User、Email、Process;
  2. 關係採用全部大寫,包含動詞和副詞,例如:HAS_IP;
  3. 屬性採用英文小寫簡寫,例如:title、sid、pid

圖計算

如何設計一個高性能的 schema

上圖給出了圖數據庫和圖計算的工作流,可以直觀地查看到二者的區別。圖數據庫的工作流相對簡單,拿我們常見的一個場景舉例,已知某個有問題的進程 A,要溯源找尋它的源頭。對應到圖這邊,圖數據庫的查詢一般會 GO / LOOKUP / MATCH / FETCH 錨定某個起始點,比如這裏的進程 A,然後管道 / WITCH 進行下一步的處理,最後用 RETURN / YIELD 來返回基本結構。但,注意,這個基本結構會進行二次加工。剛設計 Schema 的時候提到過,並不是所有的屬性都會設計進去,只有和業務相關的核心屬性才會設計進入。像請求接口之類的操作,都會在下一步過濾 / 擴展處理時完成。

上面説的是圖的直接業務簡單查詢,但還有一種場景是用圖來進行機器學習,比如 GNN 和 GCN 用圖來做 feature / 特徵,這塊本文就不展開講述,流程和上面有所不同。

那,什麼時候用圖數據庫,什麼時候用圖計算呢?

如何設計一個高性能的 schema

如上圖所示,有限點的拓展就比較適合用圖數據庫,或者説 NebulaGraph 來實現;而全局挖掘就比較適合用圖計算。從圖計算的流程上來看,簡單粗暴地講,圖計算就是把一批數據撈到內存中,一次性計算完,然後“吐”出來,再進行下一步的過濾和處理。至於它是如何計算的,圖計算裏面配有計算引擎。

現在我們來問個問題,如果要找全圖點度 Top10 的點,應該用什麼?

自然是圖計算,圖計算也就是 OLAP 主打的是吞吐,即一次性能處理多少數據;而圖數據庫,主要是應對 OLTP 場景,側重低延遲,就是查詢有多快,以及支持多大量的併發請求 QPS

只要我們記住圖數據庫和圖計算各自的擅長場景,就比較好處理相關的業務。

大圖優化

像傳統關係型數據庫中,業務無限膨脹的話,就需要做分庫分表。圖也是類似的,在大圖上做某些查詢時,你會發現性能很差,這時候你就需要進行分圖處理。像上面説到過的關係細化和加速查詢,比如我現在只關心進程關係,在特定業務場景下就需要將進程關係單獨設計成一張圖。這就是圖的一個優化手段。或者,你也可以進行業務隔離。像現在的業務是針對推薦場景,剩下的安全場景是否要放置在同一個圖空間下呢?如果業務量不大的情況下,是可以的。但是如果是數據量大的話,還是需要同傳統數據庫一樣進行業務隔離,什麼業務進入什麼圖。

這裏延伸一下,分圖場景下如何進行多圖查詢呢?簡單來説就是進程一張圖,網絡是一張圖,這時候要查詢進程和網絡的關係。業界的話,管這個叫做查詢端融合。雖然你要查詢的數據是 2 張圖,但是我假裝你是在一張圖上進行查詢。

以上為本文的分享。

延伸閲讀

下面收錄了本文相關的閲讀資料:


謝謝你讀完本文 (///▽///)

如果你想嚐鮮圖數據庫 NebulaGraph,體驗雲上圖數據庫一鍵服務你的業務 ->☆白嫖 NebulaGraph 雲服務;NebulaGraph 也是一款開源的圖數據庫,上 GitHub 看代碼、(^з^)-☆ star 它 -> GitHub;和其他的 NebulaGraph 用户一起交流圖數據庫技術和應用技能,留下「你的名片」一起玩耍呀~