布谷鸟过滤器

💡 一句话概述

Cuckoo Filter 是一种支持动态插入与删除的概率数据结构，空间效率通常优于 Counting Bloom Filter，且查询性能稳定——适合需要频繁增删的场景。

---

🔑 核心概念

1. 指纹存储：不存储位标记，而是存储元素的短指纹（Fingerprint），通常 4~8 bit。
2. 布谷鸟哈希：每个元素有 2 个候选桶（Bucket），插入时选择较空的位置；冲突时"踢出"旧元素并重新安置。
3. 原地删除：定位到指纹后可直接移除，无需计数器。
4. 半排序压缩：每个桶存储多个指纹时可做半排序编码，进一步压缩空间。

---

📝 详细说明

布谷鸟哈希原理

标准布隆过滤器用"位数组 + 多哈希"做判定；布谷鸟过滤器用的是"桶数组 + 指纹 + 布谷鸟哈希"。

graph TD
    subgraph 插入x["插入元素 x"]
        X["x"] --> FH["fingerprint(x) = 0xA3"]
        X --> H1["h₁(x) → bucket[3]"]
        X --> H2["h₂(x) → bucket[7]"]
        H1 --> CK3{"bucket[3]<br/>有空位?"}
        CK3 -->|是| INS3["放入 bucket[3]"]
        CK3 -->|否| CK7{"bucket[7]<br/>有空位?"}
        CK7 -->|是| INS7["放入 bucket[7]"]
        CK7 -->|否| KICK["随机踢出 bucket 中一个指纹<br/>被踢出者重新计算候选桶并安置"]
    end

踢出（Kick-out）过程：

1. 元素 x 的两个候选桶都满了
2. 随机选择一个桶，踢出其中一个已有指纹 y
3. 用部分关键等式算出 y 的另一个候选桶：\(h_2 = h_1 \oplus \text{hash}(fp_y)\)
4. 将 y 放入其另一个候选桶
5. 若也被占，重复踢出过程（有最大次数限制，超出则判定过滤器已满）

部分关键等式

布谷鸟过滤器的精妙之处在于：不需要存储原始元素，只需要指纹就能推导出备选位置：

\[h_2(x) = h_1(x) \oplus \text{hash}(\text{fingerprint}(x))\]

这意味着：

• 从 \(h_1\) 和指纹可以推出 \(h_2\)
• 从 \(h_2\) 和指纹可以推出 \(h_1\)
• 无需存原始元素，仅需指纹即可完成查找和重定位

删除操作

graph LR
    D["删除元素 x"] --> FH["计算 fingerprint(x)"]
    FH --> H1["检查 bucket[h₁(x)]"]
    FH --> H2["检查 bucket[h₂(x)]"]
    H1 --> M1{"找到匹配指纹?"}
    H2 --> M2{"找到匹配指纹?"}
    M1 -->|是| RM1["移除该指纹 ✅"]
    M2 -->|是| RM2["移除该指纹 ✅"]
    M1 -->|否| M2
    M2 -->|否| NF["元素不存在 ❌"]

删除步骤：

1. 计算 x 的指纹和两个候选桶位置
2. 在两个候选桶中查找匹配的指纹
3. 找到则移除，未找到则报告元素不存在

指纹冲突导致的误删

不同元素可能产生相同指纹。如果元素 y 与元素 x 指纹相同且恰好在 x 的候选桶中，删除 x 时可能误删 y 的指纹。这本质上是布谷鸟过滤器的假阳性在删除场景的体现。

---

💻 代码示例

Go 实现

package cuckoofilter

import (
    "encoding/binary"
    "fmt"
    "math/rand"
)

const (
    fingerprintSize = 4       // 4 字节指纹
    bucketsCount    = 1 << 16 // 桶数量
    entriesPerBucket = 4      // 每桶 4 个槽位
    maxKicks       = 500     // 最大踢出次数
)

