一、背景介紹

1. 圖數(shù)據(jù)庫(kù)介紹

關(guān)于圖數(shù)據(jù)庫(kù)的概念，這里不作詳細(xì)闡述。而是以圖表的形式，對(duì)其與另外幾種 NoSQL 產(chǎn)品進(jìn)行比較。圖數(shù)據(jù)庫(kù)本身歸屬于 NoSQL 存儲(chǔ)，而諸如KV 類(lèi)型、寬表類(lèi)型、文檔類(lèi)型、時(shí)序類(lèi)型等其他 NoSQL 產(chǎn)品，各自具備獨(dú)特的特性。從上圖左側(cè)的坐標(biāo)軸中可以看到，從 KV 到寬表、文檔，再到圖，數(shù)據(jù)關(guān)聯(lián)度和查詢(xún)復(fù)雜度是越來(lái)越高的。前三者，即 KV、寬表和文檔，主要關(guān)注的是單個(gè)記錄內(nèi)部的豐富性，但并未涉及記錄間的關(guān)系。而圖數(shù)據(jù)庫(kù)則專(zhuān)注于處理這些關(guān)系。圖數(shù)據(jù)庫(kù)主要適用于需要挖掘深鏈路或多維度關(guān)系的業(yè)務(wù)場(chǎng)景。

接下來(lái)通過(guò)一個(gè)具體示例，再來(lái)對(duì)比一下圖數(shù)據(jù)庫(kù)與關(guān)系型數(shù)據(jù)庫(kù)。這是社交網(wǎng)絡(luò)中常見(jiàn)的一種表結(jié)構(gòu)，包括四個(gè)數(shù)據(jù)表：用戶(hù)表、好友關(guān)系表、點(diǎn)贊行為表以及筆記詳情表。比如要查詢(xún) Tom 這個(gè)用戶(hù)的好友所點(diǎn)贊的筆記的詳細(xì)信息，那么可能需要編寫(xiě)一段冗長(zhǎng)的 SQL 語(yǔ)句。在該 SQL 語(yǔ)句中，涉及到三個(gè) join 操作，首先將用戶(hù)表和好友關(guān)系表進(jìn)行連接，從而獲取 Tom 的所有好友信息。然后，將得到的中間結(jié)果與點(diǎn)贊行為表進(jìn)行連接，以確定 Tom 的好友都點(diǎn)贊了哪些筆記。最后，還需要對(duì)先前生成的臨時(shí)表和筆記詳情表進(jìn)行連接，以便最終獲取這些筆記的全部?jī)?nèi)容。

關(guān)系型數(shù)據(jù)庫(kù)中的 join 操作通常復(fù)雜度較高，其執(zhí)行過(guò)程中需消耗大量的 CPU 資源、內(nèi)存空間以及 IO，雖然我們可以通過(guò)精心的設(shè)計(jì)，例如針對(duì)所要關(guān)聯(lián)的列創(chuàng)建索引，以降低掃描操作的比例，通過(guò)索引匹配來(lái)實(shí)現(xiàn)一定程度的性能提升。然而，這樣的舉措所產(chǎn)生的成本相對(duì)較高，因?yàn)樗行碌膱?chǎng)景都需要?jiǎng)?chuàng)建索引，要考慮如何撰寫(xiě) SQL 中的 join 條件，選擇哪個(gè)表作為驅(qū)動(dòng)表等等，這些都需要耗費(fèi)大量的精力和時(shí)間。

而如果采用圖數(shù)據(jù)庫(kù)，則會(huì)簡(jiǎn)單很多。首先進(jìn)行圖建模，創(chuàng)建兩類(lèi)頂點(diǎn)，分別為用戶(hù)和筆記，同時(shí)創(chuàng)建兩類(lèi)邊，一類(lèi)是好友關(guān)系，即用戶(hù)到用戶(hù)的邊；另一類(lèi)是用戶(hù)到筆記的點(diǎn)贊關(guān)系。當(dāng)我們將這些數(shù)據(jù)存儲(chǔ)到圖數(shù)據(jù)庫(kù)中時(shí)，它們?cè)谶壿嬌铣尸F(xiàn)出一種網(wǎng)狀結(jié)構(gòu)，其關(guān)聯(lián)關(guān)系已經(jīng)非常明確。查詢(xún)時(shí)，如上圖中使用 Gremlin 語(yǔ)句，僅需四行代碼即可獲取到所需的信息。其中第一行 g.V().has('name', 'Tom')，用于定位 Tom 節(jié)點(diǎn)，兩個(gè) out 子句，第一個(gè) out 子句用于查找 Tom 的好友，第二個(gè) out 子句用于查找 Tom 的點(diǎn)贊筆記。當(dāng)?shù)诙€(gè) out 子句執(zhí)行完畢后，就可以遍歷所有外部的綠色頂點(diǎn)，即筆記節(jié)點(diǎn)。最后，讀取它們的 content 屬性?？梢园l(fā)現(xiàn)，與關(guān)系型數(shù)據(jù)庫(kù)相比，圖數(shù)據(jù)庫(kù)的查詢(xún)語(yǔ)句更加簡(jiǎn)潔、清晰易懂。

此外，圖數(shù)據(jù)庫(kù)還有一個(gè)更為顯著的優(yōu)勢(shì)，就是在存儲(chǔ)時(shí)，它已經(jīng)將頂點(diǎn)及其關(guān)系作為一等公民進(jìn)行設(shè)計(jì)和存儲(chǔ)，因此在進(jìn)行鄰接邊訪(fǎng)問(wèn)和關(guān)系提取時(shí)，效率極高。即使數(shù)據(jù)規(guī)模不斷擴(kuò)大，也不會(huì)導(dǎo)致查詢(xún)時(shí)間顯著增加。

