如何使用 Redis 快速实现布隆过滤器？

回答重点

布隆过滤器是一种高效的概率数据结构，常用于检测一个元素是否在一个集合中，可以有效减少数据库的查询次数，解决缓存穿透等问题。

可以通过使用 位图（Bitmap） 或使用 Redis 模块 RedisBloom。

1）使用位图实现布隆过滤器：

使用 Redis 的位图结构 SETBIT 和 GETBIT 操作来实现布隆过滤器。位图本质上是一个比特数组，用于标识元素是否存在。
对于给定的数据，通过多个 哈希函数 计算位置索引，将位图中的相应位置设置为 1，表示该元素可能存在。

2）使用 RedisBloom 模块：

Redis 提供了一个官方模块 RedisBloom，封装了哈希函数、位图大小等操作，可以直接用于创建和管理布隆过滤器。
使用 BF.ADD 来向布隆过滤器添加元素，使用 BF.EXISTS 来检查某个元素是否可能存在。

扩展知识

布隆过滤器原理

布隆过滤器是由一个 位数组 和 k 个独立的哈希函数 组成。

添加元素时，通过 k 个哈希函数将元素映射到位数组的 k 个位置上，将这些位置设置为 1。

检查元素是否存在时，同样计算 k 个位置，如果所有位置都是 1，则说明元素可能存在；只要有一个位置为 0，就可以确定元素一定不存在。

例如某个 key 通过 hash-1 和 hash-2 两个哈希函数，定位到数组中的值都为 1，则说明它存在。

如果布隆过滤器判断一个元素不存在集合中，那么这个元素一定不在集合中，如果判断元素存在集合中则不一定是真的，因为哈希可能会存在冲突。因此布隆过滤器有误判的概率。

而且它不好删除元素，只能新增，如果想要删除，只能重建。

布隆过滤器优缺点

1）优点

高效性：插入和查询操作都非常高效，时间复杂度为 O(k)，k 为哈希函数的数量。
节省空间：相比于直接存储所有元素，布隆过滤器大幅度减少了内存使用。
可扩展性：可以根据需要调整位数组的大小和哈希函数的数量来平衡时间和空间效率。

2）缺点

误判率：可能会误认为不存在的元素在集合中，但不会漏报（不存在的元素不会被认为存在）。
不可删除：一旦插入元素，不能删除，因为无法确定哪些哈希值是由哪个元素设置的。
需要多个哈希函数：选择合适的哈希函数并保证它们独立性并不容易。

使用 Redis 位图（bitmap）实现布隆过滤器

bitmap 基本操作：

SETBIT key offset value：将 key 的值在 offset 位置上的位设置为 value（0 或 1）。
GETBIT key offset：获取 key 的值在 offset 位置上的位的值（0 或 1）。
BITCOUNT key [start end]：计算字符串中设置为 1 的位的数量。
BITOP operation destkey key [key …]：对一个或多个 key 进行位运算，并将结果存储在 destkey 中。支持的操作包括 AND、OR、XOR 和 NOT。

实现布隆过滤器流程：

位图使用单个位来表示某个位置的状态，通过 Redis 的 SETBIT key offset value 操作可以设置位图中某个偏移位置的值。
假设有 k 个哈希函数 H1, H2, ..., Hk，对于每个新加入的元素 x，通过这些哈希函数计算位置，将相应位置的比特位设置为 1。
查询元素是否存在时，计算相同的 k 个位置并用 GETBIT key offset 来判断这些位置是否都是 1。

以下 Java 中为利用 bitmap 实现布隆过滤器的例子，供大家参考：

import redis.clients.jedis.Jedis;
import java.nio.charset.StandardCharsets;
import java.util.BitSet;
import java.util.List;
import java.util.ArrayList;

public class RedisBloomFilter {

    private static final String BLOOM_FILTER_KEY = "bloom_filter";
    private static final int BITMAP_SIZE = 1000000; // 位图大小
    private static final int[] HASH_SEEDS = {3, 5, 7, 11, 13, 17}; // 多个哈希函数的种子

    private Jedis jedis;
    private List<SimpleHash> hashFunctions;

    public RedisBloomFilter() {
        this.jedis = new Jedis("localhost", 6379);
        this.hashFunctions = new ArrayList<>();
        for (int seed : HASH_SEEDS) {
            hashFunctions.add(new SimpleHash(BITMAP_SIZE, seed));
        }
    }

    // 添加元素到布隆过滤器
    public void add(String value) {
        for (SimpleHash hashFunction : hashFunctions) {
            jedis.setbit(BLOOM_FILTER_KEY, hashFunction.hash(value), true);
        }
    }

    // 检查元素是否可能存在于布隆过滤器中
    public boolean mightContain(String value) {
        for (SimpleHash hashFunction : hashFunctions) {
            if (!jedis.getbit(BLOOM_FILTER_KEY, hashFunction.hash(value))) {
                return false;
            }
        }
        return true;
    }

    // 关闭连接
    public void close() {
        jedis.close();
    }

    // 简单哈希函数
    public static class SimpleHash {
        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        public int hash(String value) {
            int result = 0;
            byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
            for (byte b : bytes) {
                result = seed * result + b;
            }
            return (cap - 1) & result;
        }
    }

    public static void main(String[] args) {
        RedisBloomFilter bloomFilter = new RedisBloomFilter();

        // 添加元素到布隆过滤器
        bloomFilter.add("user1");
        bloomFilter.add("user2");
        bloomFilter.add("user3");

        // 检查元素是否可能存在
        System.out.println("Does user1 exist? " + bloomFilter.mightContain("user1")); // 输出: true
        System.out.println("Does user4 exist? " + bloomFilter.mightContain("user4")); // 输出: false

        // 关闭连接
        bloomFilter.close();
    }
}

在 Java 中的 redisson 提供了 bloomFilter 类，可直接使用这个类提供的布隆过滤器实现。

RedisBloom 模块的使用

RedisBloom 是 Redis 官方提供的插件，简化了布隆过滤器的实现，提供了更好的性能和更少的误判率控制。

常用命令：

**BF.RESERVE key error_rate capacity**：创建一个布隆过滤器，指定误判率和容量。
**BF.ADD key item**：向布隆过滤器中添加一个元素。
**BF.EXISTS key item**：检查一个元素是否可能存在。
- RedisBloom 可以自动调整底层数据结构大小以适应不断增加的数据量，用户可以指定误判率。

RedisBloom实现布隆过滤器的步骤示例：

1）创建布隆过滤器（基于 RedisBloom 模块）：

BF.RESERVE myBloomFilter 0.01 1000000

上述命令创建了一个误判率为 1% 且容量为 100 万的布隆过滤器。

2）添加元素：

BF.ADD myBloomFilter "item1"

3）检查元素是否存在：

BF.EXISTS myBloomFilter "item1"    # 返回 1（可能存在）
BF.EXISTS myBloomFilter "item2"    # 返回 0（一定不存在）

布隆过滤器适用场景

布隆过滤器一般都在海量数据判断场景，且可以允许误判。

1）爬虫：

对已经爬取过的海量 URL 去重。

2）黑名单：

例如反垃圾邮件，用于判断一个邮件地址是否在黑名单中，提高垃圾邮件过滤的效率（可能会误杀）。

3）分布式系统：

用于判断数据是否在某个节点上，减少网络请求，提高系统性能。例如，Hadoop 和 Cassandra 都使用布隆过滤器来优化数据分布和查找。

4）推荐系统：

用于判断用户是否已经看过某个推荐内容，避免重复推荐。