一文理解布隆過濾器和布谷鳥過濾器

作者：京東保險 王奕龍

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

布隆過濾器

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

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

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

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

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

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

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

type BloomFilter struct {
	// m 位
	m uint
	// k 個 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 {
	// 添加驗證容量大小的邏輯，如果超過了提示 warn 信息
	// four unit64
	h := baseHashes(data)
	for i := uint(0); i < f.k; i++ {
		// 調(diào)用 bitset.BitSet 的 `Set` 方法，將計算出的位置添加到布隆過濾器中
		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 計算元素的四個哈希值，用于 k 次哈希計算
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 個哈希位置映射到布隆過濾器的位數(shù)組中
func (f *BloomFilter) location(h [4]uint64, i uint) uint {
	return uint(location(h, i) % uint64(f.m))
}

// 計算第 i 個哈希值
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 實現(xiàn)，用于高效地判斷一個元素是否存在于集合中，在 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)建一個布隆過濾器，預(yù)計插入 3000000 個整數(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.");
            }
        }
    }
}

布谷鳥過濾器

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我們在此討論下它的刪除方法實現(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)
}

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

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

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

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

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

適用場景

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

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

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

巨人的肩膀

Redis - Bloom filter

Github - bloom

Redisson - Bloom filter

Redis - Cuckoo filter

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

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

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

Github - cuckoofilter

審核編輯 黃宇