2. 圖數(shù)據(jù)庫(kù)在小紅書(shū)的使用場(chǎng)景

小紅書(shū)是一個(gè)年輕的生活方式共享平臺(tái)。在小紅書(shū)，用戶(hù)可以通過(guò)短視頻、圖片等方式，直觀(guān)地記錄生活的點(diǎn)點(diǎn)滴滴。在小紅書(shū)內(nèi)部，圖數(shù)據(jù)庫(kù)被廣泛應(yīng)用于多種場(chǎng)景中，下面將分別列舉在線(xiàn)、近線(xiàn)以及離線(xiàn)場(chǎng)景的實(shí)例。

第一個(gè)案例是社交實(shí)時(shí)推薦功能。小紅書(shū)具有典型的社區(qū)特性，用戶(hù)可以在其中點(diǎn)贊、發(fā)布貼文、關(guān)注他人、轉(zhuǎn)發(fā)信息等。譬如我進(jìn)入某用戶(hù)主頁(yè)并停留了較長(zhǎng)時(shí)間，那么系統(tǒng)便會(huì)判定我對(duì)該用戶(hù)有興趣，而這個(gè)用戶(hù)可能同樣吸引了他人的注意。因此，系統(tǒng)會(huì)將該用戶(hù)的其他關(guān)注者以及他們所關(guān)注的其他用戶(hù)推薦給我，因?yàn)槲覀冇泄餐呐d趣愛(ài)好，所以他們的關(guān)注內(nèi)容我也有可能感興趣，這便是一種簡(jiǎn)單的實(shí)時(shí)推薦機(jī)制。

第二個(gè)案例是社區(qū)風(fēng)控機(jī)制，小紅書(shū)社區(qū)會(huì)對(duì)優(yōu)質(zhì)筆記或優(yōu)質(zhì)視頻的創(chuàng)作者進(jìn)行獎(jiǎng)勵(lì)，但這也給了一些羊毛黨可乘之機(jī)，他們發(fā)布一些質(zhì)量較低的帖子或筆記，將其發(fā)布在互刷群中，或者轉(zhuǎn)發(fā)給親朋好友，讓他們點(diǎn)贊和轉(zhuǎn)發(fā)，從而偽裝成所謂的高質(zhì)量筆記，以此來(lái)騙取平臺(tái)的獎(jiǎng)勵(lì)。社區(qū)業(yè)務(wù)部門(mén)擁有一些離線(xiàn)算法，能夠?qū)σ延械臄?shù)據(jù)進(jìn)行分析，識(shí)別出哪些用戶(hù)和筆記屬于作弊用戶(hù)，在圖中用紅色的點(diǎn)標(biāo)出。在近線(xiàn)場(chǎng)景中，系統(tǒng)會(huì)判斷每個(gè)頂點(diǎn)在多跳關(guān)系內(nèi)接觸到的作弊用戶(hù)的數(shù)量或比例，如果超過(guò)一定的閾值，則會(huì)將這個(gè)人標(biāo)記為潛在的風(fēng)險(xiǎn)用戶(hù)，即黃色的頂點(diǎn)，進(jìn)而采取防范措施。

第三個(gè)案例是離線(xiàn)任務(wù)的調(diào)度問(wèn)題，在大數(shù)據(jù)平臺(tái)中，往往存在大量的離線(xiàn)任務(wù)，而任務(wù)之間的依賴(lài)關(guān)系錯(cuò)綜復(fù)雜，如何合理地調(diào)度任務(wù)，成為一個(gè)棘手的問(wèn)題。圖結(jié)構(gòu)非常適合解決這類(lèi)問(wèn)題，通過(guò)拓?fù)渑判蚧蚱渌惴?，可以找出最受依?lài)的任務(wù)，并進(jìn)行反向推理。

3. 業(yè)務(wù)上面臨的困境

小紅書(shū)在社交、風(fēng)控及離線(xiàn)任務(wù)調(diào)度等場(chǎng)景中均采用了圖數(shù)據(jù)庫(kù)，然而在實(shí)際應(yīng)用過(guò)程中遇到了諸多挑戰(zhàn)。在此，簡(jiǎn)要介紹其中基于實(shí)時(shí)推薦場(chǎng)景的一個(gè)痛點(diǎn)。

業(yè)務(wù)訴求是能即時(shí)向用戶(hù)推送可能感興趣的“好友”或“內(nèi)容”，如圖所示，A 與 F 之間僅需經(jīng)過(guò)三次跳躍即可到達(dá)，因此 A 與 F 構(gòu)成了一種可推薦的關(guān)聯(lián)關(guān)系，如果能即時(shí)完成此推薦，則能有效提升用戶(hù)使用體驗(yàn)，提升留存率。然而，由于先前 REDgraph 在某些方面的能力尚未完善，業(yè)務(wù)一直只采用了一跳和兩跳查詢(xún)，未使用三跳，風(fēng)控場(chǎng)景也是類(lèi)似。

業(yè)務(wù)對(duì)時(shí)延的具體要求為，社交推薦要求三跳的 P99 低于 50 毫秒，風(fēng)控則要求三跳的 P99 低于 200 毫秒，這是目前 REDgraph 所面臨的一大難題。

那為何一至二跳可行，三跳及以上就難以實(shí)現(xiàn)呢？對(duì)此，我們基于圖數(shù)據(jù)庫(kù)與其他類(lèi)型系統(tǒng)在工作負(fù)載的差異，做了一些難點(diǎn)與可行性分析。

首先在并發(fā)方面，OLTP 的并發(fā)度很高，而 OLAP 則相對(duì)較低。圖的三跳查詢(xún)，服務(wù)的仍然是在線(xiàn)場(chǎng)景，其并發(fā)度也相對(duì)較高，這塊更貼近 OLTP 場(chǎng)景。

