什么是 BloomFilter

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

通常我們會(huì)遇到很多要判斷一個(gè)元素是否在某個(gè)集合中的業(yè)務(wù)場(chǎng)景侮邀，一般想到的是將集合中所有元素保存起來念链，然后通過比較確定盼忌。鏈表、樹掂墓、散列表（又叫哈希表谦纱，Hash table）等等數(shù)據(jù)結(jié)構(gòu)都是這種思路。但是隨著集合中元素的增加君编，我們需要的存儲(chǔ)空間也會(huì)呈現(xiàn)線性增長跨嘉，最終達(dá)到瓶頸。同時(shí)檢索速度也越來越慢吃嘿，上述三種結(jié)構(gòu)的檢索時(shí)間復(fù)雜度分別為祠乃，，兑燥。

這個(gè)時(shí)候亮瓷，布隆過濾器（Bloom Filter）就應(yīng)運(yùn)而生。

布隆過濾器原理

了解布隆過濾器原理之前降瞳，先回顧下 Hash 函數(shù)原理嘱支。

哈希函數(shù)

哈希函數(shù)的概念是：將任意大小的輸入數(shù)據(jù)轉(zhuǎn)換成特定大小的輸出數(shù)據(jù)的函數(shù)，轉(zhuǎn)換后的數(shù)據(jù)稱為哈希值或哈希編碼挣饥，也叫散列值斗塘。下面是一幅示意圖：

布隆過濾器，我也是個(gè)搞過十億級(jí)數(shù)據(jù)的人兒

所有散列函數(shù)都有如下基本特性：

如果兩個(gè)散列值是不相同的（根據(jù)同一函數(shù)）亮靴，那么這兩個(gè)散列值的原始輸入也是不相同的馍盟。這個(gè)特性是散列函數(shù)具有確定性的結(jié)果，具有這種性質(zhì)的散列函數(shù)稱為單向散列函數(shù)茧吊。
散列函數(shù)的輸入和輸出不是唯一對(duì)應(yīng)關(guān)系的贞岭，如果兩個(gè)散列值相同八毯，兩個(gè)輸入值很可能是相同的，但也可能不同瞄桨，這種情況稱為“散列碰撞（collision）”话速。

但是用 hash表存儲(chǔ)大數(shù)據(jù)量時(shí)，空間效率還是很低芯侥，當(dāng)只有一個(gè) hash 函數(shù)時(shí)泊交，還很容易發(fā)生哈希碰撞。

布隆過濾器數(shù)據(jù)結(jié)構(gòu)

BloomFilter 是由一個(gè)固定大小的二進(jìn)制向量或者位圖（bitmap）和一系列映射函數(shù)組成的柱查。

在初始狀態(tài)時(shí)廓俭，對(duì)于長度為 m 的位數(shù)組，它的所有位都被置為0唉工，如下圖所示：

[圖片上傳失敗...(image-303c04-1595324887187)]

當(dāng)有變量被加入集合時(shí)研乒，通過 K 個(gè)映射函數(shù)將這個(gè)變量映射成位圖中的 K 個(gè)點(diǎn)，把它們置為 1（假定有兩個(gè)變量都通過 3 個(gè)映射函數(shù)）淋硝。

布隆過濾器雹熬，我也是個(gè)搞過十億級(jí)數(shù)據(jù)的人兒

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

如果這些點(diǎn)有任何一個(gè) 0，則被查詢變量一定不在谣膳；
如果都是 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 位)

特性

一個(gè)元素如果判斷結(jié)果為存在的時(shí)候元素不一定存在，但是判斷結(jié)果為不存在的時(shí)候則一定不存在纽帖。
布隆過濾器可以添加元素宠漩，但是不能刪除元素。因?yàn)閯h掉元素會(huì)導(dǎo)致誤判率增加懊直。

添加與查詢?cè)夭襟E

添加元素

將要添加的元素給 k 個(gè)哈希函數(shù)
得到對(duì)應(yīng)于位數(shù)組上的 k 個(gè)位置
將這k個(gè)位置設(shè)為 1

