布隆過濾器，你也可以處理十幾億的大數據

文章收錄在 GitHub JavaKeeper ，N線互聯網開發必備技能兵器譜

什麼是 BloomFilter

布隆過濾器（英語：Bloom Filter）是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。主要用於判斷一個元素是否在一個集合中。

通常我們會遇到很多要判斷一個元素是否在某個集合中的業務場景，一般想到的是將集合中所有元素保存起來，然後通過比較確定。鏈表、樹、散列表（又叫哈希表，Hash table）等等數據結構都是這種思路。但是隨着集合中元素的增加，我們需要的存儲空間也會呈現線性增長，最終達到瓶頸。同時檢索速度也越來越慢，上述三種結構的檢索時間複雜度分別為$O(n)$，$O(logn)$，$O(1)$。

這個時候，布隆過濾器（Bloom Filter）就應運而生。

布隆過濾器原理

了解布隆過濾器原理之前，先回顧下 Hash 函數原理。

哈希函數

哈希函數的概念是：將任意大小的輸入數據轉換成特定大小的輸出數據的函數，轉換後的數據稱為哈希值或哈希編碼，也叫散列值。下面是一幅示意圖：

所有散列函數都有如下基本特性：

  • 如果兩個散列值是不相同的（根據同一函數），那麼這兩個散列值的原始輸入也是不相同的。這個特性是散列函數具有確定性的結果，具有這種性質的散列函數稱為單向散列函數。

  • 散列函數的輸入和輸出不是唯一對應關係的，如果兩個散列值相同，兩個輸入值很可能是相同的，但也可能不同，這種情況稱為「散列碰撞（collision）」。

但是用 hash表存儲大數據量時，空間效率還是很低，當只有一個 hash 函數時，還很容易發生哈希碰撞。

布隆過濾器數據結構

BloomFilter 是由一個固定大小的二進制向量或者位圖（bitmap）和一系列映射函數組成的。

在初始狀態時，對於長度為 m 的位數組，它的所有位都被置為0，如下圖所示：

當有變量被加入集合時，通過 K 個映射函數將這個變量映射成位圖中的 K 個點，把它們置為 1（假定有兩個變量都通過 3 個映射函數）。

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

  • 如果這些點有任何一個 0，則被查詢變量一定不在；
  • 如果都是 1，則被查詢變量很可能存在

為什麼說是可能存在，而不是一定存在呢？那是因為映射函數本身就是散列函數，散列函數是會有碰撞的。

誤判率

布隆過濾器的誤判是指多個輸入經過哈希之後在相同的bit位置1了，這樣就無法判斷究竟是哪個輸入產生的，因此誤判的根源在於相同的 bit 位被多次映射且置 1。

這種情況也造成了布隆過濾器的刪除問題，因為布隆過濾器的每一個 bit 並不是獨佔的，很有可能多個元素共享了某一位。如果我們直接刪除這一位的話，會影響其他的元素。(比如上圖中的第 3 位)

特性

  • 一個元素如果判斷結果為存在的時候元素不一定存在，但是判斷結果為不存在的時候則一定不存在。
  • 布隆過濾器可以添加元素，但是不能刪除元素。因為刪掉元素會導致誤判率增加。

添加與查詢元素步驟

添加元素

  1. 將要添加的元素給 k 個哈希函數
  2. 得到對應於位數組上的 k 個位置
  3. 將這k個位置設為 1

查詢元素

  1. 將要查詢的元素給k個哈希函數
  2. 得到對應於位數組上的k個位置
  3. 如果k個位置有一個為 0，則肯定不在集合中
  4. 如果k個位置全部為 1，則可能在集合中

優點

相比於其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數 $O(K)$，另外，散列函數相互之間沒有關係，方便由硬件並行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。

布隆過濾器可以表示全集，其它任何數據結構都不能；

缺點

但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨着存入的元素數量增加，誤算率隨之增加。但是如果元素數量太少，則使用散列表足矣。

另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位數組變成整數數組，每插入一個元素相應的計數器加 1, 這樣刪除元素時將計數器減掉就可以了。然而要保證安全地刪除元素並非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器裏面。這一點單憑這個過濾器是無法保證的。另外計數器迴繞也會造成問題。

在降低誤算率方面，有不少工作，使得出現了很多布隆過濾器的變種。

布隆過濾器使用場景和實例

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

如網頁 URL 去重、垃圾郵件識別、大集合中重複元素的判斷和緩存穿透等問題。

布隆過濾器的典型應用有：

  • 數據庫防止穿庫。 Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter來減少不存在的行或列的磁盤查找。避免代價高昂的磁盤查找會大大提高數據庫查詢操作的性能。

  • 業務場景中判斷用戶是否閱讀過某視頻或文章，比如抖音或頭條，當然會導致一定的誤判，但不會讓用戶看到重複的內容。

  • 緩存宕機、緩存擊穿場景，一般判斷用戶是否在緩存中，如果在則直接返回結果，不在則查詢db，如果來一波冷數據，會導致緩存大量擊穿，造成雪崩效應，這時候可以用布隆過濾器當緩存的索引，只有在布隆過濾器中，才去查詢緩存，如果沒查詢到，則穿透到db。如果不在布隆器中，則直接返回。

  • WEB攔截器，如果相同請求則攔截，防止重複被攻擊。用戶第一次請求，將請求參數放入布隆過濾器中，當第二次請求時，先判斷請求參數是否被布隆過濾器命中。可以提高緩存命中率。Squid 網頁代理緩存服務器在 cache digests 中就使用了布隆過濾器。Google Chrome瀏覽器使用了布隆過濾器加速安全瀏覽服務

  • Venti 文檔存儲系統也採用布隆過濾器來檢測先前存儲的數據。

  • SPIN 模型檢測器也使用布隆過濾器在大規模驗證問題時跟蹤可達狀態空間。

