前言

在现代互联网系统中，过滤器作为高效的集合判断结构被广泛使用。尤其在**布隆过滤器（Bloom Filter）**存在删除困难和空间使用不佳的问题时，**Cuckoo Filter（布谷鸟过滤器）**应运而生，成为一个更灵活且支持删除操作的替代方案。

定义

Wiki 定义如下：

A cuckoo filter is a probabilistic data structure, an approximate set-membership query data structure, that supports add, delete, and lookup operations.

简而言之：Cuckoo Filter 是一种基于 Cuckoo Hashing 的概率性集合判断结构，支持插入、查询和删除操作，且空间效率优于布隆过滤器。

工作原理

一句话：通过将元素指纹插入哈希表的两个候选位置之一，并在冲突时“踢出”已有元素，实现高效的集合判断与管理。

工作步骤简述：

  1. 对元素计算 fingerprint（指纹）；
  2. 计算两个候选桶的位置；
  3. 若两者有空位，插入其一；
  4. 若无空位，随机踢出一个已有指纹，并尝试重新插入被踢出的指纹；
  5. 若反复尝试后仍失败，则认为插入失败（表满）。

属性与指标

关注的 Cuckoo Filter 属性与指标包括：

  1. False Positive Rate（误判率）：低于布隆过滤器，尤其在高负载情况下更稳定；
  2. 支持删除操作：相较布隆过滤器的最大优势；
  3. 空间利用率：在相同误判率下，比布隆过滤器更节省内存（~95% 装载率）；
  4. 负载因子：超过一定容量后插入失败概率上升；
  5. 插入失败概率：可通过扩容或重新哈希解决；
  6. 查询复杂度：通常为 O(1)；
  7. 删除复杂度：O(1)，不需计数器；
  8. 可扩展性：原生不支持扩展，可借助多表扩展策略实现。

类型

标准 Cuckoo Filter

最基础实现，基于 Cuckoo Hashing，适用于静态容量或负载可控场景。

扩展型 Cuckoo Filter

为支持大规模增长，可采用分区哈希或动态表扩展策略，避免频繁插入失败。

压缩型 Cuckoo Filter

通过减小指纹长度或桶容量，换取更高空间压缩率，但牺牲一定误判率。

多槽桶型

每个 bucket 拥有多个槽（如 4-way），进一步提高装载率和插入成功率。

应用场景

Cuckoo Filter 的典型应用如下：

  1. 缓存系统预过滤：与 Redis/Memcached 联用，减少穿透请求；
  2. 分布式存储系统：用于快速判定 key 是否存在，如在 RocksDB 中使用；
  3. 网络防火墙：用于黑名单判定，支持增删；
  4. 数据库索引加速：判断 key 是否存在避免无效读；
  5. 爬虫系统 URL 去重：支持删除、空间效率高；
  6. 边缘计算场景：低资源场合使用高效集合过滤结构。

常用实现与工具库

以下是常见的 Cuckoo Filter 实现：

  1. Cuckoo Filter (by Fan et al)：最早且权威的 C/C++ 实现，GitHub 开源；
  2. Redis + CuckooFilter Module：作为模块扩展使用；
  3. Python：pycuckoofilter：纯 Python 封装，适合快速实验；
  4. Go：github.com/seiflotfy/cuckoofilter：高性能 Go 实现；
  5. Java：CuckooFilter4J、stream-lib 中扩展实现；
  6. ScyllaDB：在其存储引擎中采用改进型 Cuckoo Filter 加速 SSTable 查找。