需求: BloomFilter 如何防止DB 回源攻擊?
介紹:?
Bloomfilter: 布隆過濾器,?它是由一個很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)組成，布隆過濾器可以用于檢索一個元素是否在一個集合中眷细。它的優(yōu)點(diǎn)是空間效率和查詢時間都遠(yuǎn)遠(yuǎn)超過一般的算法扬卷，缺點(diǎn)是有一定的誤識別率。即Bloom Filter報(bào)告某一元素存在于某集合中烁落，但是實(shí)際上該元素并不在集合中。但是如果某個元素確實(shí)沒有在該集合中，那么Bloom Filter 是不會報(bào)告該元素存在于集合中的阀湿，所以不會漏報(bào)。
Bloomfilter 算法邏輯:?
1.??首先需要k個hash函數(shù)瑰妄，每個函數(shù)可以把key散列成為1個整數(shù)?
2.?初始化時陷嘴，需要一個長度為n比特的數(shù)組，每個比特位初始化為0
3.?某個key加入集合時间坐，用k個hash函數(shù)計(jì)算出k個散列值灾挨，并把數(shù)組中對應(yīng)的比特位置為1
4.?判斷某個key是否在集合時，用k個hash函數(shù)計(jì)算出k個散列值竹宋，并查詢數(shù)組中對應(yīng)的比特位劳澄，如果所有的比特位都是1，認(rèn)為在集合中
那么需要多少個K函數(shù)呢? 是不是覺得很神奇蜈七。那下面來算一算秒拔。K 是hash 函數(shù)的個數(shù)，m 是?位數(shù)組大小宪潮。插入元素個數(shù) n
最優(yōu)的 k 如下
k = (m/n)ln2.
接下來看看緩存:
緩存問題溯警，一共有以下幾類:
1. 緩存穿透: 請求去查詢一條數(shù)據(jù)庫中不存在的數(shù)據(jù)趣苏，就是數(shù)據(jù)庫和緩存中都不存在，但是請求每次都會打到數(shù)據(jù)庫上面去梯轻。
2. 緩存擊穿: 大量的請求同時查詢一個key的時候食磕，此時key正好失效，就會導(dǎo)正大量的請求打到數(shù)據(jù)庫中去
3.緩存雪崩: 某一時刻發(fā)生大規(guī)模緩存失效的情況喳挑， 比如緩存數(shù)據(jù)庫crash掉了彬伦，導(dǎo)致大量請求打到數(shù)據(jù)庫，DB撐不住就掛掉了伊诵。
4.熱點(diǎn)數(shù)據(jù)失效: 設(shè)置緩存的時候单绑，一般會設(shè)置失效時間，對于一些熱點(diǎn)數(shù)據(jù)曹宴，當(dāng)緩存失效的時候會存在大量的請求打到數(shù)據(jù)庫中去搂橙，從而導(dǎo)致數(shù)據(jù)庫崩掉。
根據(jù)上面·BloomFilter 的介紹笛坦，針對第一個問題区转，緩存穿透“胬可以把存在key的集合都放到BoolmFilter里面废离，再訪問某個key的時候，先會去BloomFilter 查看有沒有key礁芦，存在的話蜻韭，再去查緩存，緩存沒有再去查DB, BloomFilter 判斷沒有key柿扣，就直接返回肖方。?
BloomFilter在時間和空間上占有優(yōu)勢，但是會有一定的錯誤率窄刘。
具體的使用窥妇，可以采用guava 的BloomFilter舷胜， 很簡單娩践。
private static int size = 1000000;
private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size);
? ? public static void main(String[] args) {
? ? ? ? for (int i = 0; i < size; i++) {
? ? ? ? ? ? bloomFilter.put(i);
? ? ? ? }
? ? ? ? long startTime = System.nanoTime(); // 獲取開始時間
? ? ? ? //判斷這一百萬個數(shù)中是否包含29999這個數(shù)
? ? ? ? if (bloomFilter.mightContain(29999)) {
? ? ? ? ? ? System.out.println("命中了");
? ? ? ? }
? ? ? ? long endTime = System.nanoTime();? // 獲取結(jié)束時間
? ? ? ? System.out.println("程序運(yùn)行時間： " + (endTime - startTime) + "納秒");
? ? }
