没有合适的资源?快使用搜索试试~ 我知道了~
硬核 - Redis 布隆(Bloom Filter)过滤器原理与实战.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
5星 · 超过95%的资源 1 下载量 99 浏览量
2022-07-09
10:10:09
上传
评论
收藏 1.85MB DOC 举报
温馨提示
试读
11页
硬核 - Redis 布隆(Bloom Filter)过滤器原理与实战.doc
资源推荐
资源详情
资源评论
硬核 | Redis 布隆(Bloom Filter)过滤器原理与实战
在 Redis 缓存击穿(失效)、缓存穿透、缓存雪崩怎么解决?中我们说到可以使用布隆过
滤器避免「缓存穿透」。
码哥,布隆过滤器还能在哪些场景使用呀?
比如我们使用「码哥跳动」开发的「明日头条」APP 看新闻,如何做到每次推荐给该用
户的内容不会重复,过滤已经看过的内容呢?
你会说我们只要记录了每个用户看过的历史记录,每次推荐的时候去查询数据库过滤存在
的数据实现去重。
实际上,如果历史记录存储在关系数据库里,去重就需要频繁地对数据库进行 exists 查
询,当系统并发量很高时,数据库是很难扛住压力的。
码哥,我可以使用缓存啊,把历史数据存在 Redis 中。
万万不可,这么多的历史记录那要浪费多大的内存空间,所以这个时候我们就能使用布隆
过滤器去解决这种去重问题。又快又省内存,互联网开发必备杀招!
当你遇到数据量大,又需要去重的时候就可以考虑布隆过滤器,如下场景:
解决 Redis 缓存穿透问题(面试重点);
邮件过滤,使用布隆过滤器实现邮件黑名单过滤;
爬虫爬过的网站过滤,爬过的网站不再爬取;
推荐过的新闻不再推荐;
什么是布隆过滤器
布隆过滤器 (Bloom Filter)是由 Burton Howard Bloom 于 1970 年提出,它是一种 space
efficient 的概率型数据结构,用于判断一个元素是否在集合中。
当布隆过滤器说,某个数据存在时,这个数据可能不存在;当布隆过滤器说,某个数据不
存在时,那么这个数据一定不存在。
哈希表也能用于判断元素是否在集合中,但是布隆过滤器只需要哈希表的 1/8 或 1/4 的
空间复杂度就能完成同样的问题。
布隆过滤器可以插入元素,但不可以删除已有元素。
其中的元素越多,false positive rate(误报率)越大,但是 false negative (漏报)是不可能的。
布隆过滤器原理
BloomFilter 的算法是,首先分配一块内存空间做 bit 数组,数组的 bit 位初始值全部设
为 0。
加入元素时,采用 k 个相互独立的 Hash 函数计算,然后将元素 Hash 映射的 K 个位
置全部设置为 1。
检测 key 是否存在,仍然用这 k 个 Hash 函数计算出 k 个位置,如果位置全部为 1,
则表明 key 存在,否则不存在。
如下图所示:
哈希函数会出现碰撞,所以布隆过滤器会存在误判。
这里的误判率是指,BloomFilter 判断某个 key 存在,但它实际不存在的概率,因为它存
的是 key 的 Hash 值,而非 key 的值。
所以有概率存在这样的 key,它们内容不同,但多次 Hash 后的 Hash 值都相同。
对于 BloomFilter 判断不存在的 key ,则是 100% 不存在的,反证法,如果这个 key
存在,那它每次 Hash 后对应的 Hash 值位置肯定是 1,而不会是 0。布隆过滤器判断存
在不一定真的存在。
码哥,为什么不允许删除元素呢?
删除意味着需要将对应的 k 个 bits 位置设置为 0,其中有可能是其他元素对应的位。
因此 remove 会引入 false negative,这是绝对不被允许的。
Redis 集成布隆过滤器
Redis 4.0 的时候官方提供了插件机制,布隆过滤器正式登场。以下网站可以下载官方提
供的已经编译好的可拓展模块。
https://redis.com/redis-enterprise-software/download-center/modules/
码哥推荐使用 Redis 版本 6.x,最低 4.x 来集成布隆过滤器。如下指令查看版本,码哥
安装的版本是 6.2.6。
redis-server -v
Redis server v=6.2.6 sha=00000000:0 malloc=libc bits=64 build=b5524b65e12bbef5
下载
我们自己编译安装,需要从 下载,目前的 release 版本是 v2.2.14,下载地址:
https://.com/RedisBloom/RedisBloom/releases/tag/v2.2.14
剩余10页未读,继续阅读
资源评论
- 汭(ruì)2023-03-21实在是宝藏资源、宝藏分享者!感谢大佬~
书博教育
- 粉丝: 1
- 资源: 2837
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功