作者：京東保險(xiǎn) 王奕龍

最近在大促中使用到了布隆過濾器，所以本次借著機(jī)會(huì)整理下相關(guān)內(nèi)容，并了解了布谷鳥過濾器，希望對后續(xù)學(xué)習(xí)的同學(xué)有啟發(fā)~

布隆過濾器

布隆過濾器是 概率性數(shù)據(jù)結(jié)構(gòu)，用于檢查元素是否存在集合中。布隆過濾器并不存儲集合中的所有元素，而是存儲元素的哈希表示，因此犧牲了一些精確性：當(dāng)布隆過濾報(bào)告某元素在集合中不存在時(shí)，那么它一定不存在；報(bào)告某元素存在時(shí)，允許出現(xiàn)“假陽性”，有時(shí)會(huì)錯(cuò)誤地報(bào)告某個(gè)元素在集合中，而實(shí)際上它不存在，這樣的權(quán)衡使得布隆過濾器非常節(jié)省空間且速度快。

布隆過濾器本質(zhì)上是由許多位組成的數(shù)組。當(dāng)一個(gè)元素 “添加” 到布隆過濾器時(shí)，該元素會(huì)被哈希，然后將位數(shù)組中索引為 [hashval % nbits] 的位置設(shè)為 1。這與哈希表中桶的映射方式類似，要檢查一個(gè)元素是否存在，計(jì)算其哈希值，并查看相應(yīng)的位是否被設(shè)置為 1。

如果發(fā)生哈希碰撞，便會(huì)出現(xiàn)“假陽性”。為了減少碰撞風(fēng)險(xiǎn)，一個(gè)元素可以使用多個(gè)位：元素會(huì)進(jìn)行多次哈希（每次哈希使用不同的 Seed 生成不同的哈希值），并將每個(gè)哈希值對應(yīng)的 hashval % nbits 位設(shè)置為 1。要檢查元素是否存在，該元素也會(huì)被多次哈希，如果有任何對應(yīng)的位未被設(shè)置，則可以確定該項(xiàng)不存在。每個(gè)元素的位數(shù) 在創(chuàng)建過濾器時(shí)已經(jīng)被確定了。通常，每個(gè)元素使用的位越多，假陽性的可能性就越低，如下所示為需要設(shè)置 3 位才能確定該元素存在的過濾器：

影響布隆過濾器準(zhǔn)確度的另一個(gè)因素是填充率，即過濾器中實(shí)際設(shè)置了多少位。如果過濾器設(shè)置了絕大多數(shù)位，則任何特定查找返回 false 的可能性就會(huì)降低，過濾器誤報(bào)的可能性就會(huì)增加，所以過濾器在初始化時(shí)會(huì)規(guī)定容量。

Redis 提供了 可擴(kuò)展的布隆過濾器，來解決布隆過濾器容量固定的問題。當(dāng)一個(gè)布隆過濾器達(dá)到容量時(shí)，會(huì)在其上創(chuàng)建一個(gè)新的過濾器。通常，新過濾器的容量比之前的更大，以減少再堆疊另一個(gè)過濾器的可能。在可擴(kuò)展的布隆過濾器中，檢查元素是否存在便涉及檢查所有過濾器。即使是 Redis 提供了創(chuàng)建可擴(kuò)展的布隆過濾器的功能，但是了解預(yù)期包含多少元素依然很重要，如果初始的過濾器只能包含少量元素，那么隨著過濾器的擴(kuò)展，性能會(huì)降低。

向布隆過濾器中插入的時(shí)間復(fù)雜度為 O(K)，其中 k 為哈希函數(shù)的數(shù)量，對于擴(kuò)展過濾器，檢查元素的復(fù)雜度為 O(K) 或 O(K*(n + 1))，其中 n 是已擴(kuò)展的過濾器數(shù)量。

Github - bloom 倉庫是基于 Golang 實(shí)現(xiàn)的布隆過濾器，適合學(xué)習(xí)了解原理。因?yàn)樵搶?shí)現(xiàn)全量代碼較少，所以將需要關(guān)注的邏輯全部列在下面，并表明了注釋，供大家參考：

type BloomFilter struct {
	// m 位
	m uint
	// k 個(gè) Hash
	k uint
	// 大小為 m 的 BitSet
	b *bitset.BitSet
}

// NewWithEstimates 創(chuàng)建布隆過濾器，根據(jù)容量和假陽率估算（estimate）位數(shù)和要Hash的次數(shù)
func NewWithEstimates(n uint, fp float64) *BloomFilter {
	m, k := EstimateParameters(n, fp)
	return New(m, k)
}

