Bloom Filter 是什么？

先簡單的介紹下Bloom Filter（布隆過濾器）是1970年由布隆提出的。它實際上是一個很長的二進(jìn)制向量和一系列隨機映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都遠(yuǎn)遠(yuǎn)超過一般的算法，缺點是有一定的誤識別率和刪除困難。

在計算機科學(xué)中，我們常常會碰到時間換空間或者空間換時間的情況，即為了達(dá)到某一個方面的最優(yōu)而犧牲另一個方面。Bloom Filter在時間空間這兩個因素之外又引入了另一個因素：錯誤率。在使用Bloom Filter判斷一個元素是否屬于某個集合時，會有一定的錯誤率。也就是說，有可能把不屬于這個集合的元素誤認(rèn)為屬于這個集合（False Positive），但不會把屬于這個集合的元素誤認(rèn)為不屬于這個集合（False Negative）。在增加了錯誤率這個因素之后，Bloom Filter通過允許少量的錯誤來節(jié)省大量的存儲空間。簡單地說就是寧可放過也不殺錯。

它的用法其實是很容易理解的，我們拿個HBase中應(yīng)用的例子來說下，我們已經(jīng)知道rowKey存放在HFile中，那么為了從一系列的HFile中查詢某個rowkey，我們就可以通過 Bloom Filter 快速判斷 rowkey 是否在這個HFile中，從而過濾掉大部分的HFile，減少需要掃描的Block。

Bloom Filter的工作原理

BloomFilter對于HBase的隨機讀性能至關(guān)重要，對于get操作以及部分scan操作可以剔除掉不會用到的HFile文件，減少實際IO次數(shù)，提高隨機讀性能。在此簡單地介紹一下Bloom Filter的工作原理，Bloom Filter使用位數(shù)組來實現(xiàn)過濾，初始狀態(tài)下位數(shù)組每一位都為0，如下圖所示：

 

假如此時有一個集合S = {x1, x2, … xn}，Bloom Filter使用k個獨立的hash函數(shù)，分別將集合中的每一個元素映射到｛1,…,m｝的范圍。對于任何一個元素，被映射到的數(shù)字作為對應(yīng)的位數(shù)組的索引，該位會被置為1。比如元素x1被hash函數(shù)映射到數(shù)字8，那么位數(shù)組的第8位就會被置為1。下圖中集合S只有兩個元素x和y，分別被3個hash函數(shù)進(jìn)行映射，映射到的位置分別為（0，3，6）和（4，7，10），對應(yīng)的位會被置為1:

 

現(xiàn)在假如要判斷另一個元素是否是在此集合中，只需要被這3個hash函數(shù)進(jìn)行映射，查看對應(yīng)的位置是否有0存在，如果有的話，表示此元素肯定不存在于這個集合，否則有可能存在。下圖所示就表示z肯定不在集合｛x，y｝中：

 

從上面的內(nèi)容我們可以得知，Bloom Filter有兩個很重要的參數(shù)

哈希函數(shù)個數(shù)

位數(shù)組的大小

HFile中 Bloom Filter 相關(guān)的Block

我們來理一下 HFile 中和 Bloom Filter 相關(guān)的Block，

Scanned Block Section（掃描HFile時被讀取）：Bloom Block

Load-on-open-section（regionServer啟動時加載到內(nèi)存）：BloomFilter Meta Block、Bloom Index Block

• Bloom Block：Bloom數(shù)據(jù)塊，存儲Bloom的位數(shù)組

• Bloom Index Block：Bloom數(shù)據(jù)塊的索引

• BloomFilter Meta Block：從HFile角度看bloom數(shù)據(jù)塊的一些元數(shù)據(jù)信息，大小個數(shù)等等。

HBase中每個HFile都有對應(yīng)的位數(shù)組，KeyValue在寫入HFile時會先經(jīng)過幾個hash函數(shù)的映射，映射后將對應(yīng)的數(shù)組位改為1，get請求進(jìn)來之后再進(jìn)行hash映射，如果在對應(yīng)數(shù)組位上存在0，說明該get請求查詢的數(shù)據(jù)不在該HFile中。

HFile中的Bloom Block中存儲的就是上面說得位數(shù)組，當(dāng)HFile很大時，Data Block 就會很多，同時KeyValue也會很多，需要映射入位數(shù)組的rowKey也會很多，所以為了保證準(zhǔn)確率，位數(shù)組就會相應(yīng)越大，那Bloom Block也會越大，為了解決這個問題就出現(xiàn)了Bloom Index Block，作用和 Data Index Block 類似，一個HFile中有多個Bloom Block（位數(shù)組），根據(jù)rowKey拆分，一部分連續(xù)的Key使用一個位數(shù)組。這樣查詢rowKey就要先經(jīng)過Bloom Index Block（在內(nèi)存中）定位到Bloom Block，再把Bloom Block加載到內(nèi)存，進(jìn)行過濾。

其他應(yīng)用場景

謂詞下推

1.Bloom Filter 在小表處生成；

2.廣播到大表處；

3.大表根據(jù) Bloom Filter 進(jìn)行過濾；

4.剩下的數(shù)據(jù)傳入 JoinNode 進(jìn)行關(guān)聯(lián)。

注意：Bloom Filter 處理 join 并不是總是有效地，如果JOIN兩邊的表并不能過濾到很多數(shù)據(jù)，例如左表和右表中Join鍵的差集并不大，這種情況下反而浪費了資源計算Bloom Filter和應(yīng)用Bloom Filter

如何使用 Bloom Filter

Google Guava library為我們提供了Bloom Filter的實現(xiàn)，直接用就可以啦：com.google.common.hash.BloomFilter

private final BloomFilter<String> bloomFilter = BloomFilter.create(new Funnel<String>() {
        private static final long serialVersionUID = 1L;
        @Override
        public void funnel(String arg0, PrimitiveSink arg1) {
            arg1.putString(arg0, Charsets.UTF_8);
        }
    }, 1024*1024*32);

public synchronized boolean contains(String id){
        if(StringUtils.isEmpty(id)){
            return true;
        }
        boolean exists = bloomFilter.mightContain(id);  //布隆過濾器是否包含這個id
        if(!exists){
            bloomFilter.put(id);   //添加進(jìn)布隆過濾器
        }
        return exists;
    }