布隆過濾器 Bloom Filter

一 前言

假如有一個15億用戶的系統,每天有幾億用戶訪問系統,要如何快速判斷是否為系統中的用戶呢?

  • 方法一,將15億用戶存儲在數據庫中,每次用戶訪問系統,都到數據庫進行查詢判斷,準確性高,但是查詢速度會比較慢。
  • 方法二,將15億用戶緩存在Redis內存中,每次用戶訪問系統,都到Redis中進行查詢判斷,準確性高,查詢速度也快,但是佔用內存極大。即使只存儲用戶ID,一個用戶ID一個字符,則15億*8位元組=12GB,對於一些內存空間有限的服務器來說相對浪費。

還有對於網站爬蟲的項目,我們都知道世界上的網站數量及其之多,每當我們爬一個新的網站url時,如何快速判斷是否爬蟲過了呢?還有垃圾郵箱的過濾,廣告電話的過濾等等。如果還是用上面2種方法,顯然不是最好的解決方案。

再者,查詢是一個系統最高頻的操作,當查詢一個數據,首先會先到緩存查詢(例如Redis),如果緩存沒命中,於是到持久層數據庫(mongo,mysql等)查詢,發現也沒有此數據,於是本此查詢失敗。如果用戶很多的時候,並且緩存都沒命中,進而全部請求了持久層數據庫,這就給數據庫帶來很大壓力,嚴重可能拖垮數據庫。俗稱緩存穿透

可能大家也聽到另一個詞叫緩存擊穿,它是指一個熱點key,不停着扛着高並發,突然這個key失效了,在失效的瞬間,大量的請求緩存就沒命中,全部請求到數據庫。

對於以上這些以及類似的場景,如何高效的解決呢?針對此,布隆過濾器應運而生了。

二 布隆過濾器

布隆過濾器(Bloom Filter)是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的算法要好的多,缺點是有一定的誤識別率和刪除困難。

二進制向量,簡單理解就是一個二進制數組。這個數組裏面存放的值要麼是0,要麼是1。

映射函數,它可以將一個元素映射成一個位陣列(Bit array)中的一個點。所以通過這個點,就能判斷集合中是否有此元素。

基本思想

  • 當一個元素被加入集合時,通過K個散列函數將這個元素映射到一個位數組中的K個點,把它們置為1。
  • 檢索某個元素時,再通過這K個散列函數將這個元素映射,看看這些位置是不是都是1就能知道集合中這個元素存不存在。如果這些位置有任何一個0,則該元素一定不存在;如果都是1,則被檢元素很可能存在。

Bloom Filter跟單個哈希函數映射不同,Bloom Filter使用了k個哈希函數,每個元素跟k個bit對應。從而降低了衝突的概率。

在這裡插入圖片描述

優點

  1. 二進制組成的數組,內存佔用空間少,並且插入和查詢速度很快,常數級別。
  2. Hash函數相互之間沒有必然聯繫,方便由硬件並行實現。
  3. 只存儲0和1,不需要存儲元素本身,在某些對保密要求非常嚴格的場合有優勢。

缺點

  1. 存在誤差率。隨着存入的元素數量增加,誤算率隨之增加。(比如現實中你是否遇到正常郵件也被放入垃圾郵件目錄,正常短訊被攔截)可以增加一個小的白名單,存儲那些可能被誤判的元素。
  2. 刪除困難。一個元素映射到bit數組的k個位置上是1,刪除的時候不能簡單的直接置為0,可能會影響其他元素的判斷。因為其他元素的映射也有可能在相同的位置置為1。可以採用Counting Bloom Filter解決。

三 Redis實現

在Redis中,有一種數據結構叫位圖,即bitmap。以下是一些常用的操作命令。

在Redis命令中,SETBIT key offset value,此命令表示將key對應的值的二進制數組,從左向右起,offset下標的二進制數字設置為value。

在這裡插入圖片描述

