当前位置： 首页 > article >正文

【redis】数据类型之布隆过滤器

article 2025/3/13 0:52:14

布隆过滤器（Bloom Filter）的算法是由Burton Howard Bloom（伯顿·霍华德·布隆）在1970年提出的。它是一种空间效率很高的概率型数据结构，通常用于判断一个元素是否在集合中。这种数据结构的核心思想是通过一个很长的二进制向量（位数组）和一系列哈希函数来实现快速且近似的存在性查询。

基本组成

二进制向量（位数组）：布隆过滤器使用一个很长的二进制向量作为存储结构，向量中的每个位置（bit）都可以被设置为0或1。

哈希函数：布隆过滤器使用多个哈希函数，这些函数将输入的元素映射到位数组中的多个不同位置。每个哈希函数都会生成一个哈希值，该值指示了位数组中应该被设置为1的位的位置。

基本原理

布隆过滤器主要由一个很长的二进制向量（位数组）和一系列随机映射函数（哈希函数）组成。对于同一个元素，多个哈希函数会将其映射到位数组中的多个不同位置，并将这些位置都标记为1。当需要查询一个元素是否存在于布隆过滤器中时，同样使用这些哈希函数对要查询的元素进行哈希计算，得到多个哈希值。然后检查位数组中对应索引位置的值是否为1。如果所有哈希值对应的位数组中的值都为1，则认为该元素可能存在于集合中。但需要注意的是，由于哈希碰撞的存在，这只是一个概率性的判断，存在误判的可能性。如果任何一个哈希值对应的位数组中的值为0，则可以确定该元素一定不在集合中。

添加元素：当需要向布隆过滤器中添加一个元素时，使用所有的哈希函数对该元素进行哈希计算，得到多个哈希值。然后，将这些哈希值对应的位数组中的位置都设置为1。

查询元素：当需要查询一个元素是否存在于布隆过滤器中时，同样使用所有的哈希函数对该元素进行哈希计算，得到多个哈希值。然后，检查这些哈希值对应的位数组中的位置是否都为1。如果所有位置都为1，则认为该元素可能存在于集合中；如果任何一个位置为0，则可以确定该元素一定不在集合中。

优缺点

优点：

  • 空间效率高：布隆过滤器通过大型bit数组存储数据，每个元素仅占一位空间，大幅降低了内存占用。

  • 查询速度快：由于布隆过滤器只需要进行哈希计算和位检查操作，因此它的查询速度非常快。

  • 时间复杂度低：增加和查询元素的时间复杂度为O(N)，其中N为哈希函数的个数，通常比较小。

  • 保密性强：布隆过滤器不存储元素本身，只存储哈希值，增强了数据的保密性。

  • 支持并行操作：多个哈希函数可以并行计算，提高了处理效率。

  • 可以表示全集：布隆过滤器可以判断一个元素是否不属于某个集合，而其他数据结构往往难以实现这一点。

缺点：

  • 存在一定的误判率：由于哈希碰撞的存在，布隆过滤器可能会将一个不存在的元素误判为存在，但不会将一个存在的元素误判为不存在。

  • 无法获取元素本身：布隆过滤器只存储哈希值，不存储元素本身，因此无法从布隆过滤器中直接获取元素。

  • 删除元素困难：传统的布隆过滤器不支持删除元素。一旦某个元素被添加，无法准确将其从位数组中移除，否则可能会影响其他元素的判定。不过，有一些变形的特定布隆过滤器（如计数布隆过滤器或动态布隆过滤器）可以在一定程度上解决这一问题。

误判率的优化方案

  1. 增大位数组的大小

  2. 增加哈希函数的数量

误判率的大小与哈希函数的数量有关，具体公式：ceil(-ln(error_rate) / ln(2))。

每个元素所需要的字节数与误判率、哈希函数的数量有关，具体公式：-ln(error_rate) / ln(2)^2。

布隆过滤器所占内存的大小为每个元素所需的字节数 * 预估元素数量，具体公式：capacity * -ln(error_rate) / ln(2)^2。

1%的误判率需要7个哈希函数，每个元素需要9.585个字节数。

0.1%的误判率需要10个哈希函数，每个元素需要14.378个字节数。

0.01%的误判率需要14个哈希函数，每个元素需要19.170个字节数。

参考官网：https://redis.io/docs/latest/develop/data-types/probabilistic/bloom-filter/

应用场景

防止缓存穿透：在缓存系统中，布隆过滤器可以用于判断一个请求是否可能命中缓存，从而避免直接访问数据库导致的性能问题。

