冷飯新炒：理解布隆過(guò)濾器算法的實(shí)現(xiàn)原理

前提

這是《冷飯新炒》系列的第六篇文章。

本文會(huì)翻炒一個(gè)用途比較廣的算法 - 「布隆過(guò)濾器算法」。

布隆過(guò)濾器的一些概念

主要包括：

• 簡(jiǎn)介
• 算法
• 參數(shù)
• 優(yōu)勢(shì)和劣勢(shì)

布隆過(guò)濾器簡(jiǎn)介

布隆過(guò)濾器是「一種空間高效概率性的數(shù)據(jù)結(jié)構(gòu)」（百科中原文是a space-efficient probabilistic data structure），該數(shù)據(jù)結(jié)構(gòu)于1970年由Burton Howard Bloom提出，「作用是測(cè)試一個(gè)元素是否某個(gè)集合的一個(gè)成員」。布隆過(guò)濾器是可能出現(xiàn)false positive（這個(gè)是專有名詞"假陽(yáng)性"，可以理解為誤判的情況，下文如果用到這個(gè)名詞會(huì)保留英文單詞使用）匹配的，換言之，布隆過(guò)濾器在使用的時(shí)候有可能返回結(jié)果"可能存在于集合中"或者"必定不存在于集合中"。

布隆過(guò)濾器算法描述

在場(chǎng)景復(fù)雜的網(wǎng)絡(luò)爬蟲(chóng)中，爬取到的網(wǎng)頁(yè)URL依賴有可能成環(huán)，例如在URL-1頁(yè)面中展示了URL-2，然后又在URL-2中的頁(yè)面展示了URL-1，這個(gè)時(shí)候需要一種方案記錄和判斷歷史訪問(wèn)過(guò)的URL。這個(gè)時(shí)候可能會(huì)想到下面的方案：

• 方案一：使用數(shù)據(jù)庫(kù)存儲(chǔ)已經(jīng)訪問(wèn)過(guò)的URL，例如MySQL表中基于URL建立唯一索引或者使用Redis的SET數(shù)據(jù)類型
• 方案二：使用HashSet（其實(shí)這里不局限于HashSet，鏈表、樹(shù)和散列表等數(shù)據(jù)結(jié)構(gòu)都能滿足）存儲(chǔ)已經(jīng)訪問(wèn)過(guò)的URL
• 方案三：基于方案一和方案二進(jìn)行優(yōu)化，存儲(chǔ)URL的摘要，使用摘要算法如MD5、SHA-n算法針對(duì)URL字符串生成摘要
• 方案四：使用Hash函數(shù)處理對(duì)應(yīng)的URL生成一個(gè)哈希碼，再把哈希碼通過(guò)一個(gè)映射函數(shù)映射到一個(gè)固定容量的BitSet中的某一個(gè)比特

對(duì)于方案一、方案二和方案三，在歷史訪問(wèn)URL數(shù)據(jù)量極大的情況下，會(huì)消耗巨大的存儲(chǔ)空間（磁盤(pán)或者內(nèi)存），對(duì)于方案四，如果URL有100億個(gè)，那么要把沖突幾率降低到1%，那么BitSet的容量需要設(shè)置為10000億。

所以上面的四種方案都有明顯的不足之處，而布隆過(guò)濾器算法的基本思路跟方案四差不多，最大的不同點(diǎn)就是方案四中只提到使用了一個(gè)散列函數(shù)，而布隆過(guò)濾器中使用了k（k >= 1）個(gè)相互獨(dú)立的高效低沖突的散列函數(shù)。

一個(gè)初始化的布隆過(guò)濾器是一個(gè)所有比特都設(shè)置為0的長(zhǎng)度為m的比特?cái)?shù)組，也就是認(rèn)知中的Bit Array、Bit Set或者Redis中的Bit Map概念。然后需要引入k個(gè)不同的散列函數(shù)，某個(gè)新增元素通過(guò)這k個(gè)散列函數(shù)處理之后，映射到比特?cái)?shù)組m個(gè)比特中的k個(gè)，并且把這些命中映射的k個(gè)比特位設(shè)置為1，產(chǎn)生一個(gè)均勻的隨機(jī)分布。通常情況下，k的一個(gè)較小的常數(shù)，取決于所需的誤判率，而布隆過(guò)濾器容量m與散列函數(shù)個(gè)數(shù)k和需要添加元素?cái)?shù)量呈正相關(guān)。

