摘要

• 本文介绍 Redis 扩展模型 RedisBloom 中的 Cuckoo Filter 数据类型
• 本文基于redis-7.4.7，springboot-3.5.8
• Redis官网：https://redis.io/
• Redis 命令文档：https://redis.io/docs/latest/commands/
• 示例代码：GitHub

Cuckoo Filter（布谷鸟过滤器）

• Cuckoo Filter 是 Bloom Filter 的改进版，支持 动态添加和删除元素，仍能提供比布隆过滤器更高的查询性能。
• 维基百科对 Cuckoo Filter 的描述
• 在高 QPS 查询场景下，Cuckoo Filter 通常优于 Bloom Filter。
• 优点：低误判率 + 高负载率，基于相同的集合和误报率，Cuckoo Filter通常占用空间更少。相对的，算法实现也就更复杂。
• 缺点：与Bloom Filter一样，有可能将一个不在集合中的元素错误的判断成在集合中
• Bloom Filter 的误报率通过调整位数组的大小和哈希函数数量来控制，而 Cuckoo Filter 的误报率受指纹大小和桶大小控制。

布谷哈希算法

• 百度百科对布谷哈希算法的描述]
• 算法使用两个不同哈希函数计算对应 key 的位置。
  • 1. 当两个哈希任意位置为空，则随机选择一个位置插入
  • 2. 当两个哈希有位置为空时，则插入到空位置
  • 3. 当两个哈希位置均不为空时，随机选择一个位置插入并踢出原key，原key会再次经过计算获得新的位置，转至1执行，反复直到成功或者达到最大迭代次数。

Cuckoo Filter 的实现原理

• 布谷过滤器 是在布谷哈希算法的算法基础上扩充来的，但是它所提供的概念不是表，而是提供了多个数据桶(Bucket)
• 每一个数据桶都是个一维数组，每个数组的保存内容为条目(Entry)，每一个条目里面可以保存一个指纹数据(指纹数据就是原始数据经过哈希计算得到的一个n位的数据标记)，除了指纹数据之外，还会同时得出一个保存位置P1标记。
• 当两个数据计算得到的指纹数据相同时，就会发生冲突，冲突操作的解决思路是使用布谷哈希算法，简单说就是新的数据会将原有数据踢出，而被踢出的数据会被重新计算得到新的指纹数据和保存位置标记。
• 布谷过滤器里面需要进行各种数据的踢出操作，这个踢出的方式就是使用P1标志位和指纹数据进行异或计算得出来的P2标志位，按照同样的思路(前提:一直都有冲突操作)一直计算新的P2位，直到冲突解决或者达到最大迭代次数，就会失败。
• 指纹数据里面包含有唯一性，所以可以实现数据的删除，当然，不同的数据计算是有可能得到相同指纹的，那么一旦删除数据之后，有可能造成数据的"假删除"，所以布谷过滤器本身也是存在有误差的。
• Cuckoo Filter 中的 BUSKETSIZE
  • BUSKETSIZE，表示每个桶(Busket)中存放的元素个数，即桶大小。
  • Cuckoo Filter的数组里存的不是位，而是桶(busket)，每个桶里可以存放多个数据。
  • 同一个桶中存放的数据越多，空间利用率更高，相应的误判率也就越高，性能也更慢。
  • Redis的CuckooFilter实现中，BUSKETSIZE应该是一个在1到255之间的整数，默认的 BUSKETSIZE 是 2。
  • 桶(Busket)中并不实际保存数据本身，而是保存数据的指纹(fingerprint)。指纹越小，HASH冲突造成误判的几率就越小。这个参数的调整比较复杂，Redis的CuckooFilter中不支持调整这个参数。

CF 命令说明

• 对应Redis命令： CF.xxx

Bloom vs Cuckoo

RedisBloom Cuckoo Filter 不支持设置 误判率，通常 容量 越大，误判率越低。

CF 命令示例

# 创建 Cuckoo Filter
## 容量1000，这个是必填参数。后面几个都是可选参数。
## BUSKETSIZE越大，空间利用率更高，但是误判率也更高，性能更差，默认2
## MAXITARATIONS越小，性能越好。如果设置越大，空间利用率就越好。默认20
## EXPANSION 是指空间扩容的比例。默认1，不扩容
127.0.0.1:6379> CF.RESERVE user:cf 1000 BUCKETSIZE 2 MAXITERATIONS 500 EXPANSION 2
OK
# 添加元素
127.0.0.1:6379> CF.ADD user:cf user_1
(integer) 1
127.0.0.1:6379> CF.ADD user:cf user_2
(integer) 1
# 可以重复添加元素
127.0.0.1:6379> CF.ADD user:cf user_1
(integer) 1
# 返回元素出现次数
127.0.0.1:6379> CF.COUNT user:cf user_1
(integer) 2
# 判断元素是否存在
127.0.0.1:6379> CF.EXISTS user:cf user_1
(integer) 1
# 批量判断元素是否存在
127.0.0.1:6379> CF.MEXISTS user:cf user_1 user_2 user_100
1) (integer) 1
2) (integer) 1
3) (integer) 0
# 删除元素，一次只删除一个
127.0.0.1:6379> CF.DEL user:cf user_1
(integer) 1
# 因为user_1有两个，所以才是还是能查询出 user_1
127.0.0.1:6379> CF.COUNT user:cf user_1
(integer) 1
# 再次删除
127.0.0.1:6379> CF.DEL user:cf user_1
(integer) 1
# 同名元素已全部删除，查询不到
127.0.0.1:6379> CF.COUNT user:cf user_1
(integer) 0

