Reddit 如何統(tǒng)計(jì)每個(gè)帖子的瀏覽量

之前沒聽過也沒了解過HyperLogLog，通過翻譯這篇文章正好簡(jiǎn)單學(xué)習(xí)下。歡迎指正錯(cuò)誤~

我們想要更好的向用戶展示Reddit的規(guī)模。為了這一點(diǎn)，投票和評(píng)論數(shù)是一個(gè)帖子最重要的指標(biāo)。然而，在Reddit上有相當(dāng)多的用戶只瀏覽內(nèi)容，既不投票也不評(píng)論。所以我們想要建立一個(gè)能夠計(jì)算一個(gè)帖子瀏覽數(shù)的系統(tǒng)。這一數(shù)字會(huì)被展示給帖子的創(chuàng)作者和版主，以便他們更好的了解某個(gè)帖子的活躍程度。

在這篇博客中，我們將討論我們是如何實(shí)現(xiàn)超大數(shù)據(jù)量的計(jì)數(shù)。

計(jì)數(shù)機(jī)制

對(duì)于計(jì)數(shù)系統(tǒng)我們主要有四種需求:

帖子瀏覽數(shù)必須是實(shí)時(shí)或者近實(shí)時(shí)的，而不是每天或者每小時(shí)匯總。

同一用戶在短時(shí)間內(nèi)多次訪問帖子，只算一個(gè)瀏覽量

顯示的瀏覽量與真實(shí)瀏覽量間允許有小百分之幾的誤差

Reddit是全球訪問量第八的網(wǎng)站，系統(tǒng)要能在生產(chǎn)環(huán)境的規(guī)模上正常運(yùn)行，僅允許幾秒的延遲

要全部滿足以上四個(gè)需求的困難遠(yuǎn)遠(yuǎn)比聽上去大的多。為了實(shí)時(shí)精準(zhǔn)計(jì)數(shù)，我們需要知道某個(gè)用戶是否曾經(jīng)訪問過這篇帖子。想要知道這個(gè)信息，我們就要為每篇帖子維護(hù)一個(gè)訪問用戶的集合，然后在每次計(jì)算瀏覽量時(shí)檢查集合。一個(gè)naive的實(shí)現(xiàn)方式就是將訪問用戶的集合存儲(chǔ)在內(nèi)存的hashMap中，以帖子Id為key。

這種實(shí)現(xiàn)方式對(duì)于訪問量低的帖子是可行的，但一旦一個(gè)帖子變得流行，訪問量劇增時(shí)就很難控制了。甚至有的帖子有超過100萬的獨(dú)立訪客！對(duì)于這樣的帖子，存儲(chǔ)獨(dú)立訪客的ID并且頻繁查詢某個(gè)用戶是否之前曾訪問過會(huì)給內(nèi)存和CPU造成很大的負(fù)擔(dān)。

因?yàn)槲覀儾荒芴峁?zhǔn)確的計(jì)數(shù)，我們查看了幾種不同的基數(shù)估計(jì)算法。有兩個(gè)符合我們需求的選擇：

一是線性概率計(jì)數(shù)法，很準(zhǔn)確，但當(dāng)計(jì)數(shù)集合變大時(shí)所需內(nèi)存會(huì)線性變大。

二是基于HyperLogLog(以下簡(jiǎn)稱HLL)的計(jì)數(shù)法。HLL空間復(fù)雜度較低，但是精確度不如線性計(jì)數(shù)。

下面看下HLL會(huì)節(jié)省多少內(nèi)存。如果我們需要存儲(chǔ)100萬個(gè)獨(dú)立訪客的ID,每個(gè)用戶ID 8字節(jié)長(zhǎng)，那么為了存儲(chǔ)一篇帖子的獨(dú)立訪客我們就需要8 M的內(nèi)存。反之，如果采用HLL會(huì)顯著減少內(nèi)存占用。不同的HLL實(shí)現(xiàn)方式消耗的內(nèi)存不同。如果采用這篇文章的實(shí)現(xiàn)方法，那么存儲(chǔ)100萬個(gè)ID僅需12 KB，是原來的0.15%！！

Big Data Counting:How to count a billion distinct objects using only 1.5KB of Memory–High Scalability-這篇文章很好的總結(jié)了上面的算法。

許多HLL的實(shí)現(xiàn)都是結(jié)合了上面兩種算法。在集合小的時(shí)候采用線性計(jì)數(shù)，當(dāng)集合大小到達(dá)一定的閾值后切換到HLL。前者通常被成為”稀疏“(sparse)HLL，后者被稱為”稠密“(dense)HLL。這種結(jié)合了兩種算法的實(shí)現(xiàn)有很大的好處，因?yàn)樗鼘?duì)于小集合和大集合都能夠保證精確度，同時(shí)保證了適度的內(nèi)存增長(zhǎng)?？梢栽趃oogle的這篇論文中了解這種實(shí)現(xiàn)的詳細(xì)內(nèi)容。

