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

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

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

【資料圖】

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

方案一：Set

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

一般來說，像是短視頻推薦的場(chǎng)景下，對(duì) feeds 的實(shí)時(shí)性要求相對(duì)較高，一般會(huì)使用 Redis 作為曝光打擊的載體。

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

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

我們來簡(jiǎn)單試算一下，假設(shè)國民級(jí) App 的日活躍用戶在 3kw，每人每天平均刷 200 條視頻 feeds，每條 feeds 的 id 長(zhǎng)度為 32B。
如果以 Redis Set 的方案來計(jì)算：3kw * 200 * 32 * 1.5(Redis 數(shù)據(jù)結(jié)構(gòu)自身存儲(chǔ)) ~ 288G，每天需要消耗存儲(chǔ) 288G，1個(gè)月呢？8.6T，1年呢？103T。以騰訊云 keewiDB 的持久內(nèi)存來估計(jì) 64元/GB/月，1月成本大約 55w，有錢也不能這么造啊。

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

方案二：Bloom Filter

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

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

布隆過濾器介紹

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

bloom filter

簡(jiǎn)單說下它的使用：

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

2. 檢查：對(duì)數(shù)據(jù) data 同樣進(jìn)行 k 次 hash 運(yùn)算，得到結(jié)果后，檢測(cè) 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 都對(duì) bit 數(shù)組中 bits[2] 置1了，如果刪除 x，則 bits[2]為0，y判定時(shí)，也判定失敗了。

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

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

誤判率計(jì)算公式

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

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

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

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

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

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

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

bloom filter 規(guī)格

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

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

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

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

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

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

分級(jí) BF

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

標(biāo)簽：