你在刷抖音的時候，有沒有發現，抖音從來不會給你推送相同內容的視頻？你可能會想，這有啥難的，給每個人都存一個記錄，以后推送的時候避開就好了呀。nononono！可沒有這么簡單啊！
海量用戶的重復內容過濾
這是一個非常嚴肅的問題。在互聯網領域，重復推送是一件非常影響用戶體驗的行為。一旦出現重復內容，會大大增加用戶跳出的幾率。
搞數據庫的同學會說：這還不簡單？反正有用戶日志，我們給每個人都存一個訪問日志表，推送之前exists一下就好了。
怎么說呢，如果用戶量只有你們公司幾百號人，這個方案是沒問題的。但是抖音、快手動輒幾億人，每天都刷，這得存多少份log？？每一個用戶的log有多大？每一個推送都要從這個大log里exists一下，得耗多少時間？
等你exists一下，用戶早就跑了好么？所以在抖音、快手動輒幾億日活，每人每天最少看幾百個短視頻的情況，如何快速推送不重復的內容是非常困難的事情。
高速過濾的秘密武器
需求：幾億個用戶，每個用戶有1~幾萬（甚至更多）個已看記錄，快速判斷下一個推送給用戶的視頻是否已經看過。
解決方案1-表級處理：每個用戶一張表，存視頻id，推薦之后，展示之前，過濾一下。這個表太多，表里的數據也太多，過濾效率太慢了。信息得進一步壓縮，速度要再快點才行。
解決方案2-圖計算：把每個用戶與每個視頻發生的關系都存到圖數據庫。推薦的時候直接通過關系過濾掉。這個雖然不用建N張表，只是存用戶和視頻的關系就行了。但是用過圖數據庫的人就知道，節點太多了，計算效果也是非常的慢。不行，信息還得進一步壓縮。還能咋壓縮啊？
解決方案3-位圖：把所有用戶當天是否登錄的信息映射到一張位圖中，這樣我們就能迅速通過某個位是0還是1快速判定這個用戶當天是否登錄過系統。
假如說我們同樣使用位圖，把每個用戶是否看過這個視頻映射到位圖中，是不是就可以通過某個位是0還是1快速判定這個用戶是否看過這個視頻呢？哆啦A夢告訴我們：可以！而且有更完善的方法--布隆過濾器！
布隆過濾器：1970年由布隆提出的一種方法，由隨機映射函數和二進制向量組成，可以快速檢索一個元素是否在一個集合中。
如布隆過濾器的描述，其實就是隨機映射函數（hash散列）+二進制向量（位圖）組成的。我們把任意需要存儲的內容，經過hash散列映射成為一個隨機數字，然后存在這張超大的位圖中，將對應的位上的值由0改成1就可以了。這樣我們就能知道這個這個事情是否發生過。
上圖中，用戶A看了視頻B，hash后的值是5，那么第5位的值就變成1了。如果我們想判斷用戶A是否看了視頻B，只要看看第5位是不是1就可以了。
但是hash有個問題，當數據量超大的時候，就有可能會重復（碰撞）。幸好布隆早就想到了，他是這么解決的：
多hash幾次就好了，這樣就能就大大降低了重復（碰撞）的問題。總不可能連續好幾次hash都是一樣的結果吧？
視頻推薦過濾器
原理有了，那么就可以開始設計了。
這里我們可以看到，有兩個實體：用戶和視頻。簡單組合一下，就有三種方法：
1、給每個用戶建一個看過視頻的布隆過濾器，推薦系統推送的內容使用布隆過濾器過濾一下，把不在列表里的讓客戶可見即可；
2、給每個視頻建一個觀看列表的布隆過濾器，推薦系統給用戶推送的時候使用布隆過濾器過濾一下，不在列表里的才能推送即可；
3、建一個大的布隆過濾器，把每個用戶的觀看記錄都放在這個過濾器中，推薦系統給用戶推送的時候到大布隆過濾器中過濾一下，不在列表里的才能推送。
以上三種方法都可以，我也不太清楚抖音用的是那種方法，我猜是第一種，因為視頻總比用戶多，而一個大布隆過濾器的話，又太大了。
布隆過濾器的優化
不過即便是每個用戶一個布隆過濾器，數據量還是太大了。任何事情都會引發量變引起質變的問題。所以布隆過濾器誤判的問題仍然是存在的。比如：
用戶A看視頻B，3次hash散列結果是2、5、6；用戶A看視頻D，3次hash散列結果是5、7、8；用戶A看視頻F，3次hash散列結果是1、9、3；
這時候，位圖中的1、2、3、5、7、8、9都被打上1了。
而我們需要詢問布隆過濾器用戶A是否看過視頻H的時候就出現了：
用戶A看視頻H，3次hash散列結果是3、8、9，
布隆過濾器里3、8、9的結果內容里已經被打上1了，也就是說布隆過濾器告訴我
們，這個視頻已經被看過了（實際上并沒有看）。那我們怎么解決這個問題呢？
簡單的兩招：
1、增加位圖的位數（或者減少原始數據量）；
2、適當增加hash次數；
布隆大大早就給我們算好了，最佳的原始數據和位圖位數比是1:20，經過8次hash，誤判率會在千分之一左右。如果把hash次數提高，誤判率會更低。
不過，我們的應用是要知道這個用戶沒看過的，那就不用咋優化了。因為布隆過濾器告訴我們看過，可能是誤判，但是如果告訴我們沒看過，那就肯定是沒看過。