當(dāng)需要新增的所有元素都添加到布隆過(guò)濾器之后，那么比特?cái)?shù)組中的很多比特都被設(shè)置為1。這個(gè)時(shí)候如果需要判斷一個(gè)元素是否存在于布隆過(guò)濾器中，只需要通過(guò)k個(gè)散列函數(shù)處理得到比特?cái)?shù)組的k個(gè)下標(biāo)，然后判斷比特?cái)?shù)組對(duì)應(yīng)的下標(biāo)所在比特是否為1。如果這k個(gè)下標(biāo)所在比特中「至少存在一個(gè)0，那么這個(gè)需要判斷的元素必定不在布隆過(guò)濾器代表的集合中」；如果這k個(gè)下標(biāo)所在比特全部都為1，那么那么這個(gè)需要判斷的元素「可能存在于」布隆過(guò)濾器代表的集合中或者剛好是一個(gè)False Positive，至于誤差率分析見(jiàn)下文的「布隆過(guò)濾器的相關(guān)參數(shù)」一節(jié)。False Positive出現(xiàn)的情況可以見(jiàn)下圖：

當(dāng)添加到布隆過(guò)濾器的元素?cái)?shù)量比較大，并且布隆過(guò)濾器的容量設(shè)置不合理（過(guò)小），容易出現(xiàn)多個(gè)元素通過(guò)k個(gè)散列函數(shù)，映射到相同的k個(gè)位（如上圖的下標(biāo)1、3、9所在的位），這個(gè)時(shí)候就無(wú)法準(zhǔn)確判斷這k個(gè)位由具體那個(gè)元素映射而來(lái)。其實(shí)可以極端一點(diǎn)思考：假設(shè)布隆過(guò)濾器容量為24，散列函數(shù)只有一個(gè)，那么添加最多25個(gè)不同元素，必定有兩個(gè)不同的元素的映射結(jié)果落在同一個(gè)位。

布隆過(guò)濾器的相關(guān)參數(shù)

在算法描述一節(jié)已經(jīng)提到過(guò)，布隆過(guò)濾器主要有下面的參數(shù)：

• 初始化比特?cái)?shù)組容量m
• 散列函數(shù)個(gè)數(shù)k
• 誤判率ε（數(shù)學(xué)符號(hào)Epsilon，代表False Positive Rate）
• 需要添加到布隆過(guò)濾器的元素?cái)?shù)量n

考慮到篇幅原因，這里不做這幾個(gè)值的關(guān)系推導(dǎo)，直接整理出結(jié)果和關(guān)系式。

• 誤判率ε的估算值為：[1 - e^(-kn/m)]^k
• 最優(yōu)散列函數(shù)數(shù)量k的推算值：對(duì)于給定的m和n，當(dāng)k = m/n * ln2的時(shí)候，誤判率ε最低
• 推算初始化比特容量m的值，當(dāng)k = m/n * ln2的時(shí)候，m >= n * log2(e) * log2(1/ε)

這里貼一個(gè)參考資料中m/n、k和False Positive Rate之間的關(guān)系圖：

這里可以推算一下表格中最大參數(shù)所需要的空間極限，假設(shè)n為10億，m/n = 32，那么m為320億，而k為24，此時(shí)的誤判率為2.17e-07(0.000000217)，需要空間3814.69727m。一般規(guī)律是：

• 當(dāng)k固定的時(shí)候，m/n越大，誤判率越小
• 當(dāng)m/n固定的時(shí)候，k越大，誤判率越大

通常情況下，k需要固定，而n是無(wú)法確定準(zhǔn)確值，最好要評(píng)估增長(zhǎng)趨勢(shì)預(yù)先計(jì)算一個(gè)比較大的m值去降低誤判率，當(dāng)然也要權(quán)衡m值過(guò)大導(dǎo)致空間消耗過(guò)大的問(wèn)題。

既然參數(shù)的關(guān)系式都已經(jīng)有推導(dǎo)結(jié)果，可以基于關(guān)系式寫(xiě)一個(gè)參數(shù)生成器：

import java.math.BigDecimal;
import java.math.RoundingMode;

public class BloomFilterParamGenerator {

    public BigDecimal falsePositiveRate(int m, int n, int k) {
        double temp = Math.pow(1 - Math.exp(Math.floorDiv(-k * n, m)), k);
        return BigDecimal.valueOf(temp).setScale(10, RoundingMode.FLOOR);
    }

    public BigDecimal kForMinFalsePositiveRate(int m, int n) {
        BigDecimal k = BigDecimal.valueOf(Math.floorDiv(m, n) * Math.log(2));
        return k.setScale(10, RoundingMode.FLOOR);
    }

