BloomFilter应用与D-Lelft BloomFilter实现_dleft hash 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:也可以一起交流,共同学习)


count bloomfilter 需要避免key重入,即在add前判断是否已经存在,否则会破坏bloomfilter的false negative逻辑。
回复:add什么时候操作,这个自己注意初始化场景吧,应用层尽量避免重复元素加入。对于add前判断是否存在,这个存在的情况,就是碰撞的情况,add也是合理。
个人理解,countbloomfilter支持元素删除,从而可以在bloomfilter内部维护数据的一致性,不用为了降低误判率而定期重建bloomfilter;请教一下:实际使用中数据初始化的策略,在线初始化还是离线初始化?
回复:支持删除是为了删除从系统中已经清除的元素,对于bloomfilter判断元素是否存在再决定是否增加,本身没意义,因为碰撞的存在,不相同的元素也有可能判断存在,所以清除的话会使bloomfilter萎乱的,使一些本属于系统的元素被判断为不存在。
而这一是否添加重复元素,如果系统使用bf,就得保证不去添加重复元素,对于你说的重建,也是不需要的。(实际使用时如果是分布式系统,牵涉到数据一致性,如果数据版本号不一致时,才有重建操作) 
对于初始化:这个看你们应用数据量多少,初始化需要多少时间,以及系统可容忍啊,看需求了。
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/fuwei736349065/article/details/75642933

智能推荐

在阿里云上的高校计划(白嫖计划)部署beego_sd用阿里云高效学生计划-程序员宅基地

文章浏览阅读1k次。我的博客地址(内容优先更新)brook1711.com在阿里云上的高校计划(白嫖计划)部署beego阿里云高校计划地址https://developer.aliyun.com/adc/student/首先需要进行实名认证和学生认证和别家不同的是,阿里云的学生服务器在到期前一个月可以通过学习课程免费续费。接下来在服务器上部署一个简单的beego项目1、登陆服务器过程略2、配置golang环境 wget https://golang.google.cn/dl/go1.16.linux-am_sd用阿里云高效学生计划

ORB原理与源码解析-程序员宅基地

文章浏览阅读528次。转载:http://blog.csdn.net/luoshixian099/article/details/48523267CSDN-勿在浮沙筑高台没有时间重新复制代码,只能一股脑的复制,所以代码效果不好。。。。。。   为了满足实时性的要求,前面文章中介绍过快速提取特征点算法Fast,以及特征描述子Brief。本篇文章介绍的ORB算法结合了Fast和Brief的速度..._python orb源码

DRF使用记录(二) -序列化器_validationerror(ordereddict([('drug', [errordetail-程序员宅基地

文章浏览阅读707次。drf使用记录(二) - 序列化器简述序列化:序列化器会把模型对象转换成字典,经过response以后变成json字符串反序列化:把客户端发送过来的数据,经过request以后变成字典,序列化器可以把字典转成模型即在客户端请求时,使用序列化器可以完成对数据的反序列化在服务器响应时,使用序列化器可以完成对数据的序列化序列化定义序列化器Django REST framework中..._validationerror(ordereddict([('drug', [errordetail(string='not a valid strin

python读取pickle,csv,excel文件速度大比拼_python读ecxel快还是读csv-程序员宅基地

文章浏览阅读2.7k次。进行数据处理时数据量一大,excel文件就力不从心。这次对三个文件格式的读取速度做大比拼。# -*- coding: UTF-8 -*-import timeimport pandas as pd"""csvexcelpkl速度大比拼"""start = time.clock()df = pd.read_pickle('table.pkl')elapsed = (tim..._python读ecxel快还是读csv

C语言排序算法演示:冒泡法_c语言测试冒泡算法在不同情况下的表现-程序员宅基地

文章浏览阅读8.8k次。C语言排序算法演示:冒泡法作者:Ackarlix 冒泡排序的算法分析与改进 交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。  应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。 冒泡排序 1、排序方法  将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是_c语言测试冒泡算法在不同情况下的表现

机器学习算法整理(一)线性回归与梯度下降 python实现-程序员宅基地

文章浏览阅读104次。回归算法以下均为自己看视频做的笔记,自用,侵删!一、线性回归θ是bias(偏置项)线性回归算法代码实现# coding: utf-8​get_ipython().run_line_magic('matplotlib', 'inline')import matplotlib.pylab as pltimport numpy ...

随便推点

curl详细用法_curl -i --basic -u-程序员宅基地

文章浏览阅读5.6k次,点赞2次,收藏4次。简介curl是一个和服务器交互信息(发送和获取信息)的命令行工具,支持DICT, FILE, FTP, FTPS, GOPHER, HTTP, HTTPS, IMAP, IMAPS, LDAP, LDAPS, POP3, POP3S, RTMP, RTSP, SCP, SFTP, SMTP, SMTPS, TELNET和TFTP等协议。curl支持代理、用户认证、FTP上传、HTTP POST..._curl -i --basic -u

Springboot使用RestTemplate发送Post请求postForEntity (application/x-www-form-urlencoded)_resttemplate postforentity-程序员宅基地

文章浏览阅读1w次,点赞4次,收藏14次。Springboot使用RestTemplate发送Post请求postForEntity[application/x-www-form-urlencoded] 背景思路正文ServiceRestTemplate 使用 postForEntity 请求接口基于xml系列注解解析XML返回值XML的一些基本常识实体类与xml文件对应实体代码参考博客背景对接请求为(application/x-www-form-urlencoded),返回XML格式接口。思路ServiceRestTemplate 使用_resttemplate postforentity

【Windows】你没有权限打开该文件,请向文件的所有者或管理员申请权限-程序员宅基地

文章浏览阅读7.4k次。【Windows】你没有权限打开该文件,请向文件的所有者或管理员申请权限原文链接:https://yangman824.gitee.io/posts/windows/问题:[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lZMpSi7B-1640160600075)(C:\Users\Sonder\AppData\Roaming\Typora\typora-user-images\image-20211220175325122.png)]解决方法:右键–属性–安全–编

用着超爽的stm32的串口DMA+空闲中断接收和发送方案_串口发送中断和空闲中断同时使能-程序员宅基地

文章浏览阅读1.4k次,点赞2次,收藏18次。串口一次只能传1byte数据,在实际应用中,我们会发送和接收一串数据,如果没发送和接收一个数据就会进去中断会严重影响程序的正常执行,占用过多的cpu资源。如果串口模块能够自动判别一串数据的结束,并且把接收数据放在我们指定的ram,发送数据直接扔到ram不用cpu操作,那该多省心!stm32的串口DMA+空闲中断接收和发送方案就能实现。我使用的是stm32f103芯片和freertos系统,串口程序已经长时间高效稳定运行在几万台设备上。我使用的是uart4。代码如下:初始化void UART4_Ini_串口发送中断和空闲中断同时使能

一文读懂逻辑信道、传输信道和物理信道-程序员宅基地

文章浏览阅读2.9k次,点赞4次,收藏18次。什么是信道?_逻辑信道

Source Insight 4.0 Sublime主题_sourceinsight4主题-程序员宅基地

文章浏览阅读1.4k次。Source Insight 4.0 Sublime主题_sourceinsight4主题

推荐文章

热门文章

相关标签