淺談圖資料庫

從社交網絡談起

下面這張圖是一個社交網絡場景，每個使用者可以發微網誌、分享微網誌或評論他人的微網誌。這些都是最基本的增删改查，也是大多數研發人員對資料庫做的常見操作。而在研發人員的日常工作中除了要把使用者的基本資訊錄入資料庫外，還需找到與該使用者相關聯的資訊，友善去對單個的使用者進行下一步的分析，比如說：我們發現張三的賬戶裡有很多關于 AI 和音樂的内容，那麼我們可以據此推測出他可能是一名程式員，進而推送他可能感興趣的内容。

這些資料分析每時每刻都會發生，但有時候，一個簡單的資料工作流在實作的時候可能會變得相當複雜，此外資料庫性能也會随着資料量的增加而銳減，比如說擷取某管理者下屬三級彙報關系的員工，這種統計查詢在現在的資料分析中是一種常見的操作，而這種操作往往會因為資料庫選型導緻性能産生巨大差異。

傳統資料庫的解決思路

傳統資料庫的概念模型及查詢的代碼

傳統解決上述問題最簡單的方法就是建立一個關系模型，我們可以把每個員工的資訊錄入表中，存在諸如 MySQL 之類的關系資料庫，下圖是最基本的關系模型：

但是基于上述的關系模型，要實作我們的需求，就不可避免地涉及到很多關系資料庫 

JOIN

 操作，同時實作出來的查詢語句也會變得相當長(有時達到上百行)：

(SELECT T.directReportees AS directReportees, sum(T.count) AS countFROM (SELECT manager.pid AS directReportees, 0 AS count
	FROM person_reportee manager	WHERE manager.pid = (SELECT id FROM person WHERE name = "fName lName")UNION
	SELECT manager.pid AS directReportees, count(manager.directly_manages) AS countFROM person_reportee managerWHERE manager.pid = (SELECT id FROM person WHERE name = "fName lName")GROUP BY directReporteesUNIONSELECT manager.pid AS directReportees, count(reportee.directly_manages) AS countFROM person_reportee managerJOIN person_reportee reporteeON manager.directly_manages = reportee.pidWHERE manager.pid = (SELECT id FROM person WHERE name = "fName lName")GROUP BY directReporteesUNIONSELECT manager.pid AS directReportees, count(L2Reportees.directly_manages) AS countFROM person_reportee managerJOIN person_reportee L1ReporteesON manager.directly_manages = L1Reportees.pidJOIN person_reportee L2ReporteesON L1Reportees.directly_manages = L2Reportees.pidWHERE manager.pid = (SELECT id FROM person WHERE name = "fName lName")GROUP BY directReportees
) AS TGROUP BY directReportees)UNION(SELECT T.directReportees AS directReportees, sum(T.count) AS countFROM (SELECT manager.directly_manages AS directReportees, 0 AS countFROM person_reportee managerWHERE manager.pid = (SELECT id FROM person WHERE name = "fName lName")UNIONSELECT reportee.pid AS directReportees, count(reportee.directly_manages) AS countFROM person_reportee managerJOIN person_reportee reporteeON manager.directly_manages = reportee.pidWHERE manager.pid = (SELECT id FROM person WHERE name = "fName lName")GROUP BY directReporteesUNIONSELECT depth1Reportees.pid AS directReportees,count(depth2Reportees.directly_manages) AS countFROM person_reportee managerJOIN person_reportee L1ReporteesON manager.directly_manages = L1Reportees.pidJOIN person_reportee L2ReporteesON L1Reportees.directly_manages = L2Reportees.pidWHERE manager.pid = (SELECT id FROM person WHERE name = "fName lName")GROUP BY directReportees
) AS TGROUP BY directReportees)UNION(SELECT T.directReportees AS directReportees, sum(T.count) AS count
	FROM(	SELECT reportee.directly_manages AS directReportees, 0 AS countFROM person_reportee managerJOIN person_reportee reporteeON manager.directly_manages = reportee.pidWHERE manager.pid = (SELECT id FROM person WHERE name = "fName lName")GROUP BY directReporteesUNIONSELECT L2Reportees.pid AS directReportees, count(L2Reportees.directly_manages) AScountFROM person_reportee managerJOIN person_reportee L1ReporteesON manager.directly_manages = L1Reportees.pidJOIN person_reportee L2ReporteesON L1Reportees.directly_manages = L2Reportees.pidWHERE manager.pid = (SELECT id FROM person WHERE name = "fName lName")GROUP BY directReportees
) AS TGROUP BY directReportees)UNION(SELECT L2Reportees.directly_manages AS directReportees, 0 AS countFROM person_reportee managerJOIN person_reportee L1ReporteesON manager.directly_manages = L1Reportees.pidJOIN person_reportee L2ReporteesON L1Reportees.directly_manages = L2Reportees.pidWHERE manager.pid = (SELECT id FROM person WHERE name = "fName lName")
)      

