記一篇REDIS布隆過濾器的使用
開場:
如何判斷一個大集合中是否含有某個元素？
背景:
為了最大化提升廣告轉化效果，業務方決定對接巨量引擎，廣點通以及快手RTA服務。並針對自身情況決定是否出廣告（新使用者出，舊使用者不出）。
大致示意圖
要求： 1。 QPS至少要能撐住
30W。
2。 介面響應不能超過
60ms
面臨的問題:
1。高併發——> 負載均衡這塊交由中臺完成（部署到k8s， 由40個pod分攤掉流量）。
2。低延遲 ——> 響應要快，計算不能太耗時。
調研:
對於低延遲，快速判斷請求側使用者資訊是不是老使用者，需要對舊使用者池進行檢索。儲存方面自然想到redis。
檢索示意圖
資料量級： 目前舊使用者池約有
6億
條資料， 考慮到裝置標識多樣性（IDFA， IMEI， Android_id。。）， 以及大小寫問題，這個資料量可以估算為
15億
左右（需要多預估一些空間）。
挑選資料結構： String。 每一個裝置都是一個key， 請求方只需要看這個key在不在即可
實現：
key： key字首+md5（device）。
例： app：old_users：202cb962ac59075b964b07152d234b70
值： 1
寫命令： SET app：old_users：202cb962ac59075b964b07152d234b70 1
讀命令： EXISTS app：old_users：202cb962ac59075b964b07152d234b70
空間預估：
size = key.length * 16億 = 46B * 16 * 10^8 = 68GB
這種方案成本較高，且會隨著使用者增加線性提升，直接pass。需要找到一種查詢快，且佔用空間小的方案。
抽象:
判斷一個裝置是否在舊使用者池，如果把使用者池看成集合，把裝置看做元素，那麼就可以回到開場的問題——如何判斷一個大集合中是否含有某個元素？
布隆過濾器
似乎是最佳的解決方案。
使用布隆過濾器的好處：
省空間
： 不需要儲存完整的元素，只需要對元素進行hash然後將bit向量表中的某個位設為1即可（先不考慮碰撞問題）
查詢快
： 只需要對查詢的元素進行hash然後看bit向量表中對應的位是否為1。
缺點：
1。因為碰撞，會有一定的誤報率（ 不在集合的一定不在， 在的不一定在 ）。這個可以透過使用多個hash函式減少誤報，但無法完全消除。
2。不支援刪除操作（還是因為碰撞，會出現誤刪的問題）。
有關布隆過濾器的詳解可以參考
結合REDIS
：
redis原生並不自帶布隆過濾器， 需要專門下載並自行編譯和載入，使用方法見
這裡用到布隆過濾器兩個API
1。讀方： BF。EXISTS KEY element
2。寫方： BF。ADD KEY element
兩個API即可完成布隆過濾器元素的增加和查詢操作（注： 這裡的KEY就是布隆過濾器）。
拆KEY：
阿里雲的redis單機只能經受10WQPS，再往上就不行了；所以需要選擇叢集版redis， 用叢集來承擔讀方的查詢壓力。那麼需要將key打散並分攤到不同的節點上。
拆key的規則： 取md5（device）頭四位拼接，這樣頭四位相同的裝置會落到相同的key裡（布隆過濾器）
例： deviceArray = ［
“202cb962ac59075b964b07152d234b70”，
“202cb35dac59075b964b07152d234b95”，
“202cb35dac09875b964b07152d234b88”，
。。。。
］
對應的寫命令：
BF。ADD app：old_users：202c 202cb962ac59075b964b07152d234b70
BF。ADD app：old_users：202c 202cb35dac59075b964b07152d234b95
BF。ADD app：old_users：202c 202cb35dac09875b964b07152d234b88
。。。。
空間預估： key的數量最多為 16^4（十六進位制） 。
size = key.length 16^4 = 18B * 65536 = 1.125MB
這樣key所佔的空間可以忽略。
上線效果:
線上介面QPS： 峰值26W， 谷底4W，平響9ms。
redis使用情況：key數： 13w+（因為一些原因要增加其它的key）， 佔用記憶體：3。19GB（布隆過濾器本身以及bit向量都需要佔用空間）。
總結:
專案做完後，有一些值得思考的地方，整理一下
1。提前預估（要為專案的以後做打算）
QPS預估： 最開始是按最小峰值預估的（10W左右），沒有考慮業務發展的情況（後期接近30W）。如果不是領導提醒，自己就傻乎乎的按10W的量去做了，那redis的選型就會有問題（主從版redis只能支援10w，後來改為叢集版），以後要估高一些，若資源使用率不高，再降配也不晚。
2。布隆過濾器使用（技術方案要儘可能通用）
開發時使用redis布隆過濾器的時候，用的是本地載入官方元件並啟動redis，並沒有考慮到阿里雲是否支援；結果預設是不支援的。。。 好在後來跟對方協商，對方可以提供定製化版的redis，可以支援布隆過濾器的API。 這個事後還是有點後怕的， 如果它不支援呢？ 如果要遷移到別的雲呢？這個其實是留下了隱患的。 技術方案要有備選（用bitmap+偏移量實現， 但是hash演算法要找輪子或自己實現）
3。抽象能力
這個非常重要，最終的技術方案並不是自己想到的，而是經過領導指點的。在特定的業務場景下，用合適的資料結構解決業務上的問題，為什麼別人能抽象到具體的方案，而自己沒想到？ 歸根結底還是對資料結構和算法理解的不夠透徹， 這塊是需要深耕的地方。
