Boolean Filter布隆過濾器

前言

boolean 過濾器，顧名思義就是用來資料過濾，主要用來判斷資料是否存在，經常用在redis 中，防止緩存失效，造成雪崩

Boolean Filter

• 布隆過濾器是一個叫“布隆”的人提出的，它本身是一個很長的二進制向量，存儲的資料隻能是0或1
• 由于采用二進制向量存儲(存儲結構與bitmap類似)，隻能存儲狀态資料，不存儲中繼資料，非常節省記憶體空間
• 核心：

  判定不在的資料一定不存在，存在的資料不一定存在

  先記住
• 布隆過濾器存在一定的誤判(涉及時間/空間轉換)

應用場景

1. redis 緩存雪崩
2. 資料去重，比如：頭條、抖音看過的内容不會重複出現(排除少量誤判)
3. 涉及大量資料，去重，都可使用布隆

實作邏輯

初始布隆過濾器資料位預設是0

• 查詢world 根據hash 算法，取得資料和前兩個存儲資料有重疊，都是1， 判定資料已存在，但是實際并未存在，有誤差。
• 布隆過濾器，初始長度和容錯率可以自己設定，容量一旦确定不能修改
• 随着資料越來越多，誤判率也會升高，需要定期重新設定過濾器
• 過濾器不允許删除，因為一個資料位可能關聯到多個資料

redis 布隆過濾器

redis4,x 以後提供了boolean，使用的redis5.0.8

• 配置插件

# 下載下傳布隆過濾器的插件
wget https://github.com/RedisLabsModules/rebloom/archive/v1.1.1.tar.gz
# 解壓後在根目錄
make
# redis.conf 配置檔案的添加boolean filter
loadmodule /root/booleanFilter/RedisBloom/rebloom.so
           

• 測試

127.0.0.1:6379> bf.add bf a 
(integer) 1
127.0.0.1:6379> bf.add bf b
(integer) 1
127.0.0.1:6379> bf.exists bf a
(integer) 1
127.0.0.1:6379> bf.exists bf c
(integer) 0
127.0.0.1:6379> bf.madd bf 1 2 3 4
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
127.0.0.1:6379>  bf.mexists bf 1 3 d
1) (integer) 1
2) (integer) 1
3) (integer) 0
127.0.0.1:6379> bf.reserve bf 0.0001 1000 #設定長度和精确度 Boolean fileter 預設長度是 100，容錯是0.01， 已存在布隆過濾，不允許修改
(error) ERR item exists
127.0.0.1:6379> bf.reserve bf1  0.0001 1000
OK
           

Java 使用

• pom

<dependency>
	<groupId>com.redislabs</groupId>
    <artifactId>jrebloom</artifactId>
    <version>1.2.0</version>
</dependency>
           

• 實作

public class BooleanFilterTest

@Test
public void testBf{
        Client bloomClient = new Client("127.0.0.1",6390);
        bloomClient.add("bf01","a");
        bloomClient.add("bf01","b");
        bloomClient.add("bf01","c");
        System.out.println("判斷是否存在 :"+bloomClient.exists("bf02","c"));
        bloomClient.createFilter("bf03",10000,0.001);
    }
}
           

總結

• 布隆過濾器隻能判斷資料一定不存在，不能判斷不存在
• 布隆過濾器的初始值估計過大，會浪費空間，估計的過小就會影響準确率，使用之前一定要盡可能的精确估計元素的數量，還需要加上一定的備援空間避免實踐元素過多導緻的準确率影響
• 布隆過濾器的fpp(誤差)越小，需要的空間就越大，對于不需要特别精确的場合，可以稍微大一些
• 使用的時候不要讓實際資料大于初始化大小，當實際元素超出初始化大小時，應該對布隆過濾器進行重建，重新配置設定一個size更大的布隆過濾器，将所有資料再批量add進去