查詢?cè)?/h1>

將要查詢的元素給k個(gè)哈希函數(shù)

得到對(duì)應(yīng)于位數(shù)組上的k個(gè)位置

如果k個(gè)位置有一個(gè)為 0扒吁，則肯定不在集合中

如果k個(gè)位置全部為 1，則可能在集合中

優(yōu)點(diǎn)

相比于其它的數(shù)據(jù)結(jié)構(gòu)室囊，布隆過濾器在空間和時(shí)間方面都有巨大的優(yōu)勢(shì)雕崩。布隆過濾器存儲(chǔ)空間和插入/查詢時(shí)間都是常數(shù) 魁索，另外，散列函數(shù)相互之間沒有關(guān)系盼铁，方便由硬件并行實(shí)現(xiàn)粗蔚。布隆過濾器不需要存儲(chǔ)元素本身，在某些對(duì)保密要求非常嚴(yán)格的場(chǎng)合有優(yōu)勢(shì)饶火。

布隆過濾器可以表示全集鹏控，其它任何數(shù)據(jù)結(jié)構(gòu)都不能；

缺點(diǎn)

但是布隆過濾器的缺點(diǎn)和優(yōu)點(diǎn)一樣明顯肤寝。誤算率是其中之一当辐。隨著存入的元素?cái)?shù)量增加，誤算率隨之增加醒陆。但是如果元素?cái)?shù)量太少瀑构，則使用散列表足矣裆针。

另外刨摩，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位數(shù)組變成整數(shù)數(shù)組世吨，每插入一個(gè)元素相應(yīng)的計(jì)數(shù)器加 1, 這樣刪除元素時(shí)將計(jì)數(shù)器減掉就可以了澡刹。然而要保證安全地刪除元素并非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器里面耘婚。這一點(diǎn)單憑這個(gè)過濾器是無法保證的罢浇。另外計(jì)數(shù)器回繞也會(huì)造成問題。

在降低誤算率方面沐祷，有不少工作嚷闭，使得出現(xiàn)了很多布隆過濾器的變種。

布隆過濾器使用場(chǎng)景和實(shí)例

在程序的世界中赖临，布隆過濾器是程序員的一把利器胞锰，利用它可以快速地解決項(xiàng)目中一些比較棘手的問題。

如網(wǎng)頁 URL 去重兢榨、垃圾郵件識(shí)別嗅榕、大集合中重復(fù)元素的判斷和緩存穿透等問題。

布隆過濾器的典型應(yīng)用有：

數(shù)據(jù)庫防止穿庫吵聪。Google Bigtable凌那，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter來減少不存在的行或列的磁盤查找。避免代價(jià)高昂的磁盤查找會(huì)大大提高數(shù)據(jù)庫查詢操作的性能吟逝。
業(yè)務(wù)場(chǎng)景中判斷用戶是否閱讀過某視頻或文章帽蝶，比如抖音或頭條躺酒，當(dāng)然會(huì)導(dǎo)致一定的誤判巡莹，但不會(huì)讓用戶看到重復(fù)的內(nèi)容蘑志。
緩存宕機(jī)址否、緩存擊穿場(chǎng)景，一般判斷用戶是否在緩存中麦锯，如果在則直接返回結(jié)果恕稠，不在則查詢db，如果來一波冷數(shù)據(jù)扶欣，會(huì)導(dǎo)致緩存大量擊穿鹅巍，造成雪崩效應(yīng)，這時(shí)候可以用布隆過濾器當(dāng)緩存的索引料祠，只有在布隆過濾器中骆捧，才去查詢緩存，如果沒查詢到髓绽，則穿透到db敛苇。如果不在布隆器中，則直接返回顺呕。
WEB攔截器枫攀，如果相同請(qǐng)求則攔截，防止重復(fù)被攻擊株茶。用戶第一次請(qǐng)求来涨，將請(qǐng)求參數(shù)放入布隆過濾器中，當(dāng)?shù)诙握?qǐng)求時(shí)启盛，先判斷請(qǐng)求參數(shù)是否被布隆過濾器命中蹦掐。可以提高緩存命中率僵闯。Squid 網(wǎng)頁代理緩存服務(wù)器在 cache digests 中就使用了布隆過濾器卧抗。Google Chrome瀏覽器使用了布隆過濾器加速安全瀏覽服務(wù)
Venti 文檔存儲(chǔ)系統(tǒng)也采用布隆過濾器來檢測(cè)先前存儲(chǔ)的數(shù)據(jù)。
SPIN 模型檢測(cè)器也使用布隆過濾器在大規(guī)模驗(yàn)證問題時(shí)跟蹤可達(dá)狀態(tài)空間鳖粟。

