本文翻譯自全球訪問(wèn)量排名第8位的論壇Reddit博客上的文章，講的是關(guān)于Reddit如何在海量瀏覽量下實(shí)時(shí)統(tǒng)計(jì)瀏覽量的褪那。
本文我們就來(lái)聊一聊，Reddit是如何在大規(guī)模下統(tǒng)計(jì)帖子瀏覽量的式塌。
統(tǒng)計(jì)方法
我們對(duì)統(tǒng)計(jì)瀏覽量有四個(gè)基本的要求
- 計(jì)數(shù)必須達(dá)到實(shí)時(shí)或者接近實(shí)時(shí)博敬。
- 每個(gè)用戶(hù)在一個(gè)時(shí)間窗口內(nèi)僅被記錄一次。
- 帖子顯示的統(tǒng)計(jì)數(shù)量的誤差不能超過(guò)百分之幾峰尝。
- 整個(gè)系統(tǒng)必須能在生成環(huán)境下偏窝，數(shù)秒內(nèi)完成閱讀計(jì)數(shù)的處理。
滿足上面四個(gè)條件武学，其實(shí)比想象中要復(fù)雜祭往。為了在實(shí)時(shí)統(tǒng)計(jì)的情況下保持精準(zhǔn)度，我們需要知道某一個(gè)用戶(hù)之前是否瀏覽過(guò)一篇文章火窒，所以我們需要為每一篇文章存儲(chǔ)瀏覽過(guò)它的用戶(hù)的集合硼补，并且在每次新增瀏覽時(shí)檢查該集合進(jìn)行去重復(fù)操作。
一個(gè)比較簡(jiǎn)單的解決方案是熏矿，為每篇文章維護(hù)一個(gè)哈希表括勺，用文章ID作為key，去重的userid的集合(set數(shù)據(jù)結(jié)構(gòu))作為value曲掰。
這種方案在文章數(shù)量和閱讀數(shù)比較小的情況下疾捍，還能很好的運(yùn)行，但當(dāng)數(shù)據(jù)量到達(dá)大規(guī)模時(shí)栏妖，它就不適用了乱豆。尤其是該文章變成了熱門(mén)文章，閱讀數(shù)迅速增長(zhǎng)吊趾，有些受歡迎的文章的閱讀者數(shù)量超過(guò)百萬(wàn)級(jí)別宛裕，想象一下維護(hù)一個(gè)超過(guò)百萬(wàn)的unqine userId的集合在內(nèi)存中的瑟啃，還有經(jīng)受住不斷的查詢(xún)，集合中的用戶(hù)是否存在揩尸。
自從我們決定不提供100%精準(zhǔn)的數(shù)據(jù)后蛹屿，我們開(kāi)始考慮使用幾種不同的基數(shù)估計(jì)算法。我們綜合考慮下選出量?jī)蓚€(gè)可以滿足需求的算法：
- 線性概率計(jì)算方法岩榆，它非常精確错负，但是需要的內(nèi)存數(shù)量是根據(jù)用戶(hù)數(shù)線性增長(zhǎng)的。
- 基于HyperLogLog (HLL)的計(jì)算方法勇边，HLL的內(nèi)存增長(zhǎng)是非線性的犹撒，但是統(tǒng)計(jì)的精準(zhǔn)度和線性概率就不是同一級(jí)別的了。
為了更好的理解基于HLL的計(jì)算方法粒褒，究竟能夠節(jié)省多少內(nèi)存识颊，我們這里使用一個(gè)例子∞确兀考慮到r/pics文章祥款，在本文開(kāi)頭提及，該文章收到了超過(guò)一百萬(wàn)用戶(hù)的瀏覽過(guò)月杉，如果我們存儲(chǔ)一百萬(wàn)個(gè)唯一的用戶(hù)ID刃跛，每一個(gè)id占用8個(gè)字節(jié)，那么僅僅一篇文章就需要8mb的空間存儲(chǔ)沙合！對(duì)照著HLL所需要的存儲(chǔ)空間就非常少了，在這個(gè)例子中使用HLL計(jì)算方法僅需要 12kb的空間也就是第一種方法的0.15%跌帐。
(This article on High Scalability 這篇文章講解了上面的兩種算法.)
有很多的HLL實(shí)現(xiàn)是基于上面兩種算法的結(jié)合而成的首懈，也就是一開(kāi)始統(tǒng)計(jì)數(shù)量少的情況下使用線性概率方法，當(dāng)數(shù)量達(dá)到一定閾值時(shí)谨敛，切換為HLL方法究履。這種混合方法非常有用，不但能夠?yàn)樾×繑?shù)據(jù)集提供精準(zhǔn)性脸狸，也能為大量數(shù)據(jù)節(jié)省存儲(chǔ)空間最仑。該種實(shí)現(xiàn)方式的細(xì)節(jié)請(qǐng)參閱論文（Google’s HyperLogLog++ paper）
HLL算法的實(shí)現(xiàn)是相當(dāng)標(biāo)準(zhǔn)的，這里有三種不同的實(shí)現(xiàn)方式炊甲，要注意的是泥彤，基于內(nèi)存存儲(chǔ)方案的HLL，這里我們只考慮Java和Scale兩種實(shí)現(xiàn)
- Twitter的Algebird庫(kù)卿啡，Scala實(shí)現(xiàn)吟吝，Algebird的文檔撰寫(xiě)非常好，但是關(guān)于它是如何實(shí)現(xiàn)HLL的颈娜，不是很容易理解剑逃。
- stream-lib庫(kù)中的HyperLogLog++實(shí)現(xiàn)浙宜，Java編寫(xiě)。 stream-lib代碼的文檔化做的很好蛹磺，但我們對(duì)如何適當(dāng)調(diào)優(yōu)它粟瞬，還是有些困惑的。
- Redis的HLL實(shí)現(xiàn)(我們最終的選擇)萤捆，我們覺(jué)得Redis的實(shí)現(xiàn)不管從文檔完善程度還是配置和提供的API接口裙品，來(lái)說(shuō)做的都非常好。另外的加分點(diǎn)是鳖轰，使用Redis可以減少我們對(duì)CPU和內(nèi)存性能的擔(dān)憂清酥。
Reddit的數(shù)據(jù)管道，主要都是使用Apache Kafka的蕴侣。每當(dāng)一個(gè)用戶(hù)瀏覽一篇文章時(shí)焰轻，就會(huì)觸發(fā)一個(gè)事件并且被發(fā)送到事件收集服務(wù)器，然后批量的將這些事件發(fā)送打kafka中進(jìn)行持久化昆雀。
Reddit的瀏覽統(tǒng)計(jì)系統(tǒng)辱志，分為兩個(gè)順序執(zhí)行的組成部分，其中的第一部分是狞膘，被稱(chēng)為Nazar的kafka隊(duì)列『消費(fèi)者』(consumer) 揩懒，它會(huì)從kafka中讀取事件，然后將這些事件通過(guò)特定的條件進(jìn)行過(guò)濾挽封，判斷改事件是否應(yīng)該被算作一次文章閱讀計(jì)數(shù)已球，它被稱(chēng)為『NAZAR』是因?yàn)樵谙到y(tǒng)中它有作為『眼鏡』的用處，識(shí)別出哪些事件是不應(yīng)該被加入到統(tǒng)計(jì)中的辅愿。Nazar使用Redis 維護(hù)狀態(tài)還有一個(gè)事件不被計(jì)數(shù)的潛在原因智亮，這個(gè)原因可能是用戶(hù)短時(shí)間內(nèi)重復(fù)瀏覽統(tǒng)一文章。Nazar會(huì)在事件被發(fā)送回kafka時(shí)点待，為事件添加一個(gè)標(biāo)識(shí)位阔蛉，根據(jù)該事件是否被加入到計(jì)數(shù)當(dāng)中的布爾值。
統(tǒng)計(jì)系統(tǒng)的第二部是一個(gè)稱(chēng)為Abacus 的kafka『消費(fèi)者』它會(huì)真正的統(tǒng)計(jì)瀏覽量癞埠，并且讓瀏覽量數(shù)據(jù)可以在整站和客戶(hù)端上顯示状原， 它接收從Nazar發(fā)送出來(lái)的事件消息，然后根據(jù)該消息中包含著標(biāo)識(shí)值（Nazar中處理的）來(lái)判斷這個(gè)事件是否算做一次計(jì)數(shù)苗踪，如果事件被計(jì)數(shù)颠区，Abacus會(huì)首先檢查這個(gè)事件中文章的HLL計(jì)數(shù)是否存在于Redis中，如果存在通铲，Abacus會(huì)發(fā)送一個(gè)PFADD請(qǐng)求給Redis瓦呼，如果不存在，Abacus會(huì)發(fā)生一個(gè)請(qǐng)求到Cassandra集群，Cassandra集群會(huì)持久化HLL 計(jì)數(shù)和真實(shí)的原始計(jì)數(shù)數(shù)據(jù)央串，然后再發(fā)送一個(gè)SET請(qǐng)求到Redis磨澡，這個(gè)過(guò)程通常出現(xiàn)在用戶(hù)閱讀一個(gè)已經(jīng)被Redis剔除的就文章的情況下發(fā)送。
為了讓維護(hù)一個(gè)在Redis可能被剔除的舊文章质和，Abacus會(huì)定期的稳摄，從Redis中將HLL過(guò)濾數(shù)據(jù)，包括每篇文章的計(jì)數(shù)饲宿，全部寫(xiě)入到Cassandra集群中厦酬，當(dāng)然為了避免集群過(guò)載，這個(gè)步驟會(huì)分為每篇文章10秒一組批次進(jìn)行寫(xiě)入瘫想。下圖就是整個(gè)過(guò)程的流程圖仗阅。
