本文由小紅書基礎架構存儲組空洞和劉備分享，原題“小紅書如何應對萬億級社交網(wǎng)絡關系挑戰(zhàn)？圖存儲系統(tǒng) REDtao 來了！”，本文有修訂和改動。

小紅書是一個社區(qū)屬性為主的產(chǎn)品，它涵蓋了各個領域的生活社區(qū)，并存儲海量的社交網(wǎng)絡關系。

為了解決社交場景下超大規(guī)模數(shù)據(jù)的更新與關聯(lián)讀取問題，并減少數(shù)據(jù)庫壓力和成本，我們自研了面向超大規(guī)模社交網(wǎng)絡的圖存儲系統(tǒng) REDtao，大大提高了系統(tǒng)穩(wěn)定性。該系統(tǒng)借鑒了 Facebook 的圖存儲系統(tǒng)設計，將緩存和底層數(shù)據(jù)庫封裝起來，并對外提供統(tǒng)一的圖查詢 API，實現(xiàn)了訪問收斂，同時在緩存中實現(xiàn)了高效的邊聚合。

本文將為你分享小紅書面向超大規(guī)模社交網(wǎng)絡的圖存儲系統(tǒng)REDtao的架構設計與技術實踐過程，希望能帶給你啟發(fā)。

空洞：小紅書基礎架構存儲組，負責圖存儲系統(tǒng) REDtao 和分布式緩存的研發(fā)。

劉備：小紅書基礎架構存儲組負責人，負責REDkv / REDtao / REDtable / REDgraph 的整體架構和技術演進。

基礎架構存儲組是給小紅書的業(yè)務部門提供穩(wěn)定可靠的存儲和數(shù)據(jù)庫服務，滿足業(yè)務對存儲產(chǎn)品的功能、性能、成本和穩(wěn)定性要求。目前負責自研分布式 KV、分布式緩存、圖存儲系統(tǒng)、圖數(shù)據(jù)庫和表格存儲。

已上線的存儲產(chǎn)品包括：

小紅書是以年輕人為主的生活記錄、分享平臺，用戶可以通過短視頻、圖文等形式記錄生活點滴，分享生活方式。

在小紅書的社交領域里，我們有用戶、筆記、商品等實體，這些實體之間有各種各樣的關系。

例如：用戶與筆記之間可能存在“擁有”（發(fā)布）、“點贊”、“收藏”等三種關系，同時還存在對應的反向關系“被點贊”，“被收藏”等。

小紅書的社交圖譜數(shù)據(jù)已經(jīng)達到了萬億條邊的規(guī)模，且增長速度非?？?。當用戶登陸小紅書時，每個用戶都會看到關注的好友、粉絲、點贊、收藏以及其他為其量身定做的內(nèi)容。

這些信息高度個性化，需要實時從這些海量社交關系數(shù)據(jù)中讀取用戶相關信息。這是一個讀為主的過程，讀取壓力非常大。

過去，我們將這些社交圖譜數(shù)據(jù)都存儲在運維成熟的 MySQL 數(shù)據(jù)庫中。

然而，即使我們只有百萬請求每秒的規(guī)模，MySQL 的 CPU 使用率仍然到達了 55% 。隨著用戶和 DAU 爆發(fā)式的增長，需要不斷擴容 MySQL 數(shù)據(jù)庫，這帶來了巨大的成本和穩(wěn)定性壓力。

為了解決這些問題且考慮到?jīng)]有合適的開源方案，2021 年初我們開啟了從 0 到 1 自研 REDtao 的歷程。

4.1方案調(diào)研

我們充分調(diào)研了業(yè)內(nèi)其他廠商的實現(xiàn)，發(fā)現(xiàn)有著強社交屬性的公司基本上都有一個自研的圖存儲系統(tǒng)（如下圖所示）。

比如：

