深度解析某頭條的一道面試題

首先，某頭條的文章量、用戶量都是很大的，點擊量那就更恐怖了。

請問，如果實時展現熱門文章，比如近8小時點擊量最大的文章前100名。

> 這個好辦啊，redis一個sortedset搞定啊，score計數，key是文章ID，不就ok了么？

> 回答的不錯，你可以走了！

要聽清題目，說好的8小時動態時間窗口，計數是會過期的。還有，頭條的量有這麼小么，一個redis就搞定了？同學啊，我告訴你，文章的量你起碼得估計個幾十萬，用戶你得估計幾個億，點擊量你至少得估計個1M/s吧。

數據接收

1M/s的點擊並發量，肯定是需要分散式了。客戶端可能會為了減輕伺服器的壓力而選擇延遲合併點擊請求進行批量發送。簡單起見，這裡就使用HTTP協議吧。我們先不考慮惡意用戶刷點擊的行為。

伺服器肯定會有多台機器多進程部署來接受點擊請求，接收到的請求在進行參數解析後，被發送到存儲單元。為了減輕存儲的壓力，每個進程可能會使用小窗口聚合數據，每隔一小段時間將窗口內的數據聚合起來一起發給存儲單元。

數據存儲

點擊數據是很重要的數據，用戶的興趣偏好就靠它了。這麼大的點擊數據如果全部用內存裝的話，成本太高。所以別指望完全使用redis了。

拿kafka存是一個好辦法，ZeroCopy機制並發量很高，數據持久化在磁碟里成本低。不過kafka的數據一般是有過期時間的，如果想完全記住用戶的點擊以便做長期的數據分析，少不了要使用hdfs了。

但是因為要做准實時統計，hdfs可不適合干這個，hdfs適合做離線統計的數據源。所以還得靠kafka接數據，然後消費者一邊入hdfs，一邊做實時統計。

實時統計可以使用spark stream、storm接受kafka的輸入，也可以自己手寫。

分散式TopN演算法

用戶太多，用戶表按用戶ID哈希分成了1024張子表。用戶表裡有一個欄位score，表示這個用戶的積分數。現在我們要計算前100名積分最多的用戶以及積分數，該怎麼查詢？

如果是單個表，一個SQL也就搞定了

select id, score from user order by score desc limit 100

如果是多個子表，你得在每個子表上都進行一次TopN查詢，然後聚合結果再做一次TopN查詢。下面是偽代碼

candidates = []for k in range(1024): # 每個表都取topn rows = select id, score from user_${k} order by score desc limit 100 # 聚合結果 candidates.extend(rows)# 根據score倒排candidates = sorted(candidates, key=lambda t: t[1], reverse=True)# 再取topncandidates[:100]

子表查詢可以多線程並行，提高聚合效率。

滑動窗口

8小時的滑動窗口，意味著新的數據源源不斷的進來，舊的數據時時刻刻在淘汰。嚴格來說，精準的8小時滑動窗口要求每條數據要嚴格的過期，差了1秒都不行，到點了就立即被淘汰。

精準的代價是我們要為每條點擊記錄都設置過期時間，過期時間本身也是需要存儲的，而且過期策略還需要定時掃描時間堆來確認哪些記錄過期了。量大的時候這些都是不容小噓的負擔。

但是在業務上來講，排行版沒有必要做到如此的精準，偏差個幾分鐘這都不是事。

業務上的折中給服務的資源優化帶來了機遇。我們對時間片進行了切分，一分鐘一個槽來進行計數。下面是偽代碼

