多跳查詢?yōu)槠髽I(yè)提供了深入的數(shù)據(jù)洞察和分析能力，它在小紅書眾多在線業(yè)務(wù)中扮演重要的角色。然而，這類查詢往往很難滿足穩(wěn)定的 P99 時延要求。小紅書基礎(chǔ)架構(gòu)存儲團隊針對這一挑戰(zhàn)，基于大規(guī)模并行處理（MPP）的理念，開發(fā)了一種圖數(shù)據(jù)庫上的分布式并行查詢框架，成功將多跳查詢的時延降低了 50% 以上，尤其是使 3 跳查詢在在線場景從不能用到落地，極大地增強了在線業(yè)務(wù)的數(shù)據(jù)處理能力。

本文核心貢獻在于：團隊提出了一種從框架層面優(yōu)化多跳查詢時延的方案，在業(yè)務(wù)上使在線場景中使用多跳查詢成為可能，在技術(shù)上實現(xiàn)了圖數(shù)據(jù)庫查詢的框架級優(yōu)化。全文將從以下幾個方面依次展開：

• 介紹小紅書使用圖數(shù)據(jù)庫的背景，并分析多跳查詢在實際業(yè)務(wù)中因時延高而受限的現(xiàn)狀（需求是什么）
• 深入探討 REDgraph 架構(gòu)，揭示原有查詢模式的不足和可優(yōu)化點（存在的問題）
• 詳細闡述優(yōu)化原查詢模式的方案，并提供部分實現(xiàn)細節(jié)（改進方案）
• 通過一系列性能測試，驗證優(yōu)化措施的有效性（改進后效果）

本方案為具有復(fù)雜查詢需求的在線存儲產(chǎn)品提供了優(yōu)化思路，歡迎業(yè)界同行深入探討。

同時，作者再興曾在「DataFunCon 2024·上海站」分享過本議題，感興趣的同學歡迎點擊“閱讀原文”，回看完整錄播視頻。

一、背景

1.1 圖數(shù)據(jù)庫在小紅書的使用場景

小紅書是一個以社區(qū)屬性為主的產(chǎn)品，覆蓋多個領(lǐng)域，鼓勵用戶通過圖文、短視頻、直播等形式記錄和分享生活點滴。在社交領(lǐng)域中，我們存在多種實體，如用戶、筆記、商品等，它們之間構(gòu)成了復(fù)雜的關(guān)系網(wǎng)絡(luò)。為高效處理這些實體間的一跳查詢，小紅書自研了圖存儲系統(tǒng) REDtao，滿足極致性能的需求。

（參見：小紅書如何應(yīng)對萬億級社交網(wǎng)絡(luò)關(guān)系挑戰(zhàn)？圖存儲系統(tǒng) REDtao 來了！）

面對更為復(fù)雜的多跳查詢場景，我們自研了圖數(shù)據(jù)庫系統(tǒng) REDgraph，將多跳查詢的需求應(yīng)用于小紅書多個業(yè)務(wù)領(lǐng)域，包括但不限于：

• 社區(qū)推薦：利用用戶間的關(guān)系鏈和分享鏈，為用戶推薦可能感興趣的好友、筆記和視頻。這類推薦機制通常涉及多于一跳的復(fù)雜關(guān)系。
• 風控場景：通過分析用戶和設(shè)備的行為模式，識別可能的欺詐行為（如惡意薅羊毛），從而保護平臺免受濫用和作弊行為的影響。
• 電商場景：構(gòu)建商品與商品、商品與品牌之間的關(guān)聯(lián)模型，優(yōu)化商品分類和推薦，從而提升用戶的購物體驗。

在傳統(tǒng)的 SQL 產(chǎn)品（如 MySQL）中，想實現(xiàn)這些多跳查詢，通常需要在一個查詢語句中寫多個 JOIN，這樣的性能無疑是較差的。若想利用鍵值存儲 KV 產(chǎn)品實現(xiàn)，則需要分多次發(fā)送 get 請求，并自行處理中間結(jié)果，實現(xiàn)過程也較為麻煩。

