布隆過濾器及其應用

1、布隆過濾器及其在HBase中的應用什么是布隆過濾器什么是布隆過濾器1布隆過濾器的布隆過濾器的Java實現(xiàn)實現(xiàn)2布隆過濾器在布隆過濾器在HBase中的中的應用應用3主要內(nèi)容什么是布隆過濾器*布隆過濾器（Bloom Filter）是一種概率空間高效的數(shù)據(jù)結構。它與hashmap非常相似，用于檢索一個元素是否在一個集合中。它在檢索元素是否存在時，能很好地取舍空間使用率與誤報比例。正是由于這個特性，它被稱作概率性數(shù)據(jù)結構（probabilistic data structure）布隆過濾器的基本思想* Bloom-Filter算法的核心思想就是利用多個不同的Hash函數(shù)來解決“沖突”。 計算某元素x是

2、否在一個集合中，首先能想到的方法就是將所有的已知元素保存起來構成一個集合R，然后用元素x跟這些R中的元素一一比較來判斷是否存在于集合R中；我們可以采用鏈表等數(shù)據(jù)結構來實現(xiàn)。但是，隨著集合R中元素的增加，其占用的內(nèi)存將越來越大。試想，如果有幾千萬個不同網(wǎng)頁需要下載，所需的內(nèi)存將足以占用掉整個進程的內(nèi)存地址空間。即使用MD5，UUID這些方法將URL轉成固定的短小的字符串，內(nèi)存占用也是相當巨大的.布隆過濾器優(yōu)缺點*優(yōu)點： 具有很好的空間和時間效率（只需要哈希表的1/8或1/4的空間復雜度就能完成同樣的問題） 不存在false negative (漏報)，就是說如果元素存在的話，必能得到正確的結果缺

3、點： 不能刪除已儲存的元素 元素越多，false positive rate(誤報率)越大，也就說將不存在的元素判定為存在。（常見的補救方法：增加一個白名單，存儲可能被誤判的元素）布隆過濾器的空間效率*當使用列表或者集合時，空間效率都是重要且顯著的，那么布隆過濾器就應當被考慮。布隆過濾器基礎*布隆過濾器是N位的位數(shù)組，其中N是位數(shù)組的大小。它還有另一個參數(shù)k，表示使用哈希函數(shù)的個數(shù)。這些哈希函數(shù)用來設置位數(shù)組的值。當往過濾器中插入元素x時，h1(x), h2(x), , hk(x)所對應索引位置的值被置“1”，索引值由各個哈希函數(shù)計算得到。注意，如果我們增加哈希函數(shù)的數(shù)量，誤報的概率會趨近于0

4、.但是，插入和查找的時間開銷更大，布隆過濾器的容量也會減小。為了用布隆過濾器檢驗元素是否存在，我們需要校驗是否所有的位置都被置“1”，與我們插入元素的過程非常相似。如果所有位置都被置“1”，那也就意味著該元素很有可能存在于布隆過濾器中。若有位置未被置“1”，那該元素一定不存在什么是布隆過濾器什么是布隆過濾器1布隆過濾器的布隆過濾器的Java實現(xiàn)實現(xiàn)2布隆過濾器在布隆過濾器在HBase中的中的應用應用3主要內(nèi)容布隆過濾器Java實現(xiàn)*示例： 為了存儲一億個電子郵件地址 建立一個含有十六億二進制比特，也就是兩億字節(jié) 將十六億的比特全部設置為0 我們用八個不同的哈希函數(shù)，以電子郵件地址為鍵，算出值，

5、有8個（也許不是數(shù)字） 我們再一個哈希函數(shù)，分別以這8個值為鍵，會得到8個數(shù)值（范圍為1到十六億的某個數(shù)字） 以上一步算出的8個數(shù)值為下標，將這8個位置的二進制都設置為1（存儲了一個地址）查詢時只需要用類似的方法得到相應電子郵件的8個數(shù)值，以其為下標看二進制是否都設置為了1，如果設置為了1，那么這個電子郵件就存在在這個表中。什么是什么是布隆布隆過濾器過濾器1布隆過濾器的布隆過濾器的Java實現(xiàn)實現(xiàn)2布隆過濾器在布隆過濾器在HBase中的中的應用應用3主要內(nèi)容布隆過濾器的應用*應用：1. 垃圾郵件過濾中的黑白名單2. 爬蟲(Crawler)的網(wǎng)址判重模塊3. HBase ROWKEY查詢HBas

6、e布隆過濾器的原理*數(shù)據(jù)塊索引提供了一個有效的方法，在訪問一個特定的行時用來查找應該讀取的HFile的數(shù)據(jù)塊。但是它的效用是有限的。HFile數(shù)據(jù)塊的默認大小是64KB，這個大小不能調(diào)整太多如果你要查找一個短行，只在整個數(shù)據(jù)塊的起始行鍵上建立索引無法給你細粒度的索引信息。例如，如果你的行占用100字節(jié)存儲空間，一個64KB的數(shù)據(jù)塊包含(64 * 1024)/100 = 655.53 = 700行，而你只能把起始行放在索引位上。你要查找的行可能落在特定數(shù)據(jù)塊上的行區(qū)間里，但也不是肯定存放在那個數(shù)據(jù)塊上。這有多種情況的可能，或者該行在表里不存在，或者存放在另一個HFile里，甚至在MemStore

