什么是布隆過濾器？如何解決高并發(fā)緩存穿透問題？

日常開發(fā)中，大家經常使用緩存，但是你知道大型的互聯(lián)網(wǎng)公司面對高并發(fā)流量，要注意緩存穿透問題嗎!!!    本文會介紹布隆過濾器，空間換時間，以較低的內存空間、高效解決這個問題。

本篇文章的目錄：

1、性能不夠，緩存來湊

現(xiàn)在的年輕人都喜歡網(wǎng)購，沒事就逛逛淘寶，剁剁手，買些自己喜歡的東西，釋放下工作壓力。

地址：

https://detail.tmall.com/item.htm?id=628993216729

上圖是一個天貓 iphone12 的商品詳情頁，id表示商品的編號

我們都知道淘寶的訪問量是非常高的，為了提升系統(tǒng)的吞吐量，做了很多性能優(yōu)化，其中非常重要一點是將信息異構到緩存中。

有句話說的好：性能不夠，緩存來湊。

但是，使用緩存時，我們要關注一個重要問題，如果緩存沒有命中怎么辦？

2、緩存沒有命中，怎么辦？

• ①我們先查詢緩存，判斷緩存中是否有數(shù)據(jù)
• ②如果有數(shù)據(jù)，直接返回
• ③如果緩存為空，我們需要再查一次數(shù)據(jù)庫，并將數(shù)據(jù)格式異構化，然后預熱到緩沖中，然后將結果返回

注意：

步驟 ③ 存在風險漏洞，如果緩存中數(shù)據(jù)不存在，壓力會轉嫁給數(shù)據(jù)庫。假如被競爭對手利用，搞無效請求流量攻擊，瞬間大量請求打到數(shù)據(jù)庫中，對系統(tǒng)性能產生很大影響，很容易把數(shù)據(jù)庫打掛，這種現(xiàn)象稱為緩存穿透。

3、那么如何處理緩存穿透？

我們的思路是，緩存中能不能判斷這個數(shù)據(jù)庫值的存在性，如果真的不存在，直接返回，也避免一次數(shù)據(jù)庫查詢。

由于不存在是個無限邊界，所以，我們采用反向策略，將存在的值建立一個高效的檢索。每次緩存取值時，先走一次判空檢索。

簡單歸納下，這個框架的要求：

• 快速檢索
• 內存空間要非常小

經調研，我們發(fā)現(xiàn)布隆過濾器具備以上兩個條件。

4、什么是布隆過濾器？

布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。

• 優(yōu)點：空間效率和查詢時間都遠遠超過一般的算法。
• 缺點：有一定的誤識別率，刪除困難。

5、布隆過濾器如何構建？

布隆過濾器本質上是一個 n 位的二進制數(shù)組，用0和1表示。

假如我們以商品為例，有三件商品，商品編碼分別為，id1、id2、id3

a）首先，對id1，進行三次哈希，并確定其在二進制數(shù)組中的位置。

三次哈希，對應的二進制數(shù)組下標分別是 2、5、8，將原始數(shù)據(jù)從 0 變?yōu)?1。

b）對id2，進行三次哈希，并確定其在二進制數(shù)組中的位置。

三次哈希，對應的二進制數(shù)組下標分別是 2、7、98，將原始數(shù)據(jù)從 0 變?yōu)?1。

下標 2，之前已經被操作設置成 1，則本次認為是哈希沖突，不需要改動。

Hash 規(guī)則：如果在 Hash 后，原始位它是 0 的話，將其從 0 變?yōu)?1；如果本身這一位就是 1 的話，則保持不變。

6、布隆過濾器如何使用？

跟初始化的過程有點類似，當查詢一件商品的緩存信息時，我們首先要判斷這件商品是否存在。

• 通過三個哈希函數(shù)對商品id計算哈希值
• 然后，在布隆數(shù)組中查找訪問對應的位值，0或1
• 判斷，三個值中，只要有一個不是1，那么我們認為數(shù)據(jù)是不存在的。

注意：布隆過濾器只能精確判斷數(shù)據(jù)不存在情況，對于存在我們只能說是可能，因為存在Hash沖突情況，當然這個概率非常低。

7、如何減少布隆過濾器的誤判？

a）增加二進制位數(shù)組的長度。這樣經過hash后數(shù)據(jù)會更加的離散化，出現(xiàn)沖突的概率會大大降低

b）增加Hash的次數(shù)，變相的增加數(shù)據(jù)特征，特征越多，沖突的概率越小

8、布隆過濾器會不會很費內存？

帶著疑問，我們來做個實驗

假設有1千萬個數(shù)據(jù)，我們需要記錄其是否存在。存在的話標記1，不存在標記為0。技術選型，框架采用Redis的BitMap存儲。

數(shù)據(jù)初始化預熱代碼：

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("數(shù)據(jù)預熱完成");

性能有點慢，我們也可以采用分組形式，10000個數(shù)一組，多批次提交。

數(shù)據(jù)上傳完了后，大小 1.19M，跟我們設想的一樣。

計算公式： 10000000/8/1024/1024=1.19M

9、Java應用中，如何使用布隆過濾器？代碼實例

Java語言的生態(tài)非常繁榮，提供了很多開箱即用的開源框架供我們使用。布隆過濾器也不例外，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");
    // 初始化布隆過濾器，數(shù)組長度100W，誤判率 1%
    bloomFilter.tryInit(1000000L, 0.01);
    // 添加數(shù)據(jù)
    bloomFilter.add("Tom哥");
    // 判斷是否存在
    System.out.println(bloomFilter.contains("微觀技術"));
    System.out.println(bloomFilter.contains("Tom哥"));
}

運行結果：

false   // 肯定不存在
true    // 可能存在，有1%的誤判率

注意：誤判率設置過小，會產生更多次的 Hash 操作，降低系統(tǒng)的性能。通常我們的建議值是 1%

10、布隆過濾器二進制數(shù)組，如何處理刪除？

初始化后的布隆過濾器，可以直接拿來使用了。但是如果原始數(shù)據(jù)刪除了怎么辦？布隆過濾器二進制數(shù)組如何維護？

直接刪除不行嗎？

還真不行！因為這里面有Hash沖突的可能，會導致誤刪。

怎么辦？

方案1：開發(fā)定時任務，每隔幾個小時，自動創(chuàng)建一個新的布隆過濾器數(shù)組，替換老的，有點CopyOnWriteArrayList的味道

方案2：布隆過濾器增加一個等長的數(shù)組，存儲計數(shù)器，主要解決沖突問題，每次刪除時對應的計數(shù)器減一，如果結果為0，更新主數(shù)組的二進制值為0

11、布隆過濾器的應用場景

• 本文重點介紹的，解決緩存穿透
• 網(wǎng)頁爬蟲對URL的去重，避免爬取相同的URL地址
• 反垃圾郵件，從數(shù)十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