redis布隆过滤器（Bloom）具体使用教程

布隆过滤器

Bloom 过滤器是一种概率型数据布局，用于快速判断一个元素是否属于一个聚集。它以较小的空间占用和高效的查询时间著称。下面将对 Bloom 过滤器进行具体论述。
1. 原理

Bloom 过滤器基于哈希函数和位数组实现。它的核心思想是使用多个哈希函数将元素映射到位数组中，并将对应的位设置为1。当查询一个元素时，通过对该元素进行雷同的哈希计算，查抄对应的位是否都为1。假如其中有任何一位为0，则可以确定该元素不在集会合；假如所有位都为1，则该元素大概在集会合，但并不确定，存在肯定的概率误判。
2. 布局和操作

• 位数组（Bit Array）：Bloom 过滤器使用一个固定长度的位数组来表现聚集，并初始化为全0。每个元素通过多个哈希函数映射到位数组上的多个位置。
  
• 哈希函数（Hash Function）：Bloom 过滤器使用多个独立的哈希函数，每个哈希函数可以将一个元素映射到位数组的差别位置。常用的哈希函数包括 MurmurHash、FnvHash、SHA 等。
  
• 添加元素（Add Element）：当向 Bloom 过滤器中添加一个元素时，将该元素颠末多个哈希函数的计算得到的位置对应的位设置为1。
  
• 查询元素（Query Element）：当查询一个元素时，通过多个哈希函数计算出对应的位置，并查抄这些位置上的位是否都为1。假如有任何一位为0，则可以确定该元素不在集会合；假如所有位都为1，则该元素大概在集会合。
  

3. 特点和应用场景

• 空间效率高：Bloom 过滤器使用位数组表现聚集，所需的内存空间相对较小，与聚集大小无关。
  
• 查询效率高：由于只需计算多个哈希函数并查抄位数组上的位，查询时间较短，通常为常数时间复杂度。
  
• 概率误判：Bloom 过滤器在判断一个元素不在集会合时，永远是准确的；但在判断一个元素在集会合时，存在肯定的概率误判。误判率取决于哈希函数的个数和位数组的大小。
  
• 应用场景：Bloom 过滤器适用于需要快速判断元素是否属于一个大规模聚集的场景，如网页爬虫中的 URL 去重、缓存穿透的防护、垃圾邮件过滤等。
  

4. 缺点和留意事项

• 无法删除元素：Bloom 过滤器的位数组一旦被置为1，就无法撤销。因此，无法从 Bloom 过滤器中删除元素。
  
• 哈希函数选择：选择符合的哈希函数和哈希函数的数量非常重要。哈希函数应具有较低的冲突率，并且应该尽量使用独立性较强的哈希函数。
  
• 误判率：误判率取决于哈希函数的个数和位数组的大小。通过调整这些参数可以降低误判率，但也会增加空间占用和查询时间。
  
• 适用范围：Bloom 过滤器适用于对查询时间和空间占用有较高要求，而对概率误判可以接受的场景。在对精确性要求较高的情况下，Bloom 过滤器大概不适用。
  

总而言之，Bloom 过滤器是一种高效的概率型数据布局，通过位数组和多个哈希函数实现快速的聚集元素判断。它在一些特定的应用场景中具有很大的上风，但需要留意选择符合的哈希函数和参数设置，以及理解概率误判的特性。
应用-redis插件布隆过滤器使用具体过程

安装以及配置

布隆过滤器有很多，我这里用的redis提供的布隆过滤器，这次使用的是用docker安装的redis以及配置布隆过滤器
1. 首先下载布隆过滤器这个插件

1. wget https://github.com/RedisLabsModules/rebloom/archive/v2.2.6.tar.gz

复制代码

下载以后解压备用一会等着放到redis中
2.docker安装redis
首先创建文件夹以及配置文件，用于挂在redis启动的后容器中的文件，方便我们在容器外部操作redis的配置
创建文件夹

1. mkdir data  ##创建文件
2. touch redis.conf  ## 创建文件

复制代码

在创建完文件夹以后将我们第一步中下载并解压好的布隆过滤器的文件夹放到我们创建的data文件夹下

在我们创建的redis.conf文件中添加一行配置loadmodule /data/RedisBloom-2.2.6/redisbloom.so

随后直接使用dokcer run下令进行启动，假如没有安装redis则进行下载

