Reddit 如何統計每個帖子的瀏覽量,reddit如何統計每個帖子的瀏覽量

Reddit如何統計每個帖子的瀏覽量

之前沒聽說過HyperLogLog，翻譯這篇文章也就學習這么簡單。歡迎來錯~

我們想更好地向用戶展示Reddit的規模。對于這一點，投票數和評論數是一個帖子最重要的指標。然而，Reddit上相當一部分用戶只是瀏覽內容，既沒有投票也沒有評論。所以我們想建立一個系統，可以計算一個帖子的瀏覽量。這個數字會顯示給帖子的創建者和版主，讓他們更好的了解一個帖子的活躍度。

在這篇博客中，我們將討論如何實現對海量數據的計數。

計算機

我們對計數系統有四個主要要求:

查看的帖子數量必須是實時或接近實時的，而不是每天或每小時。

同一用戶在短時間內多次訪問一個帖子，只計一次瀏覽量。

顯示的頁面瀏覽量和真實的頁面瀏覽量之間允許有多大的百分比誤差

Reddit是全球訪問量第八大的網站，所以系統應該能在生產環境的規模上正常運行，只允許有幾秒鐘的延遲。

滿足以上四個需求，遠比聽起來難。為了實時準確地統計，我們需要知道某個用戶是否曾經訪問過這個帖子。為了了解這些信息，我們必須為每個帖子維護一個訪問用戶集合，然后在每次計算頁面瀏覽量時檢查該集合。naive的實現是將訪問用戶的集合存儲在內存的hashMap中，以post Id作為鍵。

這種實現方式對于低流量的帖子是可行的，但是一旦某個帖子變得熱門，流量劇增時就很難控制了。甚至有些帖子的獨立訪客超過100萬對于這類帖子，存儲獨立訪問者的ID，頻繁查詢某個用戶之前是否訪問過，會對內存和CPU造成很大的負擔。

因為我們不能提供精確的計數，所以我們研究了幾種不同的基數估計算法。有兩個選項可以滿足我們的需求:

一種是線性概率計數法，這種方法非常精確，但是當計數集變大時，所需內存會線性變大。

第二種是基于超對數的計數方法(以下簡稱HLL)。HLL空間復雜度低，但其精度不如線性計數。

讓我們來看看HLL將節省多少內存。如果我們需要存儲100萬獨立訪問者的ID，每個用戶ID的長度為8個字節，那么我們需要8 M的內存來存儲一個帖子的獨立訪問者。相反，如果采用HLL，內存占用會顯著減少。HLL的不同實現消耗不同的內存。如果采用本文的實現方法，存儲100萬個id只需要12 KB，是原來的0.15%

大數據計數:如何僅用1.5 KB內存計數十億個不同的對象——高可擴展性——本文很好地總結了上述算法。

HLL的許多實現結合了上述兩種算法。當集合規模較小時，采用線性計數，當集合規模達到一定閾值時，切換到HLL。前者通常被稱為“稀疏的)HLL，而后者被稱為“稠密的)HLL。這種結合了兩種算法的實現具有很大的優勢，因為它既能保證小集合的準確性，又能保證大集合的準確性，同時還能保證適度的內存增長。你可以在google的這篇論文中了解到這個實現的細節。

論文鏈接

https://antirez.com/news/75

現在我們已經決定采用HLL算法，但是在選擇具體的實現方式時，我們考慮了以下三種不同的實現方式。因為我們的數據工程團隊用的是Java和Scala，所以我們只考慮Java和Scala的實現。

Twitter提供的Algebird是Scala實現的。Algebird有很好的文檔，但是他們不容易理解稀疏和密集HLL的實現細節。

streamlib中提供的HyperLogLog++是用Java實現的。streamlib中的代碼文檔是完整的，但其中一些很難理解如何正確使用它們并轉換它們以滿足我們的需求。

Redis HLL實施，這是我們最終的選擇。我們認為Redis中HLLs的實現文檔是完整的，易于配置，提供的相關API也易于集成。另一個優勢是，我們可以部署專用服務器，從而降低性能壓力。

Reddit的數據管道依賴于卡夫卡。當用戶訪問一個博客時，會觸發一個事件，該事件會被發國際快遞事件收集服務器，并在Kafka中持久化。

之后，計數系統將依次運行這兩個組件。在我們的計數系統架構中，第一部分是一個Kafka消費者，我們稱之為Nazar。Nazar會從Kafka讀取每一個事件，它會通過一系列配置好的規則來判斷事件是否需要計數。我們取這個名字只是因為Nazar是一個眼睛形狀的護身符，而“Nazar”系統就像眼睛一樣，讓我們的計數系統遠離惡意者的破壞。我們不統計一次事件的原因之一是同一用戶短時間內重復訪問。Nazar將修改事件，添加一個布爾標志，指示是否應該計數，并將事件放回Kafka。

系統的第二部分來了。我們稱之為第二個卡夫卡消費算盤，用于計算真實瀏覽量，并將計算結果顯示在網站或客戶端。Abacus從Kafka讀取Nazar處理的事件，根據Nazar的處理結果決定是跳過這個事件還是加入計數。如果在Nazar中處理的結果是您可以加入計數，那么Abacus將首先檢查與該事件相關聯的帖子是否已經在Redis中有HLL計數器。如果已經存在，Abacus將向Redis發快遞PFADD請求。如果不存在，那么Abacus將向Cassandra cluster (Cassandra用于持久化HLL計數器和計數值)發快遞一個請求，然后向Redis發快遞一個SET請求。這通常發生在當一個網民訪問一個舊帖子時，此時該帖子的計數器可能已經在Redis中過期。

為了存儲Redis中存儲的計數器過期的舊帖子的頁面視圖。Abacus會定期將Redis中每個帖子的所有HLL和頁面瀏覽量寫入Cassandra cluster。為了避免集群過載，我們以10秒為周期批量寫入。

下圖顯示了事件流的一般流程:

摘要

我們希望瀏覽量可以讓發帖人知道帖子的所有訪問量，也可以幫助版主快速定位自己社區中訪問量高的帖子。未來，我們計劃利用我們數據管道的實時潛力，為Reddit用戶提供更多有用的反饋。

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