我們想要更好的向用戶展示 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í)施計(jì)數(shù)。
計(jì)數(shù)方法
對(duì)于計(jì)數(shù)我們主要有四種需求：
計(jì)數(shù)必須是實(shí)時(shí)的或接近實(shí)時(shí)的，而不是每天或每小時(shí)匯總。
每個(gè)用戶在短時(shí)間內(nèi)多次訪問(wèn)，只能計(jì)算一次
顯示的瀏覽量與真實(shí)瀏覽量間的誤差允許在幾個(gè)百分點(diǎn)內(nèi)
系統(tǒng)要能在生產(chǎn)環(huán)境的規(guī)模上正常運(yùn)行，在幾秒鐘內(nèi)處理發(fā)生的事件
滿足所有這四個(gè)要求比聽(tīng)起來(lái)更棘手。為了保持實(shí)時(shí)精確計(jì)數(shù)，我們需要知道特定用戶是否曾訪問(wèn)過(guò)該帖子。要了解這些信息，我們需要存儲(chǔ)先前訪問(wèn)過(guò)每個(gè)帖子的用戶集合，然后在每次查看帖子時(shí)檢查該集合。一個(gè)天真的實(shí)現(xiàn)方式就是將唯一的用戶集作為散列表存儲(chǔ)在內(nèi)存中，以帖子 ID 為 key。
這種實(shí)現(xiàn)方式對(duì)于訪問(wèn)量低的帖子是可行的，但一旦一個(gè)帖子變得流行，訪問(wèn)量劇增時(shí)就很難控制了。有的帖子甚至有超過(guò) 100 萬(wàn)的獨(dú)立訪客！ 對(duì)于這樣的帖子，存儲(chǔ)獨(dú)立訪客的 ID 并且頻繁查詢某個(gè)用戶是否之前曾訪問(wèn)過(guò)會(huì)給內(nèi)存和 CPU 造成很大的負(fù)擔(dān)。
由于我們無(wú)法提供確切的數(shù)據(jù)，我們研究了幾種不同的基數(shù)估計(jì)算法。有兩個(gè)符合我們需求的選項(xiàng)：
線性概率計(jì)數(shù)方法是非常準(zhǔn)確的，但是隨著被計(jì)數(shù)的集合的增加，所需內(nèi)存會(huì)線性變大。
基于 HyperLogLog（簡(jiǎn)稱 HLL）的計(jì)數(shù)方法。HLLs 隨著設(shè)置大小而呈線性增長(zhǎng)，但是精確度不如線性計(jì)數(shù)。
了解 HLLs 會(huì)節(jié)省多少內(nèi)存。如果我們不得不存儲(chǔ) 100 萬(wàn)個(gè)唯一的用戶 ID，并且每個(gè)用戶 ID 是一個(gè)8字節(jié)的長(zhǎng)度，那么我們將需要 8M 的內(nèi)存來(lái)計(jì)算單個(gè)帖子的唯一用戶數(shù)！相比之下，使用 HLL 進(jìn)行計(jì)數(shù)將占用較少的內(nèi)存。不同的 HLL 實(shí)現(xiàn)方式消耗的內(nèi)存不同。但是在這種實(shí)現(xiàn)的情況下，存儲(chǔ)超過(guò) 100 萬(wàn)個(gè) ID 僅需 12 KB，是原來(lái)的 0.15%！
Big Data Counting: How to count a billion distinct objects using only 1.5KB of Memory 這篇文章對(duì)上述兩種算法都有很好的概述。
許多 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)。這種方法更詳細(xì)地描述參看 Google 論文。
現(xiàn)在我們已經(jīng)確定要采用 HLL 算法了，不過(guò)在選擇具體的實(shí)現(xiàn)時(shí)，我們考慮了以下三種不同的實(shí)現(xiàn)。因?yàn)槲覀兊臄?shù)據(jù)工程團(tuán)隊(duì)使用 Java 和 Scala，所以我們只考慮 Java 和 Scala 的實(shí)現(xiàn)。
Twitter’s Algebird library, implemented in Scala。Algebird 有很好的文檔，但對(duì)于 sparse 和 dense HLL 的實(shí)現(xiàn)細(xì)節(jié)不是很容易理解。
An implementation of HyperLogLog++ located in stream-lib, implemented in Java。stream-lib 中的代碼有很好的文檔，但是很難理解如何正確使用庫(kù)并根據(jù)需要進(jìn)行調(diào)整。
Redis’s HLL implementation (which we chose)。我們認(rèn)為 Redis HLLs 的實(shí)施文檔很好、容易配置，提供的相關(guān) API 也很容易整合。作為一個(gè)額外的好處，使用 Redis 可以將計(jì)數(shù)應(yīng)用程序的 CPU 和內(nèi)存密集型部分（HLL計(jì)算）移動(dòng)到專用服務(wù)器上，從而緩解了許多性能問(wèn)題。
Reddit 的數(shù)據(jù)管道依賴于 Apache Kafka。當(dāng)用戶查看帖子時(shí)，事件將被觸發(fā)并發(fā)送到事件收集服務(wù)器，該服務(wù)器將事件分批并將其持久化在 Kafka 中。
之后，計(jì)數(shù)系統(tǒng)會(huì)按順序依次運(yùn)行兩個(gè)組件。我們的計(jì)數(shù)架構(gòu)的第一部分是一個(gè)稱之為 Nazar 的 Kafka 的消費(fèi)者。Nazar 將從 Kafka 中讀取每個(gè)事件，并通過(guò)一系列配置規(guī)則來(lái)判斷該事件是否需要被計(jì)數(shù)。Nazar 使用 Redis 維持狀態(tài)，并跟蹤不應(yīng)該被計(jì)數(shù)的潛在原因。其中一個(gè)我們不將一個(gè)事件計(jì)數(shù)在內(nèi)的原因就是同一個(gè)用戶在很短時(shí)間內(nèi)重復(fù)訪問(wèn)。在將事件發(fā)送回 Kafka 之前，Nazar 會(huì)更改事件，并添加一個(gè)布爾標(biāo)志，表示是否應(yīng)該計(jì)數(shù)。
下面就是系統(tǒng)的第二部分。我們將第二個(gè) Kafka 的消費(fèi)者稱為 Abacus，用來(lái)進(jìn)行真正的計(jì)數(shù)，并將計(jì)算結(jié)果顯示在網(wǎng)站或客戶端。Abacus 從 Kafka 中讀取經(jīng)過(guò) Nazar 處理過(guò)的事件，并根據(jù) Nazar 的處理結(jié)果決定是跳過(guò)這個(gè)事件還是將其加入計(jì)數(shù)。如果事件被標(biāo)記為計(jì)數(shù)，則 Abacus 首先檢查 Redis 中是否存在與事件相對(duì)應(yīng)的帖子的 HLL 計(jì)數(shù)器。如果已經(jīng)存在，Abacus 會(huì)給 Redis 發(fā)送一個(gè) PFADD 請(qǐng)求。如果不存在，那么 Abacus 會(huì)給 Cassandra 集群（用來(lái)持久化 HLL 計(jì)數(shù)器和計(jì)數(shù)值）發(fā)送一個(gè)請(qǐng)求，然后再向 Redis 發(fā)送請(qǐng)求。這通常發(fā)生在人們?cè)L問(wèn)較老帖子的時(shí)候，這時(shí)該帖子的計(jì)數(shù)器很可能已經(jīng)在 Redis 中過(guò)期了。
為了維護(hù) Redis 中計(jì)數(shù)器過(guò)期的老帖子的計(jì)數(shù)，Abacus 會(huì)定期向 Redis 發(fā)出完整的 HLL 計(jì)數(shù)器以及每個(gè)帖子的計(jì)數(shù)到 Cassandra 集群。為了避免集群過(guò)載，我們以 10 秒為周期批量寫(xiě)入。
事件流程圖：
總結(jié)
我們希望瀏覽量可以讓發(fā)帖者了解帖子全部的訪問(wèn)量，也幫助版主快速定位自己社區(qū)中高訪問(wèn)量的帖子。在未來(lái)，我們計(jì)劃利用數(shù)據(jù)管道在實(shí)時(shí)方面的潛力來(lái)為 Reddit 的用戶提供更多的有用的反饋。
