布隆過濾器、計(jì)數(shù)布隆過濾器及其應(yīng)用

《布隆過濾器、計(jì)數(shù)布隆過濾器及其應(yīng)用》由會(huì)員分享，可在線閱讀，更多相關(guān)《布隆過濾器、計(jì)數(shù)布隆過濾器及其應(yīng)用（57頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

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

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

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

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

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

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

11、6f7 = F7f8 = F8信息 指紋隨 機(jī) 數(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) 解決 了 這 個(gè) 問 題 ， 它 將 標(biāo) 準(zhǔn) Bloom Filter位 數(shù) 組 的 每 一 位 擴(kuò) 展 為 一 個(gè)小 的 計(jì) 數(shù) 器 (Counter)， 在 插 入 元 素時(shí) 給 對(duì) 應(yīng) 的 k(k

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

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

14、N個(gè) 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 查 詢 一 個(gè) counter時(shí) ， DCF要求 兩 次 內(nèi) 存 訪 問 。 假 設(shè) 想 查詢 位 置 為 j的 counter的 值 ，

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

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

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

18、ZE = 2 28 ;/二進(jìn)制向量的位數(shù) private static final int seeds = new int3, 5, 7, 11, 13, 31, 37, 61;/用于生成信息指紋的8個(gè)隨機(jī)數(shù)，最好選取質(zhì)數(shù) private BitSet bits = new BitSet(BIT_SIZE); private Hash func = new Hashseeds.length;/用于存儲(chǔ)8個(gè)隨機(jī)哈希值對(duì)象 public BloomFilter() for(int i = 0; i seeds.length; i+) funci = new Hash(BIT_SIZE, seeds

19、i); 已爬URL的過濾代碼實(shí)現(xiàn)public void addValue(String value) /將字符串value哈希為8個(gè)或多個(gè)整數(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; /將要比較的字符串重新以上述方法計(jì)算hash值，再與布隆過濾器比對(duì) for(Hash f : func) re

20、t = ret return ret; 已爬URL的過濾代碼實(shí)現(xiàn)/*隨機(jī)哈希值對(duì)象*/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; /* 計(jì)算哈希值(也可以選用別的恰當(dāng)?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(); 計(jì)數(shù)布隆過濾器負(fù) 載 均 衡 （ load balance） ： 將 任 務(wù) 平 攤 到

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

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

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

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

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

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