7、里。這些情況下，從硬盤讀取數(shù)據(jù)塊會帶來IO開銷，也會濫用數(shù)據(jù)塊緩存。這會影響性能，尤其是當你面對一個巨大的數(shù)據(jù)集并且有很多并發(fā)讀用戶時 布隆過濾器允許你對存儲在每個數(shù)據(jù)塊的數(shù)據(jù)做一個反向測試。當某行被請求時，先檢查布隆過濾器看看該行是否不在這個數(shù)據(jù)塊。布隆過濾器要么確定回答該行不在，要么回答它不知道布隆過濾器的代價*存儲這個額外的索引層次占用額外的空間。布隆過濾器隨著它們的索引對象數(shù)據(jù)增長而增長，所以行級布隆過濾器比列標識符級布隆過濾器占用空間要少。當空間不是問題時，它們可以幫助你榨干系統(tǒng)的性能潛力。 Bloomfilter是一個列族（cf）級別的配置屬性，如果你在表中設置了Bloomfilt

8、er，那么HBase會在生成StoreFile時包含一份bloomfilter結構的數(shù)據(jù)，稱其為MetaBlock；MetaBlock與DataBlock（真實的KeyValue數(shù)據(jù)）一起由LRUBlockCache維護。所以，開啟bloomfilter會有一定的存儲及內(nèi)存cache開銷布隆過濾器在HBase中的應用*HBase利用Bloomfilter來提高隨機讀（Get）的性能，對于順序讀（Scan）而言，設置Bloomfilter是沒有作用的（0.92以后，如果設置了bloomfilter為ROWCOL，對于指定了qualifier的Scan有一定的優(yōu)化，但不是那種直接過濾文件，排除在查

9、找范圍的形式）布隆過濾器在HBase表中使用方式*hbase(main):007:0 create mytable, NAME = colfam1, BLOOMFILTER = ROWCOL BLOOMFILTER參數(shù)的默認值是NONE。一個行級布隆過濾器用ROW打開，列標識符級布隆過濾器用ROWCOL打開。行級布隆過濾器在數(shù)據(jù)塊里檢查特定行鍵是否不存在，列標識符級布隆過濾器檢查行和列標識符聯(lián)合體是否不存在。ROWCOL布隆過濾器的開銷高于ROW布隆過濾器。布隆過濾器在如何提高GET性能*對于某個region的隨機讀，HBase會遍歷讀memstore及storefile（按照一定的順序），將

10、結果合并返回給客戶端。如果你設置了bloomfilter，那么在遍歷讀storefile時，就可以利用bloomfilter，忽略某些storefileHBase中布隆過濾器的類型及應用*ROW, 根據(jù)KeyValue中的row來過濾storefile 舉例：假設有2個storefile文件sf1和sf2， sf1包含kv1（r1 cf:q1 v）、kv2（r2 cf:q1 v） sf2包含kv3（r3 cf:q1 v）、kv4（r4 cf:q1 v） 如果設置了CF屬性中的bloomfilter為ROW，那么get(r1)時就會過濾sf2，get(r3)就會過濾sf1 ROWCOL,根據(jù)Ke

11、yValue中的row+qualifier來過濾storefile 舉例：假設有2個storefile文件sf1和sf2， sf1包含kv1（r1 cf:q1 v）、kv2（r2 cf:q1 v） sf2包含kv3（r1 cf:q2 v）、kv4（r2 cf:q2 v） 如果設置了CF屬性中的bloomfilter為ROW，無論get(r1,q1)還是get(r1,q2)，都會讀取sf1+sf2；而如果設置了CF屬性中的bloomfilter為ROWCOL，那么get(r1,q1)就會過濾sf2，get(r1,q2)就會過濾sf1ROW vs ROWCOL*ROWCOL一定比一定比ROW效果好

12、效果好么么?1.ROWCOL只對指定列（Qualifier）的隨機讀（Get）有效,如果應用中的隨機讀get，只含row，而沒有指定讀哪個qualifier，那么設置ROWCOL是沒有效果的，這種場景就應該使用ROW 2.如果隨機讀中指定的列（Qualifier）的數(shù)目大于等于2，在0.90版本中ROWCOL是無效的，而在0.92版本以后，HBASE-2794對這一情景作了優(yōu)化，是有效的（通過KeyValueScanner#seekExactly） 3.如果同一row多個列的數(shù)據(jù)在應用上是同一時間put的，那么ROW與ROWCOL的效果近似相同，而ROWCOL只對指定了列的隨機讀才會有效，所以

13、設置為ROW更佳 4.ROWCOL與ROW只在名稱上有聯(lián)系，ROWCOL并不是ROW的擴展，不能取代ROW結論*1. region下的下的storefile數(shù)目越多，數(shù)目越多，bloomfilter的效果越好的效果越好2. region下的下的storefile數(shù)目越少，數(shù)目越少，HBase讀性能越好讀性能越好 任何類型的get（基于rowkey和基于row+col）bloomfilter都能生效，關鍵是get的類型要匹配bloomfilter的類型 基于row的scan是沒辦法優(yōu)化的 scan是一個范圍，如果是row的bloomfilter不命中只能說明該rowkey不在此storefile中，但next rowkey可能在。