布隆過濾器是一個精巧而且經典的數據結構。

你可能沒想到：RocketMQ、 Hbase 、Cassandra 、LevelDB 、RocksDB 這些知名項目中都有布隆過濾器的身影。

對於後端程序員來講，學習和理解布隆過濾器有很大的必要性。來吧，我們一起品味布隆過濾器的設計之美。

1 緩存穿透

我們先來看一個商品服務查詢詳情的接口：

public Product queryProductById (Long id){
   // 查詢緩存
   Product product = queryFromCache(id);
   if(product != null) {
     return product ;
   }
   // 從數據庫查詢
   product = queryFromDataBase(id);
   if(product != null) {
       saveCache(id , product);
   }
   return product;
}

假設此商品既不存儲在緩存中，也不存在數據庫中，則沒有辦法回寫緩存，當有類似這樣大量的請求訪問服務時，數據庫的壓力就會極大。

這是一個典型的緩存穿透的場景。

爲了解決這個問題呢，通常我們可以向分佈式緩存中寫入一個過期時間較短的空值佔位，但這樣會佔用較多的存儲空間，性價比不足。

問題的本質是：" 如何以極小的代價檢索一個元素是否在一個集合中？"

我們的主角布隆過濾器出場了，它就能遊刃有餘的平衡好時間和空間兩種維度。

2 原理解析

布隆過濾器（英語：Bloom Filter）是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。

布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。

布隆過濾器的原理：當一個元素被加入集合時，通過 K 個散列函數將這個元素映射成一個位數組中的 K 個點，把它們置爲 1。檢索時，我們只要看看這些點是不是都是 1 就（大約）知道集合中有沒有它了：如果這些點有任何一個 0，則被檢元素一定不在；如果都是 1，則被檢元素很可能在。

簡單來說就是準備一個長度爲 m 的位數組並初始化所有元素爲 0，用 k 個散列函數對元素進行 k 次散列運算跟 len (m) 取餘得到 k 個位置並將 m 中對應位置設置爲 1。

如上圖，位數組的長度是８，散列函數個數是 3，先後保持兩個元素ｘ，ｙ。這兩個元素都經過三次哈希函數生成三個哈希值，並映射到位數組的不同的位置，並置爲 1。元素 x 映射到位數組的第０位，第４位，第７位，元素ｙ映射到數組的位數組的第１位，第４位，第６位。

保存元素 x 後，位數組的第 4 位被設置爲 1 之後，在處理元素 y 時第 4 位會被覆蓋，同樣也會設置爲 1。

當布隆過濾器保存的元素越多，被置爲 1 的 bit 位也會越來越多，元素 x 即便沒有存儲過，假設哈希函數映射到位數組的三個位都被其他值設置爲 1 了，對於布隆過濾器的機制來講，元素 x 這個值也是存在的，也就是說布隆過濾器存在一定的誤判率。

▍ 誤判率

布隆過濾器包含如下四個屬性：

• k : 哈希函數個數

• m : 位數組長度

• n : 插入的元素個數

• p : 誤判率

若位數組長度太小則會導致所有 bit 位很快都會被置爲 1 ，那麼檢索任意值都會返回” 可能存在 “ ， 起不到過濾的效果。位數組長度越大，則誤判率越小。

同時，哈希函數的個數也需要考量，哈希函數的個數越大，檢索的速度會越慢，誤判率也越小，反之，則誤判率越高。

從張圖我們可以觀察到相同位數組長度的情況下，隨着哈希函數的個人的增長，誤判率顯著的下降。

誤判率 p 的公式是

1. k 次哈希函數某一 bit 位未被置爲 1 的概率爲

2. 插入 n 個元素後某一 bit 位依舊爲 0 的概率爲

3. 那麼插入 n 個元素後某一 bit 位置爲 1 的概率爲

4. 整體誤判率爲 ，當 m 足夠大時，誤判率會越小，該公式約等於

