什么是布隆過濾器？如何解決高并發(fā)緩存穿透問題？
[導(dǎo)讀]日常開發(fā)中，大家經(jīng)常使用緩存，但是你知道大型的互聯(lián)網(wǎng)公司面對高并發(fā)流量，要注意緩存穿透問題嗎!!!???本文會介紹布隆過濾器，空間換時(shí)間，以較低的內(nèi)存空間、高效解決這個(gè)問題。本篇文章的目錄：1、性能不夠，緩存來湊現(xiàn)在的年輕人都喜歡網(wǎng)購，沒事就逛逛淘寶，剁剁手，買些自己喜歡的東西，...
日常開發(fā)中，大家經(jīng)常使用緩存，但是你知道大型的互聯(lián)網(wǎng)公司面對高并發(fā)流量，要注意緩存穿透問題嗎!!!? ??本文會介紹布隆過濾器，空間換時(shí)間，以較低的內(nèi)存空間、高效解決這個(gè)問題。本篇文章的目錄：
1、性能不夠，緩存來湊現(xiàn)在的年輕人都喜歡網(wǎng)購，沒事就逛逛淘寶，剁剁手，買些自己喜歡的東西，釋放下工作壓力。
地址：https://detail.tmall.com/item.htm?id=628993216729上圖是一個(gè)天貓 iphone12 的
商品詳情頁，id表示商品的編號我們都知道淘寶的訪問量是非常高的，為了提升系統(tǒng)的吞吐量，做了很多性能優(yōu)化，其中非常重要一點(diǎn)是將信息異構(gòu)到緩存中。有句話說的好：性能不夠，緩存來湊。但是，使用緩存時(shí)，我們要關(guān)注一個(gè)重要問題，如果緩存沒有命中怎么辦？2、緩存沒有命中，怎么辦？
- ①我們先查詢緩存，判斷緩存中是否有數(shù)據(jù)
- ②如果有數(shù)據(jù)，直接返回
- ③如果緩存為空，我們需要再查一次數(shù)據(jù)庫，并將數(shù)據(jù)格式異構(gòu)化，然后預(yù)熱到緩沖中，然后將結(jié)果返回
3、那么如何處理緩存穿透？我們的思路是，緩存中能不能判斷這個(gè)數(shù)據(jù)庫值的存在性，如果真的不存在，直接返回，也避免一次數(shù)據(jù)庫查詢。由于不存在是個(gè)
無限邊界，所以，我們采用反向策略，將存在的值建立一個(gè)高效的檢索。每次緩存取值時(shí)，先走一次判空檢索。簡單歸納下，這個(gè)框架的要求：- 快速檢索
- 內(nèi)存空間要非常小
布隆過濾器具備以上兩個(gè)條件。4、什么是布隆過濾器？布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。
- 優(yōu)點(diǎn)：空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過一般的算法。
- 缺點(diǎn)：有一定的誤識別率，刪除困難。
5、布隆過濾器如何構(gòu)建？布隆過濾器本質(zhì)上是一個(gè) n 位的二進(jìn)制數(shù)組，用0和1表示。假如我們以商品為例，有三件商品，商品編碼分別為，
id1、id2、id3a）首先，對id1，進(jìn)行三次哈希，并確定其在二進(jìn)制數(shù)組中的位置。三次哈希，對應(yīng)的二進(jìn)制數(shù)組下標(biāo)分別是 2、5、8，將原始數(shù)據(jù)從 0 變?yōu)?1。b）對
id2，進(jìn)行三次哈希，并確定其在二進(jìn)制數(shù)組中的位置。三次哈希，對應(yīng)的二進(jìn)制數(shù)組下標(biāo)分別是 2、7、98，將原始數(shù)據(jù)從 0 變?yōu)?1。下標(biāo) 2，之前已經(jīng)被操作設(shè)置成 1，則本次認(rèn)為是哈希沖突，不需要改動(dòng)。Hash 規(guī)則：如果在 Hash 后，原始位它是 0 的話，將其從 0 變?yōu)?1；如果本身這一位就是 1 的話，則保持不變。
6、布隆過濾器如何使用？
跟初始化的過程有點(diǎn)類似，當(dāng)查詢一件商品的緩存信息時(shí)，我們首先要判斷這件商品是否存在。
- 通過三個(gè)哈希函數(shù)對商品id計(jì)算哈希值
- 然后，在布隆數(shù)組中查找訪問對應(yīng)的位值，0或1
- 判斷，三個(gè)值中，只要有一個(gè)不是1，那么我們認(rèn)為數(shù)據(jù)是不存在的。
7、如何減少布隆過濾器的誤判？a）增加二進(jìn)制位數(shù)組的長度。這樣經(jīng)過hash后數(shù)據(jù)會更加的離散化，出現(xiàn)沖突的概率會大大降低b）增加Hash的次數(shù)，變相的增加數(shù)據(jù)特征，特征越多，沖突的概率越小
8、布隆過濾器會不會很費(fèi)內(nèi)存？帶著疑問，我們來做個(gè)實(shí)驗(yàn)假設(shè)有1千萬個(gè)數(shù)據(jù)，我們需要記錄其是否存在。存在的話標(biāo)記1，不存在標(biāo)記為0。技術(shù)選型，框架采用Redis的
BitMap存儲。數(shù)據(jù)初始化預(yù)熱代碼：redisTemplate.executePipelined(new?RedisCallback()?{
????@Nullable
????@Override
????public?Long?doInRedis(RedisConnection?connection)?throws?DataAccessException?{
????????connection.openPipeline();
????????for?(int?offset?=?10000000;?offset?>=?0;?offset--)?{
????????????boolean?value?=?offset?%?2?==?0???true?:?false;
????????????connection.setBit("bloom-filter-data-1".getBytes(),?offset,?value);
????????}
????????connection.closePipeline();
????????return?null;
????}
});
System.out.println("數(shù)據(jù)預(yù)熱完成");
性能有點(diǎn)慢，我們也可以采用分組形式，10000個(gè)數(shù)一組，多批次提交。
數(shù)據(jù)上傳完了后，大小 1.19M，跟我們設(shè)想的一樣。計(jì)算公式： 10000000/8/1024/1024=1.19M
9、Java應(yīng)用中，如何使用布隆過濾器？代碼實(shí)例Java語言的生態(tài)非常繁榮，提供了很多開箱即用的開源框架供我們使用。布隆過濾器也不例外，Java 中提供了一個(gè)
Redisson 的組件，它內(nèi)置了布隆過濾器。首先引入依賴包
????org.redisson
????redisson
????3.11.1
/**
?*?@author 微信公眾號：微觀技術(shù)
?*/
@Test
public?void?test5()?{
????Config?config?=?new?Config();
????config.useSingleServer().setAddress("redis://172.16.67.37:6379");
????RedissonClient?cient?=?Redisson.create(config);
????RBloomFilter?bloomFilter?=?cient.getBloomFilter("test5-bloom-filter");
????//?初始化布隆過濾器，數(shù)組長度100W，誤判率?1%
????bloomFilter.tryInit(1000000L,?0.01);
????//?添加數(shù)據(jù)
????bloomFilter.add("Tom哥");
????//?判斷是否存在
????System.out.println(bloomFilter.contains("微觀技術(shù)"));
????System.out.println(bloomFilter.contains("Tom哥"));
}
運(yùn)行結(jié)果：false???//?肯定不存在
true????//?可能存在，有1%的誤判率
注意：誤判率設(shè)置過小，會產(chǎn)生更多次的 Hash 操作，降低系統(tǒng)的性能。通常我們的建議值是 1%10、布隆過濾器二進(jìn)制數(shù)組，如何處理刪除？初始化后的布隆過濾器，可以直接拿來使用了。但是如果原始數(shù)據(jù)刪除了怎么辦？布隆過濾器二進(jìn)制數(shù)組如何維護(hù)？直接刪除不行嗎？還真不行！因?yàn)檫@里面有Hash沖突的可能，會導(dǎo)致誤刪。怎么辦？方案1：開發(fā)定時(shí)任務(wù)，每隔幾個(gè)小時(shí)，自動(dòng)創(chuàng)建一個(gè)新的布隆過濾器數(shù)組，替換老的，有點(diǎn)
CopyOnWriteArrayList的味道方案2：布隆過濾器增加一個(gè)等長的數(shù)組，存儲計(jì)數(shù)器，主要解決沖突問題，每次刪除時(shí)對應(yīng)的計(jì)數(shù)器減一，如果結(jié)果為0，更新主數(shù)組的二進(jìn)制值為011、布隆過濾器的應(yīng)用場景
- 本文重點(diǎn)介紹的，解決緩存穿透
- 網(wǎng)頁爬蟲對URL的去重，避免爬取相同的URL地址
- 反垃圾郵件，從數(shù)十億個(gè)垃圾郵件列表中判斷某郵箱是否垃圾郵箱
下載文檔