這種 glue 代碼對維護人員和開發者來說就是一場災難，沒有人想寫或者去調試這種代碼，此外，這類代碼往往伴随着嚴重的性能問題，這個在之後會詳細讨論。

傳統關系資料庫的性能問題

性能問題的本質在于資料分析面臨的資料量，假如隻查詢幾十個節點或者更少的内容，這種操作是完全不需要考慮資料庫性能優化的，但當節點資料從幾百個變成幾百萬個甚至幾千萬個後，資料庫性能就成為了整個産品設計的過程中最需考慮的因素之一。

随着節點的增多，使用者跟使用者間的關系，使用者和産品間的關系，或者産品和産品間的關系都會呈指數增長。

以下是一些公開的資料，可以反映資料、資料和資料間關系的一些實際情況：

• 推特：使用者量為 5 億，使用者之間存在關注、點贊關系
• 亞馬遜：使用者量 1.2 億，使用者和産品間存在購買關系
• AT&T（美國三大營運商之一）： 1 億個号碼，電話号碼間可建立通話關系

如下表所示，開源的圖資料集往往有着上千萬個節點和上億的邊的資料：

Data set name	nodes	edges
YahooWeb	1.4 Billion	6 Billion
Symantec Machine-File Graph	1 Billion	37 Billion
Twitter	104 Million	3.7 Billion
Phone call network	30 Million	260 Million

在資料量這麼大的場景中，使用傳統 SQL 會産生很大的性能問題，原因主要有兩個：

1. 大量 JOIN 操作帶來的開銷：之前的查詢語句使用了大量的 JOIN 操作來找到需要的結果。而大量的 JOIN 操作在資料量很大時會有巨大的性能損失，因為資料本身是被存放在指定的地方，查詢本身隻需要用到部分資料，但是 JOIN 操作本身會周遊整個資料庫，這樣就會導緻查詢效率低到讓人無法接受。
2. 反向查詢帶來的開銷：查詢單個經理的下屬不需要多少開銷，但是如果我們要去反向查詢一個員工的老闆，使用表結構，開銷就會變得非常大。表結構設計得不合理，會對後續的分析、推薦系統産生性能上的影響。比如，當關系從_老闆 -> 員工 _變成 使用者 -> 産品，如果不支援反向查詢，推薦系統的實時性就會大打折扣，進而帶來經濟損失。

下表列出的是一個非官方的性能測試（社交網絡測試集，一百萬使用者，每個大概有 50 個好友），展現了在關系資料庫裡，随着好友查詢深度的增加而産生的性能變化：

levels	RDBMS execution time(s)
2	0.016
3	30.267
4	1543.595

傳統資料庫的正常優化政策

政策一：索引

索引：SQL 引擎通過索引來找到對應的資料。

常見的索引包括 B- 樹索引和哈希索引，建立表的索引是比較正常的優化 SQL 性能的操作。B- 樹索引簡單地來說就是給每個人一個可排序的獨立 ID，B- 樹本身是一個平衡多叉搜尋樹，這個樹會将每個元素按照索引 ID 進行排序，進而支援範圍查找，範圍查找的複雜度是 O(logN)  ，其中 N 是索引的檔案數目。

但是索引并不能解決所有的問題，如果檔案更新頻繁或者有很多重複的元素，就會導緻很大的空間損耗，此外索引的 IO 消耗也值得考慮，索引 IO 尤其是在機械硬碟上的 IO 讀寫性能上來說非常不理想，正常的 B- 樹索引消耗四次 IO 随機讀，當 JOIN 操作變得越來越多時，硬碟查找更可能發生上百次。

政策二：緩存