鍵k1對應的值為keke,對應ASCII碼為107 101 107 101,對應的二進制為 0110 1011,0110 0101,0110 1011,0110 0101。將下標5的位置設置為1,所以變成 0110 1111,0110 0101,0110 1011,0110 0101。即 oeke。

GETBIT key offset命令,它用來獲取指定下標的值。

在這裡插入圖片描述

還有一個比較常用的命令,BITCOUNT key [start end],用來獲取位圖中指定範圍值為1的個數。注意,start和end指定的是位元組的個數,而不是位數組下標。

在這裡插入圖片描述

Redisson是用於在Java程序中操作Redis的庫,利用Redisson我們可以在程序中輕鬆地使用Redis。Redisson這個客戶端工具實現了布隆過濾器,其底層就是通過bitmap這種數據結構來實現的。

Redis 4.0提供了插件功能之後,Redis就提供了布隆過濾器功能。布隆過濾器作為一個插件加載到了Redis Server之中,給Redis提供了強大的布隆去重功能。此文就不細講了,大家感興趣地可到官方查看詳細文檔介紹。它又如下常用命令:

  1. bf.add:添加元素
  2. bf.madd:批量添加元素
  3. bf.exists:檢索元素是否存在
  4. bf.mexists:檢索多個元素是否存在
  5. bf.reserve:自定義布隆過濾器,設置key,error_rate和initial_size

下面演示是在本地單節點Redis實現的,如果數據量很大,並且誤差率又很低的情況下,那單節點內存可能會不足。當然,在集群Redis中,也是可以通過Redisson實現分佈式布隆過濾器的。

引入依賴

<!-- //mvnrepository.com/artifact/org.redisson/redisson -->
<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.13.6</version>
</dependency>

代碼測試

package com.nobody;

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

/**
 * @Description
 * @Author Mr.nobody
 * @Date 2021/3/6
 * @Version 1.0
 */
public class RedissonDemo {

    public static void main(String[] args) {

        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");
        // config.useSingleServer().setPassword("123456");

        RedissonClient redissonClient = Redisson.create(config);
        // 獲取一個redis key為users的布隆過濾器
        RBloomFilter<Integer> bloomFilter = redissonClient.getBloomFilter("users");

        // 假設元素個數為10萬
        int size = 100000;

        // 進行初始化,預計元素為10萬,誤差率為1%
        bloomFilter.tryInit(size, 0.01);

        // 將1至100000這十萬個數映射到布隆過濾器中
        for (int i = 1; i <= size; i++) {
            bloomFilter.add(i);
        }

        // 檢查已在過濾器中的值,是否有匹配不上的
        for (int i = 1; i <= size; i++) {
            if (!bloomFilter.contains(i)) {
                System.out.println("存在不匹配的值:" + i);
            }
        }

        // 檢查不在過濾器中的1000個值,是否有匹配上的
        int matchCount = 0;
        for (int i = size + 1; i <= size + 1000; i++) {
            if (bloomFilter.contains(i)) {
                matchCount++;
            }
        }
        System.out.println("誤判個數:" + matchCount);
    }
}

結果存在的10萬個元素都匹配上了;不存在布隆過濾器中的1千個元素,有23個誤判。

誤判個數:23

四 Guava實現

布隆過濾器有許多實現與優化,Guava中就提供了一種實現。Google Guava提供的布隆過濾器的位數組是存儲在JVM內存中,故是單機版的,並且最大位長為int類型的最大值。

  • 使用布隆過濾器時,重要關注點是預估數據量n以及期望的誤判率fpp。
  • 實現布隆過濾器時,重要關注點是hash函數的選取以及bit數組的大小。

Bit數組大小選擇

根據預估數據量n以及誤判率fpp,bit數組大小的m的計算方式:

在這裡插入圖片描述

Guava中源碼實現如下:

@VisibleForTesting
static long optimalNumOfBits(long n, double p) {
  if (p == 0) {
    p = Double.MIN_VALUE;
  }
  return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}

哈希函數選擇

