“ Top K 系統(tǒng) ” 是非常常見(jiàn)的一種子系統(tǒng)，基本上，就是從全量巨大的統(tǒng)計(jì)數(shù)據(jù)中，篩選出數(shù)值最大的 K 個(gè)來(lái)并按序展示。這樣的篩選可以是全時(shí)間內(nèi)的，也可以是最近某一段時(shí)間內(nèi)的；可以是全分類的，也可以是某個(gè)特定分類的。
具體來(lái)說(shuō)，像 Twitter 的 Trending Topic，微博熱搜，視頻網(wǎng)站的點(diǎn)擊排行，下載排行（可以是日榜、月榜、總榜）等等。這樣的系統(tǒng)，在統(tǒng)計(jì)數(shù)據(jù)非常大（heavy hitters）的時(shí)候，其中的挑戰(zhàn)性在于兩個(gè)：
無(wú)法簡(jiǎn)單地在單臺(tái)機(jī)器的內(nèi)存中進(jìn)行目標(biāo) id -> count 計(jì)數(shù)的簡(jiǎn)單映射，因?yàn)閿?shù)據(jù)量太大，內(nèi)存放不下。
無(wú)法用實(shí)時(shí)的方式高效地顯示出動(dòng)態(tài)變化的 Top K 列表來(lái)。
image.png
- 上圖包含了兩個(gè)思路，一個(gè)是實(shí)時(shí)排行（榜單），通過(guò) Count-min Sketch 實(shí)現(xiàn)，快速，但是不夠精確（或者使用 Lossy Counting）；另一個(gè)是周期性排行，通過(guò)異步的 MR 數(shù)據(jù)處理實(shí)現(xiàn)，數(shù)據(jù)上看比較準(zhǔn)確，但是處理是異步的，實(shí)時(shí)性差。
- 第一個(gè)思路方面，統(tǒng)計(jì)要盡可能實(shí)時(shí)。為了提高處理效率，用戶的話題引用可以直接進(jìn)入 filter 進(jìn)行處理。在我讀到的某些材料中，類似系統(tǒng)這一步也有通過(guò)異步批量的方式進(jìn)入隊(duì)列并處理的。不過(guò)在這里，我還是保留了比較簡(jiǎn)單的一種實(shí)現(xiàn)。
- 接著經(jīng)過(guò)簡(jiǎn)單的 filtering 和 parsing 去掉不關(guān)心的數(shù)據(jù)，比如對(duì)于微博的話題來(lái)說(shuō)，某一些詞是小詞，或者是我們不希望成為話題的詞；而某一些近似詞可以合并。完成以后數(shù)據(jù)有兩個(gè)去向，一個(gè)是右側(cè)的即時(shí)統(tǒng)計(jì)，一個(gè)是持久化到下方的數(shù)據(jù)庫(kù)中（這個(gè)數(shù)據(jù)庫(kù)可以是 Redis 這樣的 KV 數(shù)據(jù)庫(kù)）。
- 對(duì)于每一個(gè)詞，經(jīng)過(guò) hash 以后，到 Count-min Sketch 表格中累積計(jì)數(shù)，并根據(jù)計(jì)數(shù)到當(dāng)前大小為 K 的最小堆（這個(gè)最小堆用來(lái)存放一定時(shí)間內(nèi)累計(jì)的前 K 大條目）中尋找是否比堆頂更大，如果是，就入堆并移除原堆頂，從而保持堆的大小為 K。由于 Count-min Sketch 這個(gè)堆的大小都是確定并可控的，這樣的統(tǒng)計(jì)就可以在單個(gè)節(jié)點(diǎn)上完成了。
- 如果需要的即時(shí)統(tǒng)計(jì)數(shù)據(jù)不是 “總榜”，而是最近一段時(shí)間的 “趨勢(shì)榜”，那就可以借助 Ring Buffer——比如我們只關(guān)心最近一小時(shí)的趨勢(shì)，就可以把一小時(shí)劃分為 ring 上的 60 個(gè)區(qū)間，每個(gè)區(qū)間使用 Count-min Sketch 甚至簡(jiǎn)單的 Map 分別統(tǒng)計(jì)，趨勢(shì)榜每次可聚合這 60 個(gè)區(qū)間得出 top K；每過(guò)一分鐘都覆寫(xiě)最老的那一個(gè)區(qū)間的數(shù)據(jù)，從而保證 ring 上的數(shù)據(jù)始終是最近一小時(shí)的。
- 第二個(gè)思路方面，統(tǒng)計(jì)不實(shí)時(shí)，但相對(duì)精確。對(duì)于這些持久化的數(shù)據(jù)，由 MR 的 job 定期執(zhí)行來(lái)處理，并更新結(jié)果到數(shù)據(jù)庫(kù)中。
- 讀取數(shù)據(jù)的時(shí)候，根據(jù)需要可以讀取即時(shí)統(tǒng)計(jì)或者異步計(jì)算得到的統(tǒng)計(jì)數(shù)據(jù)，數(shù)據(jù)可以在外部緩存。
轉(zhuǎn)自：https://www.raychase.net/6275
