Redis教程

Redis之布隆过滤器BloomFilter

本文主要是介绍Redis之布隆过滤器BloomFilter,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

【引】
基数很大的集合,需要我们比较某个元素是不是存在于这个集合。如果这个查询验证的频率还很高,那么如何设计呢?
【方案】
1.数据库查询
可能我们要考虑的就是如何去分库了,然后再hash到对应的库中进行查找元素。这会是一个比较复杂,实施起来也麻烦的方案。
2.HashSet
对于查询的热点数据,我们也可以存于Set,即内存中,这样响应速度肯定也快,但是如何判断哪些需要在内存哪些需要放在磁盘也是需要平衡的。
3.布隆过滤器
布隆过滤器(bloomfilter,以下简称bf)是用误差率来换取空间,并且是极大的提升了空间利用率。我们可以利用bf技术,只用极小的空间(相比于set)就能够处理这种大基数的元素查询,虽然不能保证全部正确,但是用少量的误差,配合DB,可以使服务器的负载控制在可以接受的范围。
【RedBloom安装】
简单说,就是Redis本身是不支持bf的,得安装插件。Linux环境中下载插件[https://github.com/RedisLabsModules/rebloom/archive/v2.2.6.tar.gz]编译好,再在redis.conf中修改配置引用这个.so文件,重启Redis服务即可。
参考 [https://blog.csdn.net/qq_41125219/article/details/119972808]
【简单使用】
关键指令是bf.add key value , bf.madd key value1 value2 ...,bf.exists key value, bf.mexists value1 value2 ...

【基本原理】
每个布隆过滤器对应到 Redis 底层的数据结构就是一个大型的位数组和一系列的无偏哈希函数(所谓无偏就是能够把元素的哈希值算得比较均匀):

向布隆过滤器中添加键值对时,会使用这一系列哈希函数分别对键名进行哈希运算,然后将得到的整数索引值与位数组长度进行取模运算得到最终索引位置,再把位数组的这几个索引位都置为 1,这就完成了 bf.add 操作。
向布隆过滤器查询指定键名是否存在时,和 bf.add 一样,也会把哈希后的索引位置都算出来,看看位数组中这几个索引位的值是否都为 1,只要有一个位为 0,则说明布隆过滤器中这个键名不存在。如果都为 1,也并不能说明这个键名就一定存在,只是很有可能存在,因为这些位被置为 1 可能是其它键名哈希运算时出现哈希冲突所致(概率很低,但是存在)。
如果这个位数组比较稀疏,判断正确的概率就会很大,如果这个位数组比较稠密,判断正确的概率就会降低,因为出现哈希冲突的概率会提高,但是相对整体而言依然是很小的比例。
【空间与误差率】
Redis还提供了自定义参数的bf.实际使用时,如果需要的话,可以通过在 bf.add 之前执行 bf.reserve 指令自定义布隆过滤器的参数,这个指令支持三个参数:

key:指定键名;
error_rate:错误率,默认是 0.01,即 1%,你可以将其调小,但是错误率越低,所需要的集合容量就越大,占用的存储空间就越大;
initial_size:初始化的集合容量(集合中存放的元素数量),默认是 100,该值越大,错误率越低,但所需的存储空间也就越大,反之该值越小,所需的存储空间越小,但错误率越高。

注意:如果key已经存在(Redis默认使用的bf中error_rate为0.01,initial_size为100),使用bf.reserve时会报错的:

所以,在知道了集合总量多的情况下,当我们指定错误率时,我们是能够估计它的空间占用多大的。
  k=0.7*(L/N) #N表示集合总量,L表示位数组的长度,即bit长度,过滤器的空间大小。而k表示hash函数的数量
  f=0.6185^(L/N) #f表示错误率,L表示位长度即空间大小,N为集合总量
【使用场景】
1. 解决缓存穿透
(1). 含义
 业务请求中数据缓存中没有,DB中也没有,导致类似请求直接跨过缓存,反复在DB中查询,与此同时缓存也不会得到更新。(详见:https://www.cnblogs.com/yaopengfei/p/13878124.html)
(2). 解决思路
 事先把存在的key都放到redis的Bloom Filter 中,他的用途就是存在性检测,如果 BloomFilter 中不存在,那么数据一定不存在;如果 BloomFilter 中存在,实际数据也有可能会不存在。
剖析:布隆过滤器可能会误判,放过部分请求,当不影响整体,所以目前该方案是处理此类问题最佳方案。

2. 黑名单校验
 识别垃圾邮件,只要发送者在黑名单中的,就识别为垃圾邮件。假设黑名单的数量是数以亿计的,存放起来就是非常耗费存储空间的,布隆过滤器则是一个较好的解决方案。把所有黑名单都放在布隆过滤器中,再收到邮件时,判断邮件地址是否在布隆过滤器中即可。
ps:
  如果用哈希表,每存储一亿个 email地址,就需要 1.6GB的内存(用哈希表实现的具体办法是将每一个 email地址对应成一个八字节的信息指纹,然后将这些信息指纹存入哈希表,由于哈希表的存储效率一般只有 50%,因此一个 email地址需要占用十六个字节。一亿个地址大约要 1.6GB,即十六亿字节的内存)。因此存贮几十亿个邮件地址可能需要上百 GB的内存。而Bloom Filter只需要哈希表 1/8到 1/4 的大小就能解决同样的问题。

3. Web拦截器
(1). 含义
 如果相同请求则拦截,防止重复被攻击。
(2). 解决思路
 用户第一次请求,将请求参数放入布隆过滤器中,当第二次请求时,先判断请求参数是否被布隆过滤器命中,从而提高缓存命中率。

【参考】
《Redis深度历险 核心原理与应用实践》
https://blog.csdn.net/qq_41125219/article/details/119972808
https://www.cnblogs.com/yaopengfei/p/13928512.html

这篇关于Redis之布隆过滤器BloomFilter的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!