相比之下，圖數(shù)據(jù)庫的設(shè)計理念為處理這類查詢提供了天然優(yōu)勢。在圖數(shù)據(jù)庫中，數(shù)據(jù)表被抽象為頂點，表之間的關(guān)系被抽象為邊，并且邊作為一等公民被存儲和處理。這樣一來，執(zhí)行 n 度關(guān)系查詢只需查詢 n 次邊表，大大簡化查詢過程，并提高了效率。

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

小紅書在社交、風控及離線任務(wù)調(diào)度等場景中均采用了圖數(shù)據(jù)庫，然而在實際應(yīng)用過程中遇到了一些挑戰(zhàn)。

場景一：社交推薦

在社交推薦中，我們希望能夠及時地將用戶可能感興趣的好友或內(nèi)容推薦給他們。例如，如果用戶 A 關(guān)注了用戶 B，而用戶 B 點贊了筆記 C，那么用戶 D（也點贊了筆記 C）就可能成為用戶 A 的潛在好友，使小紅書的好友社區(qū)建立更豐富的連接。

業(yè)務(wù)當然可以使用離線任務(wù)分析，基于分析結(jié)果進行推薦，但社交圖譜是無時無刻不在變化，基于離線分析做出的推薦往往是滯后的。如果推薦得更及時，能更好地抓住一些潛在的用戶關(guān)系，建立更豐富完善的社交圖譜，賦能其他業(yè)務(wù)（如：社區(qū)興趣小組，電商商品推薦）。

業(yè)務(wù)希望能即時向用戶推送可能感興趣的 “好友” 或 “內(nèi)容”，如果能即時完成此推薦，則能有效優(yōu)化用戶使用體驗，提升留存率。然而，由于先前 REDgraph 在某些方面的能力尚未完善，導致三跳時延比較高，所以業(yè)務(wù)一直只采用了一跳和兩跳查詢。

場景二：社區(qū)生態(tài)與風險控制

小紅書致力于促進社區(qū)生態(tài)的健康發(fā)展，對優(yōu)質(zhì)內(nèi)容創(chuàng)作者提供獎勵。然而，這也吸引了一些作弊用戶想薅羊毛。例如，作弊用戶可能會通過組織點贊來提升低質(zhì)量筆記的排名，將低質(zhì)筆記偽造成優(yōu)質(zhì)筆記以賺取獎勵。

風控業(yè)務(wù)需要對這種行為予以識別并防范，借助圖數(shù)據(jù)庫的多跳查詢，我們構(gòu)建出一個包含用戶和筆記為頂點、點贊為邊的復(fù)雜關(guān)系圖（“用戶->筆記-> ... ->用戶->筆記“）。隨后，對每篇筆記查詢其多度關(guān)系（筆記 -> 用戶 -> 筆記 -> 用戶）上作弊用戶的比例，若比例高于一定閾值，把筆記打上作弊標簽，系統(tǒng)便不對作弊用戶和作弊筆記發(fā)放獎勵。

打標行為往往是實時消費消息隊列去查詢圖數(shù)據(jù)庫，如果查詢動作本身比較慢，則會造成整體消費積壓。例如，如果一個查詢?nèi)蝿?wù)本應(yīng)在 12:00 執(zhí)行，但由于性能問題直到 12:10 才開始觸發(fā)，那么在這十分鐘的延遲期間，一篇劣質(zhì)筆記已成為優(yōu)質(zhì)筆記，作者薅羊毛成功。等到發(fā)現(xiàn)這是作弊用戶時，顯然「為時晚矣」，因為損失已經(jīng)造成了。

具體來說，社交推薦場景要求三跳的 P99 低于 50 毫秒，風控場景則要求三跳的 P99 低于 200 毫秒，這是目前 REDgraph 所面臨的一大難題。那為何一至二跳可行，三跳及以上就難以實現(xiàn)呢？對此，我們基于圖數(shù)據(jù)庫與其他類型系統(tǒng)在工作負載的差異，做了一些難點與可行性分析。

1.3 難點與可行性分析

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

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

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

最后，查詢失敗代價方面。OLTP 一次查詢的成本較低，因此其失敗的代價也低；而 OLAP 由于需要消耗大量的計算資源，因此其失敗代價很高。圖查詢在這塊，更像 OLTP 場景一些，能夠容忍一些失敗，但畢竟訪問的數(shù)據(jù)量較大，在查一遍代價稍高，因此同樣歸屬到中等。

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

