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

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

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

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

計數(shù)機制

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

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

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

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

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

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

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

因為我們不能提供準確的計數(shù)，我們查看了幾種不同的基數(shù)估計算法。有兩個符合我們需求的選擇：

一是線性概率計數(shù)法，很準確，但當計數(shù)集合變大時所需內(nèi)存會線性變大。

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

下面看下HLL會節(jié)省多少內(nèi)存。如果我們需要存儲100萬個獨立訪客的ID,每個用戶ID 8字節(jié)長，那么為了存儲一篇帖子的獨立訪客我們就需要8 M的內(nèi)存。反之，如果采用HLL會顯著減少內(nèi)存占用。不同的HLL實現(xiàn)方式消耗的內(nèi)存不同。如果采用這篇文章的實現(xiàn)方法，那么存儲100萬個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的實現(xiàn)都是結(jié)合了上面兩種算法。在集合小的時候采用線性計數(shù)，當集合大小到達一定的閾值后切換到HLL。前者通常被成為”稀疏“(sparse)HLL，后者被稱為”稠密“(dense)HLL。這種結(jié)合了兩種算法的實現(xiàn)有很大的好處，因為它對于小集合和大集合都能夠保證精確度，同時保證了適度的內(nèi)存增長。可以在google的這篇論文中了解這種實現(xiàn)的詳細內(nèi)容。

論文鏈接

https://antirez.com/news/75

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

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

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

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

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

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

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

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

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

總結(jié)

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