Redis布隆过滤器

简介

布隆过滤器（Bloom Filter）是 1970 年由布隆提出的，是一种非常节省空间的概率数据结构，运行速度快，占用内存小，但是有一定的误判率且无法删除元素。它实际上是一个很长的二进制向量和一系列随机映射函数组成，主要用于判断一个元素是否在一个集合中。

Guava 中的布隆过滤器仅使用于单机环境，不使用于分布式环境，分布式环境

模块加载

1、点击https://redis.io/modules 找到RedisBloom。 实际地址：https://github.com/RedisBloom/RedisBloom

2、点击进去下载RedisBloom-master.zip文件，上传到linux

3、解压缩刚才的RedisBloom文件

unzip RedisBloom-master.zip
cd RedisBloom-master
#编译安装
make
#make完生成redisbloom.so，拷贝到redis的安装目录。
cp redisbloom.so /home/www/server/redis

4、在redis.conf配置文件中加入RedisBloom的redisbloom.so文件的地址

loadmodule /home/www/server/redis/redisbloom.so

如果是集群则每个配置文件中都需要加入redisbloom.so文件的地址

5、或者在启动时指定 module。

redis-server redis.conf --loadmodule /home/www/server/redis/redisbloom.so

重启Redis，在本地和测试环境还可以，但是正式环境能不重启就不需要重启，那这么做可以不重启Redis，使用module load命令执行。

MODULE LOAD /home/www/server/redis/redisbloom.so
module list

命令介绍

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

创建BloomFilter

使用给定的期望错误率和初始容量创建空的布隆过滤器

BF.RESERVE {
   key} {
   error_rate} {
   capacity} [EXPANSION expansion] [NONSCALING]

参数说明

• key：布隆过滤器的key
• error_rate：期望的错误率（False Positive Rate），该值必须介于0和1之间。该值越小，BloomFilter的内存占用量越大，CPU使用率越高
• capacity：布隆过滤器的初始容量，即期望添加到布隆过滤器中的元素的个数。当实际添加的元素个数超过该值时，布隆过滤器将进行自动的扩容，该过程会导致性能有所下降，下降的程度是随着元素个数的指数级增长而线性下降
• EXPANSION：元素超过capacity，扩展。即新容器的capacity是旧容器的capacity的多少倍。默认值是2.
• NONSCALING：元素超过capacity，不扩展。

返回值

• 成功：OK
• 其它情况返回相应的异常信息

增加元素

BF.ADD   {key}  {element}
BF.MADD {key}  {element}  {element}  {element}

• BF.ADD 返回值：

  • 元素不存在插入成功：返回1
  • 元素可能已经存在：返回0
  • 其它情况返回相应的异常信息

• BF.MADD返回值：

  • 成功：返回一个数组，数组的每一个元素可能为1或0，当item一定不存在时数组元素值为1，当item可能已经存在时数组元素值为0
  • 其它情况返回相应的异常信息

判断是否存在

 BF.EXISTS  {key}  {element}
 BF.MEXISTS   {key}  {element} {element} {element}

• BF.EXISTS返回值：
  • 元素一定不存在：0
  • 元素可能存在：1
  • 其它情况返回相应的异常信息
• BF.MEXISTS返回值：返回一个数组。
  • 元素一定不存在：0
  • 元素可能存在：1
  • 其它情况返回相应的异常信息

插入元素

向key指定的Bloom中添加多个元素，添加时可以指定大小和错误率，且可以控制在Bloom不存在的时候是否自动创建

bf.insert{key} [CAPACITY {cap}] [ERROR {ERROR}] [NOCREATE] ITEMS {item…}

增量持久化

用于对布隆过滤器的增量保存，这适用于不能正常保存和恢复的大型布隆过滤器，第一次调用此命令时，iter的值应为 0。此命令返回连续(iter, data)对，直到(0, NULL)指示完成。

bf.scandump {key} {item}

• 参数说明：
  • key：布隆过滤器的名字
  • item：首次调用传值0，或者上次调用此命令返回的结果值

加载数据

加载增量保存的布隆过滤器数据。

BF.LOADCHUNK {key} {iter} {data}

其中iter和data是每次执行BF.SCANDUMP返回的结果值

参考：https://redis.io/commands/bf.scandump/

查看信息

返回布隆过滤器的相关信息

bf.info {key}