此外正如上文指出的，在小紅書業(yè)務(wù)場景中，三跳查詢的首要目標還是降低延遲。有些系統(tǒng)中會考慮犧牲一點時延來換取吞吐的大幅提升，而這在小紅書業(yè)務(wù)上是不可接受的。如果吞吐上不去，還可以通過擴大集群規(guī)模來作為兜底方案，而如果時延高則直接不能使用了。

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

2.1 REDgraph 架構(gòu)

REDgraph 的整體結(jié)構(gòu)如上圖所示，其與當前較為流行的 NewSQL，如 TiDB 的架構(gòu)構(gòu)相似，采用了存算分離 + shared-nothing 的架構(gòu)。奇包含三類節(jié)點：

• Meta 服務(wù)：負責管理圖數(shù)據(jù)庫的元信息，包括數(shù)據(jù)模式（Schema）、用戶賬號和權(quán)限、存儲分片的位置信息、作業(yè)與后臺任務(wù)等；
• Graph 服務(wù)：負責處理用戶的查詢請求，并做相應(yīng)的處理，涵蓋查詢的解析、校驗、優(yōu)化、調(diào)度、執(zhí)行等環(huán)節(jié)。其本身是無狀態(tài)的，便于彈性擴縮容；
• Storgae 服務(wù)：負責數(shù)據(jù)的物理存儲，其架構(gòu)分為三層。最上層是圖語義 API，將 API 請求轉(zhuǎn)換為對 Graph 的鍵值（KV）操作；中間層采用 Raft 協(xié)議實現(xiàn)共識機制，確保數(shù)據(jù)副本的強一致性和高可用性；最底層是單機存儲引擎，使用 rocksdb 來執(zhí)行數(shù)據(jù)的增刪查等操作。

2.2 圖切分方式

圖切分的含義是，如果我們擁有一個巨大的圖，規(guī)模在百億到千億水平，應(yīng)該如何將其存儲在集群的各節(jié)點之中，即如何對其切分。在工業(yè)界中，主要存在兩種典型的切分策略：邊切分和點切分。

邊切分，以頂點為中心，這種切分策略的核心思想是每個頂點會根據(jù)其 ID 進行哈希運算，并將其路由到特定的分片上。每個頂點上的每條邊在磁盤中都會被存儲兩份，其中一份與起點位于同一分片，另一份則與終點位于同一分片。

點切分，與邊切分相對應(yīng)，也就是以邊為中心做哈希打散，每個頂點會在集群內(nèi)保存多份。

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

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

2.3 優(yōu)化方案 1.0

·  通用性差，且在 3 跳場景中效果還不夠。

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

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

2.4 新方案思考

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

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

由于耗時大頭在查詢層，所以我們重點關(guān)注這塊。因為查詢計劃的優(yōu)化是一個無止境的工程，用戶可能會寫出各種查詢語句，產(chǎn)生各種算子，難以找到一個通用且可收斂的方案來覆蓋所有情況。而執(zhí)行引擎則可以有一個相對固定的優(yōu)化方案，因此我們優(yōu)先選擇了優(yōu)化執(zhí)行引擎。

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

2.5 原多跳查詢執(zhí)行流程

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

2.6 可優(yōu)化點分析

2.6.1 Barrier 等待使時延增加

從上述物理執(zhí)行中可以看出：查詢節(jié)點必須等所有存儲節(jié)點的響應(yīng)返回后，才會執(zhí)行后面的算子。這樣即使大多數(shù)存儲節(jié)點很快返回，只要有一個「慢存儲節(jié)點」存在，整個查詢都得 block 住。

在圖計算（AP）場景中，一次計算往往要經(jīng)過很多輪迭代（Epoch），并且每輪迭代后都需要進行全局指標的更新，更新完再繼續(xù)下一輪迭代。在 Epoch 之間插入 Barrier 做同步是有必要的。

但在圖查詢（TP）場景中，通常不需要全局性更新，只是在下發(fā)請求時對起點 ID 做去重，即使有往往也是在查詢的最后一步，因此沒有必要 barrier。