type fingerprint [fingerprintSize]byte

type bucket struct {
    entries [entriesPerBucket]fingerprint
    used    [entriesPerBucket]bool
}

type CuckooFilter struct {
    buckets [bucketsCount]bucket
    count   int
}

// New 创建布谷鸟过滤器
func New() *CuckooFilter {
    return &CuckooFilter{}
}

// fp 计算元素指纹
func fp(data []byte) fingerprint {
    h := fnvHash(data)
    var f fingerprint
    binary.BigEndian.PutUint32(f[:], h)
    return f
}

// hash 计算主桶位置
func hash(data []byte) uint {
    h := fnvHash(data)
    return uint(h) % bucketsCount
}

// altIndex 计算备选桶位置
func altIndex(idx uint, f fingerprint) uint {
    h := fnvHash(f[:])
    return (idx ^ h) % bucketsCount
}

// Insert 插入元素
func (cf *CuckooFilter) Insert(data []byte) bool {
    f := fp(data)
    i1 := hash(data)
    i2 := altIndex(i1, f)

    // 尝试放入主桶
    if cf.insertToBucket(i1, f) {
        cf.count++
        return true
    }
    // 尝试放入备选桶
    if cf.insertToBucket(i2, f) {
        cf.count++
        return true
    }

    // 两个桶都满，执行踢出
    idx := i1
    if rand.Intn(2) == 0 {
        idx = i2
    }
    for k := 0; k < maxKicks; k++ {
        // 随机选一个槽位踢出
        slot := rand.Intn(entriesPerBucket)
        evicted := cf.buckets[idx].entries[slot]
        cf.buckets[idx].entries[slot] = f
        cf.buckets[idx].used[slot] = true

        // 被踢出的指纹寻找备选位置
        idx = altIndex(idx, evicted)
        if cf.insertToBucket(idx, evicted) {
            cf.count++
            return true
        }
        f = evicted
    }
    // 超过最大踢出次数，过滤器已满
    return false
}

func (cf *CuckooFilter) insertToBucket(idx uint, f fingerprint) bool {
    b := &cf.buckets[idx]
    for i := 0; i < entriesPerBucket; i++ {
        if !b.used[i] {
            b.entries[i] = f
            b.used[i] = true
            return true
        }
    }
    return false
}

// Lookup 查询元素是否可能存在
func (cf *CuckooFilter) Lookup(data []byte) bool {
    f := fp(data)
    i1 := hash(data)
    i2 := altIndex(i1, f)
    return cf.findInBucket(i1, f) || cf.findInBucket(i2, f)
}

func (cf *CuckooFilter) findInBucket(idx uint, f fingerprint) bool {
    b := &cf.buckets[idx]
    for i := 0; i < entriesPerBucket; i++ {
        if b.used[i] && b.entries[i] == f {
            return true
        }
    }
    return false
}

// Delete 删除元素
func (cf *CuckooFilter) Delete(data []byte) bool {
    f := fp(data)
    i1 := hash(data)
    i2 := altIndex(i1, f)

    if cf.removeFromBucket(i1, f) || cf.removeFromBucket(i2, f) {
        cf.count--
        return true
    }
    return false // 元素不存在（或假阳性误删）
}

func (cf *CuckooFilter) removeFromBucket(idx uint, f fingerprint) bool {
    b := &cf.buckets[idx]
    for i := 0; i < entriesPerBucket; i++ {
        if b.used[i] && b.entries[i] == f {
            b.used[i] = false
            return true
        }
    }
    return false
}

func fnvHash(data []byte) uint32 {
    h := fnv.New32a()
    h.Write(data)
    return h.Sum32()
}

Redis 布谷鸟过滤器

# 创建布谷鸟过滤器
CF.RESERVE my_cuckoo 1000000

# 插入
CF.ADD my_cuckoo user:1001

# 查询
CF.EXISTS my_cuckoo user:1001   # → 1

