Reddit如何實現(xiàn)大規(guī)模的帖子瀏覽計數(shù)

對瀏覽計數(shù)有四個主要要求，滿足這四項要求比聽起來要復(fù)雜得多。

-- Krishnan Chandra

我們希望更好地將 Reddit 的規(guī)模傳達(dá)給我們的用戶。到目前為止，投票得分和評論數(shù)量是特定的帖子活動的主要指標(biāo)。然而，Reddit 有許多訪問者在沒有投票或評論的情況下閱讀內(nèi)容。我們希望建立一個能夠捕捉到帖子閱讀數(shù)量的系統(tǒng)。然后將該數(shù)量展示給內(nèi)容創(chuàng)建者和版主，以便他們更好地了解特定帖子上的活動。

在這篇文章中，我們將討論我們?nèi)绾未笠?guī)模地實現(xiàn)計數(shù)。

計數(shù)方法

對瀏覽計數(shù)有四個主要要求：

? 計數(shù)必須是實時的或接近實時的。不是每天或每小時的總量。

? 每個用戶在短時間內(nèi)只能計數(shù)一次。

? 顯示的數(shù)量與實際的誤差在百分之幾。

? 系統(tǒng)必須能夠在生產(chǎn)環(huán)境運行，并在事件發(fā)生后幾秒內(nèi)處理事件。

滿足這四項要求比聽起來要復(fù)雜得多。為了實時保持準(zhǔn)確的計數(shù)，我們需要知道某個特定的用戶是否曾經(jīng)訪問過這個帖子。要知道這些信息，我們需要存儲先前訪問過每個帖子的用戶組，然后在每次處理對該帖子的新訪問時查看該組。這個解決方案的一個原始實現(xiàn)是將這個唯一用戶的集合作為散列表存儲在內(nèi)存中，并且以帖子 ID 作為鍵名。

這種方法適用于瀏覽量較少的文章，但一旦文章流行，閱讀人數(shù)迅速增加，這種方法很難擴展。有幾個熱門的帖子有超過一百萬的唯一讀者！對于這種帖子，對于內(nèi)存和 CPU 來說影響都很大，因為要存儲所有的 ID，并頻繁地查找集合，看看是否有人已經(jīng)訪問過。

由于我們不能提供精確的計數(shù)，我們研究了幾個不同的基數(shù)估計[1]算法。我們考慮了兩個非常符合我們期望的選擇：

☉ 線性概率計數(shù)方法，非常準(zhǔn)確，但要計數(shù)的集合越大，則線性地需要更多的內(nèi)存。

☉ 基于 HyperLogLog[2]（HLL）的計數(shù)方法。HLL 隨集合大小增長，但不能提供與線性計數(shù)器相同的準(zhǔn)確度。

要了解 HLL 真正節(jié)省的空間大小，看一下這篇文章頂部包括的 r/pics 帖子。它有超過 100 萬的唯一用戶。如果我們存儲 100 萬個唯一用戶 ID，并且每個用戶 ID 是 8 個字節(jié)長，那么我們需要 8 兆內(nèi)存來計算單個帖子的唯一用戶數(shù)！相比之下，使用 HLL 進(jìn)行計數(shù)會占用更少的內(nèi)存。每個實現(xiàn)的內(nèi)存量是不一樣的，但是對于這個實現(xiàn)[3]，我們可以使用僅僅 12 千字節(jié)的空間計算超過一百萬個 ID，這將是原始空間使用量的 0.15％！

（這篇關(guān)于高可伸縮性的文章[4]很好地概述了上述兩種算法。）

許多 HLL 實現(xiàn)使用了上述兩種方法的組合，即對于小集合以線性計數(shù)開始，并且一旦大小達(dá)到特定點就切換到 HLL。前者通常被稱為 “稀疏” HLL 表達(dá)，而后者被稱為“密集” HLL 表達(dá)。混合的方法是非常有利的，因為它可以提供準(zhǔn)確的結(jié)果，同時保留適度的內(nèi)存占用量。這個方法在 Google 的 HyperLogLog++ 論文[5]中有更詳細(xì)的描述。

