首頁 > 綜合 > 正文

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

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

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

【資料圖】

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

方案一：Set

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

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

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

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

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

那有沒有更優惠的實現方案呢？這就要說到本文的主角，布隆過濾器了。

方案二：Bloom Filter

布隆過濾器，本質上是一個高階 Bitmap，最適合的場景就是海量數據的過濾了。

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

布隆過濾器介紹

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

bloom filter

簡單說下它的使用：

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

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

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

1. bloom 中存的摘要，而不是原始數據 data，所以空間占用遠遠低于 set 的占用。

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

3. bloom 無法動態擴展大小，如上圖示，bit 數組是固定的，如果 bits 數組長度調整了，那么同樣的 x、y hash 后的 bits 索引也會發生變化。

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

誤判率計算公式

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

布隆過濾器實現曝光打擊

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

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

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

當設置 bloom 容量為 200 時，每人每天1個key，可以保證當天看到不重復的 feeds，BF 規格如下：

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

bloom filter 規格

進一步優化

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

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

怎么優化呢？有幾種思路。

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

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

分級 BF

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

標簽：