什麼是布隆過濾器?如何解決高併發緩存穿透問題?
大家好,我是 Tom 哥~
日常開發中,大家經常使用緩存,但是你知道大型的互聯網公司面對高併發流量,要注意緩存穿透問題嗎!!! 本文會介紹布隆過濾器,空間換時間,以較低的內存空間、高效解決這個問題。
本篇文章的目錄:
1、性能不夠,緩存來湊
現在的年輕人都喜歡網購,沒事就逛逛淘寶,剁剁手,買些自己喜歡的東西,釋放下工作壓力。
地址:
https://detail.tmall.com/item.htm?id=628993216729
上圖是一個天貓 iphone12 的商品詳情頁
,id 表示商品的編號
我們都知道淘寶的訪問量是非常高的,爲了提升系統的吞吐量,做了很多性能優化,其中非常重要一點是將信息異構到緩存中。
有句話說的好:性能不夠,緩存來湊。
但是,使用緩存時,我們要關注一個重要問題,如果緩存沒有命中怎麼辦?
2、緩存沒有命中,怎麼辦?
-
①我們先查詢緩存,判斷緩存中是否有數據
-
②如果有數據,直接返回
-
③如果緩存爲空,我們需要再查一次數據庫,並將數據格式異構化,然後預熱到緩衝中,然後將結果返回
注意:
步驟 ③ 存在風險漏洞,如果緩存中數據不存在,壓力會轉嫁給數據庫。假如被競爭對手利用,搞無效請求流量攻擊,瞬間大量請求打到數據庫中,對系統性能產生很大影響,很容易把數據庫打掛,這種現象稱爲緩存穿透。
3、那麼如何處理緩存穿透?
我們的思路是,緩存中能不能判斷這個數據庫值的存在性,如果真的不存在,直接返回,也避免一次數據庫查詢。
由於不存在是個無限邊界
,所以,我們採用反向策略,將存在的值建立一個高效的檢索。每次緩存取值時,先走一次判空檢索。
簡單歸納下,這個框架的要求:
-
快速檢索
-
內存空間要非常小
經調研,我們發現布隆過濾器
具備以上兩個條件。
4、什麼是布隆過濾器?
布隆過濾器(Bloom Filter)是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用於檢索一個元素是否在一個集合中。
-
優點:空間效率和查詢時間都遠遠超過一般的算法。
-
缺點:有一定的誤識別率,刪除困難。
5、布隆過濾器如何構建?
布隆過濾器本質上是一個 n 位的二進制數組,用 0 和 1 表示。
假如我們以商品爲例,有三件商品,商品編碼分別爲,id1
、id2
、id3
a)首先,對id1
,進行三次哈希,並確定其在二進制數組中的位置。
三次哈希,對應的二進制數組下標分別是 2、5、8,將原始數據從 0 變爲 1。
b)對id2
,進行三次哈希,並確定其在二進制數組中的位置。
三次哈希,對應的二進制數組下標分別是 2、7、98,將原始數據從 0 變爲 1。
下標 2,之前已經被操作設置成 1,則本次認爲是哈希衝突,不需要改動。
Hash 規則:如果在 Hash 後,原始位它是 0 的話,將其從 0 變爲 1;如果本身這一位就是 1 的話,則保持不變。
6、布隆過濾器如何使用?
跟初始化的過程有點類似,當查詢一件商品的緩存信息時,我們首先要判斷這件商品是否存在。
-
通過三個哈希函數對商品 id 計算哈希值
-
然後,在布隆數組中查找訪問對應的位值,0 或 1
-
判斷,三個值中,只要有一個不是 1,那麼我們認爲數據是不存在的。
注意:布隆過濾器只能精確判斷數據不存在情況,對於存在我們只能說是可能,因爲存在 Hash 衝突情況,當然這個概率非常低。
7、如何減少布隆過濾器的誤判?
a)增加二進制位數組的長度。這樣經過 hash 後數據會更加的離散化,出現衝突的概率會大大降低
b)增加 Hash 的次數,變相的增加數據特徵,特徵越多,衝突的概率越小
8、布隆過濾器會不會很費內存?
帶着疑問,我們來做個實驗
假設有 1 千萬個數據,我們需要記錄其是否存在。存在的話標記 1,不存在標記爲 0。技術選型,框架採用 Redis 的BitMap
存儲。
數據初始化預熱代碼:
redisTemplate.executePipelined(new RedisCallback<Long>() {
@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("數據預熱完成");
性能有點慢,我們也可以採用分組形式,10000 個數一組,多批次提交。
數據上傳完了後,大小 1.19M,跟我們設想的一樣。
計算公式: 10000000/8/1024/1024=1.19M
9、Java 應用中,如何使用布隆過濾器?代碼實例
Java 語言的生態非常繁榮,提供了很多開箱即用的開源框架供我們使用。布隆過濾器也不例外,Java 中提供了一個 Redisson
的組件,它內置了布隆過濾器。
首先引入依賴包
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.11.1</version>
</dependency>
代碼示例:
/**
* @author 微信公衆號:微觀技術
*/
@Test
public void test5() {
Config config = new Config();
config.useSingleServer().setAddress("redis://172.16.67.37:6379");
RedissonClient cient = Redisson.create(config);
RBloomFilter<String> bloomFilter = cient.getBloomFilter("test5-bloom-filter");
// 初始化布隆過濾器,數組長度100W,誤判率 1%
bloomFilter.tryInit(1000000L, 0.01);
// 添加數據
bloomFilter.add("Tom哥");
// 判斷是否存在
System.out.println(bloomFilter.contains("微觀技術"));
System.out.println(bloomFilter.contains("Tom哥"));
}
運行結果:
false // 肯定不存在
true // 可能存在,有1%的誤判率
注意:誤判率設置過小,會產生更多次的 Hash 操作,降低系統的性能。通常我們的建議值是 1%
10、布隆過濾器二進制數組,如何處理刪除?
初始化後的布隆過濾器,可以直接拿來使用了。但是如果原始數據刪除了怎麼辦?布隆過濾器二進制數組如何維護?
直接刪除不行嗎?
還真不行!因爲這裏面有 Hash 衝突的可能,會導致誤刪。
怎麼辦?
方案 1:開發定時任務,每隔幾個小時,自動創建一個新的布隆過濾器數組,替換老的,有點CopyOnWriteArrayList
的味道
方案 2:布隆過濾器增加一個等長的數組,存儲計數器,主要解決衝突問題,每次刪除時對應的計數器減一,如果結果爲 0,更新主數組的二進制值爲 0
11、布隆過濾器的應用場景
-
本文重點介紹的,解決緩存穿透
-
網頁爬蟲對 URL 的去重,避免爬取相同的 URL 地址
-
反垃圾郵件,從數十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱
關於我:前阿里架構師,出過專利,競賽拿過獎,CSDN 博客專家,負責過電商交易、社區生鮮、營銷、金融等業務,多年團隊管理經驗,愛思考,喜歡結交朋友
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/3OIbp837pTAvQaRlmzU7Nw