HBase中BloomFilter是什么

Bloom Filter 是什么？

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

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

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

Bloom Filter的工作原理

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

 

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

 

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

 

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

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

位數(shù)組的大小

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

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

Scanned Block Section（掃描HFile時(shí)被讀?。築loom Block

Load-on-open-section（regionServer啟動時(shí)加載到內(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ù)信息，大小個(gè)數(shù)等等。

HBase中每個(gè)HFile都有對應(yīng)的位數(shù)組，KeyValue在寫入HFile時(shí)會先經(jīng)過幾個(gè)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很大時(shí)，Data Block 就會很多，同時(shí)KeyValue也會很多，需要映射入位數(shù)組的rowKey也會很多，所以為了保證準(zhǔn)確率，位數(shù)組就會相應(yīng)越大，那Bloom Block也會越大，為了解決這個(gè)問題就出現(xiàn)了Bloom Index Block，作用和 Data Index Block 類似，一個(gè)HFile中有多個(gè)Bloom Block（位數(shù)組），根據(jù)rowKey拆分，一部分連續(xù)的Key使用一個(gè)位數(shù)組。這樣查詢r(jià)owKey就要先經(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鍵的差集并不大，這種情況下反而浪費(fèi)了資源計(jì)算Bloom Filter和應(yīng)用Bloom Filter

如何使用 Bloom Filter

Google Guava library為我們提供了Bloom Filter的實(shí)現(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);  //布隆過濾器是否包含這個(gè)id
        if(!exists){
            bloomFilter.put(id);   //添加進(jìn)布隆過濾器
        }
        return exists;
    }