Coding~

知道了布隆過濾去的原理和使用場景，我們可以自己實現一個簡單的布隆過濾器

自定義的 BloomFilter

public class MyBloomFilter {

    /**
     * 一個長度為10 億的比特位
     */
    private static final int DEFAULT_SIZE = 256 << 22;

    /**
     * 為了降低錯誤率，使用加法hash算法，所以定義一個8個元素的質數數組
     */
    private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};

    /**
     * 相當於構建 8 個不同的hash算法
     */
    private static HashFunction[] functions = new HashFunction[seeds.length];

    /**
     * 初始化布隆過濾器的 bitmap
     */
    private static BitSet bitset = new BitSet(DEFAULT_SIZE);

    /**
     * 添加數據
     *
     * @param value 需要加入的值
     */
    public static void add(String value) {
        if (value != null) {
            for (HashFunction f : functions) {
                //計算 hash 值並修改 bitmap 中相應位置為 true
                bitset.set(f.hash(value), true);
            }
        }
    }

    /**
     * 判斷相應元素是否存在
     * @param value 需要判斷的元素
     * @return 結果
     */
    public static boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (HashFunction f : functions) {
            ret = bitset.get(f.hash(value));
            //一個 hash 函數返回 false 則跳出循環
            if (!ret) {
                break;
            }
        }
        return ret;
    }

    /**
     * 模擬用戶是不是會員，或用戶在不在線。。。
     */
    public static void main(String[] args) {

        for (int i = 0; i < seeds.length; i++) {
            functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
        }

        // 添加1億數據
        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？我們寫的這些早有大牛幫我們實現，還造輪子，真是浪費時間，No，No，No，我們學習過程中是可以造輪子的，造輪子本身就是我們自己對設計和實現的具體落地過程，不僅能提高我們的編程能力，在造輪子的過程中肯定會遇到很多我們沒有思考過的問題，成長看的見~~

實際項目使用的時候，領導和我說項目一定要穩定運行，沒自信的我放棄了自己的輪子。

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) {
        //後邊兩個參數：預計包含的數據量，和允許的誤差值
        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();
    }
}

分佈式環境中，布隆過濾器肯定還需要考慮是可以共享的資源，這時候我們會想到 Redis，是的，Redis 也實現了布隆過濾器。

當然我們也可以把布隆過濾器通過 bloomFilter.writeTo() 寫入一個文件，放入OSS、S3這類對象存儲中。

Redis 中的 BloomFilter

Redis 提供的 bitMap 可以實現布隆過濾器，但是需要自己設計映射函數和一些細節，這和我們自定義沒啥區別。

Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之後才正式登場。布隆過濾器作為一個插件加載到 Redis Server 中，給 Redis 提供了強大的布隆去重功能。

在已安裝 Redis 的前提下，安裝 RedisBloom，有兩種方式

直接編譯進行安裝

git clone //github.com/RedisBloom/RedisBloom.git
cd RedisBloom
make     #編譯 會生成一個rebloom.so文件
redis-server --loadmodule /path/to/rebloom.so   #運行redis時加載布隆過濾器模塊
redis-cli    # 啟動連接容器中的 redis 客戶端驗證

使用Docker進行安裝

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

使用

布隆過濾器基本指令：

  • bf.add 添加元素到布隆過濾器
  • bf.exists 判斷元素是否在布隆過濾器
  • bf.madd 添加多個元素到布隆過濾器，bf.add 只能添加一個
  • bf.mexists 判斷多個元素是否在布隆過濾器
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

我們只有這幾個參數，肯定不會有誤判，當元素逐漸增多時，就會有一定的誤判了，這裡就不做這個實驗了。

上面使用的布隆過濾器只是默認參數的布隆過濾器，它在我們第一次 add 的時候自動創建。

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

  • error_rate：允許布隆過濾器的錯誤率，這個值越低過濾器的位數組的大小越大，佔用空間也就越大
  • initial_size：布隆過濾器可以儲存的元素個數，當實際存儲的元素個數超過這個值之後，過濾器的準確率會下降

但是這個操作需要在 add 之前顯式創建。如果對應的 key 已經存在，bf.reserve 會報錯

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 來實現的，Java 的 Redis 客戶端比較多，有些還沒有提供指令擴展機制，筆者已知的 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");
        // 初始化布隆過濾器，預計統計元素數量為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
    }
}

擴展

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

由於使用較少，暫不深入。

參考與感謝

//www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

//www.justdojava.com/2019/10/22/bloomfilter/

//www.cnblogs.com/cpselvis/p/6265825.html

//juejin.im/post/5cc5aa7ce51d456e431adac5

Tags:

VirMach 便宜 VPS

QNews

QNews