其次在計(jì)算復(fù)雜度方面，OLTP 場(chǎng)景中的查詢(xún)語(yǔ)句較為簡(jiǎn)單，包含一到兩個(gè) join 操作就算是較為復(fù)雜的情況了，因此，OLTP 的計(jì)算復(fù)雜度相對(duì)較低。OLAP 則是專(zhuān)門(mén)為計(jì)算設(shè)計(jì)的，因此其計(jì)算復(fù)雜度自然較高。圖的三跳查詢(xún)則介于 OLTP 和 OLAP 之間，它雖不像 OLAP 那樣需要執(zhí)行大量的計(jì)算，但其訪(fǎng)問(wèn)的數(shù)據(jù)量相對(duì)于 OLTP 來(lái)說(shuō)還是更可觀(guān)的，因此屬于中等復(fù)雜度。

第三，數(shù)據(jù)時(shí)效性方面，OLTP 對(duì)時(shí)效性的要求較高，必須基于最新的數(shù)據(jù)提供準(zhǔn)確且實(shí)時(shí)的響應(yīng)。而在 OLAP 場(chǎng)景中則沒(méi)有這么高的時(shí)效要求，早期的 OLAP 數(shù)據(jù)庫(kù)通常提供的是 T+1 的時(shí)效。圖的三跳查詢(xún)，由于我們服務(wù)的是在線(xiàn)場(chǎng)景，所以對(duì)時(shí)效性有一定的要求，但并不是非常高。使用一小時(shí)或 10 分鐘前的狀態(tài)進(jìn)行推薦，也不會(huì)產(chǎn)生過(guò)于嚴(yán)重的后果。因此，我們將其定義為中等時(shí)效性。

最后，查詢(xún)失敗代價(jià)方面。OLTP 一次查詢(xún)的成本較低，因此其失敗的代價(jià)也低；而 OLAP 由于需要消耗大量的計(jì)算資源，因此其失敗代價(jià)很高。圖查詢(xún)?cè)谶@塊，更像 OLTP 場(chǎng)景一些，但畢竟訪(fǎng)問(wèn)的數(shù)據(jù)量較大，因此同樣歸屬到中等。

總結(jié)一下：圖的三跳查詢(xún)具備 OLTP 級(jí)別的并發(fā)度，卻又有比一般 OLTP 大得多的數(shù)據(jù)訪(fǎng)問(wèn)量和計(jì)算復(fù)雜度，所以比較難在在線(xiàn)場(chǎng)景中使用。好在其對(duì)數(shù)據(jù)時(shí)效性的要求沒(méi)那么高，也能容忍一些查詢(xún)失敗，所以我們能?chē)L試對(duì)其優(yōu)化。

正如前面提到的，在小紅書(shū)，三跳查詢(xún)的首要目標(biāo)還是降低延遲。有些系統(tǒng)中會(huì)考慮犧牲一點(diǎn)時(shí)延來(lái)?yè)Q取吞吐的大幅提升，而這在小紅書(shū)業(yè)務(wù)上是不可接受的。如果吞吐上不去，還可以通過(guò)擴(kuò)大集群規(guī)模來(lái)兜底，而如果時(shí)延高則直接不能使用了。

二、原架構(gòu)問(wèn)題分析

第二部分將詳述原體系結(jié)構(gòu)中所存在的問(wèn)題及其優(yōu)化措施。

1. RedGraph 整體架構(gòu)

REDgraph 的整體結(jié)構(gòu)如上圖所示，其與當(dāng)前較為流行的 NewSQL，如 TiDB 的架構(gòu)構(gòu)相似。采用了存儲(chǔ)和計(jì)算分離的架構(gòu)，并且存儲(chǔ)是 shared-nothing 的。三類(lèi)節(jié)點(diǎn)分別為 meta-server，元信息的管理；query-server，用戶(hù)查詢(xún)請(qǐng)求的處理；store-server，存儲(chǔ)數(shù)據(jù)。

2. RedGraph 圖切分方式

圖切分的含義為，如果我們擁有一個(gè)巨大的圖，規(guī)模在百億到千億水平，應(yīng)該如何將其存儲(chǔ)在分布式集群之中，以及如何對(duì)其進(jìn)行切分。在工業(yè)界中，主要存在兩種典型的切分策略，即邊切分和點(diǎn)切分。

邊切分，以頂點(diǎn)為中心，這種切分策略的核心思想是每個(gè)頂點(diǎn)會(huì)根據(jù)其 ID 進(jìn)行哈希運(yùn)算，并將其路由到特定的分片上。每個(gè)頂點(diǎn)上的每條邊在磁盤(pán)中都會(huì)被存儲(chǔ)兩份，其中一份與起點(diǎn)位于同一分片，另一份則與終點(diǎn)位于同一分片。如上圖中的例子，其中涉及到 ABC 三個(gè)頂點(diǎn)的哈希定位結(jié)果。在這個(gè)例子中，A 至 C 的這條出邊，被放置在與 A 同一個(gè)節(jié)點(diǎn)上。同樣，B 至 C 的出邊跟 B 放到了一起，最后一個(gè)桶中保存了 C 以及 C 的入邊，即由 A 和 B 指向 C 的兩條入邊。

點(diǎn)切分，與邊切分相對(duì)應(yīng)，以邊為中心，每個(gè)頂點(diǎn)會(huì)在集群內(nèi)保存多份。