緩存：緩存主要是為了解決有具有空間或者時間局域性資料的頻繁讀取帶來的性能優化問題。一個比較常見的使用緩存的架構是 lookaside cache architecture。下圖是之前 Facebook 用 Memcached  + MySQL 的執行個體（現已被 Facebook 自研的圖資料庫 TAO 替代）：

在架構中，設計者假設使用者創造的内容比使用者讀取的内容要少得多，Memcached 可以簡單地了解成一個分布式的支援增删改查的哈希表，支援上億量級的使用者請求。基本的使用流程是當用戶端需讀資料時，先檢視一下緩存，然後再去查詢 SQL 資料庫。而當使用者需要寫入資料時，用戶端先删除緩存中的 key，讓資料過期，再去更新資料庫。但是這種架構有幾個問題：

• 首先，鍵值緩存對于圖結構資料并不是一個好的操作語句，每次查詢一條邊，需要從緩存裡把節點對應的邊全部拿出來；此外，當更新一條邊，原來的所有依賴邊要被删除，繼而需要重新加載所有對應邊的資料，這些都是并發的性能瓶頸，畢竟實際場景中一個點往往伴随着幾千條邊，這種操作帶來的時間、記憶體消耗問題不可忽視。
• 其次，資料更新到資料讀取有一個過程，在上面架構中這個過程需要主從資料庫跨域通信。原始模型使用了一個外部辨別來記錄過期的鍵值對，并且異步地把這些讀取的請求從隻讀的從節點傳遞到主節點，這個需要跨域通信，延遲相比直接從本地讀大了很多。（類似從之前需要走幾百米的距離而現在需要走從北京到深圳的距離）

使用圖結構模組化

上述關系型資料庫模組化失敗的主要原因在于資料間缺乏内在的關聯性，針對這類問題，更好的模組化方式是使用圖結構。 假如資料本身就是表格的結構，關系資料庫就可以解決問題，但如果你要展示的是資料與資料間的關系，關系資料庫反而不能解決問題了，這主要是在查詢的過程中不可避免的大量 JOIN 操作導緻的，而每次 JOIN 操作卻隻用到部分資料，既然反複 JOIN 操作本身會導緻大量的性能損失，如何模組化才能更好的解決問題呢？答案在點和點之間的關系上。

點、關聯關系和圖資料模型

在我們之前的讨論中，傳統資料庫雖然運用 JOIN 操作把不同的表連結了起來，進而隐式地表達了資料之間的關系，但是當我們要通過 A 管理 B，B 管理 A 的方式查詢結果時，表結構并不能直接告訴我們結果。 如果我們想在做查詢前就知道對應的查詢結果，我們必須先定義節點和關系。

節點和關系先定義是圖資料庫和别的資料庫的核心差別。打個比方，我們可以把經理、員工表示成不同的節點，并用一條邊來代表他們之前存在的管理關系，或者把使用者和商品看作節點，用購買關系模組化等等。而當我們需要新的節點和關系時，隻需進行幾次更新就好，而不用去改變表的結構或者去遷移資料。

根據節點和關聯關系，之前的資料可以根據下圖所示模組化：

通過圖資料庫 Nebula Graph 原生 nGQL 圖查詢語言進行模組化，參考如下操作：

-- Insert PeopleINSERT VERTEX person(ID, name) VALUES 1:(2020031601, ‘Jeff’);INSERT VERTEX person(ID, name) VALUES 2:(2020031602, ‘A’);INSERT VERTEX person(ID, name) VALUES 3:(2020031603, ‘B’);INSERT VERTEX person(ID, name) VALUES 4:(2020031604, ‘C’);-- Insert edgeINSERT EDGE manage (level_s, level_end) VALUES 1 -> 2: ('0'， '1')INSERT EDGE manage (level_s, level_end) VALUES 1 -> 3: ('0'， '1')INSERT EDGE manage (level_s, level_end) VALUES 1 -> 4: ('0'， '1')      

而之前超長的 query 語句也可以通過 Cypher / nGQL 縮減成短短的 3、4 行代碼。

下面為 nGQL 語句

GO FROM 1 OVER manage YIELD manage.level_s as start_level, manage._dst AS personid
| GO FROM $personid OVER manage where manage.level_s < start_level + 3
YIELD SUM($$.person.id) AS TOTAL, $$.person.name AS list      