1. docker run -p 6379:6379 --name redis -v /root/redis/data:/data -v /root/redis/redis.conf:/etc/redis/redis.conf --restart=always --network host  -d redis:5.0.7 redis-server /etc/redis/redis.conf

复制代码

这个下令是用于在 Docker 中运行 Redis 容器，并进行一些配置。下面是对每个参数的解释：

• -p 6379:6379: 将 Docker 容器的端口 6379 映射到主机的端口 6379，以便可以从主机访问 Redis 服务。
  
• --name redis: 指定容器的名称为 “redis”。
  
• -v /root/redis/data:/data: 将主机的 /root/redis/data 目次挂载到容器的 /data 目次，用于持久化生存 Redis 数据。
  
• -v /root/redis/redis.conf:/etc/redis/redis.conf: 将主机的 /root/redis/redis.conf 配置文件挂载到容器的 /etc/redis/redis.conf，使用该配置文件作为 Redis 的配置。
  
• --restart=always: 设置容器在退出时主动重新启动。
  
• --network host: 使用主机网络模式，容器将共享主机的网络栈。
  
• -d: 在背景运行容器。
  
• redis:5.0.7: 指定使用的 Redis 镜像及其版本号。
  
• redis-server /etc/redis/redis.conf: 在容器中实行的下令，即启动 Redis 服务器，并使用指定的配置文件。
  

实行上述操作redis容器假如启动没有标题那么我们的布隆过滤器的插件和redis都安装并启动乐成了，假如没有启动乐成可以通过docker logs 查看一下redis的启动过程中出现什么标题
下面连接redis实行下面的代码查看否布隆过滤器安装乐成

1. bf.add user test

复制代码

解释一下：bf.add 是安装布隆过滤器后才可以使用的下令，这是添加一个key的下令，user是过滤器的名字，而tese就是我们要去添加的key

这是添加乐成的标识。
springboot项目使用redis布隆过滤器

上面我们把布隆过滤器安装乐成了，那么下面介绍一下在项目中如何应用这个过滤器如何通过代码往复和过滤器交互
我这里使用的redis的过滤器所以用到的依靠直接使用的spring-data-redis这个就可以了

1.         <!--redis的依赖-->
2.         <dependency>
3.             <groupId>org.springframework.boot</groupId>
4.             <artifactId>spring-boot-starter-data-redis</artifactId>
5.         </dependency>

复制代码

引入依靠以后我们配置封装一个用于调用过滤器的工具类

