共計 6191 個字符，預計需要花費 16 分鐘才能閱讀完成。
這篇文章主要介紹“Redis 中的布隆過濾器怎么實現”，在日常操作中，相信很多人在 Redis 中的布隆過濾器怎么實現問題上存在疑惑，丸趣 TV 小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Redis 中的布隆過濾器怎么實現”的疑惑有所幫助！接下來，請跟著丸趣 TV 小編一起來學習吧！
概述
布隆過濾器（Bloom Filter）是一個數據結構，由布?。˙urton Howard Bloom）于 1970 年提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數?！鞠嚓P推薦：Redis 視頻教程】
布隆過濾器可以用于高效的檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠優于一般的算法，缺點是有一定的誤識別率，而且難以刪除（一般不支持，需要額外的實現）。
誤識率指的是可以判斷元素肯定不在集合中，判斷元素可能在集合中，無法判斷元素一定在集合中。
布隆過濾器之所以高效，因為它是一個概率數據結構，它能確認元素肯定不在集合中，或者元素可能在集合中。之所以說是可能，是因為它有一定的誤識別率，使得無法 100% 確定元素一定在集合中。
問題引出
在日常工作中，有一個比較常見的需求，就是需要判斷一個元素是否在集合中。例如以下場景
給定一個 IP 黑名單庫，檢查指定 IP 是否在黑名單中？
在接收郵件的時候，判斷一個郵箱地址是否為垃圾郵件？
在文字處理軟件中，檢查一個英文單詞是否拼寫正確？
遇到這種問題，通常直覺會告訴我們，應該使用集合這種數據結構來實現。例如，先將 IP 黑名單庫的所有 IP 全部存儲到一個集合中，然后再拿指定的 IP 到該集合中檢查是否存在，如果存在則說明該 IP 命中黑名單。
通過一段代碼來模擬 IP 黑名單庫的存儲和檢查。
public class IPBlackList {public static void main(String[] args) {Set String set = new HashSet ();
set.add( 192.168.1.1
set.add( 192.168.1.2
set.add( 192.168.1.4
System.out.println(set.contains( 192.168.1.1));
System.out.println(set.contains( 192.168.1.2));
System.out.println(set.contains( 192.168.1.3));
System.out.println(set.contains( 192.168.1.4));
}集合的內部，通常是使用散列表來實現。其優點是查詢非常高效，缺點是比較耗費存儲空間。
一般在數據量比較小的時候，我們會使用集合來進行存儲。以空間換時間，在占用空間較小的情況下，同時又能提高查詢效率。
但是，當存儲的數據量比較大的時候，耗費大量空間將會成為問題。因為這些數據通常會存儲到進程內存中，以加快查詢效率。而機器的內存通常都是有限的，要盡可能高效的使用。
另一方面，散列表在空間和效率上是需要做平衡的。存儲相同數量的元素，如果散列表容量越小，出現沖突的概率就越高，用于解決沖突的時間將會花費更多，從而影響性能。
而布隆過濾器（Bloom Filter）的產生，能夠很好的解決這個問題。一方面能夠以更少的內存來存儲數據，另一方面能夠實現非常高效的查詢性能。
基本原理
首先，建立一個二進制向量，并將所有位設置為 0
然后，選定 K 個散列函數，用于對元素進行 K 次散列，計算向量的位下標。
添加元素
當添加一個元素到集合中時，通過 K 個散列函數分別作用于元素，生成 K 個值作為下標，并對向量的相應位設置為 1。
檢查元素
如果要檢查一個元素是否存在集合中，用同樣的散列方法，生成 K 個下標，并檢查向量的相應位是否全部是 1。
如果全為 1，則該元素很可能在集合中；否則（只要有 1 個或以上的位為 0），該元素肯定不在集合中。
Demo
假設有一個布隆過濾器，容量是 15 位，使用 2 個哈希函數，如下所示。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|0|||||||||||||||||||
添加一個字符串 a，2 次哈希得到下標為 4 和 10，將 4 和 10 對應的位由 0 標記為 1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|||||1||||||1|||||||||
再添加一個字符串 b，2 次哈希得到下標為 11，將 11 對應的位由 0 標記為 1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|||||1||||||1|1||||||||
再添加一個字符串 c，2 次哈希得到下標為 11 和 12，將對應的位由 0 標記為 1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|||||1||||||1|1|1|||||||
最后添加一個字符串 sam，2 次哈希得到下標為 0 和 7，將對應的位由 0 標記為 1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|1||||1|||1|||1|1|1|||||||
上面，我們添加了 4 個字符串，每個字符串分別進行 2 次哈希，對應的 2 個位標記為 1，最終被標記為 1 的共有 6 位而不是 8 位。
這說明，不同的元素，哈希后得到的位置是可能出現重疊的。如果元素越多，出現重疊的概率會更高。如果有 2 個元素出現重疊的位置，我們是無法判斷任一元素一定在集合中的。
如果要檢查一下元素是否存在集合中，只需要以相同的方法，進行 2 次哈希，將得到的 2 個下標在布隆過濾器中的相應位進行查找。如果對應的 2 位不是全部為 1，則該元素肯定不在集合中。如果對應的 2 位全部為 1，則說明該元素可能在集合中，也可能不存在。
例如，檢查字符串 b 是否存在集合中，哈希得到的 2 個下標都為 11。檢查發現，11 對應的位為 1。但是，這并不能說明 b 一定在集合中。這是因為，字符串 c 哈希后的下標也包含 11，有可能只是字符串 c 在集合中，而 b 卻不存在，這就是造成了誤識別，也稱為假陽性。
再檢查字符串 foo，哈希得到的下標分別為 8 和 13，對應的位都為 0。因此，字符串 foo 肯定不在集合中。
數學原理
布隆過濾器背后的數學原理是
兩個完全隨機的數字相沖突的概率很小，因此可以在很小的誤識別率條件下，用很少的空間存儲大量信息。
誤識別率
誤識別率（FPP，false positive probabilistic）的計算如下。
假設布隆過濾器大小為 m 比特，存儲了 n 個元素，使用 k 次散列函數來計算元素的存儲位置。
添加 1 個元素，則任一比特為 1 的概率為 1/m，任一比特為 0 的概率為 1-1/m；
添加 1 個元素，執行 k 次散列之后，則任一比特為 0 的概率為 (1-1/m)^k，任一比特為 1 的概率為 1-(1-1/m)^k；
如果添加 n 個元素，那么任一比特為 0 的概率為 (1-1/m)^kn，任一比特為 1 的概率為 1-(1-1/m)^kn；
如果將 1 個新的元素，添加到已存在 n 個元素的布隆過濾器中，則任一比特已經為 1 的概率與上面相同，概率為 1-(1-1/m)^kn。因此，k 個比特都為 1 的概率為：(1-(1-1/m)^kn)^k，此即為新插入元素的誤識別率。
當 n 值比較大時，$(1-(1-1/m)^{kn})^k$ 約等于 $(1-e^{-kn/m})^k$
假定布隆過濾器大小 m 為 16 比特，k 為 8，存儲元素 n 為 1，那么誤識別（假陽性）的概率是萬分之五（5/10000）。
此時，m/n=16，事實上這表示 1 個元素使用 16 個比特的空間來存儲。
因此，當 k 相同時，m/n 為 16/1、32/2、64/4 等值時具有相同的誤識別率。
網站 Bloom Filters – the math 給出了布隆過濾器的誤識別率表，可以很方便的查處不同 m，n，k 給定值下的誤識別率。
解決誤識別率
解決誤識別率的常用方法包括
白名單
回溯確認
白名單
解決誤識別率的常見方法，是建立一個較小的白名單，用來存儲那些可能被誤識別的數據。
以垃圾郵件過濾為例。假設我們有一個垃圾郵件庫，用于在接收郵件的時候過濾掉垃圾郵件。
這時可以先將這個垃圾郵件庫存儲到布隆過濾器中，當接收到郵件的時候，可以先通過布隆過濾器高效的過濾出大部分正常郵件。
而對于少部分命中（可能為）垃圾郵件的，其中有一部分可能為正常郵件。
再創建一個白名單庫，當在布隆過濾器中判斷可能為垃圾郵件時，通過查詢白名單來確認是否為正常郵件。
對于沒在白名單中的郵件，默認會被移動到垃圾箱。通過人工識別的方式，當發現垃圾箱中存在正常郵件的時候，將其移入白名單。
回源確認
很多時候，使用布隆過濾器是為了低成本，高效率的攔截掉大量數據不在集合中的場景。例如
Google Bigtable，Apache HBase 以及 Apache Cassandra 和 PostgreSQL 使用 Bloom 過濾器來減少對不存在的行或列的磁盤查找。避免進行昂貴的磁盤查找，可大大提高數據庫查詢操作的性能。
在谷歌瀏覽器用于使用布隆過濾器來識別惡意 URL 的網頁瀏覽器。首先會針對本地 Bloom 過濾器檢查所有 URL，只有在 Bloom 過濾器返回肯定結果的情況下，才對執行的 URL 進行全面檢查（如果該結果也返回肯定結果，則用戶會發出警告）。
攔截掉大量非 IP 黑名單請求，對于少量可能在黑名單中的 IP，再查詢一次黑名單庫。
這是布隆過濾器非常典型的應用場景，先過濾掉大部分請求，然后只處理少量不明確的請求。
這個方法，和白名單庫的區別是，不需要再另外建立一套庫來處理，而是使用本來就已經存在的數據和邏輯。
例如 Google Bigtable 查詢數據行本來就是需要查的，只不過使用布隆過濾器攔截掉了大部分不必要的請求。而 IP 是否為黑名單也是需要查詢的，同樣是先使用布隆過濾器來攔截掉大部分 IP。
而上面垃圾郵件的處理，對于可能為垃圾郵件的情況，不是通過完整的垃圾郵件庫再查詢一次進行確認，而是用增加白名單來進行判斷的方式。因為通常來說，白名單庫會更小，便于緩存。
這里所說的回源，實際上是對可能被誤識別的請求，最后要回到數據源頭或邏輯確認一次。
Guava 中的布隆容器的實現
Guava 中就提供了一種 Bloom Filter 的實現。
guava 包引入
要使用 Bloom Filter，需要引入 guava 包
dependency
groupId com.google.guava /groupId
artifactId guava /artifactId
version 23.0 /version
/dependency誤判率測試
下面對布隆容器的誤判率進行測試，分 2 步
往過濾器中放一百萬個數，然后去驗證這一百萬個數是否能通過過濾器
另外找一萬個數，去檢驗漏網之魚的數量
/**
* 測試布隆過濾器 (可用于 redis 緩存穿透)
*
* @author 敖丙
*/
public class TestBloomFilter {
private static int total = 1000000;
private static BloomFilter Integer bf = BloomFilter.create(Funnels.integerFunnel(), total);
// private static BloomFilter Integer bf = BloomFilter.create(Funnels.integerFunnel(), total, 0.001);
public static void main(String[] args) {
// 初始化 1000000 條數據到過濾器中
for (int i = 0; i total; i++) { bf.put(i);
}
// 匹配已在過濾器中的值，是否有匹配不上的
for (int i = 0; i total; i++) { if (!bf.mightContain(i)) {
System.out.println( 有壞人逃脫了~~~
}
}
// 匹配不在過濾器中的 10000 個值，有多少匹配出來
int count = 0;
for (int i = total; i total + 10000; i++) { if (bf.mightContain(i)) {
count++;
}
}
System.out.println(誤傷的數量： + count);
}
}運行結果
誤傷的數量：320運行結果表示，遍歷這一百萬個在過濾器中的數時，都被識別出來了。一萬個不在過濾器中的數，誤傷了 320 個，錯誤率是 0.03 左右。
Bloom Filter 源碼分析
public static T BloomFilter T create(Funnel ? super T funnel, int expectedInsertions) { return create(funnel, (long) expectedInsertions);
}
public static T BloomFilter T create(Funnel ? super T funnel, long expectedInsertions) { return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
}
public static T BloomFilter T create( Funnel ? super T funnel, long expectedInsertions, double fpp) { return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);
}
static T BloomFilter T create( Funnel ? super T funnel, long expectedInsertions, double fpp, Strategy strategy) {
......
}Bloom Filter 一共四個 create 方法，不過最終都是走向第 4 個?？匆幌旅總€參數的含義
funnel：數據類型 (一般是調用 Funnels 工具類中的)
expectedInsertions：期望插入的值的個數
fpp：錯誤率 (默認值為 0.03)
strategy：哈希算法 Bloom Filter 的應用
到此，關于“Redis 中的布隆過濾器怎么實現”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注丸趣 TV 網站，丸趣 TV 小編會繼續努力為大家帶來更多實用的文章！
