從小白到架構師(4): Feed 流系統實戰
- 2022 年 11 月 4 日
- 筆記
「從小白到架構師」系列努力以淺顯易懂、圖文並茂的方式向各位讀者朋友介紹 WEB 服務端從單體架構到今天的大型分散式系統、微服務架構的演進歷程。讀了三篇萬字長文之後各位想必已經累了（主要是我寫累了😏）， 今天我們回來看看小明和他的「淘金網」的故事。
「淘金網」里有一個頁面叫「關注頁」，關注頁的邏輯十分常見就是將用戶關注的創作者發表的文章聚合在一起，按時間倒序排列即可。
這種產品形態在業內一般被叫做 Feed 流，Feed 流產品在我們手機APP中幾乎無處不在，比如微信朋友圈、新浪微博、今日頭條等。只要大拇指不停地往下劃手機螢幕，就有一條條的資訊不斷湧現出來。就像給寵物餵食一樣，只要它吃光了就要不斷再往裡加，故此得名Feed（飼養）。
Feed 流產品一般有兩種形態，一種是基於演算法推薦，另一種是基於關注關係並按時間排列。「關注頁」這種按時間排序的 Feed 流也被為 Timeline。「關注頁」自然的也被稱為「關注 Timeline」, 存放自己發送過的 Feed 的頁面被稱為「個人 Timeline」 比如微博的個人頁。
就是這麼個 Feed 流系統讓「淘金網」的工程師分成兩派吵作一團，一直吵到了小明辦公室。。。
推與拉之爭
拉模型
一部分工程師認為應該在查詢時首先查詢用戶關注的所有創作者 uid，然後查詢他們發布的所有文章，最後按照發布時間降序排列。
使用拉模型方案用戶每打開一次「關注頁」系統就需要讀取 N 個人的文章（N 為用戶關注的作者數）, 因此拉模型也被稱為讀擴散。
拉模型不需要存儲額外的數據，而且實現比較簡單：發布文章時只需要寫入一條 articles 記錄，用戶關注(或取消關注)也只需要增刪一條 followings 記錄。特別是當粉絲數特別多的頭部作者發布內容時不需要進行特殊處理，等到讀者進入關注頁時再計算就行了。
拉模型的問題同樣也非常明顯，每次閱讀「關注頁」都需要進行大量讀取和一次重新排序操作，若用戶關注的人數比較多一次拉取的耗時會長到難以接受的地步。
推模型
另一部分工程師認為在創作者發布文章時就應該將新文章寫入到粉絲的關注 Timeline，用戶每次閱讀只需要到自己的關注 Timeline 拉取就可以了：
使用推模型方案創作者每次發布新文章系統就需要寫入 M 條數據（M 為創作者的粉絲數），因此推模型也被稱為寫擴散。推模型的好處在於拉取操作簡單高效，但是缺點一樣非常突出。
首先，在每篇文章要寫入 M 條數據，在如此恐怖的放大倍率下關注 Timeline 的總體數據量將達到一個驚人數字。而粉絲數有幾十萬甚至上百萬的頭部創作者每次發布文章時巨大的寫入量都會導致伺服器地震。
通常為了發布者的體驗文章成功寫入就向前端返回成功，然後通過消息隊列非同步地向粉絲的關注 Timeline 推送文章。
其次，推模型的邏輯要複雜很多，不僅發布新文章時需要實現相關邏輯，新增關注或者取消關注時也要各自實現相應的邏輯，聽上去就要加很多班。。
在線推，離線拉
在做出最終決定之前我們先來對比一下推拉模型：
| 優點 | 缺點 | |
|---|---|---|
| 推 | 讀取操作快 | 邏輯複雜 消耗大量存儲空間 粉絲數多的時候會是災難 |
| 拉 | 邏輯簡單 節約存儲空間 |
讀取效率低下，關注人數多的時候會出現災難 |
雖然乍看上去拉模型優點多多，但是 Feed 流是一個極度讀寫不平衡的場景，讀請求數比寫請求數高兩個數量級也不罕見，這使得拉模型消耗的 CPU 等資源反而更高。
此外推送可以慢慢進行，但是用戶很難容忍打開頁面時需要等待很長時間才能看到內容（很長：指等一秒鐘就覺得卡）。 因此拉模型讀取效率低下的缺點使得它的應用受到了極大限制。
我們回過頭來看困擾推模型的這個問題「粉絲數多的時候會是災難」，我們真的需要將文章推送給作者的每一位粉絲嗎？
仔細想想這也沒有必要，我們知道粉絲群體中活躍用戶是有限的，我們完全可以只推送給活躍粉絲，不給那些已經幾個月沒有啟動 App 的用戶推送新文章。
至於不活躍的用戶，在他們回歸後使用拉模型重新構建一下關注 Timeline 就好了。因為不活躍用戶回歸是一個頻率很低的事件，我們有充足的計算資源使用拉模型
進行計算。
因為活躍用戶和不活躍用戶常常被叫做「在線用戶」和「離線用戶」，所以這種通過推拉結合處理頭部作者發布內容的方式也被稱為「在線推，離線拉」。
再優化一下存儲
在前面的討論中不管是「關注 Timeline」還是關注關係等數據我們都存儲在了 MySQL 中。拉模型可以用 SQL 描述為：
SELECT *
FROM articles
WHERE author_uid IN (
SELECT following_uid
FROM followings
WHERE uid = ?
)
ORDER BY create_time DESC
LIMIT 20;
通過查看執行計劃我們發現，臨時表去重+Filesort、這個查詢疊了不少 debuff：
至於推模型，關注 Timeline 巨大的數據量和讀寫負載就不是 MySQL 能扛得住的。。。
遇事不決上 Redis
顯然關注 Timeline 的數據是可以通過 articles 和 followings 兩張表中數據重建的，其存在只是為了提高讀取操作的效率。這有沒有讓你想起另外一個東西？
沒錯！就是快取，關注 Timeline 實質上就是一個快取，也就是說關注 Timeline 與快取一樣只需要暫時存儲熱門數據。
我們可以給關注 Timeline 存儲設置過期時間，若用戶一段時間沒有打開 App 他的關注 Timeline 存儲將被過期釋放，在他回歸之後通過拉模型重建即可。
在使用「在線推，離線拉」策略時我們需要判斷用戶是否在線，在為 Timeline 設置了過期時間後，Timeline 快取是否存在本身即可以作為用戶是否在線的標誌。
就像很少有人翻看三天前的朋友圈一樣，用戶總是關心關注頁中最新的內容，所以關注 Timeline 中也沒有必要存儲完整的數據只需要存儲最近一段時間即可，舊數據等用戶翻閱時再構建就行了。
魯迅有句話說得好 ——「遇事不決上 Redis」，既然是快取那麼就是 Redis 的用武之地了。
Redis 中有序數據結構有列表 List 和有序集合 SortedSet 兩種，對於關注 Timeline 這種需要按時間排列且禁止重複的場景當然閉著眼睛選 SortedSet。
將 article_id 作為有序集合的 member、發布時間戳作為 score, 關注 Timeline 以及個人 Timeline 都可以快取起來。
在推送新 Feed 的時候只需要對目標 Timeline 的 SortedSet 進行 ZAdd 操作。若快取中沒有某個 Timeline 的數據就使用拉模型進行重建。
在使用消息隊列進行推送時經常出現由於網路延遲等原因導致重複推送的情況，所幸 article_id 是唯一的，即使出現了重複推送 Timeline 中也不會出現重複內容。
這種重複操作不影響結果的特性有個高大上的名字 ——— 冪等性
當 Redis 中沒有某個 Timeline 的快取時我們無法判斷是快取失效了，還是這個用戶的 Timeline 本來就是空的。我們只能通過讀取 MySQL 中的數據才能進行判斷，這就是經典的快取穿透問題。
對於時間線這種集合式的還存在第二類快取穿透問題，正如我們剛剛提到的 Redis 中通常只存儲最近一段時間的 Timeline，當我們讀完了 Redis 中的數據之後無法判斷資料庫中是否還有更舊的數據。
這兩類問題的解決方案是一樣的，我們可以在 SortedSet 中放一個 NoMore 的標誌，表示資料庫中沒有更多數據了。對於 Timeline 本來為空的用戶來說，他們的 SortedSet 中只有一個 NoMore 標誌：
最後一點：拉取操作要注意保持原子性不要將重建了一半的 Timeline 暴露出去：
總結一下使用 Redis 做關注時間線的要點:
- 使用 SortedSet 結構存儲，Member 為 FeedID，Score 為時間戳
- 給快取設置自動過期時間，不活躍用戶的快取會自動被清除。使用「在線推，離線拉」時只給 Timeline 快取未失效的用戶推送即可
- 需要在快取中放置標誌來防止快取擊穿
一層快取不夠再來一層
雖然 Redis 可以方便的實現高性能的關注 Timeline 系統，但是記憶體空間總是十分珍貴的，我們常常沒有足夠的記憶體為活躍用戶快取關注 Timeline。
快取不足是電腦領域的經典問題了，問問你的 CPU 它就會告訴你答案 —— 一級快取不夠用就做二級快取，L1、L2、L3 都用光了我才會用記憶體。
只要是支援有序結構的 NewSQL 資料庫比如 Cassandra、HBase 都可以勝任 Redis 的二級快取：
附上一條 Cassandra 的表結構描述：
-- Cassandra 是一個 Map<PartionKey, SortedMap<ClusteringKey, OtherColumns>> 結構
-- 必須指定一個 PartionKey，順序也只能按照 ClusteringKey 的順序排列
-- 這裡 PartionKey 是 uid, ClusteringKey 是 publish_time + article_id
-- publish_time 必須寫在 ClusteringKey 第一列才能按照它進行排序
-- article_id 也寫進 ClusteringKey 是為了防止 publish_time 出現重複
CREATE TABLE taojin.following_timelins (
uid bigint，
publish_time timestamp,
article_id bigin,
PRIMARY KEY (uid, publish_time, article_id)
) WITH default_time_to_live = 60 * 24 * 60 * 60;
這裡還是要提醒一下，每多一層快取便要多考慮一層一致性問題，到底要不要做多級快取需要仔細權衡。
還有一些細節要優化
分頁器
Feed 流是一個動態的列表，列表內容會隨著時間不斷變化。傳統的 limit + offset 分頁器會有一些問題：
在 T1 時刻讀取了第一頁，T2時刻有人新發表了 article 11 ，如果這時來拉取第二頁，會導致 article 6 在第一頁和第二頁都被返回了。
解決這個問題的方法是根據上一頁最後一條 Feed 的 ID 來拉取下一頁：
使用 Feed ID 來分頁需要先根據 ID 查找 Feed，然後再根據 Feed 的發布時間讀取下一頁，流程比較麻煩。若作為分頁游標的 Feed 被刪除了，就更麻煩了。
筆者更傾向於使用時間戳來作為游標：
使用時間戳不可避免的會出現兩條 Feed 時間戳相同的問題, 這會讓我們的分頁器不知所措。
這裡有個小技巧是將 Feed id 作為 score 的小數部分，比如 article 11 在 2022-10-27 13:55:11 發布（時間戳 1666850112）， 那麼它的 score 為 1666850112.11 小數部分既不影響按時間排序又避免了重複。
大規模推送
雖然我們已經將推送 Feed 的任務轉移給了 MQ Worker 來處理，但面對將 Feed 推送給上百萬粉絲這樣龐大的任務, 單機的 Worker 還是很難處理。 而且一旦處理中途崩潰就需要全部重新開始。
我們可以將大型推送任務拆分成多個子任務，通過消息隊列發送到多台 MQ Worker 上進行處理。
因為負責拆分任務的 Dispatcher 只需要掃描粉絲列表負擔和故障概率大大減輕。若某個推送子任務失敗 MQ 會自動進行重試，也無需我們擔心。
總結
至此，我們完成了一個關注 Feed 流系統的設計。總結一下本文我們都討論了哪些內容：
- 基本模型有兩種。推模型：發布新 Feed 時推送到每個粉絲的 Timeline; 拉模型：打開 Timeline 時拉取所有關注的人發布的 Feed，重新聚合成粉絲的 Timeline。推模型讀取快，但是推送慢，粉絲數多的時候峰值負載很重。拉模型沒有峰值問題，但是讀取很慢用戶打開 Timeline 時要等待很久，讀極多寫極少的環境中消耗的計算資源更多。
- 頭部用戶的幾十上百萬粉絲中活躍用戶比例很少，所以我們可以只將他們的新 Feed 推送給活躍用戶，不活躍用戶等回歸時再使用拉模型重建 Timeline.即通過「在線推、離線拉」的模式解決推模型的峰值問題。
- 雖然關注 Timeline 數據很多但實際上是一種快取，沒必要全部存儲。我們按照快取的思路只存儲活躍用戶、最近一段時間的數據即可，沒有快取的數據在用戶閱讀時再通過拉模型重建。
- Timeline 推薦使用 Redis 的 SortedSet 結構存儲，Member 為 FeedID，Score 為時間戳。給快取設置自動過期時間，不活躍用戶的快取會自動被清除。使用「在線推，離線拉」時只給 Timeline 快取未失效的用戶推送即可
- 在 Redis 記憶體不足時可以使用 Cassandra 作為 Redis 的二級快取。