class HitSlot { long timestamp; # earlies timestamp map[int]int hits; # post_id => hits void onHit(int postId, int hits) { this.hits[postId] += hits; }}class WindowSlots { HitSlot currentSlot; # current active slots LinkedList<HitSlot> historySlots; # history unactive slots map[int]int topHits; # topn posts void onHit(int postId, int hits) { # 因為上游有合併點擊，所以有了hits參數 long ts = System.currentTimeMillis(); if(this.currentSlot == null) { # 創建第一個槽 this.currentSlot == new HitSlot(ts); } elif(ts - this.currentSlot.timestamp > 60 * 1000) { # 創建下一個槽，一分鐘一個槽 this.historySlots.add(this.currentSlot); this.currentSlot = new HitSlot(ts); } this.currentSlot.onHit(postId, hits); } void onBeat() { # 維護窗口，移除過期的槽，然後統計topn，30s~60s調用一次 if(historySlots.isEmpty()) { return; } HitSlot slot = historySlots[0]; long ts = System.currentTimeMillis(); if(ts - slot.timestamp > 8 * 60 * 60 * 1000) { # 過期了8小時，移掉第一個 historySlots.remove(0); topHits = topn(aggregateSlots(historySlots)); # 計算topn的帖子 } }}

上面的代碼代表著每個分散式子節點的邏輯，因為是偽代碼，所以加鎖問題就不細寫了。

定時任務

每個子節點都會有一個定時任務去負責維持統計窗口，過期失效的統計數據，計算局部的topn熱帖。

現在每個子節點都有了各自的局部topn熱帖，那麼還需要一個主節點去匯總這些局部熱點，然後計算去全局熱帖。

主節點也沒必要特別實時，定期從子節點拉取topn數據即可，也可以讓位元組點主動彙報。

class HotPostsAggregator { map[int]map[int]int localTopnPosts; # nodeId => topn posts map[int]int globalTopnPosts; void onBeat() { // do aggregate // save globalTopnPosts to redis } void onLocalReport(int nodeId, map[int]int topnPosts) { // 子節點上報局部熱帖 }}

散列

按照頭條的文章至少幾十萬篇，如果每個子節點都要對所有的文章統計點擊數，似乎也會佔用不少內存，聚合和排序熱帖也會有不少計算量。最好的想法是每個子節點只負責一部分文章的統計，這樣可以明顯節省計算資源。

我們將kafka的分區數設置為位元組點的數量，這樣每個節點負責消費一個分區的數據。在kafka生產端，對點擊記錄的帖子ID進行散列，保證相同文章ID的點擊流進入相同的分區，最終流向同一個統計子節點。

消費者掛了

當機器增多時，節點掛掉的概率也會增大。硬體可能損壞，電源可能掉電，人為操作失誤。如果沒有做任何防範措施，當一個位元組點掛掉時，該節點上8個小時時間窗口的統計數據將會丟失。該節點所管理的局部熱點文章就喪失了進入全局熱帖的機會。

這可能不會對產品和體驗上帶來很大的傷害，節點重啟8小時之後也就完全恢復了。而且這8小時之內，喪失了部分文章的熱點投票權也不會對整體業務帶來巨大影響。

但是我們都希望系統可以更加完美一點不是么？當節點掛掉時，我們希望可以快速恢復狀態，這也是可以做到的，難度也不是很大，不過是定時做一下checkpoint，將當前的狀態持久化到本地文件或者資料庫中。因為每個子節點管理的文章不會太多，所以需要序列化的內容也不會太大。當節點重啟時，從持久化的checkpoint中將之前的狀態恢復出來，然後繼續進行消費和統計。

如果你使用的是spark-stream，它內置的checkpoint功能會讓你實現備份和恢復會更加簡單，更加安全。

如果你不想做checkpoint，辦法還是有的，就是可能耗時舊一點。那就是對hdfs中的存儲的所有的點擊流數據進行一次mapreduce，將8小時窗口內的點擊流的點擊量統計出來，然後想辦法導入到位元組點進程中去。

這要求hdfs的數據也是散列存儲的，和kafka對應，這樣可以快速圈出需要統計的數據範圍。也許會因為mapreduce本身會耗時一點時間，最終導致恢復的數據沒有那麼準確，不過這關係也不大，我們用這樣粗糙的方法，能對得起那9.5成的數據已經做的很不錯了。

點擊去重

上面講了一堆堆，代碼敲了不少圖畫了不少，似乎很有道理。但是還有個重要的沒提到，那就是點擊去重。如果一個用戶反覆點擊了很多次，那該如何計數比較合理。

一篇好的文章如果它不是太短的話，一般會吸引讀者反覆閱讀很多次。這個計數如果完全去重了記為一次似乎也不太合理。但是如果是故意被人反覆點擊而被記了太多次明顯也不好。那該如何選擇呢？

首先要從客戶端下手，客戶端本身可以過濾一部分無效點擊。同一篇文章在太短的時間內被當前用戶反覆點擊，這個模式還是很好發現的。如果間隔時間比較長，那就是讀者的回味點擊，屬於文章的正向反饋，應該記錄下來。

客戶端做好了，然後再從伺服器端下手，伺服器端下手就比較困難了。要探測用戶的行為模式意味著要對用戶的行為狀態化，這樣就會大量加重伺服器的存儲負擔。

伺服器還需要防止用戶的防刷行為。如果缺失防刷控制，一個頭條號可以通過這種漏洞來使得自己的文章非法獲得大量點擊，進入熱門文章列表，打上熱門標籤，被海量的用戶看到，就會獲得較大的經濟效益，即使這篇文章內容本身吸引力並不足夠。

當用戶發現這樣差勁的內容也能上熱門榜單時，無疑會對產品產生一定的質疑。如果這種行為泛濫開來，那就可能對產品造成比較致命的負面影響。

防刷是一門大型課題，本篇內容就不做詳細講解了，筆者在這方面也不是什麼專家。簡單點說放刷本質上就是提取惡意行為的特徵。常見的策略就是同一篇文章被來自於同一個IP或者有限的幾個IP的頻繁點擊請求，這時就可以使用封禁IP的招數來搞定。還可以使用用戶反饋機制來識別非正常的熱門內容，然後人工干預等。業界還有一些更高級的如機器學習深度學習等方法來防刷，這些讀者都可以自行搜索研究。

閱讀相關文章，關注公眾號【碼洞】

推薦閱讀：