精华内容
下载资源
问答
  • 布隆过滤器原理

    2020-09-22 18:24:56
    布隆过滤器原理 布隆过滤器原理 开发一个电商项目,因为数据量一直在增加(已达亿级),所以需要重构之前开发好的秒杀功能,为了更好的支持高并发,在验证用户是否重复购买的环节,就考虑用布隆过滤器。 也顺便...
     
    

    布隆过滤器原理

    开发一个电商项目,因为数据量一直在增加(已达亿级),所以需要重构之前开发好的秒杀功能,为了更好的支持高并发,在验证用户是否重复购买的环节,就考虑用布隆过滤器。

    也顺便更加深入的去了解下布隆过滤器的原理,感觉还是蛮有意思的,这一连串的公式不静下心来思考,很容易被绕晕。

    一、概述

    1、什么是布隆过滤器

    本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构,特点是高效地插入和查询。根据查询结果可以用来告诉你 某样东西一定不存在或者可能存在 这句话是该算法的核心。

    相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的,同时布隆过滤器还有一个缺陷就是

    数据只能插入不能删除

    2、数据如何存入布隆过滤器

    布隆过滤器是由一个很长的bit数组和一系列哈希函数组成的

    数组的每个元素都只占1bit空间,并且每个元素只能为0或1。

    布隆过滤器还拥有k个哈希函数,当一个元素加入布隆过滤器时,会使用k个哈希函数对其进行k次计算,得到k个哈希值,并且根据得到的哈希值,在维数组中把对应下标的值置位1。

    判断某个数是否在布隆过滤器中,就对该元素进行k次哈希计算,得到的值在位数组中判断每个元素是否都为1,如果每个元素都为1,就说明这个值在布隆过滤器中。

    3、布隆过滤器为什么会有误判

    当插入的元素越来越多时,当一个不在布隆过滤器中的元素,经过同样规则的哈希计算之后,得到的值在位数组中查询,有可能这些位置因为其他的元素先被置1了。

    所以布隆过滤器存在误判的情况,但是如果布隆过滤器判断某个元素不在布隆过滤器中,那么这个值就一定不在

    如果对布隆过滤器的概念还不是很理解的话,推荐一篇博客,图文并茂好理解很多。详解布隆过滤器的原理、使用场景和注意事项

    4、使用场景

    • 网页爬虫对URL的去重,避免爬去相同的URL地址。
    • 垃圾邮件过滤,从数十亿个垃圾邮件列表中判断某邮箱是否是杀垃圾邮箱。
    • 解决数据库缓存击穿,黑客攻击服务器时,会构建大量不存在于缓存中的key向服务器发起请求,在数据量足够大的时候,频繁的数据库查询会导致挂机。
    • 秒杀系统,查看用户是否重复购买。

    二、实际应用场景

    背景 现在有个100亿个黑名单网页数据,每个网页的URL占用64字节。现在想要实现一种网页过滤系统,可以根据网页的URL判断该网站是否在黑名单上,请设计该系统。

    需求可以允许有0.01%以下的判断失误率,并且使用的总空间不要超过200G。

    这里一共有4个常量:

    100亿条黑名单数据每条数据占64个字节,万分之一的失误率总空间不要超过200G

    如果不考虑不拢过滤器,那么这里存储100亿条数据就需要 100亿 * 64字节 = 596G 显然超过300G

    解题 在满足有 100亿条数据 并且允许 万分之一的失误率 的布隆过滤器需要多大的bit数组呢?

    • 设bit数组大小为m,样本数量为n,失误率为p。
    • 由题可知 n = 100亿,p = 0.01%

    布隆过滤器的大小m公式

    ![在这里插入图片描述](https://img-blog.csdnimg.cn/img_convert/a591f51eab30461fd7489774b50eb21c.png#pic_center)

    求得 m = 19.19n,向上取整为 20n。所以2000亿bit,约为186G。

    算完m,我们顺便来算下m,n已知,这时满足最小误差的k是几个。

    哈希函数的个数k公式

    ![在这里插入图片描述](https://img-blog.csdnimg.cn/img_convert/de9f7deaf1c86cd928191444e0d47ea0.png#pic_center)

    求得 k = 14,即需要14个哈希函数。

    通过通过 m = 20n, k = 14我们再来算下真实的失误率。

    布隆过滤器真实失误率p公式

    ![在这里插入图片描述](https://img-blog.csdnimg.cn/img_convert/966748d5d49fe41241d881df2f1c00a3.png#pic_center)

    求得 p = 0.006%,即布隆过滤器的真实失误率为0.006%。

    通过布隆过滤器公式也可以看出:

    单个数据的大小不影响布隆过滤器大小,因为样本会通过哈希函数得到输出值

    就好比上面的 每个网页的URL占用64字节 这个数据大小 跟布隆过滤器大小没啥关系。

    这三个公式就是有关布隆过滤器已经推倒出的公式,下面我们来推下这个公式是如何推导出来的。


    三、公式推导

    讲公式,应该先知道几个关键的常量。

    误判率p布隆过滤器长度m元素个数n哈希函数个数k

    我们再来一步一步由简单到难推导公式。

    1、误差率公式推导

    前提条件:就是假设每个元素哈希得到的值分布到m数组上的每一个数组节点的概率是相等的。

    1) 假设布隆过滤器长度为m,元素个数n为1,哈希函数个数k也为1。那么在插入时某一数组节点没有被置为1的概率。

    ![在这里插入图片描述](https://img-blog.csdnimg.cn/img_convert/278eeee95b072d78d61af749c4a1cc35.png#pic_center)

    这个应该很好理解。

    2)如果上面其它不变,而哈希函数个数变成k个,那么在插入时某一数组节点没有被置为1的概率。

    在这里插入图片描述

    好理解!

    3)如果元素个数变成n个,而哈希函数个数变成k个,那么在插入时某一数组节点没有被置为1的概率。

    在这里插入图片描述

    4)从上面推导出的是: 当布隆过滤器长度为m,元素个数变成n个,哈希函数个数变成k个的时候,某一节点被置为1的概率为

    在这里插入图片描述

    到这里应该也好理解,第三步是该位置从未被置为1,那么1去减去它就是至少有一次被置为1,那么只要存在一次被置1,那么该位置的bit标示就是1,因为布隆过滤器是不能删除的。

    5)这个还需要考虑到,一个元素通过hash会生成多个k,放入m数组中,所以需要这k个值都为1才会认为该该元素已经存在。所以是这样的。

    ![在这里插入图片描述](https://img-blog.csdnimg.cn/img_convert/752e66a0eb6f8963d2d57a36c29a1394.png#pic_center)

    上面这个公式推导在转换下就成了

    ![在这里插入图片描述](https://img-blog.csdnimg.cn/img_convert/3e92455eceb4dff9baaedd468c1ea263.png#pic_center)

    思考 为什么上面这个公式的值就是最终的误差率?

    因为当一个布隆过滤器中不存在的元素进来的是的时候,首先通过hash算法产生k个哈希值,分布在m数组上都为1的的概率不就是上面推导出的这个公式吗,那不就是误差吗?

    因为明明是不存在的值,却有这个概率表明已经存在。

    思考 给定的m和n,思考k值为多少误差会最小

    为什么k值的大小不合理会影响误差呢?

    我们来思考下,一个元素最终生成k个hash值,那么会在数组m上的k个位置标记为1。

    假设k为1,那么每次进来只在m上的某一个位置标记为1,这样的话如果一个新元素进来刚好hash值也在这里,而不用其它位置来判断是否为1,这个误差就会比较大

    假设k为m,那么第一个元素进来,在m上所有位置上都表为1了 ,以后只要进来一个元素就会标记为已存在。这个误差也太大了

    上面只是举了两个极端的例子,但也说明k值太大、太小都不好,它的最优值一定跟m、n存在某种关系。

    至于完整公式的推导,我这里就不在写了,后面会贴一个人家怎么推导的博客。

    它们之间的关系只要记住下面这个公式就可以了。

    在这里插入图片描述

    这篇博客就到这里了,后面有整理通过谷歌的guava工具 和 redis 实现布隆过滤器的示例。通过Lua脚本批量插入数据到Redis布隆过滤器


    参考

    1、详解布隆过滤器的原理,使用场景和注意事项

    2、布隆过滤器概念及其公式推导

    3、说一说布隆过滤器



    展开全文
  • 布隆过滤器原理及实现 前言 最近有朋友面试经常被问到redis缓存穿透怎么解决,什么是redis缓存穿透呢?就是客户端去访问一个缓存和数据库都不存在的 key这样的查询直接打到数据库上。解决办法很多。 1接口参数校验,...

    布隆过滤器原理及实现

    前言
    最近有朋友面试经常被问到redis缓存穿透怎么解决,什么是redis缓存穿透呢?就是客户端去访问一个缓存和数据库都不存在的 key这样的查询直接打到数据库上。解决办法很多。
    1接口参数校验,
    2在缓存中设置空值,
    3布隆过滤器。

    本章咱们就来看下布隆过滤器怎么解决的

    什么是布隆过滤器
    布隆过滤器可以快速的从海量中数据校验一个数据是否存在。
    它内部结构由多个hash函数和一组bit数组成
    每个bit位置默认是0
    下面请看图

    在这里插入图片描述
    实现过程
    1、把所有数据的位置信息添加到bit数组

    每条数据经过hash函数运算,有几个函数就计算几次,
    每次计算都会算出对应的位置信息,然后把该位置由0置为1,

    2、校验单个数据是否存在布隆过滤器里
    跟添加位置信息一样经过多个函数算出对应的值信息
    如果每个位置信息都是1则布隆过滤器判断该数据存在
    如果都为0或者有一个位置信息为0则判断数据不存在

    优势:
    1、仅仅保留保留数据的位置信息,空间效率极高
    2、信息安全性较高,不能根据位置信息反算出来数据
    3、查询效率极高,时间复杂度0(n)
    缺点:
    存在一定的误判:当一个不存在的数据经过hash运算算出的位置信息 都是1的时候,这时候就发生了hash冲突,布隆过滤器就会误判,hash冲突我们无法避免,所以误判无法避免,hash函数越多误判率越低,这个误判率我们可以手动配置,但是记住一点误判率越低bit数组越大,hash函数越多相应的性能就会降低。
    数据删除困难:当我们要删除一个数据的时候不能仅把他对应的位置置为0,因为该位置可能还是别的数据的位置信息。所以不能物理删除。

    看到这里,可能会有人问既然布隆过滤器没办法避免误判率,那么我们为什么要用它或者什么时候要用它呢?
    它只会误判不存在的数据,不会误判存在的数据
    首先回到我们前言说的redis缓存穿透的问题,当有人恶意攻击你的服务器缓存,每秒上万的用不存在的k来访问我们缓存时候,我们在缓存前面加上布隆过滤器,当有真实存在的数据一定不会误判,这样经过布隆过滤器后可能只有很少的非法数据访问到我们的服务器,服务器也可以承受。

    经典应用场景
    1、字处理软件,需要检查一个英语单词是否正确
    2、网站非法url过滤
    3、订单物流单号查询
    4、FBI,查询一个嫌疑人是否存在嫌疑名单上

    最后来下看demo

    所需依赖

      <dependency>
                <groupId>com.google.guava</groupId>
                <artifactId>guava</artifactId>
                <version>21.0</version>
       </dependency>
    
    

    代码实现

    package com.teamer.servicetm.controller;
    
    
    import com.google.common.base.Charsets;
    import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnels;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.UUID;
    
    
    public class BloomFilterTest {
    
        private static  final int num=1000000;
    
    
        public static void main(String[] args) {
    
    
            /**
             创建一个存储string的布隆过滤器,初始化大小为num,默认误判率为0.03,如果我们想把误判率可以这样写
                BloomFilter<String> bloomFilter=BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),num,0.01D);
    
            */
          
            BloomFilter<String> bloomFilter=BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),num);
            //创建两个list容器 用来验证过滤器、以及他的误判率
            List<String> list=new ArrayList<>(num);
            List<String> list1=new ArrayList<>(num);
    
            for(int i=0;i<num;i++){
                String uuid= UUID.randomUUID().toString();
                bloomFilter.put(uuid);
                list.add(uuid);
                list1.add(uuid);
            }
            int nums=0;
            int trueNum=0;//正确的个数
            int wrongNum=0;//错误的个数
    
            for(int i=0;i<10000;i++){
                String str=i%100==0?list.get(i):UUID.randomUUID().toString();
                //布隆过滤器判断如果为true证明布隆过滤器认为存在
                if(bloomFilter.mightContain(str)){
                    nums++;
                    //再用list1判断下如果list1也认为存在则证明布隆过滤器判断正确,反之判断错误
                    if(list1.contains(str)){
                        trueNum++;
                    }else{
                        wrongNum++;
                    }
                }
            }
            System.out.println("布隆过滤器校验的个数为"+nums);
            System.out.println("正确的个数为"+trueNum);
            System.out.println("误判的个数为"+wrongNum);
        }
    }
    
    

    这里只是讲下大致原理过程,真正实现时候我们要多个线程去一块初始化数据,需要用到线程池化技术、锁(因为布隆过滤器是线程不安全的)、线程协作等。有兴趣的可以了解下Fork/Join。

    展开全文
  • 什么是布隆过滤器 本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。 相比于传统的 List...

    什么是布隆过滤器

    本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。

    相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的。

    布隆过滤器可以做什么

    上面说了布隆过滤器可以告诉你某个东西一定不存在和可能存在
    一定不存在?很多的使用都是利用布隆过滤器一定不存在的这个特性来进行的。
    HashMap当然这种功能也可以使用HashMap来完成,但是在数据量很小的情况下是可行的,在海量数据下,就不能支撑了,就得靠这篇博客里的主角布隆过滤器

    缓存问题

    在项目中肯定会使用到缓存,就以redis为例,当前端发送大量恶意请求的时候,导致查不到redis缓存,然后请求就到了数据库,把数据库干崩了,也是我们常说的redis的穿透,这种情况下布隆过滤器就是一个很好的选择。
    其实只要是遇到符合布隆过滤器特性的就可以使用它

    布隆过滤器原理

    布隆过滤器是一个叫“布隆”的人提出的,它本身是一个很长的二进制向量,既然是二进制的向量,那么显而易见的,存放的不是0,就是1。

    现在我们新建一个长度为16的布隆过滤器,默认值都是0,就像下面这样:
    在这里插入图片描述
    现在需要添加一个数据:

    我们通过某种计算方式,比如Hash1,计算出了Hash1(数据)=5,我们就把下标为5的格子改成1,就像下面这样:

    在这里插入图片描述
    我们又通过某种计算方式,比如Hash2,计算出了Hash2(数据)=9,我们就把下标为9的格子改成1,就像下面这样:
    在这里插入图片描述
    还是通过某种计算方式,比如Hash3,计算出了Hash3(数据)=2,我们就把下标为2的格子改成1,就像下面这样:
    在这里插入图片描述

    根据hash函数将数据映射到了布隆过滤器里面

    现在进来一个和上面不一样的数据,想要判断和上面存储的数据是否一致,这个不一样的数据也经过这几个hash函数映射在布隆过滤器里,假如和第一个数据映射的一样,就证明可能这俩个数据一致。假如不一致就证明这个数据再没加进来之前一定不存在。

    为什么可能俩数据一致呢?
    因为数据结果hash函数计算过后映射到布隆过滤器后,还可能另外一种情况就是有另外一个数据和上面数据虽然不是一致的,但是通过hash函数计算后映射的是一样的

    所以就是可以根据映射的地址判断进来的这个数据是否在布隆过滤器中一定存在,但是不能判断他一定存在

    布隆过滤器的优缺点

    优点:

    由于存放的不是完整的数据,所以占用的内存很少,而且新增,查询速度够快;

    缺点:

    随着数据的增加,误判率随之增加;无法做到删除数据;只能判断数据是否一定不存在,而无法判断数据是否一定存在。

    总结

    在真实开发中肯定不能使用二进制长度16的布隆过滤器,因为数据的增多肯定会导致误判率的增大,为了尽量避免这种情况,我们可以增多计算函数,还可以给布隆过滤器更长的二进制量

    参考链接:
    https://www.jianshu.com/p/2104d11ee0a2
    https://www.cnblogs.com/CodeBear/p/10911177.html

    展开全文
  • 布隆过滤器原理以及java/redis使用

    千次阅读 2020-08-05 17:55:30
    文章目录布隆过滤器布隆过滤器原理使用场景利用Google开源的 Guava中自带的布隆过滤器Redis 中的布隆过滤器使用Docker安装命令 布隆过滤器 布隆过滤器是用于判断一个元素是否在集合中。通过一个位数组和N个hash函数...

    布隆过滤器

    布隆过滤器是用于判断一个元素是否在集合中。通过一个位数组和N个hash函数实现。(某样东西一定不存在或者可能存在.)

    • 优点:
      • 空间效率高,所占空间小。
      • 查询时间短。
      • 自带去重
    • 缺点:
      • 元素添加到集合中后,不能被删除。
      • 有一定的误判率

    布谷鸟过滤器解决了布隆过滤器无法删除的问题

    布隆过滤器原理

    当一个元素加入布隆过滤器中的时候,会进行如下操作:

    1. 使用布隆过滤器中的哈希函数对元素值进行计算,得到哈希值(有几个哈希函数得到几个哈希值)。
    2. 根据得到的哈希值,在位数组中把对应下标的值置为 1。

    当我们需要判断一个元素是否存在于布隆过滤器的时候,会进行如下操作:

    1. 对给定元素再次进行相同的哈希计算;
    2. 得到值之后判断位数组中的每个元素是否都为 1,如果值都为 1,那么说明这个值可能在布隆过滤器中,如果存在一个值不为 1,说明该元素一定不在布隆过滤器中。

    使用场景

    • 大量数据中判断某个数据是否存在(用户是否阅读过某个文章):这就可以实现出上述的去重功能,如果你的服务器内存足够大的话,那么使用 HashMap 可能是一个不错的解决方案,理论上时间复杂度可以达到 O(1 的级别,但是当数据量起来之后,还是只能考虑布隆过滤器。
    • 解决缓存穿透:我们经常会把一些热点数据放在 Redis 中当作缓存,例如产品详情。 通常一个请求过来之后我们会先查询缓存,而不用直接读取数据库,这是提升性能最简单也是最普遍的做法,但是 如果一直请求一个不存在的缓存,那么此时一定不存在缓存,那就会有 大量请求直接打到数据库 上,造成 缓存穿透,布隆过滤器也可以用来解决此类问题。这时候可以用布隆过滤器当缓存的索引,只有在布隆过滤器中,才去查询缓存,如果没查询到,则穿透到db。如果不在布隆器中,则直接返回不进行缓存和db的查询。
    • 爬虫/ 邮箱等系统的过滤:平时不知道你有没有注意到有一些正常的邮件也会被放进垃圾邮件目录中,这就是使用布隆过滤器 误判 导致的。

    利用Google开源的 Guava中自带的布隆过滤器

            <dependency>
                <groupId>com.google.guava</groupId>
                <artifactId>guava</artifactId>
                <version>28.0-jre</version>
            </dependency>
    
            // 创建布隆过滤器对象,指定容量和容错率
            BloomFilter<Integer> filter = BloomFilter.create(
                    Funnels.integerFunnel(),
                    1500,
                    0.01);
            // 判断指定元素是否存在
            System.out.println(filter.mightContain(1));
            System.out.println(filter.mightContain(2));
            // 将元素添加进布隆过滤器
            filter.put(1);
            filter.put(2);
            System.out.println(filter.mightContain(1));
            System.out.println(filter.mightContain(2));
    

    Redis 中的布隆过滤器

    Redis v4.0 之后有了 Module(模块/插件) 功能,Redis Modules 让 Redis 可以使用外部模块扩展其功能 。布隆过滤器就是其中的 Module。

    使用Docker安装

    docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
    docker exec -it redis-redisbloom bash
    
    redis-cli
    

    命令

    • bf.add 添加元素到布隆过滤器,如果该过滤器尚不存在,则创建该过滤器。格式:BF.ADD {key} {item}
    • bf.exists 判断元素是否在布隆过滤器,格式:BF.EXISTS {key} {item}
    • bf.madd 添加多个元素到布隆过滤器,bf.add只能添加一个.格式:BF.MADD {key} {item} [item ...]
    • bf.mexists 判断多个元素是否在布隆过滤器.格式:BF.MEXISTS {key} {item} [item ...]
    • bf.reserve 创建布隆过滤器.格式:BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion]
      • key:布隆过滤器的名称
      • error_rate :误报的期望概率。这应该是介于0到1之间的十进制值。例如,对于期望的误报率0.1%(1000中为1),error_rate应该设置为0.001。该数字越接近零,则每个项目的内存消耗越大,并且每个操作的CPU使用率越高。
      • capacity: 过滤器的容量。当实际存储的元素个数超过这个值之后,性能将开始下降。实际的降级将取决于超出限制的程度。随着过滤器元素数量呈指数增长,性能将线性下降。
      • expansion:如果创建了一个新的子过滤器,则其大小将是当前过滤器的大小乘以expansion。默认扩展值为2。这意味着每个后续子过滤器将是前一个子过滤器的两倍。(子过滤器,但与初始化时容量合适的等效过滤器相比,它将消耗更多的内存和CPU)
    127.0.0.1:6379> BF.ADD myFilter java
    (integer) 1
    127.0.0.1:6379> BF.ADD myFilter javaguide
    (integer) 1
    127.0.0.1:6379> BF.EXISTS myFilter java
    (integer) 1
    127.0.0.1:6379> BF.EXISTS myFilter javaguide
    (integer) 1
    127.0.0.1:6379> BF.EXISTS myFilter github
    (integer) 0
    
    展开全文
  • 布隆过滤器是一种用来检索数据是否在大集合中的高效的、空间占用少的概率型数据结构,该数据结构由哈希函数以及位数组(二进制向量)来实现的,一般而言,布隆过滤器支持add 和 isExist 操作。 过滤器使用场景 1、布隆...
  • HBase布隆过滤器原理深度剖析1. 数据结构与原理1.1 初始化1.2 变量映射1.3 变量检索1.4 总结2. 过滤器特性2.1. 误判率2.2 判断特点3. 案列代码 1970年,布隆提出布隆过滤器(BloomFilter),用于判断一个元素是否不...
  • 布隆过滤器原理简介

    2020-06-25 21:58:10
    目录 1.布隆过滤器简介 2. 布隆过滤器的实现思路 ...相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的,同时布隆过滤器还有一个缺陷就是数据只..
  • 本文将带你快速了解布隆过滤器的核心思想,并通过Bloom Filter 模拟器带你快速弄懂这大名鼎鼎的布隆过滤器。 操作 基本的bloom过滤器支持两种操作:检测和添加。 检测用于检查给定元素是否在集合中。他只有两个返回...
  • 布隆过滤器原理和基于BloomFilter的误判率展示 布隆过滤器 布隆过滤器原理 布隆过滤器是由n个Hash函数和一个二进制数组组成。 如图所示(参考,hash函数可以多个) 1.保存操作 发来一个请求数据hello 对数据...
  • 算法(3)—布隆过滤器原理 开发一个电商项目,因为数据量一直在增加(已达亿级),所以需要重构之前开发好的秒杀功能,为了更好的支持高并发,在验证用户是否重复购买的环节,就考虑用布隆过滤器。 也顺便更加深入的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,566
精华内容 4,226
关键字:

布隆过滤器原理