• 返回值：
  • Capacity：预设容量
  • Size：实际占用情况，但如何计算待进一步确认
  • Number of filters：过滤器层数
  • Number of items inserted：已经实际插入的元素数量
  • Expansion rate：子过滤器扩容系数（默认2）

debug

查看布隆过滤器的内部详细信息

bf.debug  {key}

返回值：

• size：布隆过滤器中已插入的元素数量
• 每层BloomFilter的详细信息
  • bytes：占用字节数量
    bits：占用bit位数量，bits = bytes * 8
  • shashes：该层hash函数数量
  • hashwidth：hash函数宽度
  • capacity：该层容量（第一层为BloomFilter初始化时设置的容量，第2层容量 = 第一层容量 * expansion，以此类推）
  • size：该层中已插入的元素数量（各层size之和等于BloomFilter中已插入的元素数量size）
  • ratio：该层错误率（第一层的错误率 = BloomFilter初始化时设置的错误率 * 0.5，第二层为第一层的0.5倍，以此类推，ratio与expansion无关）

Java集成Redis使用布隆过滤器

1、redisson实现

<dependency>
   <groupId>org.redisson</groupId>
   <artifactId>redisson-spring-boot-starter</artifactId>
   <version>3.13.2</version>
</dependency>

代码示例1：

Config config = new Config();
SingleServerConfig singleServerConfig = config.useSingleServer();
singleServerConfig.setAddress("redis://127.0.0.1:6379");
singleServerConfig.setPassword("123456");
RedissonClient redissonClient = Redisson.create(config);
RBloomFilter<String> bloom = redissonClient.getBloomFilter("name");
// 初始化布隆过滤器；  大小:100000，误判率:0.01
bloom.tryInit(100000L, 0.01);
for(int i=0;i<100000;i++) {
   
    bloom.add("name" + i);
}
boolean notExist = bloom.contains("name1");
if (notExist) {
   
    notExistList.add(str);
}

代码示例2：

@RunWith(SpringRunner.class)
@SpringBootTest
public class BloomFilterTest {
   

    @Autowired
    private RedissonClient redissonClient;


    @Test
    public void testAll() {
   
        String key ="BF:AAB";
        RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter(key);
       bloomFilter.tryInit(500,0.01);

        bloomFilter.add("happy");
        bloomFilter.add("cool");
        boolean aNew = bloomFilter.contains("new");
        System.out.println(aNew);
        aNew =   bloomFilter.contains("cool");
        System.out.println(aNew);
    }
}

注意：

#如果不执行 bloom.tryInit(100000L, 0.01); 进行初始化，则会抛出以下异常：
Bloom filter is not initialized!
# Redisson 创建的bloomFilter 内部类型为String。不能操作使用bf.RESERVE 生成的key
WRONGTYPE Operation against a key holding the wrong kind of value. channel: [id: 0x155aa9f1, L:/192.168.8.55:50887 - R:/192.168.1.54:6378] command: (SETBIT), params: [BF:AAA, 14, 1]

127.0.0.1:6379> type BF:AAA
MBbloom--
127.0.0.1:6379> type BF:AAB
string

2、com.redislabs实现

        <!-- https://mvnrepository.com/artifact/com.redislabs/jrebloom -->
        <dependency>
            <groupId>com.redislabs</groupId>
            <artifactId>jrebloom</artifactId>
            <version>2.2.2</version>
        </dependency>

@Configuration

public class RedisBloomFilterConfiguration {
   

    @Autowired
    private RedisTemplate redisTemplate;

    @Bean
    public JedisPool jedisPool() {
   
        RedisConnectionFactory connectionFactory = redisTemplate.getConnectionFactory();
        if (connectionFactory instanceof LettuceConnectionFactory) {
   
            LettuceConnectionFactory lettuceConnectionFactory = (LettuceConnectionFactory) connectionFactory;

            return new JedisPool(new GenericObjectPoolConfig()
                    , lettuceConnectionFactory.getHostName()
                    , lettuceConnectionFactory.getPort()
                    , Long.valueOf(lettuceConnectionFactory.getTimeout()).intValue()
                    , lettuceConnectionFactory.getPassword()
                    , lettuceConnectionFactory.getDatabase());
        } else {
   
            if (connectionFactory instanceof JedisConnectionFactory) {
   
                JedisConnectionFactory jedisConnectionFactory = (JedisConnectionFactory) connectionFactory;
                return new JedisPool((jedisConnectionFactory).getPoolConfig());
            }
        }
        throw new IllegalArgumentException("RedisConnectionFactory unsupport.");
    }
}

