如何避免快取穿透?以下這篇文章帶大家了解一下Redis中避免快取穿透的利器-布隆過濾器(Bloom Filter),希望對大家有幫助!
布隆過濾器(Bloom Filter
)是一個資料結構,由布隆(Burton Howard Bloom)於1970年提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。 【相關建議:Redis影片教學】
布隆過濾器可以用於高效的檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠優於一般的演算法,缺點是有一定的誤識別率,而且難以刪除(一般不支持,需要額外的實現)。
誤識率指的是可以判斷元素肯定不在集合中,判斷元素可能在集合中,無法判斷元素一定在集合中。
布隆過濾器之所以高效,因為它是一個機率資料結構,它能確認元素肯定不在集合中,或者元素可能在集合中。之所以說是可能,是因為它有一定的誤辨識率,使得無法 100% 確定元素一定在集合中。
在日常工作中,有一個比較常見的需求,就是需要判斷一個元素是否在集合中。例如下列場景
遇到這種問題,通常直覺會告訴我們,應該使用集合這種資料結構來實現。例如,先將 IP 黑名單庫的所有 IP 全部儲存到一個集合中,然後再拿指定的 IP 到該集合中檢查是否存在,如果存在則說明該 IP 命中黑名單。
透過一段程式碼來模擬 IP 黑名單庫的儲存和檢查。
public class IPBlackList { public static void main(String[] args) { Set<String> set = new HashSet<>(); set.add("192.168.1.1"); set.add("192.168.1.2"); set.add("192.168.1.4"); System.out.println(set.contains("192.168.1.1")); System.out.println(set.contains("192.168.1.2")); System.out.println(set.contains("192.168.1.3")); System.out.println(set.contains("192.168.1.4")); } }
集合的內部,通常是使用散列表來實現。其優點是查詢非常高效,缺點是比較耗費儲存空間。
一般在資料量比較小的時候,我們會使用集合來進行儲存。以空間換時間,在佔用空間較小的情況下,同時又能提高查詢效率。
但是,當儲存的資料量比較大的時候,耗費大量空間將會成為問題。因為這些資料通常會儲存到進程記憶體中,以加快查詢效率。而機器的記憶體通常都是有限的,要盡可能有效率的使用。
另一方面,散列表在空間和效率上是需要做平衡的。儲存相同數量的元素,如果散列表容量越小,出現衝突的機率就越高,用於解決衝突的時間將會花費更多,從而影響效能。
而布隆過濾器(Bloom Filter
)的產生,能夠很好的解決這個問題。一方面能夠以更少的記憶體來儲存數據,另一方面能夠實現非常高效的查詢效能。
首先,建立一個二進位向量,並將所有位元設為0
然後,選定K 個雜湊函數,用於對元素進行K 次雜湊,計算向量的位元下標。
當新增一個元素到集合時,透過K 個雜湊函數分別作用於元素,產生K 個值作為下標,並對向量的相應位元設定為1。
如果要檢查一個元素是否存在集合中,用同樣的雜湊方法,產生K 個下標,並檢查向量的對應位元是否全部是1。
如果全為 1,則該元素很可能在集合中;否則(只要有1個或以上的位元為0),該元素肯定不在集合中。
假設有一個布林過濾器,容量是15位,使用2個雜湊函數,如下所示。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |0|||||||||||||||||||
新增一個字串a
,2次哈希得到下標示為4 和10,將4 和10 對應的位元由0 標記為1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1||||||1|||||||||
再加入一個字串b
,2 個哈希得到下標為11,將11 對應的位元由0 標記為1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1||||||1|1||||||||
####再增加一個字串 c
,2 次雜湊得到下標為 11 和 12,對應的位元由 0 標記為 1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1||||||1|1|1|||||||
最後加入一個字串sam
,2次哈希得到下標為0 和7,對應的位元由0 標記為1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |1||||1|||1|||1|1|1|||||||
上面,我們加入了4 個字串,每個字串分別進行2 次哈希,對應的2個位元標記為1,最終被標記為1的共有6位而不是8位。
這說明,不同的元素,雜湊後得到的位置是可能出現重疊的。如果元素越多,出現重疊的機率會更高。如果有2個元素出現重疊的位置,我們是無法判斷任一元素一定在集合中的。
如果要檢查元素是否存在集合中,只需要以相同的方法,進行 2 次哈希,將得到的 2 個下標在布隆過濾器中的對應位元進行查找。如果對應的 2 位元不是全部為1,則該元素肯定不在集合中。如果對應的 2 位元全部為1,則表示該元素可能在集合中,也可能不存在。
例如,檢查字串 b
是否存在集合中,哈希得到的 2 個下標都為11。檢查發現,11對應的位為1。但是,這並不能說明 b
一定在集合中。這是因為,字串c
雜湊後的下標也包含11,有可能只是字串c在集合中,而b
卻不存在,這就是造成了誤識別,也稱為假陽性。
再檢查字串 foo
,雜湊得到的下標分別為 8 和 13,對應的位元都為0。因此,字串 foo
肯定不在集合中。
布隆過濾器背後的數學原理是
#兩個完全隨機的數字相衝突的機率很小,因此可以在很小的誤識別率條件下,用很少的空間儲存大量資訊。
誤辨識率(FPP
,false positive probabilistic
)的計算如下。
假設布隆過濾器大小為m
比特,儲存了n
個元素,使用k
次雜湊函數來計算元素的儲存位置。
1/m
,任一位元為0 的機率為1-1/m
;(1-1/m)^k
,任一位元為1 的機率為1-(1-1/m)^k
;(1-1 /m)^kn
,任一位元為1 的機率為1-(1-1/m)^kn
;n
個元素的布隆過濾器中,則任一位元已經為1 的機率與上方相同,機率為1-(1-1/m)^kn
。因此,k 個位元都為1的機率為:(1-(1-1/m)^kn)^k
,此即為新插入元素的誤辨識率。 當n 值比較大時,$(1-(1-1/m)^{kn})^k$
約等於$ (1-e^{-kn/m})^k$
假定布隆過濾器大小m
為16 位元,k為8,儲存元素n
為1,那麼誤辨識(假陽性)的機率是萬分之五(5/10000)。
此時,m/n=16
,事實上這表示 1個元素使用 16 個位元的空間來儲存。
因此,當 k
相同時,m/n
為 16/1、32/2、64/4 等值時具有相同的誤識別率。
網站Bloom Filters - the math 給出了布隆過濾器的誤識別率表,可以很方便的查處不同m
,n
,k
給定值下的誤辨識率。
解決誤識別率的常用方法包括
#白名單
回溯確認
解決誤識別率的常見方法,是建立一個較小的白名單,用來儲存那些可能被誤識別的數據。
以垃圾郵件過濾為例。假設我們有一個垃圾郵件庫,用於在接收郵件的時候過濾掉垃圾郵件。
這時可以先將這個垃圾郵件庫儲存到布隆過濾器中,當接收到郵件的時候,可以先透過布隆過濾器高效的過濾出大部分正常郵件。
而對於少部分命中(可能為)垃圾郵件的,其中有一部分可能為正常郵件。
再创建一个白名单库,当在布隆过滤器中判断可能为垃圾邮件时,通过查询白名单来确认是否为正常邮件。
对于没在白名单中的邮件,默认会被移动到垃圾箱。通过人工识别的方式,当发现垃圾箱中存在正常邮件的时候,将其移入白名单。
很多时候,使用布隆过滤器是为了低成本,高效率的拦截掉大量数据不在集合中的场景。例如
这是布隆过滤器非常典型的应用场景,先过滤掉大部分请求,然后只处理少量不明确的请求。
这个方法,和白名单库的区别是,不需要再另外建立一套库来处理,而是使用本来就已经存在的数据和逻辑。
例如 Google Bigtable 查询数据行本来就是需要查的,只不过使用布隆过滤器拦截掉了大部分不必要的请求。而 IP 是否为黑名单也是需要查询的,同样是先使用布隆过滤器来拦截掉大部分IP。
而上面垃圾邮件的处理,对于可能为垃圾邮件的情况,不是通过完整的垃圾邮件库再查询一次进行确认,而是用增加白名单来进行判断的方式。因为通常来说,白名单库会更小,便于缓存。
这里所说的回源,实际上是对可能被误识别的请求,最后要回到数据源头或逻辑确认一次。
Guava 中就提供了一种 Bloom Filter 的实现。
要使用 Bloom Filter,需要引入 guava 包
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>23.0</version> </dependency>
下面对布隆容器的误判率进行测试,分2步
往过滤器中放一百万个数,然后去验证这一百万个数是否能通过过滤器
另外找一万个数,去检验漏网之鱼的数量
/** * 测试布隆过滤器(可用于redis缓存穿透) * * @author 敖丙 */ public class TestBloomFilter { private static int total = 1000000; private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total); // private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total, 0.001); public static void main(String[] args) { // 初始化1000000条数据到过滤器中 for (int i = 0; i < total; i++) { bf.put(i); } // 匹配已在过滤器中的值,是否有匹配不上的 for (int i = 0; i < total; i++) { if (!bf.mightContain(i)) { System.out.println("有坏人逃脱了~~~"); } } // 匹配不在过滤器中的10000个值,有多少匹配出来 int count = 0; for (int i = total; i < total + 10000; i++) { if (bf.mightContain(i)) { count++; } } System.out.println("误伤的数量:" + count); } }
运行结果
误伤的数量:320
运行结果表示,遍历这一百万个在过滤器中的数时,都被识别出来了。一万个不在过滤器中的数,误伤了320个,错误率是0.03左右。
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions) { return create(funnel, (long) expectedInsertions); } public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) { return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions } public static <T> BloomFilter<T> create( Funnel<? super T> funnel, long expectedInsertions, double fpp) { return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64); } static <T> BloomFilter<T> create( Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) { ...... }
Bloom Filter 一共四个 create
方法,不过最终都是走向第4个。看一下每个参数的含义
funnel
:数据类型(一般是调用Funnels工具类中的)
expectedInsertions
:期望插入的值的个数
fpp
: 错误率(默认值为0.03)
strategy
: 哈希算法 Bloom Filter的应用
更多编程相关知识,请访问:编程视频!!
以上是深入淺析Redis中的布隆過濾器(Bloom Filter)的詳細內容。更多資訊請關注PHP中文網其他相關文章!