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

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

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

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

克里希南·錢德拉

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

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

計(jì)數(shù)方法

瀏覽計(jì)數(shù)有四個(gè)主要要求:

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

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

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

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

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

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

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

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

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

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

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

許多HLL實(shí)現(xiàn)使用上述兩種方法的組合，也就是說，從小集合的線性計(jì)數(shù)開始，一旦大小達(dá)到特定點(diǎn)就切換到HLL。前者通常被稱為“稀疏”的HLL表達(dá)式，而后者被稱為“密集”的HLL表達(dá)式?；旌戏椒ǚ浅Ｓ欣?yàn)樗梢蕴峁?zhǔn)確的結(jié)果，同時(shí)保持適度的內(nèi)存占用。這個(gè)方法在Google的HyperLogLog++論文中有更詳細(xì)的描述[5]。

盡管HLL算法是相當(dāng)標(biāo)準(zhǔn)的，我們考慮在我們的實(shí)現(xiàn)中使用三種變體。請(qǐng)注意，對(duì)于內(nèi)存HLL實(shí)現(xiàn)，我們只關(guān)注Java和Scala實(shí)現(xiàn)，因?yàn)槲覀冊(cè)跀?shù)據(jù)工程團(tuán)隊(duì)主要使用Java和Scala。

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

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

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

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

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

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

為了維護(hù)Redis中可能被刪除的舊帖子，Abacus會(huì)定期將Redis的完整HLL過濾器和每個(gè)帖子的計(jì)數(shù)記錄到Cassandra cluster中?？ㄉ旱吕?0秒為一批進(jìn)行寫作，以避免超載。以下是高級(jí)事件流程圖。

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