我們會預估布隆過濾器的誤判率 p 以及待插入的元素個數 n 分別推導出最合適的位數組長度 m 和 哈希函數個數 k。

▍ 布隆過濾器支持刪除嗎

布隆過濾器其實並不支持刪除元素，因爲多個元素可能哈希到一個布隆過濾器的同一個位置，如果直接刪除該位置的元素，則會影響其他元素的判斷。

▍ 時間和空間效率

布隆過濾器的空間複雜度爲 O(m) ，插入和查詢時間複雜度都是 O(k) 。存儲空間和插入、查詢時間都不會隨元素增加而增大。空間、時間效率都很高。

▍哈希函數類型

Murmur3，FNV 系列和 Jenkins 等非密碼學哈希函數適合，因爲 Murmur3 算法簡單，能夠平衡好速度和隨機分佈，很多開源產品經常選用它作爲哈希函數。

3 Guava 實現

Google Guava 是 Google 開發和維護的開源 Java 開發庫，它包含許多基本的工具類，例如字符串處理、集合、併發工具、I/O 和數學函數等等。

1、添加 Maven 依賴

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre<</version>
</dependency>

2、創建布隆過濾器

BloomFilter<Integer> filter = BloomFilter.create(
  //Funnel 是一個接口，用於將任意類型的對象轉換爲字節流，
  //以便用於布隆過濾器的哈希計算。
  Funnels.integerFunnel(), 
  10000,  // 插入數據條目數量
  0.001  // 誤判率
);

3、添加數據

@PostConstruct
public void addProduct() {
    logger.info("初始化布隆過濾器數據開始");
    //插入4個元素
     filter.put(1L);
     filter.put(2L);
     filter.put(3L);
     filter.put(4L);
     logger.info("初始化布隆過濾器數據結束");
}

4、判斷數據是否存在

public boolean maycontain(Long id) {
    return filter.mightContain(id);
}

接下來，我們查看 Guava 源碼中布隆過濾器是如何實現的 ？

static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, BloomFilter.Strategy strategy) {
    // 省略部分前置驗證代碼 
    // 位數組長度
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
    // 哈希函數次數
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    try {
      return new BloomFilter<T>(
                    new LockFreeBitArray(numBits), 
                    numHashFunctions, 
                    funnel,
                    strategy
      );
    } catch (IllegalArgumentException e) {
      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
    }
}

//計算位數組長度
//n:插入的數據條目數量
//p:期望誤判率
@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)));
}

// 計算哈希次數
@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)));
}

Guava 的計算位數組長度和哈希次數和原理解析這一節展示的公式保持一致。

重點來了，Bloom filter 是如何判斷元素存在的 ？

方法名就非常有 google 特色 ，  ”mightContain“的中文表意是：” 可能存在 “ 。方法的返回值爲 true ，元素可能存在，但若返回值爲 false ，元素必定不存在。

public <T extends @Nullable Object> boolean mightContain(
    @ParametricNullness T object,
    //Funnel 是一個接口，用於將任意類型的對象轉換爲字節流，
    //以便用於布隆過濾器的哈希計算。
    Funnel<? super T> funnel,  
    //用於計算哈希值的哈希函數的數量
    int numHashFunctions,
    //位數組實例，用於存儲布隆過濾器的位集
    LockFreeBitArray bits) {
  long bitSize = bits.bitSize();
  //使用 MurmurHash3 哈希函數計算對象 object 的哈希值，
  //並將其轉換爲一個 byte 數組。
  byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
  long hash1 = lowerEight(bytes);
  long hash2 = upperEight(bytes);

  long combinedHash = hash1;
  for (int i = 0; i < numHashFunctions; i++) {
    // Make the combined hash positive and indexable
    // 計算哈希值的索引，並從位數組中查找索引處的位。
    // 如果索引處的位爲 0，表示對象不在布隆過濾器中，返回 false。
    if (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) {
      return false;
    }
    // 將 hash2 加到 combinedHash 上，用於計算下一個哈希值的索引。
    combinedHash += hash2;
  }
  return true;
}

