需求: BloomFilter 如何防止DB 回源攻擊?
介紹:?
Bloomfilter: 布隆過濾器,?它是由一個(gè)很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)組成，布隆過濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過一般的算法，缺點(diǎn)是有一定的誤識(shí)別率。即Bloom Filter報(bào)告某一元素存在于某集合中，但是實(shí)際上該元素并不在集合中。但是如果某個(gè)元素確實(shí)沒有在該集合中，那么Bloom Filter 是不會(huì)報(bào)告該元素存在于集合中的，所以不會(huì)漏報(bào)。
Bloomfilter 算法邏輯:?
1.??首先需要k個(gè)hash函數(shù)，每個(gè)函數(shù)可以把key散列成為1個(gè)整數(shù)?
2.?初始化時(shí)，需要一個(gè)長度為n比特的數(shù)組，每個(gè)比特位初始化為0
3.?某個(gè)key加入集合時(shí)，用k個(gè)hash函數(shù)計(jì)算出k個(gè)散列值，并把數(shù)組中對(duì)應(yīng)的比特位置為1
4.?判斷某個(gè)key是否在集合時(shí)，用k個(gè)hash函數(shù)計(jì)算出k個(gè)散列值，并查詢數(shù)組中對(duì)應(yīng)的比特位，如果所有的比特位都是1，認(rèn)為在集合中
那么需要多少個(gè)K函數(shù)呢? 是不是覺得很神奇。那下面來算一算。K 是hash 函數(shù)的個(gè)數(shù)，m 是?位數(shù)組大小。插入元素個(gè)數(shù) n
最優(yōu)的 k 如下
k = (m/n)ln2.
接下來看看緩存:
緩存問題，一共有以下幾類:
1. 緩存穿透: 請(qǐng)求去查詢一條數(shù)據(jù)庫中不存在的數(shù)據(jù)，就是數(shù)據(jù)庫和緩存中都不存在，但是請(qǐng)求每次都會(huì)打到數(shù)據(jù)庫上面去。
2. 緩存擊穿: 大量的請(qǐng)求同時(shí)查詢一個(gè)key的時(shí)候，此時(shí)key正好失效，就會(huì)導(dǎo)正大量的請(qǐng)求打到數(shù)據(jù)庫中去
3.緩存雪崩: 某一時(shí)刻發(fā)生大規(guī)模緩存失效的情況， 比如緩存數(shù)據(jù)庫crash掉了，導(dǎo)致大量請(qǐng)求打到數(shù)據(jù)庫，DB撐不住就掛掉了。
4.熱點(diǎn)數(shù)據(jù)失效: 設(shè)置緩存的時(shí)候，一般會(huì)設(shè)置失效時(shí)間，對(duì)于一些熱點(diǎn)數(shù)據(jù)，當(dāng)緩存失效的時(shí)候會(huì)存在大量的請(qǐng)求打到數(shù)據(jù)庫中去，從而導(dǎo)致數(shù)據(jù)庫崩掉。
根據(jù)上面·BloomFilter 的介紹，針對(duì)第一個(gè)問題，緩存穿透。可以把存在key的集合都放到BoolmFilter里面，再訪問某個(gè)key的時(shí)候，先會(huì)去BloomFilter 查看有沒有key，存在的話，再去查緩存，緩存沒有再去查DB, BloomFilter 判斷沒有key，就直接返回。?
BloomFilter在時(shí)間和空間上占有優(yōu)勢，但是會(huì)有一定的錯(cuò)誤率。
具體的使用，可以采用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í)間
? ? ? ? //判斷這一百萬個(gè)數(shù)中是否包含29999這個(gè)數(shù)
? ? ? ? if (bloomFilter.mightContain(29999)) {
? ? ? ? ? ? System.out.println("命中了");
? ? ? ? }
? ? ? ? long endTime = System.nanoTime();? // 獲取結(jié)束時(shí)間
? ? ? ? System.out.println("程序運(yùn)行時(shí)間： " + (endTime - startTime) + "納秒");
? ? }