网络爬虫中的URL去重：在网络爬虫系统中，为了避免重复抓取相同的网页，需要对已经访问过的URL进行记录。使用布隆过滤器可以在保证较低误报率的前提下，极大地节省存储空间。

数据库查询优化：在大型分布式数据库或缓存系统中，使用布隆过滤器可以预先判断一条数据是否存在于数据库中，从而避免不必要的磁盘I/O操作或者网络请求。

垃圾邮件过滤：在电子邮件服务中，可以通过布隆过滤器来快速判断一封邮件的发送者是否位于黑名单中，从而提高过滤效率。

推荐系统：在用户行为日志分析等推荐系统的某些环节，为了快速判断一个用户是否对某个商品产生过特定的行为（如点击、购买），可以使用布隆过滤器来加速处理过程。

密码学与安全领域：例如，在防止字典攻击时，可以使用布隆过滤器来检查输入的密码哈希值是否出现在已知弱密码列表中，而无需直接存储这些敏感信息。

区块链技术：一些区块链实现中使用布隆过滤器来加速交易验证过程，通过减少全节点之间的通信量来提升整个网络的效率。

大数据处理：在处理海量数据时，为了快速过滤掉不符合条件的数据，可以利用布隆过滤器来进行初步筛选，然后再进行精确计算。

安装布隆过滤器

redis实现布隆过滤器有以下几种方式：

  • redis社区版本安装模块RedisBloom

  • 使用安装了布隆过滤器的redis的Docker镜像

  • Redis Stack和Redis企业版自带布隆过滤器

redis社区版本安装模块RedisBloom

下面通过在redis社区版本中安装模块RedisBloom来实现布隆过滤器。

安装RedisBloom模块

首先，你需要下载并安装RedisBloom模块。你可以从RedisBloom的GitHub页面获取最新的版本。

下载地址：https://github.com/RedisBloom/RedisBloom/releases

找到自己安装Redis服务对应版本进行下载，可使用version命令查看redis版本：

$ redis-server --version
Redis server v=6.2.6 sha=00000000:0 malloc=jemalloc-5.1.0 bits=64 build=fffa7f0bbaac9e3e

本机使用的redis版本为6.2.6，需要安装2.4.x版本的RedisBloom即可。

  1. 下载RedisBloom：
$ wget https://github.com/RedisBloom/RedisBloom/archive/refs/tags/v2.4.5.tar.gz
  1. 编译RedisBloom模块：
    安装RedisBloom，需要有以下要求：
# Make 4.0+
$ make -v

# gcc 9以下
$ gcc -v

# Python3
$ python3 -v

执行以下命令进行解压缩：

# 解压缩
$ tar -zxvf RedisBloom-2.4.5.tar.gz

# 进入到解压目录
$ cd RedisBloom-2.4.5

执行以下命令进行安装：

$ ./sbin/setup

$ make

执行./sbin/setup报如下错误：

$ ./sbin/setup
./sbin/setup: line 7: /root/soft/RedisBloom-2.4.5/deps/readies/shibumi/defs: No such file or directory
./sbin/setup: line 11: /root/soft/RedisBloom-2.4.5/deps/readies/bin/getpy3: No such file or directory
./sbin/setup: line 12: get_profile_d: command not found
Traceback (most recent call last):
  File "/root/soft/RedisBloom-2.4.5/sbin/system-setup.py", line 11, in <module>
    import paella
ModuleNotFoundError: No module named 'paella'

Paella是一个Python库，它是RedisBloom模块的依赖项。错误信息表明，Python解释器无法找到Paella库。要解决这个问题，你需要安装Paella库。

# python3安装Paella 
$ pip3 install paella

启动Redis并加载RedisBloom模块

第一种：编译成功后，得到下面文件redisbloom.so文件，可复制到/usr/local/lib/redis/modules/下，并赋予执行权限。

$ cp redisbloom.so /usr/local/lib/redis/modules/redisbloom.so

$ chmod +x /usr/local/lib/redis/modules/redisbloom.so

第二种：在Redis配置文件中加载模块，在redis.conf文件中增加如下内容：

loadmodule /root/soft/RedisBloom/bin/linux-x64-release/redisbloom.so

第三种：你可以在启动Redis时通过命令行参数加载模块：

redis-server --loadmodule /root/soft/RedisBloom/bin/linux-x64-release/redisbloom.so

第四种：如果你已经在运行Redis实例，可以使用MODULE LOAD命令动态加载模块：

redis-cli MODULE LOAD /root/soft/RedisBloom/bin/linux-x64-release/redisbloom.so

使用安装了布隆过滤器的redis的Docker镜像

使用Docker是一种更加简便的方式，官方提供了集成RedisBloom的Docker镜像。

