布隆過濾器的實(shí)現(xiàn)及其他應(yīng)用場景

緩存雪崩

緩存雪崩就是Redis的大量熱點(diǎn)數(shù)據(jù)同時(shí)過期（失效），因?yàn)樵O(shè)置了相同的過期時(shí)間，剛好這個(gè)時(shí)候Redis請求的并發(fā)量又很大，就會導(dǎo)致所有的請求落到數(shù)據(jù)庫。

這個(gè)問題怎么解決呢？

加互斥鎖或者使用隊(duì)列，針對同一個(gè)key只允許一個(gè)線程到數(shù)據(jù)庫查詢

緩存定時(shí)預(yù)先更新，避免同時(shí)失效

通過加隨機(jī)數(shù)，使key在不同的時(shí)間過期

緩存永不過期

緩存穿透

大家看下這幅圖，用戶可能進(jìn)行了一次條件錯(cuò)誤的查詢，這時(shí)候redis是不存在的，按照常規(guī)流程就是去數(shù)據(jù)庫找了，可是這是一次錯(cuò)誤的條件查詢，數(shù)據(jù)庫當(dāng)然也不會存在，也不會往redis里面寫值，返回給用戶一個(gè)空，這樣的操作一次兩次還好，可是次數(shù)多了還了得，我放redis本來就是為了擋一擋，減輕數(shù)據(jù)庫的壓力，現(xiàn)在redis變成了形同虛設(shè)，每次還是去數(shù)據(jù)庫查找了，這個(gè)就叫做緩存穿透，相當(dāng)于redis不存在了，被擊穿了，對于這種情況很好解決，我們可以在redis緩存一個(gè)空字符串或者特殊字符串，比如&&，下次我們?nèi)edis中查詢的時(shí)候，當(dāng)取到的值是空或者&&，我們就知道這個(gè)值在數(shù)據(jù)庫中是沒有的，就不會在去數(shù)據(jù)庫中查詢，ps：這里緩存不存在key的時(shí)候一定要設(shè)置過期時(shí)間，不然當(dāng)數(shù)據(jù)庫已經(jīng)新增了這一條記錄的時(shí)候，這樣會導(dǎo)致緩存和數(shù)據(jù)庫不一致的情況

上面這個(gè)是重復(fù)查詢同一個(gè)不存在的值的情況，如果應(yīng)用每次查詢的不存在的值是不一樣的呢？即使你每次都緩存特殊字符串也沒用，因?yàn)樗闹挡灰粯?，比如我們的?shù)據(jù)庫用戶id是111，112，113，114依次遞增，但是別人要攻擊你，故意拿-100，-936，-545這種亂七八糟的key來查詢，這時(shí)候redis和數(shù)據(jù)庫這種值都是不存在的，人家每次拿的key也不一樣，你就算緩存了也沒用，這時(shí)候數(shù)據(jù)庫的壓力是相當(dāng)大，比上面這種情況可怕的多，怎么辦呢，這時(shí)候我們今天的主角布隆過濾器 就登場了。。

從一道面試題說起問：如何在海量 元素中（例如 10 億無序、不定長、不重復(fù)）快速 判斷一個(gè)元素是否存在？好，我們最簡單的想法就是把這么多數(shù)據(jù)放到數(shù)據(jù)結(jié)構(gòu)里去，比如List、Map、Tree，一搜不就出來了嗎，比如map.get（），我們假設(shè)一個(gè)元素1個(gè)字節(jié)的字段，10億的數(shù)據(jù)大概需要 900G 的內(nèi)存空間，這個(gè)對于普通的服務(wù)器來說是承受不了的，當(dāng)然面試官也不希望聽到你這個(gè)答案，因?yàn)樘苛税?，我們肯定是要用一種好的方法，巧妙的方法來解決，這里引入一種節(jié)省空間的數(shù)據(jù)結(jié)構(gòu)，位圖 ，他是一個(gè)有序的數(shù)組，只有兩個(gè)值，0 和 1。0代表不存在，1代表存在。

