布隆過濾器、計數(shù)布隆過濾器及其應用

《布隆過濾器、計數(shù)布隆過濾器及其應用》由會員分享，可在線閱讀，更多相關《布隆過濾器、計數(shù)布隆過濾器及其應用（57頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、信息安全課程報告Bloom filter - The course report of Information security布隆過濾器組長： 匯報人： 目錄CONTENTS 1 背景介紹2 算法描述3 誤判概率證明和計算4 優(yōu)劣詳解6 布隆過濾器設計和應用5 布隆過濾器改進方案 布隆過濾器 背景介紹The background of Bloom filter 01 比 如 在 字 處 理 軟 件 中 ， 需 要 檢 查 一 個 英 語 單 詞 是 否 拼 寫 正 確 （ 也 就 是 要 判 斷 它 是 否 在 已 知 的 字 典 中 ） ；在 FBI， 一 個 嫌 疑 人 的 名 字 是

2、否 已 經 在 嫌 疑 名 單 上 ；在 網(wǎng) 絡 爬 蟲 里 ， 一 個 網(wǎng) 址 是 否 被 訪 問 過 等 等 。背景介紹 一 般 來 講 ， 計 算 機 中 的 集 合 是 用 哈 希 表 （ hash table） 來 存 儲 的 。 Hash函 數(shù) 作 用 就 是 把 要 存 的 數(shù) 據(jù) 映 射 成 hash表 中 的 一 個 位 置 ， 這 個 位置 就 是 你 要 存 放 該 數(shù) 據(jù) 的 地 方 。 一 般 把 hash表 的 每 個 位 置 都 叫 做 “ 槽（ slot） ” 。 它 的 好 處 是 快 速 準 確 ， 缺 點 是 浪 費 存 儲 空 間 。 當 集 合 比 較

