布隆過濾器、計數(shù)布隆過濾器及其應(yīng)用PPT課件

1、2021/3/91信息安全課程報告Bloom filter - The course report of Information security布隆過濾器組長： 匯報人：2021/3/92目錄CONTENTS1234652021/3/93布隆過濾器 背景介紹The background of Bloom filter012021/3/94比如在字處理軟件中，需要檢查一個英語單詞是否拼寫正確（也就是要判斷 它是否在已知的字典中）；在 FBI，一個嫌疑人的名字是否已經(jīng)在嫌疑名單上；在網(wǎng)絡(luò)爬蟲里，一個網(wǎng)址是否被訪問過等等。背景介紹2021/3/95 一般來講，計算機(jī)中的集合是用哈希表（hash t

2、able）來存儲的。 Hash函數(shù)作用就是把要存的數(shù)據(jù)映射成hash表中的一個位置，這個位置就是你要存放該數(shù)據(jù)的地方。一般把hash表的每個位置都叫做“槽（slot）”。 它的好處是快速準(zhǔn)確，缺點是浪費存儲空間。當(dāng)集合比較小時，這個問題不顯著，但是當(dāng)集合巨大時，哈希表存儲效率低的問題就顯現(xiàn)出來 了。Hash函數(shù)2021/3/96假設(shè)hash表的大小為9（即有9個槽），hash(k) = k mod 9，現(xiàn)在要把一串?dāng)?shù)據(jù)存到表里：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個關(guān)鍵字映

3、射到k個槽中，n只要大于k，一定至少有一個槽放了多于1個元素，所以不能完全避免碰撞（沖突） 。 Hash函數(shù)2852021/3/97位圖法就是Bitmap的縮寫。就是用每一位來存放某種狀態(tài)，適用于大規(guī)模數(shù)據(jù)，但數(shù)據(jù)狀態(tài)又不是很多的情況。通常是用來判斷某個數(shù)據(jù)存不存在的。 位圖法可以理解為通過一個bit數(shù)組來存儲特定數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)；由于bit是數(shù)據(jù)的最小單位，所以這種數(shù)據(jù)結(jié)構(gòu)往往是非常節(jié)省存儲空間。位圖法2021/3/98比如一個公司有8個員工，現(xiàn)在需要記錄公司的考勤記錄，傳統(tǒng)的方案是記錄下每天正?？记诘膯T工的ID列表，比如2012-01-01:1,2,3,4,5,6,7,8。 假如員工ID

4、采用byte數(shù)據(jù)類型，則保存每天的考勤記錄需要N個byte，其中N是當(dāng)天考勤的總?cè)藬?shù)。 1 2 3 4 5 6 7 8 這樣可以每天采用恒定的1個byte即可保存當(dāng)天的考勤記錄。位圖法011100112021/3/99布隆過濾器（Bloom Filter），它結(jié)合了位圖和Hash表兩者的優(yōu)點. 位圖的優(yōu)點是節(jié)省空間，但是只能處理整型值一類的問題，無法處理字符串一類的問題. 而Hash表卻恰巧解決了位圖無法解決的問題，然而Hash太浪費空間。布隆過濾器布隆過濾器2021/3/910計數(shù)計數(shù)布隆過濾器布隆過濾器 計數(shù)布隆過濾器是對基本布隆過濾器的改進(jìn)，使布隆過濾器可以支持刪除成員。 因為布隆過濾器

5、的基本單位是1個bit，只能表達(dá)2種狀態(tài)，即存在、不存在。 如果把基本單位1bit拓展成多個bit，這樣就能增加更多信息，表達(dá)出多種狀態(tài)。2021/3/911布隆過濾器 算法描述The description of its core algorithm 022021/3/912Bloom Filter 布隆過濾器（Bloom Filter）是一種概率空間高效的數(shù)據(jù)結(jié)構(gòu)。用于檢索一個元素是否在一個集合中用于檢索一個元素是否在一個集合中。 存在“在集合內(nèi)（可能錯誤）在集合內(nèi)（可能錯誤）”和“不在集合內(nèi)（絕對不不在集合內(nèi)（絕對不在集合內(nèi)）在集合內(nèi)）”兩種情況。2021/3/913 溫故知新2021/