有了這個(gè)屌炸天的東西，現(xiàn)在我們還需要一個(gè)映射關(guān)系，你總得知道某個(gè)元素在哪個(gè)位置上吧，然后在去看這個(gè)位置上是0還是1，怎么解決這個(gè)問題呢，那就要用到哈希函數(shù)，用哈希函數(shù)有兩個(gè)好處，第一是哈希函數(shù)無論輸入值的長度是多少，得到的輸出值長度是固定的，第二是他的分布是均勻的，如果全擠的一塊去那還怎么區(qū)分，比如MD5、SHA-1這些就是常見的哈希算法。

我們通過哈希函數(shù)計(jì)算以后就可以到相應(yīng)的位置去找是否存在了，我們看紅色的線，24和147經(jīng)過哈希函數(shù)得到的哈希值是一樣的，我們把這種情況叫做哈希沖突或者哈希碰撞 。哈希碰撞是不可避免的，我們能做的就是降低哈希碰撞的概率，第一種 是可以擴(kuò)大維數(shù)組的長度或者說位圖容量，因?yàn)槲覀兊暮瘮?shù)是分布均勻的，所以位圖容量越大，在同一個(gè)位置發(fā)生哈希碰撞的概率就越小。但是越大的位圖容量，意味著越多的內(nèi)存消耗，所以我們想想能不能通過其他的方式來解決，第二種 方式就是經(jīng)過多幾個(gè)哈希函數(shù)的計(jì)算，你想啊，24和147現(xiàn)在經(jīng)過一次計(jì)算就碰撞了，那我經(jīng)過5次，10次，100次計(jì)算還能碰撞的話那真的是緣分了，你們可以在一起了，但也不是越多次哈希函數(shù)計(jì)算越好，因?yàn)檫@樣很快就會填滿位圖，而且計(jì)算也是需要消耗時(shí)間，所以我們需要在時(shí)間和空間上尋求一個(gè)平衡。

布隆過濾器當(dāng)然，這個(gè)事情早就有人研究過了，在 1970 年的時(shí)候，有一個(gè)叫做布隆的前輩對于判斷海量元素中元素是否存在的問題進(jìn)行了研究，也就是到底需要多大的位圖容量和多少個(gè)哈希函數(shù)，它發(fā)表了一篇論文，提出的這個(gè)容器就叫做布隆過濾器。

大家來看下這個(gè)圖，我們看集合里面3個(gè)元素，現(xiàn)在我們要存了，比如說a，經(jīng)過f1（a），f2（a），f3（a）經(jīng)過三個(gè)哈希函數(shù)的計(jì)算，在相應(yīng)的位置上存入1，元素b，c也是通過這三個(gè)函數(shù)計(jì)算放入相應(yīng)的位置。當(dāng)取的時(shí)候，元素a通過f1（a）函數(shù)計(jì)算，發(fā)現(xiàn)這個(gè)位置上是1，沒問題，第二個(gè)位置也是1，第三個(gè)位置上也是 1，這時(shí)候我們說這個(gè)a在布隆過濾器中是存在的，沒毛病，同理我們看下面的這個(gè)d，通過三次計(jì)算發(fā)現(xiàn)得到的結(jié)果也都是1，那么我們能說d在布隆過濾器中是存在的嗎，顯然是不行的，我們仔細(xì)看d得到的三個(gè)1其實(shí)是f1（a），f1（b），f2（c）存進(jìn)去的，并不是d自己存進(jìn)去的，這個(gè)還是哈希碰撞導(dǎo)致的，我們把這種本來不存在布隆過濾器中的元素誤判為存在的情況叫做假陽性（False Positive Probability，F(xiàn)PP）。

我們再來看另一個(gè)元素，e 元素。我們要判斷它在容器里面是否存在，一樣地要用這三個(gè)函數(shù)去計(jì)算。第一個(gè)位置是 1，第二個(gè)位置是 1，第三個(gè)位置是 0。那么e元素能不能判斷是否在布隆過濾器中？答案是肯定的，e一定不存在。你想啊，如果e存在的話，他存進(jìn)去的時(shí)候這三個(gè)位置都置為1，現(xiàn)在查出來有一個(gè)位置是0，證明他沒存進(jìn)去啊。。通過上面這張圖加說明，我們得出兩個(gè)重要的結(jié)論