此外，圖數(shù)據(jù)庫負載往往呈現(xiàn)出“冪律分布”現(xiàn)象，即少數(shù)頂點鄰居邊多、多數(shù)頂點鄰居邊少；REDgraph 本身也是以邊切分的方式存儲數(shù)據(jù)，這就使得「慢存儲節(jié)點」很容易出現(xiàn)。加之某個存儲節(jié)點的網(wǎng)絡(luò)抖動或節(jié)點負載高等因素，可能導致響應(yīng)時間進一步延長，影響查詢效率。

如圖所示，如果查詢層收到一個響應(yīng)就處理一個響應(yīng)（類似于 pipeline 的機制），則能避免無意義的空等，從整體上加速查詢的執(zhí)行。

2.6.2 查詢層串行執(zhí)行效率低

在整個查詢計劃中，只有 GetNeighbor 算子是在多個存儲節(jié)點上并行執(zhí)行，而其他算子是在查詢節(jié)點上串行執(zhí)行，這里我們想到兩個問題：

• 串行執(zhí)行的效率天然低于并行執(zhí)行。只有在數(shù)據(jù)量太少或者計算邏輯太簡單的情況下，上下文切換的開銷會超過并行的收益。在正常負載的圖查詢場景中，數(shù)據(jù)量和計算邏輯都挺可觀；
• 當多個存儲節(jié)點的響應(yīng)數(shù)據(jù)匯聚到查詢節(jié)點時，數(shù)據(jù)量仍然相當可觀。如果能在 storaged 節(jié)點上完成這些計算，將顯著減少查詢節(jié)點需要處理的數(shù)據(jù)量。

我們在業(yè)務(wù)的線上集群和性能測試顯示：GetNeighbors 和 GetVertices 不是所有算子中最耗時的，反倒是不起眼的 Project 算子往往耗費更多時間，特別是那些緊隨 GetNeighbors 和 GetVertices 之后的 Project 算子，因為它不僅需要執(zhí)行數(shù)據(jù)投影，還負責將 map 展平。

這表明整個查詢的主要瓶頸在于計算量大。而查詢計劃中大部分都是純計算型算子，將它們并行化對于提升查詢效率很有必要。

2.6.3 查詢結(jié)果轉(zhuǎn)發(fā)浪費 IO

如上文所說，在圖查詢場景中一般不需要做全局性的更新，查詢節(jié)點收到各存儲節(jié)點的響應(yīng)后，只是簡單地再次分區(qū)然后下發(fā)，所以存儲節(jié)點的結(jié)果轉(zhuǎn)發(fā)到查詢層，再從查詢節(jié)點分發(fā)到各存儲節(jié)點很浪費。

如果存儲節(jié)點自身具備路由和分發(fā)的能力，那可以讓存儲節(jié)點執(zhí)行完 GetNeighbors 算子后，接著執(zhí)行 Project、InnerJoin 等算子，每當遇到下一個 GetNeighbor 算子時，自行組織請求并分發(fā)給其他存儲節(jié)點。其他存儲節(jié)點收到后接著執(zhí)行后面的算子，以此規(guī)則往復(fù)，直到最后一步將結(jié)果匯聚到查詢層，統(tǒng)一返回給客戶端。

2.7 改造后的執(zhí)行流程

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

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

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

三、分布式并行查詢的實現(xiàn)

分布式并行查詢的具體實現(xiàn)，涉及到許多個關(guān)鍵點，接下來介紹其中一些細節(jié)。

3.1 如何保證不對 1-2 跳產(chǎn)生負優(yōu)化

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

這樣，當接收到用戶的執(zhí)行計劃后，便可根據(jù)其跳數(shù)選擇不同的處理路徑。若為 1 至 2 跳，則仍沿用原有的流程，因為原有的流程能夠滿足 1-2 跳的業(yè)務(wù)需求，而 3 跳及以上則采用分布式查詢。

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

原有代碼中每一個操作都是用算子方式實現(xiàn)。為了讓分布式并行查詢的實現(xiàn)與原有框架兼容，我們把「轉(zhuǎn)發(fā)」也定義為一個算子，取名為 Forward。這一算子的功能類似于 Spark 中的 Shuffle 算子、或 OceanBase 中的 Exchange 算子，關(guān)鍵在于它能夠確保查詢在分布式環(huán)境中順暢執(zhí)行。

