本文由小紅書基礎架構存儲組空洞和劉備分享，原題“小紅書如何應對萬億級社交網絡關系挑戰？圖存儲系統 REDtao 來了！”，本文有修訂和改動。
1、引言
小紅書是一個社區屬性為主的產品，它涵蓋了各個領域的生活社區，并存儲海量的社交網絡關系。
為了解決社交場景下超大規模數據的更新與關聯讀取問題，并減少數據庫壓力和成本，我們自研了面向超大規模社交網絡的圖存儲系統 REDtao，大大提高了系統穩定性。該系統借鑒了 Facebook 的圖存儲系統設計，將緩存和底層數據庫封裝起來，并對外提供統一的圖查詢 API，實現了訪問收斂，同時在緩存中實現了高效的邊聚合。
本文將為你分享小紅書面向超大規模社交網絡的圖存儲系統REDtao的架構設計與技術實踐過程，希望能帶給你啟發。
2、關于作者
空洞：小紅書基礎架構存儲組，負責圖存儲系統 REDtao 和分布式緩存的研發。
劉備：小紅書基礎架構存儲組負責人，負責REDkv / REDtao / REDtable / REDgraph 的整體架構和技術演進。
基礎架構存儲組是給小紅書的業務部門提供穩定可靠的存儲和數據庫服務，滿足業務對存儲產品的功能、性能、成本和穩定性要求。目前負責自研分布式 KV、分布式緩存、圖存儲系統、圖數據庫和表格存儲。
已上線的存儲產品包括：
- 1）REDkv : 分布式高性能 KV；
- 2）REDtao ：滿足一跳查詢的高性能圖存儲數據庫；
- 3） REDtable ：提供 Schema 語義和二級索引的表格存儲；
- 4） REDgraph ：提供兩跳及以上的圖語義查詢數據庫。
3、技術背景
小紅書是以年輕人為主的生活記錄、分享平臺，用戶可以通過短視頻、圖文等形式記錄生活點滴，分享生活方式。
在小紅書的社交領域里，我們有用戶、筆記、商品等實體，這些實體之間有各種各樣的關系。
例如：用戶與筆記之間可能存在“擁有”（發布）、“點贊”、“收藏”等三種關系，同時還存在對應的反向關系“被點贊”，“被收藏”等。
小紅書的社交圖譜數據已經達到了萬億條邊的規模，且增長速度非?？?。當用戶登陸小紅書時，每個用戶都會看到關注的好友、粉絲、點贊、收藏以及其他為其量身定做的內容。
這些信息高度個性化，需要實時從這些海量社交關系數據中讀取用戶相關信息。這是一個讀為主的過程，讀取壓力非常大。
過去，我們將這些社交圖譜數據都存儲在運維成熟的 MySQL 數據庫中。
然而，即使我們只有百萬請求每秒的規模，MySQL 的 CPU 使用率仍然到達了 55% 。隨著用戶和 DAU 爆發式的增長，需要不斷擴容 MySQL 數據庫，這帶來了巨大的成本和穩定性壓力。
為了解決這些問題且考慮到沒有合適的開源方案，2021 年初我們開啟了從 0 到 1 自研 REDtao 的歷程。
4、方案調研和API設計
4.1方案調研
我們充分調研了業內其他廠商的實現，發現有著強社交屬性的公司基本上都有一個自研的圖存儲系統（如下圖所示）。
比如：
- 1）Facebook 實現了一個叫做 “TAO” 專門的分布式社交圖譜數據庫，并將其作為最核心的存儲系統；
- 2）Pinterest 和 Facebook 類似，也實現了類似的圖存儲系統；
- 3）字節跳動自研了 ByteGraph 并將其用于存儲核心的社交圖譜數據；
- 4）Linkedln 在 KV 之上構建了社交圖譜服務。
考慮到當時我們的社交圖譜數據已經存放在 MySQL 數據庫上且規模巨大，而社交圖譜數據服務是非常重要的服務，對穩定性的要求非常高?；厮?Facebook 當年遇到的問題和我們類似，數據存儲在 Memcache 和 MySQL 中。因此，參考 Facebook 的 Tao 圖存儲系統更貼合我們的實際情況和已有的技術架構，風險更小。
4.2API設計
社交圖譜的訪問主要是邊的關系查詢。
我們的圖模型將關系表示為一個 <key, value> 對，其中 key 是 ( FromId, AssocType, ToId ) 的三元組，value 是屬性的 JSON 格式。
比如“用戶 A ”關注“用戶 B ”，映射到 REDtao 的數據存儲結構為：
1<FromId:用戶A的ID, AssocType：關注， ToId：用戶B的ID> -> Value （屬性的json字段）
我們對業務方的需求進行分析，封裝了 25 個圖語義的 API 給業務方使用，滿足了其增刪改查的需求，并收斂業務方的使用方式。
相比于 Facebook 的 Tao，我們還補充了社交圖譜所需要的圖語義，為反作弊場景提供了額外的過濾參數。
同時，在緩存層面，我們支持對不同的字段在緩存中配置局部二級索引。
下面給一些典型的使用場景。
1）場景一：獲取關注了 A 的所有正常用戶（并且剔除作弊用戶）：
1getAssocs(“被關注類型”, 用戶A的ID, 分頁偏移量, 最大返回值, 只返回正常用戶，是否按照時間從新到舊)
2）場景二：獲取 A 的粉絲個數（并且剔除作弊用戶）：
1getAssocCount(“被關注類型”, 用戶A的ID, 只返回正常用戶)
5、整體架構設計
REDtao 的架構設計考慮了下面這幾個關鍵的要素：
整體架構分為三層：
業務方通過 REDtao SDK 接入服務。
如下圖：
在這個架構中：和 Facebook Tao 不一樣的是，我們的緩存層是一個獨立的分布式集群，和下面的持久層是解耦的。緩存層和下面的持久層可以獨立的擴容縮容，緩存分片和 MySQL 分片不需要一一對應，這樣帶來了更好的靈活性，MySQL 集群也變成了一個可以插拔替換的持久存儲。
1）讀流程：客戶端將讀請求發送給 router，router 接收到 RPC 請求后，根據邊類型選擇對應的 REDtao 集群，根據三元組 ( FromId, AssocType, ToId ) 通過一致性 Hash 計算出分片所在的 Follower 節點，將請求轉發到該節點上。Follower 節點接收到該請求，首先查詢本地的圖緩存，如果命中則直接返回結果。如果沒有命中，則將請求轉發給 Leader 節點。同樣的，Leader 節點如果命中則返回，如果不命中則查詢底層 MySQL 數據庫。
2）寫流程：客戶端將寫請求發送給 router，和讀流程一樣，會轉發到對應的 Follower 節點上。Follower 節點會轉發寫請求給 Leader 節點，Leader 節點轉發給 MySQL，當 MySQL 返回寫入成功后，Leader 會清除本地圖緩存對應的 Key，并同步給其他所有 Follower 清除掉該 Key，保證數據的最終一致性。
6、高可用設計
REDtao 分為獨立的兩層：緩存層和持久層。每一層都保證高可用性。
1）自研的分布式緩存：
我們自研了實現圖語義的分布式 cache 集群，支持故障自動檢測和恢復、水平擴縮容。
它是一個雙層 cache，每個分片都有一個 Leader 和若干個 Follower。所有的請求都先發給外層的 Follower，再由 Follower 轉發給 Leader。這樣的好處是讀壓力大的時候只需要水平擴展 Follower，單點 Leader 寫入的方式也降低了復雜度，更容易實現數據的一致性。
如果一個副本故障，系統會在秒級別內進行切換。當持久層發生故障時，分布式緩存層仍然可以對外提供讀取服務。
2）高可用的MySQL集群：
MySQL 集群通過自研的中間件實現了分庫分表方案，并支持 MySQL 的水平擴容。每個 MySQL 數據庫有若干從庫，并且與公司內部其他的 MySQL 運維方案一致，保證高可用性。
3）限流保護功能：
為防止緩存擊穿導致 MySQL 突發大量請求，從而導致 MySQL 宕機，我們通過限制每個主節點最大 MySQL 并發請求數來實現限流保護 MySQL。達到最大并發請求限制之后的請求會被掛起等待，直到已有請求被處理返回，或者達到等待超時請求被拒絕不會被繼續請求到 MySQL 。限流閾值在線可調，根據 MySQL 集群規模調整對應限制。
為防止爬蟲或者作弊用戶頻繁刷同一條數據，我們利用 REDtaoQueue 順序執行對寫入或者點查同一條邊的請求，隊列長度會被限制，控制同一時間大量相同的請求執行。相比于單個全局的隊列控制所有請求的方式，基于每個請求的隊列可以很好地限制單個同一請求，而不影響其他正常請求。
7、高性能設計
數據結構的設計是 REDtao 高性能的重要保證。
我們采用了三層嵌套 HashTable 的設計, 通過根據某個起點 from_id 從第一級 HashTable 中查找到 REDtaoGraph，記錄了所有 type 下對應的所有的出邊信息。
接著，在第二級 HashTable 中，根據某個 type_id 查找到 AssocType 對應某個 type 下邊所有出邊的計數、索引以及其他元數據。
最終在最后一級 HashTable ，通過 AssocType 的某個 to_id 查找到最終邊信息。
我們記錄了創建時間、更新時間、版本、數據以及 REDtaoQueue，time_index 則對應根據創建時間排序列表。
最后一級 HashTable 以及索引限制存儲最新的 1000 個邊信息，以限制超級點占據過多內存，同時集中提高最新熱數據的查詢命中率以及效率。REDtaoQueue 用于排隊當前某個關系的讀寫，只記錄了當前最后一個請求的元數據。
每次查詢或寫入時，首先查詢 REDtaoAssoc：
- 1）若緩存不存在，則會首先創建只包含 REDtaoQueue 的對象；
- 2）若緩存已存在，則會更新隊列元數據，將自己設置為隊列的最后一個請求，并掛起等待被執行。
通過這種多層 hash+ 跳表的設計，我們能高效地組織點、邊、索引、時間序鏈表之間的關系。內存的申請、釋放在同一個線程上完成。
在線上環境中，我們的系統可以在一臺 16 核的云廠商虛擬機上跑到 150w 查詢請求/s，同時 CPU 利用率僅有 22.5% 。下方是線上集群的一個監控圖，單機的 QPS 到達 3w ，每個 RPC 請求聚合了 50 個查詢。
8、易用性設計
1）豐富的圖語義 API ：
我們在 REDtao 中封裝了 25 個圖語義的 API 給業務方使用，滿足了業務方的增刪改查的需求。業務方無需自行編寫 SQL 語句即可實現相應操作，使用方式更加簡單和收斂。
2）統一的訪問 URL ：
由于社區后端數據太大，我們按照不同的服務和優先級拆分成了幾個 REDtao 集群。
為了讓業務方不感知后端的集群拆分邏輯，我們實現了統一的接入層。
不同的業務方只需使用同一個服務 URL ，通過 SDK 將請求發送到接入層。接入層會接收到不同業務方的圖語義的請求，并根據邊的類型路由到不同的 REDtao 集群。它通過訂閱配置中心，能夠實時感知到邊的路由關系，從而實現統一的訪問 URL，方便業務方使用。
9、數據一致性設計
作為社交圖譜數據，數據的一致性至關重要。我們需要嚴格保證數據的最終一致性以及一定場景下的強一致性。為此，我們采取了以下措施：
1）緩存更新沖突的解決：
REDtao 為每個寫入請求生成一個全局遞增的唯一版本號。在使用 MySQL 數據更新本地緩存時，需要比較版本號，如果版本號比緩存的數據版本低，則會拒絕此更新請求，以避免沖突。
2）寫后讀的一致性：
Proxy 會將同一個 fromId 的點或邊請求路由到同一個讀 cache 節點上，以保證讀取數據一致性。
3）主節點異常場景：
Leader 節點收到更新請求后，會將更新請求變為 invalidate cache 請求異步的發送給其他 follower，以保證 follower 上的數據最終一致。在異常情況下，如果 Leader 發送的隊列已滿導致 invalidate cache 請求丟失，那么會將其他的 follower cache 全部清除掉。
如果 Leader 故障，新選舉的 Leader 也會通知其他 follower 將 cache 清除。
此外，Leader 會對訪問 MySQL 的請求進行限流，從而保證即使個別分片的cache被清除掉也不會將 MySQL 打崩。
4）少量強一致的請求：
由于 MySQL 的從庫也提供讀服務，對于少量要求強一致的讀請求，客戶端可以將請求染上特殊標志，REDtao 會透傳該標志，數據庫 Proxy 層會根據該標志將讀請求轉發到 MySQL 主庫上，從而保證數據的強一致。
10、 跨云多活設計
跨云多活是公司的重要戰略，也是 REDtao 支持的一個重要特性。
REDtao 的跨云多活架構整體如下：
這里不同于 Facebook Tao 的跨云多活實現，Facebook Tao 的跨云多活實現如下圖所示。
Facebook 的方案依賴于底層的 MySQL 的主從復制都通過 DTS Replication 來做。而 MySQL 原生的主從復制是自身功能，DTS 服務并不包含 MySQL 的主從復制。該方案需要對 MySQL 和 DTS 做一定的改造。前面說到，我們的緩存和持久層是解藕的，在架構上不一樣。
因此，REDtao 的跨云多活架構是我們結合自身場景下的設計，它在不改動現有 MySQL 功能的前提下實現了跨云多活功能。
1）持久層我們通過 MySQL 原生的主從 binlog 同步將數據復制到其他云的從庫上。其他云上的寫請求和少量要求強一致讀將被轉發到主庫上。正常的讀請求將讀取本區的 MySQL 數據庫，滿足讀請求對時延的要求。
2）緩存層的數據一致性是通過 MySQL DTS 訂閱服務實現的，將 binlog 轉換為 invalidate cache 請求，以清理掉本區 REDtao cache 層的 stale 數據。由于讀請求會隨機讀取本區的任何一個 MySQL 數據庫，因此 DTS 訂閱使用了一個延遲訂閱的功能，保證從 binlog 同步最慢的節點中讀取日志，避免 DTS 的 invalidate cache 請求和本區 read cache miss 的請求發生沖突從而導致數據不一致。
11、云原生實現
REDtao 的云原生特性重點體現在彈性伸縮、支持多 AZ 和 Region 數據分布、產品可以實現在不同的云廠商間遷移等幾個方面。REDtao 在設計之初就考慮到支持彈性擴縮容、故障自動檢測及恢復。
隨著 Kubernetes 云原生技術越來越成熟，我們也在思考如何利用 k8s 的能力將部署和虛擬機解綁，進一步云原生化，方便在不同的云廠商之間部署和遷移。
REDtao 實現了一個運行在 Kubernetes 集群上的 Operator，以實現更快的部署、擴容和壞機替換。
為了讓 k8s 能感知集群分片的分配并且控制同一分片下的 Pods 調度在不同宿主機上，集群分組分片分配由 k8s Operator 渲染并控制創建 DuplicateSet （小紅書自研 k8s 資源對象）。
REDtao 則會創建主從并根據 Operator 渲染出來的分片信息創建集群，單個 Pod 故障重啟會重新加入集群，無需重新創建整個集群。集群升級時，Operator 通過感知主從分配控制先從后主的順序，按照分片分配的順序滾動升級以減少升級期間線上影響。
12、老服務的平滑升級實踐
但凡變革，皆屬不易。實現全新的 REDtao 只是完成了相對容易的那部分工作。
小紅書的社交圖譜數據服務已經在 MySQL 上運行多年，有很多不同的業務跑在上面，任何小的問題都會影響到小紅書的在線用戶。因此，如何保證不停服的情況下讓現有業務無感知地遷移到 REDtao 上成為一個非常大的挑戰。
我們的遷移工作關鍵有兩點：
1）將老的大 MySQL 集群按優先級拆分成了四個 REDtao 集群。這樣，我們可以先將優先級最低的服務遷移到一個 REDtao 集群，充分灰度后再遷移高優先級的集群；
2）專門開發了一個 Tao Proxy SDK，支持對原來的 MySQL 集群和 REDtao 集群進行雙寫雙讀，數據校驗比對。
遷移時：我們首先將低優先級的數據從 MySQL 通過 DTS 服務遷移到了一個 REDtao 集群，并升級好業務方的 SDK 。DTS 服務一直對增量數據進行同步。業務方 SDK 會訂閱配置中心的配置變更，我們修改配置讓 Tao Proxy SDK 同時讀寫 MySQL 集群和 REDtao 集群，并關閉 DTS 服務。此時會使用 MySQL 集群的結果返回給用戶。
在停止 DTS 服務時：有可能會有新的 MySQL 數據通過 DTS 同步過來，造成了 REDtao 集群新寫的數據被同步過來的老數據覆蓋。因此，在關閉 DTS 服務后，我們會通過工具讀取開雙寫之后到關閉 DTS 服務這個時間段的 binlog 對數據進行校驗和修復。
修復完成之后：Tao Proxy SDK 的雙讀會展示兩邊不一致的數據量，并過濾掉因為雙寫時延不一致導致數據不一致的請求?；叶纫欢螘r間后觀察到 diff 的數目基本為 0，將 Tao Proxy SDK 的配置改為只讀寫新的 REDtao 集群。
最終：我們在 22 年初完成小紅書所有核心社交圖譜萬億邊級別數據的遷移和正確性校驗，并做到了整個遷移服務無感知，遷移過程沒有發生一起故障。
13、新圖存儲系統帶來的結果和收益
我們的社交圖譜數據訪問中，90% 以上的請求都是讀請求，并且社交圖譜的數據有非常強的時間局部性（即最近更新的數據最容易被訪問）。REDtao 上線后，獲得 90% 以上的 cache 命中率， 對MySQL 的 QPS 降低了 70%+ ，大大降低了 MySQL 的 CPU 使用率。在縮容 MySQL 的副本數目后，整體成本降低了21.3%。
業務的訪問方式都全部收斂到 REDtao 提供的 API 接口上，在遷移過程中，我們還治理了一些老的不合理訪問 MySQL 數據庫的方式，以及自定義某些字段賦予特殊含義的不合理做法，通過 REDtao 規范了數據訪問。
對比 2022 年初和 2023 年初，隨著 DAU 的增長，社交圖譜的請求增長了 250% 以上，如果是之前 MySQL 的老架構，擴容資源基本上和請求增長速度成正比，至少需要擴容 1 倍的資源成本（數萬核）。
而得益于 REDtao 系統的存在，因其 90% 的緩存命中率，實際上整體成本只增加了 14.7%（數千核）就能扛下 2.5 倍的請求增長。在成本和穩定性上有了較大的提升。
14、未來展望
在較短的時間，我們自研了圖存儲系統 REDtao ，解決了社交圖譜關系數據快速增長的問題。
REDtao 借鑒了 FaceBook Tao 的論文，并對整體架構、跨云多活做了較多的改進，全新實現了一個高性能的分布式圖緩存，更加貼合我們自身的業務特點和提供了更好的彈性。同時，利用 k8s 能力進一步實現了云原生化。
隨著 DAU 的持續增長，萬億的數據規模也在繼續增長，我們也面臨著更多的技術挑戰。
目前公司內部的 OLTP 圖場景主要分為三塊：
1）社交圖譜數據服務：通過自研圖存儲系統 REDtao 滿足了社交場景超大規模數據的更新與關聯讀取問題。目前已經存儲了萬億規模的關系；
2）風控場景：通過自研圖數據庫 REDgraph，滿足多跳的實時在線查詢。目前存儲了千億點和邊的關系，滿足 2 跳以及 2 跳以上的查詢；
3）社交推薦：這塊主要是兩跳的查詢。每天通過 Hive 批量地導入全量的數據，通過 DTS 服務近實時的寫入更新數據。因為是在線場景，對時延的要求非常高，當前的 REDgraph 還無法滿足這么高的要求，因此業務方主要是用 REDkv 來存儲。
針對以上場景：為了快速滿足業務需求，我們使用了三套不同的自研存儲系統：REDtao 、REDgraph 和 REDkv 。
顯然相對于 3 套存儲系統，用一個統一的架構和系統去解決這幾個圖相關的場景是更加合適的。
未來：我們會將 REDgraph 和 REDtao 融合成一個統一的數據庫產品，打造業內頂尖的圖技術，對公司內部更多的場景進行賦能。
15、相關資料
[1] 以微博類應用場景為例，總結海量社交系統的架構設計步驟
[2] 騰訊技術分享：社交網絡圖片的帶寬壓縮技術演進之路
[3] 基于社交網絡的Yelp是如何實現海量用戶圖片的無損壓縮的？
[4] 社交軟件紅包技術解密(一)：全面解密QQ紅包技術方案——架構、技術實現等
[5] 社交軟件紅包技術解密(六)：微信紅包系統的存儲層架構演進實踐
[6] 社交軟件紅包技術解密(九)：談談手Q紅包的功能邏輯、容災、運維、架構等
[7] 漸行漸遠的人人網：十年親歷者的互聯網社交產品復盤和反思
[8] 中國互聯網社交二十年：全民見證的互聯網創業演義
[9] 盤點移動互聯網時代的社交產品進化史（上篇）：誰主沉浮
[10] 盤點移動互聯網時代的社交產品進化史（下篇）：大浪淘沙
（本文已同步發布于：http://www.52im.net/thread-4495-1-1.html）