BloomFilter使用与D-Lelft BloomFilter实现 - 综合当前位置:& &&&BloomFilter使用与D-Lelft BloomFilter实现BloomFilter使用与D-Lelft BloomFilter实现&&网友分享于：&&浏览：83次BloomFilter应用与D-Lelft BloomFilter实现此篇文章是开发过程中对BloomFilter应用场景的一些介绍，另外项目中实现了D-Left BloomFilter，相关实现时一些注意的地方，简单介绍下！
首先看一些应用场景：
1.海量的黑白名单。
2.爬虫抓取时重复的URL处理。
3.数据key是否存在检测
4.(一些面试题几十亿不重复整数中判断其中一个整数是否存在的问题，BitMap/BloomFilter能很好的解决)
对于以上提出的三种场景，如果数据量相对较少，可以将数据存储在数据库，或者加载内存中判断对应的黑白名单是否存在判断即可。
可是当数据量达到很大时，比如1亿条的黑白名单，假如每个名单占用空间为10byte，对于查询中将遇到两种问题，如果数据都在数据库中且并发量很大，每次查询将给DB带来的压力不可想象的。 另外如果所有名单加载到缓存中，将占据的内存空间是：1G，如果数据量更大，所占空间更多。
对于以上问题，如果通过BloomFilter，通过牺牲一定的准确率，使用1G/80 和内存空间，就能解决此问题。
一.什么是BloomFilter?
BloomFilter是一种高效的随机数据结构，被用于检测一个元素是否是一个集合中的一个元素,这种检测只会对在集合内的数据错判，而不会对不是集合内的数据进行错判，这样每个检测请求返回有“在集合内（可能错误）”和“不在集合内（绝对不在集合内）”两种情况，即如果它判断元素不在集合里，此元素一定不是集合中的元素，如果判断元素在集合里，有可能存在一定的错误率，可见 Bloom filter 是牺牲了正确率换取时间和空间。(因此需要注意使用时应用场景)
二.BloomFilter实现：
Bloom filter 采用的是哈希函数（hash fucnction）的方法，将一个元素映射到一个 m 长度的阵列上的一个点，当这个点是 1 时，那么这个元素在集合内，反之则不在集合内。这个方法的缺点就是当检测的元素很多的时候可能有冲突，解决方法就是使用 k 个哈希 函数对应 k 个点，如果所有点都是 1 的话，那么元素在集合内，如果有 0 的话，元素则不再集合内。(实现BloomFilter时，这个hash的k数可以设定，一般是4或者8)
BloomFilter测试发现，要想保持错误率低，最好让位数组有一半还空着。
三.BloomFilter应用的地方
BloomFilter在开源项目中有很多地方都有使用，其中Hadoop源码中实现了使用OpenBitSet实现了BloomFilter，另外还有CountingBloomFilter的实现。 另外Hbase源码中也有BloomFilter的实现，其中有BloomFilter的各种变种，都是跟据自己特定场景需要，进行相关实现。
四.BloomFilter的缺点：
标准的BloomFilter只支持插入和查找两种操作，如果表达的集合是静态集合的时候，在初始化集合大小，确定hash k的个数，控制错误率的基础上，BloomFilter可以很好的满足需求。但是对于一些动态集合，BloomFilter不满足需求了，其不支持删除操作，现引入Counting BloomFilter，能解决相关问题。
五.什么是Counting BloomFilter
Counting Bloom Filter,它将标准Bloom Filter位数组的每一位扩展为一个小的计数器（Counter），在插入元素时给对应的k（k为哈希函数个数）个Counter的值分别加1，删除元素时给对应的k个Counter的值分别减1。Counting Bloom Filter通过多占用几倍的存储空间的代价，给Bloom Filter增加了删除操作.如图示：
此方法实现是给每位增加一个4位的计数器，处理碰撞问题，即相当于原BloomFilter5倍的空间，可以动态维护BloomFilter, 当计数超过4位时，则溢出不处理，hash函数选择合理，数据集构造时合理，一般不会出现溢出。
Counting BloomFilter有删除操作后，其应用价值变得更广。
但是Counting BloomFilter也存在很明显的缺点：由于每个bucket负载不均衡，很多空间都被浪费掉了。因此引入了D Left BloomFilter.
六.D-Left Bloom Filter介绍
D-Left Bloom Filter也是BloomFilter的一种变种，它在比Counting BloomFilter使用更少的空间下，带来了删除操作，同时还能带来更少的错误率。
在引入D-Left Bloom Filter之间首先介绍下d-Left hash:有d个哈希表以及d个哈希函数，每一次插入时都先计算d个哈希值，然后通过计算出的地址h[key]来判断在这个位置上的负载是多少，把键值插入到负载小的表中,当负载一样时，则插入到Left表中。
d-left counting bloom filter的构造过程：在没有应用d-left hashing的情况下，我们使用一个哈希函数，把它的hash value分成两段，高位作存储地址，低位作fingerprint。现在要应用d-left hashing，有d个存储地址需要生成，我们仍然用一个哈希函数，但把它的hash value分成d+1段：高位的d段分别用作d个存储地址，每个子表对应一个，剩下的低位部分作为fingerprint在添加一个key时，先对它作一次hash，得到d个存储位置和一个fingerprint，然后判断d个位置中的负载情况，并在负载最轻的几个位置中选择最左边的插入。如果选择的位置已经存储了相同的fingerprint，就把那个cell的counter加1。在删除一个key时，同样地作一次hash，然后在d个存储位置查找相应的fingerprint，如果找到就将这个cell置空或者将相应的counter减1。
通过以上构造，对于不同元素，相同&fingerprint存在位置选择重合的问题！
给出的解决方案是：将hashing的整个操作分成两个阶段。第一阶段，我们用一个哈希函数H计算要插入元素x的hash value，记做fx；第二阶段，为了获得d个存储位置，我们另外引入d个随机置换（random permutation）。令H(x) = fx = (b, r)，其中b是bucket index，表示存储位置；r是remainder，表示要存储的fingerprint。然后令d个置换为：
P1(fx) = (b1, r1), P2(fx) = (b2, r2), … ,Pd(fx) = (bd, rd).其中Pi(fx)对应着x在第i个子表的存储位置和fingerprint。我们知道置换意味着一一对应，因此不同元素（的hash value）作置换之后的值仍然不同。这样我们就达到了前面提到的让不同元素的d个位置选择完全没有重合的目标。
引入随机置换避免了位置重合之后，我们还需要在插入元素之前作一项工作。每次插入一个元素时，先要在它的d个位置选择中检查是否已经存有相同的fingerprint，如果有，就把相应cell的counter加1。由于不同元素的存储位置不会重合，因此只有在碰撞的情况下才会出现两个相同fingerprint能存入同一组存储位置的情况。而我们一旦在插入之前作了检测，再作删除操作时就永远不会发现d个位置中有两个完全相同的fingerprint。
至于选择什么样的置换，论文作者给出的建议是：简单的线性函数。如果哈希函数的取值范围为[2q]，随机置换可以写成：
Pi(H(x)) = aH(x) mod 2q
其中a是区间[2q]中的随机奇数。
（对于我们实现中选择的奇数是定义的一常量，方便定义）
（以上为理论部分，所有相关理论部分参考http://blog.csdn.net/jiaomeng/article/details/1495500&博客中相关BloomFilter的知识，此作者写了很多相关BloomFilter的介绍，很详细，应该是写论文过程中的一些翻译记录，对于相关知识的理解很有帮忙）
七.D-Left Bloom Filter实现
使用java 实现D-Left BloomFilte实现过程中，主要注意的地方有：
1.D-Left Bloom Filter对于子表数的选择的问题，跟据实现需要选择，跟据集合数据量，我们的数据量在百万级别，选用了四张子表，每张子表对应bsize个桶.
2.初始化集合m.
3.每个桶存储8个cell,每个cell存储x位手印，每个cell的计数为y bit,(x位手印数与y位计数器，跟据集合数据量选择手印的大小，count计数可为2位或者4位)
4.采用数据结构建议使用byte[][]多维数组实现。bitsets不好控制。
5.对于hash函数的选择，可任意。（我们项目 中使用md5，128位，足够使用了）.
6.实现过程中通过hash截取，以及相关组装，置换操作，通过位操作可以很高效的实现。（置换函数可以是：Pi(H(x)) = aH(x) mod 2q, &其中a为随机奇数，以及H(x)为新组装的高位地址+手印，2q为h(x)位数对应最大值）
相关测试数据：
经过简单测试，错误率在百万分之一左右。集合在50万左右。
在五十万元素后，增加一个元素的时间在0.2ms到0.3ms左右，查询一个元素是否存在0.1ms左右，删除在0.3到0.4ms左右。
对于元素的分配，插入五十万数据，每个表的分布如下：
table 0:135203
table 1:128226
table 2:122795
table 3:113776
相对而言，每个表的数据分配还是比较均匀，这样大大的节省了空间。
项目中使用D-Left BloomFilter主要是对于一个key的查询，由于外部查询时，很多不存在的key查询我们相关数据库，这样会对系统DB有很大的负担，通过缓存查，相应的命中率也很低，为了解决这些问题，我们把相应的此key的值会在系统初始化时通过D-Left BloomFilter时加载一次，相应的add,remove操作也支持，这样在能过滤掉大部分不存在系统中的key，而对于判断存在的key，由于存在部分错误率，我们再会从缓存或者数据库中去判断是否存在，这样相应的命中率就会很高，也保证了数据的正确性。
另外同事在做相关爬虫时也使用到了BloomFilter。对于Hadoop以及Hbase源码中也有相关模块，有需要的朋友可能自行查找相关源码。（ps:也可以一起交流，共同学习）
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 12345678910 Copyright & &&版权所有再谈BloomFilter设计
对于Bloom Filter而言，容量和错误率（False Positive
Rate）已经由数学原理确定了。我们要关心的是其性能。Bloom
Filter的性能其实就是其中使用的HASH算法的性能。在《选择一种优秀的HASH算法》一文中，我测试了一些著名的HASH算法。由于Bloom
Filter每次插入或查询需要多个HASH值，最理想的做法就是计算一个长的HASH，然后把它切成等长的几个短HASH值。以速度和质量而言，最理想的就是MD5或SHA1了。
下面的表格是使用MD5或SHA1时Bloom
Filter的特性。以第一行为例，解读为：当HASH长度为32bit时，占用内存512M，使用4个HASH，在错误率为6.25%时，容量为7.44亿个项目。使用MD5算法时，m乘以k的值不得大于128bit，而SHA1则是160bit。
mem (bytes)
mem (bytes)
通过对比，我发现内存使用量相同的情况下，MD5的错误率稍高，而容量也稍大一点。使用MD5算法要达到和SHA1相同的容量，其错误率会提高0.1%～0.2%。考虑到MD5的速度较快，我觉得这点错误率的上升也是可以接受的，因为实际使用中选择的Bloom
Filter容量应该比应用所需容量大一些，而在此前提下，Bloom Filter的错误率是呈指数方式下降的。
我的更多文章：
( 09:30:38)( 21:43:07)
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
您的访问请求被拒绝 403 Forbidden - ITeye技术社区
您的访问请求被拒绝
亲爱的会员，您的IP地址所在网段被ITeye拒绝服务，这可能是以下两种情况导致：
一、您所在的网段内有网络爬虫大量抓取ITeye网页，为保证其他人流畅的访问ITeye，该网段被ITeye拒绝
二、您通过某个代理服务器访问ITeye网站，该代理服务器被网络爬虫利用，大量抓取ITeye网页
请您点击按钮解除封锁&<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
您的访问请求被拒绝 403 Forbidden - ITeye技术社区
您的访问请求被拒绝
亲爱的会员，您的IP地址所在网段被ITeye拒绝服务，这可能是以下两种情况导致：
一、您所在的网段内有网络爬虫大量抓取ITeye网页，为保证其他人流畅的访问ITeye，该网段被ITeye拒绝
二、您通过某个代理服务器访问ITeye网站，该代理服务器被网络爬虫利用，大量抓取ITeye网页
请您点击按钮解除封锁&BloomFilter算法在告警融合中的应用--《2010年全国通信安全学术会议论文集》2010年
BloomFilter算法在告警融合中的应用
【摘要】：告警融合是对入侵检测产生的一系列告警事件进行预处理、聚合与合并、关联,从而达到减少告警数量,了解入侵者真实意图的目的。本文首次提出利用Bloom Filter算法,在误差允许的条件下,对告警融合前后的信息进行两次过滤,精简告警信息比例63%以上,达到压缩并节约存储资源,同时提高整个网络安全管理系统的工作效率的目的。
【作者单位】：
【关键词】：
【分类号】：TP393.08【正文快照】：
1前言随着网络规模日益庞大，网络人侵不断增多，采取主动防御的网络人侵检测(ms)技术因能同时检测来自外部的恶意攻击和内部破坏行为而得到广泛应用，IDS对网络的运行状态进行监视、分析网络中的各种事件流，判定攻击行为，达到保障系统和资源的可用性、完整性和机密性的目
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【同被引文献】
中国期刊全文数据库
苏利敏,侯朝桢,戴忠健,潘秀琴;[J];北京理工大学学报;2002年03期
栗然,张锋奇,盛四清,张京;[J];华北电力大学学报;1998年02期
马琳茹;杨林;王建新;唐鑫;;[J];通信学报;2006年09期
中国硕士学位论文全文数据库
齐永欣;[D];河北农业大学;2002年
【二级参考文献】
中国期刊全文数据库
王志伟;郭文东;;[J];河北科技大学学报;2005年04期
穆成坡;黄厚宽;田盛丰;;[J];计算机研究与发展;2006年01期
高平利;任金昌;;[J];计算机应用与软件;2006年08期
李伟男;鄂跃鹏;葛敬国;钱华林;;[J];软件学报;2006年12期
【相似文献】
中国期刊全文数据库
郭建平;[J];有线电视技术;2003年20期
任美睿;郭龙江;玄萍;;[J];计算机工程与应用;2006年19期
王鹤娴;;[J];软件导刊;2008年07期
胡廉民;;[J];乐山师范学院学报;2006年05期
周建楠;辛仲涛;夏徐刚;;[J];铁道通信信号;2008年08期
郑千岁;齐学科;;[J];内蒙古广播与电视技术;2003年01期
闫成忠;;[J];通信管理与技术;2007年04期
徐鹏;吕海军;李明伟;;[J];电网技术;2008年08期
罗理;刘响光;胡振;周姣;张刚伟;李启平;;[J];计算机与数字工程;2011年03期
李雪梅;王洪源;;[J];科技信息;2011年09期
中国重要会议论文全文数据库
董岱林;刘志辉;郑世慧;;[A];2010年全国通信安全学术会议论文集[C];2010年
李峰;尹永胜;;[A];2008通信理论与技术新发展——第十三届全国青年通信学术会议论文集（下）[C];2008年
孟庆发;谢丰;吕铁强;周立德;;[A];第二届全国信息检索与内容安全学术会议（NCIRCS-2005）论文集[C];2005年
何锐;肖刚;易雅鑫;卢宁;;[A];计算机技术与应用进展·2007——全国第18届计算机技术与应用（CACIS）学术会议论文集[C];2007年
杨强;谷利泽;;[A];2009通信理论与技术新发展——第十四届全国青年通信学术会议论文集[C];2009年
闫斌;张茹;谷利泽;;[A];2009通信理论与技术新发展——第十四届全国青年通信学术会议论文集[C];2009年
姚伟力;王锡禄;宋俊德;;[A];2005年信息与通信领域博士后学术会议论文集[C];2005年
邵攻非;张向红;;[A];中国计量协会冶金分会2008年会论文集[C];2008年
邵攻非;张向红;;[A];2008全国第十三届自动化应用技术学术交流会论文集[C];2008年
崔晓红;张小军;;[A];中国航空学会信号与信息处理专业全国第八届学术会议论文集[C];2004年
中国重要报纸全文数据库
王洪武;[N];中国计算机报;2002年
中国石油勘探开发研究院
刘淑芬?中国石油勘探开发研究院西北分院
郭以东;[N];计算机世界;2008年
联想服务器网络事业部研发工程师 郭翔宇;[N];计算机世界;2003年
本报记者 郭平;[N];计算机世界;2002年
;[N];计算机世界;2002年
中国石油勘探开发研究院
刘淑芬 中国石油勘探开发研究院西北分院
郭以东;[N];计算机世界;2008年
苗永 陈大虎;[N];金融时报;2006年
中国电信股份有限公司上海研究院
段勇　石屹嵘
姚晓辉;[N];通信产业报;2008年
白云飞;[N];计算机世界;2004年
黄滔;[N];网络世界;2003年
中国博士学位论文全文数据库
徐前方;[D];北京邮电大学;2007年
刘兰;[D];华中科技大学;2007年
李彤岩;[D];电子科技大学;2010年
中国硕士学位论文全文数据库
龚德良;[D];中南大学;2010年
彭丽娟;[D];重庆大学;2011年
杨一兵;[D];哈尔滨工程大学;2008年
朱文颖;[D];华中科技大学;2007年
李博;[D];华中科技大学;2007年
刘强;[D];国防科学技术大学;2009年
璩啸;[D];上海交通大学;2007年
敖日格勒;[D];哈尔滨工程大学;2009年
匡红阳;[D];湖南大学;2006年
陈骏铭;[D];北方工业大学;2008年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 大众知识服务
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号}