需求: 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) + "納秒");
? ? }