這兩種切分方式各有利弊。邊切分的優(yōu)點(diǎn)在于每個(gè)頂點(diǎn)與其鄰居都保存在同一個(gè)分片中，因此當(dāng)需要查詢(xún)某個(gè)頂點(diǎn)的鄰居時(shí)，其訪(fǎng)問(wèn)局部性極佳；其缺點(diǎn)在于容易負(fù)載不均，且由于節(jié)點(diǎn)分布的不均勻性，引發(fā)熱點(diǎn)問(wèn)題。點(diǎn)切分則恰恰相反，其優(yōu)點(diǎn)在于負(fù)載較為均衡，但缺點(diǎn)在于每個(gè)頂點(diǎn)會(huì)被切成多個(gè)部分，分配到多個(gè)機(jī)器上，因此更容易出現(xiàn)同步問(wèn)題。

REDgraph 作為一個(gè)在線(xiàn)的圖查詢(xún)系統(tǒng)，選擇的是邊切分的方案。

3. 優(yōu)化方案 1.0

我們之前已經(jīng)實(shí)施了一些優(yōu)化，可以稱(chēng)之為優(yōu)化方案 1.0。當(dāng)時(shí)主要考慮的是如何快速滿(mǎn)足用戶(hù)需求，因此我們的方案包括：首先根據(jù)常用的查詢(xún)模式提供一些定制化的算法，這些算法可以跳過(guò)解析、校驗(yàn)、優(yōu)化和執(zhí)行等繁瑣步驟，直接處理請(qǐng)求，從而實(shí)現(xiàn)加速。其次，我們會(huì)對(duì)每個(gè)頂點(diǎn)的扇出操作進(jìn)行優(yōu)化，即每個(gè)頂點(diǎn)在向外擴(kuò)展時(shí)，對(duì)其擴(kuò)展數(shù)量進(jìn)行限制，以避免超級(jí)點(diǎn)的影響，降低時(shí)延。此外，我們還完善了算子的下推策略，例如 filter、sample、limit 等，使其盡可能在存儲(chǔ)層完成，以減少網(wǎng)絡(luò)帶寬的消耗。同時(shí)，我們還允許讀從節(jié)點(diǎn)、讀寫(xiě)線(xiàn)程分離、提高垃圾回收頻率等優(yōu)化。

然而，這些優(yōu)化策略有一個(gè)共性，就是每個(gè)點(diǎn)都比較局部化和零散，因此其通用性較低。比如第一個(gè)優(yōu)化，如果用戶(hù)需要發(fā)起新的查詢(xún)模式，那么此前編寫(xiě)的算法便無(wú)法滿(mǎn)足其需求，需要另行編寫(xiě)。第二個(gè)優(yōu)化，如果用戶(hù)所需要的是頂點(diǎn)的全部結(jié)果，那此項(xiàng)也不再適用。第三個(gè)優(yōu)化，如果查詢(xún)中本身就不存在這些運(yùn)算符，那么自然也無(wú)法進(jìn)行下推操作。諸如此類(lèi)，通用性較低，因此需要尋找一種更為通用，能夠減少重復(fù)工作的優(yōu)化策略。

4. 新方案思考

如上圖中，是對(duì)一個(gè)耗時(shí)接近一秒的三跳查詢(xún)的 profile 分析。我們發(fā)現(xiàn)在每一跳產(chǎn)出的記錄數(shù)量上，第一跳至第二跳擴(kuò)散了 200 多倍，第二跳至第三跳擴(kuò)散了 20 多倍，表現(xiàn)在結(jié)果上，需要計(jì)算的數(shù)據(jù)行數(shù)從 66 條直接躍升至 45 萬(wàn)條，產(chǎn)出增長(zhǎng)速度令人驚訝。此外，我們發(fā)現(xiàn)三跳算子在整個(gè)查詢(xún)過(guò)程中占據(jù)了較大的比重，其在查詢(xún)層的耗時(shí)更是占據(jù)了整個(gè)查詢(xún)的 80% 以上。

那么應(yīng)該如何進(jìn)行優(yōu)化呢？在數(shù)據(jù)庫(kù)性能優(yōu)化方面，有許多可行的方案，主要分為三大類(lèi)：存儲(chǔ)層的優(yōu)化、查詢(xún)計(jì)劃的優(yōu)化以及執(zhí)行引擎的優(yōu)化。

由于耗時(shí)大頭在查詢(xún)層，所以我們重點(diǎn)關(guān)注這塊。因?yàn)椴樵?xún)計(jì)劃的優(yōu)化是一個(gè)無(wú)止境的工程，用戶(hù)可能會(huì)寫(xiě)出各種查詢(xún)語(yǔ)句，產(chǎn)生各種算子，難以找到一個(gè)通用且可收斂的方案來(lái)覆蓋所有情況。而執(zhí)行引擎則可以有一個(gè)相對(duì)固定的優(yōu)化方案，因此我們優(yōu)先選擇了優(yōu)化執(zhí)行引擎。

圖數(shù)據(jù)庫(kù)的核心就是多跳查詢(xún)執(zhí)行框架，而其由于數(shù)據(jù)量大，計(jì)算量大，導(dǎo)致查詢(xún)時(shí)間較長(zhǎng)，因此我們借鑒了 MPP 數(shù)據(jù)庫(kù)和其他計(jì)算引擎的思想，提出了分布式并行查詢(xún)的解決方案。

原有的多跳查詢(xún)執(zhí)行流程如上圖所示。假設(shè)我們要查詢(xún)933 頂點(diǎn)的三跳鄰居節(jié)點(diǎn) ID，即檢索到藍(lán)圈中的所有頂點(diǎn)。經(jīng)過(guò)查詢(xún)層處理后，將生成右圖所示執(zhí)行計(jì)劃，START 表示計(jì)劃的起點(diǎn)，本身并無(wú)實(shí)際操作。GetNeighbor 算子則負(fù)責(zé)實(shí)際查詢(xún)頂點(diǎn)的鄰居，例如根據(jù) 933 找到 A 和 B。后續(xù)的 Project、InnerJoin 以及 Project 等操作均為對(duì)先前產(chǎn)生的結(jié)果進(jìn)行數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換、處理及裁剪等操作，以確保整個(gè)計(jì)算流程的順利進(jìn)行。正是后續(xù)的這幾個(gè)算子耗費(fèi)的時(shí)延較高。

