“ Top K 系統(tǒng) ” 是非常常見的一種子系統(tǒng)飘庄，基本上脑蠕，就是從全量巨大的統(tǒng)計數據中，篩選出數值最大的 K 個來并按序展示跪削。這樣的篩選可以是全時間內的谴仙，也可以是最近某一段時間內的；可以是全分類的碾盐，也可以是某個特定分類的晃跺。
具體來說，像 Twitter 的 Trending Topic廓旬，微博熱搜哼审，視頻網站的點擊排行，下載排行（可以是日榜孕豹、月榜、總榜）等等十气。這樣的系統(tǒng)励背，在統(tǒng)計數據非常大（heavy hitters）的時候，其中的挑戰(zhàn)性在于兩個：
無法簡單地在單臺機器的內存中進行目標 id -> count 計數的簡單映射砸西，因為數據量太大叶眉，內存放不下。
無法用實時的方式高效地顯示出動態(tài)變化的 Top K 列表來芹枷。
image.png
- 上圖包含了兩個思路衅疙，一個是實時排行（榜單），通過 Count-min Sketch 實現鸳慈，快速饱溢，但是不夠精確（或者使用 Lossy Counting）；另一個是周期性排行走芋，通過異步的 MR 數據處理實現绩郎，數據上看比較準確潘鲫，但是處理是異步的，實時性差肋杖。
- 第一個思路方面溉仑，統(tǒng)計要盡可能實時。為了提高處理效率状植，用戶的話題引用可以直接進入 filter 進行處理浊竟。在我讀到的某些材料中，類似系統(tǒng)這一步也有通過異步批量的方式進入隊列并處理的津畸。不過在這里振定，我還是保留了比較簡單的一種實現。
- 接著經過簡單的 filtering 和 parsing 去掉不關心的數據洼畅，比如對于微博的話題來說吩案，某一些詞是小詞，或者是我們不希望成為話題的詞帝簇；而某一些近似詞可以合并徘郭。完成以后數據有兩個去向，一個是右側的即時統(tǒng)計丧肴，一個是持久化到下方的數據庫中（這個數據庫可以是 Redis 這樣的 KV 數據庫）残揉。
- 對于每一個詞，經過 hash 以后芋浮，到 Count-min Sketch 表格中累積計數抱环，并根據計數到當前大小為 K 的最小堆（這個最小堆用來存放一定時間內累計的前 K 大條目）中尋找是否比堆頂更大，如果是纸巷，就入堆并移除原堆頂镇草，從而保持堆的大小為 K。由于 Count-min Sketch 這個堆的大小都是確定并可控的瘤旨，這樣的統(tǒng)計就可以在單個節(jié)點上完成了梯啤。
- 如果需要的即時統(tǒng)計數據不是 “總榜”，而是最近一段時間的 “趨勢榜”存哲，那就可以借助 Ring Buffer——比如我們只關心最近一小時的趨勢因宇，就可以把一小時劃分為 ring 上的 60 個區(qū)間，每個區(qū)間使用 Count-min Sketch 甚至簡單的 Map 分別統(tǒng)計祟偷，趨勢榜每次可聚合這 60 個區(qū)間得出 top K察滑；每過一分鐘都覆寫最老的那一個區(qū)間的數據，從而保證 ring 上的數據始終是最近一小時的修肠。
- 第二個思路方面贺辰，統(tǒng)計不實時，但相對精確。對于這些持久化的數據魂爪，由 MR 的 job 定期執(zhí)行來處理先舷，并更新結果到數據庫中。
- 讀取數據的時候滓侍，根據需要可以讀取即時統(tǒng)計或者異步計算得到的統(tǒng)計數據蒋川，數據可以在外部緩存。
