在上一篇 Java 多線程爬蟲及分布式爬蟲架構探索 中，我們使用了 JDK 自帶的 Set 集合來進行 URL 去重，看上去效果不錯，但是這種做法有一個致命了缺陷，就是隨著采集的 URL 增多，你需要的內存越來越大，最終會導致你的內存崩潰。那我們在不使用數據庫的情況下有沒有解決辦法呢?還記得我們在上一篇文章中提到的布隆過濾器嗎?它就可以完美解決這個問題，布隆過濾器有什么特殊的地方呢?接下來就一起來學習一下布隆過濾器。

[[280450]]

什么是布隆過濾器

布隆過濾器是一種數據結構，比較巧妙的概率型數據結構，它是在 1970 年由一個名叫布隆提出的，它實際上是由一個很長的二進制向量和一系列隨機映射函數組成，這點跟哈希表有些相同，但是相對哈希表來說布隆過濾器它更高效、占用空間更少，布隆過濾器有一個缺點那就是有一定的誤識別率和刪除困難。布隆過濾器只能告訴你某個元素一定不存在或者可能存在在集合中， 所以布隆過濾器經常用來處理可以忍受判斷失誤的業務，比如爬蟲 URL 去重。

布隆過濾器原理

在說布隆過濾器原理之前，我們先來復習一下哈希表，在上一篇文章中，我們利用的是 Set 來進行 URL 去重，我們來看看 Set 的存儲模型

Set url 去重

URL 經過一個哈希函數后，將 URL 存入了數組里，這樣查詢時也是非常高效的，但是由于數組里存入的是 URL，隨著 URL 的增多，需要的數組越來越大，意味著你需要更多的內存，比如我們采集了幾億的 URL，那么可能就需要上百G 的內存，這是條件不允許的，因為內存特別的昂貴，所以這個在 url 去重中是不可取的，占內存更小的布隆過濾器就是一種不錯的選擇。

布隆過濾器實質上由長度為 m 的位向量或位列表(僅包含 0 或 1 位值的列表)組成，最初所有值均設置為 0，如下所示。

布隆過濾器

因為底層是 bit 數組，所以意味著數組只有 0、1 兩個值，跟哈希表一樣，我們將 URL 通過 K 個函數映射 bit 數組里，并且將指向的 Bit 數組對應的值改成 1 。我們以 /nba/2492297.html 為例，如下圖所示。

布隆過濾器

/nba/2492297.html經過三個哈希函數分別映射到了 1、4、9 的位置，這三個 bit 數組的值就變成了 1，我們再存入一個 /nba/2492298.html，此時 bit 數組就變成下面這樣：

布隆過濾器

/nba/2492298.html被映射到了 0、4、11 的位置，所以此時 bit 數組上有 5 個位置的值為 1，本應該是有 6 個值為 1 的，但是因為在 4 這個位置重復了，所以會覆蓋。

布隆過濾器是如何判斷某個值一定不存在或者可能存在呢?通過判斷哈希函數映射到對應數組的值，如果都為 1，說明可能存在，如果有一個不為 1，說明一定不存在。對于一定不存在好理解，但是都為 1 時，為什么說可能存在呢?這跟哈希表一樣，哈希函數會產生哈希沖突，也就是說兩個不同的值經過哈希函數都會得到同一個數組下標，布隆過濾器也是一樣的。我們以判斷 /nba/2492299.html 是否已經采集過為例，經過哈希函數映射的 bit 數組上的位置如下圖所示：

布隆過濾器

/nba/2492299.html 被哈希函數映射到了 4、9、11 的位置，而這幾個位置的值都為 1 ，所以布隆過濾器就認為 /nba/2492299.html 被采集過了，實際上是沒有采集過的，這就說明了布隆過濾器存在誤判，這也是我們業務允許的。布隆過濾器的誤判率跟 bit 數組的大小和哈希函數的個數有關系，如果 bit 數組過小，哈希函數過多，那么 bit 數組的值很快都會變成 1，這樣誤判率就會越來越高，bit 數組過大，就會浪費更多的內存，所以就要平衡好 bit 數組的大小和哈希函數的個數，關于如何平衡這兩個的關系，不是我們這篇文章的重點。

布隆過濾器的原理我們已經了解了，為了加深對布隆過濾器的理解，我們用 Java 來實現一個簡易版的布隆過濾器，代碼如下：