論文鏈接

https://antirez.com/news/75

現(xiàn)在我們已經(jīng)確定要采用HLL算法了，不過在選擇具體的實(shí)現(xiàn)時(shí)，我們考慮了以下三種不同的實(shí)現(xiàn)。因?yàn)槲覀兊臄?shù)據(jù)工程團(tuán)隊(duì)使用Java和Scala，所以我們只考慮Java和Scala的實(shí)現(xiàn)。

Twitter提供的Algebird，采用Scala實(shí)現(xiàn)。Algebird有很好的文檔，但他們對(duì)于sparse和dense HLL的實(shí)現(xiàn)細(xì)節(jié)不是很容易理解。

stream-lib中提供的HyperLogLog++，采用Java實(shí)現(xiàn)。stream-lib中的代碼文檔齊全，但有些難理解如何合適的使用并且改造的符合我們的需求。

Redis HLL實(shí)現(xiàn)，這是我們最終選擇的。我們認(rèn)為Redis中HLLs的實(shí)現(xiàn)文檔齊全、容易配置，提供的相關(guān)API也很容易集成。還有一個(gè)好處是，我們可以用一臺(tái)專門的服務(wù)器部署，從而減輕性能上的壓力。

Reddit的數(shù)據(jù)管道依賴于Kafka。當(dāng)一個(gè)用戶訪問了一篇博客，會(huì)觸發(fā)一個(gè)事件，事件會(huì)被發(fā)送到事件收集服務(wù)器，并被持久化在Kafka中。

之后，計(jì)數(shù)系統(tǒng)會(huì)依次順序運(yùn)行兩個(gè)組件。在我們的計(jì)數(shù)系統(tǒng)架構(gòu)中，第一部分是一個(gè)Kafka的消費(fèi)者，我們稱之為Nazar。Nazar會(huì)從Kafka中讀取每個(gè)事件，并將它通過一系列配置的規(guī)則來判斷該事件是否需要被計(jì)數(shù)。我們?nèi)∵@個(gè)名字僅僅是因?yàn)镹azar是一個(gè)眼睛形狀的護(hù)身符，而”Nazar“系統(tǒng)就像眼睛一樣使我們的計(jì)數(shù)系統(tǒng)遠(yuǎn)離不懷好意者的破壞。其中一個(gè)我們不將一個(gè)事件計(jì)算在內(nèi)的原因就是同一個(gè)用戶在很短時(shí)間內(nèi)重復(fù)訪問。Nazar會(huì)修改事件，加上個(gè)標(biāo)明是否應(yīng)該被計(jì)數(shù)的布爾標(biāo)識(shí)，并將事件重新放入Kafka。

下面就到了系統(tǒng)的第二個(gè)部分。我們將第二個(gè)Kafka的消費(fèi)者稱作Abacus，用來進(jìn)行真正瀏覽量的計(jì)算，并且將計(jì)算結(jié)果顯示在網(wǎng)站或客戶端。Abacus從Kafka中讀取經(jīng)過Nazar處理過的事件，并根據(jù)Nazar的處理結(jié)果決定是跳過這個(gè)事件還是將其加入計(jì)數(shù)。如果Nazar中的處理結(jié)果是可以加入計(jì)數(shù)，那么Abacus首先會(huì)檢查這個(gè)事件所關(guān)聯(lián)的帖子在Redis中是否已經(jīng)存在了一個(gè)HLL計(jì)數(shù)器。如果已經(jīng)存在，Abacus會(huì)給Redis發(fā)送個(gè)PFADD的請(qǐng)求。如果不存在，那么Abacus會(huì)給Cassandra集群發(fā)送個(gè)請(qǐng)求（Cassandra用來持久化HLL計(jì)數(shù)器和計(jì)數(shù)值的），然后向Redis發(fā)送SET請(qǐng)求。這通常會(huì)發(fā)生在網(wǎng)友訪問較老帖子的時(shí)候，這時(shí)該帖子的計(jì)數(shù)器很可能已經(jīng)在Redis中過期了。

為了存儲(chǔ)存在Redis中的計(jì)數(shù)器過期的老帖子的瀏覽量。Abacus會(huì)周期性的將Redis中全部的HLL和每篇帖子的瀏覽量寫入到Cassandra集群中。為了避免集群過載，我們以10秒為周期批量寫入。

下圖是事件流的大致流程：

總結(jié)

我們希望瀏覽量可以讓發(fā)帖者了解帖子全部的訪問量，也幫助版主快速定位自己社區(qū)中高訪問量的帖子。在未來，我們計(jì)劃利用我們數(shù)據(jù)管道在實(shí)時(shí)方面的潛力來為Reddit的用戶提供更多的有用的反饋。