教学网站开发背景,企业网站的设计思路,遵义外国网站制作,凡科网用户登录问题的提出
我们有一个不安全网页的黑名单#xff0c;包含了100亿个黑名单网页的URL,每个网页URL最多占用64B.。
现在我们要设计一个网页过滤系统#xff0c;这个系统要判断该网页是否在黑名单里#xff0c;但是我们的空间有限#xff0c;只有30GB.
允许有万分之一的判断…问题的提出
我们有一个不安全网页的黑名单包含了100亿个黑名单网页的URL,每个网页URL最多占用64B.。
现在我们要设计一个网页过滤系统这个系统要判断该网页是否在黑名单里但是我们的空间有限只有30GB.
允许有万分之一的判断失误
布隆过滤器
我们可以把所有的URL保存起来比如放到hashmap里但是64B*100亿640GB不符合要求。
布隆过滤器Bloom Filter是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法缺点是有一定的误识别率和删除困难。
如果遇到网页黑名单系统、垃圾邮件过滤、爬虫网址判重等问题如果可以容忍一定程度的失误率那么我们就可以用布隆过滤器来解决。
哈希函数
我们先来认识一下哈希函数或者说是复习
1
哈希函数的输入可以认为是无穷大或者是非常大的范围比如任意一个整数字符串而输出域是有范围的
这就意味着不同的输入可能是相同的输出
2
当输入相同的值时返回值也相同确定性
3)
所有不同的输入值得到的输出均匀地分布在输出域内并且与输入值出现的规律无关。这也是评价一个哈希函数是否优秀的两个重要标准比如1和2相差很近但是经过优秀的哈希函数计算后他们应该差距较大。
4
速度快可以认为哈希函数的计算时间是O(1)的。
布隆过滤器输入
下面就开始介绍布隆过滤器啦。
1
我们准备k个哈希函数并且他们之间没有什么关系彼此独立。
那么对于同一个输入对象你想的没错就是一个URL经过计算出来的结果也是完全独立的没有规律的。
2
我们准备一个数组长度为m只有两种状态所以我们选用bit数组名为bitmap。
3
我们输入一个黑名单里的URL时把URL用每一个哈希函数计算出来结果%数组长度目的是能存下呀。。。。。把对应位置的bit变为1记录下来。
处理完所有URL我们的布隆过滤器就准备好啦。
布隆过滤器检查
我们如何用布隆过滤器检查某个URL是否是黑名单中的呢 同样的方法把这个值用k个哈希函数算出结果每一个结果都去bitmap里找有没有存在过只要有一个结果不存在那这个URL就肯定不是黑名单了。因为之前用同样的方法bitmap变为1的那些位置和现在应该是一样的
接下来就是比较佛性的事了既然有一个答案不存在这个URL就不是黑名单里的那。。。所有答案都存在就能确定它在黑名单里吗
不是的。
因为可能是其它URL算出的答案恰好把本URL的答案全都算出来过。
想到这就不禁要问了那这个数据结构有啥用不是坑爹呢
其实是有用的他的失误率是很低很低的。
他的原则就是“宁可错杀三千不可放过一个”
如何设计空间和哈希函数 首先我们应该想到数组太小的话肯定是不准确的比如 就这么小个数组存了几个URL十个地方全算出来过全成1了。
那后面判断的时候就比较坑了随便来什么URL,随便什么哈希函数算出的答案全都出现过这显然不是我们想要的。
所以我们应该知道数组过小会影响准确性。
那么我们如何根据数据量来设计数组大小和哈希函数个数呢
以本题为例
样本数100亿
失误率不超过0.01%记为p
每个样本大小64B这个其实不影响布隆过滤器大小因为这是和哈希函数有关的一般的哈希函数都能接受64B的数据并且输出bitmap只需记录答案是否出现过即可
布隆过滤器大小m由以下公式决定 根据公式算出m19.19n向上取整20所以需要2000亿bit25GB
哈希函数的个数由以下公式决定 k14
布隆过滤器的失误率为 计算出为0.006%符合要求此题可解。
公式分析 白名单
过滤器会用错误对已经发现的错误样本可以建立白名单防止错误。
其他使用场景
网页爬虫对URL的去重避免爬去相同的URL地址垃圾邮件过滤从数十亿个垃圾邮件列表中判断某邮箱是否是杀垃圾邮箱解决数据库缓存击穿黑客攻击服务器时会构建大量不存在于缓存中的key向服务器发起请求在数据量足够大的时候频繁的数据库查询会导致挂机。
