IndexType：Bloom - 緩存穿透(Cache Penetration)

前言

上一篇我們知道了bloom filter的運作原理，
這裡我們來介紹bloom filter的實際應用。

這裡的緩存指的是Cache，在台灣翻譯成快取，
但個人比較喜歡翻譯成緩存，類似緩衝存取的概念。

Bloom具有不管資料集多大，都可以透過O(1)的效率確定資料是否存在，
如果可以事先知道資料是否存在，就可以過濾掉大部分緩存穿透問題。

緩存問題

在介紹bloom filter可以減少緩存穿透問題前，
我們先了解一下什麼是緩存穿透，並順帶一提其他緩存問題。

緩存為in memory的storage，
所以真實資料通常會存在long term persistence的裝置中(e.g. db)，
但因爲存取時間過長，所以會將部分資料存在cache之中，
當資料有更新或過期，還是需要去db等裝置中存取，然後再次暫存到cache server之中。
因此延伸了三大議題。

1。 緩存雪崩 (Cache Avalanche)
2。 緩存擊穿 (Hotspot Invalid)
3。 緩存穿透 (Cache Penetration)

緩存雪崩(大量中DB)

如cache server發生crash或大量的key過期，造成request大量的直接存取db。

緩存擊穿(中DB)

資料並不存在於 cache中，存在db中
資料並不存在於 cache中，將會進db做查詢，

緩存穿透(完全沒命中)

資料並不存在於 cache中，也不會在db之中。
資料並不存在於 cache中，將會進db做查詢， 看似非常正常的操作。
但如果量一多，就會照成問題(e.g. 使用機器人直接掃)

了解了緩存穿透後，其實緩存穿透可以透過我們學過的bloom filter來解決，
當查詢db前，先經過bloom filter，
確定資料的存在性，就可以大量的減少緩存穿透問題。

使用場景

基本上就是hash的使用場景。

1. 查詢單一資料
2. 資料基數非常大時
3. 大海撈針式查詢

Bloom filter使用範例

這裡使用redis作為我們bloom filter的使用範例。

新增值進入bloom filter

> BF.ADD newFilter foo
(integer) 1

bloom filter的name為newFilter，如果之前沒有建立過這個bloom filter，將會自動建立

一次新增多個值

> BF.MADD myFilter foo bar baz
1) (integer) 1
2) (integer) 1
3) (integer) 1

確認值是否存在newFilter這個bloom filter

> BF.EXISTS newFilter foo
(integer) 1

存在，回傳1，表示true

> BF.EXISTS newFilter notpresent
(integer) 0

不存在，回傳0，表示false

一次查詢多個值

> BF.MEXISTS myFilter foo nonexist bar
1) (integer) 1
2) (integer) 0
3) (integer) 1

我們可以將資料利用bloom filter這個結構先存下來，
當cache找不到值時，先不急著進入db查詢，
先經過bloom filter做第一層的塞選

結語

今天了解了
緩存雪崩 (Cache Avalanche)，緩存擊穿 (Hotspot Invalid)與緩存穿透 (Cache Penetration)，
並實際使用redis的bloom filter來做第一層的過濾。
那麼db中是如何使用bloom filter作為bloom index type呢？
將在明天細細介紹。

參考資料

1. Redis 布隆（Bloom Filter）過濾器原理與實戰
2. Bloom Filters – Introduction and Implementation
3. Bloom filter