雖然 HLL 算法是相當(dāng)標(biāo)準(zhǔn)的，但在我們的實現(xiàn)中我們考慮使用三種變體。請注意，對于內(nèi)存中的 HLL 實現(xiàn)，我們只關(guān)注 Java 和 Scala 實現(xiàn)，因為我們主要在數(shù)據(jù)工程團(tuán)隊中使用 Java 和 Scala。

☉ Twitter 的 Algebird 庫，用 Scala 實現(xiàn)。Algebird 有很好的使用文檔，但是稀疏和密集的 HLL 表達(dá)的實現(xiàn)細(xì)節(jié)不容易理解。

☉ 在 stream-lib 中的 HyperLogLog++ 的實現(xiàn)，用 Java 實現(xiàn)。stream-lib 中的代碼有很好的文檔，但是要理解如何正確使用這個庫并且調(diào)整它以滿足我們的需求是有些困難的。

☉ Redis 的 HLL 實現(xiàn)（我們選擇的）。我們認(rèn)為，Redis 的 HLL 實施方案有很好的文檔并且易于配置，所提供的 HLL 相關(guān)的 API 易于集成。作為一個額外的好處，使用 Redis 通過將計數(shù)應(yīng)用程序（HLL 計算）的 CPU 和內(nèi)存密集型部分移出并將其移至專用服務(wù)器上，從而緩解了我們的許多性能問題。

Reddit 的數(shù)據(jù)管道主要圍繞 Apache Kafka[6]。當(dāng)用戶查看帖子時，事件被激發(fā)并發(fā)送到事件收集器服務(wù)器，該服務(wù)器批量處理事件并將其保存到 Kafka 中。

從這里，瀏覽計數(shù)系統(tǒng)有兩個按順序運行的組件。我們的計數(shù)架構(gòu)的第一部分是一個名為 Nazar[7] 的 Kafka 消費者，它將讀取來自 Kafka 的每個事件，并通過我們編制的一組規(guī)則來確定是否應(yīng)該計算一個事件。我們給它起了這個名字是因為 Nazar 是一個保護(hù)你免受邪惡的眼形護(hù)身符，Nazar 系統(tǒng)是一個“眼睛”，它可以保護(hù)我們免受不良因素的影響。Nazar 使用 Redis 保持狀態(tài)，并跟蹤不應(yīng)計算瀏覽的潛在原因。我們可能無法統(tǒng)計事件的一個原因是，由于同一用戶在短時間內(nèi)重復(fù)瀏覽的結(jié)果。Nazar 接著將改變事件，添加一個布爾標(biāo)志表明是否應(yīng)該被計數(shù)，然后再發(fā)回 Kafka 事件。

這是這個項目要說的第二部分。我們有第二個叫做 Abacus[8] 的 Kafka 消費者，它實際上對瀏覽進(jìn)行計數(shù)，并使計數(shù)在網(wǎng)站和客戶端可見。Abacus 讀取 Nazar 輸出的 Kafka 事件。接著，根據(jù) Nazar 的決定，它將計算或跳過本次瀏覽。如果事件被標(biāo)記為計數(shù)，那么 Abacus 首先檢查 Redis 中是否存在已經(jīng)存在與事件對應(yīng)的帖子的 HLL 計數(shù)器。如果計數(shù)器已經(jīng)在 Redis 中，那么 Abacus 向 Redis 發(fā)出一個 PFADD[9] 的請求。如果計數(shù)器還沒有在 Redis 中，那么 Abacus 向 Cassandra 集群發(fā)出請求，我們用這個集群來持久化 HLL 計數(shù)器和原始計數(shù)，并向 Redis 發(fā)出一個 SET[10] 請求來添加過濾器。這種情況通常發(fā)生在人們查看已經(jīng)被 Redis 刪除的舊帖的時候。

為了保持對可能從 Redis 刪除的舊帖子的維護(hù)，Abacus 定期將 Redis 的完整 HLL 過濾器以及每個帖子的計數(shù)記錄到 Cassandra 集群中。 Cassandra 的寫入以 10 秒一組分批寫入，以避免超載。下面是一個高層的事件流程圖。