首頁 > 綜合 > 正文

天天新消息丨布隆過濾器在短視頻 feeds 系統(tǒng)中的妙用

2023-03-12 03:12:47來源:騰訊云  

大家平時刷抖音、視頻號、快手時,幾乎總能刷到最新的視頻。那這里是怎么實現(xiàn)的呢?


【資料圖】

上述場景,可以簡單抽象為曝光去重,就是用戶看過的 feeds1、feeds2、feeds3 ...... 等,如何保證在用戶下次進入系統(tǒng)時不會再次出現(xiàn)呢?今天,我們就來探討下幾種實現(xiàn)方案吧。

方案一 :Set

這個方案簡單粗暴,就是每個用戶用一個集合,存儲看過的所有 feedsid。每次推薦系統(tǒng)要出新的 feeds 時,去 set 中 check 一下是否存在,如果存在的話,就過濾掉這條 feeds。

一般來說,像是短視頻推薦的場景下,對 feeds 的實時性要求相對較高,一般會使用 Redis 作為曝光打擊的載體。

不了解 Redis Set 的同學可以參考下:https://redis.io/commands/set/,簡而言之就是一個字典。

這種方案的問題是,在海量用戶的場景下,1是成本會很高(像 Redis 是純內(nèi)存數(shù)據(jù)庫);2是隨著 feeds 數(shù)量越來越多,set 查詢會隨之變慢(像短視頻的場景下,1晚上刷個上百條還是不成問題的)。

我們來簡單試算一下,假設國民級 App 的日活躍用戶在 3kw,每人每天平均刷 200 條視頻 feeds,每條 feeds 的 id 長度為 32B。

如果以 Redis Set 的方案來計算:3kw * 200 * 32 * 1.5(Redis 數(shù)據(jù)結構自身存儲) ~ 288G,每天需要消耗存儲 288G,1個月呢?8.6T,1年呢?103T。以騰訊云 keewiDB 的持久內(nèi)存來估計 64元/GB/月,1月成本大約 55w,有錢也不能這么造啊。

那有沒有更優(yōu)惠的實現(xiàn)方案呢?這就要說到本文的主角,布隆過濾器了。

方案二:Bloom Filter

布隆過濾器,本質(zhì)上是一個高階 Bitmap,最適合的場景就是海量數(shù)據(jù)的過濾了。

不了解 Bitmap 的同學可以參考 https://www.cnblogs.com/dragonsuc/p/10993938.html。

布隆過濾器介紹

布隆過濾器的結構如下圖示:

bloom filter

簡單說下它的使用:

1. 寫入:對數(shù)據(jù) data 進行 k 次 hash 運算(hash 函數(shù)可選擇,本文不具體較少),得到結果后,對 bit 數(shù)組相應位置置1。

2. 檢查:對數(shù)據(jù) data 同樣進行 k 次 hash 運算,得到結果后,檢測 bloom bit 數(shù)組中相應位置是否全為1,如全是1,則表示該 data 存在于 bloom 中;否則,表示該數(shù)據(jù)不在 bloom 中。

結合上述描述,我們可以得出如下結論:

1. bloom 中存的摘要,而不是原始數(shù)據(jù) data,所以空間占用遠遠低于 set 的占用。

2. bloom 無法刪除數(shù)據(jù),如上圖示 x、y 都對 bit 數(shù)組中 bits[2] 置1了,如果刪除 x,則 bits[2]為0,y判定時,也判定失敗了。

3. bloom 無法動態(tài)擴展大小,如上圖示,bit 數(shù)組是固定的,如果 bits 數(shù)組長度調(diào)整了,那么同樣的 x、y hash 后的 bits 索引也會發(fā)生變化。

4. bloom 存在誤判的可能,例如 x、y hash 后得到的 bits 數(shù)組索引都是 1、3、5,那么即使 bloom 中只添加了 x,當 y 來判定時,也會判定為存在。

誤判率計算公式

這里不細究它的推導過程了,感興趣的同學可以自行研究。

布隆過濾器實現(xiàn)曝光打擊

由上述布隆過濾器的特性所知:必須合理選擇 bloom 過濾器的規(guī)格,bloom bit 數(shù)組太小,則誤判率過高;bloom bit 數(shù)組太大,則過于浪費存儲。

還是以相同的條件來試算,

假設國民級 App 的日活躍用戶在 3kw,每人每天平均刷 200 條視頻 feeds,每條 feeds 的 id 長度為 32B。

如果以 Redis bloom 的方案來計算:400B * 3kw ~ 12G,相比 set 方案的 288G,節(jié)約了 96% 的存儲成本。1月可以節(jié)約 52.8w 成本,降本增效杠杠的。

當設置 bloom 容量為 200 時,每人每天1個key,可以保證當天看到不重復的 feeds,BF 規(guī)格如下:

采用 Redis Bloom 插件計算,https://redis.io/docs/stack/bloom/。

bloom filter 規(guī)格

進一步優(yōu)化

上述場景下,Bloom 大小按照 200 計算,那活躍用戶呢?總有一些高活用戶,每天會刷大幾百條視頻,這部分用戶不做特殊處理的話,體驗會非常差,后面總是看到重復的視頻。還有就是一些特殊場景,例如業(yè)務希望用戶1月內(nèi)都不要看到重復的 feeds。這種,如果僅僅以每天每人作為 bloom 的 key,那么實現(xiàn)1個月內(nèi)不重復,1個用戶要查詢30個 bloom,有點夸張。

Redis 雖然能抗,但假設用戶刷視頻的頻率是 10w/s,擴散后,對 Redis 的壓力就是300w/s

怎么優(yōu)化呢?有幾種思路。

1. 最簡單,讓 Redis 抗,單機扛不住,分片還扛不住嗎?分片扛不住,讀寫分離還扛不住嗎?反正肯定能抗住。

2. 記錄1個總數(shù)量的 bloom key,分級,遞增設置容量。例如起始 bf0 容量是 1000,當 bf0 滿了,新建一個 bf1,容量是 10000,bf1 滿了,再新建一個 bf2,容量是 10w。這種方案有兩個好處,1是遞進的增加 bf 容量,減少 Redis 的 key 訪問次數(shù),減輕 Redis 的壓力;2是不浪費存儲,大部分用戶都是非活躍用戶,可能看到的 feeds 量在 1w 以內(nèi),只有真正活躍的用戶才會分配 10w 以上的大 bf,精準的占用存儲。

分級 BF

至此,本文就大體結束了,后面有時間了再開一篇布谷鳥過濾器的說明,先鴿一下。

標簽:

相關閱讀

精彩推薦

相關詞

推薦閱讀