    public BigDecimal bestM(int n, double falsePositiveRate) {
        double temp = log2(Math.exp(1) + Math.floor(1 / falsePositiveRate));
        return BigDecimal.valueOf(n).multiply(BigDecimal.valueOf(temp)).setScale(10, RoundingMode.FLOOR);
    }

    public double log2(double x) {
        return Math.log(x) / Math.log(2);
    }

    public static void main(String[] args) {
        BloomFilterParamGenerator generator = new BloomFilterParamGenerator();
        System.out.println(generator.falsePositiveRate(2, 1, 2));  // 0.3995764008
        System.out.println(generator.kForMinFalsePositiveRate(32, 1)); // 22.1807097779
        System.out.println(generator.bestM(1, 0.3995764009)); // 2.2382615950
    }
}

這里的計(jì)算沒(méi)有考慮嚴(yán)格的進(jìn)位和截?cái)?，所以和?shí)際的結(jié)果可能有偏差，只提供一個(gè)參考的例子。

布隆過(guò)濾器的優(yōu)勢(shì)和劣勢(shì)

布隆過(guò)濾器的優(yōu)勢(shì)：

• 布隆過(guò)濾器相對(duì)于其他數(shù)據(jù)結(jié)構(gòu)在時(shí)空上有巨大優(yōu)勢(shì)，占用內(nèi)存少，查詢和插入元素的時(shí)間復(fù)雜度都是O(k)
• 可以準(zhǔn)確判斷元素不存在于布隆過(guò)濾器中的場(chǎng)景
• 散列函數(shù)可以獨(dú)立設(shè)計(jì)
• 布隆過(guò)濾器不需要存儲(chǔ)元素本身，適用于某些數(shù)據(jù)敏感和數(shù)據(jù)嚴(yán)格保密的場(chǎng)景

布隆過(guò)濾器的劣勢(shì)：

• 不能準(zhǔn)確判斷元素必定存在于布隆過(guò)濾器中的場(chǎng)景，存在誤判率，在k和m固定的情況下，添加的元素越多，誤判率越高
• 沒(méi)有存儲(chǔ)全量的元素，對(duì)于一些準(zhǔn)確查詢或者準(zhǔn)確統(tǒng)計(jì)的場(chǎng)景不適用
• 原生的布隆過(guò)濾器無(wú)法安全地刪除元素

?

這里留一個(gè)很簡(jiǎn)單的問(wèn)題給讀者：為什么原生的布隆過(guò)濾器無(wú)法安全地刪除元素？（可以翻看之前的False Positive介紹）

?

布隆過(guò)濾器算法實(shí)現(xiàn)

著名的Java工具類庫(kù)Guava中自帶了一個(gè)beta版本的布隆過(guò)濾器實(shí)現(xiàn)，這里參考其中的源碼實(shí)現(xiàn)思路和上文中的算法描述進(jìn)行一次布隆過(guò)濾器的實(shí)現(xiàn)。先考慮設(shè)計(jì)散列函數(shù)，簡(jiǎn)單一點(diǎn)的方式就是參考JavaBean的hashCode()方法的設(shè)計(jì)：

// 下面的方法來(lái)源于java.util.Arrays#hashCode
public static int hashCode(Object a[]) {
    if (a == null)
        return 0;
    int result = 1;
    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());
    return result;
}

上面方法的31可以作為一個(gè)輸入的seed，每個(gè)散列函數(shù)設(shè)計(jì)一個(gè)獨(dú)立的seed，并且這個(gè)seed值選用素?cái)?shù)基于字符串中的每個(gè)char進(jìn)行迭加就能實(shí)現(xiàn)計(jì)算出來(lái)的結(jié)果是相對(duì)獨(dú)立的：

import java.util.Objects;

public class HashFunction {

    /**
     * 布隆過(guò)濾器容量
     */
    private final int m;

    /**
     * 種子
     */
    private final int seed;

    public HashFunction(int m, int seed) {
        this.m = m;
        this.seed = seed;
    }

    public int hash(String element) {
        if (Objects.isNull(element)) {
            return 0;
        }
        int result = 1;
        int len = element.length();
        for (int i = 0; i < len; i++) {
            result = seed * result + element.charAt(i);
        }
        // 這里確保計(jì)算出來(lái)的結(jié)果不會(huì)超過(guò)m
        return (m - 1) & result;
    }
}

