Twitter的Timeline是怎樣服務數億用戶的？

和傳統的網站相比，社交網站的擴展是非常難的工程問題。有幾方面的原因：

• 社交網站用戶的活躍度更高，在同一時刻，很大比例的用戶處於活躍狀態。與這些用戶相關的數據也處於活躍狀態，因此大量數據必須保存在緩存中，以便加快存取。
• 數據難以切分，因為社交網路的用戶是相互連接的。對於普通的網站，可以使用簡單的一致性hash演算法把數據分散到不同節點上，但是社交網路沒辦法做這種簡單處理。

Twitter的時間線（Timeline）服務就充分展示了社交網路應用的複雜性。時間線展示了社交網路用戶發布的內容，不同社交網路對於時間線的讀、寫請求，有不同的處理方式。Facebook在用戶發布狀態時，只是把數據寫入資料庫；在用戶讀取時間線的時候，從資料庫中讀取所有好友的狀態更新，構造時間線。但是Twitter的做法不同，會存儲並維護每個用戶獨立的時間線，在用戶發推文的時候，Twitter會把這條推文的ID寫入所有關注者的時間線中；在用戶讀取的時候，可以快速獲得自己的時間線。下面分析一下Twitter的時間線服務。

Twitter

Twitter逐步從一個簡單三層架構的Ruby On Rails應用成長為一個服務驅動的龐大網站。當前擁有數億活躍用戶，獲取時間線的請求達到30萬QPS，每天有多達4億條推文在系統里流動。 從Lady Gaga發出一條推文，到她3100萬粉絲全部收到需要5分鐘時間。

• Twitter不再是一個Web應用，它致力通過一系列的API，成為整個地球最大的實時消息匯流排。
• Twitter系統以消費為主，而不是生產為主。時間線讀請求達到30萬QPS，而寫請求只有6000QPS左右。
• 有龐大粉絲群體的用戶越來越常見。這樣的用戶發一條推文擴散到所有粉絲有可能很慢。Twitter試圖在5秒內完成，但是並不是總能達成這個目標，尤其當名人之間互發推文的時候。
• 每個用戶的主頁時間線以列表形式保存在Redis集群中，最多可存儲800條推文。

Twitter的挑戰

• 數億用戶，時間線服務超過30萬QPS（包括主頁和搜索）。人們在Twitter不停創造內容。Twitter的任務就是把內容整合併向粉絲推送出去。
• 曾嘗試採用select語句查詢來構造時間線，在用戶超過一定數量時，已經不可行。
• 解決方案是寫操作的擴散（fanout）。當推文到達的時候，系統把推文寫到多個位置上。這可以讓讀操作更加便捷快速。讀操作本身不會做任何計算。由於所有工作都由寫操作完成，寫操作的速率低於讀操作，大概在4000QPS左右。
• 真正的挑戰是實時性的要求。Twitter的目標是讓推文消息在5秒鐘之內能到達用戶。消息推送的目的地包括時間線集群（內存中）、移動APP推送、郵件、簡訊等等。Twitter是單用戶SMS發送最多的應用。

技術方案

• Twitter的信息發布有兩種方式：
  • 拉取：主頁時間線和查詢、搜索API是基於拉取實現的。
  • 推送：Twitter運行著一個最大的實時事件推送系統，速率達到22MB/S。客戶端向Twitter推送服務建立一個socket連接，twitter會在150ms內完成推文的推送。在任何時刻，有100萬個連接連在推送服務上。TwitterDeck應用也是使用推送服務來接受推文的。

• 基於拉取的時間線：

時間線有兩種：主頁時間線（關注的用戶發布的所有推文）和用戶時間線（用戶發送的所有推文），時間線的構造涉及一些業務邏輯，比如當前未關注的用戶的回復會被過濾掉。

當推文通過寫介面到達的時候，它經過負載均衡和TFE（Twitter前端服務），執行一些業務邏輯。然後，就開始執行fanout過程：推文先存儲在一個龐大的Redis集群中，每條推文會在3個不同機器上有備份；然後fanout查詢社交關係資料庫（Flock），Flock維護著用戶間互相關注的關係圖；Flock返回推文接受者的列表，然後fanout開始循環把推文寫到這些人的時間線中（時間線使用Redis的List存儲）。假設你有2萬粉絲，fanout服務會查找你的2萬粉絲的時間線所在的位置，然後把推文ID、發送方ID以及幾個標誌位插入到這些時間線中。所以你發一條推文，會有2萬個插入操作。每個人的home時間線最多有800條。活躍用戶（過去30天內有登錄的用戶）的時間線存儲在內存中，以減少響應時間。如果一個用戶的時間線不在內存中，訪問時會觸發一個重建的過程：先查詢社交關係資料庫，找到你關注的人，然後查詢每個人的推文，把構造好的時間線重新寫入Redis。推文的磁碟存儲使用的是MySQL。

處理讀時間線請求時，只要找到相應用戶的時間線在集群中的位置，就可以迅速返回。提高讀操作效率的代價就是寫操作（fanout）需要的時間長一些。因為時間線的數據結構中只包含ID，在讀操作返回給用戶之前，需要填充推文的內容，向T-bird（推文的存儲服務）發送一條multiget的命令即可獲得所有推文。在時間線返回之前也需要做一些過濾操作，比如在法國，和納粹相關的內容會被過濾掉。

寫到所有Redis集群是一個O(N)的過程。對於N很大的情況，比如Taylor Swift或者奧巴馬這樣的名人發布一條推文，需要有上千萬的fanout操作；當兩個名人互發推文，這個延遲時間就會更長。對於這種情況，Twitter考慮了讀路徑和寫路徑的平衡：對於粉絲眾多的用戶，他們的推文不是在寫入時fanout，而是在粉絲讀取時查詢、併入時間線。

時間線的讀取是一個O(1)操作，僅需幾十毫秒。Twitter對於讀操作做這樣的優化，是因為Twitter偏重於信息消費，而不是信息生產。

• 搜索和時間線相反，所有的計算都發生在讀路徑上。

當推文進入系統時，Ingester對推文做詞法分析，根據索引的種類，把推文發送到EarlyBird（一個自定製的Lucene），索引是存儲在內存中的。和fanout不同，推文在Early bird只存儲一份。在讀取搜索結果時，Blender負責完成搜索時間線的構造，它會查詢所有的EarlyBird分片，把返回的結果合併、排序並返回。

Twitter的Discovery（發現服務）其實是基於系統對你的了解（你的關注、點擊等等）定製的一個特殊搜索。

對於寫操作的時間複雜度是O(1)，但是讀操作是O(N)。但是因為索引保存在內存中，搜索還是比較快的，響應時間在幾百毫秒的級別。

參考資料

http://highscalability.com/blog/2013/7/8/the-architecture-twitter-uses-to-deal-with-150m-active-users.html

http://highscalability.com/blog/2009/10/13/why-are-facebook-digg-and-twitter-so-hard-to-scale.html

Timelines at Scale
推薦閱讀：