// EstimateParameters 根據(jù)容量和假陽率估算 位數(shù)和Hash次數(shù)
func EstimateParameters(n uint, p float64) (m uint, k uint) {
	// 位數(shù) = (p 的對數(shù)的相反數(shù) * 容量 / 2 的對數(shù)的平方)的最接近的整數(shù)
	m = uint(math.Ceil(-1 * float64(n) * math.Log(p) / math.Pow(math.Log(2), 2)))
	// hash次數(shù) = (2 的對數(shù) * 位數(shù) / 容量) 最接近的整數(shù)
	k = uint(math.Ceil(math.Log(2) * float64(m) / float64(n)))
	return
}

func New(m uint, k uint) *BloomFilter {
	return &BloomFilter{max(1, m), max(1, k), bitset.New(m)}
}

func max(x, y uint) uint {
	if x > y {
		return x
	}
	return y
}

// Add 添加新的元素到布隆過濾器中，支持鏈?zhǔn)?a  target="_blank">編程
func (f *BloomFilter) Add(data []byte) *BloomFilter {
	// 添加驗(yàn)證容量大小的邏輯，如果超過了提示 warn 信息
	// four unit64
	h := baseHashes(data)
	for i := uint(0); i < f.k; i++ {
		// 調(diào)用 bitset.BitSet 的 `Set` 方法，將計(jì)算出的位置添加到布隆過濾器中
		f.b.Set(f.location(h, i))
	}
	return f
}

// Test 檢查某元素是否在布隆過濾器中
func (f *BloomFilter) Test(data []byte) bool {
	h := baseHashes(data)
	for i := uint(0); i < f.k; i++ {
		if !f.b.Test(f.location(h, i)) {
			return false
		}
	}
	return true
}

// baseHashes 計(jì)算元素的四個(gè)哈希值，用于 k 次哈希計(jì)算
func baseHashes(data []byte) [4]uint64 {
	var d digest128 // murmur hashing
	hash1, hash2, hash3, hash4 := d.sum256(data)
	return [4]uint64{
		hash1, hash2, hash3, hash4,
	}
}

// 將第 i 個(gè)哈希位置映射到布隆過濾器的位數(shù)組中
func (f *BloomFilter) location(h [4]uint64, i uint) uint {
	return uint(location(h, i) % uint64(f.m))
}

// 計(jì)算第 i 個(gè)哈希值
func location(h [4]uint64, i uint) uint64 {
	ii := uint64(i)
	return h[ii%2] + ii*h[2+(((ii+(ii%2))%4)/2)]
}

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

Redisson 提供了操作布隆過濾器的簡單易用 API，以下是使用布隆過濾器的示例：

引入依賴

    
        org.redisson
        redisson
        3.37.0
    

使用示例

    private void redisson() {
        RedissonClient redissonClient = Redisson.create();

        RBloomFilter bloomFilter = redissonClient.getBloomFilter("bloomFilter");
        // 初始化大小為 10億，假陽率為 0.001（在使用布隆過濾器之前，必須完成初始化操作）
        bloomFilter.tryInit(1000000000, 0.001);

        Object object = new Object();
        // 添加元素
        bloomFilter.add(object);

        // 檢查元素是否存在
        boolean exist = bloomFilter.contains(object);
    }

Guava 也提供了 BloomFilter 實(shí)現(xiàn)，用于高效地判斷一個(gè)元素是否存在于集合中，在 23.0 及之后版本中，是線程安全的。以下是 Guava 中布隆過濾器使用示例：

引入依賴

    com.google.guava
    guava
    
    33.3.1-jre

使用示例

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

public class BloomFilterExample {
    public static void main(String[] args) {
        // 創(chuàng)建一個(gè)布隆過濾器，預(yù)計(jì)插入 3000000 個(gè)整數(shù)，假陽率為0.01
        BloomFilter bloomFilter = BloomFilter.create(
                Funnels.integerFunnel(), 3000000, 0.01);

        // 向布隆過濾器中添加元素
        for (int i = 0; i < 3000000; i++) {
            bloomFilter.put(i);
        }

        // 測試布隆過濾器
        for (int i = 0; i < 3001000; i++) {
            if (bloomFilter.mightContain(i)) {
                System.out.println(i + " might be in the filter.");
            } else {
                System.out.println(i + " is definitely not in the filter.");
            }
        }
    }
}

布谷鳥過濾器

布隆過濾器不記錄元素本身，并且存在一個(gè)位被多個(gè)元素共用的情況，所以它不支持刪除元素。布谷鳥過濾器（詳細(xì)了解可以參考這篇論文《布谷鳥過濾器：實(shí)際上優(yōu)于布隆過濾器》）的提出解決了這個(gè)問題，它支持刪除操作，此外它還帶來了其他優(yōu)勢：

