hbase中的位圖索引--布隆過濾器

   在hbase中，讀業務是非常頻繁的。很多操作都是客戶端根據meta表定位到具體的regionserver然后再查詢region中的具體的數據。

   但是現在問題來了，一個region由一個memstore以及多個filestore組成，memstore類似緩存在服務器內存中，可以提高插入的效率，當memstore達到一定大小（由hbase.hregion.memstore.flush.size設置）或者說用戶手動flush之后，就會固化存儲在hdfs之類的磁盤系統上。也就是說一個region可以對應很多有著有效數據的文件，雖然文件內的數據是按照rowkey進行排序的，但是文件之間的rowkey并沒有任何順序（除非經過一次major_compact合并為一個文件）。

   如果用戶現在提出的請求是查看一個rowkey（row1）的隨意某個列（cf1:col1）

   即使用 get 'tab','row1','cf1:col1'這樣命令

   很有可能的一種現象是，row1在每個文件的startkey以及endkey之間，因此regionserver需要掃描每個文件的相關數據塊，進行多次物理IO。可是并不能確保每個文件中一定有row1這樣的行健，很多物理IO都是無效的，這樣以來對性能就有很大的影響。于是乎就有了布隆過濾器，在一定程度上判別文件中是否有指定的行健。

   布隆過濾器分為row以及rowcol兩種，原理差不多，以rowcol類型為例：

   在memstore寫入到hdfs形成文件時，文件內有一個部分叫做meta，在寫入的過程中遵循如下算法：

    1.首先會初始化一個比較長的bit數組不妨叫做bit arr[n]={0}；

    2.利用k個hash函數（k<n），對單個（row:cf:col）這樣的數據進行k次hash運算，保證計算結果在[0，n-1]之間；

    3.假設某個hash函數的運算結果為r，則設置arr[r]=1，這樣每個（row:cf:col）差不多都可以有k個結果，并將arr數據相應位置設置為1；

    4.如此反復知道所有的數據都被寫入文件，然后將arr寫入文件中的meta部分

   由于位圖索引本身的結構特點，可以保證arr[n]不會很大；所以即使被緩存到內存中（不是memstore）也不會占用太大空間，雖然在關系型數據庫中，尤其是oltp系統，位圖索引會造成大量鎖現象，但是在hbase中，已經寫入的文件除非compact否則幾乎不會修改。

   現在再來看 get 'tab','row1','cf1:col1'，在判斷某個文件是否含有（row1:cf1:col1）時，只需要將row1:cf1:col1進行k個hash運算，并判斷是否每個結果對應的arr數組值是不是1，如果有一個不是，則可以表明文件中不存在這一列數據（當然即使全部都是1也不一定代表就有），這樣可以避免讀不必要的文件，提高查詢效率。

   從上可見布隆過濾器可以在一定程度上避免讀不必要的文件，可是由于是基于hash函數的，所以也不能說是完全準確的，而且對于大規模的scan這樣的操作，完全沒有必要使用布隆過濾器。

                        2017.1.15