從容器的角度來說：

如果布隆過濾器判斷元素在集合中存在，不一定存在

如果布隆過濾器判斷不存在，一定不存在

從元素的角度來說：

如果元素實(shí)際存在，布隆過濾器一定判斷存在

如果元素實(shí)際不存在，布隆過濾器可能判斷存在

小伙們請牢記

Guava實(shí)現(xiàn)布隆過濾器java為什么寫的人多，基數(shù)大，因?yàn)槭情_源的，擁抱開源，框架多，輪子多，而且一個(gè)功能的輪子還不止一個(gè)，光序列化就有fastjson，jackson，gson，隨你挑任你選，那布隆過濾器的輪子就是google提供的guava，我們用代碼來看一下使用方法

首先引入我們的架包

com.google.guava
guava
21.0

這里先往布隆過濾器里面存放100萬個(gè)元素，然后分別測試100個(gè)存在的元素和9900個(gè)不存在的元素他們的正確率和誤判率

//插入多少數(shù)據(jù)
privatestaticfinalintinsertions=1000000;

//期望的誤判率
privatestaticdoublefpp=0.02;

publicstaticvoidmain(String[]args){

//初始化一個(gè)存儲string數(shù)據(jù)的布隆過濾器,默認(rèn)誤判率是0.03
BloomFilterbf=BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),insertions,fpp);

//用于存放所有實(shí)際存在的key，用于是否存在
Setsets=newHashSet(insertions);

//用于存放所有實(shí)際存在的key，用于取出
Listlists=newArrayList(insertions);

//插入隨機(jī)字符串
for(inti=0;iintrightNum=0;
intwrongNum=0;

for(inti=0;i10000;i++){
//0-10000之間，可以被100整除的數(shù)有100個(gè)（100的倍數(shù)）
Stringdata=i%100==0?lists.get(i/100):UUID.randomUUID().toString();

//這里用了might,看上去不是很自信，所以如果布隆過濾器判斷存在了,我們還要去sets中實(shí)錘
if(bf.mightContain(data)){
if(sets.contains(data)){
rightNum++;
continue;
}
wrongNum++;
}
}

BigDecimalpercent=newBigDecimal(wrongNum).divide(newBigDecimal(9900),2,RoundingMode.HALF_UP);
BigDecimalbingo=newBigDecimal(9900-wrongNum).divide(newBigDecimal(9900),2,RoundingMode.HALF_UP);
System.out.println("在100W個(gè)元素中，判斷100個(gè)實(shí)際存在的元素，布隆過濾器認(rèn)為存在的："+rightNum);
System.out.println("在100W個(gè)元素中，判斷9900個(gè)實(shí)際不存在的元素，誤認(rèn)為存在的："+wrongNum+"，命中率："+bingo+"，誤判率："+percent);
}

最后得出的結(jié)果

我們看到這個(gè)結(jié)果正是印證了上面的結(jié)論，這100個(gè)真實(shí)存在元素在布隆過濾器中一定存在，另外9900個(gè)不存在的元素，布隆過濾器還是判斷了216個(gè)存在，這個(gè)就是誤判，原因上面也說過了，所以布隆過濾器不是萬能的，但是他能幫我們抵擋掉大部分不存在的數(shù)據(jù)已經(jīng)很不錯(cuò)了，已經(jīng)減輕數(shù)據(jù)庫很多壓力了，另外誤判率0.02是在初始化布隆過濾器的時(shí)候我們自己設(shè)的，如果不設(shè)默認(rèn)是0.03，我們自己設(shè)的時(shí)候千萬不能設(shè)0！

