Documentation
高性能
✅什么是布谷鸟过滤器，实现原理是什么？

✅什么是布谷鸟过滤器，实现原理是什么？

典型回答

**布谷鸟过滤器（Cuckoo Filter）**是一种更优秀的数据结构，它在设计上就支持删除操作。它的核心思想是 “每个项都有两个（或多个）‘桶’，并且它会携带一个唯一的‘指纹’”

这个名字源于 “布谷鸟筑巢” 的行为。布谷鸟不会自己筑巢，而是会把蛋下到其他鸟的巢里，并把原来的蛋踢出去。布谷鸟过滤器中的插入过程与此非常相似：如果一个新元素发现它的两个“家”都满了，它就会随机把其中一个“老住户”（已有的指纹）踢出去，然后为自己安家。那个被踢出去的“老住户”就得去寻找它的另一个“家”。

Redis 8.0中新增的数据结构中，有一个就是本文的主角——Cockoo Filter ：https://redis.io/docs/latest/develop/data-types/probabilistic/cuckoo-filter/

指纹

最开始看这个布谷鸟过滤器的时候，有点懵b，因为他引入了指纹和两个桶的概念。但是，这里可以先不考虑2个桶的事儿，只考虑指纹。

我们知道布隆过滤器之所以不能删除元素，是因为在某个位置上如果被设置为1，并不代表着只有当前元素的hash结果在这里，有可能hash冲突，其他元素也在这里，所以你不能直接设置为0。

但是，如果这个位置，只存一个元素呢？这样删除的时候我就可以检查，如果是和要删除的元素一样，就可以删除。

但是这样做就和Set、数据啥的都一样了，所以，布谷鸟过滤器提出了不要存数据的原值，而是存一个短小的值，也就是上面提到的指纹了。虽然指纹也会有冲突的可能，但是指纹又冲突了，最终存的桶有一样的概率就低很多。

  • 指纹（Fingerprint）：使用一个短小的、固定位数的哈希值（比如8位）来唯一代表一个元素。虽然不同元素的指纹可能冲突，但概率很低。

所以，指纹有2个作用：

1、指纹是存储在布谷鸟过滤器桶中的实际数据。过滤器中不存储庞大的原始数据，只存储这个短小的、固定长度（如8位）的哈希值。这极大地节省了空间。而且在查询和删除时，我们通过比对指纹来判断一个元素是否存在。

2、指纹的长度直接决定了过滤器的精度。指纹越长，不同元素产生相同指纹（冲突）的概率就越低。

那如果真的很不幸指纹冲突了，那么也可以借助接下来要介绍的2个桶来降低冲突的可能。

多个候选桶

在布谷鸟过滤器中，每个元素不是映射到位数组的一系列位上，而是根据其指纹被计算到两个确定的候选桶中（也可以扩展成多个）。当一个新元素要插入时，它有两个“桶”可以选择。如果第一个桶满了，它可以去第二个桶。这大大提高了过滤器的空间利用率和插入成功率。还避免了像布隆过滤器那样，所有元素都共享同一个大位数组，导致位冲突概率随元素增加而急剧上升的问题。

先看插入、查找和删除的过程。

执行过程

插入过程

对元素 x，首先计算指纹： f = fingerprint(x)然后

  • 计算第一个桶索引：i1 = hash(x) % N，i1和指纹无关，和要存储的元素的hash有关
  • 计算第二个桶索引：i2 = i1 XOR hash(f)（异或运算），i2和指纹有关，也和要存储的元素的hash有关

这里使用 **XOR**（异或）操作是关键。它确保了第二个桶的位置也依赖于指纹 **f**。这意味着，只要你知道 **f** 和 **i1**，你一定能计算出 **i2**；反之亦然。这个特性对查找和删除至关重要。

接下来开始插入，

  • 如果桶 i1 或桶 i2 中还有空槽位，直接将**指纹 **f** **放入其中一个空位。插入成功！
  • 如果两个桶都满了，随机选择其中一个桶（比如 i1），“踢出” 该桶中的一个随机指纹 f_old。然后将新的指纹 f 放入桶 i1 中。

被踢出去的元素先尝试向他的另一个桶中插入（如i2），如果能插入则直接插入，如果无法插入，就和前面一样，踢出其他元素。

如果冲突很高的话，这个踢出过程可能会形成一条很长的“踢出链”。为了避免无限循环，会设置一个最大重试次数。如果超过这个次数，就认为过滤器已近乎满载，插入失败，需要对过滤器进行扩容。

注意！！！：这里在桶中存的是指纹。而不是元素的值，也不是0或者1。

查找过程

查找元素 x 非常简单高效：

  1. 计算其指纹 f = fingerprint(x)。
  2. 计算两个候选桶：
    • i1 = hash(x) % num_buckets
    • i2 = i1 XOR hash(f) % num_buckets
  3. 检查桶 i1 和桶 i2 中是否存在指纹 f。
  4. 如果任何一个桶中存在 f，则返回 “可能存在”。
  5. 如果两个桶中都找不到 f，则返回 “肯定不存在”。

删除过程

删除是布谷鸟过滤器相比布隆过滤器的巨大优势，操作同样直接：

  1. 计算要删除元素 x 的指纹 f = fingerprint(x)。
  2. 计算它的两个候选桶 i1 和 i2。
  3. 检查这两个桶。
  4. 从包含指纹 f 的槽位中移除该指纹（将该槽位置空）。
  5. 完成。

**之所以布谷鸟过滤器的删除很安全，是因为一个元素只可能存在于它的两个候选桶的其中一个中，并且我们是通过完整的指纹 ****f**的值来匹配的。只要指纹 **f** 的位数足够（例如8位），不同元素产生相同指纹并恰好也映射到同一个桶的概率（即误删的概率）是非常非常低的。也可以通过调整指纹长度来控制（例如，12位指纹的冲突概率约为1/4096）。

✅什么是QPS，什么是RT？✅什么是布隆过滤器，实现原理是什么？