• 欢迎访问搞代码网站,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站!
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏搞代码吧

布隆过滤器(bloom filter)介绍以及php和redis实现布隆过滤器实现方法

redis 海叔叔 1天前 5次浏览 已收录 0个评论

引言在介绍布隆过滤器之前我们首先

引入几个场景

场景一

在一个高并发的计数系统中,如果一个key没有计数,此时我们应该返回0。但是访问的key不存在,相当于每次访问缓存都不起作用了。那么如何避免频繁访问数量为0的key而导致的缓存被击穿?
有人说, 将这个key的值置为0存入缓存不就行了吗?这是确实是一种解决方案。当访问一个不存在的key的时候,设置一个带有过期时间的标志,然后放入缓存。不过这样做的缺点也很明显:浪费内存和无法抵御随机key攻击。

场景二

在一个黑名单系统中,我们需要设置很多黑名单内容。比如一个邮件系统,我们需要设置黑名单用户,当判断垃圾邮件的时候,要怎么去做。比如爬虫系统,我们要记录下来已经访问过的链接避免下次访问重复的链接。
在邮件很少或者用户很少的情况下,我们用普通数据库自带的查询就能完成。在数据量太多的时候,为了保证速度,通常情况下我们会将结果缓存到内存中,数据结构用hash表。这种查找的速度是O(1),但是内存消耗也是惊人的。打个比方,假如我们要存10亿条数据,每条数据平均占据32个字节,那么需要的内存是64G,这已经是一个惊人的大小了。

一种解决思路

能不能有一种思路,查询的速度是O(1),消耗内存特别小呢?前辈门早就想出了一个很好的解决方案。由于上面说的场景判断的结果只有两种状态(是或者不是,存在或者不存在),那么对于所存的数据完全可以用位来表示。数据本身则可以通过一个hash函数计算出一个key,这个key是一个位置,而这个key所对的值就是0或者1(因为只有两种状态),如下图:

布隆过滤器原理

上面的思路其实就是布隆过滤器的思想,只不过因为hash函数的限制,多个字符串很可能会hash成一个值。为了解决这个问题,布隆过滤器引入多个hash函数来降低误判率。
下图表示有三个hash函数,比如一个集合中有x,y,z三个元素,分别用三个hash函数映射到二进制序列的某些位上,假设我们判断w是否在集合中,同样用三个hash函数来映射,结果发现取得的结果不全为1,则表示w不在集合里面。
布隆过滤器处理流程
布隆过滤器应用很广泛,比如垃圾邮件过滤,爬虫的url过滤,防止缓存击穿等等。下面就来说说布隆过滤器的一个完整流程,相信读者看到这里应该能明白布隆过滤器是怎样工作的。

第一步:开辟空间

开辟一个长度为m的位数组(或者称二进制向量),这个不同的语言有不同的实现方式,甚至你可以用文件来实现。

第二步:寻找hash函数

获取几个hash函数,前辈们已经发明了很多运行良好的hash函数,比如BKDRHash,JSHash,RSHash等等。这些hash函数我们直接获取就可以了。

第三步:写入数据

将所需要判断的内容经过这些hash函数计算,得到几个值,比如用3个hash函数,得到值分别是1000,2000,3000。之后设置m位数组的第1000,2000,3000位的值位二进制1。

第四步:判断

接下来就可以判断一个新的内容是不是在我们的集合中。判断的流程和写入的流程是一致的。

误判问题

布隆过滤器虽然很高效(写入和判断都是O(1),所需要的存储空间极小),但是缺点也非常明显,那就是会误判。当集合中的元素越来越多,二进制序列中的1的个数越来越多的时候,判断一个字符串是否在集合中就很容易误判,原本不在集合里面的字符串会被判断在集合里面。

数学推导

布隆过滤器原理十分简单,但是hash函数个数怎么去判断,误判率有多少?
假设二进制序列有m位,那么经过当一个字符串hash到某一位的概率为:1m。也就是说当前位被反转为1的概率:p(1)=1m。那么这一位没有被反转的概率为:p(0)=1−1m。
假设我们存入n各元素,使用k个hash函数,此时没有被翻转的概率为:p(0)=(1−1m)nk。那什么情况下我们会误判呢,就是原本不应该被翻转的位,结果翻转了,也就是 p(误判)=1−(1−1m)nk
由于只有k个hash函数同时误判了,整体才会被误判,最后误判的概率为 p(误判)=(1−(1−1m)nk)k。
要使得误判率最低,那么我们需要求误判与m、n、k之间的关系,现在假设m和n固定,我们计算一下k。可以首先看看这个式子:(1−1m)nk。
由于我们的m很大,通常情况下我们会用2^32来作为m的值。上面的式子中含有一个重要极限 limx→∞(1+1x)x=e。
因此误判率的式子可以写成 p(误判)=(1−(e)−nk/m)k。
接下来令t=−n/m,两边同时取对数,求导,得到:p′1p=ln(1−etk)+klnet(−etk)1−etk
让p′=0,则等式后面的为0,最后整理出来的结果是 (1−etk)ln(1−etk)=etklnetk
计算出来的k为ln2mn,约等于0.693mn,将k代入p(误判),我们可以得到概率和m、n之间的关系,最后的结果 (1/2)ln2mn,约等于0.6185m/n
以上我们就得出了最佳hash函数个数以及误判率与mn之前的关系了。

php+Redis实现的布隆过滤器

由于Redis实现了setbit和getbit操作,天然适合实现布隆过滤器,redis也有布隆过滤器插件。这里使用php+redis实现布隆过滤器。
首先定义一个hash函数集合类,这些hash函数不一定都用到,实际上32位hash值的用3个就可以了,具体的数量可以根据你的位序列总量和你需要存入的量决定,上面已经给出最佳值。

接着就是连接redis来进行操作

上面定义的是一个抽象类,如果要使用,可以根据具体的业务来使用。比如下面是一个过滤重复内容的过滤器。


喜欢 (0)
[搞代码]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址