我們對查詢計劃進行了以下關(guān)鍵改寫：

• 在每個要「切換分區(qū)才能執(zhí)行的」算子前（例如 GetNeighbors、GetVertices 等），我們添加一個 FORWARD 算子。FORWARD 算子負責記錄分區(qū)的依據(jù)，通常是起點 ID。
• 為了將分布式節(jié)點的查詢結(jié)果有效地匯總，我們在查詢計劃的末端添加了 CONVERGE 算子，它指示各節(jié)點將結(jié)果發(fā)送回 DistDriver 節(jié)點，即最初接收用戶請求的節(jié)點。
• 隨后，我們引入了 MERGE 算子，它的作用是對所有從節(jié)點收到的結(jié)果進行匯總，并將最終結(jié)果返回給客戶端。

通過這種方式，當 REDgraph-Server 準備執(zhí)行 GetNeighbors、GetVertices 算子時，它會首先執(zhí)行 FORWARD、CONVERGE算子，將必要的數(shù)據(jù)和查詢計劃轉(zhuǎn)發(fā)到其他服務(wù)器。這樣，其他服務(wù)器在接收到請求后，就能明確自己的任務(wù)和所需的數(shù)據(jù)，從而推動查詢計劃的執(zhí)行。

值得注意的是，F(xiàn)ORWARD 和 CONVERGE算子都有「轉(zhuǎn)發(fā)/發(fā)送」數(shù)據(jù)的含義，不過它們的側(cè)重點不太一樣：

• FORWARD 強調(diào)的是路由轉(zhuǎn)發(fā)，并且要指定轉(zhuǎn)發(fā)的依據(jù)，即 partitionKey 字段，不同的數(shù)據(jù)行會根據(jù)其 partitionKey 字段值的不同轉(zhuǎn)發(fā)到不同的節(jié)點上；
• CONVERGE 強調(diào)的是發(fā)送匯聚，具有單一確定的目標節(jié)點，即 DistDriver；

因它們只是在做轉(zhuǎn)發(fā)/發(fā)送的工作，我們將這類算子統(tǒng)稱為「路由」算子。

在改造后的查詢計劃中，從 START 算子開始，直到遇到「路由」算子，這多個算子都可以在某個節(jié)點本地執(zhí)行的，因此我們將這一系列算子劃分到一個 stage 內(nèi)。整個查詢計劃由多個 stage 組成，其中首尾兩個 stage 在 DistDriver 上執(zhí)行，中間的 stage 在 DistWorker 上執(zhí)行。

需要注意的是：stage 是一個邏輯概念，具體執(zhí)行時，每個 stage 會依據(jù)分區(qū)和所屬節(jié)點產(chǎn)生多個 task，這些 task 會分布在多個節(jié)點上執(zhí)行，每個節(jié)點僅訪問本節(jié)點內(nèi)數(shù)據(jù)，無需跨網(wǎng)絡(luò)拉取數(shù)據(jù)。這種結(jié)構(gòu)化的方法極大地提高了查詢的并行性和效率。

3.3 如何做熱點處理

在原查詢模式中，每一次在發(fā)起 GetNeighbors 算子前，查詢層會對起點 ID 去重（查詢計劃中 GetNeighbors 算子的 dedup 為 true），收到存儲節(jié)點的響應(yīng)后，再依靠后續(xù)算子將結(jié)果按需展平，因此存儲節(jié)點不會產(chǎn)生重復(fù)查詢。以下圖舉例說明：

原查詢模式的執(zhí)行流程可簡單描述為：

1. 第一跳從存儲層查到 A->C 和 B->C，返回到查詢層；
2. 查詢層會 Project 得到兩個 C，以備后面做 InnerJoin；
3. 準備執(zhí)行第二跳，構(gòu)造起點集合時，由于 dedup 為 true，僅會保留一個 C；
4. 第二跳從存儲層查到 C->D 和 C->E，返回到查詢層；
5. 查詢層執(zhí)行 InnerJoin，由于此前有兩個 C，所以 C->D 和 C->E 也各會變成兩個；
6. 查詢層再次 Project 取出 dstId2，得到結(jié)果 D、D、E、E。

