緩存穿透和布隆演算法一樣嗎

A. 什麼是緩存穿透

緩存穿透又稱緩存擊穿,是指在高並發場景下緩存中(包括本地緩存和Redis緩存)的某一個Key被高並發的訪問沒有命中,此時回去資料庫中訪問數據,導致資料庫並發的執行大量查詢操作,對DB造成巨大的壓力。

B. 布隆過濾器詳解

布隆過濾器 （英語：Bloom Filter）是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。主要用於判斷一個元素是否在一個集合中。

通常我們會遇到很多要判斷一個元素是否在某個集合中的業務場景，一般想到的是將集合中所有元素保存起來，然後通過比較確定。鏈表、樹、散列表（又叫哈希表，Hash table）等等數據結構都是這種思路。但是隨著集合中元素的增加，我們需要的存儲空間也會呈現線性增長，最終達到瓶頸。同時檢索速度也越來越慢，上述三種結構的檢索時間復雜度分別為 ， ， 。

這個時候，布隆過濾器（Bloom Filter）就應運而生。

了解布隆過濾器原理之前，先回顧下 Hash 函數原理。

哈希函數的概念是：將任意大小的輸入數據轉換成特定大小的輸出數據的函數，轉換後的數據稱為哈希值或哈希編碼，也叫散列值。下面是一幅示意圖：

所有散列函數都有如下基本特性：

但是用 hash表存儲大數據量時，空間效率還是很低，當只有一個 hash 函數時，還很容易發生哈希碰撞。

BloomFilter 是由一個固定大小的二進制向量或者點陣圖（bitmap）和一系列映射函數組成的。

在初始狀態時，對於長度為 m 的位數組，它的所有位都被置為0，如下圖所示：

當有變數被加入集合時，通過 K 個映射函數將這個變數映射成點陣圖中的 K 個點，把它們置為 1（假定有兩個變數都通過 3 個映射函數）。

查詢某個變數的時候我們只要看看這些點是不是都是 1 就可以大概率知道集合中有沒有它了

為什麼說是可能存在，而不是一定存在呢？那是因為映射函數本身就是散列函數，散列函數是會有碰撞的。

布隆過濾器的誤判是指多個輸入經過哈希之後在相同的bit位置1了，這樣就無法判斷究竟是哪個輸入產生的，因此誤判的根源在於相同的 bit 位被多次映射且置 1。

這種情況也造成了布隆過濾器的刪除問題，因為布隆過濾器的每一個 bit 並不是獨占的，很有可能多個元素共享了某一位。如果我們直接刪除這一位的話，會影響其他的元素。(比如上圖中的第 3 位)

相比於其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數 ，另外，散列函數相互之間沒有關系，方便由硬體並行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。

布隆過濾器可以表示全集，其它任何數據結構都不能；

但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。但是如果元素數量太少，則使用散列表足矣。

另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位數組變成整數數組，每插入一個元素相應的計數器加 1, 這樣刪除元素時將計數器減掉就可以了。然而要保證安全地刪除元素並非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器裡面。這一點單憑這個過濾器是無法保證的。另外計數器回繞也會造成問題。

在降低誤算率方面，有不少工作，使得出現了很多布隆過濾器的變種。

在程序的世界中，布隆過濾器是程序員的一把利器，利用它可以快速地解決項目中一些比較棘手的問題。

如網頁 URL 去重、垃圾郵件識別、大集合中重復元素的判斷和緩存穿透等問題。

布隆過濾器的典型應用有：

知道了布隆過濾去的原理和使用場景，我們可以自己實現一個簡單的布隆過濾器

分布式環境中，布隆過濾器肯定還需要考慮是可以共享的資源，這時候我們會想到 Redis，是的，Redis 也實現了布隆過濾器。

當然我們也可以把布隆過濾器通過 bloomFilter.writeTo() 寫入一個文件，放入OSS、S3這類對象存儲中。

Redis 提供的 bitMap 可以實現布隆過濾器，但是需要自己設計映射函數和一些細節，這和我們自定義沒啥區別。

Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之後才正式登場。布隆過濾器作為一個插件載入到 Redis Server 中，給 Redis 提供了強大的布隆去重功能。

在已安裝 Redis 的前提下，安裝 RedisBloom，有兩種方式

直接編譯進行安裝

使用Docker進行安裝

使用

布隆過濾器基本指令：

我們只有這幾個參數，肯定不會有誤判，當元素逐漸增多時，就會有一定的誤判了，這里就不做這個實驗了。

