【算法】BloomFilter概念和原理以及业务中的应用场景

举报
互联网小阿祥 发表于 2023/05/31 21:12:58 2023/05/31
【摘要】 BloomFilter概念和原理以及业务中的应用场景
思考:海量数据下去重,如果是非数值类型的话如何判断?

1.什么是布隆过滤器

  • 1970年由布隆提出的一种空间效率很高的概率型数据结构,它可以用于检索一个元素是否在一个集合中。

  • 由只存0或1的位数组和多个hash算法, 进行判断数据 【一定不存在或者可能存在的算法】。

  • 如果这些bit数组 有任何一个0,则被判定的元素一定不在; 如果都是1则被检元素很可能在

  • 对比bitmap位图,布隆过滤器适合更多类型元素,通过hash值转换

在这里插入图片描述

  • 原理

    • 将元素添加到一个bitmap数组中,每个散列函数将元素映射到bitmap数组中的一个位置

    • 如果该位置已经被占用,则将该位置置为1,否则置为0

    • 当要查询一个元素是否存在时,只需要计算该元素的散列值,并检查bitmap数组中对应的位置是否已经被置为1

    • 如果都是1,则该元素可能存在,否则肯定不存在。

    • 优点

      • 占用空间小,查询速度快,空间效率和查询时间都远远超过一般的算法
    • 缺点

      • 有一定的误识别率,有一定的误识别率,即某个元素可能存在,但实际上并不存在。
      • 删除困难,因为无法确定某个位置是由哪个元素映射而来的
  • 案例测试地址:https://www.jasondavies.com/bloomfilter/

在这里插入图片描述
在这里插入图片描述

  • 记住结论:不存在的一定不存在,存在的不一定存在

  • 注意点

    • 布隆过滤器存在误判率,数组越小,所占的空间越小,误判率越高;如果要降低误判率,则数组越长,但所占空间越大

    • 最大限度的避免误差, 选取的位数组应尽量大, hash函数的个数尽量多, 但空间占用的浪费和性能的下降

    • 业务选择的时候, 需要误判率与bit数组长度和hash函数数量的平衡

    • 布隆过滤器不能直接删除元素,因为所属的bit可能多个元素有使用

    • 如果要删除则需要重新生成布隆过滤器,或者把布隆过滤器改造成带引用计数的方式

  • 如何解决布隆过滤器不支持删除的问题

    • Counting Bloom Filter将标准 Bloom Filter位数组的每一位扩展为一个小的计数器(counter),在插入元素时给对应的k(k为哈希函数个数)个Counter的值分别加1,删除元素时给对应的k个Counter的值分别减1。Counting Bloom Filter通过多占用几倍的存储空间的代价,给Bloom Filter增加了删除操作。

在这里插入图片描述

2.BloomFilter业务中的应用场景

(1)海量数据下垃圾邮件解决方案(垃圾短信、黑名单同理)

  • 收集一组具有特定特征的垃圾邮件样本,这些样本可以是文本内容或其他特征,比如发件人、收件人等
  • 将这些样本的特征信息进行哈希处理,并将处理后的结果存储在布隆过滤器中。
  • 接下来,当有新的电子邮件到达时,将该邮件的特征信息也进行哈希处理,并且与布隆过滤器中的信息进行比较
  • 如果布隆过滤器中存在该邮件的特征信息,则判断该邮件为垃圾邮件;如果不存在,则判断该邮件为正常邮件

在这里插入图片描述

(2)解决缓存穿透解决方案

  • 什么是缓存穿透(查询不存在数据)
    • 查询一个不存在的数据,由于缓存是不命中的,如发起为id为“-1”不存在的数据
    • 如果从存储层查不到数据则不写入缓存,导致这个不存在的数据每次请求都要到存储层去查询,
    • 大量查询不存在的数据,可能DB就挂掉了,是黑客利用不存在的key频繁攻击应用的一种方式
  • 将所有要【缓存的数据】经过处理后存储布隆过滤器中,即对应的bit上是1
  • 当外部请求发起时,首先会把请求的参数 通过哈希算法处理,获得相应的哈希值;
  • 根据哈希值计算出位数组中的位置,如果全部计算的hash值对于的bit存储都是1
  • 则表示数据在合理中,从缓存读出(缓存失效则从数据库中取出)
  • 如果计算的hash值对于的bit存储存在一个是0或以上,则表示这条数据不合理,直接返回数据不存在,不查缓存和数据库
  • 如果布隆过滤器认为值不存在,那么值一定是不存在的,无需查询缓存也无需查询数据库

在这里插入图片描述

(3)爬虫URL去重和分库分表注册手机号唯一性解决方案

大量的网页爬取,通过解析已经爬取页面中的网页链接,然后再爬取这些链接对应的网页
同一个网页链接有可能被包含在多个页面中,会导致爬虫在爬取的过程中,重复爬取相同的网页
  • 创建布隆过滤器,根据业务数据量设置位数组的大小,将位数组全部设置为0;
  • 将每个URL地址通过哈希算法处理,获得相应的哈希值;
  • 根据哈希值计算出位数组中的位置,将位数组中的位置设置为1;
  • 当新的URL地址进入时,重复上述步骤计算出对应的位置
  • 检查位数组中的位置是否为0,如果是0,则表示该URL地址一定没被爬取过;
  • 如果URL地址不存在,经过爬虫处理后,则将其对应的位置设置为1,以表示该URL地址已经存在;
  • 重复上述步骤,直到所有的URL地址都处理完毕,完成去重。
  • 具体的SpringBoot整合案例请看我的另外一篇文章:【案例实战】爬虫URL去重实战-SpringBoot2.x+Guava布隆过滤器

在这里插入图片描述

(4)海量数据下-分库分表下手机号重复注册解决方案

  • 一般业务里面的partitionKey是不可变动的,所以不能用手机号作为分片键(换手机号需求是存在的)
  • 所以业务里面的分片键,多数是固定的业务id,比如user_id

在这里插入图片描述

  • 创建布隆过滤器,根据业务数据量设置位数组的大小,将位数组全部设置为0;

  • 把要注册的手机号通过通过哈希算法处理,获得相应的哈希值;

  • 根据哈希值计算出位数组中的位置,如果对应的位数组中的位置有存在0,则一定是未注册的

  • 如果经过多个hash函数处理,对应的位数组中都是1,则认为是注册过的

  • 最后如果用户注册成功后,将位数组中的位置设置为1

  • 根据哈希值计算出位数组中的位置,如果对应的位数组中的位置有存在0,则一定是未注册的

  • 如果经过多个hash函数处理,对应的位数组中都是1,则认为是注册过的

  • 最后如果用户注册成功后,将位数组中的位置设置为1

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。