接著實(shí)現(xiàn)布隆過(guò)濾器：

public class BloomFilter {

    private static final int[] K_SEED_ARRAY = {5, 7, 11, 13, 31, 37, 61, 67};

    private static final int MAX_K = K_SEED_ARRAY.length;

    private final int m;

    private final int k;

    private final BitSet bitSet;

    private final HashFunction[] hashFunctions;

    public BloomFilter(int m, int k) {
        this.k = k;
        if (k <= 0 && k > MAX_K) {
            throw new IllegalArgumentException("k = " + k);
        }
        this.m = m;
        this.bitSet = new BitSet(m);
        hashFunctions = new HashFunction[k];
        for (int i = 0; i < k; i++) {
            hashFunctions[i] = new HashFunction(m, K_SEED_ARRAY[i]);
        }
    }

    public void addElement(String element) {
        for (HashFunction hashFunction : hashFunctions) {
            bitSet.set(hashFunction.hash(element), true);
        }
    }

    public boolean contains(String element) {
        if (Objects.isNull(element)) {
            return false;
        }
        boolean result = true;
        for (HashFunction hashFunction : hashFunctions) {
            result = result && bitSet.get(hashFunction.hash(element));
        }
        return result;
    }

    public int m() {
        return m;
    }

    public int k() {
        return k;
    }

    public static void main(String[] args) {
        BloomFilter bf = new BloomFilter(24, 3);
        bf.addElement("throwable");
        bf.addElement("throwx");
        System.out.println(bf.contains("throwable"));  // true
    }
}

這里的散列算法和有限的k值不足以應(yīng)對(duì)復(fù)雜的場(chǎng)景，僅僅為了說(shuō)明如何實(shí)現(xiàn)布隆過(guò)濾器，總的來(lái)說(shuō)，原生布隆過(guò)濾器算法是比較簡(jiǎn)單的。對(duì)于一些復(fù)雜的生產(chǎn)場(chǎng)景，可以使用一些現(xiàn)成的類庫(kù)如Guava中的布隆過(guò)濾器API、Redis中的布隆過(guò)濾器插件或者Redisson（Redis高級(jí)客戶端）中的布隆過(guò)濾器API。

布隆過(guò)濾器應(yīng)用

主要包括：

• Guava中的API
• Redisson中的API
• 使用場(chǎng)景

使用Guava中的布隆過(guò)濾器API

引入Guava的依賴：

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

使用布隆過(guò)濾器：

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

import java.nio.charset.StandardCharsets;

public class GuavaBloomFilter {

    @SuppressWarnings("UnstableApiUsage")
    public static void main(String[] args) {
        BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(StandardCharsets.US_ASCII), 10000, 0.0444D);
        bloomFilter.put("throwable");
        bloomFilter.put("throwx");
        System.out.println(bloomFilter.mightContain("throwable"));
        System.out.println(bloomFilter.mightContain("throwx"));
    }
}

構(gòu)造BloomFilter的最多參數(shù)的靜態(tài)工廠方法是BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, BloomFilter.Strategy strategy)，參數(shù)如下：

• funnel：主要是把任意類型的數(shù)據(jù)轉(zhuǎn)化成HashCode，是一個(gè)頂層接口，有大量?jī)?nèi)置實(shí)現(xiàn)，見(jiàn)Funnels
• expectedInsertions：期望插入的元素個(gè)數(shù)
• fpp：猜測(cè)是False Positive Percent，誤判率，小數(shù)而非百分?jǐn)?shù)，默認(rèn)值0.03
• strategy：映射策略，目前只有MURMUR128_MITZ_32和MURMUR128_MITZ_64（默認(rèn)策略）

參數(shù)可以參照上面的表格或者參數(shù)生成器的指導(dǎo)，基于實(shí)際場(chǎng)景進(jìn)行定制。

使用Redisson中的布隆過(guò)濾器API

高級(jí)Redis客戶端Redisson已經(jīng)基于Redis的bitmap數(shù)據(jù)結(jié)構(gòu)做了封裝，屏蔽了復(fù)雜的實(shí)現(xiàn)邏輯，可以開(kāi)箱即用。引入Redisson的依賴：

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.15.1</version>
</dependency>

使用Redisson中的布隆過(guò)濾器API：

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

public class RedissonBloomFilter {

