如何從10億數據中快速判斷是否存在某一個元素
前言
當 Redis 用作快取時，其目的就是為了減少資料庫訪問頻率，降低資料庫壓力，但是假如我們某些數據並不存在於 Redis 當中，那麼請求還是會直接到達資料庫，而一旦在同一時間大量快取失效或者一個不存在快取的請求被惡意攻擊訪問，這些都會導致資料庫壓力驟增，這又該如何防止呢？
快取雪崩
快取雪崩指的是 Redis 當中的大量快取在同一時間全部失效，而假如恰巧這一段時間同時又有大量請求被發起，那麼就會造成請求直接訪問到資料庫，可能會把資料庫衝垮。
快取雪崩一般形容的是快取中沒有而資料庫中有的數據，而因為時間到期導致請求直達資料庫。
解決方案
解決快取雪崩的方法有很多，常用的有以下幾種：
- 加鎖，保證單執行緒訪問快取。這樣就不會有很多請求同時訪問到資料庫。
key值的失效時間不要設置成一樣。典型的就是初始化預熱數據的時候，將數據存入快取時可以採用隨機時間來確保不會在同一時間有大量快取失效。- 記憶體允許的情況下，可以將快取設置為永不失效。
快取擊穿
快取擊穿和快取雪崩很類似，區別就是快取擊穿一般指的是單個快取失效，而同一時間又有很大的並發請求需要訪問這個 key，從而造成了資料庫的壓力。
解決方案
解決快取擊穿的方法和解決快取雪崩的方法很類似：
- 加鎖，保證單執行緒訪問快取。這樣第一個請求到達資料庫後就會重新寫入快取，後續的請求就可以直接讀取快取。
- 記憶體允許的情況下，可以將快取設置為永不失效。
快取穿透
快取穿透和上面兩種現象的本質區別就是這時候訪問的數據不但在 Redis 中不存在，而且在資料庫中也不存在，這樣如果並發過大就會造成數據源源不斷的到達資料庫，給資料庫造成極大壓力。
解決方案
對於快取穿透問題，加鎖並不能起到很好地效果，因為本身 key 就是不存在，所以即使控制了執行緒的訪問數，但是請求還是會源源不斷的到達資料庫。
解決快取穿透問題一般可以採用以下方案配合使用：
- 介面層進行校驗，發現非法的
key直接返回。比如資料庫中採用的是自增id，那麼如果來了一個非整型的id或者負數id可以直接返回，或者說如果採用的是32位uuid，那麼發現id長度不等於32位也可以直接返回。 - 將不存在的數據也進行快取，可以直接快取一個空或者其他約定好的無效
value。採用這種方案最好將key設置一個短期失效時間，否則大量不存在的key被存儲到Redis中，也會佔用大量記憶體。
布隆過濾器（Bloom Filter）
針對上面快取穿透的解決方案，我們思考一下：假如一個 key 可以繞過第 1 種方法的校驗，而此時有大量的不存在 key 被訪問（如 1 億個或者 10 億個），那麼這時候全部存儲到記憶體中，是不太現實的。
那麼有沒有一種更好的解決方案呢？這就是我們接下來要介紹的布隆過濾器，布隆過濾器就可以用儘可能小的空間存儲儘可能多的數據。
什麼是布隆過濾器
布隆過濾器（Bloom Filter）是由布隆在 1970 年提出的。它實際上是一個很長的二進位向量（點陣圖）和一系列隨機映射函數（哈希函數）。
布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的演算法要好的多，缺點是有一定的誤識別率而且刪除困難。
點陣圖（Bitmap）
Redis 當中有一種數據結構就是點陣圖，布隆過濾器其中重要的實現就是點陣圖的實現，也就是位數組，並且在這個數組中每一個位置只有 0 和 1 兩種狀態，每個位置只佔用 1 個位元組，其中 0 表示沒有元素存在，1 表示有元素存在。如下圖所示就是一個簡單的布隆過濾器示例（一個 key 值經過哈希運算和位運算就可以得出應該落在哪個位置）：
哈希碰撞
上面我們發現，lonely和wolf落在了同一個位置，這種不同的key值經過哈希運算後得到相同值的現象就稱之為哈希碰撞。發生哈希碰撞之後再經過位運算，那麼最後肯定會落在同一個位置。
如果發生過多的哈希碰撞，就會影響到判斷的準確性，所以為了減少哈希碰撞，我們一般會綜合考慮以下 2 個因素：
- 增大點陣圖數組的大小（點陣圖數組越大，佔用的記憶體越大）。
- 增加哈希函數的次數（同一個
key值經過1個函數相等了，那麼經過2個或者更多個哈希函數的計算，都得到相等結果的概率就自然會降低了）。
上面兩個方法我們需要綜合考慮：比如增大位數組，那麼就需要消耗更多的空間，而經過越多的哈希計算也會消耗 cpu 影響到最終的計算時間，所以位數組到底多大，哈希函數次數又到底需要計算多少次合適需要具體情況具體分析。
布隆過濾器的 2 大特點
下圖這個就是一個經過了 2 次哈希函數得到的布隆過濾器，根據下圖我們很容易看到，假如我們的 Redis 根本不存在，但是 Redis 經過 2 次哈希函數之後得到的兩個位置已經是 1 了（一個是 wolf 通過 f2 得到，一個是 Nosql 通過 f1 得到，這就是發生了哈希碰撞，也是布隆過濾器可能存在誤判的原因）。
所以通過上面的現象，我們從布隆過濾器的角度可以得出布隆過濾器主要有 2 大特點：
- 如果布隆過濾器判斷一個元素存在，那麼這個元素可能存在。
- 如果布隆過濾器判斷一個元素不存在，那麼這個元素一定不存在。
而從元素的角度也可以得出 2 大特點：
- 如果元素實際存在，那麼布隆過濾器一定會判斷存在。
- 如果元素不存在，那麼布隆過濾器可能會判斷存在。
PS：需要注意的是，如果經過 N 次哈希函數，則需要得到的 N 個位置都是 1 才能判定存在，只要有一個是 0，就可以判定為元素不存在布隆過濾器中。
fpp
因為布隆過濾器中總是會存在誤判率，因為哈希碰撞是不可能百分百避免的。布隆過濾器對這種誤判率稱之為假陽性概率，即：False Positive Probability，簡稱為 fpp。
在實踐中使用布隆過濾器時可以自己定義一個 fpp，然後就可以根據布隆過濾器的理論計算出需要多少個哈希函數和多大的位數組空間。需要注意的是這個 fpp 不能定義為 100%，因為無法百分保證不發生哈希碰撞。
布隆過濾器的實現（Guava）
在 Guava 的包中提供了布隆過濾器的實現，下面就通過 Guava 來體會一下布隆過濾器的應用：
- 引入
pom依賴
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>29.0-jre</version>
</dependency>
- 新建一個測試類
BloomFilterDemo：
package com.lonely.wolf.note.redis;
import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.UUID;
public class GuavaBloomFilter {
private static final int expectedInsertions = 1000000;
public static void main(String[] args) {
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),expectedInsertions);
List<String> list = new ArrayList<>(expectedInsertions);
for (int i = 0; i < expectedInsertions; i++) {
String uuid = UUID.randomUUID().toString();
bloomFilter.put(uuid);
list.add(uuid);
}
int mightContainNum1 = 0;
NumberFormat percentFormat =NumberFormat.getPercentInstance();
percentFormat.setMaximumFractionDigits(2); //最大小數位數
for (int i=0;i < 500;i++){
String key = list.get(i);
if (bloomFilter.mightContain(key)){
mightContainNum1++;
}
}
System.out.println("【key真實存在的情況】布隆過濾器認為存在的key值數：" + mightContainNum1);
System.out.println("-----------------------分割線---------------------------------");
int mightContainNum2 = 0;
for (int i=0;i < expectedInsertions;i++){
String key = UUID.randomUUID().toString();
if (bloomFilter.mightContain(key)){
mightContainNum2++;
}
}
System.out.println("【key不存在的情況】布隆過濾器認為存在的key值數：" + mightContainNum2);
System.out.println("【key不存在的情況】布隆過濾器的誤判率為：" + percentFormat.format((float)mightContainNum2 / expectedInsertions));
}
}
運行之後的結果為：
第一部分輸出的 mightContainNum1一定是和 for 循環內的值相等，也就是百分百匹配。即滿足了原則 1：如果元素實際存在，那麼布隆過濾器一定會判斷存在。
第二部分的輸出的誤判率即 fpp 總是在 3% 左右，而且隨著 for 循環的次數越大，越接近 3%。即滿足了原則 2：如果元素不存在，那麼布隆過濾器可能會判斷存在。
這個 3% 的誤判率是如何來的呢？我們進入創建布隆過濾器的 create 方法，發現默認的fpp就是 0.03：
對於這個默認的 3% 的 fpp 需要多大的位數組空間和多少次哈希函數得到的呢？在 BloomFilter 類下面有兩個 default 方法可以獲取到位數組空間大小和哈希函數的個數：
- optimalNumOfHashFunctions：獲取哈希函數的次數
- optimalNumOfBits：獲取位數組大小
debug 進去看一下：
得到的結果是 7298440 bit=0.87M，然後經過了 5 次哈希運算。可以發現這個空間佔用是非常小的，100W 的 key 才佔用了 0.87M。
PS：點擊這裡可以進入網站計算 bit 數組大小和哈希函數個數。
布隆過濾器的如何刪除
布隆過濾器判斷一個元素存在就是判斷對應位置是否為 1 來確定的，但是如果要刪除掉一個元素是不能直接把 1 改成 0 的，因為這個位置可能存在其他元素，所以如果要支援刪除，那我們應該怎麼做呢？最簡單的做法就是加一個計數器，就是說位數組的每個位如果不存在就是 0，存在幾個元素就存具體的數字，而不僅僅只是存 1，那麼這就有一個問題，本來存 1 就是一位就可以滿足了，但是如果要存具體的數字比如說 2，那就需要 2 位了，所以帶有計數器的布隆過濾器會佔用更大的空間。
帶有計數器的布隆過濾器
下面就是一個帶有計數器的布隆過濾器示例：
pom文件引入依賴：
<dependency>
<groupId>com.baqend</groupId>
<artifactId>bloom-filter</artifactId>
<version>1.0.7</version>
</dependency>
- 新建一個帶有計數器的布隆過濾器
CountingBloomFilter：
package com.lonelyWolf.redis.bloom;
import orestes.bloomfilter.FilterBuilder;
public class CountingBloomFilter {
public static void main(String[] args) {
orestes.bloomfilter.CountingBloomFilter<String> cbf = new FilterBuilder(10000,
0.01).countingBits(8).buildCountingBloomFilter();
cbf.add("zhangsan");
cbf.add("lisi");
cbf.add("wangwu");
System.out.println("是否存在王五：" + cbf.contains("wangwu")); //true
cbf.remove("wangwu");
System.out.println("是否存在王五：" + cbf.contains("wangwu")); //false
}
}
構建布隆過濾器前面 2 個參數一個就是期望的元素數，一個就是 fpp 值，後面的 countingBits 參數就是計數器佔用的大小，這裡傳了一個 8 位，即最多允許 255 次重複，如果不傳的話這裡默認是 16 位大小，即允許 65535次重複。
總結
本文主要講述了使用 Redis 存在的三種問題：快取雪崩，快取擊穿和快取穿透。並分別對每種問題的解決方案進行了描述，最後著重介紹了快取穿透的解決方案：布隆過濾器。原生的布隆過濾器不支援刪除，但是可以引入一個計數器實現帶有計數器的布隆過濾器來實現刪除功能，同時在最後也提到了，帶有計數器的布隆過濾器會佔用更多的空間問題。
