一. 背景

在業(yè)務(wù)開發(fā)中，在并發(fā)量很高的情況下，通常會使用緩存對系統(tǒng)查詢性能進行優(yōu)化，在緩存命中率很高的情況下，緩存的使用能夠大幅提升系統(tǒng)查詢性能。但是在緩存命中率非常低場景下，如果采用傳統(tǒng)緩存讀取模式，大部分的請求會穿透至數(shù)據(jù)庫，造成數(shù)據(jù)庫的巨大壓力。

例如：最近上線一個“貴族”功能，由于貴族價格比較貴，擁有比較強的特權(quán)，該功能也主要面向平臺頭部大R用戶，所以如果采用傳統(tǒng)的緩存模式，查詢一個用戶的貴族信息就會大概率出現(xiàn)緩存無法命中去讀庫的情況。

有些同學可能會將“空結(jié)果”緩存至數(shù)據(jù)庫，這樣下次去查詢該用戶的結(jié)果時就會命中緩存。但是由于平臺巨大的用戶量，如果將所有用戶的空結(jié)果進行緩存成本是非常高的。

此種場景就非常適合使用布隆過濾器去解決緩存命中率低的問題。

二. 什么是布隆過濾器

本質(zhì)上布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu)，比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure），特點是高效地插入和查詢，可以用來告訴你 “某樣?xùn)|西一定不存在或者可能存在”。

相比于傳統(tǒng)的 List、Set、Map 等數(shù)據(jù)結(jié)構(gòu)，它更高效、占用空間更少，但是缺點是其返回的結(jié)果是概率性的，而不是確切的。

2.1 實現(xiàn)原理

布隆過濾器是一個 bit 向量或者說 bit 數(shù)組，長這樣：

如果我們要映射一個值到布隆過濾器中，我們需要使用多個不同的哈希函數(shù)生成**多個哈希值，**并對每個生成的哈希值指向的 bit 位置 1，例如針對值 “baidu” 和三個不同的哈希函數(shù)分別生成了哈希值 0、3、6，則上圖轉(zhuǎn)變?yōu)椋?/p>

Ok，我們現(xiàn)在再存一個值 “tencent”，如果哈希函數(shù)返回 2、3、7 的話，圖繼續(xù)變?yōu)椋?/p>

值得注意的是，3 這個 bit 位由于兩個值的哈希函數(shù)都返回了這個 bit 位，因此它被覆蓋了?，F(xiàn)在我們?nèi)绻氩樵?“dianping” 這個值是否存在，哈希函數(shù)返回了 0、4、7三個值，結(jié)果我們發(fā)現(xiàn) 4 這個 bit 位上的值為 0，說明沒有任何一個值映射到這個 bit 位上，因此我們可以很確定地說 “dianping” 這個值不存在。而當我們需要查詢 “baidu” 這個值是否存在的話，那么哈希函數(shù)必然會返回 0、3、6，然后我們檢查發(fā)現(xiàn)這三個 bit 位上的值均為 1，那么我們可以說 “baidu” 存在了么？答案是不可以，只能是 “baidu” 這個值可能存在。

這是為什么呢？答案跟簡單，因為隨著增加的值越來越多，被置為 1 的 bit 位也會越來越多，這樣某個值 “taobao” 即使沒有被存儲過，但是萬一哈希函數(shù)返回的三個 bit 位都被其他值置位了 1 ，那么程序還是會判斷 “taobao” 這個值存在。

2.2 支持刪除么

傳統(tǒng)的布隆過濾器并不支持刪除操作。但是名為 Counting Bloom filter 的變種可以用來測試元素計數(shù)個數(shù)是否絕對小于某個閾值，它支持元素刪除。可以參考文章 Counting Bloom Filter 的原理和實現(xiàn)

2.3 如何選擇哈希函數(shù)個數(shù)和布隆過濾器長度

很顯然，過小的布隆過濾器很快所有的 bit 位均為 1，那么查詢?nèi)魏沃刀紩祷亍翱赡艽嬖凇保鸩坏竭^濾的目的了。布隆過濾器的長度會直接影響誤報率，布隆過濾器越長其誤報率越小。

另外，哈希函數(shù)的個數(shù)也需要權(quán)衡，個數(shù)越多則布隆過濾器 bit 位置位 1 的速度越快，且布隆過濾器的效率越低；但是如果太少的話，那我們的誤報率會變高。

k 為哈希函數(shù)個數(shù)，m 為布隆過濾器長度，n 為插入的元素個數(shù)，p 為誤報率

四. 布隆過濾器實現(xiàn)

4.1 guava

Google提供的guava包里面也提供了布隆過濾器,引入pom文件：

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

具體的實現(xiàn)調(diào)用的代碼如下，同樣可以指定具體的存儲數(shù)量以及預(yù)計的誤判率：

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class GuavaBloomFilter {
    public static void main(String[] args) {
        BloomFilter<String> bloomFilter = BloomFilter.create(
                Funnels.stringFunnel(Charsets.UTF_8),1000000,0.04);

        bloomFilter.put("Sam");

        System.out.println(bloomFilter.mightContain("Jane"));
        System.out.println(bloomFilter.mightContain("Sam"));
    }
}

由于guava的布隆過濾器是緩存在本地的，所以在分布式環(huán)境中并不能很好的使用。

4.2 redisson

Redisson利用Redis實現(xiàn)了Java分布式的布隆過濾器。因此，在多個JVM節(jié)點上或者是其他進程里面，Redisson可以通過同一個Key獲取到布隆過濾器。

public class BloomFilterTest extends BaseTest {

    @Autowired
    private RedissonClient redisson;

    @Test
    public void test() {
        RBloomFilter<Object> bloomFilter = redisson.getBloomFilter("bloomTest");
        bloomFilter.tryInit(5000000L,0.03);
        System.out.println(bloomFilter.contains("2"));
        bloomFilter.add("2");
        System.out.println(bloomFilter.contains("2"));
    }
}

五. 布隆過濾器在緩存系統(tǒng)中的實踐

查詢流程：

布隆過濾器維護流程：