布谷鸟过滤器
布谷鸟过滤器是一种概率数据结构，用于检查元素是否存在于集合中
布谷鸟过滤器，就像布隆过滤器一样，是 Redis 开源版中的一种概率数据结构，它可以以非常快速且节省空间的方式检查元素是否存在于集合中，同时还支持删除操作，并在某些场景下表现优于布隆过滤器。
布隆过滤器是一个位数组，根据哈希函数确定的位置翻转位；而布谷鸟过滤器是一个桶数组，根据两个哈希函数确定的位置将值的指纹存储在其中一个桶中。对项目 x 的成员资格查询会搜索可能的桶以查找 x 的指纹，如果找到相同的指纹则返回 true。布谷鸟过滤器的指纹大小将直接决定误报率。
用例
定向广告活动（广告、零售）
此应用解答这个问题：用户是否已注册此活动？
为每个活动使用一个布谷鸟过滤器，填充目标用户的 ID。每次访问时，都会针对其中一个布谷鸟过滤器检查用户 ID。
- 如果检查结果为“是”（即用户 ID 存在于过滤器中），表示用户尚未注册该活动。显示广告。
- 如果用户点击广告并注册，将用户 ID 从该布谷鸟过滤器中移除。
- 如果检查结果为“否”（即用户 ID 不存在于过滤器中），表示用户已注册该活动。尝试下一个广告/布谷鸟过滤器。
折扣码/优惠券验证（零售、网店）
此应用解答这个问题：此折扣码/优惠券是否已使用？
使用一个填充了所有折扣码/优惠券的布谷鸟过滤器。每次尝试时，都会根据过滤器检查输入的代码。
- 如果检查结果为“否”（即代码不存在于过滤器中），则优惠券无效。
- 如果检查结果为“是”（即代码存在于过滤器中），则优惠券可能有效。检查主数据库。如果有效，则从布谷鸟过滤器中移除，标记为
used。
注意> 除了这两个用例，布谷鸟过滤器也非常适合所有布隆过滤器的用例。
示例
你将学习如何创建一个初始容量为 1,000 个项目的空布谷鸟过滤器，添加项目，检查它们是否存在，并删除它们。尽管 CF.ADD 命令可以在过滤器不存在时创建新过滤器，但其大小可能不适合你的需求。最好使用 CF.RESERVE 命令设置一个具有你偏好容量的过滤器。
> CF.RESERVE bikes:models 1000000
OK
> CF.ADD bikes:models "Smoky Mountain Striker"
(integer) 1
> CF.EXISTS bikes:models "Smoky Mountain Striker"
(integer) 1
> CF.EXISTS bikes:models "Terrible Bike Name"
(integer) 0
> CF.DEL bikes:models "Smoky Mountain Striker"
(integer) 1
"""
Code samples for Cuckoo filter doc pages:
https://redis.ac.cn/docs/latest/develop/data-types/probabilistic/cuckoo-filter/
"""
import redis
r = redis.Redis(decode_responses=True)
res1 = r.cf().reserve("bikes:models", 1000000)
print(res1) # >>> True
res2 = r.cf().add("bikes:models", "Smoky Mountain Striker")
print(res2) # >>> 1
res3 = r.cf().exists("bikes:models", "Smoky Mountain Striker")
print(res3) # >>> 1
res4 = r.cf().exists("bikes:models", "Terrible Bike Name")
print(res4) # >>> 0
res5 = r.cf().delete("bikes:models", "Smoky Mountain Striker")
print(res5) # >>> 1
import assert from 'assert';
import { createClient } from 'redis';
const client = createClient();
await client.connect();
const res1 = await client.cf.reserve('bikes:models', 1000000);
console.log(res1); // >>> OK
const res2 = await client.cf.add('bikes:models', 'Smoky Mountain Striker');
console.log(res2); // >>> 1
const res3 = await client.cf.exists('bikes:models', 'Smoky Mountain Striker');
console.log(res3); // >>> 1
const res4 = await client.cf.exists('bikes:models', 'Terrible Bike Name');
console.log(res4); // >>> 0
const res5 = await client.cf.del('bikes:models', 'Smoky Mountain Striker');
console.log(res5); // >>> 1
package io.redis.examples;
import org.junit.jupiter.api.Test;
import redis.clients.jedis.UnifiedJedis;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
public class CuckooFilterExample {
public void run() {
UnifiedJedis jedis = new UnifiedJedis("redis://:6379");
String res1 = jedis.cfReserve("bikes:models", 1000000);
System.out.println(res1); // >>> OK
boolean res2 = jedis.cfAdd("bikes:models", "Smoky Mountain Striker");
System.out.println(res2); // >>> True
boolean res3 = jedis.cfExists("bikes:models", "Smoky Mountain Striker");
System.out.println(res3); // >>> True
boolean res4 = jedis.cfExists("bikes:models", "Terrible Bike Name");
System.out.println(res4); // >>> False
boolean res5 = jedis.cfDel("bikes:models", "Smoky Mountain Striker");
System.out.println(res5); // >>> True
jedis.close();
}
}
package example_commands_test
import (
"context"
"fmt"
"github.com/redis/go-redis/v9"
)
func ExampleClient_cuckoo() {
ctx := context.Background()
rdb := redis.NewClient(&redis.Options{
Addr: "localhost:6379",
Password: "", // no password docs
DB: 0, // use default DB
})
res1, err := rdb.CFReserve(ctx, "bikes:models", 1000000).Result()
if err != nil {
panic(err)
}
fmt.Println(res1) // >>> OK
res2, err := rdb.CFAdd(ctx, "bikes:models", "Smoky Mountain Striker").Result()
if err != nil {
panic(err)
}
fmt.Println(res2) // >>> true
res3, err := rdb.CFExists(ctx, "bikes:models", "Smoky Mountain Striker").Result()
if err != nil {
panic(err)
}
fmt.Println(res3) // >>> true
res4, err := rdb.CFExists(ctx, "bikes:models", "Terrible Bike Name").Result()
if err != nil {
panic(err)
}
fmt.Println(res4) // >>> false
res5, err := rdb.CFDel(ctx, "bikes:models", "Smoky Mountain Striker").Result()
if err != nil {
panic(err)
}
fmt.Println(res5) // >>> true
}
using NRedisStack.RedisStackCommands;
using NRedisStack.Tests;
using StackExchange.Redis;
public class Cuckoo_tutorial
{
public void run()
{
var muxer = ConnectionMultiplexer.Connect("localhost:6379");
var db = muxer.GetDatabase();
bool res1 = db.CF().Reserve("bikes:models", 1000000);
Console.WriteLine(res1); // >>> True
bool res2 = db.CF().Add("bikes:models", "Smoky Mountain Striker");
Console.WriteLine(res2); // >>> True
bool res3 = db.CF().Exists("bikes:models", "Smoky Mountain Striker");
Console.WriteLine(res3); // >>> True
bool res4 = db.CF().Exists("bikes:models", "Terrible Bike Name");
Console.WriteLine(res4); // >>> False
bool res5 = db.CF().Del("bikes:models", "Smoky Mountain Striker");
Console.WriteLine(res5); // >>> True
// Tests for 'cuckoo' step.
}
}
布隆过滤器对比布谷鸟过滤器
布隆过滤器在插入项目时通常表现出更好的性能和可伸缩性（因此，如果你经常向数据集中添加项目，布隆过滤器可能是理想选择）。布谷鸟过滤器在检查操作上更快，并且允许删除。
布谷鸟过滤器大小调整
这些是布谷鸟过滤器的主要参数和特性
p 目标误报率f 指纹长度（比特）α 填充率或负载因子 (0≤α≤1)b 每个桶的条目数m 桶数n 项目数C 每个项目的平均比特数
首先要记住，布谷鸟过滤器的一个桶可以有多个条目（每个条目存储一个指纹）。如果所有条目都被指纹占用，我们将没有空槽来保存新元素，过滤器将被声明为满，这就是为什么我们应该始终保持一定比例的布谷鸟过滤器为空。
因此，一个项目的“实际”内存成本除了指纹大小外，还应包括该开销。如果 α 是负载因子（指纹大小 / 总过滤器大小），f 是一个条目中的比特数，则分摊空间成本为 f/α 比特。
初始化新过滤器时，你需要选择其容量和桶大小。
CF.RESERVE {key} {capacity} [BUCKETSIZE bucketSize] [MAXITERATIONS maxIterations]
[EXPANSION expansion]
选择容量 (capacity)
布谷鸟过滤器的容量计算公式为
capacity = n*f/α
其中 n 是你期望过滤器中包含的元素数量，f 是指纹长度（比特），设置为 8，α 是填充因子。因此，要确定过滤器的容量，必须首先选择一个填充因子。填充因子将决定你数据的密度以及内存占用。容量将被向上取整到下一个“2 的幂 (2n)”数。
请注意，在布谷鸟过滤器中插入重复项目会尝试多次添加它们，导致过滤器被填满
由于布谷鸟过滤器的工作原理，过滤器可能会在达到容量之前自行声明已满，因此填充率可能永远无法达到 100%。
选择桶大小 (BUCKETSIZE)
每个桶中的项目数。桶大小值越大，填充率越高，但也会导致更高的错误率和稍微慢的性能。
error_rate = (buckets * hash_functions)/2^fingerprint_size = (buckets*2)/256
当桶大小为 1 时，填充率为 55%，误报率为 2/256 ≈ 0.78%，这是你可以实现的最小误报率。更大的桶会线性增加错误率，但会提高过滤器的填充率。例如，桶大小为 3 会产生 2.34% 的错误率和 80% 的填充率。桶大小为 4 会产生 3.12% 的错误率和 95% 的填充率。
选择扩展因子 (EXPANSION)
当过滤器自行声明已满时，它将通过生成附加子过滤器来自动扩展，代价是性能降低和错误率增加。新子过滤器的大小是前一个子过滤器的大小乘以 EXPANSION（在创建过滤器时选择）。与桶大小一样，附加子过滤器会线性增加错误率（复合错误是所有子过滤器错误的总和）。新子过滤器的大小是最后一个子过滤器的大小乘以扩展因子，这一点非常重要。如果你知道将来某个时候必须进行扩展，最好选择一个更高的扩展值。默认值为 1。
也许你会问“如果我知道我反正会扩展，为什么还要创建一个具有高扩展率的小型过滤器呢？”答案是：在需要维护许多过滤器（例如，每个用户或每个产品一个过滤器）的情况下，大多数过滤器会保持较小规模，但有些活动较多的过滤器则需要扩展。
扩展因子将被向上取整到下一个“2 的幂 (2n)”数。
选择最大迭代次数 (MAXITERATIONS)
MAXITERATIONS 决定了寻找传入指纹槽位的尝试次数。一旦过滤器满载，高 MAXITERATIONS 值会减慢插入速度。默认值为 20。
有趣的事实
- 先前子过滤器中未使用的容量在可能时会自动使用。
- 过滤器可以扩展多达 32 倍。
- 你可以删除项目以保持在过滤器限制内，而不是重建
- 多次添加相同的元素将创建多个条目，从而填满你的过滤器。
向布谷鸟过滤器添加元素的时间复杂度为 O(1)。
同样，检查元素和删除元素的时间复杂度也为 O(1)。
学术来源