开发者社区> 王小明hit> 正文

布隆过滤器原理

简介: 布隆过滤器原理
+关注继续查看

布隆过滤器



布隆过滤器拥有极高的性能,无论是写入操作还是读取操作,时间复杂度是O(1)。

在空间上相对于其他数据结构,有很大优势, 20亿的数据需要 2000000000bit/8/1024/1024 = 238 M ,如果使用数组来存储,假设每个用户 ID 占用 4个字节的空间,存储20亿用户需要 2000000000byte/4/8/1024/1024 = 7600M 的空间,是布隆过滤器的32倍。


布隆过滤器(Bloom Filter)


640.png


hash  函数



640.png


布隆过滤器的缺点


  1. 在判断元素是否在集合中有一定的错误几率,会误判,把不是在集合中的元素判断为处在集合中。
  2. 不支持删除元素


布隆过滤器误判是怎么回事?


hash 算法也叫做 摘要算法,作用是对任意一组数据输入,得到一个固定长度的输出摘要。

误判的原因,主要是Hash算法的问题。布隆过滤器是由于一个二进制和一个 Hash 算法组成的,Hash 算法存在着一定的碰撞几率。Hash 碰撞的含义是不同的输入值经过 hash 得到相同的 hash 结果。


hash 算法的输入值是无限的,输出值空间是固定的,比如 16位 hash 值的之空间是 65535 这样碰撞几率就是 1/65535 ,即输入值的个数超过 65535 就一定会发生碰撞。

但是,如果使用更长的 hash 值会带来更高的存储成本和计算成本,32 位的 hash 算法,值空间长度是 2^32-1 大概 42亿,如果有 20亿用户数据,碰撞的概率高达 50%。hash 碰撞造成两个用户,A 和 B 会计算出相同的两个 hash 值,如果A 是注册用户,B不是注册用户, 但是 A 和 B 在的的数组中是相同的,然后产生误判。

布隆过滤器的误判有一个特点,只会出现 false positive 的情况,当布隆过滤器判断元素在集合中,这个元素可能不在集合中,但是布隆过滤器判断这个元素不在集合时,它一定不在集合中,这一点非常适合解决缓存穿透的问题。

布隆过滤器有一个可预测的误判率(FPP):


640.png



  • n 是已经添加元素的数量;
  • k 哈希的次数;
  • m 布隆过滤器的长度(如比特数组的大小);


怎么减少这个误判几率


布隆过滤器存在误判,但是依然可以减少缓存穿透的发,但是为了尽量减少误判,可以使用如下解决方案:

使用多个 hash 算法为元素计算出多个 Hash 值,只有所有的hash 值对应的数组都为1个小时,才会认定这个元素在集合中。


布隆过滤器不支持删除元素的缺点也合 Hash 碰撞有关


有这样的场景,A 和 B 都是集合中的元素,他没有相同的 hash 值,会映射到数组同一个位置,但是如果此时上次了A,数组中对应位置从1 编程0 ,但是判断 B 时,会发现值是0 ,认为 B 不存在集合中。这样产生误判。

解决这个问题,一般有这样的解决方案:

数组上不再是1 和 0 两个值,而是存储一个计数,如果 A  和 B 命中同一个位置 值就是 2 ,如果 A 删除就把这个值改成1,但是这样数组就不存在 1bit ,而是存储数值,会增加空间的消耗。


布隆过滤器使用


  1. 选择多个 Hash 函数计算多个 hash 值,可以减少误判
  2. 布隆过滤器会消耗一定的内存空间,所以在使用时需要评估业务场景需要多大的内存消耗。

如果出现了一个极热数据,一旦失效,会有大量数据穿透到数据库。给数据库造成极大压力。


如何解决热点数据失效问题


极热数据缓存失效,也叫"狗壮效应"

  1. 热点数据失效后启动一个线程,将数据加载到缓存中,在缓存数据加载前,所有访问的请求都不穿透数据库直接返回。
  2. 通过 Redis 设置分布式锁,只有获得锁,才能够穿透到数据库。


布隆过滤器使用


pom.xml 依赖


<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>28.0-jre</version>
</dependency>

Java 代码


import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterDemo {
    public static void main(String[] args) {
        int total = 1000000; // 总数量
        BloomFilter<CharSequence> bf = 
          BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
        // 初始化 1000000 条数据到过滤器中
        for (int i = 0; i < total; i++) {
            bf.put("" + i);
        }
        // 判断值是否存在过滤器中
        int count = 0;
        for (int i = 0; i < total + 10000; i++) {
            if (bf.mightContain("" + i)) {
                count++;
            }
        }
        System.out.println("已匹配数量 " + count);
    }
}

总结


布隆过滤器可以一定程度上解决缓存穿透的问题,解决缓存穿透的问题核心是减少数据库的并发访问。由于 hash 碰撞的原因,布隆过滤器存在一定的误判几率,也存在不支持删除元素的问题。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
20719 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
30124 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
23008 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
17261 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
21208 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23629 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14926 0
+关注
227
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载