Reddit如何實現大規模的帖子瀏覽計數,reddit算法

Reddit是如何實現大規模的帖子瀏覽計數的

瀏覽計數有四個主要要求，滿足這四個要求比聽起來要復雜得多。

克里希南·錢德拉

我們希望更好地向我們的用戶傳達Reddit的規模。到目前為止，投票分數和評論數是一個具體帖子活動的主要指標。然而，Reddit有許多訪問者在沒有投票或評論的情況下閱讀內容。我們希望建立一個系統，可以捕捉閱讀的帖子數量。然后把這個量展示給內容創作者和版主，讓他們更好地了解具體帖子上的活動。

在本文中，我們將討論如何實現大規模計數。

計數方法

瀏覽計數有四個主要要求:

計數必須是實時或接近實時的。而不是每天或每小時的總數。

每個用戶在短時間內只能計數一次。

顯示的數量和實際數量之間的誤差在百分之幾。

系統必須能夠在生產環境中運行，并在事件發生后幾秒鐘內處理事件。

滿足這四個要求比聽起來要復雜得多。為了實時保持準確的計數，我們需要知道特定的用戶是否曾經訪問過這個帖子。為了了解這些信息，我們需要存儲以前訪問過每個帖子的用戶組，然后在每次處理對該帖子的新訪問時檢查這個用戶組。這個解決方案的一個原始實現是將這個唯一的用戶集合作為哈希表存儲在內存中，并將帖子ID作為鍵名。

這種方法適用于瀏覽量較少的文章，但一旦文章流行起來，讀者數量迅速增加，這種方法就很難推廣。有幾個受歡迎的帖子擁有超過一百萬的獨立讀者對于這種帖子來說，對內存和CPU的影響很大，因為所有的id都要存儲起來，要經常搜索收藏，看看有沒有人訪問過。

由于我們無法提供準確的計數，我們研究了幾種不同的基數估計[1]算法。我們考慮了兩個非常符合我們預期的選項:

☉線性概率計數法，這種方法非常精確，但是要計數的集合越大，線性需要的內存就越多。

基于超對數的☉計數方法[2](HLL)。HLL隨著設定的大小而增長，但它不能提供與線性計數器相同的精度。

要想知道HLL到底節省了多少空間，看看本文頂部的r/pics帖子。它擁有超過一百萬的獨立用戶。如果我們存儲100萬個唯一用戶ID，每個用戶ID的長度為8個字節，那么我們需要8兆的內存來計算一篇帖子的唯一用戶數相比之下，使用HLL計數將占用更少的內存。每個實現中的內存量是不同的，但是對于這個實現[3]，我們可以僅使用12千字節的空間來計算超過一百萬個id，這將是原始空間使用量的0.15%

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

許多HLL實現使用上述兩種方法的組合，也就是說，從小集合的線性計數開始，一旦大小達到特定點就切換到HLL。前者通常被稱為“稀疏”的HLL表達式，而后者被稱為“密集”的HLL表達式。混合方法非常有利，因為它可以提供準確的結果，同時保持適度的內存占用。這個方法在Google的HyperLogLog++論文中有更詳細的描述[5]。

盡管HLL算法是相當標準的，我們考慮在我們的實現中使用三種變體。請注意，對于內存HLL實現，我們只關注Java和Scala實現，因為我們在數據工程團隊主要使用Java和Scala。

☉Twitter的☉·阿爾吉伯德圖書館，用Scala實現。Algebird有很好的文檔，但是稀疏和密集HLL表達式的實現細節不容易理解。

☉hyperlog log ++在streamlib中的實現，用Java實現。streamlib中的代碼有很好的文檔記錄，但要理解如何正確使用這個庫并調整它以滿足我們的需求有些困難。

☉Redis(我們選擇的)的☉ HLL實現。我們相信Redis的HLL實現是有據可查的，并且易于配置，所提供的與HLL相關的API也易于集成。作為一個額外的好處，使用Redis通過將計數應用程序(HLL計算)的CPU和內存密集型部分轉移到專用服務器上，緩解了我們的許多性能問題。

Reddit的數據管道主要圍繞阿帕奇卡夫卡[6]。當用戶查看帖子時，事件被觸發并發國際快遞事件收集器服務器，該服務器批量處理事件并將其保存到Kafka。

從這里開始，瀏覽計數系統有兩個按順序運行的組件。我們計數架構的第一部分是一個叫Nazar[7]的Kafka消費者，他會從Kafka讀取每一個事件，并通過我們編制的一套規則來決定一個事件是否應該被計數。我們給它起這個名字是因為納扎爾是保護你遠離邪惡的眼睛護身符，納扎爾系統是可以保護我們遠離不良因素的“眼睛”。Nazar使用Redis來保持狀態，并跟蹤瀏覽不應被計算的潛在原因。我們可能無法統計事件的一個原因是同一用戶在短時間內重復瀏覽的結果。Nazar隨后會更改事件，添加一個布爾標志來指示是否應該計數，然后發回Kafka事件。

這是這個項目的第二部分。我們有第二個Kafka消費者，叫做Abacus[8]，它實際上是對瀏覽進行計數，并使計數在網站和客戶端上可見。Abacus讀取Nazar輸出的卡夫卡事件。然后，根據Nazar的決定，它將計算或跳過這一瀏覽。如果事件被標記為計數，Abacus首先檢查Redis中是否有HLL計數器已經有與事件對應的帖子。如果計數器已經在Redis中，那么Abacus向Redis發快遞PFADD[9]請求。如果計數器不在Redis中，那么Abacus向Cassandra cluster發快遞一個請求。我們使用這個集群來保存HLL計數器和原始計數，并向Redis發快遞一個SET[10]請求來添加一個過濾器。這通常發生在人們查看被Redis刪除的舊帖子時。

為了維護Redis中可能被刪除的舊帖子，Abacus會定期將Redis的完整HLL過濾器和每個帖子的計數記錄到Cassandra cluster中。卡珊德拉以10秒為一批進行寫作，以避免超載。以下是高級事件流程圖。

特別聲明：以上文章內容僅代表作者本人觀點，不代表ESG跨境電商觀點或立場。如有關于作品內容、版權或其它問題請于作品發表后的30日內與ESG跨境電商聯系。