考慮到當時我們的社交圖譜數(shù)據(jù)已經(jīng)存放在 MySQL 數(shù)據(jù)庫上且規(guī)模巨大，而社交圖譜數(shù)據(jù)服務是非常重要的服務，對穩(wěn)定性的要求非常高。回溯 Facebook 當年遇到的問題和我們類似，數(shù)據(jù)存儲在 Memcache 和 MySQL 中。因此，參考 Facebook 的 Tao 圖存儲系統(tǒng)更貼合我們的實際情況和已有的技術架構，風險更小。

4.2API設計

社交圖譜的訪問主要是邊的關系查詢。

我們的圖模型將關系表示為一個?<key, value>?對，其中 key 是 (?FromId,??AssocType,??ToId?) 的三元組，value?是屬性的??JSON 格式。

比如“用戶 A ”關注“用戶 B ”，映射到 REDtao 的數(shù)據(jù)存儲結構為：

1<FromId:用戶A的ID, AssocType：關注， ToId：用戶B的ID>? ->? Value （屬性的json字段）

我們對業(yè)務方的需求進行分析，封裝了 25 個圖語義的 API 給業(yè)務方使用，滿足了其增刪改查的需求，并收斂業(yè)務方的使用方式。

相比于 Facebook 的 Tao，我們還補充了社交圖譜所需要的圖語義，為反作弊場景提供了額外的過濾參數(shù)。

同時，在緩存層面，我們支持對不同的字段在緩存中配置局部二級索引。

下面給一些典型的使用場景。

1）場景一：獲取關注了 A 的所有正常用戶（并且剔除作弊用戶）：

1getAssocs(“被關注類型”, 用戶A的ID, 分頁偏移量, 最大返回值, 只返回正常用戶，是否按照時間從新到舊)

2）場景二：獲取 A 的粉絲個數(shù)（并且剔除作弊用戶）：

1getAssocCount(“被關注類型”, 用戶A的ID, 只返回正常用戶)

REDtao 的架構設計考慮了下面這幾個關鍵的要素：

整體架構分為三層：

業(yè)務方通過 REDtao SDK 接入服務。

如下圖：

在這個架構中：和 Facebook Tao 不一樣的是，我們的緩存層是一個獨立的分布式集群，和下面的持久層是解耦的。緩存層和下面的持久層可以獨立的擴容縮容，緩存分片和 MySQL 分片不需要一一對應，這樣帶來了更好的靈活性，MySQL 集群也變成了一個可以插拔替換的持久存儲。

1）讀流程：客戶端將讀請求發(fā)送給 router，router 接收到 RPC 請求后，根據(jù)邊類型選擇對應的 REDtao 集群，根據(jù)三元組 (?FromId,??AssocType,??ToId?) 通過一致性 Hash 計算出分片所在的 Follower 節(jié)點，將請求轉發(fā)到該節(jié)點上。Follower 節(jié)點接收到該請求，首先查詢本地的圖緩存，如果命中則直接返回結果。如果沒有命中，則將請求轉發(fā)給 Leader 節(jié)點。同樣的，Leader 節(jié)點如果命中則返回，如果不命中則查詢底層 MySQL 數(shù)據(jù)庫。

2）寫流程：客戶端將寫請求發(fā)送給 router，和讀流程一樣，會轉發(fā)到對應的 Follower 節(jié)點上。Follower 節(jié)點會轉發(fā)寫請求給 Leader 節(jié)點，Leader 節(jié)點轉發(fā)給 MySQL，當 MySQL 返回寫入成功后，Leader 會清除本地圖緩存對應的 Key，并同步給其他所有 Follower 清除掉該 Key，保證數(shù)據(jù)的最終一致性。

REDtao 分為獨立的兩層：緩存層和持久層。每一層都保證高可用性。

1）自研的分布式緩存：

我們自研了實現(xiàn)圖語義的分布式 cache 集群，支持故障自動檢測和恢復、水平擴縮容。