算子的物理執(zhí)行過(guò)程如上圖所示。查詢(xún)服務(wù)器（Query Server）執(zhí)行 START 指令后，將請(qǐng)求發(fā)送至存儲(chǔ)節(jié)點(diǎn)（Store Server）中的一個(gè)，該節(jié)點(diǎn)獲取其鄰居信息，并反饋至查詢(xún)層。查詢(xún)層接收到結(jié)果后，會(huì)對(duì)其中的數(shù)據(jù)進(jìn)行去重或其他相關(guān)處理，然后再次下發(fā)，此次的目標(biāo)是另外兩個(gè) Store Server。這一步驟即為獲取二度鄰居的信息，返回至查詢(xún)層后，再對(duì)這些結(jié)果進(jìn)行匯總和去重處理，如此往復(fù)。

在整個(gè)流程中，我們明顯觀(guān)察到三個(gè)問(wèn)題。首先，圖中藍(lán)色方框內(nèi)的算子都是串行運(yùn)行的，必須等待前一個(gè)計(jì)算完成后，才能執(zhí)行下一個(gè)。對(duì)于大規(guī)模的數(shù)據(jù)，串行執(zhí)行的效率顯然無(wú)法與并行執(zhí)行相提并論。其次，Query Server 內(nèi)部存在一個(gè)同步點(diǎn)，即左側(cè)標(biāo)注為紅色的字（等待所有響應(yīng)返回），要求 query Server 等待所有存儲(chǔ)節(jié)點(diǎn)的響應(yīng)返回后，才能繼續(xù)執(zhí)行后續(xù)操作。若某一存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù)量較大或負(fù)載過(guò)高，導(dǎo)致響應(yīng)速度較慢，則會(huì)耗費(fèi)大量時(shí)間在等待上，因此我們考慮取消同步等待的過(guò)程。最后，存儲(chǔ)層的結(jié)果需要先轉(zhuǎn)發(fā)回查詢(xún)層進(jìn)行簡(jiǎn)單處理，然后再向下發(fā)送，這無(wú)疑增加了不必要的轉(zhuǎn)發(fā)成本。如果存儲(chǔ)節(jié)點(diǎn)（Store Server）能夠自行轉(zhuǎn)發(fā)，便可避免一次網(wǎng)絡(luò)轉(zhuǎn)發(fā)過(guò)程，從而降低開(kāi)銷(xiāo)。

相應(yīng)的解決策略便是三點(diǎn)：算子并行執(zhí)行，取消同步點(diǎn)，以及讓 Store Server 的結(jié)果直接轉(zhuǎn)發(fā)。基于此，我們提出了如下的改造思路。

首先，查詢(xún)服務(wù)器（Query Server）將整個(gè)執(zhí)行計(jì)劃以及執(zhí)行計(jì)劃所需的初始數(shù)據(jù)傳輸至存儲(chǔ)服務(wù)器（Store Server），之后 Store Server 自身來(lái)驅(qū)動(dòng)整個(gè)執(zhí)行過(guò)程。以 Store Server 1 為例，當(dāng)它完成首次查詢(xún)后，便會(huì)根據(jù)結(jié)果 ID 所在的分區(qū)，將結(jié)果轉(zhuǎn)發(fā)至相應(yīng)的 Store Server。各個(gè) Store Server 可以獨(dú)立地繼續(xù)進(jìn)行后續(xù)操作，從而實(shí)現(xiàn)整個(gè)執(zhí)行動(dòng)作的并行化，并且無(wú)同步點(diǎn)，也無(wú)需額外轉(zhuǎn)發(fā)。

需要說(shuō)明的是，圖中右側(cè)白色方框比左側(cè)要矮一些，這是因?yàn)閿?shù)據(jù)由上方轉(zhuǎn)到下方時(shí)，進(jìn)行了分區(qū)下發(fā)，必然比在查詢(xún)服務(wù)器接收到的總數(shù)據(jù)量要少。

可以看到，在各部分獨(dú)立驅(qū)動(dòng)后，并未出現(xiàn)等待或額外轉(zhuǎn)發(fā)的情況，Query Server 只需在最后一步收集各個(gè) Store Server 的結(jié)果并聚合去重，然后返回給客戶(hù)端。如此一來(lái)，整體時(shí)間相較于原始模型得到了顯著縮短。

三、分布式并行查詢(xún)實(shí)現(xiàn)

分布式并行查詢(xún)的具體實(shí)現(xiàn)，涉及到多個(gè)關(guān)鍵元素。接下來(lái)介紹其中一些細(xì)節(jié)。

1. 如何保證不對(duì) 1-2 跳產(chǎn)生負(fù)優(yōu)化

首先一個(gè)問(wèn)題是，在進(jìn)行改造時(shí)如何確保不會(huì)對(duì)原始的 1-2 跳產(chǎn)生負(fù)優(yōu)化。在企業(yè)內(nèi)部進(jìn)行新的改造和優(yōu)化時(shí)，必須謹(jǐn)慎評(píng)估所采取的措施是否會(huì)對(duì)原有方案產(chǎn)生負(fù)優(yōu)化。我們不希望新方案還未能帶來(lái)收益，反而破壞了原有的系統(tǒng)。因此，架構(gòu)總體上與原來(lái)保持一致。在 Store Server 內(nèi)部插入了一層，稱(chēng)為執(zhí)行層，該層具有網(wǎng)絡(luò)互聯(lián)功能，主要用于分布式查詢(xún)的轉(zhuǎn)發(fā)。Query Server 層則基本保持不變。