3 Redisson 實現

Redisson 是一個用 Java 編寫的 Redis 客戶端，它實現了分佈式對象和服務，包括集合、映射、鎖、隊列等。Redisson 的 API 簡單易用，使得在分佈式環境下使用 Redis 更加容易和高效。

1、添加 Maven 依賴

<dependency>
   <groupId>org.redisson</groupId>
   <artifactId>redisson</artifactId>
   <version>3.16.1</version>
</dependency>

2、配置 Redisson 客戶端

@Configuration
public class RedissonConfig {

 Bean
 public RedissonClient redissonClient() {
    Config config = new Config();
    config.useSingleServer().setAddress("redis://localhost:6379");
    return Redisson.create(config);
 }
 
}

3、初始化

RBloomFilter<Long> bloomFilter = redissonClient.
                                      getBloomFilter("myBloomFilter");
//10000表示插入元素的個數，0.001表示誤判率
bloomFilter.tryInit(10000, 0.001);
//插入4個元素
bloomFilter.add(1L);
bloomFilter.add(2L);
bloomFilter.add(3L);
bloomFilter.add(4L);

4、判斷數據是否存在

public boolean mightcontain(Long id) {
    return bloomFilter.contains(id);
}

好，我們來從源碼分析 Redisson 布隆過濾器是如何實現的 ？

public boolean tryInit(long expectedInsertions, double falseProbability) {
    // 位數組大小
    size = optimalNumOfBits(expectedInsertions, falseProbability);
    // 哈希函數次數
    hashIterations = optimalNumOfHashFunctions(expectedInsertions, size);
    CommandBatchService executorService = new CommandBatchService(commandExecutor);
    // 執行 Lua腳本，生成配置
    executorService.evalReadAsync(configName, codec, RedisCommands.EVAL_VOID,
            "local size = redis.call('hget', KEYS[1], 'size');" +
                    "local hashIterations = redis.call('hget', KEYS[1], 'hashIterations');" +
                    "assert(size == false and hashIterations == false, 'Bloom filter config has been changed')",
                    Arrays.<Object>asList(configName), size, hashIterations);
    executorService.writeAsync(configName, StringCodec.INSTANCE,
                                            new RedisCommand<Void>("HMSET", new VoidReplayConvertor()), configName,
            "size", size, "hashIterations", hashIterations,
            "expectedInsertions", expectedInsertions, "falseProbability", BigDecimal.valueOf(falseProbability).toPlainString());
    try {
        executorService.execute();
    } catch (RedisException e) {
    }
    return true;
}

Bf 配置信息

Redisson 布隆過濾器初始化的時候，會創建一個 Hash 數據結構的 key ，存儲布隆過濾器的 4 個核心屬性。

那麼 Redisson 布隆過濾器如何保存元素呢 ？

public boolean add(T object) {
    long[] hashes = hash(object);
    while (true) {
        int hashIterations = this.hashIterations;
        long size = this.size;
        long[] indexes = hash(hashes[0], hashes[1], hashIterations, size);
        CommandBatchService executorService = new CommandBatchService(commandExecutor);
        addConfigCheck(hashIterations, size, executorService);
        //創建 bitset 對象， 然後調用setAsync方法，該方法的參數是索引。
        RBitSetAsync bs = createBitSet(executorService);
        for (int i = 0; i < indexes.length; i++) {
            bs.setAsync(indexes[i]);
        }
        try {
            List<Boolean> result = (List<Boolean>) executorService.execute().getResponses();
            for (Boolean val : result.subList(1, result.size()-1)) {
                if (!val) {
                    return true;
                }
            }
            return false;
        } catch (RedisException e) {
        }
    }
}

