Redis教程

redis缓存穿透——布隆过滤器和布谷鸟过滤器

本文主要是介绍redis缓存穿透——布隆过滤器和布谷鸟过滤器,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

缓存穿透就是查询一次不存在的数据,因为不存在,所以也不会往redis里写值,这样一直查不存在的数据就会导致一直查数据库,redis并没有起到作用。

解决这个可以让redis缓存一个空值或者缓存一个特殊的字符串,但如果别人故意每次用不同的不存在的值恶意攻击的话,即使缓存了空值也还是没有,

这就可以用布隆过滤器来解决

布隆过滤器就是一串01位图,和几个哈希函数

就像这样,插入数据时,数据a经过三个哈希函数的计算,得到三个哈希值,分别把三个位置上的0变成1

当取得时候,数据a如果经过三个哈希函数算得的位置上都为1,就判断a存在,所以这就有问题,如果判断d的时候,得到的三个位置两个是a占的,一个是b占的,这样还判断d存在吗?显然是不对的

所以如果布隆过滤器判断一个元素存在,这个元素可能不存在

如果布隆过滤器判断一个元素不存在,这个元素一定不存在

如果想减少误判率就需要增加01数组的长度,和多加几个哈希函数。

布隆过滤器的缺点:

1.布隆过滤器也是不能修改和删除的,因为如果hello和你好算得的哈希值相同,然后把你好删了,这样就把hello也误删了

2.查询性能弱:布隆过滤器使用多个hash函数计算位图多个不同位点,由于多个位点在内存中不连续,CPU寻址花销较大。

3.空间利用率低

 

 

还有一种可以简单实现删除的过滤器——布谷鸟过滤器,不过他的删除也是有缺陷的

布谷鸟过滤器不是用位图实现的,使用的是一维数组,数组里面存放的是数据的指纹。

布谷鸟过滤器是可以鸠占鹊巢的,还拿上面的图来说

布谷鸟过滤器有三个哈希函数,两个哈希映射函数,和一个计算指纹的函数

H3(key) = key’s fingerprint = hash(key)
H1(key) = hash1(key)
H2(key) = H1(key) ^ H1(key’s fingerprint) 

数据a经过两个哈希映射函数,得到两个位置,如果数据a在两个位置里随机选择一个位置,如果这个位置没人就直接占据这个位置,如果已经有人了,就把这个位置上的人踢走,如果给他重新选择一个位置

重新选位置的时候,另一个位置可以通过指纹的哈希值和位置的哈希值异或得来

但这样也有问题,如果数组太过拥挤,就会导致踢了几十次依然没有给每个人找到位置。

改良的方案之一是增加 hash 函数, 让每个元素不止有两个巢, 这样可以大大降低碰撞的概率, 将空间利用率提高到 95% 左右.

还有个方案是给每个位置上设置多个座位,就像二维数组一样, 这样不会马上就挤来挤去. 也能大大降低碰撞概率, 空间利用率虽然比第一种改良方案稍低(约为 85%), 但cpu 缓存的利用率会提高不少.

删除的话,就是找到对应位置上的自己的指纹,然后删除掉

但这样的删除,如果通过哈希函数计算的指纹是一样的,位置也是一样的,就会造成误删

而且布谷鸟过滤器不能连续插入相同的数据,如果一直插入1,假设有两个位置,每个位置有四个座位,当插入第九个1的时候,就会导致没地方去了

所以插入相同的数据不能超过kb,k是位置数,b是座位数。

 

这篇关于redis缓存穿透——布隆过滤器和布谷鸟过滤器的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!