    public static void main(String[] args) {
        Config config = new Config();
        config.useSingleServer()
                .setAddress("redis://127.0.0.1:6379");
        RedissonClient redissonClient = Redisson.create(config);
        RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter("ipBlockList");
        // 第一個(gè)參數(shù)expectedInsertions代表期望插入的元素個(gè)數(shù)，第二個(gè)參數(shù)falseProbability代表期望的誤判率，小數(shù)表示
        bloomFilter.tryInit(100000L, 0.03D);
        bloomFilter.add("127.0.0.1");
        bloomFilter.add("192.168.1.1");
        System.out.println(bloomFilter.contains("192.168.1.1")); // true
        System.out.println(bloomFilter.contains("192.168.1.2")); // false
    }
}

Redisson提供的布隆過(guò)濾器接口RBloomFilter很簡(jiǎn)單：

常用的方法有tryInit()（初始化）、add()（添加元素）和contains()（判斷元素是否存在）。相對(duì)于Guava的內(nèi)存態(tài)的布隆過(guò)濾器實(shí)現(xiàn)，Redisson提供了基于Redis實(shí)現(xiàn)的「分布式布隆過(guò)濾器」，可以滿足分布式集群中布隆過(guò)濾器的使用。

布隆過(guò)濾器使用場(chǎng)景

其實(shí)布隆過(guò)濾器的使用場(chǎng)景可以用百科中的一張示意圖來(lái)描述：

基于上圖具體化的一些場(chǎng)景列舉如下：

• 網(wǎng)站爬蟲(chóng)應(yīng)用中進(jìn)行URL去重（不存在于布隆過(guò)濾器中的URL必定是未爬取過(guò)的URL）
• 防火墻應(yīng)用中IP黑名單判斷（不局限于IP黑名單，通用的黑名單判斷場(chǎng)景基本都可以使用布隆過(guò)濾器，不存在于布隆過(guò)濾器中的IP必定是白名單）
• 用于規(guī)避緩存穿透（不存在于布隆過(guò)濾器中的KEY必定不存在于后置的緩存中）

布隆過(guò)濾器變體

布隆過(guò)濾器的變體十分多，主要是為了解決布隆過(guò)濾器算法中的一些缺陷或者劣勢(shì)。常見(jiàn)的變體如下：

這里挑選Counting Bloom Filter（簡(jiǎn)稱CBF）變體稍微展開(kāi)一下。原生布隆過(guò)濾器的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)是位向量，CBF擴(kuò)展原生布隆過(guò)濾器的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，底層數(shù)組的每個(gè)元素使用4位大小的計(jì)數(shù)器存儲(chǔ)添加元素到數(shù)組某個(gè)下標(biāo)時(shí)候映射成功的頻次，在插入新元素的時(shí)候，通過(guò)k個(gè)散列函數(shù)映射到k個(gè)具體計(jì)數(shù)器，這些命中的計(jì)數(shù)器值增加1；刪除元素的時(shí)候，通過(guò)k個(gè)散列函數(shù)映射到k個(gè)具體計(jì)數(shù)器，這些計(jì)數(shù)器值減少1。使用CBF判斷元素是否在集合中的時(shí)候：

• 某個(gè)元素通過(guò)k個(gè)散列函數(shù)映射到k個(gè)具體計(jì)數(shù)器，所有計(jì)數(shù)器的值都為0，那么元素必定不在集合中
• 某個(gè)元素通過(guò)k個(gè)散列函數(shù)映射到k個(gè)具體計(jì)數(shù)器，至少有1個(gè)計(jì)數(shù)器的值大于0，那么元素可能在集合中

小結(jié)

一句話簡(jiǎn)單概括布隆過(guò)濾器的基本功能：「不存在則必不存在，存在則不一定存在?！?/strong>

在使用布隆過(guò)濾器判斷一個(gè)元素是否屬于某個(gè)集合時(shí)，會(huì)有一定的誤判率。也就是有可能把不屬于某個(gè)集合的元素誤判為屬于這個(gè)集合，這種錯(cuò)誤稱為False Positive，但不會(huì)把屬于某個(gè)集合的元素誤判為不屬于這個(gè)集合（相對(duì)于False Positive，"假陽(yáng)性"，如果屬于某個(gè)集合的元素誤判為不屬于這個(gè)集合的情況稱為False Negative，"假陰性"）。False Positive，也就是錯(cuò)誤率或者誤判率這個(gè)因素的引入，是布隆過(guò)濾器在設(shè)計(jì)上權(quán)衡空間效率的關(guān)鍵。

參考資料：

• Bloom filter
• Guava相關(guān)源碼
• Bloom Filters - the math

（本文完 c-1-w e-a-20210306）