Coding~

知道了布隆過濾器的原理和使用場(chǎng)景社裆，我們可以自己實(shí)現(xiàn)一個(gè)簡單的布隆過濾器

自定義的 BloomFilter

public class MyBloomFilter {
    /**
     * 一個(gè)長度為10 億的比特位
     */
    private static final int DEFAULT_SIZE = 256 << 22;
    /**
     * 為了降低錯(cuò)誤率，使用加法hash算法牺弹，所以定義一個(gè)8個(gè)元素的質(zhì)數(shù)數(shù)組
     */
    private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};
    /**
     * 相當(dāng)于構(gòu)建 8 個(gè)不同的hash算法
     */
    private static HashFunction[] functions = new HashFunction[seeds.length];
    /**
     * 初始化布隆過濾器的 bitmap
     */
    private static BitSet bitset = new BitSet(DEFAULT_SIZE);
    /**
     * 添加數(shù)據(jù)
     *
     * @param value 需要加入的值
     */
    public static void add(String value) {
        if (value != null) {
            for (HashFunction f : functions) {
                //計(jì)算 hash 值并修改 bitmap 中相應(yīng)位置為 true
                bitset.set(f.hash(value), true);
            }
        }
    }
    /**
     * 判斷相應(yīng)元素是否存在
     * @param value 需要判斷的元素
     * @return 結(jié)果
     */
    public static boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (HashFunction f : functions) {
            ret = bitset.get(f.hash(value));
            //一個(gè) hash 函數(shù)返回 false 則跳出循環(huán)
            if (!ret) {
                break;
            }
        }
        return ret;
    }
    /**
     * 模擬用戶是不是會(huì)員浦马，或用戶在不在線。张漂。晶默。
     */
    public static void main(String[] args) {
        for (int i = 0; i < seeds.length; i++) {
            functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
        }
        // 添加1億數(shù)據(jù)
        for (int i = 0; i < 100000000; i++) {
            add(String.valueOf(i));
        }
        String id = "123456789";
        add(id);
        System.out.println(contains(id));   // true
        System.out.println("" + contains("234567890"));  //false
    }
}
class HashFunction {
    private int size;
    private int seed;
    public HashFunction(int size, int seed) {
        this.size = size;
        this.seed = seed;
    }
    public int hash(String value) {
        int result = 0;
        int len = value.length();
        for (int i = 0; i < len; i++) {
            result = seed * result + value.charAt(i);
        }
        int r = (size - 1) & result;
        return (size - 1) & result;
    }
}

What？我們寫的這些早有大牛幫我們實(shí)現(xiàn)航攒，還造輪子磺陡，真是浪費(fèi)時(shí)間，No，No币他，No坞靶，我們學(xué)習(xí)過程中是可以造輪子的，造輪子本身就是我們自己對(duì)設(shè)計(jì)和實(shí)現(xiàn)的具體落地過程蝴悉，不僅能提高我們的編程能力彰阴，在造輪子的過程中肯定會(huì)遇到很多我們沒有思考過的問題，成長看的見~~

實(shí)際項(xiàng)目使用的時(shí)候拍冠，領(lǐng)導(dǎo)和我說項(xiàng)目一定要穩(wěn)定運(yùn)行尿这，沒自信的我放棄了自己的輪子。

