Reddit 如何統(tǒng)計每個帖子的瀏覽量,reddit如何統(tǒng)計每個帖子的瀏覽量

Reddit如何統(tǒng)計每個帖子的瀏覽量

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

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

在這篇博客中，我們將討論如何實現(xiàn)對海量數(shù)據(jù)的計數(shù)。

計算機

我們對計數(shù)系統(tǒng)有四個主要要求:

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

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

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

Reddit是全球訪問量第八大的網(wǎng)站，所以系統(tǒng)應(yīng)該能在生產(chǎn)環(huán)境的規(guī)模上正常運行，只允許有幾秒鐘的延遲。

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

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

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

一種是線性概率計數(shù)法，這種方法非常精確，但是當(dāng)計數(shù)集變大時，所需內(nèi)存會線性變大。

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

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

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

HLL的許多實現(xiàn)結(jié)合了上述兩種算法。當(dāng)集合規(guī)模較小時，采用線性計數(shù)，當(dāng)集合規(guī)模達(dá)到一定閾值時，切換到HLL。前者通常被稱為“稀疏的)HLL，而后者被稱為“稠密的)HLL。這種結(jié)合了兩種算法的實現(xiàn)具有很大的優(yōu)勢，因為它既能保證小集合的準(zhǔn)確性，又能保證大集合的準(zhǔn)確性，同時還能保證適度的內(nèi)存增長。你可以在google的這篇論文中了解到這個實現(xiàn)的細(xì)節(jié)。

論文鏈接

https://antirez.com/news/75

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

Twitter提供的Algebird是Scala實現(xiàn)的。Algebird有很好的文檔，但是他們不容易理解稀疏和密集HLL的實現(xiàn)細(xì)節(jié)。

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

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

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

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

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

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

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

摘要

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

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