布隆过滤器计数布隆过滤器及其应用-课件

信息安全课程报告Bloom filter -The course report of Information security布隆过滤器组长：汇报人：2020/10/281目录CONTENTS1背景介绍2算法描述3误判概率证明和计算4优劣详解6布隆过滤器设计和应用5布隆过滤器改进方案2020/10/282精品资料2020/10/283布隆过滤器 背景介绍The background of Bloom filter012020/10/284比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断 它是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。背景介绍2020/10/285 一般来讲，计算机中的集合是用哈希表（hash table）来存储的。Hash函数作用就是把要存的数据映射成hash表中的一个位置，这个位置就是你要存放该数据的地方。一般把hash表的每个位置都叫做“槽（slot）”。它的好处是快速准确，缺点是浪费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。Hash函数2020/10/286假设hash表的大小为9（即有9个槽），hash(k)=k mod 9，现在要把一串数据存到表里：5,28,19,15,20,33,12,17,10 hash(5)=5,hash(28)=1，hash(19)=1，0 1 2 3 4 5 6 7 8 n个关键字映射到k个槽中，n只要大于k，一定至少有一个槽放了多于1个元素，所以不能完全避免碰撞（冲突）。Hash函数2852020/10/287位图法就是Bitmap的缩写。就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。位图法可以理解为通过一个bit数组来存储特定数据的一种数据结构；由于bit是数据的最小单位，所以这种数据结构往往是非常节省存储空间。位图法2020/10/288比如一个公司有8个员工，现在需要记录公司的考勤记录，传统的方案是记录下每天正常考勤的员工的ID列表，比如2012-01-01:1,2,3,4,5,6,7,8。假如员工ID采用byte数据类型，则保存每天的考勤记录需要N个byte，其中N是当天考勤的总人数。1 2 3 4 5 6 7 8 这样可以每天采用恒定的1个byte即可保存当天的考勤记录。位图法011100112020/10/289布隆过滤器（Bloom Filter），它结合了位图和Hash表两者的优点.位图的优点是节省空间，但是只能处理整型值一类的问题，无法处理字符串一类的问题.而Hash表却恰巧解决了位图无法解决的问题，然而Hash太浪费空间。布隆过滤器布隆过滤器2020/10/2810计数计数布隆过滤器布隆过滤器计数布隆过滤器是对基本布隆过滤器的改进，使布隆过滤器可以支持删除成员。因为布隆过滤器的基本单位是1个bit，只能表达2种状态，即存在、不存在。如果把基本单位1bit拓展成多个bit，这样就能增加更多信息，表达出多种状态。2020/10/2811布隆过滤器 算法描述The description of its core algorithm 022020/10/2812BloomFilter布隆过滤器（BloomFilter）是一种概率空间高效的数据结构。用于检索一个元素是否在一个集合中用于检索一个元素是否在一个集合中。存在“在集合内（可能错误）在集合内（可能错误）”和“不在集合内（绝对不在不在集合内（绝对不在集合内）集合内）”两种情况。2020/10/2813温故知新2020/10/2814核心思想核心思想就是利用多个不同的多个不同的Hash函数函数来解决“冲突”。如何判断某元素x是否在一个集合中？X1,X2,X3.XnRX核心思想2020/10/2815算法原理BloomFilter需要一个位数组位数组(和位图类似)和K个映射函数个映射函数(和Hash表类似)。包含两种操作：插入和查询插入和查询1.初始化：将所有位置置02.集合R=r1,r2.rn,通过k个相互独立的映射函数h1,h2,.hk，将集合R中的每个元素rj(1=j 忽略碰撞并且只存储元素是否在其中的二进制信息时k=1的布隆过滤器2020/10/2833使用k1的布隆过滤器，即k个哈希函数将每个元素改为对应于k个bits，因为误判度会降低很多，并且如果参数k和m选取得好，一半的m可被置为1，这充分说明了布隆过滤器的空间效率性。优点空间效率性2020/10/2834布隆过滤器可以表示全集，其它任何数据结构都不能。k和m相同，使用同一组散列函数的两个布隆过滤器的交并差运算可以使用位操作进行。优点2020/10/2835在增加了错误率这个因素之后，布隆过滤器通过允许少量的错误来节省大量的存储空间。优点错误率2020/10/2836有误判的概率，即存在假阳性（FalsePosition），无法获取集合中的元素数据。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。（误判补救方法是：再建立一个小的白名单，存储那些可能被误判的信息。）缺点2020/10/2837一般情况下不能从布隆过滤器中删除元素。另外计数器回绕也会造成问题。缺点2020/10/2838布隆过滤器 改进方案The design and application in Bloom filter052020/10/283900000000001亿邮箱1616亿二进制亿二进制亿二进制亿二进制随机数生成器随机数生成器F1-8f1=F1f2=F2f3=F3f4=F4f5=F5f6=F6f7=F7f8=F8信息指信息指纹纹随机数生成器随机数生成器G1011111110f1f1f2f2f3f3f4f4f5f5f6f6f7f7f8f8添加地址f2f22111111110f1=F1=f1f2=F2f3=F3=m2f4=F4=m3f5=F5=m4f6=F6=m5f7=F7=m6f8=F8=m7f1f1Counter2020/10/2840增加删除功能增加删除功能CountingBloomFilterCountingBloomFilterCounting Bloom FilterCounting Bloom Filter的出现解的出现解决了这个问题，它将标准决了这个问题，它将标准Bloom Bloom FilterFilter位数组的每一位扩展为一个小位数组的每一位扩展为一个小的计数器的计数器(Counter)(Counter)，在插入元素时，在插入元素时给对应的给对应的k(kk(k为哈希函数个数为哈希函数个数)个个CounterCounter的值分别加的值分别加1 1，删除元素时给，删除元素时给对应的对应的k k个个CounterCounter的值分别减的值分别减1 1，Counting Bloom FilterCounting Bloom Filter通过多占用通过多占用几倍几倍几倍几倍的存储空间的代价，给的存储空间的代价，给Bloom Bloom FilterFilter增加了删除操作。增加了删除操作。10110A AB B10210A AB BBFCBF2020/10/2841CountingBloomFilterCountingBloomFiltern n：集合元素个数，：集合元素个数，k k：HashHash函数个数，函数个数，k=0.7*m/n M M：位数组的大小：位数组的大小从从nknk次哈希中选择次哈希中选择j j次次j j次哈希都选中了第次哈希都选中了第i i个个CounterCounter其它其它nkjnkj次哈希没有次哈希没有选中第选中第i i个个CounterCounter2020/10/2842出现频率查询出现频率查询SpectralBloomFilterSpectralBloomFilter基本思想：基本思想：1.1.元素元素x x对应的对应的k k个个countercounter中的最小值中的最小值m mx x=出现频率出现频率f fx x2.2.f fx x m mx x的概率和标准的概率和标准bloom filterbloom filter的误判概率相同的误判概率相同5016111210A AB Bk k个位置全个位置全部发生碰撞部发生碰撞2020/10/2843SpectralBloomFilterSpectralBloomFilter索引结构索引结构co1co2co3co4o1o2o3o4子串长度子串长度log3N位位Coarse VectorCoarse Vectorco1co2o1o2子串长度子串长度(loglogN)3位位LOOK UP TABLEOffset VectorOffset Vector子串长度子串长度=(loglogN)3位位loglog2 2N N个个countercounterlogN/loglogNlogN/loglogN2020/10/2844DynamicDynamicC CountountF Filterilter025701026527Counter000001000100010OverFlow VectorCounting Bloom Filter Vectorx=log(M/n)y=floor(log(max(OFj)+1M M M M：集合中元素的个数：集合中元素的个数：集合中元素的个数：集合中元素的个数n n n n：集合中元素种类：集合中元素种类：集合中元素种类：集合中元素种类查询一个查询一个countercounter时，时，DCFDCF要要求两次内存访问。假设想查求两次内存访问。假设想查询位置为询位置为j j的的countercounter的值，的值，我们先读出我们先读出CBFVCBFV和和OFVOFV的值，的值，分别为分别为CjCj和和OFjOFj，那么，那么countercounter的值就可以表示为的值就可以表示为Vj=(2xOFj Vj=(2xOFj Cj)Cj)。2020/10/2845DynamicDynamicC CountountF Filterilter最大值增加至最大值增加至2x+12x+1时，每次时，每次OFVOFV大小改变的时候都需要重建大小改变的时候都需要重建。重建是一件开销很大的工作，。重建是一件开销很大的工作，必须重新创建一个必须重新创建一个OFVOFV数组，然数组，然后把旧后把旧OFVOFV数组的值拷贝到新建数组的值拷贝到新建的的OFVOFV数组中，最后把旧数组中，最后把旧OFVOFV数数组的空间释放掉。组的空间释放掉。1000001000100010当当OFVOFV的最大值减少到的最大值减少到2x 2x 1 1时，我们可以选择马上重建时，我们可以选择马上重建OFVOFV，也可以采用一些策略延，也可以采用一些策略延迟迟OFVOFV的重建，以避免一些临的重建，以避免一些临时性的减少导致时性的减少导致OFVOFV反复重建。反复重建。0000010000000102020/10/2846布隆过滤器 设计和应用The design and application in Bloom filter062020/10/2847布隆过滤器应用假设有一条URL，那么就先建立32个二进制常量(取不同值，误报率会不同)。即4字节的向量，然后将这32个二进制位全部设置为0，对于这条URL，用8个不同的随机数产生8个信息指纹，再用一个随机数产生器把这8个信息指纹映射到1到32的8个自然数，并把这些位置置为1。如果要检测某条URL是否在这个Bloom Filter中，我们仍然用上述8个随机数产生8个信息指纹，并将这8个指纹对应到布隆过滤器的8个二进制位，如果8位都为1，则说明这条URL在这个Bloom Filter中，否则只要有一位不为1，就说明不在。Bloom Filter绝不会漏掉任何一个重复的URL，但可能会有误报情况，虽然这种可能性很小，上述说的误报概率只有千万分之一，可以通过建立一个小的名单，存储可能误判的URL，并进行比较。2020/10/2848已爬URL的过滤代码实现class BloomFilter private static final int BIT_SIZE=2 28;/二进制向量的位数 private static final int seeds=new int3,5,7,11,13,31,37,61;/用于生成信息指纹的8个随机数，最好选取质数 private BitSet bits=new BitSet(BIT_SIZE);private Hash func=new Hashseeds.length;/用于存储8个随机哈希值对象 public BloomFilter()for(int i=0;i seeds.length;i+)funci=new Hash(BIT_SIZE,seedsi);2020/10/2849已爬URL的过滤代码实现public void addValue(String value)/将字符串value哈希为8个或多个整数，然后在这些整数的bit上变为1 if(value!=null)for(Hash f:func)bits.set(f.hash(value),true);public boolean contains(String value)if(value=null)return false;boolean ret=true;/将要比较的字符串重新以上述方法计算hash值，再与布隆过滤器比对 for(Hash f:func)ret=ret&bits.get(f.hash(value);return ret;2020/10/2850已爬URL的过滤代码实现/*随机哈希值对象*/public static class Hash private int size;/二进制向量数组大小 private int seed;/随机数种子 public Hash(int cap,int seed)this.size=cap;this.seed=seed;/*计算哈希值(也可以选用别的恰当的哈希函数)*/public int hash(String value)int result=0;int len=value.length();for(int i=0;i len;i+)result=seed*result+value.charAt(i);return(size-1)&result;public class Test public static void main(String args)BloomFilter b=new BloomFilter();b.addValue();b.addValue();System.out.println(b.contains();System.out.println(b.contains();2020/10/2851计数布隆过滤器负载均衡（loadbalance）：将任务平摊到多个操作单元上执行，共同完成工作。半流：由相同的数据包组成的集合。全流：标识的半流和标识的半流的并集。大部分的多媒体协议信令和数据传输采用的是不同的端口。传统的负载均衡算法不能保证将多媒体会话映射到一个处理核上。因此应该根据流的信息动态调整映射位置。通过增加DP、SP的端口信息生成信息摘要，通过布隆过滤器直接映射到同一个处理器上面。2020/10/2852计数布隆过滤器将需要调整的全流标识生成对应的摘要信息Digest，将其保存到精确流匹配布隆过滤器中，对于每一个到来的IP数据包，提取标识并生成Digest然后根据和Digest查询ESBF结构，如果在其中，则转发到指定的处理核否则，对Digest取模得到对应的处理核ID。通过保存全流的标识到哈希表中，可以动态指定某个全流到相应的处理核2020/10/2853计数布隆过滤器ESBF算法基于CBF,利用CBF的多个哈希函数保证算法具有更低的冲突概率,CBF可以高效的根据(DA,SA,DP,SP)和k个哈希函数对IP包映射到不同的CPU上面进行处理。同时也可以对索引记录高效的插入和删除。动态更改处理IP包的CPU。2020/10/2854计数布隆过滤器插入算法代码如下：Insertelem(x，id)DigestDIGESTHASH(x)；创建链表结点并将digest、id域赋值；for(i=ltok)ifLinkheadbi(x)counter=0)将结点添加到链表尾部；elseif(链表长度为counter)将结点添加到链表尾部；else将结点添加到链表头部；)Linkhead(h。(x)counter+；)插入算法将由生成的Digest依次插入到k个链表之中。为了节省空间，如果结点都添加到链表尾部，则k个链表可以共享一个链表结点。2020/10/2855计数布隆过滤器删除算法代码如下：Deletelem(x)DigestDIGESTHASH(x)；for(i=1tok)j=O；while(jLinkheadh(x)counter)if(结点中的digest域与Digest相等)将结点从链表中删除，跳出循环；j+；Linkhead(h。(x)Counter一；删除算法将k个链表中结点digest的值与生成的Digest相等的结点从链表中依次删除。2020/10/2856计数布隆过滤器查询算法代码如下：Lookup(x)DigestDIGESTHASH(x)；for(i=ltok)if(Linkhead(h，(x)counter=0)returnfalse；J-k个counter中最小值对应的hi(x)for(i：1toLinkheadDcounter)i结点中的digest域与Digest相等)return结点的id域；returnfalse；)查询算法取k个计数器中值最小的计数器所对应的链表进行比较，最坏情况下比较的次数为该最小计数器的值。2020/10/2857