import io.rebloom.client.Client;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.test.context.junit4.SpringRunner;
import redis.clients.jedis.JedisPool;

@RunWith(SpringRunner.class)
@SpringBootTest
public class BloomFilter2Test {
   

    @Autowired
    private RedisTemplate redisTemplate;
    @Autowired
    private JedisPool jedisPool;

    @Test
    public void testAll() {
   
        String key = "BF:AAE";

        Client client = new Client(jedisPool);

        Boolean exists = redisTemplate.hasKey(key);
        if (!exists) {
   
            client.createFilter(key, 1000, 0.01);
        }

        client.add(key, "happy");
        client.add(key, "cool");
        boolean aNew = client.exists(key, "new");
        System.out.println(aNew);
        aNew = client.exists(key, "cool");
        System.out.println(aNew);
    }
}

127.0.0.1:6379> type BF:AAE
MBbloom--

3、redistemplate + lua

import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.core.script.DefaultRedisScript;
import org.springframework.data.redis.core.script.RedisScript;

import java.util.Arrays;
import java.util.List;

/**
 * RedisBloomFilterUtil
 * RedisTemplate实现方式
 *
 * @author lihz
 * @date 2023/12/5
 */
public class RedisBloomFilterUtil {
   

    private static RedisScript<Boolean> SCRIPT_RESERVE = new DefaultRedisScript<>("return redis.call('bf.reserve', KEYS[1], ARGV[1], ARGV[2])", Boolean.class);

    private static RedisScript<Boolean> SCRIPT_ADD = new DefaultRedisScript<>("return redis.call('bf.add', KEYS[1], ARGV[1])", Boolean.class);

    private static RedisScript<Boolean> SCRIPT_EXISTS = new DefaultRedisScript<>("return redis.call('bf.exists', KEYS[1], ARGV[1])", Boolean.class);

    private static String SCRIPT_MADD = "return redis.call('bf.madd', KEYS[1], %s)";

    private static String SCRIPT_MEXISTS = "return redis.call('bf.mexists', KEYS[1], %s)";

    private RedisTemplate redisTemplate;

    public RedisBloomFilterUtil(RedisTemplate redisTemplate) {
   
        this.redisTemplate = redisTemplate;
    }

    /**
     * 设置错误率和大小（需要在添加元素前调用，若已存在元素，则会报错）
     * 错误率越低，需要的空间越大
     *
     * @param key
     * @param errorRate   错误率，默认0.01
     * @param initialSize 默认100，预计放入的元素数量，当实际数量超出这个数值时，误判率会上升，尽量估计一个准确数值再加上一定的冗余空间
     * @return
     */
    public Boolean reserve(String key, double errorRate, int initialSize) {
   
        return (Boolean) redisTemplate.<Boolean>execute(SCRIPT_RESERVE, Arrays.asList(key), String.valueOf(errorRate),
                String.valueOf(initialSize));
    }

    /**
     * 添加元素
     *
     * @param key
     * @param value
     * @return true表示添加成功，false表示添加失败（存在时会返回false）
     */
    public Boolean add(String key, String value) {
   
        return (Boolean) redisTemplate.<Boolean>execute(SCRIPT_ADD, Arrays.asList(key), value);
    }

    /**
     * 查看元素是否存在（判断为存在时有可能是误判，不存在是一定不存在）
     *
     * @param key
     * @param value
     * @return true表示存在，false表示不存在
     */
    public Boolean exists(String key, String value) {
   
        return (Boolean) redisTemplate.<Boolean>execute(SCRIPT_EXISTS, Arrays.asList(key), value);
    }

    /**
     * 批量添加元素
     *
     * @param key
     * @param values
     * @return 按序 1表示添加成功，0表示添加失败
     */
    public List<Integer> madd(String key, List<String> values) {
   
        String[] vs = new String[values.size()];
        values.toArray(vs);

        return (List<Integer>) redisTemplate.execute(this.generateScript(SCRIPT_MADD, vs), Arrays.asList(key),
                vs);
    }