它是一個雙層 cache，每個分片都有一個 Leader 和若干個 Follower。所有的請求都先發(fā)給外層的 Follower，再由 Follower 轉發(fā)給 Leader。這樣的好處是讀壓力大的時候只需要水平擴展 Follower，單點 Leader 寫入的方式也降低了復雜度，更容易實現(xiàn)數(shù)據(jù)的一致性。

如果一個副本故障，系統(tǒng)會在秒級別內(nèi)進行切換。當持久層發(fā)生故障時，分布式緩存層仍然可以對外提供讀取服務。

2）高可用的MySQL集群：

MySQL 集群通過自研的中間件實現(xiàn)了分庫分表方案，并支持 MySQL 的水平擴容。每個 MySQL 數(shù)據(jù)庫有若干從庫，并且與公司內(nèi)部其他的 MySQL 運維方案一致，保證高可用性。

3）限流保護功能：

為防止緩存擊穿導致 MySQL 突發(fā)大量請求，從而導致 MySQL 宕機，我們通過限制每個主節(jié)點最大 MySQL 并發(fā)請求數(shù)來實現(xiàn)限流保護 MySQL。達到最大并發(fā)請求限制之后的請求會被掛起等待，直到已有請求被處理返回，或者達到等待超時請求被拒絕不會被繼續(xù)請求到 MySQL 。限流閾值在線可調(diào)，根據(jù) MySQL 集群規(guī)模調(diào)整對應限制。

為防止爬蟲或者作弊用戶頻繁刷同一條數(shù)據(jù)，我們利用 REDtaoQueue 順序執(zhí)行對寫入或者點查同一條邊的請求，隊列長度會被限制，控制同一時間大量相同的請求執(zhí)行。相比于單個全局的隊列控制所有請求的方式，基于每個請求的隊列可以很好地限制單個同一請求，而不影響其他正常請求。

數(shù)據(jù)結構的設計是 REDtao 高性能的重要保證。

我們采用了三層嵌套 HashTable 的設計, 通過根據(jù)某個起點 from_id 從第一級 HashTable 中查找到 REDtaoGraph，記錄了所有 type 下對應的所有的出邊信息。

接著，在第二級 HashTable 中，根據(jù)某個 type_id 查找到 AssocType 對應某個 type 下邊所有出邊的計數(shù)、索引以及其他元數(shù)據(jù)。

最終在最后一級 HashTable ，通過 AssocType 的某個 to_id 查找到最終邊信息。

我們記錄了創(chuàng)建時間、更新時間、版本、數(shù)據(jù)以及 REDtaoQueue，time_index 則對應根據(jù)創(chuàng)建時間排序列表。

最后一級 HashTable 以及索引限制存儲最新的 1000 個邊信息，以限制超級點占據(jù)過多內(nèi)存，同時集中提高最新熱數(shù)據(jù)的查詢命中率以及效率。REDtaoQueue 用于排隊當前某個關系的讀寫，只記錄了當前最后一個請求的元數(shù)據(jù)。

每次查詢或?qū)懭霑r，首先查詢 REDtaoAssoc：

通過這種多層 hash+ 跳表的設計，我們能高效地組織點、邊、索引、時間序鏈表之間的關系。內(nèi)存的申請、釋放在同一個線程上完成。

在線上環(huán)境中，我們的系統(tǒng)可以在一臺 16 核的云廠商虛擬機上跑到 150w 查詢請求/s，同時 CPU 利用率僅有 22.5% 。下方是線上集群的一個監(jiān)控圖，單機的 QPS 到達 3w ，每個 RPC 請求聚合了 50 個查詢。

1）豐富的圖語義 API ：

我們在 REDtao 中封裝了 25 個圖語義的 API 給業(yè)務方使用，滿足了業(yè)務方的增刪改查的需求。業(yè)務方無需自行編寫 SQL 語句即可實現(xiàn)相應操作，使用方式更加簡單和收斂。

2）統(tǒng)一的訪問 URL ：

由于社區(qū)后端數(shù)據(jù)太大，我們按照不同的服務和優(yōu)先級拆分成了幾個 REDtao 集群。