6、3/914 核心思想核心思想就是利用多個不同的多個不同的Hash函數(shù)函數(shù)來解決“沖突”。 如何判斷某元素x是否在一個集合中？X1,X2,X3.XnRX核心思想2021/3/915算法原理 Bloom Filter需要一個位數(shù)組位數(shù)組(和位圖類似)和K個映射函數(shù)個映射函數(shù)(和Hash表類似)。包含兩種操作：插入和查詢插入和查詢1.初始化：將所有位置置02. 集合R=r1,r2.rn,通過k個相互獨立的映射函數(shù)h1,h2,.hk，將集合R中的每個元素rj(1=j 忽略碰撞并且只存儲元素是否在其中的二進(jìn)制信息時k=1的布隆過濾器2021/3/933 使用k1的布隆過濾器，即k個哈希函數(shù)將每個元素改為

7、對應(yīng)于k個bits，因為誤判度會降低很多，并且如果參數(shù)k和m選取得好，一半的m可被置為1，這充分說明了布隆過濾器的空間效率性。優(yōu)點2021/3/934 布隆過濾器可以表示全集，其它任何數(shù)據(jù)結(jié)構(gòu)都不能。 k和m相同，使用同一組散列函數(shù)的兩個布隆過濾器的交并差運算可以使用位操作進(jìn)行。優(yōu)點2021/3/935 在增加了錯誤率這個因素之后，布隆過濾器通過允許少量的錯誤來節(jié)省大量的存儲空間。優(yōu)點2021/3/936 有誤判的概率，即存在假陽性（False Position），無法獲取集合中的元素數(shù)據(jù)。 隨著存入的元素數(shù)量增加，誤算率隨之增加。但是如果元素數(shù)量太少，則使用散列表足矣。（誤判補(bǔ)救方法是：再建

8、立一個小的白名單，存儲那些可能被誤判的信息。）缺點2021/3/937 一般情況下不能從布隆過濾器中刪除元素。 另外計數(shù)器回繞也會造成問題。缺點2021/3/938布隆過濾器 改進(jìn)方案The design and application in Bloom filter052021/3/9390000000000隨機(jī)數(shù)生成器隨機(jī)數(shù)生成器F1-8f1 = F1 f2 = F2f3 = F3f4 = F4 f5 = F5f6 = F6f7 = F7f8 = F8隨機(jī)數(shù)生成器隨機(jī)數(shù)生成器G2111111110f1 = F1 = f1 f2 = F2 f3 = F3 = m2f4 = F4 = m3 f

9、5 = F5 = m4f6 = F6 = m5f7 = F7 = m6f8 = F8 = m7Counter2021/3/940Counting Bloom FilterCounting Bloom Filter的出現(xiàn)解的出現(xiàn)解決了這個問題，它將標(biāo)準(zhǔn)決了這個問題，它將標(biāo)準(zhǔn)Bloom Bloom FilterFilter位數(shù)組的每一位擴(kuò)展為一個位數(shù)組的每一位擴(kuò)展為一個小的計數(shù)器小的計數(shù)器(Counter)(Counter)，在插入元素，在插入元素時給對應(yīng)的時給對應(yīng)的k(kk(k為哈希函數(shù)個數(shù)為哈希函數(shù)個數(shù)) )個個CounterCounter的值分別加的值分別加1 1，刪除元素時，刪除元素時給對

10、應(yīng)的給對應(yīng)的k k個個CounterCounter的值分別減的值分別減1 1，Counting Bloom FilterCounting Bloom Filter通過多占用通過多占用的存儲空間的代價，給的存儲空間的代價，給Bloom Bloom FilterFilter增加了刪除操作。增加了刪除操作。1011010210BFCBF2021/3/941n n：集合元素個數(shù)，：集合元素個數(shù)，k k：HashHash函數(shù)個數(shù)，函數(shù)個數(shù)，k = 0.7 * m / n M M：位數(shù)組的大小：位數(shù)組的大小從從nknk次哈希中選擇次哈希中選擇j j次次j j次哈希都選中了第次哈希都選中了第i i個個Cou

11、nterCounter其它其它nkjnkj次哈希沒有次哈希沒有選中第選中第i i個個CounterCounter2021/3/942基本思想：基本思想：1.1.元素元素x x對應(yīng)的對應(yīng)的k k個個countercounter中的最小值中的最小值m mx x=出現(xiàn)頻率出現(xiàn)頻率f fx x2.2.f fx x m mx x的概率和標(biāo)準(zhǔn)的概率和標(biāo)準(zhǔn)bloom filterbloom filter的誤判概率相同的誤判概率相同5016111210k k個位置全個位置全部發(fā)生碰撞部發(fā)生碰撞2021/3/943索引結(jié)構(gòu)索引結(jié)構(gòu)co1co2co3co4o1o2o3o4子串長度子串長度log3N位位Coarse

12、 VectorCoarse Vectorco1co2o1o2子串長度子串長度(loglogN)3位位LOOK UP TABLEOffset VectorOffset Vector子串長度子串長度=(loglogN)3位位loglog2 2N N個個countercounterlogN/loglogNlogN/loglogN2021/3/944025701026527Counter000001000100010OverFlow Vector0000000000000001000000000000001000001111Counting Bloom Filter Vectorx=log(M/n)y

13、 = floor(log(max(OFj) + 1查詢一個查詢一個countercounter時，時，DCFDCF要要求兩次內(nèi)存訪問。假設(shè)想查求兩次內(nèi)存訪問。假設(shè)想查詢位置為詢位置為j j的的countercounter的值，的值，我們先讀出我們先讀出CBFVCBFV和和OFVOFV的值，的值，分別為分別為CjCj和和OFjOFj，那么，那么countercounter的值就可以表示為的值就可以表示為Vj = (2xVj = (2xOFj OFj Cj)Cj)。2021/3/945最大值增加至最大值增加至2x+12x+1時，每次時，每次OFVOFV大小改變的時候都需要重大小改變的時候都需要重建

14、。重建是一件開銷很大的工建。重建是一件開銷很大的工作，必須重新創(chuàng)建一個作，必須重新創(chuàng)建一個OFVOFV數(shù)數(shù)組，然后把舊組，然后把舊OFVOFV數(shù)組的值拷數(shù)組的值拷貝到新建的貝到新建的OFVOFV數(shù)組中，最后數(shù)組中，最后把舊把舊OFVOFV數(shù)組的空間釋放掉。數(shù)組的空間釋放掉。1000001000100010當(dāng)當(dāng)OFVOFV的最大值減少到的最大值減少到2x 2x 1 1時，我們可以選擇馬上重建時，我們可以選擇馬上重建OFVOFV，也可以采用一些策略延，也可以采用一些策略延遲遲OFVOFV的重建，以避免一些臨的重建，以避免一些臨時性的減少導(dǎo)致時性的減少導(dǎo)致OFVOFV反復(fù)重建。反復(fù)重建。000001

15、0000000102021/3/946布隆過濾器 設(shè)計和應(yīng)用The design and application in Bloom filter062021/3/947布隆過濾器應(yīng)用假設(shè)有一條URL，那么就先建立32個二進(jìn)制常量(取不同值，誤報率會不同)。即4字節(jié)的向量，然后將這32個二進(jìn)制位全部設(shè)置為0，對于這條URL，用8個不同的隨機(jī)數(shù)產(chǎn)生8個信息指紋，再用一個隨機(jī)數(shù)產(chǎn)生器把這8個信息指紋映射到1到32的8個自然數(shù)，并把這些位置置為1。如果要檢測某條URL是否在這個Bloom Filter中，我們?nèi)匀挥蒙鲜?個隨機(jī)數(shù)產(chǎn)生8個信息指紋，并將這8個指紋對應(yīng)到布隆過濾器的8個二進(jìn)制位，如果8位都

16、為1，則說明這條URL在這個Bloom Filter中，否則只要有一位不為1，就說明不在。Bloom Filter絕不會漏掉任何一個重復(fù)的URL，但可能會有誤報情況，雖然這種可能性很小，上述說的誤報概率只有千萬分之一，可以通過建立一個小的名單，存儲可能誤判的URL，并進(jìn)行比較。2021/3/948已爬URL的過濾代碼實現(xiàn)class BloomFilter private static final int BIT_SIZE = 2 28 ;/二進(jìn)制向量的位數(shù) private static final int seeds = new int3, 5, 7, 11, 13, 31, 37, 61;/

17、用于生成信息指紋的8個隨機(jī)數(shù)，最好選取質(zhì)數(shù) private BitSet bits = new BitSet(BIT_SIZE); private Hash func = new Hashseeds.length;/用于存儲8個隨機(jī)哈希值對象 public BloomFilter() for(int i = 0; i seeds.length; i+) funci = new Hash(BIT_SIZE, seedsi); 2021/3/949已爬URL的過濾代碼實現(xiàn)public void addValue(String value) /將字符串value哈希為8個或多個整數(shù)，然后在這些整數(shù)的

18、bit上變?yōu)? 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; 2021/3/950已爬URL的過濾代碼實現(xiàn)/*隨機(jī)哈希值對

19、象*/public static class Hash private int size;/二進(jìn)制向量數(shù)組大小 private int seed;/隨機(jī)數(shù)種子 public Hash(int cap, int seed) this.size = cap; this.seed = seed; /* 計算哈希值(也可以選用別的恰當(dāng)?shù)墓：瘮?shù)) */ public int hash(String value) int result = 0; int len = value.length(); for(int i = 0; i len; i+) result = seed * result + val

20、ue.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(); 2021/3/951計數(shù)布隆過濾器負(fù)載均衡（load balance）：將任務(wù)平攤到多個操作單元上執(zhí)行，共同完成工作。半流 ：由相同的數(shù)據(jù)包

21、組成的集合。全流：標(biāo)識的半流和標(biāo)識的半流的并集 。大部分的多媒體協(xié)議信令和數(shù)據(jù)傳輸采用的是不同的端口。傳統(tǒng)的負(fù)載均衡算法不能保證將多媒體會話映射到一個處理核上。因此應(yīng)該根據(jù)流的信息動態(tài)調(diào)整映射位置。通過增加DP、SP的端口信息生成信息摘要，通過布隆過濾器直接映射到同一個處理器上面。2021/3/952計數(shù)布隆過濾器將需要調(diào)整的全流標(biāo)識生成對應(yīng)的摘要信息Digest，將其保存到精確流匹配布隆過濾器中，對于每一個到來的 IP數(shù)據(jù)包，提取標(biāo)識并生成 Digest然后根據(jù)和 Digest查詢 ESBF結(jié)構(gòu) ，如果在其中，則轉(zhuǎn)發(fā)到指定的處理核 否則 ，對 Digest取模得到對應(yīng)的處理核 ID。通過保存

22、全流的標(biāo)識到哈希表中 ，可以動態(tài)指定某個全流到相應(yīng)的處理核2021/3/953計數(shù)布隆過濾器ESBF算法基于 CBF,利用 CBF的多個哈希函數(shù)保證算法具有更低的沖突概率,CBF可以高效的根據(jù)(DA, SA, DP, SP)和k個哈希函數(shù)對IP包映射到不同的CPU上面進(jìn)行處理。同時也可以對索引記錄高效的插入和刪除。動態(tài)更改處理IP包的CPU。 2021/3/954計數(shù)布隆過濾器插入算法代碼如下：Insertelem(x，id)Digest DIGEST HASH(x)；創(chuàng)建鏈表結(jié)點并將 digest、id域賦值 ；for(i=l to k)ifLinkheadbi(x)counter=0)將結(jié)點添加到鏈表尾部；elseif(鏈表長度為 co