概述

• 曝光過濾通常是在召回階段做，具體的方法就是用 Bloom Filter

曝光過濾問題

• 如果用戶看過某個物品，則不再把該物品曝光給用戶。原因是同一個物品重復曝光給用戶會損害用戶體驗，但也不是所有推薦系統都有曝光過濾，像 youtube 這樣的長視頻就沒有曝光過濾，看過的也可以再次推薦
• 對于每個用戶，記錄已經曝光給他的物品（小紅書只召回 1 個月以內的筆記，因此只需要記錄每個用戶最近 1 個月的曝光歷史）
• 對于每個召回的物品，判斷它是否已經給該用戶曝光過，排除掉曾經曝光過的物品
• 一位用戶看過 $n$ 個物品，本次召回 $r$ 個物品，如果爆力對比，需要 $O(nr)$ 的時間。
• 在小紅書一個月 $n$ 的曝光量級大概是幾千，每次推薦召回量 $r$ 的量級也是幾千，暴力對比的計算量太大了，所以實踐中不暴力對比，而是用 Bloom Fliter

Bloom Filter

• Bloom Filter是一種數據結構，發表在 1970 年，以它的發明者命名
• 推薦系統的曝光過濾基本上都是用 Bloom Fliter 做的
• Bloom Fliter 判斷要給物品ID是否已經在已曝光的物品集合中
• 如果判斷為 no，那么該物品一定不在集合中
• 如果判斷為 yes，那么該物品很可能在集合中（可能誤傷，錯誤判斷未曝光物品為已曝光，將其過濾掉）
• 如果用 Bloom Fliter 過濾，肯定能干掉所有已經曝光的物品，但是可能會誤傷
• Bloom Fliter 把物品集合表征為一個 m 維二進制向量
• 每個用戶有一個曝光物品的集合，表征為一個向量，需要 m bit 的存儲
• Bloom fliter 有 k 個哈希函數，每個哈希函數把物品ID映射成介于 0 和 m-1 之間的整數

Bloom Filter (k=1)

• 初始的時候向量是全 0 的
  
• 我們知道用戶有哪些已經曝光過的物品，如下圖哈希函數把第一個物品 $I{D}_1$ 映射為 1，所以我們將二進制的第一位映射為 1
  
• 第二個物品 $I{D}_2$ 映射為了 8，所以把位置 8 的二進制位改為 1
  
• 哈希函數把第三個物品 $I{D}_3$ 映射為了位置 1，這個位置的元素已經是 1 了，不需要修改這個數值
  
• 哈希函數把第四個物品 $I{D}_4$ 映射到了位置 5，我們也將其置為 1
  
• 哈希函數把第五第六個物品都映射到了位置 5，這個位置已經是 1 了，不需要修改這個數值，到此為止我們已經把 6 個物品表征為一個向量
  
• 用戶發起推薦請求后曝光很多物品，這里用一個之前未曝光給用戶的物品，他被映射到位置 2，這個位置是 0，所以 Bloom Filter 判斷這個物品之間沒有被曝光
• 這個判斷是正確的。如果 Bloom Filter 認為它沒有被曝光，那么它肯定沒被曝光，Bloom Filter 不會把已曝光的物品錯判未未曝光
  
• 而下面又一個新來的物品已經曝光了，那么它就會被映射到之前它標記過的位置
  
• 對于又一個新的未曝光的物品，哈希函數把它映射到了位置 8，這個位置已經被標記為了 1，所以被認為已經曝光過了，此時錯判
  

Bloom Filter (k=3)

• 初始全0，來了一個 $I{D}_1$ 物品，此時有 3 個哈希函數，我們把它映射到了 3 個位置上，我們把 3 個位置都置為 1
  
• $I{D}_2$ 也是一個已曝光的物品，我們還用 3 個哈希函數把它映射到 3 個位置上，把 3 個位置的都置為 1
  
• 現在有一個召回的物品 $I{D}_8$，用 3 個哈希函數把它映射到了 3 個不同的位置。假如這個物品已經曝光，那么 3 個位置肯定都是 1 了，但其中 1 個位置是 0，說明這個物品還未曝光
  
• 對于 $I{D}_4$ ，它已經被曝光，判斷是正確的
  
• 對于未曝光的 $I{D}_9$ ，它映射的 3 個位置都為 1，被誤判了
  

誤傷概率分析

• 曝光物品集合大小為 $n$，二進制向量維度為 $m$，使用 $k$ 個哈希函數
• $n$ 越大，向量中的 1 越多，誤傷的概率越大（未曝光的 $k$ 個位置恰好都是 1 的概率大）
• $m$ 越大，向量越長，越不容易發生哈希碰撞，需要的存儲也越多
• $k$ 太大，太小都不好，$k$ 有最優取值
  
• 設定可容忍的誤傷概率為 $\delta$ ，那么最優參數為：
  
• 只需要 m = 10n bit，就可以把誤傷概率降低到 1% 以下

曝光過濾的鏈路

• 把曝光物品記錄下來，反饋給召回階段，用于過濾召回的物品
  
• app 的前端有埋點，所有曝光的物品都會被記錄下來。這個落表的速度要足夠快，否則可能會出問題
• 用戶推薦頁面兩次刷新間隔也就幾分鐘，快的話也就一二十秒，在下次刷新前就得把本次曝光的結果寫道 Bloom Filter 上，否則下一刷很可能會出重復的物品。
• 所以要用實時流處理，比如把曝光物品寫入 Kafka 消息隊列，用 Flink 做實時計算
  
• Flink 實時讀取 Kafka 消息隊列，計算曝光物品的哈希值，把結果寫道 Bloom Fliter 的二進制向量上
• 用這樣的實時數據鏈路，在曝光發生的幾秒后，這位用戶的 Bloom Filter 就會被修改，就可以避免重復曝光
• 但實時流這部分也是最容易出問題的，如果掛掉了或者延時特別大。那么上一刷才看過的物品又會出現
  
• 曝光過濾具體用在召回完成之后：召回服務器請求曝光過濾服務，曝光過濾服務把二進制向量發送給召回服務器，在召回服務器上用 Bloom Filter 計算召回的物品的哈希值，再和二進制向量做對比，把已經曝光的物品給過濾掉，發送剩余的物品給排序服務器

Bloom Filter 的缺點

• Bloom 把物品的集合表示成一個二進制向量
• 每往集合中添加一個物品，只需要把向量的 k 個位置的元素置為 1
• Bloom Filter 只支持添加物品，不支持刪除物品，從集合中移除物品，無法消除它對向量的影響。因為是共享的，所以要移除的話不能簡單的把它的位置都改為 0，因為有可能別的物品也在這個位置有標記
• 每天都需要從物品集合中移除年齡大于 1 個月的物品（超齡物品不可能被召回，沒必要把它們記錄在 Bloom Filter，降低 n 可以降低誤傷率）
• 想要刪除一個物品，需要計算整個集合的二進制向量