# 删除 ✅ 原生支持
CF.DEL my_cuckoo user:1001

# 批量插入
CF.MADD my_cuckoo user:1002 user:1003 user:1004

# 查看容量信息
CF.INFO my_cuckoo

---

📊 与其他过滤器对比

特性	布隆过滤器	Counting Bloom	Cuckoo Filter
插入	O(k)	O(k)	均摊 O(1)，最坏 O(maxKicks)
查询	O(k)	O(k)	O(1) — 只查 2 个桶
删除	❌	✅	✅
假阳性	有	有	有（相似量级）
空间效率（每元素）	~9.6 bit（1% FP）	~38 bit（4 bit 计数器）	~12.6 bit（1% FP）
接近满载	误判率上升	误判率上升	插入失败（可感知）
动态扩容	需 Scalable BF	需类似机制	需重建

空间效率优势

在相同假阳性率下，Cuckoo Filter 比 Counting Bloom Filter 省约 3 倍空间；与标准布隆过滤器相比略有开销，但换来了删除能力。

---

⚠️ 常见陷阱

接近满载时插入性能下降

当利用率超过 95% 时，踢出链变长，单次插入可能需要数百次踢出。建议负载不超过 80~85%，超出后扩容重建。

重复插入需谨慎删除

同一元素插入多次会产生多个指纹副本。每次 Delete 只移除一个副本。如果插入了 3 次只删除 1 次，查询仍会返回"存在"。

指纹冲突导致误删

不同元素可能有相同指纹且落入相同桶。删除元素 A 时可能误删元素 B 的指纹。指纹越长（4→8 bit），误删概率越低，但空间开销增加。

不支持扩容

桶数组大小在建时确定。超过容量后只能全量重建更大的过滤器。与标准布隆过滤器不同，布谷鸟过滤器无法像 Scalable Bloom Filter 那样串联扩容。

---

🏋️ 练习题

练习 1：Cuckoo Filter 的部分关键等式 \(h_2 = h_1 \oplus \text{hash}(fp)\) 有什么好处？

只需存储指纹，不需要存储原始元素或完整的两个桶索引。从任意一个桶索引和指纹就能算出另一个桶索引。

答案

省空间：不需要额外存储两个候选桶位置。只需一个桶索引 + 指纹就能用 XOR 推导出另一个候选位置。同时也使踢出重定位逻辑更简洁——被踢出的指纹只需知道自己当前在哪个桶，就能算出另一个桶。

练习 2：为什么 Cuckoo Filter 接近满载时插入性能会下降？

可用空位越来越少，新插入的元素更容易遇到两个候选桶都满的情况，需要更多次踢出才能成功安置。

答案

随着利用率升高，空位减少导致踢出链变长。极端情况下，踢出可能形成环（A 踢 B，B 踢 C，C 又踢 A），触发最大踢出次数限制后插入失败。这是"布谷鸟哈希"的固有特性——在负载因子约 93% 时，期望查找时间趋于无穷大。生产中应监控负载率，超过 80% 时考虑重建。

练习 3：100 万元素、1% 假阳性率，Cuckoo Filter 需要多少空间？比 CBF 省多少？

Cuckoo Filter 每元素约 12.6 bit。CBF 每元素约 38 bit（4 bit 计数器 × 约 9.6 槽位/元素）。

答案

Cuckoo Filter：100 万 × 12.6 bit ≈ 1.5 MB。CBF：100 万 × 38 bit ≈ 4.6 MB。Cuckoo 节省约 **3 倍**空间，同时支持删除。

---

🔗 相关链接

• 布隆过滤器 — 标准布隆过滤器基础
• 布隆过滤器删除问题 — 核心问题与工程方案
• 计数布隆过滤器 — 另一种支持删除的方案
• Cuckoo Filter 原论文 — Fan et al., CoNEXT 2014
• RedisBloom CF 命令 — Redis 原生布谷鸟过滤器