• SpringBoot 中使用布隆过滤器 Guava、Redission实现

    目前市面上也有好几种实现方式，如果你需要高度定制化，可以完全从零实现，当然这不是一个简单的工程。

    如果只是想快速开始的话，那么市面上现成的实现，无疑是最快的。

    前言

    今天说到的实现方式有以下几种：

    • 引入 Guava 实现
    • 引入 hutool 实现
    • 引入 Redission 实现
    • Guava 布隆过滤器结合 Redis （重点）

    项目工程的搭建，就在这里先写明啦~

    boot项目就是四步走~ 导包->写配置->编写配置类->使用

    补充说明：我使用的 redis 是用docker下载的一个集成redis和布隆过滤器的镜像。安装方式：Docker安装Redis布隆过滤器

    如果你是在windows上安装的redis 是3.0版本的，是无法集成布隆过滤器。

    如果是在liunx版本上的redis，需要再额外下载一个布隆过滤器的模块。需要自行百度啦~

    我将要用到的所有jar都放在这里啦~

    1.  <parent>
    2.      <artifactId>spring-boot-dependencies</artifactId>
    3.      <groupId>org.springframework.boot</groupId>
    4.      <version>2.5.2</version>
    5.  </parent>
    6.  <dependencies>
    7.      <dependency>
    8.          <groupId>org.springframework.boot</groupId>
    9.          <artifactId>spring-boot-starter</artifactId>
    10.      </dependency>
    11.      <dependency>
    12.          <groupId>org.springframework.boot</groupId>
    13.          <artifactId>spring-boot-starter-web</artifactId>
    14.      </dependency>
    15.      <dependency>
    16.          <groupId>org.springframework.boot</groupId>
    17.          <artifactId>spring-boot-starter-data-redis</artifactId>
    18.      </dependency>
    19.      <!-- https://mvnrepository.com/artifact/org.redisson/redisson-spring-boot-starter -->
    20.      <dependency>
    21.          <groupId>org.redisson</groupId>
    22.          <artifactId>redisson-spring-boot-starter</artifactId>
    23.          <version>3.17.6</version>
    24.      </dependency>
    25.  ​
    26.      <dependency>
    27.          <groupId>com.google.guava</groupId>
    28.          <artifactId>guava</artifactId>
    29.          <version>30.0-jre</version>
    30.      </dependency>
    31.      <dependency>
    32.          <groupId>org.springframework.boot</groupId>
    33.          <artifactId>spring-boot-starter-test</artifactId>
    34.      </dependency>
    35.      <dependency>
    36.          <groupId>junit</groupId>
    37.          <artifactId>junit</artifactId>
    38.          <scope>test</scope>
    39.      </dependency>
    40.      <dependency>
    41.          <groupId>org.projectlombok</groupId>
    42.          <artifactId>lombok</artifactId>
    43.      </dependency>
    44.      <dependency>
    45.          <groupId>cn.hutool</groupId>
    46.          <artifactId>hutool-all</artifactId>
    47.          <version>5.7.22</version>
    48.      </dependency>
    49.  </dependencies>
    50.  ​
    51. 复制代码

    yml 配置文件：

    1.  server:
    2.    port: 8081
    3.  spring:
    4.    redis:
    5.      port: 6379
    6.      host: 192.xxx
    7. 复制代码

    一、Guava 实现布隆过滤器

    这个方式非常快捷：

    直接用一个Demo来说明吧

    1.      @Test
    2.      public void test2() {
    3.          // 预期插入数量
    4.          long capacity = 10000L;
    5.          // 错误比率
    6.          double errorRate = 0.01;
    7.          //创建BloomFilter对象，需要传入Funnel对象，预估的元素个数，错误率
    8.          BloomFilter<Long> filter = BloomFilter.create(Funnels.longFunnel(), capacity, errorRate);
    9.  //        BloomFilter<String> filter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 10000, 0.0001);
    10.          //put值进去
    11.          for (long i = 0; i < capacity; i++) {
    12.              filter.put(i);
    13.          }
    14.          // 统计误判次数
    15.          int count = 0;
    16.          // 我在数据范围之外的数据，测试相同量的数据，判断错误率是不是符合我们当时设定的错误率
    17.          for (long i = capacity; i < capacity * 2; i++) {
    18.              if (filter.mightContain(i)) {
    19.                  count++;
    20.              }
    21.          }
    22.          System.out.println(count);
    23.      }
    24.  ​
    25. 复制代码

    当容量为1k，误判率为 0.01时

    1.  2022-08-26 23:50:01.028  INFO 14748 --- [           main] com.nzc.test.RedisBloomFilterTest        : 存入元素为==1000
    2.  误判个数为==>10
    3. 复制代码

    当容量为1w，误判率为 0.01时

    1.  2022-08-26 23:49:23.618  INFO 21796 --- [           main] com.nzc.test.RedisBloomFilterTest        : 存入元素为==10000
    2.  误判个数为==>87
    3.  ​
    4. 复制代码

    当容量为100w，误判率为 0.01时

    1.  2022-08-26 23:50:45.167  INFO 8964 --- [           main] com.nzc.test.RedisBloomFilterTest        : 存入元素为==1000000
    2.  误判个数为==>9946
    3. 复制代码

    BloomFilter filter = BloomFilter.create(Funnels.longFunnel(), capacity, errorRate);

    create方法实际上调用的方法是：

    1.  public static  BloomFilter create(
    2.      Funnelsuper T> funnel, int expectedInsertions, double fpp) {
    3.    return create(funnel, (long) expectedInsertions, fpp);
    4.  }
    5. 复制代码
    • funnel 用来对参数做转化,方便生成hash值
    • expectedInsertions 预期插入的数据量大小
    • fpp 误判率

    里面具体的实现，相对我来说，数学能力有限，没法说清楚。希望大家多多包含。

    二、Hutool 布隆过滤器

    Hutool 工具中的布隆过滤器，内存占用太高了，并且功能相比于guava也弱了很多，个人不建议使用。

    1.  @Test
    2.  public void test4(){
    3.      int capacity = 100;
    4.      // 错误比率
    5.      double errorRate = 0.01;
    6.      // 初始化
    7.      BitMapBloomFilter filter = new BitMapBloomFilter(capacity);
    8.      for (int i = 0; i < capacity; i++) {
    9.          filter.add(String.valueOf(i));
    10.      }
    11.  ​
    12.      log.info("存入元素为=={}",capacity);
    13.      // 统计误判次数
    14.      int count = 0;
    15.      // 我在数据范围之外的数据，测试相同量的数据，判断错误率是不是符合我们当时设定的错误率
    16.      for (int i = capacity; i < capacity * 2; i++) {
    17.          if (filter.contains(String.valueOf(i))) {
    18.              count++;
    19.          }
    20.      }
    21.      log.info("误判元素为==={}",count);
    22.  }
    23. 复制代码

    三、Redission 布隆过滤器

    redission的使用其实也很简单，官方也有非常好的教程。

    引入jar，然后编写一个config类即可

    1.  ​
    2.  <dependency>
    3.      <groupId>org.springframework.boot</groupId>
    4.      <artifactId>spring-boot-starter-data-redis</artifactId>
    5.  </dependency>
    6.  <!-- https://mvnrepository.com/artifact/org.redisson/redisson-spring-boot-starter -->
    7.  <dependency>
    8.      <groupId>org.redisson</groupId>
    9.      <artifactId>redisson-spring-boot-starter</artifactId>
    10.      <version>3.17.6</version>
    11.  </dependency>
    12. 复制代码

    出了注入 redissionclient，还注入了一些redis相关的东西，都是历史包裹~

    1.  /**
    2.   * @description:
    3.   * @author: Yihui Wang
    4.   * @date: 2022年08月26日 22:06
    5.   */
    6.  @Configuration
    7.  @EnableCaching
    8.  public class RedisConfig {
    9.  ​
    10.      @Bean
    11.      public RedissonClient redissonClient(){
    12.          Config config = new Config();
    13.          config.useSingleServer().setAddress("redis://47.113.227.254:6379");
    14.          RedissonClient redissonClient = Redisson.create(config);
    15.          return  redissonClient;
    16.      }
    17.  ​
    18.      @Bean
    19.      public CacheManager cacheManager(RedisConnectionFactory connectionFactory) {
    20.          RedisCacheManager rcm=RedisCacheManager.create(connectionFactory);
    21.          return rcm;
    22.      }
    23.      @Bean
    24.      public RedisTemplate<String, Object> redisTemplate(RedisConnectionFactory factory) {
    25.          RedisTemplate<String, Object> redisTemplate = new RedisTemplate<String, Object>();
    26.          redisTemplate.setConnectionFactory(factory);
    27.   
    28.          Jackson2JsonRedisSerializer jackson2JsonRedisSerializer = new
    29.                  Jackson2JsonRedisSerializer(Object.class);
    30.          ObjectMapper om = new ObjectMapper();
    31.          om.setVisibility(PropertyAccessor.ALL, JsonAutoDetect.Visibility.ANY);
    32.          om.enableDefaultTyping(ObjectMapper.DefaultTyping.NON_FINAL);
    33.          jackson2JsonRedisSerializer.setObjectMapper(om);
    34.          //序列化设置 ，这样计算是正常显示的数据，也能正常存储和获取
    35.          redisTemplate.setKeySerializer(jackson2JsonRedisSerializer);
    36.          redisTemplate.setValueSerializer(jackson2JsonRedisSerializer);
    37.          redisTemplate.setHashKeySerializer(jackson2JsonRedisSerializer);
    38.          redisTemplate.setHashValueSerializer(jackson2JsonRedisSerializer);
    39.   
    40.          return redisTemplate;
    41.      }
    42.      @Bean
    43.      public StringRedisTemplate stringRedisTemplate(RedisConnectionFactory factory) {
    44.          StringRedisTemplate stringRedisTemplate = new StringRedisTemplate();
    45.          stringRedisTemplate.setConnectionFactory(factory);
    46.          return stringRedisTemplate;
    47.      }
    48.  }
    49. 复制代码

    我们在中间再编写一个Service，

    1.  @Service
    2.  public class BloomFilterService {
    3.  ​
    4.      @Autowired
    5.      private RedissonClient redissonClient;
    6.  ​
    7.      /**
    8.       * 创建布隆过滤器
    9.       * @param filterName 布隆过滤器名称
    10.       * @param capacity 预测插入数量
    11.       * @param errorRate 误判率
    12.       * @param <T>
    13.       * @return
    14.       */
    15.      public <T> RBloomFilter<T> create(String filterName, long capacity, double errorRate) {
    16.          RBloomFilter<T> bloomFilter = redissonClient.getBloomFilter(filterName);
    17.          bloomFilter.tryInit(capacity, errorRate);
    18.          return bloomFilter;
    19.      }
    20.  }
    21. 复制代码

    测试：

    1.  package com.nzc.test;
    2.  ​
    3.  import com.nzc.WebApplication;
    4.  import com.nzc.service.BloomFilterService;
    5.  import lombok.extern.slf4j.Slf4j;
    6.  import org.junit.Test;
    7.  import org.junit.runner.RunWith;
    8.  import org.redisson.api.RBloomFilter;
    9.  import org.springframework.beans.factory.annotation.Autowired;
    10.  import org.springframework.boot.test.context.SpringBootTest;
    11.  import org.springframework.test.context.junit4.SpringRunner;
    12.  ​
    13.  @Slf4j
    14.  @RunWith(SpringRunner.class)
    15.  @SpringBootTest(classes = WebApplication.class)
    16.  public class BloomFilterTest {
    17.  ​
    18.      @Autowired
    19.      private BloomFilterService bloomFilterService;
    20.  ​
    21.      @Test
    22.      public void testBloomFilter() {
    23.          // 预期插入数量
    24.          long expectedInsertions = 1000L;
    25.          // 错误比率
    26.          double falseProbability = 0.01;
    27.          RBloomFilter<Long> bloomFilter = bloomFilterService.create("NZC:BOOM-FILTER", expectedInsertions, falseProbability);
    28.          // 布隆过滤器增加元素
    29.          for (long i = 0; i < expectedInsertions; i++) {
    30.              bloomFilter.add(i);
    31.          }
    32.          long elementCount = bloomFilter.count();
    33.          log.info("布隆过滤器中含有元素个数 = {}.", elementCount);
    34.  ​
    35.          // 统计误判次数
    36.          int count = 0;
    37.          // 我在数据范围之外的数据，测试相同量的数据，判断错误率是不是符合我们当时设定的错误率
    38.          for (long i = expectedInsertions; i < expectedInsertions * 2; i++) {
    39.              if (bloomFilter.contains(i)) {
    40.                  count++;
    41.              }
    42.          }
    43.          log.info("误判次数 = {}.", count);
    44.  ​
    45.          // 清空布隆过滤器 内部实现是个异步线程在执行  我只是为了方便测试
    46.          bloomFilter.delete();
    47.      }
    48.  }
    49. 复制代码

    当容量为1k，误判率为0.01时的输出情况

    1.  2022-08-26 23:37:04.903  INFO 1472 --- [           main] com.nzc.test.BloomFilterTest             : 布隆过滤器中含有元素个数 = 993.
    2.  2022-08-26 23:37:38.549  INFO 1472 --- [           main] com.nzc.test.BloomFilterTest             : 误判次数 = 36.
    3. 复制代码

    当容量为1w，误判率为0.01时的输出情况

    1.  2022-08-26 23:50:54.478  INFO 17088 --- [           main] com.nzc.test.BloomFilterTest             : 布隆过滤器中含有元素个数 = 9895.
    2.  2022-08-26 23:56:56.171  INFO 17088 --- [           main] com.nzc.test.BloomFilterTest             : 误判次数 = 259.
    3. 复制代码

    四、小结

    我实际测试的时候，Guava 的效果应该是最好的，Redission 虽然是直接集成了Redis，但实际效果比起Guava较差一些，我这里没有贴上时间，Redission所创建出来的布隆过滤器，速度较慢。

    当然我的测试范围是有限的，并且只是循环测试，另外服务器也并非在本地，这都有影响。

    但是仅目前看来是这样的。

    还有就是将 Guava 结合 Redis 一起使用。

    五、Guava 布隆过滤器结合 Redis 使用

    仅限于测试，一切效果还是需看实测。

    我是以 Guava 中创建 布隆过滤器为基础，利用它构造的方法，来进行修改，功能相比于 guava 还是少了很多的。

    1.  package com.nzc.boom;
    2.   
    3.  import com.google.common.annotations.VisibleForTesting;
    4.  import com.google.common.base.Preconditions;
    5.  import com.google.common.hash.Funnel;
    6.  import com.google.common.hash.Hashing;
    7.  import com.google.common.primitives.Longs;
    8.  ​
    9.  public class BloomFilterHelper<T> {
    10.   
    11.      private int numHashFunctions;
    12.   
    13.      private int bitSize;
    14.   
    15.      private Funnel<T> funnel;
    16.   
    17.      public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp) {
    18.          Preconditions.checkArgument(funnel != null, "funnel不能为空");
    19.          this.funnel = funnel;
    20.          // 计算bit数组长度
    21.          bitSize = optimalNumOfBits(expectedInsertions, fpp);
    22.          // 计算hash方法执行次数
    23.          numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
    24.      }
    25.  ​
    26.  ​
    27.      /** 源码
    28.       *public <T> boolean mightContain(
    29.       *         T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {
    30.       *       long bitSize = bits.bitSize();
    31.       *       byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
    32.       *       long hash1 = lowerEight(bytes);
    33.       *       long hash2 = upperEight(bytes);
    34.       *
    35.       *       long combinedHash = hash1;
    36.       *       for (int i = 0; i < numHashFunctions; i++) {
    37.       *         // Make the combined hash positive and indexable
    38.       *         if (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) {
    39.       *           return false;
    40.       *         }
    41.       *         combinedHash += hash2;
    42.       *       }
    43.       *       return true;
    44.       *     }
    45.       * @param value
    46.       * @return
    47.       */
    48.      public long[] murmurHashOffset(T value) {
    49.          long[] offset = new long[numHashFunctions];
    50.          byte[] bytes = Hashing.murmur3_128().hashObject(value, funnel).asBytes();
    51.          long hash1 = lowerEight(bytes);
    52.          long hash2 = upperEight(bytes);
    53.          long combinedHash = hash1;
    54.          for (int i = 1; i <= numHashFunctions; i++) {
    55.              long nextHash = hash1 + i * hash2;
    56.              if (nextHash < 0) {
    57.                  nextHash = ~nextHash;
    58.              }
    59.              offset[i - 1] = nextHash % bitSize;
    60.          }
    61.          return offset;
    62.  ​
    63.  ​
    64.      }
    65.      private /* static */ long lowerEight(byte[] bytes) {
    66.          return Longs.fromBytes(
    67.                  bytes[7], bytes[6], bytes[5], bytes[4], bytes[3], bytes[2], bytes[1], bytes[0]);
    68.      }
    69.  ​
    70.      private /* static */ long upperEight(byte[] bytes) {
    71.          return Longs.fromBytes(
    72.                  bytes[15], bytes[14], bytes[13], bytes[12], bytes[11], bytes[10], bytes[9], bytes[8]);
    73.      }
    74.      /**
    75.       * 计算bit数组长度
    76.       * 同样是guava创建布隆过滤器中的计算bit数组长度方法
    77.       */
    78.      private int optimalNumOfBits(long n, double p) {
    79.          if (p == 0) {
    80.              // 设定最小期望长度
    81.              p = Double.MIN_VALUE;
    82.          }
    83.          return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    84.      }
    85.   
    86.      /**
    87.       * 这里是从guava 中 copy 出来的
    88.       * 就是guava 创建一个 布隆过滤器时，
    89.       * 计算hash方法执行次数的方法
    90.       */
    91.      private int optimalNumOfHashFunctions(long n, long m) {
    92.          int countOfHash = Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    93.          return countOfHash;
    94.      }
    95.  ​
    96.  }
    97. 复制代码

    以上的这些代码，在guava包都可以找到的。

    在redisConfig中注入布隆过滤器

    1.  ​
    2.  /**
    3.   * @description:
    4.   * @author: Yihui Wang
    5.   * @date: 2022年08月26日 22:06
    6.   */
    7.  @Configuration
    8.  @EnableCaching
    9.  public class RedisConfig {
    10.  ​
    11.      @Bean
    12.      public CacheManager cacheManager(RedisConnectionFactory connectionFactory) {
    13.          RedisCacheManager rcm=RedisCacheManager.create(connectionFactory);
    14.          return rcm;
    15.      }
    16.      @Bean
    17.      public RedisTemplate<String, Object> redisTemplate(RedisConnectionFactory factory) {
    18.          RedisTemplate<String, Object> redisTemplate = new RedisTemplate<String, Object>();
    19.          redisTemplate.setConnectionFactory(factory);
    20.   
    21.          Jackson2JsonRedisSerializer jackson2JsonRedisSerializer = new
    22.                  Jackson2JsonRedisSerializer(Object.class);
    23.          ObjectMapper om = new ObjectMapper();
    24.          om.setVisibility(PropertyAccessor.ALL, JsonAutoDetect.Visibility.ANY);
    25.          om.enableDefaultTyping(ObjectMapper.DefaultTyping.NON_FINAL);
    26.          jackson2JsonRedisSerializer.setObjectMapper(om);
    27.          //序列化设置 ，这样计算是正常显示的数据，也能正常存储和获取
    28.          redisTemplate.setKeySerializer(jackson2JsonRedisSerializer);
    29.          redisTemplate.setValueSerializer(jackson2JsonRedisSerializer);
    30.          redisTemplate.setHashKeySerializer(jackson2JsonRedisSerializer);
    31.          redisTemplate.setHashValueSerializer(jackson2JsonRedisSerializer);
    32.   
    33.          return redisTemplate;
    34.      }
    35.      @Bean
    36.      public StringRedisTemplate stringRedisTemplate(RedisConnectionFactory factory) {
    37.          StringRedisTemplate stringRedisTemplate = new StringRedisTemplate();
    38.          stringRedisTemplate.setConnectionFactory(factory);
    39.          return stringRedisTemplate;
    40.      }
    41.   
    42.      
    43.      //初始化布隆过滤器，放入到spring容器里面
    44.      @Bean
    45.      public BloomFilterHelper<String> initBloomFilterHelper() {
    46.          return new BloomFilterHelper<String>((Funnel<String>) (from, into) -> into.putString(from, Charsets.UTF_8).putString(from, Charsets.UTF_8), 1000, 0.01);
    47.      }
    48.  ​
    49.      @Bean
    50.      public BloomFilterHelper<Long> initLongBloomFilterHelper() {
    51.          return new BloomFilterHelper<Long>((Funnel<Long>) (from, into) -> into.putLong(from),1000, 0.01);
    52.      }
    53.  ​
    54.  ​
    55.  }
    56. 复制代码

    也就是注入我们刚刚编写的那个布隆过滤器。

    然后再编写一个Service 层

    1.  ​
    2.  /**
    3.   * @description:
    4.   * @author: Yihui Wang
    5.   */
    6.  @Slf4j
    7.  @Service
    8.  public class RedisBloomFilter {
    9.  ​
    10.      @Autowired
    11.      private RedisTemplate redisTemplate;
    12.  ​
    13.      /**
    14.       * 根据给定的布隆过滤器添加值
    15.       */
    16.      public <T> void addByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
    17.          Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
    18.          long[] offset = bloomFilterHelper.murmurHashOffset(value);
    19.          for (long i : offset) {
    20.              log.info("key :{} ，value : {}", key,  i);
    21.              redisTemplate.opsForValue().setBit(key, i, true);
    22.          }
    23.      }
    24.  ​
    25.      /**
    26.       * 根据给定的布隆过滤器判断值是否存在
    27.       */
    28.      public <T> boolean includeByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
    29.          Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
    30.          long[] offset = bloomFilterHelper.murmurHashOffset(value);
    31.          for (long i : offset) {
    32.              log.info("key :{} ，value : {}", key,  i);
    33.              if (!redisTemplate.opsForValue().getBit(key, i)) {
    34.                  return false;
    35.              }
    36.          }
    37.          return true;
    38.      }
    39.  }
    40. 复制代码

    测试：

    1.      @Test
    2.      public void test1() {
    3.          // 预期插入数量
    4.          long capacity = 1000L;
    5.          // 错误比率
    6.          double errorRate = 0.01;
    7.          for (long i = 0; i < capacity; i++) {
    8.              redisBloomFilter.addByBloomFilter(bloomFilterHelper, "nzc:bloomFilter1", i);
    9.          }
    10.          log.info("存入元素为=={}", capacity);
    11.          // 统计误判次数
    12.          int count = 0;
    13.          // 我在数据范围之外的数据，测试相同量的数据，判断错误率是不是符合我们当时设定的错误率
    14.          for (long i = capacity; i < capacity * 2; i++) {
    15.              if (redisBloomFilter.includeByBloomFilter(bloomFilterHelper, "nzc:bloomFilter1", i)) {
    16.                  count++;
    17.              }
    18.          }
    19.          System.out.println("误判个数为==>" + count);
    20.      }
    21.  ​
    22. 复制代码

    输出：

    1.  存入元素为==1000
    2.  误判个数为==>12
  • 相关阅读:
    Web应用开发 - 实训三 B Servlet基础
    销售外勤自动生成日报：每天节省 20 分钟，每年节省 121小时，把更多精力放在客户开发和跟进上
    【微信小程序开发】宠物预约医疗项目实战-环境配置与Vant UI集成
    学习SpringMVC的第四天
    【技术积累】软件工程中的测试驱动开发【一】
    Java中操作MongoDB-自用笔记
    温湿度计传感器DHT11控制数码管显示verilog代码及视频
    为自己量身打造一个 Rust 项目模板/脚手架
    CentOS 7通过yum安装Docker和docker-compose
    python3网络爬虫--2323爬取B站视频弹幕 解so文件（附源码）
  • 原文地址：https://blog.csdn.net/m0_73311735/article/details/126557115