Redis实现布隆过滤器的方法及原理

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

本文将介绍布隆过滤器的原理以及Redis如何实现布隆过滤器。

应用场景

1、50亿个电话号码，现有10万个电话号码，如何判断这10万个是否已经存在在50亿个之中？（可能方案：数据库，set, hyperloglog）
2、新闻客户端看新闻时，它会不断推荐新的内容，每次推荐时都要去重，那么如何实现推送去重？
3、爬虫URL去重？
4、NoSQL数据库领域降低数据库的IO请求数量？
5、邮箱系统的垃圾邮件过滤？

布隆过滤器（Bloom Filter）就是专门来解决这种问题的，它起到去重的同时，在空间上还能节省90%以上，只是存在一定的误判概率。

认识布隆过滤器

布隆过滤器是一种类似set的数据结构，只是不太准确，当用bf.exists判断元素是否存在时返回结果存在但真实不一定存在；当返回不存在时肯定是不存在，所以判断去重时有一定的误判概率。
当然，误判只会发生在过滤器没有添加过的元素，对于添加过的元素不会发生误判。
特点：高效地插入和查询，占用空间少，返回的结果是不确定性的。

布隆过滤器原理

每个布隆过滤器对应到Redis的数据结构中就是一个大型的位数组和几个不同的无偏hash函数，无偏表示分布均匀。

添加key时，使用多个hash函数对key进行hash运算得到一个整数索引值，对位数组长度进行取模运算得到一个位置，每个hash函数都会得到一个不同的位置，将这几个位置都置1就完成了add操作。

查询同理，只要有一位是0就表示这个key不存在，但如果都是1，则不一定存在对应的key。

空间占用估计

布隆过滤器的空间占用有一个简单的计算公式，但推导比较繁琐。布隆过滤器有两个参数，预计元素数量n，错误率f，公式得到两个输出，位数组长度L（即存储空间大小bit），hash函数的最佳数量k。

k = 0.7*(1/n)
f = 0.6185^(L/n)

1、位数组相对长度越长，错误率越低；
2、位数组相对长度越长，需要的hash函数越多；
3、当一个元素平均需要一个字节（8bit）的指纹空间时（L/n=8)，错误率大约为2%。

实际元素超出时，误判率会怎样变化？

f = (1-0.5^t)^k  # t为实际元素与预计元素的倍数
1、当错误率为10%时，倍数比为2时，错误率接近40%；
2、当错误率为1%，倍数比为2时，错误率15%；
3、当错误率为0.1%，倍数为2时，错误率5%

Redis实现简单Bloom Filter

要想使用redis提供的布隆过滤器，必须添加redis 4.0版本以上的插件才行，具体参照网上安装步骤。

布隆过滤器有两个基本指令，bf.add添加元素，bf.exists查询元素是否存在，bf.madd一次添加多个元素，bf.mexists一次查询多个元素。

> bf.add spiderurl www.baidu.com
> bf.exists spiderurl www.baidu.com
> bf.madd spiderurl www.sougou.com www.jd.com
> bf.mexists spiderurl www.jd.com www.taobao.com

布隆过滤器在第一次add的时候自动创建基于默认参数的过滤器，Redis还提供了自定义参数的布隆过滤器。

在add之前使用bf.reserve指令显式创建，其有3个参数，key，error_rate， initial_size，错误率越低，需要的空间越大，error_rate表示预计错误率，initial_size参数表示预计放入的元素数量，当实际数量超过这个值时，误判率会上升，所以需要提前设置一个较大的数值来避免超出。

默认的error_rate是0.01，initial_size是100。

利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求。

总结

以上所述是小编给大家介绍的Redis实现布隆过滤器的方法及原理，希望对大家有所帮助，如果大家有任何疑问欢迎给我留言，小编会及时回复大家的！

赞 (0)

