資料庫必知詞彙：布隆過濾器（Bloom Filter）

|名詞定義|

布隆過濾器（Bloom Filter）是由Burton Bloom 在1970年提出的，其後在P2P上得到了廣泛的應用。一個空的布隆過濾器是一個m位的位數組，所有位的值都為0。定義了k個不同的符合均勻随機分布的哈希函數，每個函數把集合元素映射到位數組的m位中的某一位。Bloom filter算法可用來查詢某一資料是否在某一資料集合中。其優點是查詢效率高、可節省空間。但其缺點是會存在一定的錯誤。是以Bloom filter 算法僅僅能應用于那些同意有一定錯誤的場合。可使用Bloom filter 算法的場合包含字典軟體、分布式緩存、P2P網絡和資源路由等等。

| 發展曆程 |

1970年由Burton Bloom提出布隆過濾器（Bloom Filter）是一個空間效率比較高的資料結構，用于檢測一個元素在集合中是否存在。Bloom Filter就被廣泛用于拼寫檢查和資料庫系統中。

近一二十年，伴随着網絡的普及和發展，Bloom Filter在網絡領域獲得了新生，各種Bloom Filter變種和新的應用不斷出現。可以預見，随着網絡應用的不斷深入，新的變種和應用将會繼續出現，Bloom Filter必将獲得更大的發展。

| 技術特點 |

使用布隆過濾器能夠推斷一個元素是否在某一個集合中。假設這個集合是使用線性結構存儲的話。其查找的時間複雜度是O(n)；使用像二叉樹或B-tree這種樹形結構存儲的話其查找的時間複雜度是O(logn)。而使用布隆過濾器在能夠容忍一定錯誤率的情況下，其時間複雜度是O(1)。是以，與傳統的權衡空間或時間的算法不同，布隆過濾器極其巧妙。通過引入一定的錯誤率來換取時間和空間，在某些應用大大提高了性能。

如果想要判斷一個元素是不是在一個集合裡，一般想到的是将所有元素儲存起來，然後通過比較确定。連結清單，樹等等資料結構都是這種思路。但是随着集合中元素的增加，我們需要的存儲空間越來越大，檢索速度也越來越慢(O(n),O(logn))。不過世界上還有一種叫作散清單（又叫哈希表，Hash table）的資料結構。它可以通過一個Hash函數将一個元素映射成一個位陣列（Bit array）中的一個點。這樣一來，我們隻要看看這個點是不是1就可以知道集合中有沒有它了。這就是布隆過濾器的基本思想。

相比于其它的資料結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數。另外, Hash函數互相之間沒有關系，友善由硬體并行實作。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。

布隆過濾器之是以能做到在時間和空間上的效率比較高，是因為犧牲了判斷的準确率、删除的便利性：

• 存在誤判，可能要查到的元素并沒有在容器中，但是Hash之後得到的k個位置上值都是1。如果布隆過濾器中存儲的是黑名單，那麼可以通過建立一個白名單來存儲可能會誤判的元素。
• 删除困難。一個放入容器的元素映射到bit數組的k個位置上是1，删除的時候不能簡單的直接置為0，可能會影響其他元素的判斷。可以采用Counting Bloom Filter。

| 相關詞 |

Bloom_filter – 布隆過濾器

HBase – 資料庫

Hash table – 哈希表

| 案例展示 |

• Google 的分布式資料庫 Bigtable 使用了布隆過濾器來查找不存在的行或列，以減少磁盤查找的IO次數。
• Squid 網頁代理緩存伺服器在 cache digests 中使用了也布隆過濾器。
• Venti 文檔存儲系統也采用布隆過濾器來檢測先前存儲的資料。
• SPIN 模型檢測器也使用布隆過濾器在大規模驗證問題時跟蹤可達狀态空間。
• Google Chrome浏覽器使用了布隆過濾器加速安全浏覽服務。
• Google Guava - 使用bloom過濾器判斷是否存在該行（rows）或（colums），以減少對磁盤的通路，提高資料庫的通路性能
• Apache的HBase - 使用bloom過濾器判斷是否存在該行（rows）或（colums），以減少對磁盤的通路，提高資料庫的通路性能
• Apache_Cassandra - 使用bloom過濾器判斷是否存在該行（rows）或（colums），以減少對磁盤的通路，提高資料庫的通路性能
• 比特币 - 使用布隆過濾判斷錢包是否同步OK

|資料來源|

Dillinger, Peter C.;Manolios, Panagiotis (2004a), "Fast and Accurate Bitstate Verification forSPIN", Proceedings of the 11thInternational Spin Workshop on Model Checking Software, Springer-Verlag, LectureNotes in Computer Science 2989

Kirsch, Adam; Mitzenmacher, Michael(2006), "Less Hashing, Same Performance: Building a Better BloomFilter", in Azar, Yossi; Erlebach, Thomas, Algorithms– ESA 2006, 14th Annual European Symposium (PDF), LectureNotes in Computer Science 4168,Springer-Verlag, Lecture Notes in Computer Science 4168, pp. 456–467, doi:10.1007/11841036, ISBN 978-3-540-38875-3

Mitzenmacher & Upfal (2005), pp. 109–111, 308.

BloomFilter基本概念和實作原理

https://blog.csdn.net/zq602316498/article/details/40660235

Bloom Filter 算法具體解釋

https://www.cnblogs.com/lcchuguo/p/5254340.html

布隆過濾器(BloomFilter)的原理、實作和探究

https://my.oschina.net/LucasZhu/blog/1813110

大資料量下的集合過濾—Bloom Filter

https://www.cnblogs.com/z941030/p/9218356.html