下面為 Cypher 版本

MATCH (boss)-[:MANAGES*0..3]->(sub),
(sub)-[:MANAGES*1..3]->(personid)
WHERE boss.name = “Jeff”
RETURN sub.name AS list, count(personid) AS Total      

從近百行代碼變成 3、4 行代碼可以明顯地看出圖資料庫在資料表達能力上的優勢。

圖資料庫性能優化

圖資料庫本身對高度連接配接、結構性不強的資料做了專門優化。不同的圖資料庫根據不同的場景也做了針對性優化，筆者在這裡簡單介紹以下幾種圖資料庫，BTW，這些圖資料庫都支援原生圖模組化。

Neo4j

Neo4j 是最知名的一種圖資料庫，在業界有微軟、ebay 在用 Neo4j 來解決部分業務場景，Neo4j 的性能優化有兩點，一個是原生圖資料處理上的優化，一個是運用了 LRU-K 緩存來緩存資料。

原生圖資料處理優化

我們說一個圖資料庫支援原生圖資料處理就代表這個資料庫有能力去支援 index-free adjacency。

index-free adjancency 就是每個節點會保留連接配接節點的引用，進而這個節點本身就是連接配接節點的一個索引，這種操作的性能比使用全局索引好很多，同時假如我們根據圖來進行查詢，這種查詢是與整個圖的大小無關的，隻與查詢節點關聯邊的數目有關，如果用 B 樹索引進行查詢的複雜度是 O(logN)，使用這種結構查詢的複雜度就是 O(1)。當我們要查詢多層資料時，查詢所需要的時間也不會随着資料集的變大而呈現指數增長，反而會是一個比較穩定的常數，畢竟每次查詢隻會根據對應的節點找到連接配接的邊而不會去周遊所有的節點。

主存緩存優化

在 2.2 版本的 Neo4j 中使用了 LRU-K 緩存，這種緩存簡而言之就是将使用頻率最低的頁面從緩存中彈出，青睐使用頻率更高的頁面，這種設計保證在統計意義上的緩存資源使用最優化。

JanusGraph

JanusGraph 本身并沒有關注于去實作存儲和分析，而是實作了圖資料庫引擎與多種索引和存儲引擎的接口，利用這些接口來實作資料和存儲和索引。JanusGraph 主要目的是在原來架構的基礎上支援圖資料的模組化同時優化圖資料序列化、圖資料模組化、圖資料執行相關的細節。JanusGraph 提供了子產品化的資料持久化、資料索引和用戶端的接口，進而更友善地将圖資料模型運用到實際開發中。

此外，JanusGraph 支援用 Cassandra、HBase、BerkelyDB 作為存儲引擎，支援使用 ElasticSearch、Solr 還有 Lucene 進行資料索引。 在應用方面，可以用兩種方式與 JanusGraph 進行互動：

• 将 JanusGraph 變成應用的一部分進行查詢、緩存，并且這些資料互動都是在同一台 JVM 上執行，但資料的來源可能在本地或者在别的地方。
• 将 JanusGraph 作為一個服務，讓用戶端與服務端分離，同時用戶端送出 Gremlin 查詢語句到伺服器上執行對應的資料處理操作。

Nebula Graph

下面簡單地介紹了一下 Nebula Graph 的系統設計。

使用 KV 對來進行圖資料處理

Nebula Graph 使用了 

vertexID + TagID

 作為鍵在不同的 partition 間存儲 in-key 和 out-key 相關的資料，這種操作可以確定在大規模叢集上的高可用，使用分布式的 partition 和 sharding 也增加了 Nebula Graph 的吞吐量和容錯的能力。

Shared-noting 分布式存儲層

Storage Service 采用 shared-nothing 的分布式架構設計，每個存儲節點都有多個本地 KV 存儲執行個體作為實體存儲。Nebula 采用多數派協定 Raft 來保證這些 KV 存儲之間的一緻性（由于 Raft 比 Paxo 更簡潔，我們選用了 Raft）。在 KVStore 之上是圖語義層，用于将圖操作轉換為下層 KV 操作。 圖資料（點和邊）通過 Hash 的方式存儲在不同 partition 中。這裡用的 Hash 函數實作很直接，即 vertex_id 取餘 partition 數。在 Nebula Graph 中，partition 表示一個虛拟的資料集，這些 partition 分布在所有的存儲節點，分布資訊存儲在 Meta Service 中（是以所有的存儲節點和計算節點都能擷取到這個分布資訊）。

