Bloom Filter如何解決緩存穿透

緩存穿透是什麼?

關於緩存穿透，簡單來說就是系統處理了大量不存在的數據查詢。正常的使用緩存流程大致是，數據查詢先進行緩存查詢，如果key不存在或者key已經過期，再對資料庫進行查詢，並把查詢到的對象，放進緩存。如果資料庫查詢對象為空，則不放進緩存。現在系統接收了大量不存在的key，緩存層形同虛設，大量請求引向資料庫，資料庫承受不了壓力，宕機。

布隆過濾器是什麼?

Bloom Filter適用於判斷數據是否在一個集合中。

Bloom Filter的基本原理是位數組與Hash函數的聯合使用。

首先，Bloom Filter是一個包含了m位的位數組，數組的每一位都初始化為;其次，定義k個不同的Hash函數，每個函數都可以將集合中的元素映射到位數組的某一位。

當向集合中插入元素時，根據K個Hash函數可以得到位數組中的k個位，如果有的位為0，則元素肯定不在集合中，如果全部為1，則元素可能在集合中，因為在插入其它元素時，可能會將這些位置設為1。

所以，使用Bloom Filter法的難點是如何根據輸入元素個數n，來確定位數組m的大小以及Hash函數。

Bloom Filter的優點是具有很好的空間效率和時間效率。它的插入和查詢時間都是常數，另外，它不保存元素本身，具有良好的安全性。然而，這些優點都是以犧牲正確率為代價的。當插入的元素越多，錯判的概率越大。另外，Bloom Filter只能插入元素，不能刪除元素，原因是多個元素可能共用了位數組中的同一個位。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！