Redis實(shí)現(xiàn)布隆過濾器上面使用guava實(shí)現(xiàn)布隆過濾器是把數(shù)據(jù)放在本地內(nèi)存中，我們項(xiàng)目往往是分布式的，我們還可以把數(shù)據(jù)放在redis中，用redis來實(shí)現(xiàn)布隆過濾器，這就需要我們自己設(shè)計(jì)映射函數(shù)，自己度量二進(jìn)制向量的長度，下面貼代碼，大家可以直接拿來用的，已經(jīng)經(jīng)過測試了。。

/**
*布隆過濾器核心類
*
*@param
*@authorjackxu
*/
publicclassBloomFilterHelper<T>{
privateintnumHashFunctions;
privateintbitSize;
privateFunnelfunnel;

publicBloomFilterHelper(intexpectedInsertions){
this.funnel=(Funnel)Funnels.stringFunnel(Charset.defaultCharset());
bitSize=optimalNumOfBits(expectedInsertions,0.03);
numHashFunctions=optimalNumOfHashFunctions(expectedInsertions,bitSize);
}

publicBloomFilterHelper(Funnelfunnel,intexpectedInsertions,doublefpp){
this.funnel=funnel;
bitSize=optimalNumOfBits(expectedInsertions,fpp);
numHashFunctions=optimalNumOfHashFunctions(expectedInsertions,bitSize);
}

publicint[]murmurHashOffset(Tvalue){
int[]offset=newint[numHashFunctions];

longhash64=Hashing.murmur3_128().hashObject(value,funnel).asLong();
inthash1=(int)hash64;
inthash2=(int)(hash64>>>32);
for(inti=1;i<=?numHashFunctions;?i++)?{
????????????intnextHash=hash1+i*hash2;
if(nextHash0){
nextHash=~nextHash;
}
offset[i-1]=nextHash%bitSize;
}

returnoffset;
}

/**
*計(jì)算bit數(shù)組長度
*/
privateintoptimalNumOfBits(longn,doublep){
if(p==0){
p=Double.MIN_VALUE;
}
return(int)(-n*Math.log(p)/(Math.log(2)*Math.log(2)));
}

/**
*計(jì)算hash方法執(zhí)行次數(shù)
*/
privateintoptimalNumOfHashFunctions(longn,longm){
returnMath.max(1,(int)Math.round((double)m/n*Math.log(2)));
}
}

這里在操作redis的位圖bitmap，你可能只知道redis五種數(shù)據(jù)類型，string，list，hash，set，zset，沒聽過bitmap，但是不要緊，你可以說他是一種新的數(shù)據(jù)類型，也可以說不是，因?yàn)樗谋举|(zhì)還是string，后面我也會專門寫一篇文章來介紹數(shù)據(jù)類型以及在他們在互聯(lián)網(wǎng)中的使用場景。。

/**
*redis操作布隆過濾器
*
*@param
*@authorxhj
*/
publicclassRedisBloomFilter<T>{
@Autowired
privateRedisTemplateredisTemplate;

/**
*刪除緩存的KEY
*
*@paramkeyKEY
*/
publicvoiddelete(Stringkey){
redisTemplate.delete(key);
}

/**
*根據(jù)給定的布隆過濾器添加值，在添加一個(gè)元素的時(shí)候使用，批量添加的性能差
*
*@parambloomFilterHelper布隆過濾器對象
*@paramkeyKEY
*@paramvalue值
*@param泛型，可以傳入任何類型的value
*/
publicvoidadd(BloomFilterHelperbloomFilterHelper,Stringkey,Tvalue){
int[]offset=bloomFilterHelper.murmurHashOffset(value);
for(inti:offset){
redisTemplate.opsForValue().setBit(key,i,true);
}
}

/**
*根據(jù)給定的布隆過濾器添加值，在添加一批元素的時(shí)候使用，批量添加的性能好，使用pipeline方式(如果是集群下，請使用優(yōu)化后RedisPipeline的操作)
*
*@parambloomFilterHelper布隆過濾器對象
*@paramkeyKEY
*@paramvalueList值，列表
*@param泛型，可以傳入任何類型的value
*/
publicvoidaddList(BloomFilterHelperbloomFilterHelper,Stringkey,ListvalueList){
redisTemplate.executePipelined(newRedisCallback(){
@Override
publicLongdoInRedis(RedisConnectionconnection)throwsDataAccessException{
connection.openPipeline();
for(Tvalue:valueList){
int[]offset=bloomFilterHelper.murmurHashOffset(value);
for(inti:offset){
connection.setBit(key.getBytes(),i,true);
}
}
returnnull;
}
});
}

/**
*根據(jù)給定的布隆過濾器判斷值是否存在
*
*@parambloomFilterHelper布隆過濾器對象
*@paramkeyKEY
*@paramvalue值
*@param泛型，可以傳入任何類型的value
*@return是否存在
*/
publicbooleancontains(BloomFilterHelperbloomFilterHelper,Stringkey,Tvalue){
int[]offset=bloomFilterHelper.murmurHashOffset(value);
for(inti:offset){
if(!redisTemplate.opsForValue().getBit(key,i)){
returnfalse;
}
}
returntrue;
}
}