這樣，當(dāng)接收到用戶(hù)的執(zhí)行計(jì)劃后，便可根據(jù)其跳數(shù)選擇不同的處理路徑。若為 1 至 2 跳，則仍沿用原有的流程，因?yàn)樵械牧鞒棠軌驖M(mǎn)足 1-2 跳的業(yè)務(wù)需求，而 3 跳及以上則采用分布式查詢(xún)。

2. 如何與原有執(zhí)行框架兼容

第二個(gè)關(guān)鍵問(wèn)題是如何維持與原有執(zhí)行框架的兼容性，即在進(jìn)行分布式技術(shù)改造時(shí)，不希望對(duì)原有代碼進(jìn)行大幅修改，而希望通過(guò)最小化的調(diào)整達(dá)到目的。這里參考了其他產(chǎn)品的一些思路，具體來(lái)說(shuō)，就是在一些需要切換分區(qū)訪(fǎng)問(wèn)的算子（如 GetNeighbor 等）之前，添加具有路由功能的算子。這里有三種，分別為 Forward、Converge 和 Merge。Forward 的作用顯而易見(jiàn)，即當(dāng)遇到任何運(yùn)算符時(shí)，表示數(shù)據(jù)需要轉(zhuǎn)發(fā)給其他節(jié)點(diǎn)處理，而當(dāng)前節(jié)點(diǎn)無(wú)法繼續(xù)處理。Converge 運(yùn)算符則是在整個(gè)執(zhí)行計(jì)劃的最后一步添加，用于指示最終結(jié)果應(yīng)返回至最初接收用戶(hù)請(qǐng)求的節(jié)點(diǎn)。在 Converge 后，還需添加一個(gè) Merge 運(yùn)算符，該節(jié)點(diǎn)在收到結(jié)果后需要進(jìn)行聚合操作，然后才能將結(jié)果返回給客戶(hù)端。如此修改后，我們只需實(shí)現(xiàn)這三個(gè)算子本身，無(wú)需對(duì)其他算子進(jìn)行任何修改，且不會(huì)對(duì)網(wǎng)絡(luò)層造成干擾，實(shí)現(xiàn)了極輕量級(jí)的改造。在執(zhí)行計(jì)劃修改的過(guò)程中，我們還進(jìn)行了一些額外的優(yōu)化，例如將 GroupBy、OrderBy 等算子也進(jìn)行了下推處理。

3. 如何做熱點(diǎn)處理

第三問(wèn)題是如何進(jìn)行熱點(diǎn)處理，或者說(shuō)是重復(fù) ID 的處理。當(dāng)整個(gè)執(zhí)行流程改造成由 Store Server 自行驅(qū)動(dòng)之后，會(huì)出現(xiàn)一種情況，例如邊 AC 和邊 BC 位于兩個(gè)不同的 Store Server 上，查詢(xún)都是單跳的操作，可能左側(cè)的機(jī)器查詢(xún) AC 操作更快，而右側(cè)的機(jī)器查詢(xún) BC 操作較慢，因此導(dǎo)致左側(cè)的機(jī)器首先查找到 C，然后將結(jié)果轉(zhuǎn)發(fā)給其他機(jī)器，向下一級(jí)中間機(jī)器查詢(xún) C 的鄰居，即執(zhí)行 GetNeighbor from C，右側(cè)的節(jié)點(diǎn)雖然稍顯滯后，但也需要執(zhí)行查詢(xún) C 鄰居操作。

若不進(jìn)行任何操作，在中間節(jié)點(diǎn)便會(huì)對(duì) C 的鄰居進(jìn)行兩次查詢(xún)，造成資源浪費(fèi)。優(yōu)化策略非常簡(jiǎn)單，即在每個(gè)存儲(chǔ)節(jié)點(diǎn)之上添加 NeighborCache。本質(zhì)是這樣一個(gè) Map 結(jié)構(gòu)，每當(dāng)讀請(qǐng)求到來(lái)時(shí)，首先在 Map 中查找是否存在 C 的鄰節(jié)點(diǎn)，若存在則獲取，否則再訪(fǎng)問(wèn)存儲(chǔ)層，訪(fǎng)問(wèn)完畢后填充 NeighborCache 的條目，每個(gè)條目的生存時(shí)間都非常短暫。之所以短暫，其充分性在于左右節(jié)點(diǎn)發(fā)出請(qǐng)求的間隔肯定不會(huì)很久，不會(huì)達(dá)到數(shù)秒的級(jí)別，否則業(yè)務(wù)上也無(wú)法承受。因此，NeighborCache 的每個(gè)條目也只需存活在秒級(jí)，超過(guò)則自動(dòng)刪除。必要性則在于 Map 的 Key 的組合模式，即 Vid+edgeType 這種組合模式還是非常多的，若不及時(shí)清理，內(nèi)存很容易爆炸。此外，查詢(xún)層從 Disk Store 中查詢(xún)到數(shù)據(jù)并向 NeighborCache 回填時(shí)，也需進(jìn)行內(nèi)存檢查，以避免 OOM。

4. 如何做負(fù)載均衡

第四個(gè)問(wèn)題是怎么做負(fù)載均衡，包括兩塊，一個(gè)是存儲(chǔ)的均衡，另一個(gè)是計(jì)算的均衡。

