Reddit 如何統(tǒng)計(jì)每個(gè)帖子的瀏覽量,reddit如何統(tǒng)計(jì)每個(gè)帖子的瀏覽量-ESG跨境

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

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

之前沒(méi)聽(tīng)說(shuō)過(guò)HyperLogLog，翻譯這篇文章也就學(xué)習(xí)這么簡(jiǎn)單。歡迎來(lái)錯(cuò)~

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

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

計(jì)算機(jī)

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

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

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

顯示的頁(yè)面瀏覽量和真實(shí)的頁(yè)面瀏覽量之間允許有多大的百分比誤差

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

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

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

因?yàn)槲覀儾荒芴峁┚_的計(jì)數(shù)，所以我們研究了幾種不同的基數(shù)估計(jì)算法。有兩個(gè)選項(xiàng)可以滿足我們的需求:

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

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

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

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

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

論文鏈接

https://antirez.com/news/75

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

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

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

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

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

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

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

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

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

摘要

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

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