    /**
     * 批量检查元素是否存在（判断为存在时有可能是误判，不存在是一定不存在）
     *
     * @param key
     * @param values
     * @return 按序 1表示存在，0表示不存在
     */
    public List<Integer> mexists(String key, List<String> values) {
   
        String[] vs = new String[values.size()];
        values.toArray(vs);
        return (List<Integer>) redisTemplate.execute(this.generateScript(SCRIPT_MEXISTS, vs), Arrays.asList(key), vs);
    }

    private RedisScript<List> generateScript(String script, String[] values) {
   
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= values.length; i++) {
   
            if (i != 1) {
   
                sb.append(",");
            }
            sb.append("ARGV[").append(i).append("]");
        }
        return new DefaultRedisScript<>(String.format(script, sb.toString()), List.class);
    }
}


public class BloomFilter2Test {
   

    @Autowired

    private RedisTemplate redisTemplate;
    @Autowired
    private JedisPool jedisPool;

 
    public void testAll() {
   
        String key = "BF:AAH";

        StringRedisSerializer serializer = new StringRedisSerializer();
        redisTemplate.setKeySerializer(serializer);
        redisTemplate.setValueSerializer(serializer);

        RedisBloomFilterUtil util = new RedisBloomFilterUtil(redisTemplate);

        Boolean exists = redisTemplate.hasKey(key);
        if (!exists) {
   
            util.reserve(key, 0.01, 1000);
        }

        util.add(key, "happy");
        util.add(key, "cool");

        boolean aNew = util.exists(key, "new");
        System.out.println(aNew);
        aNew = util.exists(key, "cool");
        System.out.println(aNew);

        util.madd(key, Arrays.asList("rich", "niubi", "hot", "cry"));

        List<Integer> mexists = util.mexists(key, Arrays.asList("cool", "swarm"));
        System.out.println(mexists);

        mexists = util.mexists(key, Arrays.asList("cry", "xxx", "hot"));
        System.out.println(mexists);
    }

}   

区别

RedisBloom和Redisson实现的过滤器区别：

• 数据结构： RedisBloom相当于为了实现过滤器而新增了一个数据结构，而Redisson是基于redis原有的bitmap位图数据结构来通过硬编码实现的过滤器。
• 存储： 存储两者其实并没有差距，都没有存储原数据。
• 容错： 同样是10000条数据0.01容错，RedisBloom误判元素是58，Redisson实现的是227。
• 耦合度： 使用RedisBloom就需要安装RedisBloom，如果不安装RedisBloom程序直接就不能使用了，而使用Redisson他只依赖于redis。
• 分片： RedisBloom只是redis一种数据结构，本身redis集群就是支持分片的，所以RedisBloom肯定也没问题，Redisson的布隆过滤器也支持分片，但是需要付费。
• 性能： 使用 redis 的位图来实现的布隆过滤器性能上要差不少。比如一次 exists 查询会涉及到多次 getbit 操作，网络开销相比而言会高出不少。

附录

参考

https://redis.com/blog/bloom-filter/

https://github.com/redis/jedis

spring-data-redis与Jedis版本： https://mvnrepository.com/artifact/org.springframework.data/spring-data-redis

jedis与redis对应版本

免费的在线布隆过滤器在线计算

https://hur.st/bloomfilter/?n=1000000&p=0.03&m=&k=

示例

127.0.0.1:6379> BF.RESERVE BF:AAA 0.01 50 
OK
127.0.0.1:6379> BF.ADD   BF:AAA  abort
(integer) 1
127.0.0.1:6379> BF.ADD   BF:AAA  about
(integer) 1
127.0.0.1:6379> BF.MADD BF:AAA  happy  cool
1) (integer) 1
2) (integer) 1
127.0.0.1:6379> BF.EXISTS BF:AAA  abort
(integer) 1
127.0.0.1:6379> BF.EXISTS BF:AAA  pool
(integer) 0
127.0.0.1:6379> BF.MEXISTS BF:AAA abort pool rich happy
1) (integer) 1
2) (integer) 0
3) (integer) 0
4) (integer) 1
127.0.0.1:6379> BF.INFO BF:AA
(error) ERR not found
127.0.0.1:6379> BF.INFO BF:AAA
 1) Capacity
 2) (integer) 50
 3) Size
 4) (integer) 168
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 4
 9) Expansion rate
10) (integer) 2
127.0.0.1:6379> 
127.0.0.1:6379> bf.debug  BF:AAA
1) "size:4"
2) "bytes:72 bits:576 hashes:8 hashwidth:64 capacity:50 size:4 ratio:0.005"