查找性能更高：布隆過濾器要采用多種哈希函數(shù)進(jìn)行多次哈希，而布谷鳥過濾器只需一次哈希

節(jié)省更多空間：布谷鳥過濾器記錄元素更加緊湊，論文中提到，如果期望誤報(bào)率在 3% 以下，半排序桶布谷鳥過濾器每個(gè)元素所占用的空間要比布隆過濾器中單個(gè)元素占用空間要小

布谷鳥過濾器之所以被稱為“布谷鳥”，是因?yàn)樗?a target="_blank">工作原理類似于布谷鳥在自然界中的行為。布谷鳥以將自己的蛋產(chǎn)在其他鳥類的巢中而聞名，這樣一來，寄主鳥就會(huì)撫養(yǎng)布谷鳥的幼鳥。
在布谷鳥過濾器中，如果一個(gè)位置已經(jīng)被占用，新元素會(huì)“驅(qū)逐”現(xiàn)有元素，將其移到其他位置。這種“驅(qū)逐”行為類似于布谷鳥將其他鳥蛋推出巢外，以便安置自己的蛋。因此，這種過濾器得名為“布谷鳥”過濾器。

布谷鳥過濾器本質(zhì)上是一個(gè) 桶數(shù)組，每個(gè)桶中保存若干數(shù)量的 指紋（指紋由元素的部分 Hash 值計(jì)算出來）。定義一個(gè)布谷鳥過濾器，每個(gè)桶記錄 2 個(gè)指紋，5 號桶和 11 號桶分別記錄保存 a, b 和 c, d 元素的指紋，如下所示：

此時(shí)，向其中插入新的元素 e，發(fā)現(xiàn)它被哈希到的兩個(gè)候選桶分別為 5 號 和 11 號，但是這兩個(gè)桶中的元素已經(jīng)添加滿了：

按照布谷鳥過濾器的特性，它會(huì)將其中的一個(gè)元素重哈希到其他的桶中（具體選擇哪個(gè)元素，由具體的算法指定），新元素占據(jù)該元素的位置，如下：

以上便是向布谷鳥過濾器中添加元素并發(fā)生沖突時(shí)的操作流程，在我們的例子中，重新放置元素 e 觸發(fā)了另一個(gè)重置，將現(xiàn)有的項(xiàng) a 從桶 5 踢到桶 15。這個(gè)過程可能會(huì)重復(fù)，直到找到一個(gè)能容納元素的桶，這就使得布谷鳥哈希表更加緊湊，因此可以更加節(jié)省空間。如果沒有找到空桶則認(rèn)為此哈希表太滿，無法插入。雖然布谷鳥哈希可能執(zhí)行一系列重置，但其均攤插入時(shí)間為 O(1)。

與布隆過濾器一樣，布谷鳥過濾器同樣會(huì)造成假陽性，造成假陽性的有以下原因：

有限的空間：布谷鳥過濾器使用有限數(shù)量的桶和每個(gè)桶中的有限空間來存儲元素的指紋。當(dāng)多個(gè)元素的指紋映射到相同的桶時(shí)，可能會(huì)導(dǎo)致不同元素的指紋存儲在同一位置

指紋沖突：由于指紋是元素的哈希值的縮減版本，可能會(huì)有不同的元素產(chǎn)生相同的指紋。當(dāng)查詢一個(gè)不存在的元素時(shí)，可能會(huì)發(fā)現(xiàn)其指紋已經(jīng)存在于過濾器中，從而導(dǎo)致假陽性

哈希函數(shù)的性質(zhì)：哈希函數(shù)的選擇和指紋長度決定了指紋的唯一性和沖突概率。較短的指紋更容易產(chǎn)生沖突，從而增加假陽性的概率

負(fù)載因子：隨著過濾器接近滿載，沖突的概率增加，這會(huì)導(dǎo)致更多的“驅(qū)逐”操作。在高負(fù)載情況下，假陽性率也可能上升

Github - cuckoofilter 是 Github 上 Star 數(shù)較多的一個(gè)倉庫，它參考了論文內(nèi)容，并用 Golang 實(shí)現(xiàn)了布谷鳥過濾器，大家感興趣的話可以直接去參考它的源碼。該過濾器重要的參數(shù)如下：

每個(gè)元素有 2 個(gè)候選桶，每個(gè)桶記錄 4 個(gè)指紋：該配置能夠使桶的利用率達(dá)到 95%，能夠滿足多數(shù)場景，當(dāng)指定假陽性率在 0.00001 和 0.002 之間時(shí)，可以將每個(gè)元素占用空間最小化

