布隆過濾器是一個(gè)精巧而且經(jīng)典的數(shù)據(jù)結(jié)構(gòu)。
你可能沒想到： RocketMQ、 Hbase 、Cassandra 、LevelDB 、RocksDB 這些知名項(xiàng)目中都有布隆過濾器的身影。
對于后端程序員來講，學(xué)習(xí)和理解布隆過濾器有很大的必要性。來吧，我們一起品味布隆過濾器的設(shè)計(jì)之美。
1 緩存穿透
我們先來看一個(gè)商品服務(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è)此商品既不存儲(chǔ)在緩存中，也不存在數(shù)據(jù)庫中，則沒有辦法回寫緩存，當(dāng)有類似這樣大量的請求訪問服務(wù)時(shí)，數(shù)據(jù)庫的壓力就會(huì)極大。
這是一個(gè)典型的緩存穿透的場景。
為了解決這個(gè)問題呢，通常我們可以向分布式緩存中寫入一個(gè)過期時(shí)間較短的空值占位，但這樣會(huì)占用較多的存儲(chǔ)空間，性價(jià)比不足。
問題的本質(zhì)是："如何以極小的代價(jià)檢索一個(gè)元素是否在一個(gè)集合中？"
我們的主角布隆過濾器出場了，它就能游刃有余的平衡好時(shí)間和空間兩種維度。
2 原理解析
布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。
布隆過濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過一般的算法，缺點(diǎn)是有一定的誤識別率和刪除困難。
布隆過濾器的原理：當(dāng)一個(gè)元素被加入集合時(shí)，通過 K 個(gè)散列函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組中的 K 個(gè)點(diǎn)，把它們置為 1。檢索時(shí)，我們只要看看這些點(diǎn)是不是都是 1 就（大約）知道集合中有沒有它了：如果這些點(diǎn)有任何一個(gè) 0，則被檢元素一定不在；如果都是 1，則被檢元素很可能在。
簡單來說就是準(zhǔn)備一個(gè)長度為 m 的位數(shù)組并初始化所有元素為 0，用 k 個(gè)散列函數(shù)對元素進(jìn)行 k 次散列運(yùn)算跟 len (m) 取余得到 k 個(gè)位置并將 m 中對應(yīng)位置設(shè)置為 1。
如上圖，位數(shù)組的長度是８，散列函數(shù)個(gè)數(shù)是 3，先后保持兩個(gè)元素ｘ，ｙ。這兩個(gè)元素都經(jīng)過三次哈希函數(shù)生成三個(gè)哈希值，并映射到位數(shù)組的不同的位置，并置為1。元素 x 映射到位數(shù)組的第０位，第４位，第７位，元素ｙ映射到數(shù)組的位數(shù)組的第１位，第４位，第６位。
保存元素 x 后，位數(shù)組的第4位被設(shè)置為1之后，在處理元素 y 時(shí)第4位會(huì)被覆蓋，同樣也會(huì)設(shè)置為 1。
當(dāng)布隆過濾器保存的元素越多，被置為 1 的 bit 位也會(huì)越來越多，元素 x 即便沒有存儲(chǔ)過，假設(shè)哈希函數(shù)映射到位數(shù)組的三個(gè)位都被其他值設(shè)置為 1 了，對于布隆過濾器的機(jī)制來講，元素 x 這個(gè)值也是存在的，也就是說布隆過濾器存在一定的誤判率。
▍ 誤判率
布隆過濾器包含如下四個(gè)屬性：
-
k : 哈希函數(shù)個(gè)數(shù)
-
m : 位數(shù)組長度
-
n : 插入的元素個(gè)數(shù)
-
p : 誤判率
若位數(shù)組長度太小則會(huì)導(dǎo)致所有 bit 位很快都會(huì)被置為 1 ，那么檢索任意值都會(huì)返回”可能存在“ ， 起不到過濾的效果。 位數(shù)組長度越大，則誤判率越小。
同時(shí)，哈希函數(shù)的個(gè)數(shù)也需要考量，哈希函數(shù)的個(gè)數(shù)越大，檢索的速度會(huì)越慢，誤判率也越小，反之，則誤判率越高。
從張圖我們可以觀察到相同位數(shù)組長度的情況下，隨著哈希函數(shù)的個(gè)人的增長，誤判率顯著的下降。
誤判率 p 的公式是
-
k 次哈希函數(shù)某一 bit 位未被置為 1 的概率為
-
插入 n 個(gè)元素后某一 bit 位依舊為 0 的概率為
-
那么插入 n 個(gè)元素后某一 bit 位置為1的概率為
-
整體誤判率為 ，當(dāng) m 足夠大時(shí)，誤判率會(huì)越小，該公式約等于
我們會(huì)預(yù)估布隆過濾器的誤判率 p 以及待插入的元素個(gè)數(shù) n 分別推導(dǎo)出最合適的位數(shù)組長度 m 和 哈希函數(shù)個(gè)數(shù) k。
▍ 布隆過濾器支持刪除嗎
布隆過濾器其實(shí)并不支持刪除元素，因?yàn)槎鄠€(gè)元素可能哈希到一個(gè)布隆過濾器的同一個(gè)位置，如果直接刪除該位置的元素，則會(huì)影響其他元素的判斷。
▍ 時(shí)間和空間效率
布隆過濾器的空間復(fù)雜度為 O(m) ，插入和查詢時(shí)間復(fù)雜度都是 O(k) 。 存儲(chǔ)空間和插入、查詢時(shí)間都不會(huì)隨元素增加而增大。 空間、時(shí)間效率都很高。
▍哈希函數(shù)類型
Murmur3，F(xiàn)NV 系列和 Jenkins 等非密碼學(xué)哈希函數(shù)適合，因?yàn)?Murmur3 算法簡單，能夠平衡好速度和隨機(jī)分布，很多開源產(chǎn)品經(jīng)常選用它作為哈希函數(shù)。
3 Guava實(shí)現(xiàn)
Google Guava是 Google 開發(fā)和維護(hù)的開源 Java開發(fā)庫，它包含許多基本的工具類，例如字符串處理、集合、并發(fā)工具、I/O和數(shù)學(xué)函數(shù)等等。
1、添加Maven依賴
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.0.1-jre<</version>
</dependency>
2、創(chuàng)建布隆過濾器
BloomFilter<Integer> filter = BloomFilter.create(
//Funnel 是一個(gè)接口，用于將任意類型的對象轉(zhuǎn)換為字節(jié)流，
//以便用于布隆過濾器的哈希計(jì)算。
Funnels.integerFunnel(),
10000, // 插入數(shù)據(jù)條目數(shù)量
0.001 // 誤判率
);
3、添加數(shù)據(jù)
@PostConstruct
public void addProduct() {
logger.info("初始化布隆過濾器數(shù)據(jù)開始");
//插入4個(gè)元素
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 源碼中布隆過濾器是如何實(shí)現(xiàn)的 ？
static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, BloomFilter.Strategy strategy) {
// 省略部分前置驗(yàn)證代碼
// 位數(shù)組長度
long numBits = optimalNumOfBits(expectedInsertions, fpp);
// 哈希函數(shù)次數(shù)
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);
}
}
//計(jì)算位數(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)));
}
// 計(jì)算哈希次數(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 的計(jì)算位數(shù)組長度和哈希次數(shù)和原理解析這一節(jié)展示的公式保持一致。
重點(diǎn)來了，Bloom filter 是如何判斷元素存在的 ？
方法名就非常有 google 特色 ， ”mightContain“ 的中文表意是：”可能存在“ 。方法的返回值為 true ，元素可能存在，但若返回值為 false ，元素必定不存在。
public <T extends @Nullable Object> boolean mightContain(
@ParametricNullness T object,
//Funnel 是一個(gè)接口，用于將任意類型的對象轉(zhuǎn)換為字節(jié)流，
//以便用于布隆過濾器的哈希計(jì)算。
Funnel<? super T> funnel,
//用于計(jì)算哈希值的哈希函數(shù)的數(shù)量
int numHashFunctions,
//位數(shù)組實(shí)例，用于存儲(chǔ)布隆過濾器的位集
LockFreeBitArray bits) {
long bitSize = bits.bitSize();
//使用 MurmurHash3 哈希函數(shù)計(jì)算對象 object 的哈希值，
//并將其轉(zhuǎn)換為一個(gè) 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 < numHashFunctions; i++) {
// Make the combined hash positive and indexable
// 計(jì)算哈希值的索引，并從位數(shù)組中查找索引處的位。
// 如果索引處的位為 0，表示對象不在布隆過濾器中，返回 false。
if (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) {
return false;
}
// 將 hash2 加到 combinedHash 上，用于計(jì)算下一個(gè)哈希值的索引。
combinedHash += hash2;
}
return true;
}
3 Redisson實(shí)現(xiàn)
Redisson 是一個(gè)用 Java 編寫的 Redis 客戶端，它實(shí)現(xiàn)了分布式對象和服務(wù)，包括集合、映射、鎖、隊(duì)列等。Redisson的API簡單易用，使得在分布式環(huán)境下使用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表示插入元素的個(gè)數(shù)，0.001表示誤判率
bloomFilter.tryInit(10000, 0.001);
//插入4個(gè)元素
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 布隆過濾器是如何實(shí)現(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.<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;
}
Redisson 布隆過濾器初始化的時(shí)候，會(huì)創(chuàng)建一個(gè) Hash 數(shù)據(jù)結(jié)構(gòu)的 key ，存儲(chǔ)布隆過濾器的4個(gè)核心屬性。
那么 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);
//創(chuàng)建 bitset 對象， 然后調(diào)用setAsync方法，該方法的參數(shù)是索引。
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) {
}
}
}
從源碼中，我們發(fā)現(xiàn) Redisson 布隆過濾器操作的對象是 位圖（bitMap） 。
在 Redis 中，位圖本質(zhì)上是 string 數(shù)據(jù)類型，Redis 中一個(gè)字符串類型的值最多能存儲(chǔ) 512 MB 的內(nèi)容，每個(gè)字符串由多個(gè)字節(jié)組成，每個(gè)字節(jié)又由 8 個(gè) Bit 位組成。位圖結(jié)構(gòu)正是使用“位”來實(shí)現(xiàn)存儲(chǔ)的，它通過將比特位設(shè)置為 0 或 1來達(dá)到數(shù)據(jù)存取的目的，它存儲(chǔ)上限為 2^32 ，我們可以使用getbit/setbit命令來處理這個(gè)位數(shù)組。
為了方便大家理解，我做了一個(gè)簡單的測試。
通過 Redisson API 創(chuàng)建 key 為 mybitset 的 位圖 ，設(shè)置索引 3 ，5，6，8 位為 1 ，右側(cè)的二進(jìn)制值也完全匹配。
4 實(shí)戰(zhàn)要點(diǎn)
通過 Guava 和 Redisson 創(chuàng)建和使用布隆過濾器比較簡單，我們下面討論實(shí)戰(zhàn)層面的注意事項(xiàng)。
1、緩存穿透場景
首先我們需要初始化布隆過濾器，然后當(dāng)用戶請求時(shí)，判斷過濾器中是否包含該元素，若不包含該元素，則直接返回不存在。
若包含則從緩存中查詢數(shù)據(jù)，若緩存中也沒有，則查詢數(shù)據(jù)庫并回寫到緩存里，最后給前端返回。
2、元素刪除場景
現(xiàn)實(shí)場景，元素不僅僅是只有增加，還存在刪除元素的場景，比如說商品的刪除。
原理解析這一節(jié)，我們已經(jīng)知曉：布隆過濾器其實(shí)并不支持刪除元素，因?yàn)槎鄠€(gè)元素可能哈希到一個(gè)布隆過濾器的同一個(gè)位置，如果直接刪除該位置的元素，則會(huì)影響其他元素的判斷。
我們有兩種方案：
▍計(jì)數(shù)布隆過濾器
計(jì)數(shù)過濾器（Counting Bloom Filter）是布隆過濾器的擴(kuò)展，標(biāo)準(zhǔn) Bloom Filter 位數(shù)組的每一位擴(kuò)展為一個(gè)小的計(jì)數(shù)器（Counter），在插入元素時(shí)給對應(yīng)的 k （k 為哈希函數(shù)個(gè)數(shù)）個(gè) Counter 的值分別加 1，刪除元素時(shí)給對應(yīng)的 k 個(gè) Counter 的值分別減 1。
雖然計(jì)數(shù)布隆過濾器可以解決布隆過濾器無法刪除元素的問題，但是又引入了另一個(gè)問題：“更多的資源占用，而且在很多時(shí)候會(huì)造成極大的空間浪費(fèi)”。
▍ 定時(shí)重新構(gòu)建布隆過濾器
從工程角度來看，定時(shí)重新構(gòu)建布隆過濾器這個(gè)方案可行也可靠，同時(shí)也相對簡單。
- 定時(shí)任務(wù)觸發(fā)全量商品查詢 ;
- 將商品編號添加到新的布隆過濾器 ;
- 任務(wù)完成，修改商品布隆過濾器的映射（從舊 A 修改成 新 B ）;
- 商品服務(wù)根據(jù)布隆過濾器的映射，選擇新的布隆過濾器 B進(jìn)行相關(guān)的查詢操作 ；
- 選擇合適的時(shí)間點(diǎn)，刪除舊的布隆過濾器 A。
5 總結(jié)
布隆過濾器是一個(gè)很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)，用于檢索一個(gè)元素是否在一個(gè)集合中。
它的空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過一般的算法，但是有一定的誤判率 （函數(shù)返回 true , 意味著元素可能存在，函數(shù)返回 false ，元素必定不存在）。
布隆過濾器的四個(gè)核心屬性：
-
k : 哈希函數(shù)個(gè)數(shù)
-
m : 位數(shù)組長度
-
n : 插入的元素個(gè)數(shù)
-
p : 誤判率
Java 世界里 ，通過 Guava 和 Redisson 創(chuàng)建和使用布隆過濾器非常簡單。
布隆過濾器無法刪除元素，但我們可以通過計(jì)數(shù)布隆過濾器和定時(shí)重新構(gòu)建布隆過濾器兩種方案實(shí)現(xiàn)刪除元素的效果。
為什么這么多的開源項(xiàng)目中使用布隆過濾器 ？
因?yàn)樗脑O(shè)計(jì)精巧且簡潔，工程上實(shí)現(xiàn)非常容易，效能高，雖然有一定的誤判率，但軟件設(shè)計(jì)不就是要 trade off 嗎 ？
參考資料：
https://hackernoon.com/probabilistic-data-structures-bloom-filter-5374112a7832文章來源：http://www.zghlxwxcb.cn/news/detail-413504.html
如果我的文章對你有所幫助，還請幫忙點(diǎn)贊、在看、轉(zhuǎn)發(fā)一下，你的支持會(huì)激勵(lì)我輸出更高質(zhì)量的文章，非常感謝！文章來源地址http://www.zghlxwxcb.cn/news/detail-413504.html
到了這里，關(guān)于品味布隆過濾器的設(shè)計(jì)之美的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
