Bloom Filter簡述

1.适用場景

在極大的資料集合中快速查找某個元素是否存在,但是不要求100%正确.這個是文绉绉的說法,說人話: 一個很理想的場景:分布式緩存

緩存的資料可能很大,QPS也相當的高,比如千萬級,那麼一般這個緩存叢集就會達到近百台機器的規模.能不能少點機器呢? 畢竟找老闆要這麼多機器,不容易啊,動不動就是KPI導向!

這個時候Bloom Filter就可以上場了

2.橫向對比

為了查找某元素是否出現,一般有哪些方法呢?

• 将所有的資料存起來(比如存資料庫),然後直接查詢呗: 第一是存不下,第二是找不快
• 使用Hash結構存儲:更加存不下,一般hash空間使用率<=50%, 資料量大了,Hash碰撞也不容小觑
• 将原始資料md5或者SHA-1,再存hash:MD5結果128Bit, SHA-1結果160Bit,确實比上面的靠譜多了
• 位向量(将資料哈希值對應的bit位置1):可查證資料顯示,要降低沖突發生的機率到1%，就要将BitSet的長度設定為資料總數量的100倍

以上方法都是能百分百準确找到或者找不到元素,空間上多少不盡如人意,但是能百分百準确!可是作為一個緩存伺服器,百分百的準确性,有必要麼? 為了百分百的準确,多花了多少存儲啊!緩存命不中,又不懷孕,是吧? 如果降低5%的準确率,能省20%甚至40%的機器呢?是不是更劃算!

3.Bloom Filter原理

布隆過濾器首先是基于上面的方法4,位向量,判斷資料的哈希值對應的bit是否為1

改進點在于,使用多個哈希函數,而不是一個

比如資料

aaa

index1=func_hash_1(aaa)

index2=func_hash_2(aaa)

那麼同時判斷

bitset[index1]

和

bitset[index2]

是否同時為1,就能

大緻

知道aaa是否存在.

判斷規則:

• 隻要bitset[index1]活着bitset[index2]任意一個為0,表示資料aaa不存在
• bitset[index1],bitset[index2]全部同時為1,資料aaa

  可能

  存在

  為什麼所有的都是1了,隻是可能存在呢?仔細想想,每個資料都會被映射到2個标志位,可能剛好index1标志位與bbb的其中一個碰撞(重疊),剛好index2标志位與ccc的其中一個标志位碰撞(重疊).

  再直白一點 

  A=func1(aaa)

  ,  

  B=func2(aaa)

  ,  

  C=func1(bbb)

  ,  

  D=func2(bbb)

  ,AB是資料aaa産生的兩個标志位,CD是資料bbb産生的兩個标志位.然而很可能

  aaa

  和

  bbb

  原始資料都不存在,而是

  A=func2(ccc)

  ,  

  B=func1(ddd)

  ,  

  C=func2(eee)

  ,  

  D=func1(fff)

  ,意思是ccc,ddd,eee,fff分别有一個标志位與aaa,bbb碰撞(重疊),其實aaa,bbb壓根不存在

4.Counting Bloom Filter

上面已經舉例分析,布隆過濾器存在不準确性,可能誤報.誤報率是多少,有興趣額的可以查查,公式就不貼了.

此處另外一個問題,資料一旦寫入集合,就不能删除,原因同上面:

ccc,eee,fff,ddd能碰撞虛構出aaa,bbb存在的假象; 那麼你删除ccc,ddd,eee,fff時将ABCD标志位置0,也就能虛構aaa,bbb不存在的假象,而此時aaa,bbb可能恰好又倒黴催的真實存在

Counting bloomfilter(CBF)，這是一種基本Bloom Filter的變體，CBF将基本Bloom Filter每一個Bit改為一個計數器,出現一個加1,删除一個減1,此時就支援删除資料了

5.數學細節

關于

錯誤率估算

,

最優的哈希函數個數

,

位數組的大小

,這幾個值如何計算調優?鄙人數學不精,不推理公式了,有興趣的搜尋一把,應有盡有