上面使用的布隆過濾器只是默認參數的布隆過濾器，它在我們第一次 add 的時候自動創建。

Redis 還提供了自定義參數的布隆過濾器， bf.reserve 過濾器名 error_rate initial_size

但是這個操作需要在 add 之前顯式創建。如果對應的 key 已經存在，bf.reserve 會報錯

我是一名 javaer，肯定還要用 Java 來實現的，Java 的 Redis 客戶端比較多，有些還沒有提供指令擴展機制，筆者已知的 Redisson 和 lettuce 是可以使用布隆過濾器的，我們這里用 Redisson

為了解決布隆過濾器不能刪除元素的問題，布穀鳥過濾器橫空出世。論文《Cuckoo Filter：Better Than Bloom》作者將布穀鳥過濾器和布隆過濾器進行了深入的對比。相比布穀鳥過濾器而言布隆過濾器有以下不足：查詢性能弱、空間利用效率低、不支持反向操作（刪除）以及不支持計數。

由於使用較少，暫不深入。

https://www.cs.cmu.e/~dga/papers/cuckoo-conext2014.pdf

http://www.justdojava.com/2019/10/22/bloomfilter/

https://www.cnblogs.com/cpselvis/p/6265825.html

https://juejin.im/post/5cc5aa7ce51d456e431adac5

C. 該怎麼解決 Redis 緩存穿透和緩存雪崩問題

緩存雪崩： 由於緩存層承載著大量請求，有效地 保護了存儲層，但是如果緩存層由於某些原因不能提供服務，比如 Redis 節點掛掉了，熱點 key 全部失效了，在這些情況下，所有的請求都會直接請求到資料庫，可能會造成資料庫宕機的情況。
預防和解決緩存雪崩問題，可以從以下三個方面進行著手：
1、使用 Redis 高可用架構：使用 Redis 集群來保證 Redis 服務不會掛掉
2、緩存時間不一致： 給緩存的失效時間，加上一個隨機值，避免集體失效
3、限流降級策略：有一定的備案，比如個性推薦服務不可用了，換成熱點數據推薦服務
緩存穿透： 緩存穿透是指查詢一個根本不存在的數據，這樣的數據肯定不在緩存中，這會導致請求全部落到資料庫上，有可能出現資料庫宕機的情況。
預防和解決緩存穿透問題，可以考慮以下兩種方法：
1、緩存空對象： 將空值緩存起來，但是這樣就有一個問題，大量無效的空值將佔用空間，非常浪費。
2、布隆過濾器攔截： 將所有可能的查詢key 先映射到布隆過濾器中，查詢時先判斷key是否存在布隆過濾器中，存在才繼續向下執行，如果不存在，則直接返回。布隆過濾器有一定的誤判，所以需要你的業務允許一定的容錯性。

D. 緩存擊穿、穿透、雪崩及Redis分布式鎖

分布式鎖: setnx ,redisson 並發問題
冪等問題: 落表狀態,Redis

緩存擊穿: 指緩存中無,db中有
原因: 一個key高並發恰好失效導致大量請求到db
方案: 加鎖,自旋鎖,或一個線程查db,一個線程監控(直接用Redisson分布式鎖)

緩存穿透:指緩存和db中均無
原因: 一般是惡意請求
方案: 加布隆過濾,或查db無時,也設置緩存,value為某些特殊表示或"null"

雪崩:指緩存同時大量失效
原因: 大量的key同時失效,db壓力加大
方案: 設置失效時間是增加隨機數

問題方案文獻:
https://www.jianshu.com/p/31ab9b020cd9 (圖例分析)

https://blog.csdn.net/fcvtb/article/details/89478554

Redis分布式鎖:

事務未執行完鎖已到期釋放問題：使用Redissoin解決續租問題，內部已解決

分布式鎖文獻:
https://www.jianshu.com/p/4838f8be00c9
https://blog.csdn.net/qq_30038111/article/details/90696233 (setnx + expire同時操作)

====================================

https://www.runoob.com/redis/keys-scan.html
https://www.jianshu.com/p/611a492d9121 Redis原理與應用

E. 緩存穿透的意義

緩存穿透是指查詢一個一定不存在的數據，由於緩存是不命中時被動寫的，並且正羨出於容錯考慮，如舉斗拍果從存儲層查不到數據則不寫入緩存，這將導致這個不存在的數據每次請求都要到存儲層去查詢，失去了緩存的意義。在流銷租量大時，可能DB就掛掉了，要是有人利用不存在的key頻繁攻擊我們的應用，這就是漏洞。