從步驟 4 可以看到，存儲層不會產(chǎn)生重復(fù)查詢。

改造成分布式查詢后，我們只能在每個 stage 內(nèi)去重。但由于缺乏全局 barrier，多個 stage 先后往某個 DistWorker 轉(zhuǎn)發(fā)請求時，多個請求之間可能有重復(fù)的起點，會在存儲層產(chǎn)生重復(fù)查詢和計算，導致 CPU 開銷增加以及查詢時延增加。

如果每一跳產(chǎn)生的重復(fù)終點 ID（將會作為下一跳的起點 ID）很多，分布式查詢反而會帶來劣勢。為解決這一問題，我們引入一套起點 ID 去重機制 —— NeighborCache，具體方案如下：

因為沒有全局的 Barrier，無法在下發(fā)請求之前去重，我們選擇在存儲節(jié)點上提供一個 NeighborCache，其本質(zhì)就是一個 map，可表示為 map<vid +="" edgetype,="" list>。在執(zhí)行 GetNeighbors 算子前，存儲節(jié)點會首先檢查 NeighborCache，如果找到相應(yīng)的條目，則直接使用這些數(shù)據(jù)填充結(jié)果集；如果沒有找到，則訪問存儲層獲取數(shù)據(jù)，并更新 NeighborCache，讀取和更新 Cache 需要用讀寫鎖做好互斥。

另外，NeighborCache 還具有如下特點：

• 每當有更新 vid + edgeType 的請求時，都會先 invalidate cache 中對應(yīng)的條目，以此來保證緩存與數(shù)據(jù)的一致性；
• 即使沒有更新操作存在，cache 內(nèi)的每個 kv 條目存活時間也很短，通常為秒級，超過時間就會被自動刪除。為什么這么短呢？

• 充分性：由于在線圖查詢（OLTP）的特性，用戶的多跳查詢通常在幾秒到十幾秒內(nèi)完成。而 NeighborCache 只是為了去重而設(shè)計，來自于不同 DistWorker 的 GetNeighbors 請求大概率不會相隔太長時間到達，所以 cache 本身也不需要存活太久；
• 必要性：從 map 結(jié)構(gòu)的 key 就會發(fā)現(xiàn)，當 qps 較高，跳數(shù)多，頂點的鄰居邊多時，此 map 要承載的數(shù)據(jù)量是非常大的，所以也不能讓其存活的時間太久，否則很容易 OOM；

• 在填充 cache 前會做內(nèi)存檢查，如果本節(jié)點當前的內(nèi)存水位已經(jīng)比較高，則不會填充，以避免節(jié)點 OOM。

通過這種起點 ID 去重機制，我們能夠有效地減少重復(fù)查詢，提高分布式查詢的效率和性能。

3.4 如何做負載均衡

第四個問題是怎么做負載均衡，包括存儲的均衡和計算的均衡。

首先，存儲的均衡在以邊切分的圖存儲里面其實是很難的，因為它天然的就是把頂點和其鄰居全部都存在了一起，這是圖數(shù)據(jù)庫相比其他數(shù)據(jù)庫的優(yōu)勢，也是其要承擔的代價。所以目前沒有一個徹底的解決方法，只能在真的碰到此問題時擴大集群規(guī)模，讓數(shù)據(jù)的哈希打散能夠更加均勻一些，避免多個熱點都落在同一個機器的情況。而在目前的業(yè)務(wù)場景上來看，其實負載不均衡的現(xiàn)象不算嚴重，例如風控的一個比較大的集群，其磁盤用量最高和最低的也不超過 10%，所以問題其實并沒有想象中的那么嚴重。

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

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

3.5 如何做流程控制

在分布式查詢架構(gòu)中，由于前面取消全局 Barrier，使得各個 DistWorker 自行驅(qū)動查詢的進行。這種設(shè)計提高了靈活性，但也帶來新的挑戰(zhàn)：

