Reddit如何實現(xiàn)大規(guī)模的帖子瀏覽計數(shù),reddit算法-ESG跨境

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

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

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

克里希南·錢德拉

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

在本文中，我們將討論如何實現(xiàn)大規(guī)模計數(shù)。

計數(shù)方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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