相关推荐

  • Redis 中的布隆过滤器的实现

    什么是『布隆过滤器』 布隆过滤器是一个神奇的数据结构,可以用来判断一个元素是否在一个集合中.很常用的一个功能是用来去重.在爬虫中常见的一个需求:目标网站 URL 千千万,怎么判断某个 URL 爬虫是否宠幸过?简单点可以爬虫每采集过一个 URL,就把这个 URL 存入数据库中,每次一个新的 URL 过来就到数据库查询下是否访问过. select id from table where url = 'https://jaychen.cc' 但是随着爬虫爬过的 URL 越来越多,每次请求前都要访问数据

  • python实现布隆过滤器及原理解析

    在学习redis过程中提到一个缓存击穿的问题, 书中参考的解决方案之一是使用布隆过滤器, 那么就有必要来了解一下什么是布隆过滤器.在参考了许多博客之后, 写个总结记录一下. 一.布隆过滤器简介 什么是布隆过滤器? 本质上布隆过滤器( BloomFilter )是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 "某样东西一定不存在或者可能存在". 相比于传统的 Set.Map 等数据结构,它更高效

  • JAVA实现较完善的布隆过滤器的示例代码

    布隆过滤器是可以用于判断一个元素是不是在一个集合里,并且相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势.布隆过滤器存储空间和插入/查询时间都是常数.但是它也是拥有一定的缺点:布隆过滤器是有一定的误识别率以及删除困难的.本文中给出的布隆过滤器的实现,基本满足了日常使用所需要的功能. 0 0 0 0 0 0 0 0 0 0 先简单来说一下布隆过滤器.其实现方法就是:利用内存中一个长度为M的位数组B并初始化里面的所有位都为0,如下面的表格所示: 然后我们根据H个不同的散列函数,对传进来

  • Java实现布隆过滤器的方法步骤

    Java实现布隆过滤器的方法步骤

    前言 记得前段时间的文章么?redis使用位图法记录在线用户的状态,还是需要自己实现一个IM在线用户状态的记录,今天来讲讲另一方案,布隆过滤器 布隆过滤器的作用是加快判定一个元素是否在集合中出现的方法.因为其主要是过滤掉了大部分元素间的精确匹配,故称为过滤器. 布隆过滤器 在日常生活工作,我们会经常遇到这的场景,从一个Excel里面检索一个信息在不在Excel表中,还记得被CTRL+F支配的恐惧么,不扯了,软件开发中,一般会使用散列表来实现,Hash Table也叫哈希表,哈希表的优点是快速准确

  • Python+Redis实现布隆过滤器

    布隆过滤器是什么 布隆过滤器(Bloom Filter)是1970年由布隆提出的.它实际上是一个很长的二进制向量和一系列随机映射函数.布隆过滤器可以用于检索一个元素是否在一个集合中.它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难. 布隆过滤器的基本思想 通过一种叫作散列表(又叫哈希表,Hash table)的数据结构.它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点.这样一来,我们只要看看这个点是不是1就可以知道集合中有没

  • 布隆过滤器的概述及Python实现方法

    布隆过滤器 布隆过滤器是一种概率空间高效的数据结构.它与hashmap非常相似,用于检索一个元素是否在一个集合中.它在检索元素是否存在时,能很好地取舍空间使用率与误报比例.正是由于这个特性,它被称作概率性数据结构(probabilistic data structure). 空间效率 我们来仔细地看看它的空间效率.如果你想在集合中存储一系列的元素,有很多种不同的做法.你可以把数据存储在hashmap,随后在hashmap中检索元素是否存在,hashmap的插入和查询的效率都非常高.但是,由于ha

  • C++ 数据结构之布隆过滤器

    布隆过滤器 一.历史背景知识 布隆过滤器(Bloom Filter)是1970年由布隆提出的.它实际上是一个很长的二进制向量和一系列随机映射函数.布隆过滤器可以用于检索一个元素是否在一个集合中.它的优点是空间效率和查询时间都远超过一般的算法,缺点是有一定的误识别率和删除错误.而这个缺点是不可避免的.但是绝对不会出现识别错误的情况出现(即假反例False negatives,如果某个元素确实没有在该集合中,那么Bloom Filter 是不会报告该元素存在集合中的,所以不会漏报) 在 FBI,一个

  • 布隆过滤器(Bloom Filter)的Java实现方法

    布隆过滤器原理很简单:就是把一个字符串哈希成一个整数key,然后选取一个很长的比特序列,开始都是0,在key把此位置的0变为1:下次进来一个字符串,哈希之后的值key,如果在此比特位上的值也是1,那么就说明这个字符串存在了. 如果按照上面的做法,那就和哈希算法没有什么区别了,哈希算法还有重复的呢. 布隆过滤器是将一个字符串哈希成多个key,我还是按照书上的说吧. 先建立一个16亿二进制常量,然后将这16亿个二进制位全部置0.对于每个字符串,用8个不同的随机产生器(F1,F2,.....,F8)产

  • Redis实现布隆过滤器的方法及原理

    布隆过滤器(Bloom Filter)是1970年由布隆提出的.它实际上是一个很长的二进制向量和一系列随机映射函数.布隆过滤器可以用于检索一个元素是否在一个集合中.它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难. 本文将介绍布隆过滤器的原理以及Redis如何实现布隆过滤器. 应用场景 1.50亿个电话号码,现有10万个电话号码,如何判断这10万个是否已经存在在50亿个之中?(可能方案:数据库,set, hyperloglog) 2.新闻客户端看新闻时,它会不

  • 布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法

    布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法

    引言 在介绍布隆过滤器之前我们首先引入几个场景. 场景一 在一个高并发的计数系统中,如果一个key没有计数,此时我们应该返回0,但是访问的key不存在,相当于每次访问缓存都不起作用了.那么如何避免频繁访问数量为0的key而导致的缓存被击穿? 有人说, 将这个key的值置为0存入缓存不就行了吗?确实,这是一个好的方案.大部分情况我们都是这样做的,当访问一个不存在的key的时候,设置一个带有过期时间的标志,然后放入缓存.不过这样做的缺点也很明显,浪费内存和无法抵御随机key攻击. 场景二 在一个黑名

  • Redis BloomFilter布隆过滤器原理与实现

    Redis BloomFilter布隆过滤器原理与实现

    目录 Bloom Filter 概念 Bloom Filter 原理 缓存穿透 Bloom Filter的缺点 常见问题 go语言实现 Bloom Filter 概念 布隆过滤器(英语:Bloom Filter)是1970年由一个叫布隆的小伙子提出的.它实际上是一个很长的二进制向量和一系列随机映射函数.布隆过滤器可以用于检索一个元素是否在一个集合中.它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难. Bloom Filter 原理 布隆过滤器的原理是,当一个元素

  • SpringBoot+Redis实现布隆过滤器的示例代码

    目录 简述 Redis安装BloomFilter 基本指令 结合SpingBoot 方式一 方式二 简述 关于布隆过滤器的详细介绍,我在这里就不再赘述一遍了 我们首先知道:BloomFilter使用长度为m bit的字节数组,使用k个hash函数,增加一个元素: 通过k次hash将元素映射到字节数组中k个位置中,并设置对应位置的字节为1.查询元素是否存在: 将元素k次hash得到k个位置,如果对应k个位置的bit是1则认为存在,反之则认为不存在. Guava 中已经有具体的实现,而在我们实际生产

  • C++详细讲解模拟实现位图和布隆过滤器的方法

    C++详细讲解模拟实现位图和布隆过滤器的方法

    目录 位图 引论 概念 解决引论 位图的模拟实现 铺垫 结构 构造函数 存储 set,reset,test flip,size,count any,none,all 重载流运算符 测试 位图简单应用 位图代码汇总 布隆过滤器 引论 要点 代码实现 效率 解决方法 位图 引论 四十亿个无符号整数,现在给你一个无符号整数,判断这个数是否在这四十亿个数中. 路人甲:简单,快排+二分. 可是存储这四十亿个整数需要多少空间? 简单算一下,1G=1024M=1024 * 1024KB=1024 * 1024

  • Redis中Redisson布隆过滤器的学习

    目录 简介 使用 Demo 依赖 测试代码 简析 初始化 添加元素 检索元素 简介 本文基于Spring Boot 2.6.6.redisson 3.16.0简单分析Redisson布隆过滤器的使用. 布隆过滤器是一个非常长的二进制向量和一系列随机哈希函数的组合,可用于检索一个元素是否存在: 使用场景如下: 解决Redis缓存穿透问题: 邮件过滤: 使用 建立一个二进制向量,所有位设置0: 选择K个散列函数,用于对元素进行K次散列,计算向量的位下标: 添加元素:将K个散列函数作用于该元素,生成K

  • Redis 布隆过滤器命令的使用详解

    Redis 布隆过滤器命令的使用详解

    目录 一.Docker 安装 Redis 布隆过滤器 学习历史重要原因之一,就是要学会感恩,因为我们都是站在巨人的肩膀上. 1.1.安装 注意: 1.2.测试 二.RedisBloom 命令讲解 2.1.命令大纲 2.2.BF.ADD 和 BF.MADD 2.3.BF.EXISTS 和 BF.MEXISTS 2.4.BF.INFO 2.5.BF.RESERVE 2.6.BF.INSERT 因为平常使用 Docker 比较多,所以照常还是使用Docker来准备环境啦. 一.Docker 安装 Re

随机推荐