緩存穿透
什麼是緩存穿透?
緩存穿透說簡單點就是大量請求的 key 根本不存在于緩存中,
導緻請求直接到了資料庫上,根本沒有經過緩存這一層。
舉個例子:
某個黑客故意制造我們緩存中不存在的 key 發起大量請求,導緻大量請求落到資料庫。
最終導緻:
使用者的請求最終都要跑到資料庫中查詢一遍。
有哪些解決辦法?
最基本的就是首先做好參數校驗,
一些不合法的參數請求直接抛出異常資訊傳回給用戶端。
比如查詢的資料庫 id 不能小于 0、
傳入的郵箱格式不對的時候直接傳回錯誤消息給用戶端等等。
1)緩存無效 key
如果緩存和資料庫都查不到某個 key 的資料就寫一個到 Redis 中去并設定過期時間,
具體指令如下: SET key value EX 10086 。
這種方式可以解決請求的 key 變化不頻繁的情況,
如果黑客惡意攻擊,每次建構不同的請求 key,會導緻 Redis 中緩存大量無效的 key 。
很明顯,這種方案并不能從根本上解決此問題。
如果非要用這種方式來解決穿透問題的話,
盡量将無效的 key 的過期時間設定短一點比如 1 分鐘。
一般情況下我們是這樣設計 key 的: 表名:列名:主鍵名:主鍵值 。
如果用 Java 代碼展示的話,差不多是下面這樣的:
public Object getObjectInclNullById(Integer id) {
// 從緩存中擷取資料
Object cacheValue = cache.get(id);
// 緩存為空
if (cacheValue == null) {
// 從資料庫中擷取
Object storageValue = storage.get(key);
// 緩存空對象
cache.set(key, storageValue);
// 如果存儲資料為空,需要設定一個過期時間(300秒)
if (storageValue == null) {
// 必須設定過期時間,否則有被攻擊的風險
cache.expire(key, 60 * 5);
}
return storageValue;
}
return cacheValue;
}
2)布隆過濾器
布隆過濾器是一個非常神奇的資料結構,
通過它我們可以非常友善地判斷一個給定資料是否存在于海量資料中。
具體是這樣做的:把所有可能存在的請求的值都存放在布隆過濾器中,
當使用者請求過來,先判斷使用者發來的請求的值是否存在于布隆過濾器中。
不存在的話,直接傳回請求參數錯誤資訊給用戶端,存在的話才會走下面的流程。
緩存雪崩
緩存雪崩描述的就是這樣一個簡單的場景:
緩存在同一時間大面積的失效,後面的請求都直接落到了資料庫上,
造成資料庫短時間内承受大量請求。 這就好比雪崩一樣,摧枯拉朽之勢,
資料庫的壓力可想而知,可能直接就被這麼多請求弄當機了。
舉個例子:系統的緩存子產品出了問題比如當機導緻不可用。
造成系統的所有通路,都要走資料庫。
還有一種緩存雪崩的場景是:
有一些被大量通路資料(熱點緩存)在某一時刻大面積失效,
導緻對應的請求直接落到了資料庫上。 這樣的情況,有下面幾種解決辦法:
舉個例子 :秒殺開始 12 個小時之前,我們統一存放了一批商品到 Redis 中,
設定的緩存過期時間也是 12 個小時,那麼秒殺開始的時候,
這些秒殺的商品的通路直接就失效了。導緻的情況就是,
相應的請求直接就落到了資料庫上,就像雪崩一樣可怕。
解決辦法
針對 Redis 服務不可用的情況:
采用 Redis 叢集,避免單機出現問題整個緩存服務都沒辦法使用。
限流,避免同時處理大量的請求。
針對熱點緩存失效的情況:
設定不同的失效時間比如随機設定緩存的失效時間。
緩存永不失效。
保證緩存和資料庫資料的一緻性
** Cache Aside Pattern(旁路緩存模式)**
Cache Aside Pattern 中遇到寫請求是這樣的:更新 DB,然後直接删除 cache 。
如果更新資料庫成功,而删除緩存這一步失敗的情況的話,
簡單說兩個解決方案:
緩存失效時間變短(不推薦,治标不治本) :
我們讓緩存資料的過期時間變短,這樣的話緩存就會從資料庫中加載資料。
另外,這種解決辦法對于先操作緩存後操作資料庫的場景不适用。
增加 cache 更新重試機制(常用):
如果 cache 服務目前不可用導緻緩存删除失敗的話,我們就隔一段時間進行重試,
重試次數可以自己定。如果多次重試還是失敗的話,
我們可以把目前更新失敗的 key 存入隊列中,
等緩存服務可用之後,再将 緩存中對應的 key 删除即可。
布隆過濾器
什麼是布隆過濾器?
布隆過濾器(Bloom Filter)是一個叫做 Bloom 的老哥于1970年提出的。
我們可以把它看作由二進制向量(或者說位數組)
和一系列随機映射函數(哈希函數)兩部分組成的資料結構。
相比于我們平時常用的的 List、Map 、Set 等資料結構,它占用空間更少并且效率更高,
但是缺點是其傳回的結果是機率性的,而不是非常準确的。
理論情況下添加到集合中的元素越多,誤報的可能性就越大。
并且,存放在布隆過濾器的資料不容易删除。
位數組中的每個元素都隻占用 1 bit ,并且每個元素隻能是 0 或者 1。
這樣申請一個 100w 個元素的位數組
隻占用 1000000Bit / 8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空間。
總結:一個名叫 Bloom 的人提出了一種來檢索元素是否在給定大集合中的資料結構,
這種資料結構是高效且性能很好的,但缺點是具有一定的錯誤識别率和删除難度。
并且,理論情況下,添加到集合中的元素越多,誤報的可能性就越大。
布隆過濾器的原理
當一個元素加入布隆過濾器中的時候,會進行如下操作:
使用布隆過濾器中的哈希函數對元素值進行計算,
得到哈希值(有幾個哈希函數得到幾個哈希值)。
根據得到的哈希值,在位數組中把對應下标的值置為 1。
當我們需要判斷一個元素是否存在于布隆過濾器的時候,會進行如下操作:
對給定元素再次進行相同的哈希計算;
得到值之後判斷位數組中的每個元素是否都為 1,
如果值都為 1,那麼說明這個值在布隆過濾器中,
如果存在一個值不為 1,說明該元素不在布隆過濾器中。
如圖所示,當字元串存儲要加入到布隆過濾器中時,
該字元串首先由多個哈希函數生成不同的哈希值,
然後在對應的位數組的下表的元素設定為 1(當位數組初始化時 ,所有位置均為0)。
當第二次存儲相同字元串時,因為先前的對應位置已設定為 1,
是以很容易知道此值已經存在(去重非常友善)。
如果我們需要判斷某個字元串是否在布隆過濾器中時,
隻需要對給定字元串再次進行相同的哈希計算,
得到值之後判斷位數組中的每個元素是否都為 1,如果值都為 1,
那麼說明這個值在布隆過濾器中,如果存在一個值不為 1,說明該元素不在布隆過濾器中。
不同的字元串可能哈希出來的位置相同,
這種情況我們可以适當增加位數組大小或者調整我們的哈希函數。
綜上,我們可以得出:布隆過濾器說某個元素存在,小機率會誤判。
布隆過濾器說某個元素不在,那麼這個元素一定不在。
布隆過濾器使用場景
判斷給定資料是否存在:
比如判斷一個數字是否存在于包含大量數字的數字集中(數字集很大,5億以上!)、
防止緩存穿透(判斷請求的資料是否有效避免直接繞過緩存請求資料庫)等等、
郵箱的垃圾郵件過濾、黑名單功能等等。
去重:比如爬給定網址的時候對已經爬取過的 URL 去重。
通過 Java 程式設計手動實作布隆過濾器
import java.util.BitSet;
public class MyBloomFilter {
/**
* 位數組的大小
*/
private static final int DEFAULT_SIZE = 2 << 24;
/**
* 通過這個數組可以建立 6 個不同的哈希函數
*/
private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};
/**
* 位數組。數組中的元素隻能是 0 或者 1
*/
private BitSet bits = new BitSet(DEFAULT_SIZE);
/**
* 存放包含 hash 函數的類的數組
*/
private SimpleHash[] func = new SimpleHash[SEEDS.length];
/**
* 初始化多個包含 hash 函數的類的數組,每個類中的 hash 函數都不一樣
*/
public MyBloomFilter() {
// 初始化多個不同的 Hash 函數
for (int i = 0; i < SEEDS.length; i++) {
func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
}
}
/**
* 添加元素到位數組
*/
public void add(Object value) {
for (SimpleHash f : func) {
bits.set(f.hash(value), true);
}
}
/**
* 判斷指定元素是否存在于位數組
*/
public boolean contains(Object value) {
boolean ret = true;
for (SimpleHash f : func) {
ret = ret && bits.get(f.hash(value));
}
return ret;
}
/**
* 靜态内部類。用于 hash 操作!
*/
public static class SimpleHash {
private int cap;
private int seed;
public SimpleHash(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}
/**
* 計算 hash 值
*/
public int hash(Object value) {
int h;
return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
}
}
}
測試:
String value1 = "https://java.com";
String value2 = "https://github.com";
MyBloomFilter filter = new MyBloomFilter();
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
filter.add(value1);
filter.add(value2);
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
Output:
false
false
true
true
Google開源的 Guava中自帶的布隆過濾器
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>28.0-jre</version>
</dependency>
我們建立了一個最多存放 最多 1500個整數的布隆過濾器,
并且我們可以容忍誤判的機率為百分之(0.01)
// 建立布隆過濾器對象
BloomFilter<Integer> filter = BloomFilter.create(
Funnels.integerFunnel(),
1500,
0.01);
// 判斷指定元素是否存在
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
// 将元素添加進布隆過濾器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
在我們的示例中,當mightContain() 方法傳回true時,
我們可以99%确定該元素在過濾器中,當過濾器傳回false時,
我們可以100%确定該元素不存在于過濾器中。
Guava 提供的布隆過濾器的實作還是很不錯的(想要詳細了解的可以看一下它的源碼實作),
但是它有一個重大的缺陷就是隻能單機使用(另外,容量擴充也不容易),
而現在網際網路一般都是分布式的場景。
為了解決這個問題,我們就需要用到 Redis 中的布隆過濾器了。
Redis 中的布隆過濾器
使用Docker安裝
如果我們需要體驗 Redis 中的布隆過濾器非常簡單,
通過 Docker 就可以了!我們直接在 Google 搜尋docker redis bloomfilter
具體位址:https://hub.docker.com/r/redislabs/rebloom/
~ docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
~ docker exec -it redis-redisbloom bash
root@21396d02c252:/data# redis-cli
127.0.0.1:6379>
注意: key:布隆過濾器的名稱,item : 添加的元素。
BF.ADD :将元素添加到布隆過濾器中,
如果該過濾器尚不存在,則建立該過濾器。
格式:BF.ADD {key} {item}。
BF.MADD : 将一個或多個元素添加到“布隆過濾器”中,
并建立一個尚不存在的過濾器。
該指令的操作方式BF.ADD與之相同,
隻不過它允許多個輸入并傳回多個值。
格式:BF.MADD {key} {item} [item ...] 。
BF.EXISTS : 确定元素是否在布隆過濾器中存在。
格式:BF.EXISTS {key} {item}。
BF.MEXISTS : 确定一個或者多個元素是否在布隆過濾器中存在
格式:BF.MEXISTS {key} {item} [item ...]
另外,BF.RESERVE 指令需要單獨介紹一下:
這個指令的格式如下:
BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion] 。
下面簡單介紹一下每個參數的具體含義:
key:布隆過濾器的名稱
error_rate :誤報的期望機率。這應該是介于0到1之間的十進制值。
例如,對于期望的誤報率0.1%(1000中為1),error_rate應該設定為0.001。
該數字越接近零,則每個項目的記憶體消耗越大,并且每個操作的CPU使用率越高。
capacity: 過濾器的容量。當實際存儲的元素個數超過這個值之後,性能将開始下降。
實際的降級将取決于超出限制的程度。随着過濾器元素數量呈指數增長,性能将線性下降。
可選參數:
expansion:如果建立了一個新的子過濾器,
則其大小将是目前過濾器的大小乘以expansion。預設擴充值為2。
這意味着每個後續子過濾器将是前一個子過濾器的兩倍。
例如:
127.0.0.1:6379> BF.ADD myFilter java
(integer) 1
127.0.0.1:6379> BF.ADD myFilter python
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter java
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter python
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter github
(integer) 0