首先存儲(chǔ)的均衡在以邊切分的圖存儲(chǔ)里面其實(shí)是很難的，因?yàn)樗烊坏木褪前秧旤c(diǎn)和其鄰居全部都存在了一起，這是圖數(shù)據(jù)庫(kù)相比其他數(shù)據(jù)庫(kù)的優(yōu)勢(shì)，也是其要承擔(dān)的代價(jià)。所以目前沒(méi)有一個(gè)徹底的解決方法，只能在真的碰到此問(wèn)題時(shí)擴(kuò)大集群規(guī)模，讓數(shù)據(jù)的哈希打散能夠更加均勻一些，避免多個(gè)熱點(diǎn)都落在同一個(gè)機(jī)器的情況。而在目前的業(yè)務(wù)場(chǎng)景上來(lái)看，其實(shí)負(fù)載不均衡的現(xiàn)象不算嚴(yán)重，例如風(fēng)控的一個(gè)比較大的集群，其磁盤(pán)用量最高和最低的也不超過(guò) 10%，所以問(wèn)題其實(shí)并沒(méi)有想象中的那么嚴(yán)重。

另外一個(gè)優(yōu)化方法是在存儲(chǔ)層及時(shí)清理那些過(guò)期的數(shù)據(jù)，清理得快的話(huà)也可以減少一些不均衡。

計(jì)算均衡的問(wèn)題。存儲(chǔ)層采用了三副本的策略，若業(yè)務(wù)能夠接受弱一致的讀取（實(shí)際上大多數(shù)業(yè)務(wù)均能接受），我們可以在請(qǐng)求轉(zhuǎn)發(fā)時(shí)，查看三副本中的哪個(gè)節(jié)點(diǎn)負(fù)載較輕，將請(qǐng)求轉(zhuǎn)發(fā)至該節(jié)點(diǎn)，以盡量平衡負(fù)載。此外，正如前文所述，熱點(diǎn)結(jié)果緩存也是一種解決方案，只要熱點(diǎn)處理速度足夠快，計(jì)算的不均衡現(xiàn)象便不易顯現(xiàn)。

5. 如何做流程控制

接下來(lái)的問(wèn)題是如何進(jìn)行流程控制。執(zhí)行流程轉(zhuǎn)變?yōu)橛?Store Server 自行驅(qū)動(dòng)之后，僅第一個(gè) Stage 有 Driver 參與，而后續(xù)步驟則由 Worker 之間相互傳輸和控制。那么，Driver 應(yīng)如何了解當(dāng)前執(zhí)行的階段以及其對(duì)應(yīng)的某個(gè) Stage 何時(shí)可以開(kāi)始執(zhí)行呢？有一種解決方案便是要求每一個(gè) Worker 在接收到請(qǐng)求后或下發(fā)請(qǐng)求后，向 Driver 回傳一個(gè)響應(yīng)，如此便可在 Driver 內(nèi)記錄所有節(jié)點(diǎn)的進(jìn)度信息，這是可行的。

然而，此設(shè)計(jì)方案較重，因?yàn)?driver 并不需要深入了解每個(gè)節(jié)點(diǎn)的具體狀態(tài)，它僅需判斷自身是否具備執(zhí)行條件，因此在工程實(shí)現(xiàn)中，我們采取了更為輕便的方式，即每個(gè) Stage 生成一個(gè) 32 位的二進(jìn)制數(shù)字 reqId，將其發(fā)送至 ACKer 確認(rèn)器以傳達(dá)相關(guān)信息。Acker 也以 32 位整數(shù)形式記錄該信息，Stage1 同樣會(huì)接收到 Stage 0 發(fā)來(lái)的 reqId，經(jīng)過(guò)內(nèi)部一系列處理后，它會(huì)將接收到的 reqId 與自身生成的 3 個(gè) reqId 進(jìn)行異或運(yùn)算，并將異或結(jié)果再次發(fā)送至確認(rèn)器。由于異或操作的特性，當(dāng)兩個(gè)數(shù)相同時(shí)，結(jié)果為 0，因此，當(dāng) 0010 數(shù)進(jìn)行異或運(yùn)算后，這部分將變?yōu)?0。這就意味著 Stage 0 已經(jīng)執(zhí)行完畢。后續(xù)的所有階段均采用類(lèi)似的方式，當(dāng)確認(rèn)器的結(jié)果再次變?yōu)?0 時(shí)，表示整個(gè)執(zhí)行流程已經(jīng)完成，即前面的 Stage 0 至 Stage 3  已經(jīng)讀取完畢，此時(shí)可以執(zhí)行 Stage 4，從而實(shí)現(xiàn)流程驅(qū)動(dòng)。

另一個(gè)重要的問(wèn)題便是全程鏈路的超時(shí)自檢，例如在 Stage2 或 Stage3 的某一個(gè)節(jié)點(diǎn)上運(yùn)行時(shí)間過(guò)長(zhǎng)，此時(shí)不能讓其余所有節(jié)點(diǎn)一直等待，因?yàn)榭蛻?hù)端已經(jīng)超時(shí)了。因此我們?cè)诿總€(gè)算子內(nèi)部的執(zhí)行邏輯中都設(shè)置了一些埋點(diǎn)，用以檢查算子的執(zhí)行是否超過(guò)了用戶(hù)側(cè)的限制時(shí)間，一旦超過(guò)，便立即終止自身的執(zhí)行，從而迅速地自我銷(xiāo)毀，避免資源的無(wú)謂浪費(fèi)。

以上就是對(duì)一些關(guān)鍵設(shè)計(jì)的介紹。

6. 性能測(cè)試

我們?cè)诟脑旃こ掏瓿珊筮M(jìn)行了性能測(cè)試，采用 LDBC 組織提供的 SNB 數(shù)據(jù)集，生成了一個(gè) SF100 級(jí)別的社交網(wǎng)絡(luò)圖譜，規(guī)模達(dá)到 3 億頂點(diǎn)，18 億條邊。我們主要考察其一跳、二跳、三跳、四跳等多項(xiàng)查詢(xún)性能。

