牛哄哄的布隆過濾器，有什么用？
圖片來自 包圖網
本文會介紹布隆過濾器，空間換時間，以較低的內存空間、高效解決這個問題。
性能不夠，緩存來湊
現在的年輕人都喜歡網購，沒事就逛逛淘寶，剁剁手，買些自己喜歡的東西，釋放下工作壓力。
地址：
- https://detail.tmall.com/item.htm?id=628993216729
上圖是一個天貓 iPhone12 的商品詳情頁，id 表示商品的編號。
我們都知道淘寶的訪問量是非常高的，為了提升系統的吞吐量，做了很多性能優化，其中非常重要一點是將信息異構到緩存中。
有句話說的好：性能不夠，緩存來湊。但是，使用緩存時，我們要關注一個重要問題，如果緩存沒有命中怎么辦?
緩存沒有命中，怎么辦?
如上圖：
- 我們先查詢緩存，判斷緩存中是否有數據
- 如果有數據，直接返回
- 如果緩存為空，我們需要再查一次數據庫，并將數據格式異構化，然后預熱到緩沖中，然后將結果返回
注意：步驟③存在風險漏洞，如果緩存中數據不存在，壓力會轉嫁給數據庫。假如被競爭對手利用，搞無效請求流量攻擊，瞬間大量請求打到數據庫中，對系統性能產生很大影響，很容易把數據庫打掛，這種現象稱為緩存穿透。
那么如何處理緩存穿透?
我們的思路是，緩存中能不能判斷這個數據庫值的存在性，如果真的不存在，直接返回，也避免一次數據庫查詢。
由于不存在是個無限邊界，所以，我們采用反向策略，將存在的值建立一個高效的檢索。每次緩存取值時，先走一次判空檢索。
簡單歸納下，這個框架的要求：
- 快速檢索
- 內存空間要非常小
經調研，我們發現布隆過濾器具備以上兩個條件。
什么是布隆過濾器?
布隆過濾器(Bloom Filter)是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。
布隆過濾器可以用于檢索一個元素是否在一個集合中：
優點：空間效率和查詢時間都遠遠超過一般的算法。
缺點：有一定的誤識別率，刪除困難。
布隆過濾器如何構建?
布隆過濾器本質上是一個 n 位的二進制數組，用 0 和 1 表示。假如我們以商品為例，有三件商品，商品編碼分別為，id1、id2、id3。
①首先，對 id1，進行三次哈希，并確定其在二進制數組中的位置。
三次哈希，對應的二進制數組下標分別是 2、5、8，將原始數據從 0 變為 1。
②對 id2，進行三次哈希，并確定其在二進制數組中的位置。
三次哈希，對應的二進制數組下標分別是 2、7、98，將原始數據從 0 變為 1。
下標 2，之前已經被操作設置成 1，則本次認為是哈希沖突，不需要改動。
Hash 規則：如果在 Hash 后，原始位它是 0 的話，將其從 0 變為 1;如果本身這一位就是 1 的話，則保持不變。
布隆過濾器如何使用?
如下圖：
跟初始化的過程有點類似，當查詢一件商品的緩存信息時，我們首先要判斷這件商品是否存在：
- 通過三個哈希函數對商品 id 計算哈希值
- 然后，在布隆數組中查找訪問對應的位值，0 或 1
- 判斷，三個值中，只要有一個不是 1，那么我們認為數據是不存在的。
注意：布隆過濾器只能精確判斷數據不存在情況，對于存在我們只能說是可能，因為存在 Hash 沖突情況，當然這個概率非常低。
如何減少布隆過濾器的誤判?
①增加二進制位數組的長度。這樣經過 hash 后數據會更加的離散化，出現沖突的概率會大大降低。
②增加 Hash 的次數，變相的增加數據特征，特征越多，沖突的概率越小。
布隆過濾器會不會很費內存?
帶著疑問，我們來做個實驗：假設有 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
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%。
布隆過濾器二進制數組，如何處理刪除?
初始化后的布隆過濾器，可以直接拿來使用了。但是如果原始數據刪除了怎么辦?布隆過濾器二進制數組如何維護?
直接刪除不行嗎?還真不行!因為這里面有 Hash 沖突的可能，會導致誤刪。
怎么辦?
- 方案 1：開發定時任務，每隔幾個小時，自動創建一個新的布隆過濾器數組，替換老的，有點 CopyOnWriteArrayList 的味道。
- 方案 2：布隆過濾器增加一個等長的數組，存儲計數器，主要解決沖突問題，每次刪除時對應的計數器減一，如果結果為 0，更新主數組的二進制值為 0。
布隆過濾器的應用場景
如下：
本文重點介紹的，解決緩存穿透。
網頁爬蟲對 URL 的去重，避免爬取相同的 URL 地址。
反垃圾郵件，從數十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱。
作者：Tom哥
編輯：陶家龍
出處：轉載自公眾號微觀技術(ID：weiguanjishu)
