Bloom過濾器

引文

思考一個(gè)問題：從大量數(shù)據(jù)里面如何高效率地去重？
有過一點(diǎn)編程經(jīng)驗(yàn)的人都知道，可以通過Set這種數(shù)據(jù)結(jié)構(gòu)來做到。比如HashSet，采用了Hash算法，可以在O(1)的復(fù)雜度完成數(shù)據(jù)的添加和查詢操作。確實(shí)，大多數(shù)情況，這也是我們會(huì)采取的方案。但是因?yàn)镾et需要保存源數(shù)據(jù)信息，且有Hash沖突，當(dāng)樣本數(shù)據(jù)量特別龐大的情況下，比如有千萬甚至上億的數(shù)據(jù)量時(shí)，這種方式顯得有些不切實(shí)際。

布隆過濾器

布隆過濾器(Bloom Filter)的思想跟Hashmap有部分類似，也是通過hash函數(shù)映射的方式保存樣本信息，不一樣的是它依賴的數(shù)據(jù)結(jié)構(gòu)是一個(gè)位數(shù)組，數(shù)組每一位上要么是0，要么是1，初始狀態(tài)全是0。

位數(shù)組

當(dāng)要往過濾器添加一個(gè)元素的時(shí)候，我們需要n(n是正整數(shù))個(gè)獨(dú)立的hash函數(shù)給目標(biāo)元素做哈希運(yùn)算，然后我們將得到的n個(gè)結(jié)果分別映射到位數(shù)組上。
舉個(gè)簡(jiǎn)單的例子，假設(shè)我們要添加元素的元素是數(shù)字，我們?nèi)為3，選取的3個(gè)hash函數(shù)分別是

  1. hash_{1}(x) = (x ^ 2)%20
  2. hash_{2}(x) = (x ^ 3)%20
  3. hash_{3}(x) = (x ^ 4)%20

當(dāng)添加7這個(gè)元素的時(shí)候，通過三個(gè)hash函數(shù)計(jì)算的結(jié)果分別是9，3和1，我們把位數(shù)組對(duì)應(yīng)下標(biāo)的元素記為1。

元素7的指紋信息

這樣元素7就在位數(shù)組上以9，3和1三個(gè)位置信息的形式，存儲(chǔ)了起來。后續(xù)所有的元素都經(jīng)過三個(gè)hash函數(shù)，映射到位數(shù)組上。于是當(dāng)我們要判斷某個(gè)元素是否存在的時(shí)候，我們?nèi)?shù)組上此元素應(yīng)該在的位置處查看，對(duì)應(yīng)的數(shù)字是否都為1。如果有數(shù)字為0，那么元素肯定不存在。如果數(shù)字都為1，那么元素大概率存在。

算法研究

布隆過濾器是一種概率數(shù)據(jù)結(jié)構(gòu)(probabilistic data structure)，可能會(huì)出現(xiàn)誤判，但不會(huì)漏判。因?yàn)椴煌氐膆ash結(jié)果可能會(huì)相同，而且被映射位置的數(shù)字可能已經(jīng)被其他元素置為1，所以我們不能判斷某個(gè)元素一定重復(fù)。

Hash函數(shù)

過濾器需要一系列獨(dú)立的hash函數(shù)，函數(shù)的目標(biāo)是將輸出均勻地打散在目標(biāo)域上。也就是說，元素通過hash函數(shù)映射到位數(shù)組上任何位置的概率應(yīng)該是相同的。另外還有重要的一點(diǎn)，就是算法速度要快，過濾器的性能很大程度上取決于hash函數(shù)的性能。好的hash函數(shù)能在保持良好時(shí)間效率的情況下，降低過濾器的誤判率。其中比較知名的是MurmurHash, FNV Hash, MD5

參數(shù)選擇

一個(gè)合格的布隆過濾器，需要有很高的空間時(shí)間效率，較低并且可控的誤判率。從而我們很容易發(fā)現(xiàn)幾個(gè)問題。

  1. 如何選取位數(shù)組長(zhǎng)度m。m越大，占用的空間越大；m越小，誤判的幾率越高。
  2. 如何選取hash函數(shù)個(gè)數(shù)k。k越大，數(shù)組越快被占滿從而誤判率越高；k越小，產(chǎn)生hash沖突的概率越大，導(dǎo)致誤判率也越高。

對(duì)于上述的問題，切入點(diǎn)是最小化誤差率。怎樣是誤差？不就是當(dāng)查詢一個(gè)未重復(fù)元素的時(shí)候，對(duì)應(yīng)映射的位置已經(jīng)都為1了嗎。對(duì)于長(zhǎng)度為m的位數(shù)組，某個(gè)位置被設(shè)為1的概率是\frac{1}{m}，所以這個(gè)位置仍然為0的概率是

1-\frac{1}{m}

每個(gè)元素都會(huì)有k個(gè)hash映射，假設(shè)所有的hash結(jié)果相互獨(dú)立，當(dāng)數(shù)組已經(jīng)添加了n個(gè)元素的時(shí)候，該位置依然為0的概率是

(1-\frac{1}{m})^{kn}

于是這個(gè)位置已經(jīng)是1了的概率是

1-(1-\frac{1}{m})^{kn}

所以對(duì)于某個(gè)元素做k次hash映射，對(duì)應(yīng)位置都已為1的概率，即誤判率P_f為

P_f=(1-(1-\frac{1}{m})^{kn})^k

因?yàn)?/p>

\lim\limits_{x \to \infty} (1-\frac{1}{x})^x=\frac{1}{e}

所以當(dāng)數(shù)據(jù)量很大的時(shí)候，誤判率可以近似的表示為