3、 小 時 ， 這 個 問題 不 顯 著 ， 但 是 當 集 合 巨 大 時 ， 哈 希 表 存 儲 效 率 低 的 問 題 就 顯 現(xiàn) 出 來 了 。Hash函數(shù) 假 設 hash表 的 大 小 為 9（ 即 有 9個 槽 ） ， hash(k) = k mod 9， 現(xiàn) 在 要 把 一串 數(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個 關 鍵 字 映 射 到 k個 槽 中 ， n只 要 大 于 k， 一 定 至 少 有 一 個 槽 放 了 多 于 1

4、個 元素 ， 所 以 不 能 完 全 避 免 碰 撞 （ 沖 突 ） 。 Hash函數(shù) 2 8 5 位 圖 法 就 是 Bitmap的 縮 寫 。 就 是 用 每 一 位 來 存 放 某 種 狀 態(tài) ， 適 用 于大 規(guī) 模 數(shù) 據(jù) ， 但 數(shù) 據(jù) 狀 態(tài) 又 不 是 很 多 的 情 況 。 通 常 是 用 來 判 斷 某 個 數(shù) 據(jù) 存不 存 在 的 。 位 圖 法 可 以 理 解 為 通 過 一 個 bit數(shù) 組 來 存 儲 特 定 數(shù) 據(jù) 的 一 種 數(shù) 據(jù) 結 構 ；由 于 bit是 數(shù) 據(jù) 的 最 小 單 位 ， 所 以 這 種 數(shù) 據(jù) 結 構 往 往 是 非 常 節(jié) 省 存 儲 空

5、 間 。位圖法 比 如 一 個 公 司 有 8個 員 工 ， 現(xiàn) 在 需 要 記 錄 公 司 的 考 勤 記 錄 ， 傳 統(tǒng)的 方 案 是 記 錄 下 每 天 正 常 考 勤 的 員 工 的 ID列 表 ， 比 如 2012-01-01:1,2,3,4,5,6,7,8。 假 如 員 工 ID采 用 byte數(shù) 據(jù) 類 型 ， 則 保 存 每 天 的 考 勤 記 錄 需 要 N個byte， 其 中 N是 當 天 考 勤 的 總 人 數(shù) 。 1 2 3 4 5 6 7 8 這 樣 可 以 每 天 采 用 恒 定 的 1個 byte即 可 保 存 當 天 的 考 勤 記 錄 。位圖法 0 1 1 1

6、 0 0 1 1 布 隆 過 濾 器 （ Bloom Filter） ， 它 結 合 了 位 圖 和 Hash表兩 者 的 優(yōu) 點 . 位 圖 的 優(yōu) 點 是 節(jié) 省 空 間 ， 但 是 只 能 處 理 整 型 值 一 類 的 問 題 ，無 法 處 理 字 符 串 一 類 的 問 題 . 而 Hash表 卻 恰 巧 解 決 了 位 圖 無 法 解 決 的 問 題 ， 然 而 Hash太 浪 費 空 間 。布 隆 過 濾 器 計 數(shù) 布 隆 過 濾 器 計 數(shù) 布 隆 過 濾 器 是 對 基 本 布 隆 過 濾 器 的 改 進 ， 使 布 隆 過 濾 器 可 以 支持 刪 除 成 員 。 因 為

7、 布 隆 過 濾 器 的 基 本 單 位 是 1 個 bit， 只 能 表 達 2 種 狀 態(tài) ，即 存 在 、 不 存 在 。 如 果 把 基 本 單 位 1 bit拓 展 成 多 個 bit， 這 樣 就 能 增 加 更多 信 息 ， 表 達 出 多 種 狀 態(tài) 。 布隆過濾器 算法描述The description of its core algorithm 02 Bloom Filter 布 隆 過 濾 器 （ Bloom Filter） 是 一 種 概 率 空 間 高 效 的 數(shù) 據(jù) 結構 。 用 于 檢 索 一 個 元 素 是 否 在 一 個 集 合 中 。 存 在 “在 集 合

8、內 （ 可 能 錯 誤 ） ”和 “不 在 集 合 內 （ 絕 對 不 在 集合 內 ） ”兩 種 情 況 。 溫故知新 核 心 思 想 就 是 利 用 多 個 不 同 的 Hash函 數(shù) 來 解 決 “ 沖 突 ” 。 如 何 判 斷 某 元 素 x是 否 在 一 個 集 合 中 ？ X1 ,X2 ,X3 .Xn RX核心思想 算法原理 Bloom Filter需 要 一 個 位 數(shù) 組 (和 位 圖 類 似 )和 K個 映 射 函 數(shù) (和 Hash表 類似 )。 包 含 兩 種 操 作 ： 插 入 和 查 詢1 .初 始 化 ： 將 所 有 位 置 02 . 集 合 R=r1 ,r2 .

9、rn,通 過 k個 相 互 獨 立 的 映 射 函 數(shù) h1 ,h2 ,.hk， 將 集 合 R中 的 每 個 元 素 rj(1 =j 忽略碰撞并且只存儲元素是否在其中的二進制信息時 k=1的布隆過濾器 使用k1的布隆過濾器，即k個哈希函數(shù)將每個元素改為對應于k個bits，因為誤判度會降低很多，并且如果參數(shù)k和m選取得好，一半的m可被置為1，這充分說明了布隆過濾器的空間效率性。優(yōu)點 布隆過濾器可以表示全集，其它任何數(shù)據(jù)結構都不能。 k和m相同，使用同一組散列函數(shù)的兩個布隆過濾器的交并差運算可以使用位操作進行。優(yōu)點 在增加了錯誤率這個因素之后，布隆過濾器通過允許少量的錯誤來節(jié)省大量的存儲空間。優(yōu)

10、點 有誤判的概率，即存在假陽性（False Position），無法獲取集合中的元素數(shù)據(jù)。 隨著存入的元素數(shù)量增加，誤算率隨之增加。但是如果元素數(shù)量太少，則使用散列表足矣。（誤判補救方法是：再建立一個小的白名單，存儲那些可能被誤判的信息。）缺點 一般情況下不能從布隆過濾器中刪除元素。 另外計數(shù)器回繞也會造成問題。缺點 布隆過濾器 改進方案The design and application in Bloom filter 05 0 0 0 0 0 0 0 0 0 01億郵箱 隨 機 數(shù) 生 成 器F1 -8 f1 = F1 f2 = F2f3 = F3f4 = F4 f5 = F5f6 = F

11、6f7 = F7f8 = F8信息 指紋隨 機 數(shù) 生 成 器 G1 0 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 0f1 = F1 = f1 f2 = F2 f3 = F3 = m2f4 = F4 = m3 f5 = F5 = m4f6 = F6 = m5f7 = F7 = m6f8 = F8 = m7Counter Counting Bloom Filter的 出 現(xiàn) 解決 了 這 個 問 題 ， 它 將 標 準 Bloom Filter位 數(shù) 組 的 每 一 位 擴 展 為 一 個小 的 計 數(shù) 器 (Counter)， 在 插 入 元 素時 給 對 應 的 k(k

12、為 哈 希 函 數(shù) 個 數(shù) )個Counter的 值 分 別 加 1， 刪 除 元 素 時給 對 應 的 k個 Counter的 值 分 別 減 1，Counting Bloom Filter通 過 多 占 用的 存 儲 空 間 的 代 價 ， 給 Bloom Filter增 加 了 刪 除 操 作 。 10110 10210BF CBF n： 集 合 元 素 個 數(shù) ，k： Hash函 數(shù) 個 數(shù) ， k = 0 .7 * m / n M： 位 數(shù) 組 的 大 小從 nk次 哈 希 中 選 擇 j次j次 哈 希 都 選 中 了 第 i個 Counter其 它 nk j次 哈 希 沒 有選 中

13、 第 i個 Counter 基 本 思 想 ：1.元 素 x對 應 的 k個 counter中 的 最 小 值 mx=出 現(xiàn) 頻 率 fx2.fx mx的 概 率 和 標 準 bloom filter的 誤 判 概 率 相 同5 0 1 6 1 1 1 2 1 0k個 位 置 全部 發(fā) 生 碰 撞 索 引 結 構co1 co2 co3 co4o1 o2 o3 o4 子 串 長 度 log3 N位Coarse Vectorco1 co2 o1 o2 子 串 長 度 (loglogN)3 位 LOOK UP TABLEOffset Vector 子 串 長 度 =(loglogN)3 位 log2

14、N個 counterlogN/loglogN 02 5 701 0 2 65 2 7Counter 0 0 00 0 10 0 01 0 00 1 0OverFlow Vector 0 0 0 0 0 0 0 00 0 0 0 0 0 0 10 0 0 0 0 0 0 00 0 0 0 0 0 1 00 0 0 0 1 1 1 1Counting Bloom Filter Vectorx=log(M/n)y = floor(log(max(OFj) + 1 查 詢 一 個 counter時 ， DCF要求 兩 次 內 存 訪 問 。 假 設 想 查詢 位 置 為 j的 counter的 值 ，

15、我 們 先 讀 出 CBFV和 OFV的 值 ，分 別 為 Cj和 OFj， 那 么counter的 值 就 可 以 表 示 為Vj = (2x OFj Cj)。 最 大 值 增 加 至 2x+1時 ， 每 次OFV大 小 改 變 的 時 候 都 需 要 重建 。 重 建 是 一 件 開 銷 很 大 的 工作 ， 必 須 重 新 創(chuàng) 建 一 個 OFV數(shù)組 ， 然 后 把 舊 OFV數(shù) 組 的 值 拷貝 到 新 建 的 OFV數(shù) 組 中 ， 最 后把 舊 OFV數(shù) 組 的 空 間 釋 放 掉 。 1 0 0 00 0 10 0 01 0 00 1 0 當 OFV的 最 大 值 減 少 到 2x

16、 1時 ， 我 們 可 以 選 擇 馬 上 重 建OFV， 也 可 以 采 用 一 些 策 略 延遲 OFV的 重 建 ， 以 避 免 一 些 臨時 性 的 減 少 導 致 OFV反 復 重 建 。0 0 00 0 10 0 00 0 00 1 0 布隆過濾器 設計和應用The design and application in Bloom filter 06 布隆過濾器應用假設有一條URL，那么就先建立32個二進制常量(取不同值，誤報率會不同)。即4字節(jié)的向量，然后將這32個二進制位全部設置為0，對于這條URL，用8個不同的隨機數(shù)產生8個信息指紋，再用一個隨機數(shù)產生器把這8個信息指紋映射到1

17、到32的8個自然數(shù)，并把這些位置置為1。如果要檢測某條URL是否在這個Bloom Filter中，我們仍然用上述8個隨機數(shù)產生8個信息指紋，并將這8個指紋對應到布隆過濾器的8個二進制位，如果8位都為1，則說明這條URL在這個Bloom Filter中，否則只要有一位不為1，就說明不在。 Bloom Filter絕不會漏掉任何一個重復的URL，但可能會有誤報情況，雖然這種可能性很小，上述說的誤報概率只有千萬分之一，可以通過建立一個小的名單，存儲可能誤判的URL，并進行比較。 已爬URL的過濾代碼實現(xiàn)class BloomFilter private static final int BIT_SI

18、ZE = 2 28 ;/二進制向量的位數(shù) private static final int seeds = new int3, 5, 7, 11, 13, 31, 37, 61;/用于生成信息指紋的8個隨機數(shù)，最好選取質數(shù) 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, seeds

19、i); 已爬URL的過濾代碼實現(xiàn)public void addValue(String value) /將字符串value哈希為8個或多個整數(shù)，然后在這些整數(shù)的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) re

20、t = ret return ret; 已爬URL的過濾代碼實現(xiàn)/*隨機哈希值對象*/public static class Hash private int size;/二進制向量數(shù)組大小 private int seed;/隨機數(shù)種子 public Hash(int cap, int seed) this.size = cap; this.seed = seed; /* 計算哈希值(也可以選用別的恰當?shù)墓：瘮?shù)) */ public int hash(String value) int result = 0; int len = value.length(); for(int i = 0;

21、 i len; i+) result = seed * result + value.charAt(i); return (size - 1) 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(); 計數(shù)布隆過濾器負 載 均 衡 （ load balance） ： 將 任 務 平 攤 到

22、 多 個 操 作 單 元 上 執(zhí) 行 ， 共 同 完 成 工 作 。半 流 ： 由 相 同 的 數(shù) 據(jù) 包 組 成 的 集 合 。全 流 ： 標 識 的 半 流 和 標 識 的 半 流 的 并 集 。大 部 分 的 多 媒 體 協(xié) 議 信 令 和 數(shù) 據(jù) 傳 輸 采 用 的 是 不 同 的 端 口 。傳 統(tǒng) 的 負 載 均 衡 算 法 不 能 保 證 將 多 媒 體 會 話 映 射 到 一 個 處 理 核 上 。 因 此 應 該 根 據(jù) 流 的 信 息 動 態(tài) 調 整 映 射 位 置 。 通 過 增 加 DP、 SP的 端 口 信 息 生 成 信 息 摘 要 ，通 過 布 隆 過 濾 器 直

23、接 映 射 到 同 一 個 處 理 器 上 面 。 計數(shù)布隆過濾器將 需 要 調 整 的 全 流 標 識 生 成 對 應 的 摘 要 信 息 Digest，將 其 保 存 到 精 確 流 匹 配 布 隆 過 濾 器 中 ， 對 于 每 一 個 到 來的 IP數(shù) 據(jù) 包 ， 提 取 標 識 并 生 成 Digest然 后 根 據(jù) 和 Digest查 詢 ESBF結 構 ， 如果 在 其 中 ， 則 轉 發(fā) 到 指 定 的 處 理 核 否 則 ， 對 Digest取 模 得 到 對 應 的 處 理 核 ID。 通 過 保 存 全流 的 標 識 到 哈 希 表 中 ， 可 以 動 態(tài) 指 定 某 個

24、 全 流 到 相 應 的處 理 核 計數(shù)布隆過濾器 ESBF算 法 基 于 CBF,利 用 CBF的 多 個 哈 希函 數(shù) 保 證 算 法 具 有 更 低 的 沖 突 概 率 ,CBF可 以 高 效 的 根 據(jù) (DA, SA, DP, SP)和 k個 哈 希 函 數(shù)對 IP包 映 射 到 不 同 的 CPU上 面 進 行 處 理 。同 時 也 可 以 對 索 引 記 錄 高 效 的 插 入 和 刪 除 。動 態(tài) 更 改 處 理 IP包 的 CPU。 計數(shù)布隆過濾器插 入 算 法 代 碼 如 下 ：Insertelem(x， id)Digest DIGEST HASH(x)；創(chuàng) 建 鏈 表 結

25、 點 并 將 digest、 id域 賦 值 ；for(i=l to k)ifLinkheadbi(x) counter=0 )將 結 點 添 加 到 鏈 表 尾 部 ；elseif(鏈 表 長 度 為 counter)將 結 點 添 加 到 鏈 表 尾 部 ；else 將 結 點 添 加 到 鏈 表 頭 部 ； )Linkhead(h。 (x) counter+； )插 入 算 法 將 由 生 成 的 Digest依 次插 入 到 k個 鏈 表 之 中 。 為 了 節(jié) 省 空 間 ， 如 果 結 點都 添 加 到 鏈 表 尾 部 ， 則 k個 鏈 表 可 以 共 享 一 個 鏈表 結 點 。

