我們想要更好地向用戶展示 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 造成很大的負擔。

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

• 一是線性概率計數(shù)法，很準確，但當計數(shù)集合變大時所需內(nèi)存會線性變大。
• 二是基于 HyperLogLog (以下簡稱 HLL )的計數(shù)法。 HLL 空間復雜度較低，但是精確度不如線性計數(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)存增長。

現(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 也很容易集成。還有一個好處是，我們可以用一臺專門的服務器部署，從而減輕性能上的壓力。

Reddit 的數(shù)據(jù)管道依賴于 Kafka。當一個用戶訪問了一篇博客，會觸發(fā)一個事件，事件會被發(fā)送到事件收集服務器，并被持久化在 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)重復訪問。Nazar 會修改事件，加上個標明是否應該被計數(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 的用戶提供更多的有用的反饋。