為了讓業(yè)務方不感知后端的集群拆分邏輯，我們實現(xiàn)了統(tǒng)一的接入層。

不同的業(yè)務方只需使用同一個服務 URL ，通過 SDK 將請求發(fā)送到接入層。接入層會接收到不同業(yè)務方的圖語義的請求，并根據(jù)邊的類型路由到不同的 REDtao 集群。它通過訂閱配置中心，能夠?qū)崟r感知到邊的路由關系，從而實現(xiàn)統(tǒng)一的訪問 URL，方便業(yè)務方使用。

作為社交圖譜數(shù)據(jù)，數(shù)據(jù)的一致性至關重要。我們需要嚴格保證數(shù)據(jù)的最終一致性以及一定場景下的強一致性。為此，我們采取了以下措施：

1）緩存更新沖突的解決：

REDtao 為每個寫入請求生成一個全局遞增的唯一版本號。在使用 MySQL 數(shù)據(jù)更新本地緩存時，需要比較版本號，如果版本號比緩存的數(shù)據(jù)版本低，則會拒絕此更新請求，以避免沖突。

2）寫后讀的一致性：

Proxy 會將同一個 fromId 的點或邊請求路由到同一個讀 cache 節(jié)點上，以保證讀取數(shù)據(jù)一致性。

3）主節(jié)點異常場景：

Leader 節(jié)點收到更新請求后，會將更新請求變?yōu)?invalidate cache 請求異步的發(fā)送給其他 follower，以保證 follower 上的數(shù)據(jù)最終一致。在異常情況下，如果 Leader 發(fā)送的隊列已滿導致 invalidate cache 請求丟失，那么會將其他的 follower cache 全部清除掉。

如果 Leader 故障，新選舉的 Leader 也會通知其他 follower 將 cache 清除。

此外，Leader 會對訪問 MySQL 的請求進行限流，從而保證即使個別分片的cache被清除掉也不會將 MySQL 打崩。

4）少量強一致的請求：

由于 MySQL 的從庫也提供讀服務，對于少量要求強一致的讀請求，客戶端可以將請求染上特殊標志，REDtao 會透傳該標志，數(shù)據(jù)庫 Proxy 層會根據(jù)該標志將讀請求轉發(fā)到 MySQL 主庫上，從而保證數(shù)據(jù)的強一致。

跨云多活是公司的重要戰(zhàn)略，也是 REDtao 支持的一個重要特性。

REDtao 的跨云多活架構整體如下：

這里不同于 Facebook Tao 的跨云多活實現(xiàn)，F(xiàn)acebook Tao 的跨云多活實現(xiàn)如下圖所示。

Facebook 的方案依賴于底層的 MySQL 的主從復制都通過 DTS Replication 來做。而 MySQL 原生的主從復制是自身功能，DTS 服務并不包含 MySQL 的主從復制。該方案需要對 MySQL 和 DTS 做一定的改造。前面說到，我們的緩存和持久層是解藕的，在架構上不一樣。

因此，REDtao 的跨云多活架構是我們結合自身場景下的設計，它在不改動現(xiàn)有 MySQL 功能的前提下實現(xiàn)了跨云多活功能。

1）持久層我們通過 MySQL 原生的主從 binlog 同步將數(shù)據(jù)復制到其他云的從庫上。其他云上的寫請求和少量要求強一致讀將被轉發(fā)到主庫上。正常的讀請求將讀取本區(qū)的 MySQL 數(shù)據(jù)庫，滿足讀請求對時延的要求。

2）緩存層的數(shù)據(jù)一致性是通過 MySQL DTS 訂閱服務實現(xiàn)的，將 binlog 轉換為 invalidate cache 請求，以清理掉本區(qū) REDtao cache 層的 stale 數(shù)據(jù)。由于讀請求會隨機讀取本區(qū)的任何一個 MySQL 數(shù)據(jù)庫，因此 DTS 訂閱使用了一個延遲訂閱的功能，保證從 binlog 同步最慢的節(jié)點中讀取日志，避免 DTS 的 invalidate cache 請求和本區(qū) read cache miss 的請求發(fā)生沖突從而導致數(shù)據(jù)不一致。

