作者：jack_xu
juejin.im/post/5e9c110151882573793e8940
不知道從什么時候開始，本來默默無聞的布隆過濾器一下子名聲大燥，在面試中面試官問到怎么避免緩存穿透，你的第一反應(yīng)可能就是布隆過濾器，緩存穿透=布隆過濾器成了標(biāo)配，但具體什么是布隆過濾器，怎么使用布隆過濾器不是很清楚，那今天我們就來把它說清楚，講明白。。
緩存穿透
大家看下這幅圖，用戶可能進(jìn)行了一次條件錯誤的查詢，這時候redis是不存在的，按照常規(guī)流程就是去數(shù)據(jù)庫找了，可是這是一次錯誤的條件查詢，數(shù)據(jù)庫當(dāng)然也不會存在，也不會往redis里面寫值，返回給用戶一個空，這樣的操作一次兩次還好，可是次數(shù)多了還了得，我放redis本來就是為了擋一擋，減輕數(shù)據(jù)庫的壓力，現(xiàn)在redis變成了形同虛設(shè)，每次還是去數(shù)據(jù)庫查找了，這個就叫做緩存穿透，相當(dāng)于redis不存在了，被擊穿了，對于這種情況很好解決，我們可以在redis緩存一個空字符串或者特殊字符串，比如&&，下次我們?nèi)edis中查詢的時候，當(dāng)取到的值是空或者&&，我們就知道這個值在數(shù)據(jù)庫中是沒有的，就不會在去數(shù)據(jù)庫中查詢，ps：這里緩存不存在key的時候一定要設(shè)置過期時間，不然當(dāng)數(shù)據(jù)庫已經(jīng)新增了這一條記錄的時候，這樣會導(dǎo)致緩存和數(shù)據(jù)庫不一致的情況
上面這個是重復(fù)查詢同一個不存在的值的情況，如果應(yīng)用每次查詢的不存在的值是不一樣的呢？即使你每次都緩存特殊字符串也沒用，因為它的值不一樣，比如我們的數(shù)據(jù)庫用戶id是111，112，113，114依次遞增，但是別人要攻擊你，故意拿-100，-936，-545這種亂七八糟的key來查詢，這時候redis和數(shù)據(jù)庫這種值都是不存在的，人家每次拿的key也不一樣，你就算緩存了也沒用，這時候數(shù)據(jù)庫的壓力是相當(dāng)大，比上面這種情況可怕的多，怎么辦呢，這時候我們今天的主角布隆過濾器就登場了。。
從一道面試題說起
問：如何在海量元素中（例如 10 億無序、不定長、不重復(fù)）快速判斷一個元素是否存在？好，我們最簡單的想法就是把這么多數(shù)據(jù)放到數(shù)據(jù)結(jié)構(gòu)里去，比如List、Map、Tree，一搜不就出來了嗎，比如map.get(),我們假設(shè)一個元素1個字節(jié)的字段，10億的數(shù)據(jù)大概需要 900G 的內(nèi)存空間，這個對于普通的服務(wù)器來說是承受不了的，當(dāng)然面試官也不希望聽到你這個答案，因為太笨了吧，我們肯定是要用一種好的方法，巧妙的方法來解決，這里引入一種節(jié)省空間的數(shù)據(jù)結(jié)構(gòu)，位圖，他是一個有序的數(shù)組，只有兩個值，0 和 1。0代表不存在，1代表存在。
有了這個屌炸天的東西，現(xiàn)在我們還需要一個映射關(guān)系，你總得知道某個元素在哪個位置上吧，然后在去看這個位置上是0還是1，怎么解決這個問題呢，那就要用到哈希函數(shù)，用哈希函數(shù)有兩個好處，第一是哈希函數(shù)無論輸入值的長度是多少，得到的輸出值長度是固定的，第二是他的分布是均勻的，如果全擠的一塊去那還怎么區(qū)分，比如MD5、SHA-1這些就是常見的哈希算法。
我們通過哈希函數(shù)計算以后就可以到相應(yīng)的位置去找是否存在了，我們看紅色的線，24和147經(jīng)過哈希函數(shù)得到的哈希值是一樣的，我們把這種情況叫做哈希沖突或者哈希碰撞。哈希碰撞是不可避免的，我們能做的就是降低哈希碰撞的概率，第一種是可以擴大維數(shù)組的長度或者說位圖容量，因為我們的函數(shù)是分布均勻的，所以位圖容量越大，在同一個位置發(fā)生哈希碰撞的概率就越小。但是越大的位圖容量，意味著越多的內(nèi)存消耗，所以我們想想能不能通過其他的方式來解決，第二種方式就是經(jīng)過多幾個哈希函數(shù)的計算，你想啊，24和147現(xiàn)在經(jīng)過一次計算就碰撞了，那我經(jīng)過5次，10次，100次計算還能碰撞的話那真的是緣分了，你們可以在一起了，但也不是越多次哈希函數(shù)計算越好，因為這樣很快就會填滿位圖，而且計算也是需要消耗時間，所以我們需要在時間和空間上尋求一個平衡。。
布隆過濾器
當(dāng)然，這個事情早就有人研究過了，在 1970 年的時候，有一個叫做布隆的前輩對于判斷海量元素中元素是否存在的問題進(jìn)行了研究，也就是到底需要多大的位圖容量和多少個哈希函數(shù)，它發(fā)表了一篇論文，提出的這個容器就叫做布隆過濾器。
大家來看下這個圖，我們看集合里面3個元素，現(xiàn)在我們要存了，比如說a，經(jīng)過f1(a)，f2(a)，f3(a)經(jīng)過三個哈希函數(shù)的計算，在相應(yīng)的位置上存入1，元素b，c也是通過這三個函數(shù)計算放入相應(yīng)的位置。當(dāng)取的時候，元素a通過f1(a)函數(shù)計算，發(fā)現(xiàn)這個位置上是1，沒問題，第二個位置也是1，第三個位置上也是 1，這時候我們說這個a在布隆過濾器中是存在的，沒毛病，同理我們看下面的這個d，通過三次計算發(fā)現(xiàn)得到的結(jié)果也都是1，那么我們能說d在布隆過濾器中是存在的嗎，顯然是不行的，我們仔細(xì)看d得到的三個1其實是f1(a)，f1(b)，f2(c)存進(jìn)去的，并不是d自己存進(jìn)去的，這個還是哈希碰撞導(dǎo)致的，我們把這種本來不存在布隆過濾器中的元素誤判為存在的情況叫做假陽性（False Positive Probability，F(xiàn)PP）。
我們再來看另一個元素，e 元素。我們要判斷它在容器里面是否存在，一樣地要用這三個函數(shù)去計算。第一個位置是 1，第二個位置是 1，第三個位置是 0。那么e元素能不能判斷是否在布隆過濾器中？答案是肯定的，e一定不存在。你想啊，如果e存在的話，他存進(jìn)去的時候這三個位置都置為1，現(xiàn)在查出來有一個位置是0，證明他沒存進(jìn)去啊。。通過上面這張圖加說明，我們得出兩個重要的結(jié)論
從容器的角度來說：
如果布隆過濾器判斷元素在集合中存在，不一定存在
如果布隆過濾器判斷不存在，一定不存在
從元素的角度來說：
如果元素實際存在，布隆過濾器一定判斷存在
如果元素實際不存在，布隆過濾器可能判斷存在
小伙們請牢記
Guava實現(xiàn)布隆過濾器
JAVA為什么寫的人多，基數(shù)大，因為是開源的，擁抱開源，框架多，輪子多，而且一個功能的輪子還不止一個，光序列化就有fastjson，jackson，gson，隨你挑任你選，那布隆過濾器的輪子就是google提供的guava，我們用代碼來看一下使用方法
首先引入我們的架包
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>21.0</version>
</dependency>
這里先往布隆過濾器里面存放100萬個元素，然后分別測試100個存在的元素和9900個不存在的元素他們的正確率和誤判率
//插入多少數(shù)據(jù)
private static final int insertions = 1000000;
//期望的誤判率
private static double fpp = 0.02;
public static void main(String[] args) {
//初始化一個存儲string數(shù)據(jù)的布隆過濾器,默認(rèn)誤判率是0.03
BloomFilter<String> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions, fpp);
//用于存放所有實際存在的key，用于是否存在
Set<String> sets = new HashSet<String>(insertions);
//用于存放所有實際存在的key，用于取出
List<String> lists = new ArrayList<String>(insertions);
//插入隨機字符串
for (int i = 0; i < insertions; i++) {
String uuid = UUID.randomUUID().toString();
bf.put(uuid);
sets.add(uuid);
lists.add(uuid);
}
int rightNum = 0;
int wrongNum = 0;
for (int i = 0; i < 10000; i++) {
// 0-10000之間，可以被100整除的數(shù)有100個（100的倍數(shù)）
String data = i % 100 == 0 ? lists.get(i / 100) : UUID.randomUUID().toString();
//這里用了might,看上去不是很自信，所以如果布隆過濾器判斷存在了,我們還要去sets中實錘
if (bf.mightContain(data)) {
if (sets.contains(data)) {
rightNum++;
continue;
}
wrongNum++;
}
}
BigDecimal percent = new BigDecimal(wrongNum).divide(new BigDecimal(9900), 2, RoundingMode.HALF_UP);
BigDecimal bingo = new BigDecimal(9900 - wrongNum).divide(new BigDecimal(9900), 2, RoundingMode.HALF_UP);
System.out.println("在100W個元素中，判斷100個實際存在的元素，布隆過濾器認(rèn)為存在的：" + rightNum);
System.out.println("在100W個元素中，判斷9900個實際不存在的元素，誤認(rèn)為存在的：" + wrongNum + "，命中率：" + bingo + "，誤判率：" + percent);
}
最后得出的結(jié)果
我們看到這個結(jié)果正是印證了上面的結(jié)論，這100個真實存在元素在布隆過濾器中一定存在，另外9900個不存在的元素，布隆過濾器還是判斷了216個存在，這個就是誤判，原因上面也說過了，所以布隆過濾器不是萬能的，但是它能幫我們抵擋掉大部分不存在的數(shù)據(jù)已經(jīng)很不錯了，已經(jīng)減輕數(shù)據(jù)庫很多壓力了，另外誤判率0.02是在初始化布隆過濾器的時候我們自己設(shè)的，如果不設(shè)默認(rèn)是0.03，我們自己設(shè)的時候千萬不能設(shè)0!
Redis實現(xiàn)布隆過濾器
上面使用guava實現(xiàn)布隆過濾器是把數(shù)據(jù)放在本地內(nèi)存中，我們項目往往是分布式的，我們還可以把數(shù)據(jù)放在redis中，用redis來實現(xiàn)布隆過濾器，這就需要我們自己設(shè)計映射函數(shù)，自己度量二進(jìn)制向量的長度，下面貼代碼，大家可以直接拿來用的，已經(jīng)經(jīng)過測試了。。
/**
* 布隆過濾器核心類
*
* @param <T>
* @author jack xu
*/
public class BloomFilterHelper<T> {
private int numHashFunctions;
private int bitSize;
private Funnel<T> funnel;
public BloomFilterHelper(int expectedInsertions) {
this.funnel = (Funnel<T>) Funnels.stringFunnel(Charset.defaultCharset());
bitSize = optimalNumOfBits(expectedInsertions, 0.03);
numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
}
public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp) {
this.funnel = funnel;
bitSize = optimalNumOfBits(expectedInsertions, fpp);
numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
}
public int[] murmurHashOffset(T value) {
int[] offset = new int[numHashFunctions];
long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
for (int i = 1; i <= numHashFunctions; i++) {
int nextHash = hash1 + i * hash2;
if (nextHash < 0) {
nextHash = ~nextHash;
}
offset[i - 1] = nextHash % bitSize;
}
return offset;
}
/**
* 計算bit數(shù)組長度
*/
private int optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
/**
* 計算hash方法執(zhí)行次數(shù)
*/
private int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
}
這里在操作redis的位圖bitmap，你可能只知道redis五種數(shù)據(jù)類型，string，list，hash，set，zset，沒聽過bitmap，但是不要緊，你可以說他是一種新的數(shù)據(jù)類型，也可以說不是，因為他的本質(zhì)還是string，后面我也會專門寫一篇文章來介紹數(shù)據(jù)類型以及在他們在互聯(lián)網(wǎng)中的使用場景。。
/**
* redis操作布隆過濾器
*
* @param <T>
* @author xhj
*/
public class RedisBloomFilter<T> {
@Autowired
private RedisTemplate redisTemplate;
/**
* 刪除緩存的KEY
*
* @param key KEY
*/
public void delete(String key) {
redisTemplate.delete(key);
}
/**
* 根據(jù)給定的布隆過濾器添加值，在添加一個元素的時候使用，批量添加的性能差
*
* @param bloomFilterHelper 布隆過濾器對象
* @param key KEY
* @param value 值
* @param <T> 泛型，可以傳入任何類型的value
*/
public <T> void add(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for (int i : offset) {
redisTemplate.opsForValue().setBit(key, i, true);
}
}
/**
* 根據(jù)給定的布隆過濾器添加值，在添加一批元素的時候使用，批量添加的性能好，使用pipeline方式(如果是集群下，請使用優(yōu)化后RedisPipeline的操作)
*
* @param bloomFilterHelper 布隆過濾器對象
* @param key KEY
* @param valueList 值，列表
* @param <T> 泛型，可以傳入任何類型的value
*/
public <T> void addList(BloomFilterHelper<T> bloomFilterHelper, String key, List<T> valueList) {
redisTemplate.executePipelined(new RedisCallback<Long>() {
@Override
public Long doInRedis(RedisConnection connection) throws DataAccessException {
connection.openPipeline();
for (T value : valueList) {
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for (int i : offset) {
connection.setBit(key.getBytes(), i, true);
}
}
return null;
}
});
}
/**
* 根據(jù)給定的布隆過濾器判斷值是否存在
*
* @param bloomFilterHelper 布隆過濾器對象
* @param key KEY
* @param value 值
* @param <T> 泛型，可以傳入任何類型的value
* @return 是否存在
*/
public <T> boolean contains(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for (int i : offset) {
if (!redisTemplate.opsForValue().getBit(key, i)) {
return false;
}
}
return true;
}
}
最后就是測試類了
public static void main(String[] args) {
RedisBloomFilter redisBloomFilter = new RedisBloomFilter();
int expectedInsertions = 1000;
double fpp = 0.1;
redisBloomFilter.delete("bloom");
BloomFilterHelper<CharSequence> bloomFilterHelper = new BloomFilterHelper<>(Funnels.stringFunnel(Charset.defaultCharset()), expectedInsertions, fpp);
int j = 0;
// 添加100個元素
List<String> valueList = new ArrayList<>();
for (int i = 0; i < 100; i++) {
valueList.add(i + "");
}
long beginTime = System.currentTimeMillis();
redisBloomFilter.addList(bloomFilterHelper, "bloom", valueList);
long costMs = System.currentTimeMillis() - beginTime;
log.info("布隆過濾器添加{}個值，耗時：{}ms", 100, costMs);
for (int i = 0; i < 1000; i++) {
boolean result = redisBloomFilter.contains(bloomFilterHelper, "bloom", i + "");
if (!result) {
j++;
}
}
log.info("漏掉了{(lán)}個,驗證結(jié)果耗時：{}ms", j, System.currentTimeMillis() - beginTime);
}
注意這里用的是addList，它的底層是pipelining管道，而add方法的底層是一個個for循環(huán)的setBit，這樣的速度效率是很慢的，但是他能有返回值，知道是否插入成功，而pipelining是不知道的，所以具體選擇用哪一種方法看你的業(yè)務(wù)場景，以及需要插入的速度決定。。
布隆過濾器工作位置
第一步是將數(shù)據(jù)庫所有的數(shù)據(jù)加載到布隆過濾器。第二步當(dāng)有請求來的時候先去布隆過濾器查詢，如果bf說沒有，第三步直接返回。如果bf說有，在往下走之前的流程。ps：另外guava的數(shù)據(jù)加載中只有put方法，小伙們可以想下布隆過濾器中數(shù)據(jù)刪除和修改怎么辦，為什么沒有delete的方法？
布隆過濾器的其他應(yīng)用場景
- 網(wǎng)頁爬蟲對URL去重，避免爬取相同的 URL 地址；
- 反垃圾郵件，從數(shù)十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱；
- Google Chrome 使用布隆過濾器識別惡意 URL；
- Medium 使用布隆過濾器避免推薦給用戶已經(jīng)讀過的文章；
- Google BigTable，Apache HBbase 和 Apache Cassandra使用布隆過濾器減少對不存在的行和列的查找。
好了，布隆過濾器到這里就結(jié)束了，以后在面試中面試官在問到緩存擊穿怎么辦，我相信你應(yīng)該能夠回答的頭頭是道了，就像我這樣通俗易懂的說出來即可，然后在工作中也可以應(yīng)用，比如鑒權(quán)服務(wù)，當(dāng)用戶登錄的時候可以先用布隆過濾器判斷下，而不是直接去redis、數(shù)據(jù)庫查
