在本章中，你會被要求設計一個 news feed 系統。什麼是 news feed？根據 Facebook 說明頁面：「News feed 是首頁中間不斷更新的故事清單。News Feed 包含你在 Facebook 上追蹤的人、粉絲頁與社團的狀態更新、相片、影片、連結、應用程式活動與按讚」[1]。
這是常見的面試題目。類似常被問到的問題包括：設計 Facebook news feed、Instagram feed、Twitter timeline 等。
Step 1 - 理解問題並確立設計範圍#
第一組釐清性問題的目的，是了解面試官請你設計 news feed 系統時心中想的是什麼。你至少應該弄清楚要支援哪些功能。以下是應徵者與面試官互動的範例：
應徵者：這是行動 App？網頁 App？還是兩者都有？
面試官：兩者都有。
應徵者：重要的功能有哪些？
面試官：使用者可以發佈貼文，並在 news feed 頁面看到朋友的貼文。
應徵者：news feed 是依時間倒序排序，還是依某種特定順序，例如話題分數？例如，來自親近朋友的貼文有較高分數。
面試官：為了讓事情簡單一些，假設 feed 依時間倒序排序。
應徵者：一個使用者最多能有多少朋友？
面試官：5000
應徵者：流量規模是多少？
面試官：1000 萬 DAU。
應徵者：feed 可包含圖片、影片，還是只有文字？
面試官：可以包含媒體檔，包括圖片與影片。
既然已經收集到需求，我們把焦點放在設計系統上。
Step 2 - 提出高階設計並取得認可#
設計分為兩個流程：feed 發佈與 news feed 建構。
- Feed 發佈：當使用者發佈一則貼文時，對應的資料會寫入快取與資料庫。該貼文會被填到她朋友的 news feed 中。
- News feed 建構：為了簡化問題，我們假設 news feed 是透過將朋友的貼文以時間倒序聚合而建立。
Newsfeed APIs#
news feed API 是客戶端與伺服器通訊的主要方式。這些 API 是基於 HTTP 的，允許客戶端執行各種動作，包括發佈狀態、取得 news feed、加好友等。我們討論兩個最重要的 API：feed 發佈 API 與 news feed 取得 API。
Feed publishing API#
要發佈一則貼文，會發送一個 HTTP POST 請求到伺服器。API 如下：
POST /v1/me/feed
Params：
- content：content 是貼文的文字。
- auth_token：用於驗證 API 請求。
Newsfeed retrieval API#
取得 news feed 的 API 如下：
GET /v1/me/feed
Params：
- auth_token：用於驗證 API 請求。
Feed 發佈#
圖 2 顯示 feed 發佈流程的高階設計。
使用者：使用者可在瀏覽器或行動 App 上檢視 news feed。使用者透過 API 發佈內容為「Hello」的貼文：
/v1/me/feed?content=Hello&auth_token={auth_token}Load balancer：將流量分配到網頁伺服器。
網頁伺服器：將流量轉送到不同的內部服務。
Post service：將貼文持久化到資料庫與快取。
Fanout service：將新內容推播到朋友的 news feed。news feed 資料儲存在快取中以快速取得。
Notification service：通知朋友有新內容可看，並送出推播通知。
Newsfeed 建構#
在本節中，我們討論 news feed 在背後如何建立。圖 3 顯示高階設計：
- 使用者：使用者送出請求以取得她的 news feed。請求看起來像這樣：
/v1/me/feed。 - Load balancer：負載平衡器將流量轉送到網頁伺服器。
- 網頁伺服器：將請求路由到 newsfeed service。
- Newsfeed service：news feed service 從快取中取得 news feed。
- Newsfeed cache：儲存渲染 news feed 所需的 news feed ID。
Step 3 - 設計深入探討#
高階設計簡要涵蓋了兩個流程：feed 發佈與 news feed 建構。在這裡，我們會更深入地討論這些主題。
Feed 發佈深入探討#
圖 4 概述 feed 發佈的詳細設計。我們已經在高階設計中討論大部分元件，這裡會聚焦在兩個元件：網頁伺服器與 fanout service。
網頁伺服器#
除了與客戶端通訊之外，網頁伺服器還執行身份驗證與速率限制。只有以有效 auth_token 登入的使用者才能發佈貼文。
系統會限制使用者在某段期間內可發佈的貼文數量，這對於防止垃圾訊息與濫用內容至關重要。
Fanout service#
Fanout 是把貼文傳送給所有朋友的過程。兩種 fanout 模型為：
- 寫入時 fanout（fanout on write，又稱 push model）
- 讀取時 fanout（fanout on read，又稱 pull model）
兩種模型各有優缺點。我們會說明它們的工作流程，並探索支援我們系統的最佳方式。
Fanout on write。在此方法中，news feed 會在寫入時預先計算。新貼文一旦發佈後會立即送到朋友的快取中。
優點：
- News feed 即時產生並可立即推送給朋友。
- 取得 news feed 很快，因為 news feed 已在寫入時預先計算。
缺點：
- 如果使用者有許多朋友，取得朋友清單並為他們所有人產生 news feed 既慢又耗時。這稱為 hotkey 問題。
- 對於不活躍或很少登入的使用者，預先計算 news feed 是浪費運算資源。
Fanout on read。news feed 在讀取時產生。這是按需（on-demand）模型。當使用者載入她的首頁時，最近的貼文才會被拉取。
優點：
- 對於不活躍或很少登入的使用者，fanout on read 較好，因為不會在他們身上浪費運算資源。
- 資料不會被推送到朋友，因此沒有 hotkey 問題。
缺點：
- 取得 news feed 很慢，因為 news feed 沒有預先計算。
我們採用混合方法以同時取得兩種方法的好處並避免其陷阱。由於快速取得 news feed 至關重要，我們對大多數使用者使用 push 模型。對於名人或擁有許多朋友／追隨者的使用者，我們讓追隨者按需拉取貼文內容，以避免系統過載。一致性雜湊是緩解 hotkey 問題的有用技術，因為它有助於更平均地分散請求／資料。
讓我們仔細看看 fanout service，如圖 5 所示。
Fanout service 運作如下：
從**圖形資料庫（graph database）**取得朋友 ID。圖形資料庫適合管理朋友關係與朋友推薦。希望進一步了解此概念的讀者請參考參考資料 [2]。
從使用者快取取得朋友資訊。系統接著根據使用者設定過濾朋友。例如，如果你靜音了某人，她的貼文不會出現在你的 news feed，即使你們仍然是朋友。另一個貼文可能不顯示的原因是，使用者可能選擇性地與特定朋友分享資訊或對其他人隱藏。
將朋友清單與新貼文 ID 送到訊息佇列。
Fanout workers 從訊息佇列取得資料並把 news feed 資料儲存到 news feed 快取。你可以把 news feed 快取想成 <post_id, user_id> 的對應表。每當有新貼文發佈時，它會被附加到 news feed 表中，如圖 6 所示。
如果我們把整個 user 與 post 物件存進快取，記憶體使用量會變得非常龐大，因此只儲存 ID。為了讓記憶體大小保持較小，我們設定一個可設定的上限。使用者捲動到 news feed 中數千則貼文的機率很低。大多數使用者只對最新內容感興趣，因此快取未命中率（cache miss rate）很低。
將 <post_id, user_id> 儲存到 news feed 快取。圖 6 顯示快取中 news feed 的範例。
| post_id | user_id |
|---|---|
| post_id | user_id |
| post_id | user_id |
| post_id | user_id |
| post_id | user_id |
| post_id | user_id |
| post_id | user_id |
| post_id | user_id |
圖 6
Newsfeed 取得深入探討#
圖 7 說明 news feed 取得的詳細設計。
如圖 7 所示，媒體內容（圖片、影片等）儲存在 CDN 中以快速取得。讓我們看看客戶端如何取得 news feed。
- 使用者送出請求以取得她的 news feed。請求看起來像這樣：/v1/me/feed
- 負載平衡器將請求重新分配到網頁伺服器。
- 網頁伺服器呼叫 news feed service 以取得 news feed。
- News feed service 從 news feed 快取中取得貼文 ID 清單。
- 使用者的 news feed 不只是 feed ID 清單。它包含使用者名稱、頭像、貼文內容、貼文圖片等。因此，news feed service 從快取（user cache 與 post cache）取得完整的 user 與 post 物件，以建構**完整充水（fully hydrated）**的 news feed。
- 完整充水的 news feed 以 JSON 格式回傳給客戶端供渲染。
快取架構#
快取對於 news feed 系統極為重要。我們將快取層分為 5 層，如圖 8 所示。
- News Feed：儲存 news feed 的 ID。
- Content：儲存每則貼文的資料。熱門內容儲存在 hot cache。
- Social Graph：儲存使用者關係資料。
- Action：儲存關於使用者是否對某貼文按讚、回覆，或對某貼文採取其他行動的資訊。
- Counters：儲存按讚、回覆、追隨者、追隨中等的計數器。
Step 4 - 總結#
在本章中，我們設計了一個 news feed 系統。我們的設計包含兩個流程：feed 發佈與 news feed 取得。
如同任何系統設計面試題，沒有完美的系統設計方式。每家公司都有其獨特的限制條件，你必須設計一個能符合這些限制的系統。理解你的設計與技術選擇所涉及的權衡很重要。
如果還有幾分鐘，你可以談談擴展性議題。為了避免重複討論，以下只列出高階的討論點。
擴展資料庫：
- 垂直擴展 vs 水平擴展
- SQL vs NoSQL
- 主從複寫（Master-slave replication）
- 唯讀副本（Read replicas）
- 一致性模型
- 資料庫分片
其他討論點：
- 保持 web tier 無狀態
- 盡可能將資料快取
- 支援多資料中心
- 用訊息佇列鬆散耦合元件
- 監控關鍵指標。例如，尖峰時段的 QPS 與使用者重新整理 news feed 時的延遲都值得監控。
恭喜你看到這裡！現在給自己一個鼓勵。做得好！