1. import org.springframework.beans.factory.annotation.Autowired;
2. import org.springframework.data.redis.core.RedisTemplate;
3. import org.springframework.data.redis.core.script.DefaultRedisScript;
4. import org.springframework.data.redis.core.script.RedisScript;
5. import org.springframework.data.redis.serializer.RedisSerializer;
6. import org.springframework.stereotype.Component;
7. import org.springframework.transaction.annotation.Transactional;
9. import java.util.Collections;
10. import java.util.List;
11. import java.util.stream.Collectors;
13. @Component
14. public class RedisBloomUtil {
15.     @Autowired
16.     private RedisTemplate redisTemplate;
17.     // 初始化一个布隆过滤器
18.     public Boolean tryInitBloomFilter(String key, long expectedInsertions, double falseProbability) {
19.         Boolean keyExist = redisTemplate.hasKey(key);
20.         if(keyExist) {
21.             return false;
22.         }
23.         RedisScript<Boolean> script = new DefaultRedisScript<>(bloomInitLua(), Boolean.class);
24.         RedisSerializer stringSerializer = redisTemplate.getStringSerializer();
25.         redisTemplate.execute(script, stringSerializer, stringSerializer, Collections.singletonList(key), falseProbability+"", expectedInsertions+"");
26.         return true;
27.     }
28.     // 添加元素
29.     public Boolean addInBloomFilter(String key, Object arg) {
30.         RedisScript<Boolean> script = new DefaultRedisScript<>(addInBloomLua(), Boolean.class);
31.         return (Boolean) redisTemplate.execute(script, Collections.singletonList(key), arg);
32.     }
33.     @Transactional
34.     // 批量添加元素
35.     public Boolean batchAddInBloomFilter(String key, Object... args) {
36.         RedisScript<Boolean> script = new DefaultRedisScript<>(batchAddInBloomLua(), Boolean.class);
37.         return (Boolean) redisTemplate.execute(script, Collections.singletonList(key), args);
38.     }
39.     // 查看某个元素是否是存在
40.     public Boolean existInBloomFilter(String key, Object arg) {
41.         RedisScript<Boolean> script = new DefaultRedisScript<>(existInBloomLua(), Boolean.class);
42.         return (Boolean) redisTemplate.execute(script, Collections.singletonList(key), arg);
43.     }
44.     // 批量查看元素是否存在
45.     public List batchExistInBloomFilter(String key, Object... args) {
46.         RedisScript<List> script = new DefaultRedisScript(batchExistInBloomLua(), List.class);
47.         List<Long> results = (List) redisTemplate.execute(script, Collections.singletonList(key), args);
48.         List<Boolean> booleanList = results.stream().map(res -> res == 1 ? true : false).collect(Collectors.toList());
49.         return booleanList;
50.     }
53.     private String bloomInitLua() {
54.         return "redis.call('bf.reserve', KEYS[1], ARGV[1], ARGV[2])";
55.     }
56.     private String addInBloomLua() {
57.         return "return redis.call('bf.add', KEYS[1], ARGV[1])";
58.     }
59.     private String batchAddInBloomLua() {
60.         StringBuilder sb = new StringBuilder();
61.         sb.append("for index, arg in pairs(ARGV)").append("\r\n");
62.         sb.append("do").append("\r\n");
63.         sb.append("redis.call('bf.add', KEYS[1], arg)").append("\r\n");
64.         sb.append("end").append("\r\n");
65.         sb.append("return true");
66.         return sb.toString();
67.     }
68.     private String existInBloomLua() {
69.         return "return redis.call('bf.exists', KEYS[1], ARGV[1])";
70.     }
71.     private String batchExistInBloomLua() {
72.         StringBuilder sb = new StringBuilder();
73.         sb.append("local results = {}").append("\r\n");
74.         sb.append("for index, arg in pairs(ARGV)").append("\r\n");
75.         sb.append("do").append("\r\n");
76.         sb.append("local exist = redis.call('bf.exists', KEYS[1], arg)").append("\r\n");
77.         sb.append("table.insert(results, exist)").append("\r\n");
78.         sb.append("end").append("\r\n");
79.         sb.append("return results;");
80.         return sb.toString();
81.     }
82. }

复制代码

下面是布隆过滤器的一些基础下令

在 Redis 中，可以使用 RedisBloom 模块来实现布隆过滤器。RedisBloom 是一个开源模块，提供了一系列下令来操作布隆过滤器。下面是 RedisBloom 模块中常用的下令聚集：

• BF.ADD：向布隆过滤器中添加一个元素。
  
  1. BF.ADD <key> <item>

  复制代码
• BF.EXISTS：查抄一个元素是否存在于布隆过滤器中。
  
  1. BF.EXISTS <key> <item>

  复制代码
• BF.MADD：向布隆过滤器中批量添加多个元素。
  
  1. BF.MADD <key> <item> [item ...]

  复制代码
• BF.MEXISTS：批量查抄多个元素是否存在于布隆过滤器中。
  
  1. BF.MEXISTS <key> <item> [item ...]

  复制代码
• BF.INFO：获取布隆过滤器的信息，包括容量、误判率等。
  
  1. BF.INFO <key>

  复制代码
• BF.RESERVE：创建一个新的布隆过滤器，并指定容量和误判率。
  
  1. BF.RESERVE <key> <error_rate> <capacity>

  复制代码
• BF.COUNT：统计布隆过滤器中已添加的元素数量。
  
  1. BF.COUNT <key>

  复制代码
• BF.DEBUG：调试下令，用于打印布隆过滤器内部的一些调试信息。
  
  1. BF.DEBUG <subcommand> [arguments ...]

  复制代码

我上面提供的工具类就是封装的这些下令。
扩展

关于布隆过滤器我们在使用的是留意点，就是在我上面说到的测试一下是否安装乐成时使用的添加数据的下令，bf.add 过滤器名称 key，但是我并没有创建那个名字为user的过滤器，是因为这是程序帮我创建了一个叫做user的过滤器，这个过滤器的配置都是一些基础的配置，比如初始容量是100 错误率是0.01也就是百分之一的错误率，这个过滤明显不能满足我们的需要因为过滤器的工作原理就是通过多个哈希函数对key进行计算然跋文录下来，那么容量就决定了在计算的过程中发生碰撞的概率大小了，所以我们在使用的时候肯定要去手动创建过滤器以确保满足自己的需要。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。