簡介

英語：(Bloom Filter)是 1970 年由布隆提出的。它實(shí)際上是一個(gè)很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。主要用于判斷一個(gè)元素是否在一個(gè)集合中。

布隆過濾器原理

當(dāng)一個(gè)元素加入布隆過濾器中的時(shí)候，會(huì)進(jìn)行如下操作：

1. 使用布隆過濾器中的哈希函數(shù)對(duì)元素值進(jìn)行計(jì)算，得到哈希值（有幾個(gè)哈希函數(shù)得到幾個(gè)哈希值）。
2. 根據(jù)得到的哈希值，在位數(shù)組中把對(duì)應(yīng)下標(biāo)的值置為 1。

當(dāng)我們需要判斷一個(gè)元素是否存在于布隆過濾器的時(shí)候，會(huì)進(jìn)行如下操作：

1. 對(duì)給定元素再次進(jìn)行相同的哈希計(jì)算；
2. 得到值之后判斷位數(shù)組中的每個(gè)元素是否都為 1，如果值都為 1，那么說明這個(gè)值在布隆過濾器中，如果存在一個(gè)值不為 1，說明該元素不在布隆過濾器中。

舉個(gè)簡單的例子：

布隆過濾器初始狀態(tài).png

元素添加到布隆過濾器.png

查詢某個(gè)變量的時(shí)候我們只要看看這些點(diǎn)是不是都是 1 就可以大概率知道集合中有沒有它了

1. 如果這些點(diǎn)有任何一個(gè) 0，則被查詢變量一定不在；
2. 如果都是 1，則被查詢變量很可能存在；
   為什么說是可能存在，而不是一定存在呢？那是因?yàn)橛成浜瘮?shù)本身就是散列函數(shù)，散列函數(shù)是會(huì)有碰撞的。

• 誤判率
  布隆過濾器的誤判是指多個(gè)輸入經(jīng)過哈希之后在相同的bit位置1了，這樣就無法判斷究竟是哪個(gè)輸入產(chǎn)生的，因此誤判的根源在于相同的 bit 位被多次映射且置 1。
  這種情況也造成了布隆過濾器的刪除問題，因?yàn)椴悸∵^濾器的每一個(gè) bit 并不是獨(dú)占的，很有可能多個(gè)元素共享了某一位。如果我們直接刪除這一位的話，會(huì)影響其他的元素。(比如上圖中的第 3 位)

布隆過濾器使用場(chǎng)景

1. 判斷給定數(shù)據(jù)是否存在：比如判斷一個(gè)數(shù)字是否在于包含大量數(shù)字的數(shù)字集中（數(shù)字集很大，5億以上！）、 防止緩存穿透（判斷請(qǐng)求的數(shù)據(jù)是否有效避免直接繞過緩存請(qǐng)求數(shù)據(jù)庫）、郵箱的垃圾郵件過濾、黑名單功能等等；
2. 去重：比如爬給定網(wǎng)址的時(shí)候?qū)σ呀?jīng)爬取過的 URL 去重；

代碼示例

pom.xml引入依賴：

<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>23.0</version>
</dependency>

public class GuavaBloomFilterDemo {
    public static void main(String[] args) {
        // 后邊兩個(gè)參數(shù)：預(yù)計(jì)包含的數(shù)據(jù)量，和允許的誤差值
        BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 100000, 0.01);
        for (int i = 0; i < 100000; i++) {
            bloomFilter.put(i);
        }
        System.out.println(bloomFilter.mightContain(1));
        System.out.println(bloomFilter.mightContain(2));
        System.out.println(bloomFilter.mightContain(3));
        System.out.println(bloomFilter.mightContain(100001));

        //bloomFilter.writeTo();
    }
}

Guava 提供的布隆過濾器的實(shí)現(xiàn)還是很不錯(cuò)的（想要詳細(xì)了解的可以看一下它的源碼實(shí)現(xiàn)），但是它有一個(gè)重大的缺陷就是只能單機(jī)使用（另外，容量擴(kuò)展也不容易），而現(xiàn)在互聯(lián)網(wǎng)一般都是分布式的場(chǎng)景。為了解決這個(gè)問題，我們就需要用到 Redis 中的布隆過濾器了。

Redis 中的 BloomFilter