如圖所示，各個 DistWorker 上 stage3 的結(jié)果需要匯聚到 DistDriver 后才能向客戶端返回，但是 DistDriver 只在 stage0 的時候給 Node2 發(fā)送了請求，后面的所有轉(zhuǎn)發(fā)都是由 DistWorker 自行完成的，脫離了 DistDriver 的「掌控」。這樣 DistDriver 就不知道最后有多少個節(jié)點在執(zhí)行 stage3，也就不知道該等待哪些 DistWorker 給它發(fā)送結(jié)果，以及何時可以開始執(zhí)行 stage4。

我們引入一個進度匯報機制：在 DistDriver 上實現(xiàn)一個 Acker，負責接收各個 DistWorker 上報的 stage 執(zhí)行進度信息。每個 stage 向外擴散時，向 Acker 發(fā)送一條消息，記錄當前完成的 stage 和 即將開始的 stage 的節(jié)點數(shù)量。具體而言，就是包含兩個鍵值對：

• 當前的 stage 編號 -> -1；
• 下一個 stage 的編號 -> 執(zhí)行下一個 stage 的節(jié)點的數(shù)量；

比如 Node2 上的 stage-1 擴散到 stage-2 時，目標節(jié)點有 3 個：Node1、Node3、Node5，于是就發(fā)送 {stage-1: -1，stage-2: 3} 的消息到 DistDriver 上，表示有一個節(jié)點完成了 stage-1，有 3 個節(jié)點開始了 stage-2。而由于 stage-1 此前由 Node1 登記過 {stage-1: 1}，這樣一正一負就表示所有的 stage-1 都已經(jīng)執(zhí)行完畢。stage-2 和 stage-3 的更新和判定方式類似，當 DistDriver 發(fā)現(xiàn)所有的前置 stage 數(shù)量都為 0 時，就可以驅(qū)動 stage-4 。

我們實際想要的是每個 stage 數(shù)量的正負抵消能力，而非 {stage-1: -1，stage-2: 3} 的字符串。為了簡化這一過程，我們便采用異或運算（相同為 0，相異為 1）跟蹤各個 stage 的狀態(tài)，舉例說明：

