文章目錄
- 什么是布隆過濾器
-
- 布隆過濾器的優點：
- 布隆過濾器的缺點：
- 其他問題
- 布隆過濾器適合的場景
- 布隆過濾器原理
-
- 數據結構
- 增加元素
- 查詢元素
- 刪除元素
- 如何使用布隆過濾器
-
- Google開源的Guava自帶布隆過濾器
- Redis實現布隆過濾器
-
- Redis中配置布隆過濾器
- Redis中布隆過濾器指令使用
-
- 自定義參數
- 基本操作
- Java集成Redis使用布隆過濾器
-
- pom中引入redisson依賴:
- 編寫代碼測試
什么是布隆過濾器
布隆過濾器（Bloom Filter）是 1970 年由布隆提出的，是一種非常節省空間的概率數據結構，運行速度快，占用內存小，但是有一定的誤判率且無法刪除元素。它實際上是一個很長的二進制向量和一系列隨機映射函數組成，主要用于判斷一個元素是否在一個集合中。
通常我們都會遇到判斷一個元素是否在某個集合中的業務場景，這個時候我們可能都是采用 HashMap的Put方法或者其他集合將數據保存起來，然后進行比較確定，但是如果元素很多的情況下，采用這種方式就會非常浪費空間，最終達到瓶頸，檢索速度也會越來越慢，這時布隆過濾器（Bloom Filter）就應運而生了。
布隆過濾器的優點：
- 支持海量數據場景下高效判斷元素是否存在
- 布隆過濾器存儲空間小，并且節省空間，不存儲數據本身，僅存儲hash結果取模運算后的位標記
- 不存儲數據本身，比較適合某些保密場景
布隆過濾器的缺點：
- 不存儲數據本身，所以只能添加但不可刪除，因為刪掉元素會導致誤判率增加
- 由于存在hash碰撞，匹配結果如果是“存在于過濾器中”，實際不一定存在
- 當容量快滿時，hash碰撞的概率變大，插入、查詢的錯誤率也就隨之增加了
布隆過濾器中一個元素如果判斷結果為存在的時候元素不一定存在，但是判斷結果為不存在的時候則一定不存在。因此，布隆過濾器不適合那些對結果必須精準的應用場景。
其他問題
- 不支持計數，同一個元素可以多次插入，但效果和插入一次相同
- 由于錯誤率影響hash函數的數量，當hash函數越多，每次插入、查詢需做的hash操作就越多
布隆過濾器適合的場景
- 區塊鏈中使用布隆過濾器來加快錢包同步；以太坊使用布隆過濾器用于快速查詢以太坊區塊鏈的日志
- 數據庫防止穿庫，Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter來減少不存在的行或列的磁盤查找。避免代價高昂的磁盤查找會大大提高數據庫查詢操作的性能
- 判斷用戶是否閱讀過某一個視頻或者文章，類似抖音，刷過的視頻往下滑動不再刷到，可能會導致一定的誤判，但不會讓用戶看到重復的內容
- 網頁爬蟲對URL去重，采用布隆過濾器來對已經爬取過的URL進行存儲，這樣在進行下一次爬取的時候就可以判斷出這個URL是否爬取過了
- 使用布隆過濾器來做黑名單過濾，針對不同的用戶是否存入白名單或者黑名單，雖然有一定的誤判，但是在一定程度上還是很好的解決問題
- 緩存擊穿場景，一般判斷用戶是否在緩存中，如果存在則直接返回結果，不存在則查詢數據庫，如果來一波冷數據，會導致緩存大量擊穿，造成雪崩效應，這時候可以用布隆過濾器當緩存的索引，只有在布隆過濾器中，才去查詢緩存，如果沒查詢到則穿透到數據庫查詢。如果不在布隆過濾器中，則直接返回，會造成一定程度的誤判
- WEB攔截器，如果相同請求則攔截，防止重復被攻擊。用戶第一次請求，將請求參數放入布隆過濾器中，當第二次請求時，先判斷請求參數是否被布隆過濾器命中。可以提高緩存命中率。Squid 網頁代理緩存服務器在 cache digests 中就使用了布隆過濾器。Google Chrome瀏覽器使用了布隆過濾器加速安全瀏覽服務
- Google 著名的分布式數據庫 Bigtable 使用了布隆過濾器來查找不存在的行或列，以減少磁盤查找的IO次數
- Squid 網頁代理緩存服務器在 cache digests 中使用了也布隆過濾器
- Venti 文檔存儲系統也采用布隆過濾器來檢測先前存儲的數據
- SPIN 模型檢測器也使用布隆過濾器在大規模驗證問題時跟蹤可達狀態空間
- Google Chrome瀏覽器使用了布隆過濾器加速安全瀏覽服務
如果允許誤判率的話，可以使用布隆過濾器，只有你想不到的，沒有你做不到的。
布隆過濾器原理
數據結構
布隆過濾器是由一個固定大小的二進制向量或者位圖（bitmap）和一系列映射函數組成的。
對于長度為 m 的位數組，在初始狀態時，它所有位置都被置為0，如下圖所示：
位數組中的每個元素都只占用 1 bit ，并且數組中元素只能是 0 或者 1。這樣申請一個 100w 個元素的位數組只占用 1000000Bit / 8 = 125000 Byte = 125000/1024 KB ≈ 122KB 的空間。
增加元素
當一個元素加入布隆過濾器中的時候，會進行如下操作：
- 使用布隆過濾器中的哈希函數對元素值進行計算，得到哈希值（有幾個哈希函數得到幾個哈希值)
- 根據得到的哈希值，在位數組中把對應下標的值置為 1
接著再添加一個值 “xinlang”，哈希函數的值是3、5、8，如下圖所示：
這里需要注意的是，5 這個 bit 位由于兩個值的哈希函數都返回了這個 bit 位，因此被覆蓋了。
查詢元素
- 對給定元素再次進行相同的哈希計算
- 得到哈希值之后判斷位數組中的每個元素是否都為 1，如果值都為 1，那么說明這個值存在布隆過濾器當中，如果存在一個值不為 1，說明該元素不在布隆過濾器中
如下圖所示：
結果得到三個 1 ，說明 “cunzai” 是有可能存在的。
為什么說是可能存在，而不是一定存在呢？主要分為以下幾種情況：
因為映射函數本身就是散列函數，散列函數是會有碰撞的情況發生。
- 情況1：一個字符串可能是 “chongtu” 經過相同的三個映射函數運算得到的三個點跟 “xinlang” 是一樣的，這種情況下我們就說出現了誤判
- 情況2： “chongtu” 經過運算得到三個點位上的 1 是兩個不同的變量經過運算后得到的，這也不能證明字符串 “chongtu” 是一定存在的
鑒于上面的情況，不同的字符串可能哈希出來的位置相同，這種情況我們可以適當增加位數組大小或者調整哈希函數。
布隆過濾器判定某個元素存在，小概率會誤判；布隆過濾器判定某個元素不在，則這個元素一定不在。
刪除元素
布隆過濾器對元素的刪除，肯定不可以，會出現問題，比如上面添加元素的 bit 位 5 被兩個變量的哈希值共同覆蓋的情況下，一旦我們刪除其中一個值。例如“xinlang”而將其置位 0，那么下次判斷另一個值例如“baidu”是否存在的話，會直接返回 false，而實際上我們并沒有刪除它，這就導致了誤判的問題。
如何使用布隆過濾器
Google開源的Guava自帶布隆過濾器
首先引入Guava的依賴：
那么，在數據量很大的情況下，效率如何呢？
BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 5000000);for (int i = 0; i < 5000000; i++) {bloomFilter.put(i);}long start = System.nanoTime();if (bloomFilter.mightContain(500000)) {System.out.println("成功過濾到500000");}long end = System.nanoTime();System.out.println("布隆過濾器消耗時間"+(end - start)/1000000L+"毫秒");
成功過濾到500000
布隆過濾器消耗時間0毫秒
- 1
- 2
布隆過濾器消耗時間:0毫秒，有點不敢相信呢，匹配速度是不是很快？
那么，在數據量很大的情況下，1%的誤判率結果如何？
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),5000000,0.01);List<String> list = new ArrayList<>(5000000);for (int i = 0; i < 5000000; i++) {String uuid = UUID.randomUUID().toString();bloomFilter.put(uuid);list.add(uuid);}int mightContainNumber1= 0;NumberFormat percentFormat =NumberFormat.getPercentInstance();percentFormat.setMaximumFractionDigits(2);
3%的誤判率結果如何？
創建一個最多添加 500 個整數的布隆過濾器，并且可以容忍誤判率為百分之一（0.01）
public void bool(){BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(), 500, 0.01);// 判斷指定元素是否存在System.out.println(filter.mightContain(1));System.out.println(filter.mightContain(2));// 將元素添加進布隆過濾器filter.put(1);filter.put(2);// 判斷指定元素是否存在System.out.println(filter.mightContain(1));System.out.println(filter.mightContain(2));}
從上面的結果可以看出：
- 如果元素實際存在，那么布隆過濾器一定會判斷存在
- 誤判率即fpp在3%左右，隨著for循環的次數越大，而且越接近3%，那么如果元素不存在，那么布隆過濾器可能會判斷存在
看源碼可知這個3%的fpp是Guava中默認的fpp
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}
- 1
- 2
- 3
如下地址是一個免費的在線布隆過濾器在線計算的網址：
點擊這里
經過哈希計算次數設置為3次，這個3%的誤判率和3次哈希運算需要多大空間位數組呢？
計算得到的結果是984.14KiB，100W的key才占用了0.98M，而如果是10億呢，計算的結果是960M，這個內存空間是完全可以接受的。
Guava 提供的布隆過濾器的實現還是很不錯的，但是它有一個重大的缺陷就是只能單機使用（另外，容量擴展也不容易），而現在互聯網一般都是分布式的場景。為了解決這個問題就需要用到Redis中的布隆過濾器了。
Redis實現布隆過濾器
Redis中配置布隆過濾器
1、點擊https://redis.io/modules 找到RedisBloom
2、點擊進去下載RedisBloom-master.zip文件，上傳到linux
3、解壓縮剛才的RedisBloom文件
unzip RedisBloom-master.zip
cd RedisBloom-master
- 1
- 2
編譯安裝
make
- 1
make完生成redisbloom.so，拷貝到redis的安裝目錄。
cp redisbloom.so /home/www/server/redis
- 1
在redis.conf配置文件中加入如RedisBloom的redisbloom.so文件的地址,如果是集群則每個配置文件中都需要加入redisbloom.so文件的地址
loadmodule /home/www/server/redis/redisbloom.so
- 1
保存以后重啟redis服務
redis-server redis.conf --loadmodule /home/www/server/redis/redisbloom.so
- 1
上面我們有提到需要重啟Redis，在本地和測試環境還可以，但是正式環境能不重啟就不需要重啟，那這么做可以不重啟Redis，使用module load命令執行。
> MODULE LOAD /home/www/server/redis/redisbloom.so
> module list
1) 1) "name"2) "bf"3) "ver"4) (integer) 999999
- 1
- 2
- 3
- 4
- 5
- 6
看到以上數據則說明redisbloom加載成功了，模塊名name為"bf"，模塊版本號ver為999999。
Redis中布隆過濾器指令使用
使用布隆過濾器完整指令請到官網查看： 點擊這里
自定義參數
- bf.reserve {key} {error_rate} {capacity}
- 使用給定的期望錯誤率和初始容量創建空的布隆過濾器
- 參數說明：
- key：布隆過濾器的key
- error_rate：期望的錯誤率（False Positive Rate），該值必須介于0和1之間。該值越小，BloomFilter的內存占用量越大，CPU使用率越高
- capacity：布隆過濾器的初始容量，即期望添加到布隆過濾器中的元素的個數。當實際添加的元素個數超過該值時，布隆過濾器將進行自動的擴容，該過程會導致性能有所下降，下降的程度是隨著元素個數的指數級增長而線性下降
- 返回值：
- 成功：OK
- 其它情況返回相應的異常信息
基本操作
- bf.add {key} {item}
- 添加單個元素
- 參數說明：
- key：布隆過濾器的名字
- item：待插入過濾器的元素
- 返回值：
- 元素不存在插入成功：返回1
- 元素可能已經存在：返回0
- 其它情況返回相應的異常信息
- bf.madd {key} {item} [item...]
- 添加多個元素
- 參數說明：
- key：布隆過濾器的名字
- item：待插入過濾器的元素，可插入多個
- 返回值：
- 成功：返回一個數組，數組的每一個元素可能為1或0，當item一定不存在時數組元素值為1，當item可能已經存在時數組元素值為0
- 其它情況返回相應的異常信息
- bf.exists{key} {item}
- 判斷單個元素是否存在
- 參數說明：
- key：布隆過濾器的名字
- item：待檢查的元素
- 返回值：
- 元素一定不存在：0
- 元素可能存在：1
- 其它情況返回相應的異常信息
- bf.mexists{key} {item} [item...]
- 判斷多個元素是否存在
- 參數說明：
- key：布隆過濾器的名字
- item：待檢查的元素
- 返回值：
- 元素一定不存在：0
- 元素可能存在：1
- 其它情況返回相應的異常信息
- bf.insert{key} [CAPACITY {cap}] [ERROR {ERROR}] [NOCREATE] ITEMS {item…}
- 向key指定的Bloom中添加多個元素，添加時可以指定大小和錯誤率，且可以控制在Bloom不存在的時候是否自動創建
- 參數說明：
- key：布隆過濾器的名字
- CAPACITY：如果過濾器已創建，則此參數將被忽略
- ERROR：如果過濾器已創建，則此參數將被忽略
- expansion：布隆過濾器會自動創建一個子過濾器，子過濾器的大小是上一個過濾器大小乘以expansion。expansion的默認值是2，也就是說布隆過濾器擴容默認是2倍擴容。
- NOCREATE：如果設置了該參數，當布隆過濾器不存在時則不會被創建。用于嚴格區分過濾器的創建和元素插入場景。該參數不能與CAPACITY和ERROR同時設置。
- NONSCALING：設置此項后，當添加到布隆過濾器中的數據達到初始容量后，不會擴容過濾器，并且會拋出異常（(error) ERR non scaling filter is full）。
- ITEMS：待插入過濾器的元素列表，該參數必傳。
- 返回值：
- 成功：返回一個數組，數組的每一個元素可能為1或0，當item一定不存在時數組元素值為1，當item可能已經存在時數組元素值為0
- 其它情況返回相應的異常信息
127.0.0.1:6379> bf.insert name items zhangsan1 zhangsan2 zhangsan3
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.insert name items zhangsan1 zhangsan2 zhangsan3
1) (integer) 0
2) (integer) 0
3) (integer) 0
127.0.0.1:6379> bf.insert name capacity 10000 error 0.00001 nocreate items zhangsan1 zhangsan2 zhangsan3
1) (integer) 0
2) (integer) 0
3) (integer) 0
127.0.0.1:6379>
127.0.0.1:6379> bf.insert name capacity 10000 error 0.00001 nocreate items zhangsan4 zhangsan5 zhangsan6
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- bf.scandump {key} {item}
- 對布隆過濾器進行增量持久化操作
- 參數說明：
- key：布隆過濾器的名字
- item：首次調用傳值0，或者上次調用此命令返回的結果值
- 返回值：
- 返回連續的(iter, data)對，直到(0,NULL)，表示DUMP完成
- 其它情況返回相應的異常信息
- bf.scandump {key} {item}
- 對布隆過濾器進行增量持久化操作
- 參數說明：
- key：布隆過濾器的名字
- item：首次調用傳值0，或者上次調用此命令返回的結果值
- 返回值：
- 返回連續的(iter, data)對，直到(0,NULL)，表示DUMP完成
- 其它情況返回相應的異常信息
- bf.info {key}
- 返回布隆過濾器的相關信息
- 參數說明：
- key：布隆過濾器的名字
- 返回值：
- Capacity：預設容量
- Size：實際占用情況，但如何計算待進一步確認
- Number of filters：過濾器層數
- Number of items inserted：已經實際插入的元素數量
- Expansion rate：子過濾器擴容系數（默認2）
- bf.debug{key}
- 查看布隆過濾器的內部詳細信息
- 參數說明：
- key：布隆過濾器的名字
- 返回值：
- size：布隆過濾器中已插入的元素數量
- 每層BloomFilter的詳細信息
- bytes：占用字節數量
- bits：占用bit位數量，bits = bytes * 8
- shashes：該層hash函數數量
- hashwidth：hash函數寬度
- capacity：該層容量（第一層為BloomFilter初始化時設置的容量，第2層容量 = 第一層容量 * expansion，以此類推）
- size：該層中已插入的元素數量（各層size之和等于BloomFilter中已插入的元素數量size）
- ratio：該層錯誤率（第一層的錯誤率 = BloomFilter初始化時設置的錯誤率 * 0.5，第二層為第一層的0.5倍，以此類推，ratio與expansion無關）
#創建一個容量為5的布隆過濾器，其key為“name”；
127.0.0.1:6379> bf.reserve name0.1 5
OK
編寫代碼測試
public void patchingConsum(ConsumPatchingVO vo) throws ParseException {Config config = new Config();SingleServerConfig singleServerConfig = config.useSingleServer();singleServerConfig.setAddress("redis://127.0.0.1:6379");singleServerConfig.setPassword("123456");RedissonClient redissonClient = Redisson.create(config);RBloomFilter<String> bloom = redissonClient.getBloomFilter("name");// 初始化布隆過濾器； 大小:100000，誤判率:0.01bloom.tryInit(100000L, 0.01);// 新增10萬條數據for(int i=0;i<100000;i++) {bloom.add("name" + i);}// 判斷不存在于布隆過濾器中的元素List<String> notExistList = new ArrayList<>();for(int i=0;i<100000;i++) {String str = "name" + i;boolean notExist = bloom.contains(str);if (notExist) {notExistList.add(str);}}if ($.isNotEmpty(notExistList) && notExistList.size() > 0 ) {System.out.println("誤判次數:"+notExistList.size());}