Redis v4.0 之后有了 Module（模塊/插件） 功能，Redis Modules 讓 Redis 可以使用外部模塊擴(kuò)展其功能 。布隆過濾器就是其中的 Module。詳情可以查看 Redis 官方對(duì) Redis Modules 的介紹 ：https://redis.io/modules。
在已安裝 Redis 的前提下，安裝 RedisBloom，有兩種方式:

• 直接編譯進(jìn)行安裝

  git clone https://github.com/RedisBloom/RedisBloom.git
  cd RedisBloom
  make     #編譯 會(huì)生成一個(gè)rebloom.so文件
  redis-server --loadmodule /path/to/rebloom.so   #運(yùn)行redis時(shí)加載布隆過濾器模塊
  redis-cli    # 啟動(dòng)連接容器中的 redis 客戶端驗(yàn)證
  

• 使用Docker進(jìn)行安裝

  docker pull redislabs/rebloom:latest # 拉取鏡像
  docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest # 運(yùn)行容器
  docker exec -it redis-redisbloom bash
  redis-cli
  

• 常用命令一覽
  注意： key:布隆過濾器的名稱，item : 添加的元素。

  1. BF.ADD ：將元素添加到布隆過濾器中，如果該過濾器尚不存在，則創(chuàng)建該過濾器。格式：BF.ADD {key} {item}。
  2. BF.MADD : 將一個(gè)或多個(gè)元素添加到“布隆過濾器”中，并創(chuàng)建一個(gè)尚不存在的過濾器。該命令的操作方式BF.ADD與之相同，只不過它允許多個(gè)輸入并返回多個(gè)值。格式：BF.MADD {key} {item} [item ...] 。
  3. **BF.EXISTS ** : 確定元素是否在布隆過濾器中存在。格式：BF.EXISTS {key} {item}。
  4. BF.MEXISTS ： 確定一個(gè)或者多個(gè)元素是否在布隆過濾器中存在格式：BF.MEXISTS {key} {item} [item ...]。
     BF.RESERVE需要單獨(dú)介紹：
     格式 BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion]

簡單介紹一下每個(gè)參數(shù)的具體含義：
1. key：布隆過濾器的名稱
2. error_rate :誤報(bào)的期望概率。這應(yīng)該是介于0到1之間的十進(jìn)制值。例如，對(duì)于期望的誤報(bào)率0.1％（1000中為1），error_rate應(yīng)該設(shè)置為0.001。該數(shù)字越接近零，則每個(gè)項(xiàng)目的內(nèi)存消耗越大，并且每個(gè)操作的CPU使用率越高。
3. capacity: 過濾器的容量。當(dāng)實(shí)際存儲(chǔ)的元素個(gè)數(shù)超過這個(gè)值之后，性能將開始下降。實(shí)際的降級(jí)將取決于超出限制的程度。隨著過濾器元素?cái)?shù)量呈指數(shù)增長，性能將線性下降。

可選參數(shù)：
1. expansion：如果創(chuàng)建了一個(gè)新的子過濾器，則其大小將是當(dāng)前過濾器的大小乘以expansion。默認(rèn)擴(kuò)展值為2。這意味著每個(gè)后續(xù)子過濾器將是前一個(gè)子過濾器的兩倍。

• Redis bloom demo

// 使用Redisson實(shí)現(xiàn)
public class RedissonBloomFilterDemo {
    public static void main(String[] args) {
        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");
        RedissonClient redisson = Redisson.create(config);
        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("user");
        // 初始化布隆過濾器，預(yù)計(jì)統(tǒng)計(jì)元素?cái)?shù)量為55000000，期望誤差率為0.03
        bloomFilter.tryInit(55000000L, 0.03);
        bloomFilter.add("Tom");
        bloomFilter.add("Jack");
        System.out.println(bloomFilter.count());   // 2
        System.out.println(bloomFilter.contains("Tom"));  // true
        System.out.println(bloomFilter.contains("Linda"));  // false
    }
}

總結(jié)

1. 一個(gè)元素如果判斷結(jié)果為存在的時(shí)候元素不一定存在；
2. 但是判斷結(jié)果為不存在的時(shí)候則一定不存在；
3. 布隆過濾器可以添加元素，但是不能刪除元素；

————————————————————
坐標(biāo)帝都，白天上班族，晚上是知識(shí)的分享者
如果讀完覺得有收獲的話，歡迎點(diǎn)贊加關(guān)注