# 元素不存在时才添加，幂等
127.0.0.1:6379> CF.ADDNX user:cf user_2
(integer) 0
127.0.0.1:6379> CF.ADDNX user:cf user_3
(integer) 1

# 查看 Filter 元信息
127.0.0.1:6379> CF.INFO user:cf
 1) Size                      # 当前 Cuckoo Filter 实际占用的内存大小（字节）
 2) (integer) 1080
 3) Number of buckets         # 当前过滤器中 bucket（桶）的总数量，Size = Number of buckets * Bucket size(默认为2)
 4) (integer) 512
 5) Number of filters         # 内部 子 Cuckoo Filter 的数量
 6) (integer) 1
 7) Number of items inserted  # 成功插入的元素总数（近似）
 8) (integer) 2
 9) Number of items deleted   # 已删除元素的累计次数
10) (integer) 2
11) Bucket size               # 每个 bucket 可容纳的 fingerprint 数，默认为 2
12) (integer) 2
13) Expansion rate            # 过滤器自动扩容倍率，默认为1，0 或 1 表示不扩容（满则失败）
14) (integer) 2
15) Max iterations            # Cuckoo Kick-out 的最大重排次数，值越大，插入成功率越高，但写入延迟可能上升
16) (integer) 500

# 批量添加，key不存在则创建
127.0.0.1:6379> CF.INSERT order:cf CAPACITY 100 ITEMS order1 order2
1) (integer) 1
2) (integer) 1
# 幂等，元素不存在时才添加
127.0.0.1:6379> CF.INSERTNX order:cf CAPACITY 100 ITEMS order1 order2 order100
1) (integer) 0
2) (integer) 0
3) (integer) 1

# 查看类型
127.0.0.1:6379> type order:cf
MBbloomCF

SpringBoot 集成

• SpringBoot 的 RedisTemplate 中没有提供对RedisBloom的封装，需要自己封装，我这里封装了一个简易的RedisCuckooFilterTool

package com.example.redisbloom;

/**
 * 基于 RedisBloom 插件的 CuckooFilter 实现
 * https://github.com/RedisBloom/RedisBloom/releases
 */

import lombok.extern.slf4j.Slf4j;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.data.redis.core.script.DefaultRedisScript;
import org.springframework.stereotype.Component;

import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

@Component
@Slf4j
public class RedisCuckooFilterTool {

    private final StringRedisTemplate redisTemplate;

    public RedisCuckooFilterTool(StringRedisTemplate redisTemplate) {
        this.redisTemplate = redisTemplate;
    }

    /**
     * 初始化 Cuckoo Filter
     * <p>
     * 不能重复创建
     *
     * @param key      Filter 名称
     * @param capacity 预计容量
     */
    public boolean reserve(String key, long capacity) {
        String script = "return redis.call('CF.RESERVE', KEYS[1], " + capacity + ")";
        try{
            redisTemplate.execute(
                    new DefaultRedisScript<>(script, String.class),
                    Collections.singletonList(key)
            );
            return true;
        } catch (Exception e) {
            log.error("RedisCuckooFilterTool reserve error:",e);
            return false;
        }

    }

    /**
     * 初始化 Cuckoo Filter（高级参数）
     *
     * 不能重复创建
     *
     * @param key           Filter 名称
     * @param capacity      预计容量
     * @param bucketSize    每个桶里最多能放多少个 fingerprint（指纹），默认 2(大多数情况下的最优解)
     * @param maxIterations 重排次数，越大成功率越高
     * @param expansion     扩容倍数，默认 1（不扩容）
     */
    public boolean reserve(String key, long capacity, int bucketSize, int maxIterations, int expansion) {

        String script = String.format(
                "return redis.call('CF.RESERVE', KEYS[1], %d, " +
                        "'BUCKETSIZE', %d, 'MAXITERATIONS', %d, 'EXPANSION', %d)",
                capacity, bucketSize, maxIterations, expansion
        );

        try{
            redisTemplate.execute(
                    new DefaultRedisScript<>(script, String.class),
                    Collections.singletonList(key)
            );
            return true;
        } catch (Exception e) {
            log.error("RedisCuckooFilterTool reserve error:",e);
            return false;
        }
    }

