简介

布隆过滤器（Bloom Filter）由布隆于 1970 年提出，它实际上由一个很长的二进制向量和一系列随机映射函数组成。布隆过滤器可以用于查询一个元素是否在一个集合中，它的优点是空间和时间效率都远超一般的算法，缺点是会有一定的误判和删除困难。

工作中遇到的问题

es插入时,我们需要制定id,而制定了id就需要查询,导致读取的压力很大,而且会存在重复插入的场景(id一致,其他也一致,多余的操作)

考虑的几种改造方案:
方案1:插入es前,添加缓存,若存在则不进行多余的es插入
方案2:插入es前,使用boomfilter,理论上空间比方案1更加小

然而方案2,存在了漏数据的风险,这是我们无法接受的,故排除方案2

网上关于错误率是否可以接受的一些例子:

很多时候这个错误率我们是能接受的

  • 譬如垃圾邮箱问题，是坏人一定会被抓，这个能保证。无非是一些好人也被抓，这个可以通过给这些可伶的被误伤的设置个白名单就OK。
  • 至于爬虫Url重复这个就更没问题了，会缺掉一些网页而已。
  • 至于在缓存穿透上的应用，是为了避免恶意用户频繁请求缓存中不存在DB也不存在的值，会导致缓存失效、DB负载过大，可以使用BloomFilter把所有数据放到bit数组中，当用户请求时存在的值肯定能放行，部分不存在的值也会被放行，绝大部分会被拦截，这些少量漏网之鱼对于DB的影响就会比大量穿透好的多了。

技术方案中 使用布隆过滤器-的案例:

  • Google 的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列，以减少磁盘查找的IO次数。
  • Squid 网页代理缓存服务器在 cache digests 中使用了也布隆过滤器。
  • Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。
  • SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。
  • Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。
  • Google Guava – 使用bloom过滤器判断是否存在该行（rows）或（colums），以减少对磁盘的访问，提高数据库的访问性能
  • Apache的HBase – 使用bloom过滤器判断是否存在该行（rows）或（colums），以减少对磁盘的访问，提高数据库的访问性能
  • Apache_Cassandra – 使用bloom过滤器判断是否存在该行（rows）或（colums），以减少对磁盘的访问，提高数据库的访问性能
  • 比特币 – 使用布隆过滤判断钱包是否同步OK

主要是针对不存在的,进行短路操作,避免无效的查询

版权声明：本文为victor2302原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/victor2302/p/13128394.html