1. Acker 上有一個初始的 checksum 值 0000；
2. stage-0 在擴散到 stage-1 時，生成了一個隨機數(shù) 0010（這里為了表達簡便，以 4 位二進制數(shù)代替），這個 0010 是 Node2 上的 stage-1 的 Id，然后把這個 0010 伴隨著 Forward 請求發(fā)到 Node2 上，同時也發(fā)到 Acker 上，這樣就表示 0010 這個 stage 開始了，Acker 把收到的值與本地的 checksum 做異或運算，得到 0010，并以此更新本地 checksum；
3. stage-1 執(zhí)行完后擴散到 stage-2 時，由于有 3 個目標節(jié)點，就生成 3 個不相同的隨機數(shù) 0101、0001、1010（需要檢查這 3 個數(shù)異或之后不為 0），分別標識 3 個目標節(jié)點上的 stage-2，然后把這 3 個數(shù)伴隨著 Forward 請求發(fā)到 Node1、Node3、Node5 上，同時在本地把自身的 stage Id（0010）和這 3 個數(shù)一起做異或運算，再把運算的結(jié)果發(fā)到 Acker，Acker 再次做異或運算，也就是 0010 ^ (0010 ^ 0101 ^ 0001 ^ 1010），這樣 0010 就被消除掉了，也就表示 stage-1 執(zhí)行完成了；
4. 重復(fù)上述過程，最后 Acker 上的 checksum 會變回 0，表示可以驅(qū)動 stage-4。

注意：盡管在某個節(jié)點的 stage 擴散時檢查了生成的隨機數(shù)異或不為 0，但是多個節(jié)點間生成的隨機數(shù)異或到一起還是可能為 0 的，比如 Node1 的 stage-2 生成的 3 個數(shù)異或后為 0001，Node3 的 stage-2 異或后為 0010，Node5 的 stage-2 異或后為 0011，0001 ^ 0010 ^ 0011 = 0。這樣就會導致 stage-3 還在執(zhí)行中時，DistDriver 就誤認為它已經(jīng)執(zhí)行完畢，提前驅(qū)動 stage-4 的執(zhí)行。

不過考慮到我們實際使用的是 int32 整數(shù)，出現(xiàn)這種的情況的概率非常低。在未來的優(yōu)化中在，我們可以考慮給每個 Node 生成一個 16 位的隨機 Id（由 metad 生成），并保證這些 NodeId 異或結(jié)果不為 0，當 stage 擴散時，將 NodeId 置于隨機數(shù)的高位，確保分布式查詢的每個階段都能被準確跟蹤和協(xié)調(diào)。

另一個重要的問題便是全程鏈路的超時自檢，例如在 stage2 或 stage3 的某一個節(jié)點上運行時間過長，此時不能讓其余所有節(jié)點一直等待，因為客戶端已經(jīng)超時了。因此我們在每個算子內(nèi)部的執(zhí)行邏輯中都設(shè)置了一些埋點，用以檢查算子的執(zhí)行是否超過了用戶側(cè)的限制時間，一旦超過，便立即終止自身的執(zhí)行，從而迅速地自我銷毀，避免資源的無謂浪費。

四、性能測試

我們在改造工程完成后進行了性能測試，采用 LDBC 組織提供的 SNB 數(shù)據(jù)集，生成了一個 SF100 級別的社交網(wǎng)絡(luò)圖譜，規(guī)模達到 3 億頂點，18 億條邊。我們主要考察其一跳、二跳、三跳、四跳等多項查詢性能。

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

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

五、總結(jié)與展望

在過去的較短時間內(nèi)，我們基于 MPP 的理念，對 REDgraph 在分布式并行查詢上進行了深入探索和實踐。本方案能顯著優(yōu)化多跳查詢的性能，并且對業(yè)務(wù)邏輯完全兼容，沒有使用限制條件，屬于框架級的通用優(yōu)化。測試結(jié)果顯示，時延降低了 50% 以上，滿足在線業(yè)務(wù)場景的時延要求，驗證方案的有效性。

目前，許多公司的圖數(shù)據(jù)庫產(chǎn)品在在線場景中仍使用兩跳及以下的查詢。這是因為多跳查詢的時延無法滿足在線業(yè)務(wù)的要需求，導致失去許多潛在的業(yè)務(wù)價值，也未能充分發(fā)揮圖數(shù)據(jù)庫的技術(shù)優(yōu)勢。隨著小紅書 DAU 的持續(xù)增長，業(yè)務(wù)數(shù)據(jù)規(guī)模朝著萬億級規(guī)模遞增，業(yè)務(wù)上使用替代方案的瓶頸會逐漸展露。我們計劃在今年上半年完成開發(fā)工作，并在下半年開始將這套新架構(gòu)逐步應(yīng)用于相關(guān)業(yè)務(wù)場景。

本方案雖然針對的是圖數(shù)據(jù)庫，但其探索實踐對公司其他數(shù)據(jù)庫產(chǎn)品同樣具有重要的參考價值。例如，REDtable 在處理用戶請求時，經(jīng)常需要應(yīng)對復(fù)雜或計算量大的查詢，以往會建議用戶修改代碼來適應(yīng)這些情況。現(xiàn)在，我們可以借鑒本方案，為這些「具有重查詢需求」產(chǎn)品打造高性能執(zhí)行框架，以增強自身的數(shù)據(jù)處理能力。

我們將繼續(xù)提升 REDgraph 的多跳查詢能力，并將其和 REDtao 融合，打造成一個統(tǒng)一的數(shù)據(jù)庫產(chǎn)品，賦能更多業(yè)務(wù)場景。我們誠邀對技術(shù)有極致追求，志同道合的同學一起加入團隊，共同推動圖數(shù)據(jù)技術(shù)的發(fā)展。

六、作者簡介

• 再興 
  小紅書基礎(chǔ)架構(gòu)存儲組工程師，負責自研分布式表格存儲 REDtable（NewSQL），參與分布式圖數(shù)據(jù)庫 REDgraph 的研發(fā)。
• 敬德 
  小紅書基礎(chǔ)架構(gòu)存儲組工程師，負責自研圖存儲系統(tǒng) REDtao 和分布式圖數(shù)據(jù)庫 REDgraph。
• 劉備 
  
  小紅書基礎(chǔ)架構(gòu)存儲組負責人，負責 REDkv / Redis / REDtao / REDtable / REDgraph / MySQL 的整體架構(gòu)和技術(shù)演進。