REDtao 的云原生特性重點體現(xiàn)在彈性伸縮、支持多 AZ 和 Region 數(shù)據(jù)分布、產(chǎn)品可以實現(xiàn)在不同的云廠商間遷移等幾個方面。REDtao 在設計之初就考慮到支持彈性擴縮容、故障自動檢測及恢復。

隨著 Kubernetes 云原生技術越來越成熟，我們也在思考如何利用 k8s 的能力將部署和虛擬機解綁，進一步云原生化，方便在不同的云廠商之間部署和遷移。

REDtao 實現(xiàn)了一個運行在 Kubernetes 集群上的 Operator，以實現(xiàn)更快的部署、擴容和壞機替換。

為了讓 k8s 能感知集群分片的分配并且控制同一分片下的 Pods 調(diào)度在不同宿主機上，集群分組分片分配由 k8s Operator 渲染并控制創(chuàng)建 DuplicateSet （小紅書自研 k8s 資源對象）。

REDtao 則會創(chuàng)建主從并根據(jù) Operator 渲染出來的分片信息創(chuàng)建集群，單個 Pod 故障重啟會重新加入集群，無需重新創(chuàng)建整個集群。集群升級時，Operator 通過感知主從分配控制先從后主的順序，按照分片分配的順序滾動升級以減少升級期間線上影響。

但凡變革，皆屬不易。實現(xiàn)全新的 REDtao 只是完成了相對容易的那部分工作。

小紅書的社交圖譜數(shù)據(jù)服務已經(jīng)在 MySQL 上運行多年，有很多不同的業(yè)務跑在上面，任何小的問題都會影響到小紅書的在線用戶。因此，如何保證不停服的情況下讓現(xiàn)有業(yè)務無感知地遷移到 REDtao 上成為一個非常大的挑戰(zhàn)。

我們的遷移工作關鍵有兩點：

1）將老的大 MySQL 集群按優(yōu)先級拆分成了四個 REDtao 集群。這樣，我們可以先將優(yōu)先級最低的服務遷移到一個 REDtao 集群，充分灰度后再遷移高優(yōu)先級的集群；

2）專門開發(fā)了一個 Tao Proxy SDK，支持對原來的 MySQL 集群和 REDtao 集群進行雙寫雙讀，數(shù)據(jù)校驗比對。

遷移時：我們首先將低優(yōu)先級的數(shù)據(jù)從 MySQL 通過 DTS 服務遷移到了一個 REDtao 集群，并升級好業(yè)務方的 SDK 。DTS 服務一直對增量數(shù)據(jù)進行同步。業(yè)務方 SDK 會訂閱配置中心的配置變更，我們修改配置讓 Tao Proxy SDK 同時讀寫 MySQL 集群和 REDtao 集群，并關閉 DTS 服務。此時會使用 MySQL 集群的結果返回給用戶。

在停止 DTS 服務時：有可能會有新的 MySQL 數(shù)據(jù)通過 DTS 同步過來，造成了 REDtao 集群新寫的數(shù)據(jù)被同步過來的老數(shù)據(jù)覆蓋。因此，在關閉 DTS 服務后，我們會通過工具讀取開雙寫之后到關閉 DTS 服務這個時間段的 binlog 對數(shù)據(jù)進行校驗和修復。

修復完成之后：Tao Proxy SDK 的雙讀會展示兩邊不一致的數(shù)據(jù)量，并過濾掉因為雙寫時延不一致導致數(shù)據(jù)不一致的請求?；叶纫欢螘r間后觀察到 diff 的數(shù)目基本為 0，將 Tao Proxy SDK 的配置改為只讀寫新的 REDtao 集群。

最終：我們在 22 年初完成小紅書所有核心社交圖譜萬億邊級別數(shù)據(jù)的遷移和正確性校驗，并做到了整個遷移服務無感知，遷移過程沒有發(fā)生一起故障。