    /**
     * 添加元素（不去重）
     */
    public boolean add(String key, String value) {
        String script = "return redis.call('CF.ADD', KEYS[1], ARGV[1])";
        final Boolean execute = redisTemplate.execute(
                new DefaultRedisScript<>(script, Boolean.class),
                Collections.singletonList(key),
                value
        );
        return Boolean.TRUE.equals(execute);
    }

    /**
     * 添加元素（仅当不存在时）
     *
     * @return true 表示成功插入，false 表示已存在
     */
    public boolean addNx(String key, String value) {
        String script = "return redis.call('CF.ADDNX', KEYS[1], ARGV[1])";
        final Boolean execute = redisTemplate.execute(
                new DefaultRedisScript<>(script, Boolean.class),
                Collections.singletonList(key),
                value
        );
        return Boolean.TRUE.equals(execute);
    }

    /**
     * 判断元素是否存在
     */
    public boolean exists(String key, String value) {
        String script = "return redis.call('CF.EXISTS', KEYS[1], ARGV[1])";
        final Boolean execute = redisTemplate.execute(
                new DefaultRedisScript<>(script, Boolean.class),
                Collections.singletonList(key),
                value
        );
        return Boolean.TRUE.equals(execute);
    }

    /**
     * 批量判断是否存在
     * @return 每个元素对应的结果，1 表示存在，0 表示不存在
     */
    public List<Long> mexists(String key, String... items) {
        String script = "return redis.call('CF.MEXISTS', KEYS[1], unpack(ARGV))";
        if (items == null || items.length == 0) {
            return Collections.emptyList();
        }

        return redisTemplate.execute(
                new DefaultRedisScript<>(script, List.class),
                Collections.singletonList(key),
                items
        );
    }

    /**
     * 返回元素出现次数（近似）
     */
    public Long count(String key, String value) {
        String script = "return redis.call('CF.COUNT', KEYS[1], ARGV[1])";
        return redisTemplate.execute(
                new DefaultRedisScript<>(script, Long.class),
                Collections.singletonList(key),
                value
        );
    }

    /**
     * 删除元素
     *
     * @return true 删除成功，false 表示不存在
     */
    public boolean delete(String key, String value) {
        String script = "return redis.call('CF.DEL', KEYS[1], ARGV[1])";

        final Long execute = redisTemplate.execute(
                new DefaultRedisScript<>(script, Long.class),
                Collections.singletonList(key),
                value
        );
        return Boolean.TRUE.equals(execute);
    }

    /**
     * 批量插入，不去重
     * @return 每个元素对应插入结果，1 插入成功，0 插入失败
     */
    public List<Long> insert(String key, String... items) {
        String script = "return redis.call('CF.INSERT', KEYS[1], 'ITEMS', unpack(ARGV))";
        if (items == null || items.length == 0) {
            return Collections.emptyList();
        }
        return redisTemplate.execute(
                new DefaultRedisScript<>(script, List.class),
                Collections.singletonList(key),
                items
        );
    }

    /**
     * 批量插入，去重
     * @return 每个元素对应插入结果，1 插入成功，0 插入失败
     */
    public List<Boolean> insertNx(String key, String... items) {
        String script = "return redis.call('CF.INSERTNX', KEYS[1], 'ITEMS', unpack(ARGV))";
        if (items == null || items.length == 0) {
            return Collections.emptyList();
        }
        return redisTemplate.execute(
                new DefaultRedisScript<>(script, List.class),
                Collections.singletonList(key),
                items
        );
    }

    /**
     * 获取 Cuckoo Filter 元信息
     */
    public Map<String, Long> info(String key) {
        String script = "return redis.call('CF.INFO', KEYS[1])";
        List<Object> result = redisTemplate.execute(
                new DefaultRedisScript<>(script, List.class),
                Collections.singletonList(key)
        );

        if (result == null || result.isEmpty()) {
            return Collections.emptyMap();
        }

        Map<String, Long> infoMap = new LinkedHashMap<>();
        for (int i = 0; i < result.size(); i += 2) {
            String field = toString(result.get(i));
            Long value = (Long) result.get(i + 1);
            infoMap.put(field, value);
        }

        return infoMap;
    }

    /**
     * 字节数组转字符串
     * info 返回的 List
     * [
     * byte[]("Size"),                  Long(1080),
     * byte[]("Number of buckets"),     Long(512),
     * byte[]("Number of filters"),     Long(1),
     * ...
     * ]
     */
    private String toString(Object obj) {
        if (obj instanceof byte[]) {
            return new String((byte[]) obj);
        }
        return String.valueOf(obj);
    }
}