指紋的靜態(tài)大小為 8 位：指定誤報(bào)率為 0.03，根據(jù)公式 f >= log2(2b/r) b為桶的大小 r為誤報(bào)率，計(jì)算出指紋大小為 8。在 2 個(gè)候選桶和 4 個(gè)指紋的配置下，隨著指紋大小變大，空間利用率不會(huì)再隨之增加，僅降低假陽率

我們在此討論下它的刪除方法實(shí)現(xiàn)：

// Delete 刪除過濾器中的指紋
func (cf *Filter) Delete(data []byte) bool {
	// 嘗試在首選桶中刪除
	i1, fp := getIndexAndFingerprint(data, cf.bucketPow)
	if cf.delete(fp, i1) {
		return true
	}
	// 刪除失敗，則嘗試從備用桶刪除
	i2 := getAltIndex(fp, i1, cf.bucketPow)
	return cf.delete(fp, i2)
}

它的刪除方法實(shí)現(xiàn)比較簡單：它檢查給定元素的兩個(gè)候選桶，如果在首選桶中匹配到則將該指紋移除，否則去備用桶中匹配，在備用桶中則移除備用桶指紋，如果備用桶中沒有，則會(huì)提示刪除失敗。如果兩個(gè)元素 a, b 發(fā)生碰撞（共享桶和指紋），那么在 a 元素刪除后，因?yàn)?b 元素的存在，仍然會(huì)判斷 a 元素在過濾器中，表現(xiàn)出假陽性。需要注意的是，想要安全的刪除某元素，必須事先插入它，否則刪除插入項(xiàng)可能會(huì)無意中刪除共享指紋的真實(shí)存在的項(xiàng)，而且如果多次插入重復(fù)元素，想要將其刪除干凈還需要知道該元素插入了多少次。

此外，相比于布隆過濾器它也存在一些的劣勢：

插入性能可能會(huì)受到影響：隨著插入元素越多，空間利用率不斷提高，發(fā)生沖突的可能性越大，發(fā)生沖突之后，可能會(huì)不斷的觸發(fā)元素的重定位，插入性能會(huì)變差，一般通過最大重試次數(shù)來限制

插入重復(fù)元素次數(shù)存在上限：布隆過濾器插入重復(fù)元素沒有負(fù)面影響，只是再標(biāo)記相同的位，而布谷鳥過濾器插入重復(fù)元素會(huì)觸發(fā)元素的重定位，因此它的重復(fù)元素插入存在上限

對于過濾器緩存的使用，大部分情景都是讀多寫少的，而重復(fù)插入并沒有什么意義，布谷鳥過濾器的刪除雖然不完美但總好過沒有（因?yàn)椴悸∵^濾器想要?jiǎng)h除元素便需要重建，上億甚至幾十億的數(shù)據(jù)重建緩存也蠻花時(shí)間），同時(shí)還有更優(yōu)的查詢和存儲效率，應(yīng)該說在絕大多數(shù)情況下其都是一個(gè)性價(jià)比更高的選擇。

適用場景

檢測用戶名是否存在：將所有已注冊用戶名使用布隆過濾器，新用戶創(chuàng)建用戶名時(shí)，檢查該用戶名是否存在于布隆過濾器中

廣告投放：為每個(gè)用戶創(chuàng)建一個(gè)布隆過濾器，保存所有已購買的商品，在進(jìn)行商品廣告投放時(shí)，檢查該商品是否在布隆過濾器中

延保業(yè)務(wù)實(shí)踐：商城訂單詳情頁延保信息只有在商品進(jìn)入完成態(tài)時(shí)才有。在大促期間，用戶在購買完商品時(shí)，會(huì)習(xí)慣性點(diǎn)擊訂詳查看，此時(shí)會(huì)有大量的無效請求進(jìn)來，直接查詢數(shù)據(jù)庫，為了避免數(shù)據(jù)庫擊穿，將所有完成的訂單保存在布隆過濾器中，這樣便能過濾大量請求

巨人的肩膀

Redis - Bloom filter

Github - bloom

Redisson - Bloom filter

Redis - Cuckoo filter

Linvon - 布谷鳥過濾器：實(shí)際上優(yōu)于布隆過濾器

COOLSHELL - Cuckoo Filter：設(shè)計(jì)與實(shí)現(xiàn)

木鳥雜技 - 布谷鳥哈希和布谷鳥過濾器

Github - cuckoofilter

審核編輯 黃宇