我命由我,不由天!


  • 搜索
prometheus docker golang linux kubernetes

redis-布隆过滤器(六)

发表于 2021-05-29 | 0 | 阅读次数 359

布隆过滤器

解决去重问题,它在起到去重作用的同时,在空间上还能节省90%以上,只是稍微有那么点不准确,也就是有一定的误判概率

定义

把布隆过滤器理解为一个不怎么精确的set结构,当使用contains方法判断某个对象是否存在时,可能会误判,但只要参数设置合理,它的精度可以控制的足够精确,只会有小小的误判概率。

当布隆过滤器说某个值存在时,这个值可能不存在;当它说某个值不存在时,这个值肯定不存在。

基本用法

布隆过滤器有两个基本指令,bf.add 添加元素和bf.exists查询元素是否存在。

bf.add codehole user1
bf.exists codehole user1
bf.madd codehole user4 user5
bf.mexists codehole user4 user5

在add之前可以调用bf.reserve指令显示创建,如果对应的key已经存在,bf.reserve会报错。bf.reserve有三个参数,分别是key、error_rate和initial_size

error_rate 越低,需要的空间越大

initial_size表示预计放入的元素数量,当实际数量超出这个数值时,误判率会上升,需要提前设置一个较大的数值避免。

原理

每个布隆过滤器对应到redis的数据结构里面就是一个大型的位数组和几个不一样的无偏hash函数,所谓无偏就是能把元素的hash值算得比较均匀,让元素被hash映射到位数组中的位置比较随机。
image.png
添加key:会使用多个hash函数对key进行hash,算得一个整数索引值,然后对位数组长度进行取模运算的大一个位置,每个hash函数都会算得不同的位置,再把位数组的这几个位置都置为1,就完成了add操作

询问key是否存在:用hash算法把key都算出来,然后判断位置是否都为1,只要有一个位是0,那么说明这个key不存在

空间占用估计

布隆过滤器有两个参数,第一个是预计元素的数量n,第二个是错误率f。公式根据这两个输入得到输出,第一个输出是位数组的长度l,也就是需要的存储空间大小(bit),第二个是输出hash函数的最佳数量k。

其他应用

  • 爬虫系统去除重复爬取的URL
  • 数据库中不存在row的过滤
  • 垃圾邮件
  • 本文作者: Dante
  • 本文链接: https://gaodongfei.com/archives/redis-布隆过滤器
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
redis-HyperLogLog(五)
redis-限流(七)
  • 文章目录
  • 站点概览
Dante

Dante

119 日志
5 分类
5 标签
RSS
Creative Commons
0%
© 2023 Dante
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4
沪ICP备2020033702号