​哈希函數的個數的選擇也是挺講究的,哈希函數的選擇影響着性能的好壞,而且一個好的哈希函數能近似等概率的將元素映射到各個Bit。如何選擇構造k個函數呢,一種簡單的方法是選擇一個哈希函數,然後送入k個不同的參數。

哈希函數的個數k,可以根據預估數據量n和bit數組長度m計算而來:

在這裡插入圖片描述

Guava中源碼實現如下:

@VisibleForTesting
  static int optimalNumOfHashFunctions(long n, long m) {
    // (m / n) * log(2), but avoid truncation due to division!
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
  }

引入依賴

<!-- //mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>28.2-jre</version>
</dependency>

代碼測試

package com.nobody;

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

/**
 * @Description
 * @Author Mr.nobody
 * @Date 2021/3/6
 * @Version 1.0
 */
public class GuavaDemo {

    public static void main(String[] args) {

        // 假設元素個數為10萬
        int size = 100000;

        // 預計元素為10萬,誤差率為1%
        BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.01);

        // 將1至100000這十萬個數映射到布隆過濾器中
        for (int i = 1; i <= size; i++) {
            bloomFilter.put(i);
        }

        // 檢查已在過濾器中的值,是否有匹配不上的
        for (int i = 1; i <= size; i++) {
            if (!bloomFilter.mightContain(i)) {
                System.out.println("存在不匹配的值:" + i);
            }
        }

        // 檢查不在過濾器中的1000個值,是否有匹配上的
        int matchCount = 0;
        for (int i = size + 1; i <= size + 1000; i++) {
            if (bloomFilter.mightContain(i)) {
                matchCount++;
            }
        }
        System.out.println("誤判個數:" + matchCount);

    }
}

結果存在的10萬個元素都匹配上了;不存在布隆過濾器中的1千個元素,有10個誤判。

誤判個數:10

當fpp的值改為為0.001,即降低誤差率時,誤判個數為0個。

誤判個數:0

分析結果可知,誤判率確實跟我們傳入的容錯率差不多,而且在布隆過濾器中的元素都匹配到了。

源碼分析

通過debug創建布隆過濾器的方法,當預計元素為10萬個,fpp的值為0.01時,需要位數958505個,hash函數個數為7個。

當預計元素為10萬個,fpp的值為0.001時,需要位數1437758個,hash函數個數為10個。

得出結論

  • 容錯率越大,所需空間和時間越小,容錯率越小,所需空間和時間越大。
  • 理論上存10萬個數,一個int是4位元組,即32位,需要320萬位。如果使用HashMap存儲,按HashMap50%的存儲效率,需要640萬位。而布隆過濾器即使容錯率fpp為0.001,也才需要1437758位,可以看出BloomFilter的存儲空間很小。

五 擴展知識點

假如有一台服務器,內存只有4GB,磁盤上有2個大文件,文件A存儲100億個URL,文件B存儲100億個URL。請問如何模糊找出兩個文件的URL交集?如何精緻找出兩個文件的URL交集。

模糊交集:

藉助布隆過濾器思想,先將一個文件的URL通過hash函數映射到bit數組中,這樣大大減少了內存存儲,再讀取另一個文件URL,去bit數組中進行匹配。

精緻交集:

對大文件進行hash拆分成小文件,例如拆分成1000個小文件(如果服務器內存更小,則可以拆分更多個更小的文件),比如文件A拆分為A1,A2,A3…An,文件B拆分為B1,B2,B3…Bn。而且通過相同的hash函數,相同的URL一定被映射到相同下標的小文件中,例如A文件的www.baidu.com被映射到A1中,那B文件的www.baidu.com也一定被映射到B1文件中。最後再通過求相同下標的小文件(例如A1和B1)(A2和B2)的交集即可。

歡迎關注微信公眾號:「Java之言」技術文章持續更新,請持續關注……

  • 第一時間學習最新技術文章
  • 領取最新技術學習資料視頻
  • 最新互聯網資訊和面試經驗