從源碼中，我們發現 Redisson 布隆過濾器操作的對象是 位圖（bitMap） 。

在 Redis 中，位圖本質上是 string 數據類型，Redis 中一個字符串類型的值最多能存儲 512 MB 的內容，每個字符串由多個字節組成，每個字節又由 8 個 Bit 位組成。位圖結構正是使用 “位” 來實現存儲的，它通過將比特位設置爲 0 或 1 來達到數據存取的目的，它存儲上限爲 2^32 ，我們可以使用getbit/setbit命令來處理這個位數組。

爲了方便大家理解，我做了一個簡單的測試。

通過 Redisson API 創建 key 爲 mybitset 的 位圖  ，設置索引 3 ，5，6，8 位爲 1 ，右側的二進制值也完全匹配。

4 實戰要點

通過 Guava 和 Redisson 創建和使用布隆過濾器比較簡單，我們下面討論實戰層面的注意事項。

1、緩存穿透場景

首先我們需要初始化布隆過濾器，然後當用戶請求時，判斷過濾器中是否包含該元素，若不包含該元素，則直接返回不存在。

若包含則從緩存中查詢數據，若緩存中也沒有，則查詢數據庫並回寫到緩存裏，最後給前端返回。

2、元素刪除場景

現實場景，元素不僅僅是隻有增加，還存在刪除元素的場景，比如說商品的刪除。

原理解析這一節，我們已經知曉：布隆過濾器其實並不支持刪除元素，因爲多個元素可能哈希到一個布隆過濾器的同一個位置，如果直接刪除該位置的元素，則會影響其他元素的判斷。

我們有兩種方案：

▍計數布隆過濾器

計數過濾器（Counting Bloom Filter）是布隆過濾器的擴展，標準 Bloom Filter 位數組的每一位擴展爲一個小的計數器（Counter），在插入元素時給對應的 k （k 爲哈希函數個數）個 Counter 的值分別加 1，刪除元素時給對應的 k 個 Counter 的值分別減 1。

雖然計數布隆過濾器可以解決布隆過濾器無法刪除元素的問題，但是又引入了另一個問題：“更多的資源佔用，而且在很多時候會造成極大的空間浪費”。

▍ 定時重新構建布隆過濾器

從工程角度來看，定時重新構建布隆過濾器這個方案可行也可靠，同時也相對簡單。

1. 定時任務觸發全量商品查詢 ;

2. 將商品編號添加到新的布隆過濾器 ;

3. 任務完成，修改商品布隆過濾器的映射（從舊 A 修改成 新 B ）;

4. 商品服務根據布隆過濾器的映射，選擇新的布隆過濾器 B 進行相關的查詢操作 ；

5. 選擇合適的時間點，刪除舊的布隆過濾器 A。

5 總結

布隆過濾器是一個很長的二進制向量和一系列隨機映射函數，用於檢索一個元素是否在一個集合中。

它的空間效率和查詢時間都遠遠超過一般的算法，但是有一定的誤判率 （函數返回 true , 意味着元素可能存在，函數返回 false ，元素必定不存在）。

布隆過濾器的四個核心屬性：

• k :  哈希函數個數

• m : 位數組長度

• n :  插入的元素個數

• p :  誤判率

Java 世界裏 ，通過 Guava 和 Redisson 創建和使用布隆過濾器非常簡單。

布隆過濾器無法刪除元素，但我們可以通過計數布隆過濾器和定時重新構建布隆過濾器兩種方案實現刪除元素的效果。

爲什麼這麼多的開源項目中使用布隆過濾器 ？

因爲它的設計精巧且簡潔，工程上實現非常容易，效能高，雖然有一定的誤判率，但軟件設計不就是要 trade off 嗎 ？

參考資料：

https://hackernoon.com/probabilistic-data-structures-bloom-filter-5374112a7832

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/vfkPEoGRURYrknWU2mJ4ow