P_f\approx(1-e^\frac{-kn}{m})^k

對(duì)于給定的m和n，可以解出當(dāng)P_f達(dá)到極小值也就是最優(yōu)值時(shí)，k的取值為

k=\frac{m}{n}ln2

將這個(gè)結(jié)果代入到原來的表達(dá)式中消去k，最終可以得到

lnP_f=-\frac{m}{n}(ln2)^2

從而得到最優(yōu)位數(shù)組的大小

m=-\frac{nlnP_f}{(ln2)^2}

舉個(gè)例子，當(dāng)我們預(yù)估樣本數(shù)量大小n為5,000,000的時(shí)候，期望過濾器有低于1%的誤判率，依據(jù)以上兩個(gè)公式，我們可以算出理想的位數(shù)組長(zhǎng)度為

m=-\frac{nlnP_f}{(ln2)^2}=-\frac{5,000,000*ln0.01}{(ln2)^2}\approx47,925,292

最優(yōu)hash函數(shù)個(gè)數(shù)為

k=\frac{m}{n}ln2=\frac{47,925,292}{5,000,000}ln2\approx7

也就是說在這種情況下我們可以將位數(shù)組長(zhǎng)度為設(shè)置為47,925,292，并且選擇7個(gè)hash函數(shù)來達(dá)到目標(biāo)。

布隆過濾器的優(yōu)勢(shì)

時(shí)間效率高

因?yàn)槭峭ㄟ^數(shù)組下標(biāo)查詢，對(duì)每個(gè)hash函數(shù)映射結(jié)果查詢的時(shí)間復(fù)雜度都是O(1)。而且各個(gè)hash函數(shù)都是不相關(guān)的，查詢?nèi)蝿?wù)可以并行地處理，充分地發(fā)揮計(jì)算機(jī)多核多線程的優(yōu)勢(shì)，甚至可以利用分布式的計(jì)算力來進(jìn)一步優(yōu)化效率。

占用內(nèi)存小

對(duì)于給定的誤判率1%，每個(gè)元素的存儲(chǔ)通常不會(huì)超過10字節(jié)。相較于Hashset之類的要保存源元素的數(shù)據(jù)結(jié)構(gòu)來說，無論元素的原始大小是多少，布隆過濾器的大小都是恒定的，一般只需要10%-25%的內(nèi)存占用。

信息安全

布隆過濾器并不保存源信息，而是保存源信息的幾個(gè)hash指紋，所以有非常好的保密性，非常適合對(duì)信息比較敏感的場(chǎng)景。

布隆過濾器的不足

誤判

作為一種概率數(shù)據(jù)結(jié)構(gòu)，誤判應(yīng)該是最大的缺點(diǎn)了。不過我們還是可以通過選取適當(dāng)?shù)膮?shù)，將誤判率控制在一定的可接受范圍內(nèi)。

無法刪除數(shù)據(jù)

因?yàn)閔ash沖突的存在，當(dāng)考慮要?jiǎng)h除某個(gè)元素的時(shí)候，我們不能簡(jiǎn)單地把相應(yīng)映射位置的數(shù)字記為0，因?yàn)楹芸赡苡衅渌匾灿成涞搅诉@些位置。如下圖，3和7元素都映射到了1和9兩個(gè)位置，當(dāng)把7對(duì)應(yīng)位置的元素置為0的時(shí)候，也影響到了元素3。

hash沖突

一些布隆過濾器的變體，如計(jì)數(shù)布隆過濾器(Counting Bloom Filter)，穩(wěn)定布隆過濾器(Stable Bloom Filter)可以支持元素的刪除，但是是通過犧牲空間效率或準(zhǔn)確性來達(dá)成的。

應(yīng)用場(chǎng)景

綜合布隆過濾器的優(yōu)劣，我們可以知道過濾器的適用場(chǎng)景大致有幾個(gè)特點(diǎn)

  • 對(duì)誤判有一定的容忍度
  • 樣本的數(shù)量比較龐大
  • 對(duì)時(shí)間空間效率要求比較高
  1. 避免緩存穿透
    將緩存的數(shù)據(jù)放到布隆過濾器里面，當(dāng)請(qǐng)求一個(gè)一定不存在的資源的時(shí)候，在過濾器層便可把請(qǐng)求返回，從而防止緩存穿透攻擊導(dǎo)致DB癱瘓。如：Bigtable, Apache HBase
  2. 垃圾郵件/黑名單/危險(xiǎn)網(wǎng)站 的過濾
    將所有被標(biāo)記為垃圾郵件的郵箱地址存到過濾器里，當(dāng)收到新郵件時(shí)，如果發(fā)現(xiàn)發(fā)件人在過濾器里則自動(dòng)拉入垃圾郵箱。因?yàn)檎`判的存在，所以有時(shí)候我們會(huì)發(fā)現(xiàn)正常的郵件會(huì)被歸入垃圾郵件。如：瀏覽器，郵件系統(tǒng)
  3. URL的去重
    對(duì)于某些網(wǎng)頁爬蟲程序，把已經(jīng)處理過的URL放到過濾器里面，可以減少爬蟲的很多重復(fù)工作。
  4. 用戶喜好推送系統(tǒng)
    根據(jù)用戶的瀏覽記錄，給用戶發(fā)一些推送。我們可以把所有用戶的瀏覽記錄放到過濾器里面，保證推送不重復(fù)。如：Medium

總結(jié)

布隆過濾器是一個(gè)時(shí)間空間效率都很高的過濾器，但是會(huì)有一定的誤判率。在海量數(shù)據(jù)的處理場(chǎng)景中有廣泛的應(yīng)用。

參考

Bloom Filter
Bloom Filters by Example

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容