我們的社交圖譜數(shù)據(jù)訪問中，90% 以上的請求都是讀請求，并且社交圖譜的數(shù)據(jù)有非常強的時間局部性（即最近更新的數(shù)據(jù)最容易被訪問）。REDtao 上線后，獲得 90% 以上的 cache 命中率， 對MySQL 的 QPS 降低了 70%+ ，大大降低了 MySQL 的 CPU 使用率。在縮容 MySQL 的副本數(shù)目后，整體成本降低了21.3%。?

業(yè)務的訪問方式都全部收斂到 REDtao 提供的 API 接口上，在遷移過程中，我們還治理了一些老的不合理訪問 MySQL 數(shù)據(jù)庫的方式，以及自定義某些字段賦予特殊含義的不合理做法，通過 REDtao 規(guī)范了數(shù)據(jù)訪問。

對比 2022 年初和 2023 年初，隨著 DAU 的增長，社交圖譜的請求增長了 250% 以上，如果是之前 MySQL 的老架構，擴容資源基本上和請求增長速度成正比，至少需要擴容 1 倍的資源成本（數(shù)萬核）。

而得益于 REDtao 系統(tǒng)的存在，因其 90% 的緩存命中率，實際上整體成本只增加了 14.7%（數(shù)千核）就能扛下 2.5 倍的請求增長。在成本和穩(wěn)定性上有了較大的提升。

在較短的時間，我們自研了圖存儲系統(tǒng) REDtao ，解決了社交圖譜關系數(shù)據(jù)快速增長的問題。

REDtao 借鑒了 FaceBook Tao 的論文，并對整體架構、跨云多活做了較多的改進，全新實現(xiàn)了一個高性能的分布式圖緩存，更加貼合我們自身的業(yè)務特點和提供了更好的彈性。同時，利用 k8s 能力進一步實現(xiàn)了云原生化。

隨著 DAU 的持續(xù)增長，萬億的數(shù)據(jù)規(guī)模也在繼續(xù)增長，我們也面臨著更多的技術挑戰(zhàn)。

目前公司內(nèi)部的 OLTP 圖場景主要分為三塊：

1）社交圖譜數(shù)據(jù)服務：通過自研圖存儲系統(tǒng) REDtao 滿足了社交場景超大規(guī)模數(shù)據(jù)的更新與關聯(lián)讀取問題。目前已經(jīng)存儲了萬億規(guī)模的關系；

2）風控場景：通過自研圖數(shù)據(jù)庫 REDgraph，滿足多跳的實時在線查詢。目前存儲了千億點和邊的關系，滿足 2 跳以及 2 跳以上的查詢；

3）社交推薦：這塊主要是兩跳的查詢。每天通過 Hive 批量地導入全量的數(shù)據(jù)，通過 DTS 服務近實時的寫入更新數(shù)據(jù)。因為是在線場景，對時延的要求非常高，當前的 REDgraph 還無法滿足這么高的要求，因此業(yè)務方主要是用 REDkv 來存儲。

針對以上場景：為了快速滿足業(yè)務需求，我們使用了三套不同的自研存儲系統(tǒng)：REDtao 、REDgraph 和 REDkv 。

顯然相對于 3 套存儲系統(tǒng)，用一個統(tǒng)一的架構和系統(tǒng)去解決這幾個圖相關的場景是更加合適的。

未來：我們會將 REDgraph 和 REDtao 融合成一個統(tǒng)一的數(shù)據(jù)庫產(chǎn)品，打造業(yè)內(nèi)頂尖的圖技術，對公司內(nèi)部更多的場景進行賦能。

[1]?

[2]?

[3]?

[4]?

[5]?

[6]?

[7]?

[8]?

[9]?

[10]?

技術交流：

- 移動端IM開發(fā)入門文章：《》

- 開源IM框架源碼：（）

（本文已同步發(fā)布于：）