最后就是測試類了

publicstaticvoidmain(String[]args){
RedisBloomFilterredisBloomFilter=newRedisBloomFilter();
intexpectedInsertions=1000;
doublefpp=0.1;
redisBloomFilter.delete("bloom");
BloomFilterHelperbloomFilterHelper=newBloomFilterHelper<>(Funnels.stringFunnel(Charset.defaultCharset()),expectedInsertions,fpp);
intj=0;
//添加100個(gè)元素
ListvalueList=newArrayList<>();
for(inti=0;i100;i++){
valueList.add(i+"");
}
longbeginTime=System.currentTimeMillis();
redisBloomFilter.addList(bloomFilterHelper,"bloom",valueList);
longcostMs=System.currentTimeMillis()-beginTime;
log.info("布隆過濾器添加{}個(gè)值，耗時(shí)：{}ms",100,costMs);
for(inti=0;i1000;i++){
booleanresult=redisBloomFilter.contains(bloomFilterHelper,"bloom",i+"");
if(!result){
j++;
}
}
log.info("漏掉了{(lán)}個(gè),驗(yàn)證結(jié)果耗時(shí)：{}ms",j,System.currentTimeMillis()-beginTime);
}

注意這里用的是addList，他的底層是pipelining管道，而add方法的底層是一個(gè)個(gè)for循環(huán)的setBit，這樣的速度效率是很慢的，但是他能有返回值，知道是否插入成功，而pipelining是不知道的，所以具體選擇用哪一種方法看你的業(yè)務(wù)場景，以及需要插入的速度決定。。

布隆過濾器工作位置第一步是將數(shù)據(jù)庫所有的數(shù)據(jù)加載到布隆過濾器。第二步當(dāng)有請求來的時(shí)候先去布隆過濾器查詢，如果bf說沒有，第三步直接返回。如果bf說有，在往下走之前的流程。ps：另外guava的數(shù)據(jù)加載中只有put方法，小伙們可以想下布隆過濾器中數(shù)據(jù)刪除和修改怎么辦，為什么沒有delete的方法？

布隆過濾器的其他應(yīng)用場景網(wǎng)頁爬蟲對URL去重，避免爬取相同的 URL 地址；

反垃圾郵件，從數(shù)十億個(gè)垃圾郵件列表中判斷某郵箱是否垃圾郵箱；

Google Chrome 使用布隆過濾器識別惡意 URL；

Medium 使用布隆過濾器避免推薦給用戶已經(jīng)讀過的文章；

Google BigTable，Apache HBbase 和 Apache Cassandra使用布隆過濾器減少對不存在的行和列的查找。

好，布隆過濾器到這里就結(jié)束了，以后在面試中面試官在問到緩存擊穿怎么辦，我相信你應(yīng)該能夠回答的頭頭是道了，就像我這樣通俗易懂的說出來即可，然后在工作中也可以應(yīng)用，比如鑒權(quán)服務(wù)，當(dāng)用戶登錄的時(shí)候可以先用布隆過濾器判斷下，而不是直接去redis、數(shù)據(jù)庫查。
審核編輯：郭婷