無狀态計算層

每個計算節點都運作着一個無狀态的查詢計算引擎，而節點彼此間無任何通信關系。計算節點僅從 Meta Service 讀取 meta 資訊，以及和 Storage Service 進行互動。這樣設計使得計算層叢集更容易使用 K8s 管理或部署在雲上。 計算層的負載均衡有兩種形式，最常見的方式是在計算層上加一個負載均衡（balance），第二種方法是将計算層所有節點的 IP 位址配置在用戶端中，這樣用戶端可以随機選取計算節點進行連接配接。 每個查詢計算引擎都能接收用戶端的請求，解析查詢語句，生成抽象文法樹（AST）并将 AST 傳遞給執行計劃器和優化器，最後再交由執行器執行。

圖資料庫是當今的趨勢

在當今，圖資料庫收到了更多分析師和咨詢公司的關注

Graph analysis is possibly the single most effective  competitive differentiator for organizations  pursuing data-driven operations and  decisions after the design of data capture.        --------------Gartner

“Graph analysis is the true killer app for Big Data.”      --------------------Forrester

同時圖資料庫在 DB-Ranking 上的排名也呈現出上升最快的趨勢，可見需求之迫切：

圖資料庫實踐：不僅僅是社交網絡

Netflix 雲資料庫的工程實踐

Netflix 采用了JanusGraph + Cassandra + ElasticSearch 作為自身的圖資料庫架構，他們運用這種架構來做數字資産管理。 節點表示數字産品比如電影、紀錄片等，同時這些産品之間的關系就是節點間的邊。 目前的 Netflix 有大概 2 億的節點，70 多種數字産品，每分鐘都有上百條的 query 和資料更新。 此外，Netflix 也把圖資料庫運用在了授權、分布式追蹤、可視化工作流上。比如可視化 Git 的 commit，jenkins 部署這些工作。

Adobe 的技術疊代

一般而言，新技術往往在開始的時候大都不被大公司所青睐，圖資料庫并沒有例外，大公司本身有很多的遺留項目，而這些項目本身的使用者體量和使用需求又讓這些公司不敢冒着風險來使用新技術去改變這些處于穩定的産品。Adobe 在這裡做了一個疊代新技術的例子，用 Neo4j 圖資料庫替換了舊的 NoSQL Cassandra 資料庫。

這個被大改的系統名字叫 Behance，是 Adobe 在 15 年釋出的一個内容社交平台，有大概 1 千萬的使用者，在這裡人們可以分享自己的創作給百萬人看。

這樣一個巨大的遺留系統本來是通過 Cassandra 和 MongoDB 搭建的，基于曆史遺留問題，系統有不少的性能瓶頸不得不解決。 MongoDB 和 Cassandra 的讀取性能慢主要因為原先的系統設計采用了 fan-out 的設計模式——受關注多的使用者發表的内容會單獨分發給每個讀者，這種設計模式也導緻了網絡架構的大延遲，此外 Cassandra 本身的運維也需要不小的技術團隊，這也是一個很大的問題。

在這裡為了搭建一個靈活、高效、穩定的系統來提供消息 feeding 并最小化資料存儲的規模，Adobe 決定遷移原本的 Cassandra 資料庫到 Neo4j 圖資料庫。 在 Neo4j 圖資料庫中采用一種所謂的 Tiered relationships 來表示使用者之間的關系，這個邊的關系可以去定義不同的通路狀态，比如：僅部分使用者可見，僅關注者可見這些基本操作。 資料模型如圖所示

使用這種資料模型并使用 Leader-follower 架構來優化讀寫，這個平台獲得了巨大的性能提升：

1. 運維需求的時長在使用了 Neo4j 以後下降了 300%。
2. 存儲需求降低了 1000 倍， Neo4j 僅需 50G 存儲資料， 而 Cassandra 需要 50TB。
3. 僅僅需要 3 個服務執行個體就可以支援整個伺服器的流暢運作，之前則需要 48 個。鄭州試管嬰兒費用：http://jbk.39.net/yiyuanfengcai/tsyl_zztjyy/3100/

結論