请选择 进入手机版 | 继续访问电脑版

[Redis] Redis BloomFilter实例讲解

[复制链接]
查看24 | 回复4 | 2021-9-14 01:28:02 | 显示全部楼层 |阅读模式
目次

1. 简介

布隆过滤器是防止缓存穿透的方案之一。布隆过滤器紧张 是办理 大规模数据下不必要 准确 过滤的业务场景,如检查垃圾邮件地址,爬虫URL地址去重, 办理 缓存穿透题目 等。

布隆过滤器:在一个存在肯定 数目 的集合中过滤一个对应的元素,判定 该元素是否肯定 不在集合中或者大概 在集合中。它的长处 是空间服从 和查询时间都比一样寻常 的算法要好的多,缺点是有肯定 的误辨认 率和删除困难。

2. guava 实现

google的guava工具类已经帮我们造好了轮子,通过实例来感受一下。

2.1 导入依赖

  1. <dependency>
  2. <groupId>com.google.guava</groupId>
  3. <artifactId>guava</artifactId>
  4. <version>30.1.1-jre</version>
  5. </dependency>
复制代码

2.2 BloomFilterTest

  1. import com.google.common.hash.BloomFilter;
  2. import com.google.common.hash.Funnels;
  3. import lombok.extern.slf4j.Slf4j;
  4. /**
  5. * 布隆过滤器简单实现
  6. * @author ludangxin
  7. * @date 2021/8/16
  8. */
  9. @Slf4j
  10. public class BloomFilterTest {
  11. /**
  12. * 预计要插入元素个数
  13. */
  14. private static final int SIZE = 1000000;
  15. /**
  16. * 误判率
  17. */
  18. private static final double FPP = 0.01;
  19. /**
  20. * 布隆过滤器
  21. */
  22. private static final BloomFilter<Integer> BLOOMFILTER = BloomFilter.create(Funnels.integerFunnel(), SIZE, FPP);
  23. public static void main(String[] args) {
  24. //插入数据
  25. for (int i = 0; i < 1000000; i++) {
  26. BLOOMFILTER.put(i);
  27. }
  28. int count = 0;
  29. // 过滤判断
  30. for (int i = 1000000; i < 3000000; i++) {
  31. if (BLOOMFILTER.mightContain(i)) {
  32. count++;
  33. log.info(i + "误判了");
  34. }
  35. }
  36. log.info("总共的误判数:" + count);
  37. }
  38. }
复制代码

2.3 启动测试

  1. 如上代码,我们设置了0.01的误差,过滤判断时从1000000到3000000,误判了2 * 20000000 ≈ 20339 符合预期。
复制代码
  1. .....
  2. 21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999004误判了
  3. 21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999045误判了
  4. 21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999219误判了
  5. 21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999699误判了
  6. 21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999753误判了
  7. 21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999838误判了
  8. 21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999923误判了
  9. 21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999928误判了
  10. 21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 总共的误判数:20339
复制代码

2.4 末节

guava的工具包固然 好用,但是数据集是存储在jvm中的,分布式环境下依然没法使用 。

3. redisson 实现

3.1 导入依赖

  1. <dependency>
  2. <groupId>org.redisson</groupId>
  3. <artifactId>redisson-spring-boot-starter</artifactId>
  4. <version>3.16.1</version>
  5. </dependency>
复制代码

3.2 BloomFilterWithRedisson

  1. import lombok.RequiredArgsConstructor;
  2. import lombok.extern.slf4j.Slf4j;
  3. import org.redisson.api.RBloomFilter;
  4. import org.redisson.api.RedissonClient;
  5. import org.springframework.web.bind.annotation.GetMapping;
  6. import org.springframework.web.bind.annotation.RequestMapping;
  7. import org.springframework.web.bind.annotation.RestController;
  8. /**
  9. * redisson 布隆过滤器实现
  10. *
  11. * @author ludangxin
  12. * @date 2021/8/16
  13. */
  14. @Slf4j
  15. @RestController
  16. @RequestMapping("bloomFilter")
  17. @RequiredArgsConstructor
  18. public class BloomFilterWithRedisson {
  19. private final RedissonClient redissonClient;
  20. /**
  21. * 预计要插入元素个数
  22. */
  23. private static final long SIZE = 1000000L;
  24. /**
  25. * 误判率
  26. */
  27. private static final double FPP = 0.01;
  28. /**
  29. * 自定义布隆过滤器的 key
  30. */
  31. private static final String BLOOM_FILTER_KEY = "bloomFilter";
  32. /**
  33. * 向布隆过滤器中添加数据, 模拟向布隆过滤器中添加10亿个数据
  34. */
  35. @GetMapping
  36. public void filter() {
  37. // 获取布隆过滤器
  38. RBloomFilter<Integer> bloomFilter = redissonClient.getBloomFilter(BLOOM_FILTER_KEY);
  39. // 初始化,容量为100万, 误判率为0.01
  40. bloomFilter.tryInit(SIZE, FPP);
  41. // 模拟向布隆过滤器中添加100万个数据
  42. for (int i = 0; i < SIZE; i++) {
  43. bloomFilter.add(i);
  44. }
  45. int count = 0;
  46. // 过滤判断
  47. for (int i = 1000000; i < 3000000; i++) {
  48. if (bloomFilter.contains(i)) {
  49. count++;
  50. log.info(i + "误判了");
  51. }
  52. }
  53. log.info("size:" + bloomFilter.getSize());
  54. log.info("总共的误判数:" + count);
  55. }
  56. }
复制代码

3.3 启动测试

  1. 由于机器性能有限,又是单机环境,所以程序没有跑完。
  2. 但由此也可以看出,基于redis的布隆过滤器虽然解决了分布式问题,但是性能和guava bloomfilter没法比。
复制代码

到此这篇关于Redis BloomFilter实例讲解的文章就先容 到这了,更多干系 Redis BloomFilter实例内容请搜索 脚本之家从前 的文章或继续欣赏 下面的干系 文章盼望 大家以后多多支持脚本之家!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

avatar 换即势 | 2021-9-14 03:32:27 | 显示全部楼层
谢谢admin楼主的分享!
回复

使用道具 举报

avatar 夜昙SS | 2021-9-20 11:15:19 | 显示全部楼层
admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的网站,他卖的服务器是永久的,我们的网站用 服务器都是在这家买的,你可以去试试。访问地址:http://fwq.mxswl.com
回复

使用道具 举报

avatar 123457710 | 2021-10-1 06:46:28 | 显示全部楼层
admin楼主,你妈妈喊你回家吃药!
回复

使用道具 举报

avatar 哪吒2017 | 2021-10-4 10:02:26 | 显示全部楼层
admin楼主最近很消极啊!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则