布隆過濾器是一個精巧而且經(jīng)典的數(shù)據(jù)結(jié)構(gòu)。

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

對于后端程序員來講，學(xué)習(xí)和理解布隆過濾器有很大的必要性。來吧，我們一起品味布隆過濾器的設(shè)計之美。

1 緩存穿透

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

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

?

?

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

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

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

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

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

2 原理解析

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

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

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

簡單來說就是準(zhǔn)備一個長度為 m 的位數(shù)組并初始化所有元素為 0，用 k 個散列函數(shù)對元素進(jìn)行 k 次散列運算跟 len (m) 取余得到 k 個位置并將 m 中對應(yīng)位置設(shè)置為 1。

如上圖，位數(shù)組的長度是８，散列函數(shù)個數(shù)是 3，先后保持兩個元素ｘ，ｙ。這兩個元素都經(jīng)過三次哈希函數(shù)生成三個哈希值，并映射到位數(shù)組的不同的位置，并置為1。元素 x 映射到位數(shù)組的第０位，第４位，第７位，元素ｙ映射到數(shù)組的位數(shù)組的第１位，第４位，第６位。

保存元素 x 后，位數(shù)組的第4位被設(shè)置為1之后，在處理元素 y 時第4位會被覆蓋，同樣也會設(shè)置為 1。

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

▍ 誤判率

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

k : 哈希函數(shù)個數(shù)

m : 位數(shù)組長度

n : 插入的元素個數(shù)

p : 誤判率

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

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

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

誤判率 p 的公式是

k 次哈希函數(shù)某一 bit 位未被置為 1 的概率為

插入 n 個元素后某一 bit 位依舊為 0 的概率為

那么插入 n 個元素后某一 bit 位置為1的概率為

整體誤判率為 當(dāng) m 足夠大時，誤判率會越小，該公式約等于

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

▍ 布隆過濾器支持刪除嗎

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

▍ 時間和空間效率

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

▍哈希函數(shù)類型

Murmur3，F(xiàn)NV 系列和 Jenkins 等非密碼學(xué)哈希函數(shù)適合，因為 Murmur3 算法簡單，能夠平衡好速度和隨機分布，很多開源產(chǎn)品經(jīng)常選用它作為哈希函數(shù)。

基于 Spring Cloud Alibaba + Gateway + Nacos + RocketMQ + Vue & Element 實現(xiàn)的后臺管理系統(tǒng) + 用戶小程序，支持 RBAC 動態(tài)權(quán)限、多租戶、數(shù)據(jù)權(quán)限、工作流、三方登錄、支付、短信、商城等功能

項目地址：https://github.com/YunaiV/yudao-cloud

視頻教程：https://doc.iocoder.cn/video/

3 Guava實現(xiàn)

Google Guava是 Google 開發(fā)和維護(hù)的開源 Java開發(fā)庫，它包含許多基本的工具類，例如字符串處理、集合、并發(fā)工具、I/O和數(shù)學(xué)函數(shù)等等。

1、添加Maven依賴

????com.google.guava
????guava
????31.0.1-jre<

2、創(chuàng)建布隆過濾器

BloomFilter?filter?=?BloomFilter.create(
??//Funnel?是一個接口，用于將任意類型的對象轉(zhuǎn)換為字節(jié)流，
??//以便用于布隆過濾器的哈希計算。
??Funnels.integerFunnel(),?
??10000,??//?插入數(shù)據(jù)條目數(shù)量
??0.001??//?誤判率
);

3、添加數(shù)據(jù)

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

4、判斷數(shù)據(jù)是否存在

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

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

static??BloomFilter?create(Funnel?funnel,?long?expectedInsertions,?double?fpp,?BloomFilter.Strategy?strategy)?{
????//?省略部分前置驗證代碼?
????//?位數(shù)組長度
????long?numBits?=?optimalNumOfBits(expectedInsertions,?fpp);
????//?哈希函數(shù)次數(shù)
????int?numHashFunctions?=?optimalNumOfHashFunctions(expectedInsertions,?numBits);
????try?{
??????return?new?BloomFilter(
????????????????????new?LockFreeBitArray(numBits),?
????????????????????numHashFunctions,?
????????????????????funnel,
????????????????????strategy
??????);
????}?catch?(IllegalArgumentException?e)?{
??????throw?new?IllegalArgumentException("Could?not?create?BloomFilter?of?"?+?numBits?+?"?bits",?e);
????}
}
//計算位數(shù)組長度
//n:插入的數(shù)據(jù)條目數(shù)量
//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)));
}

//?計算哈希次數(shù)
@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 的計算位數(shù)組長度和哈希次數(shù)和原理解析這一節(jié)展示的公式保持一致。

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

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

public??boolean?mightContain(
????@ParametricNullness?T?object,
????//Funnel?是一個接口，用于將任意類型的對象轉(zhuǎn)換為字節(jié)流，
????//以便用于布隆過濾器的哈希計算。
????Funnel?funnel,??
????//用于計算哈希值的哈希函數(shù)的數(shù)量
????int?numHashFunctions,
????//位數(shù)組實例，用于存儲布隆過濾器的位集
????LockFreeBitArray?bits)?{
??long?bitSize?=?bits.bitSize();
??//使用?MurmurHash3?哈希函數(shù)計算對象?object?的哈希值，
??//并將其轉(zhuǎn)換為一個 byte 數(shù)組。
??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?

	3 Redisson實現(xiàn)

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

	1、添加Maven依賴

???org.redisson
???redisson
???3.16.1



	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?bloomFilter?=?redissonClient.
??????????????????????????????????????getBloomFilter("myBloomFilter");
//10000表示插入元素的個數(shù)，0.001表示誤判率
bloomFilter.tryInit(10000,?0.001);
//插入4個元素
bloomFilter.add(1L);
bloomFilter.add(2L);
bloomFilter.add(3L);
bloomFilter.add(4L);
4、判斷數(shù)據(jù)是否存在
public?boolean?mightcontain(Long?id)?{
????return?bloomFilter.contains(id);
}


	好，我們來從源碼分析 Redisson 布隆過濾器是如何實現(xiàn)的 ？
public?boolean?tryInit(long?expectedInsertions,?double?falseProbability)?{
????//?位數(shù)組大小
????size?=?optimalNumOfBits(expectedInsertions,?falseProbability);
????//?哈希函數(shù)次數(shù)
????hashIterations?=?optimalNumOfHashFunctions(expectedInsertions,?size);
????CommandBatchService?executorService?=?new?CommandBatchService(commandExecutor);
????//?執(zhí)行?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.