docker run -d --name redis-redisbloom -p 6379:6379 redislabs/rebloom:latest

Docker镜像拉不下可参考这篇文章目前国内可用Docker镜像源汇总：https://www.coderjia.cn/archives/dba3f94c-a021-468a-8ac6-e840f85867ea。

Redis Stack的Docker镜像

RedisStack是Redis官方推出的集成版，除了Redis核心功能，还集成了RedisBloom等多个模块。你可以直接使用 RedisStack来避免单独安装插件。

docker run -d --name redis-stack-server -p 6379:6379 redis/redis-stack:latest

布隆过滤器的使用

布隆过滤器的初始化：

127.0.0.1:6379> bf.reserve bf 0.01 1000
OK

往布隆过滤器中增加元素：

127.0.0.1:6379> bf.add bf 10080
(integer) 1

127.0.0.1:6379> bf.madd bf 10081 10082 10083 10084 10085 10086
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 1
6) (integer) 1

查询元素是否存在布隆过滤器中：

127.0.0.1:6379> bf.exists bf 10089
(integer) 0

127.0.0.1:6379> bf.exists bf 10086
(integer) 1

127.0.0.1:6379> bf.mexists bf 10086 10089
1) (integer) 1
2) (integer) 0

127.0.0.1:6379> type bf
MBbloom--

获取布隆过滤器的信息：

127.0.0.1:6379> bf.info bf
 1) Capacity
 2) (integer) 1000
 3) Size
 4) (integer) 1480
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 7
 9) Expansion rate
10) (integer) 2

这个命令会返回关于布隆过滤器的统计信息，比如添加的元素数量和误报率。

示例代码

以下是一个简单的Java示例，使用jedis库与安装了BloomFilter模块的redis进行交互：

package com.morris.redis.demo.bloomfilter;

import redis.clients.jedis.UnifiedJedis;

import java.util.List;

/**
 * 使用jedis连接安装了BloomFilter模块的redis
 */
public class JedisBloomFilterDemo {

    public static void main(String[] args) {
        UnifiedJedis jedis = new UnifiedJedis("redis://localhost:6379");

        String key = "jbf";

        // 初始化布隆过滤器
        String res1 = jedis.bfReserve(key, 0.01, 1000);
        System.out.println(res1); // OK

        // 往布隆过滤器添加元素
        boolean res2 = jedis.bfAdd(key, "10080");
        System.out.println(res2); // true

        // 往布隆过滤器批量添加元素
        List<Boolean> res3 = jedis.bfMAdd(key,
                "10081", "10082", "10083", "10084",
                "10085", "10086", "10087", "10088");
        System.out.println(res3); // [true, true, true, true, true, true, true, true]

        // 查询元素是否在布隆过滤器中存在
        boolean res4 = jedis.bfExists(key, "10089");
        System.out.println(res4); // false

        // 查询元素是否在布隆过滤器中存在
        boolean res5 = jedis.bfExists(key, "10086");
        System.out.println(res5); // true

        // 批量查询元素是否在布隆过滤器中存在
        List<Boolean> res6 = jedis.bfMExists(key,
                "10086", "10089");
        System.out.println(res6); // [true, false]

        jedis.close();
    }

}

注意：不是所有Redis的Java客户端都支持与安装了BloomFilter模块的redis进行交互。


http://www.kler.cn/a/582062.html

相关文章：

  • 存储过程和自定义函数在银行信贷业务中的应用(oracle)
  • Spark数据倾斜深度解析与实战解决方案
  • 力扣-数组-367 有效的完全平方数
  • 【机器学习的主要类型】
  • HTML5 + Bootstrap5 网站底部代码实现与解析
  • Django系列教程（3）——Django的MVT设计模式
  • 大语言模型（LLM）的微调与应用
  • Elasticsearch 2025/3/7
  • 【漫话机器学习系列】125.普拉托变换（Platt Scaling）
  • 【UNIAPP】获取视频的第一帧作为封面（基于视频URL，Canvas）复制即用
  • git文件过大导致gitea仓库镜像推送失败问题解决（push failed: context deadline exceeded）
  • 在VMware Workstation Pro上轻松部署CentOS7 Linux虚拟机
  • 使用Java爬虫根据关键词获取衣联网商品列表：实战指南
  • 《2025年软件测试工程师面试》MySQL面试题
  • Linux 环境变量快速上手指南
  • 《UI 设计：点亮大数据可视化的智慧之光》
  • 告别手抖烦恼，重拾生活稳 “态”
  • 【物联网-WIFI】
  • 【MySQL】增删改查进阶
  • 【测试框架篇】单元测试框架pytest（5）：setup和teardown的详细使用