26、 計數(shù)布隆過濾器 刪 除 算 法 代 碼 如 下 ：Deletelem(x)Digest DIGEST HASH(x)；for(i=1 to k)j=O；while(jLinkheadh (x) counter)if(結 點 中 的 digest域 與 Digest相 等 )將 結 點 從 鏈 表 中 刪 除 ， 跳 出 循 環(huán) ；j+； Linkhead(h。 (x) Counter一 ； 刪 除 算 法 將 k個 鏈 表 中 結 點 digest的 值 與 生 成 的 Digest相 等 的 結 點 從 鏈 表 中 依 次 刪 除 。 計數(shù)布隆過濾器 查 詢 算 法 代 碼 如 下 ：Lo

27、okup(x)Digest DIGEST HASH(x)；for(i=l to k)if(Linkhead(h， (x) counter=0 )return false；J-k個 counter中 最 小 值 對 應 的 hi(x)for(i： 1 to LinkheadD counter)i結 點 中 的 digest域 與 Digest相 等 )return 結 點 的 id域 ； return false； )查 詢 算 法 取 k個 計 數(shù) 器 中 值 最 小 的 計 數(shù) 器 所 對 應 的 鏈 表進 行 比 較 ， 最 壞 情 況 下 比 較 的 次 數(shù) 為 該 最 小 計 數(shù) 器 的 值 。 感謝聆聽，批評指導THANK YOU TO LISTEN TO CRITICISM GUIDANCE布隆過濾器組長： 匯報人：