首頁 > 綜合 > 正文

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

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

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

【資料圖】

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

方案一：Set

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

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

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

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

我們來簡單試算一下，假設(shè)國民級 App 的日活躍用戶在 3kw，每人每天平均刷 200 條視頻 feeds，每條 feeds 的 id 長度為 32B。
如果以 Redis Set 的方案來計算：3kw * 200 * 32 * 1.5(Redis 數(shù)據(jù)結(jié)構(gòu)自身存儲) ~ 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 的同學(xué)可以參考 https://www.cnblogs.com/dragonsuc/p/10993938.html。

布隆過濾器介紹

布隆過濾器的結(jié)構(gòu)如下圖示：

bloom filter

簡單說下它的使用：

1. 寫入：對數(shù)據(jù) data 進(jìn)行 k 次 hash 運(yùn)算(hash 函數(shù)可選擇，本文不具體較少)，得到結(jié)果后，對 bit 數(shù)組相應(yīng)位置置1。

2. 檢查：對數(shù)據(jù) data 同樣進(jìn)行 k 次 hash 運(yùn)算，得到結(jié)果后，檢測 bloom bit 數(shù)組中相應(yīng)位置是否全為1，如全是1，則表示該 data 存在于 bloom 中；否則，表示該數(shù)據(jù)不在 bloom 中。

結(jié)合上述描述，我們可以得出如下結(jié)論：

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

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

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

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

誤判率計算公式

這里不細(xì)究它的推導(dǎo)過程了，感興趣的同學(xué)可以自行研究。

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

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

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

假設(shè)國民級 App 的日活躍用戶在 3kw，每人每天平均刷 200 條視頻 feeds，每條 feeds 的 id 長度為 32B。
如果以 Redis bloom 的方案來計算：400B * 3kw ~ 12G，相比 set 方案的 288G，節(jié)約了 96% 的存儲成本。1月可以節(jié)約 52.8w 成本，降本增效杠杠的。

當(dāng)設(shè)置 bloom 容量為 200 時，每人每天1個key，可以保證當(dāng)天看到不重復(fù)的 feeds，BF 規(guī)格如下：

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

bloom filter 規(guī)格

進(jìn)一步優(yōu)化

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

Redis 雖然能抗，但假設(shè)用戶刷視頻的頻率是 10w/s，擴(kuò)散后，對 Redis 的壓力就是300w/s

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

1. 最簡單，讓 Redis 抗，單機(jī)扛不住，分片還扛不住嗎？分片扛不住，讀寫分離還扛不住嗎？反正肯定能抗住。

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

分級 BF

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

標(biāo)簽：