資料結構大便當：Bloom FilterKadaiBlockedUnblockFollowFollowingDec 20Bloom Filter 介紹與實作大家好，我是 Kadai，本次要分享的是在後端 Redis 分享會第一次聽到的資料結構：Bloom Filter（布隆過濾器）簡介Bloom Filter（布隆過濾器）由 Burton Howard Bloom 在 1970 構思出來，用來測試一個元素是否存在特定集合中。hash table 也可以做到，那為什麼要使用 Bloom Filter 呢？原因在於比起 hash table ，Bloom Filter 的空間複雜度有巨大的優勢，但強大的力量必然伴隨副作用，隨之而來的就是有機率會發生 false positive，幸好 false positive rate 是可以透過調整 bit array 的大小和 hash function 的數量來控制的。你可能有些疑問：到底 Bloom Filter 是怎麼運作的、為什麼 Bloom Filter 空間複雜度比較好、false positive 是什麼、我們要怎麼調整參數來控制 false positive rate？就讓我們繼續看下去吧！原理Bloom Filter 有兩個要素：長度為 n 的 bit array 和 m 個獨立的 hash function，當要寫入資料（x）的時候，用所有的 hash function 對 x 進行 hash 後 mod n 得到 m 個位置，把 bit array 這些位置的 bit 設為 1，就完成了一次寫入。圖片中的例子是 m = 3X, Y, Z 都是 int，作為 index 去設定 bit array 的值查詢也是同樣的流程在得到 m 個位置之後，去 bit array 取出相對應的值，如果全都是 1 的話就代表集合中有這個元素，就可以確認這個資料之前曾經出現過。Bloom Filter 的代價在簡介的時候有說到：越是強大的能力，必然伴隨更高的風險或是代價Bloom Filter 有機會發生 false positive，那什麼是 false positive 呢？https://en.wikipedia.org/wiki/Type_I_and_type_II_errors#Table_of_error_types指的是：如果 Bloom Filter 回傳沒有（negative）：代表資料 一定沒有 在 Bloom Filter 中如果 Bloom Filter 回傳有（positive）：代表資料 可能有 在 Bloom Filter 中，並不是一定有在 Bloom Filter 中所以在使用 Bloom Filter 情境，是要可以忍受 false positive 的發生，且發生之後不會造成太大的影響，那我們怎麼評估或是計算 false positive 發生的機率呢？在 wiki 上有相關的數學推導，可以直接套用計算，或是想要更方便更懶人的話推薦這個網站：Bloom filter calculatorCalculate the optimal size for your bloom filter, see how many items a given filter can hold, or just admire the curvy…hur.st只要輸入直接幫你算好，還順便畫好圖表。除了 false positive 有可能發生之外，第二個缺點就是無法刪除已經加入的資料，關於這點可以參考 bloom filter 的各種變形版（Counting Filter / Cuckoo Filter…）。Bloom Filter 使用案例講完原理了，讓我們來看看有什麼使用案例吧搶票流量控制：在搶票的大流量的狀況下，我們必須限制進來 server 的流量，但不能擋已經成功 reserve ticket 的 user 繼續進行後續付款取票的流程， 這時候就可以用 bloom filter 快速辨別該 request 的 jwt 是否在 bloom filter 中，有的話代表有訂到票，就可以直接放行，進行後續付款的步驟。記得控制好 false positive rate 跟處理流程，如果 false positive rate 太高，放行太多應該要擋掉的 request，後端流量還是會衝很高。Yahoo Email 確認收件者在不在連絡清單：在進入 Yahoo Email 的頁面後會把 user 的聯絡清單放到 client 端的 bloom filter，在 user 寄信的時候，可以快速檢查收件人是不是已經在聯絡清單中，沒有的話就可以詢問要不要新增，這樣做的好處是，在確認時不用在呼叫後端，也可以快速地得到結果。Tinder Suggestion：這個是猜測，Tinder 會搜尋離 user 一定範圍內的用戶來作為給 user 配對的對象，但怎麼避免已經配對或是拒絕過的呢，一樣也是把 user 配對或是拒絕過的對象放進 bloom filter，在搜尋時確認是否在 bloom filter 中，如果有就不要回傳給 client，但如果 false positive 發生，可能就這樣錯過真命天子 / 天女了呢，只能說一切都是緣分啊。from: https://www.quora.com/What-are-the-best-applications-of-Bloom-filters實作說了這麼多，大家應該對 bloom filter 應該都有一定的了解惹，那麼就要來實作啦，這次用的是 Python 3.5.1 來實作 bloom filter首先我們初始化一個 class，這次我們使用 3 個 hash function: md5, sha1, sha224，在 python 的 hashlib 已經幫你實作好了，可以直接使用。（注：如果是用 python 3.6 以上的話 hashlib 中新增了 blake 系列可以選用）為了可以直接操縱 bit 所以特別找了 bitarray 這個套件來使用，要不然使用一般的 python list 的話 size 就會比較大喔。為此我們特別加了第 12 行來試看看（最後有測試結果）接下來就是實作 add_data 這個 function，hash 之後 mod 就可拿到 index，再去改值就好了，為了看到底差多少，這邊連 list 也要一起改值喔。再來就是確認該筆 data 有沒有出現過的 is_data_exist function，只要把拿到的 bit 全部 AND 起來看是不是 1 就可以了。完整版：那麼接下來我們就可以來測試看看摟，預設的 bit array size 是 10000，然後先塞 1000 筆隨機資料進去，再用另外的 1000 隨機資料來測，然後為了比較 bloom filter / set / dict 之間的大小，所以同時也對其他兩個加入資料，也可以拿來算最後的 false positive rate。上面為了方便解釋所以切開來，完整的 code 可以參照：https://github.com/kadai0308/data_structure/blob/master/hash/bf.py如果想要直接試試看的話可以自己 clone 下來跑跑看。輸出結果：可以發現 list 用了超多的空間，再來是 dict 跟 set，false positive rate 也十分接近用計算機算出來的值 ( 1.7% )。後記會想要寫這篇是因為在 Redis 的分享會上第一次聽到 bloom filter，覺得很新奇也很有趣，同時也覺得如果可以在資料結構上有更深更廣的知識的話，在面對不同情境的問題時可以處理得更加漂亮，所以就有了複習跟學習資料結構的計畫，同時想寫下來紀錄整個過程跟學到的東西，也希望可以幫助到大家，如果有任何疑問或是問題，都歡迎直接留言，謝謝收看，我們下次再會。參考資料和延伸閱讀https://hur.st/bloomfilterhttps://en.wikipedia.org/wiki/Bloom_filterhttp://www.evanlin.com/BloomFilter/https://coolshell.cn/articles/17225.html感謝你/妳花時間讀這篇文章，如果你覺得這篇文章寫得不錯、有幫助到你，希望你能給我一點「拍手鼓勵」，也可以留言讓我知道你的想法，我會多加點油寫出更多內容的！Powered by Simon1..拍「10下」：表示你喜歡這篇文章，謝謝你！2..拍「20下」：表示你覺得這篇文章很棒、願意分享給朋友！3..拍「30–40下」：希望未來我能寫更多這類主題的文章！4..拍好拍滿「50下」：給我最大的鼓勵，這將會支持我繼續寫作，並持續分享我的經驗！拍手小秘訣： 只要將滑鼠(或手指)持續按著不放手掌的icon，就能夠連續拍手囉，試試看吧！. More details