根據(jù)評(píng)估結(jié)果顯示，在一跳和二跳情況下，原生查詢(xún)和分布式查詢(xún)性能基本相當(dāng)，未出現(xiàn)負(fù)優(yōu)化現(xiàn)象。從三跳起，分布式查詢(xún)相較于原生查詢(xún)能實(shí)現(xiàn) 50% 至 60% 的性能提升。例如，在 Max degree 場(chǎng)景下的分布式查詢(xún)已將時(shí)延控制在 50 毫秒以?xún)?nèi)。在帶有 Max degree 或 Limit 值的情況下，時(shí)延均在 200 毫秒以下。盡管數(shù)據(jù)集與實(shí)際業(yè)務(wù)數(shù)據(jù)集存在差異，但它們皆屬于社交網(wǎng)絡(luò)領(lǐng)域，因此仍具有一定的參考價(jià)值。

四跳查詢(xún)，無(wú)論是原始查詢(xún)還是分布式查詢(xún)，其時(shí)延的規(guī)模基本上都在秒至十余秒的范圍內(nèi)。因?yàn)樗奶樵?xún)涉及的數(shù)據(jù)量實(shí)在過(guò)于龐大，已達(dá)到數(shù)十萬(wàn)甚至百萬(wàn)級(jí)別，僅依賴(lài)分布式并行查詢(xún)難以滿(mǎn)足需求，因此需要采取其他策略。然而，即便如此，我們所提出的改進(jìn)方案相較于原始查詢(xún)模式仍能實(shí)現(xiàn) 50% 至 70% 的提升，效果還是很可觀(guān)的。

四、總結(jié)與展望

我們結(jié)合 MPP 的思想，成功地對(duì)原有 REDgraph 的執(zhí)行流程實(shí)現(xiàn)了框架級(jí)別上的革新，提出了一種較為通用的圖中分布式并行查詢(xún)方案。在完成改良后，至少在業(yè)務(wù)層面上，原本無(wú)法執(zhí)行的三跳任務(wù)現(xiàn)在得以實(shí)現(xiàn)，這無(wú)疑是一項(xiàng)重大突破。同時(shí)，通過(guò)實(shí)驗(yàn)驗(yàn)證，效率得到了 50% 的顯著提升。

隨著小紅書(shū) DAU 的持續(xù)攀升，業(yè)務(wù)數(shù)據(jù)規(guī)模正逐步向著萬(wàn)億的規(guī)模發(fā)展。在這樣的大背景下，業(yè)務(wù)對(duì)多條查詢(xún)的需求也將日益強(qiáng)烈。因此，該方案本身具有優(yōu)化的潛力，具備落地的可能性，且有實(shí)際應(yīng)用的場(chǎng)景。因此，我們將繼續(xù)致力于提升 REDgraph 的查詢(xún)能力。另外，盡管該方案主要在圖數(shù)據(jù)庫(kù)上實(shí)施，但其思想對(duì)于其他具有類(lèi)似重查詢(xún)需求的在線(xiàn)存儲(chǔ)系統(tǒng)同樣具有一定的參考價(jià)值。因此，其他產(chǎn)品也可借鑒此方案，設(shè)計(jì)出符合自身需求的高效執(zhí)行框架。

最后。我們誠(chéng)摯地邀請(qǐng)對(duì)技術(shù)有著極致追求、志同道合的同學(xué)們加入我們的團(tuán)隊(duì)。在此，我們特別推薦兩個(gè)渠道：一是掃描上方二維碼加入微信群，共同探討圖數(shù)據(jù)庫(kù)相關(guān)的技術(shù)問(wèn)題；二是關(guān)注小紅書(shū)的技術(shù)公眾號(hào) REDtech，該公眾號(hào)會(huì)不定期發(fā)布技術(shù)文章，歡迎大家關(guān)注和轉(zhuǎn)發(fā)。

五、問(wèn)答環(huán)節(jié)

Q：介紹中提到的 LDBC-SF 100 那個(gè)數(shù)據(jù)集選擇測(cè)試樣本的規(guī)模有多大？另外，分布式方式能夠提升性能，但分布式實(shí)施過(guò)程中可能會(huì)帶來(lái)消息通信的成本開(kāi)支，反而可能導(dǎo)致測(cè)試結(jié)果表現(xiàn)不佳，可否介紹一下小紅書(shū)的解決方法。

A：三跳基本上都是在幾十萬(wàn)的量級(jí)。

關(guān)于分布式引發(fā)的消息通信，這確實(shí)是一個(gè)問(wèn)題，但在我們的場(chǎng)景下，目前這還不是最嚴(yán)重的問(wèn)題。因?yàn)槊恳惶?，特別是三跳中產(chǎn)生的數(shù)據(jù)量是巨大的，計(jì)算算子處理這些數(shù)據(jù)量所需的時(shí)間已經(jīng)遠(yuǎn)遠(yuǎn)超過(guò)了消息通信的耗時(shí)。尤其是在多跳并存的環(huán)境中，比如一跳和二跳，其實(shí)它們作為中間結(jié)果其數(shù)據(jù)量并不大，一跳只有幾十上百個(gè)，二跳可能也就幾萬(wàn)個(gè)，但是三跳作為最后的需要參與計(jì)算的結(jié)果直接到了幾十萬(wàn)，所以通信開(kāi)銷(xiāo)跟這個(gè)比起來(lái)，其實(shí)是非常微小的。

在消息通信方面，我們也有一些解決思路，比如在發(fā)送端開(kāi)一些很小的窗口（比如 5 毫秒）來(lái)做一些聚合，把那些目標(biāo)點(diǎn)相同的請(qǐng)求進(jìn)行聚合，這樣可以減少一些通信的請(qǐng)求次數(shù)。