Redis 中的布隆过滤器的实现

什么是『布隆过滤器』

布隆过滤器是一个神奇的数据结构，可以用来判断一个元素是否在一个集合中。很常用的一个功能是用来去重。在爬虫中常见的一个需求：目标网站 URL 千千万，怎么判断某个 URL 爬虫是否宠幸过？简单点可以爬虫每采集过一个 URL，就把这个 URL 存入数据库中，每次一个新的 URL 过来就到数据库查询下是否访问过。

select id from table where url = 'https://jaychen.cc'

但是随着爬虫爬过的 URL 越来越多，每次请求前都要访问数据库一次，并且对于这种字符串的 SQL 查询效率并不高。除了数据库之外，使用 Redis 的 set 结构也可以满足这个需求，并且性能优于数据库。但是 Redis 也存在一个问题：耗费过多的内存。这个时候布隆过滤器就很横的出场了：这个问题让我来。

相比于数据库和 Redis，使用布隆过滤器可以很好的避免性能和内存占用的问题。

布隆过滤器本质是一个位数组，位数组就是数组的每个元素都只占用 1 bit 。每个元素只能是 0 或者 1。这样申请一个 10000 个元素的位数组只占用 10000 / 8 = 1250 B 的空间。布隆过滤器除了一个位数组，还有 K 个哈希函数。当一个元素加入布隆过滤器中的时候，会进行如下操作：

  • 使用 K 个哈希函数对元素值进行 K 次计算，得到 K 个哈希值。
  • 根据得到的哈希值，在位数组中把对应下标的值置为 1。

举个🌰，假设布隆过滤器有 3 个哈希函数：f1, f2, f3 和一个位数组 arr。现在要把 https://jaychen.cc 插入布隆过滤器中：

  • 对值进行三次哈希计算，得到三个值 n1, n2, n3。
  • 把位数组中三个元素 arr[n1], arr[n2], arr[3] 置为 1。

当要判断一个值是否在布隆过滤器中，对元素再次进行哈希计算，得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。

看不懂文字看下面的灵魂画手的图解释👇👇👇

看了上面的说明，必然会提出一个问题：当插入的元素原来越多，位数组中被置为 1 的位置就越多，当一个不在布隆过滤器中的元素，经过哈希计算之后，得到的值在位数组中查询，有可能这些位置也都被置为 1。这样一个不存在布隆过滤器中的也有可能被误判成在布隆过滤器中。但是如果布隆过滤器判断说一个元素不在布隆过滤器中，那么这个值就一定不在布隆过滤器中。简单来说：

  • 布隆过滤器说某个元素在，可能会被误判。
  • 布隆过滤器说某个元素不在，那么一定不在。

这个布隆过滤器的缺陷放到上面爬虫的需求中，可能存在某些没有访问过的 URL 可能会被误判为访问过，但是如果是访问过的 URL 一定不会被误判为没访问过。

Redis 中的布隆过滤器

redis 在 4.0 的版本中加入了 module 功能，布隆过滤器可以通过 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通过加载 module来使用 redis 中的布隆过滤器。但是这不是最简单的方式，使用 docker 可以直接在 redis 中体验布隆过滤器。

> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli

redis 布隆过滤器主要就两个命令：

  • bf.add 添加元素到布隆过滤器中：bf.add urls https://jaychen.cc。
  • bf.exists 判断某个元素是否在过滤器中：bf.exists urls https://jaychen.cc。

上面说过布隆过滤器存在误判的情况，在 redis 中有两个值决定布隆过滤器的准确率：

  • error_rate ：允许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间也就越大。
  • initial_size ：布隆过滤器可以储存的元素个数，当实际存储的元素个数超过这个值之后，过滤器的准确率会下降。

redis 中有一个命令可以来设置这两个值：

bf.reserve urls 0.01 100

三个参数的含义：

  • 第一个值是过滤器的名字。
  • 第二个值为 error_rate 的值。
  • 第三个值为 initial_size 的值。

使用这个命令要注意一点：执行这个命令之前过滤器的名字应该不存在，如果执行之前就存在会报错：(error) ERR item exists

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 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 中的布隆过滤器的实现

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

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

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

  • 浅析python实现布隆过滤器及Redis中的缓存穿透原理

    浅析python实现布隆过滤器及Redis中的缓存穿透原理

    目录 布隆过滤器的原理 在 Python 中使用布隆过滤器 1.标准布隆过滤器. 2.计数布隆过滤器. 3.标准扩容布隆过滤器. 4.计数扩容布隆过滤器. Redis 中使用布隆过滤器 最后的话 在开发软件时,我们经常需要判断一个元素是否在一个集合中,比如,如何判断单词的拼写是否错误(判断单词是否在已知的字典中):在网络爬虫里,如何确认一个网址是否已经爬取过:反垃圾邮件系统中,如何判断一个邮件地址是否为垃圾邮件地址等等. 如果这些作为面试题那就很有区分度了,初级工程师就会说,把全部的元素都存在

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

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

  • 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使用元素删除的布隆过滤器来解决缓存穿透问题

    Redis使用元素删除的布隆过滤器来解决缓存穿透问题

    目录 前言 缓存雪崩 解决方案 缓存击穿 解决方案 缓存穿透 解决方案 布隆过滤器(Bloom Filter) 什么是布隆过滤器 位图(Bitmap) 哈希碰撞 布隆过滤器的2大特点 fpp 布隆过滤器的实现(Guava) 布隆过滤器的如何删除 带有计数器的布隆过滤器 总结 前言 在我们日常开发中,Redis使用场景最多的就是作为缓存和分布式锁等功能来使用,而其用作缓存最大的目的就是为了降低数据库访问.但是假如我们某些数据并不存在于Redis当中,那么请求还是会直接到达数据库,而一旦在同一时间大

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

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

  • 详解SpringBoot中如何使用布隆过滤器

    目录 前言 一.Guava 实现布隆过滤器 二.Hutool 布隆过滤器 三.Redission 布隆过滤器 四.小结 五.Guava 布隆过滤器结合 Redis 使用 昨天写了一篇Redis布隆过滤器相关的命令的文章,今天来说一说springboot中如何简单在代码中使用布隆过滤器吧. 目前市面上也有好几种实现方式,如果你需要高度定制化,可以完全从零实现,当然这不是一个简单的工程. 如果只是想快速开始的话,那么市面上现成的实现,无疑是最快的. 前言 今天说到的实现方式有以下几种: 引入 Gua

  • 什么是Java布隆过滤器?如何使用你知道吗

    什么是Java布隆过滤器?如何使用你知道吗

    目录 一.布隆过滤器简介 二.布隆过滤器的结构 三.布隆过滤器应用 四.布隆过滤器的优缺点 五.布隆过滤器实战 六.总结 Redis缓存穿透可以通过布隆过滤器进行解决,那么什么是布隆过滤器呢?请往下看. 通常你判断某个元素是否存在用的是什么? 很多人想到的是HashMap. 确实可以将值映射到 HashMap 的 Key,然后可以在 O(1) 的时间复杂度内返回结果,效率奇高.但是 HashMap 的实现也有缺点,例如存储容量占比高,考虑到负载因子的存在,通常空间是不能被用满的,而一旦你的值很多

随机推荐