Guava 中的 BloomFilter

<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();
    }
}

分布式環(huán)境中射众，布隆過濾器肯定還需要考慮是可以共享的資源，這時(shí)候我們會(huì)想到 Redis晃财，是的叨橱，Redis 也實(shí)現(xiàn)了布隆過濾器。

當(dāng)然我們也可以把布隆過濾器通過 bloomFilter.writeTo() 寫入一個(gè)文件断盛，放入OSS罗洗、S3這類對(duì)象存儲(chǔ)中。

Redis 中的 BloomFilter

Redis 提供的 bitMap 可以實(shí)現(xiàn)布隆過濾器郑临，但是需要自己設(shè)計(jì)映射函數(shù)和一些細(xì)節(jié)栖博，這和我們自定義沒啥區(qū)別屑宠。

Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之后才正式登場(chǎng)厢洞。布隆過濾器作為一個(gè)插件加載到 Redis Server 中，給 Redis 提供了強(qiáng)大的布隆去重功能典奉。

在已安裝 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

使用

布隆過濾器基本指令：

bf.add 添加元素到布隆過濾器
bf.exists 判斷元素是否在布隆過濾器
bf.madd 添加多個(gè)元素到布隆過濾器卫玖，bf.add 只能添加一個(gè)
bf.mexists 判斷多個(gè)元素是否在布隆過濾器

127.0.0.1:6379> bf.add user Tom
(integer) 1
127.0.0.1:6379> bf.add user John
(integer) 1
127.0.0.1:6379> bf.exists user Tom
(integer) 1
127.0.0.1:6379> bf.exists user Linda
(integer) 0
127.0.0.1:6379> bf.madd user Barry Jerry Mars
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists user Barry Linda
1) (integer) 1
2) (integer) 0

我們只有這幾個(gè)參數(shù)公你，肯定不會(huì)有誤判，當(dāng)元素逐漸增多時(shí)假瞬，就會(huì)有一定的誤判了陕靠，這里就不做這個(gè)實(shí)驗(yàn)了。

上面使用的布隆過濾器只是默認(rèn)參數(shù)的布隆過濾器脱茉，它在我們第一次 add 的時(shí)候自動(dòng)創(chuàng)建剪芥。

Redis 還提供了自定義參數(shù)的布隆過濾器，bf.reserve 過濾器名 error_rate initial_size

error_rate：允許布隆過濾器的錯(cuò)誤率琴许，這個(gè)值越低過濾器的位數(shù)組的大小越大税肪，占用空間也就越大
initial_size：布隆過濾器可以儲(chǔ)存的元素個(gè)數(shù)，當(dāng)實(shí)際存儲(chǔ)的元素個(gè)數(shù)超過這個(gè)值之后，過濾器的準(zhǔn)確率會(huì)下降

但是這個(gè)操作需要在 add 之前顯式創(chuàng)建益兄。如果對(duì)應(yīng)的 key 已經(jīng)存在锻梳，bf.reserve 會(huì)報(bào)錯(cuò)

127.0.0.1:6379> bf.reserve user 0.01 100
(error) ERR item exists
127.0.0.1:6379> bf.reserve topic 0.01 1000
OK

我是一名 Javaer，肯定還要用 Java 來實(shí)現(xiàn)的净捅，Java 的 Redis 客戶端比較多疑枯，有些還沒有提供指令擴(kuò)展機(jī)制，筆者已知的 Redisson 和 lettuce 是可以使用布隆過濾器的蛔六，我們這里用 Redisson

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
    }
}

擴(kuò)展

為了解決布隆過濾器不能刪除元素的問題古今，布谷鳥過濾器橫空出世屁魏。論文《Cuckoo Filter：Better Than Bloom》作者將布谷鳥過濾器和布隆過濾器進(jìn)行了深入的對(duì)比。相比布谷鳥過濾器而言布隆過濾器有以下不足：查詢性能弱捉腥、空間利用效率低氓拼、不支持反向操作（刪除）以及不支持計(jì)數(shù)。

布隆過濾器