public class SimpleBloomFilterTest { 
    // bit 數組的大小 
    private static final int DEFAULT_SIZE = 1000; 
    // 用來生產三個不同的哈希函數的 
    private static final int[] seeds = new int[]{7, 31, 61,}; 
    // bit 數組 
    private BitSet bits = new BitSet(DEFAULT_SIZE); 
    // 存放哈希函數的數組 
    private SimpleHash[] func = new SimpleHash[seeds.length]; 
    public static void main(String[] args) { 
        SimpleBloomFilterTest filter = new SimpleBloomFilterTest(); 
        filter.add("https://voice.hupu.com/nba/2492440.html"); 
        filter.add("https://voice.hupu.com/nba/2492437.html"); 
        filter.add("https://voice.hupu.com/nba/2492439.html"); 
        System.out.println(filter.contains("https://voice.hupu.com/nba/2492440.html")); 
        System.out.println(filter.contains("https://voice.hupu.com/nba/249244.html")); 
    } 
    public SimpleBloomFilterTest() { 
        for (int i = 0; i < seeds.length; i++) { 
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]); 
        } 
    } 
    /** 
     * 向布隆過濾器添加元素 
     * @param value 
     */ 
    public void add(String value) { 
        for (SimpleHash f : func) { 
            bits.set(f.hash(value), true); 
        } 
    } 
    /** 
     * 判斷某元素是否存在布隆過濾器 
     * @param value 
     * @return 
     */ 
    public boolean contains(String value) { 
        if (value == null) { 
            return false; 
        } 
        boolean ret = true; 
        for (SimpleHash f : func) { 
            ret = ret && bits.get(f.hash(value)); 
        } 
        return ret; 
    } 
 
    /** 
     * 哈希函數 
     */ 
    public static class SimpleHash { 
        private int cap; 
        private int seed; 
        public SimpleHash(int cap, int seed) { 
            this.cap = cap; 
            this.seed = seed; 
        } 
        public int hash(String value) { 
            int result = 0; 
            int len = value.length(); 
            for (int i = 0; i < len; i++) { 
                result = seed * result + value.charAt(i); 
            } 
            return (cap - 1) & result; 
        } 
    } 
} 

把上面這段代碼理解好對我們理解布隆過濾器非常有幫助，實際上在工作中并不需要我們自己實現布隆過濾器，谷歌已經幫我們實現了布隆過濾器，在 Guava 包中提供了 BloomFilter，這個布隆過濾器實現的非常棒，下面就看看谷歌辦的布隆過濾器。

布隆過濾器 Guava 版

要使用 Guava 包下提供的 BloomFilter ，就需要引入 Guava 包，我們在 pom.xml 中引入下面依賴：

<dependency> 
    <groupId>com.google.guava</groupId> 
    <artifactId>guava</artifactId> 
    <version>28.1-jre</version> 
</dependency> 

Guava 中的布隆過濾器實現的非常復雜，關于細節我們就不去探究了，我們就來看看 Guava 中布隆過濾器的構造函數吧，Guava 中并沒有提供構造函數，而且提供了 create 方法來構造布隆過濾器：

public static <T> BloomFilter<T> create( 
    Funnel<? super T> funnel, int expectedInsertions, double fpp) { 
  return create(funnel, (long) expectedInsertions, fpp); 
} 

funnel：你要過濾數據的類型

expectedInsertions：你要存放的數據量

fpp：誤判率

你只需要傳入這三個參數你就可以使用 Guava 包中的布隆過濾器了，下面這我寫的一段 Guava 布隆過濾器測試程序，可以改動 fpp 多運行幾次，體驗 Guava 的布隆過濾器。

public class GuavaBloomFilterTest { 
    // bit 數組大小 
    private static int size = 10000; 
    // 布隆過濾器 
    private static BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), size, 0.03); 
 
    public static void main(String[] args) { 
        // 先向布隆過濾器中添加 10000 個url 
        for (int i = 0; i < size; i++) { 
            String url = "https://voice.hupu.com/nba/" + i; 
            bloomFilter.put(url); 
        } 
        // 前10000個url不會出現誤判 
        for (int i = 0; i < size; i++) { 
            String url = "https://voice.hupu.com/nba/" + i; 
            if (!bloomFilter.mightContain(url)) { 
                System.out.println("該 url 被采集過了"); 
            } 
        } 
        List<String> list = new ArrayList<String>(1000); 
        // 再向布隆過濾器中添加 2000 個 url ，在這2000 個中就會出現誤判了 
        // 誤判的個數為 2000 * fpp 
        for (int i = size; i < size + 2000; i++) { 
            String url = "https://voice.hupu.com/nba/" + i; 
            if (bloomFilter.mightContain(url)) { 
                list.add(url); 
            } 
        } 
        System.out.println("誤判數量：" + list.size()); 
    } 
} 

布隆過濾器的應用

緩存擊穿

緩存擊穿是查詢數據庫中不存在的數據，如果有用戶惡意模擬請求很多緩存中不存在的數據，由于緩存中都沒有，導致這些請求短時間內直接落在了DB上，對DB產生壓力，導致數據庫異常。

最常見的解決辦法就是采用布隆過濾器，將所有可能存在的數據哈希到一個足夠大的bitmap中，一個一定不存在的數據會被這個bitmap攔截掉，從而避免了對底層存儲系統的查詢壓力。下面是一段偽代碼：

public String getByKey(String key) { 
    // 通過key獲取value 
    String value = redis.get(key); 
    if (StringUtil.isEmpty(value)) { 
        if (bloomFilter.mightContain(key)) { 
            value = xxxService.get(key); 
            redis.set(key, value); 
            return value; 
        } else { 
            return null; 
        } 
    } 
    return value; 
} 

爬蟲 URL 去重

爬蟲是對 url 的去重，防止 url 重復采集，這也是我們這篇文章重點講解的內容

垃圾郵件識別

從數十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱，將垃圾郵箱添加到布隆過濾器中，然后判斷某個郵件是否是存在在布隆過濾器中，存在說明就是垃圾郵箱。