布隆過濾器在HBase中的應(yīng)用 - Echo的博客 - 博客頻道 - CSDN.NET
http://blog.csdn.net/echozhan/article/details/53154009
在討論布隆過濾器在Hbase中的應(yīng)用之前,先介紹一下HBase的塊索引機制。塊索引是HBase固有的一個特性腔稀,因為HBase的底層數(shù)據(jù)是存儲在HFile中的啃洋,而每個HFile中存儲的是有序的<key, value>鍵值對,HFile文件內(nèi)部由連續(xù)的塊組成[1],每個塊中存儲的第一行數(shù)據(jù)的行鍵組成了這個文件的塊索引,這些塊索引信息存儲在文件尾部。當HBase打開一個HFile時跑慕,塊索引信息會優(yōu)先加載到內(nèi)存;HBase首先在內(nèi)存的塊索引中進行二分查找摧找,確定可能包含給定鍵的塊核行,然后讀取磁盤塊找到實際想要的鍵。
但實際應(yīng)用中慰于,僅僅只有塊索引滿足不了需求钮科,這是因為,塊索引能幫助我們更快地在一個文件中找到想要的數(shù)據(jù)婆赠,但是我們可能依然需要掃描很多文件绵脯。而布隆過濾器就是為解決這個問題而生。因為布隆過濾器的作用是休里,用戶可以立即判斷一個文件是否包含特定的行鍵蛆挫,從而幫我們過濾掉一些不需要掃描的文件。如下圖所示妙黍,塊索引顯示每個文件中都可能包含對應(yīng)的行鍵悴侵,而布隆過濾器能幫我們跳過一些明顯不包含對應(yīng)行鍵的文件。
HBase–常用過濾器篇 - 圈里圈外 - 開源中國社區(qū)
https://my.oschina.net/circleblog/blog/715724
5. 布隆過濾器 BloomFilter簡介:hbase的storefile有很多拭嫁,隨機查的時候可能需要遍歷很多storefile可免,如果在建表的時候指定了bloomfilter,則在get查詢(scan不管用)的時候就可以過濾掉很多不符合規(guī)則的storefile做粤,提高查詢效率浇借。
從另一個角度看大數(shù)據(jù)量處理利器:布隆過濾器 - 寒山拾得 - 博客頻道 - CSDN.NET
http://blog.csdn.net/u013467442/article/details/41150241
思路:從簡單的排序談到BitMap算法,再談到數(shù)據(jù)去重問題怕品,談到大數(shù)據(jù)量處理利器:布隆過濾器妇垢。情景1:對無重復(fù)的數(shù)據(jù)進行排序
@給定數(shù)據(jù)(2,4,1闯估,12灼舍,9,7涨薪,6)如何對它排序骑素?
方法1:基本的排序方法包括冒泡,快排等尤辱。
方法2:使用BitMap算法
方法1就不介紹了砂豌,方法2中所謂的BitMap是一個位數(shù)組厢岂,跟平時使用的數(shù)組的唯一差別在于操作的是位光督。
首先是開辟2個字節(jié)大小的位數(shù)組,長度為16(該長度由上述數(shù)據(jù)中最大的數(shù)字12決定的)如圖
最后,讀取該位數(shù)組圃酵,得到排好序的數(shù)據(jù)是:(1柳畔,2,4郭赐,6薪韩,7,9捌锭,12)
比較方法1和方法2的差別:方法2中俘陷,排序需要的時間復(fù)雜度和空間復(fù)雜度很依賴與數(shù)據(jù)中最大的數(shù)字比如12,因此空間上講需要開2個字節(jié)大小的內(nèi)存观谦,時間上需要遍歷完整個數(shù)組拉盾。當數(shù)據(jù)類似(1,1000豁状,10萬)只有3個數(shù)據(jù)的時候捉偏,顯然用方法2,時間復(fù)雜度和空間復(fù)雜度相當大泻红,但是當數(shù)據(jù)比較密集時該方法就會顯示出來優(yōu)勢夭禽。
情景2:對有重復(fù)的數(shù)據(jù)進行判重
數(shù)據(jù)(2,4承桥,1驻粟,12,2,9蜀撑,7挤巡,6,1酷麦,4)如何找出重復(fù)出現(xiàn)的數(shù)字矿卑?
首先是開辟2個字節(jié)大小的位數(shù)組,長度為16(該長度由上述數(shù)據(jù)中最大的數(shù)字12決定的)如圖
當讀取完12后沃饶,數(shù)組中的數(shù)據(jù)如下圖:
當讀取2的時候母廷,發(fā)現(xiàn)數(shù)組中的值是1,則判斷出2是重復(fù)出現(xiàn)的糊肤。
應(yīng)用
應(yīng)用1:某文件中包含一些8位的電話號碼琴昆,統(tǒng)計出現(xiàn)的號碼的個數(shù)?(判斷有誰出現(xiàn))
8為最大是99 999 999馆揉,大約是99M的bit业舍,12.5MB的內(nèi)存,就可以統(tǒng)計出來出現(xiàn)的號碼升酣。
應(yīng)用2:某文件中包含一些8位的電話號碼舷暮,統(tǒng)計只出現(xiàn)一次的號碼?(判斷有誰出現(xiàn)并且指出現(xiàn)1次)
需要擴展一下噩茄,可以用兩個bit表示一個號碼下面,0代表沒有出現(xiàn)過,1代表只出現(xiàn)過1次绩聘,2代表至少出現(xiàn)2次沥割。
應(yīng)用3:有兩個文件,文件1中有1億個10位的qq號碼君纫,文件2中有5千萬個10位qq號碼驯遇,判斷兩個文件中重復(fù)出現(xiàn)的qq號。
首先建立10的10次方個大小的位數(shù)組(占用內(nèi)存大約是1.25G)蓄髓,全部初始化為0叉庐,讀取第一個文件,對應(yīng)的qq號存放到對應(yīng)的未知会喝,數(shù)值改為1陡叠,如果重復(fù)出現(xiàn)仍是1.讀取完畢第一個文件后,讀取第二個文件肢执,對應(yīng)的位置為1則表示重復(fù)出現(xiàn)枉阵。
應(yīng)用4:有兩個文件,文件1中有1億個15位的qq號碼预茄,文件2中有5千萬個15位的qq號碼兴溜,判斷兩個文件中重復(fù)出現(xiàn)的qq號侦厚。
應(yīng)用4中,qq號碼上升為15位的時候拙徽,顯然內(nèi)存是不夠用了刨沦,這個時候怎么辦?使用Bloom Filter(布隆過濾器)
Bloom Filter(布隆過濾器):
對于Bit-Map分析一下膘怕,每次都會開辟一塊表示最大數(shù)值大小的bit數(shù)組想诅,比如情景1中的16,將對應(yīng)的數(shù)據(jù)經(jīng)過映射到bit數(shù)組的下標岛心,這其實是一種最簡單的hash算法来破,對1去模。在上述應(yīng)用4中忘古,當qq號碼改為15位的時候徘禁,Bit-Map就不太好用了,如何改進呢存皂?解決辦法:減少bit數(shù)組的長度晌坤,但是增加hash函數(shù)的個數(shù)
對于每一個qq號碼逢艘,我用K個hash函數(shù)旦袋,經(jīng)過k次映射,得到k個不同位置它改,假設(shè)k=3疤孕,那么對于一個qq號碼,映射到位數(shù)組中3個不同的位置
當讀取第二個包含5千萬個qq號碼的文件的時候央拖,使用同樣的3個hash函數(shù)進行映射祭阀,當3個位置全部是1的時候才表示出現(xiàn)過,否則表示沒有出現(xiàn)過鲜戒。
有什么疑問嗎专控?
顯然,對于一個qq號碼遏餐,如果它在第一個文件中沒有出現(xiàn)過伦腐,但是它映射的3個位置已經(jīng)全部是1的情況會有嗎?答案是會的失都,但是這種概率是可控的柏蘑,可控的意思是:這種誤差跟hash函數(shù)的個數(shù)和質(zhì)量是有關(guān)系的,可以通過控制hash函數(shù)的個數(shù)和位數(shù)組的大小來控制誤差概率粹庞。至于表示3者之間的關(guān)系精確的數(shù)學(xué)公式就不再詳細研究了咳焚。
可以這樣講,布隆過濾器是Bit-Map的進一步擴展庞溜,對于大數(shù)據(jù)量判重革半,布隆過濾器可以在內(nèi)存中進行判斷,避免了對磁盤的讀寫,效率是很高的又官。以上是自己關(guān)于兩者的理解不傅,有錯誤望指教。
布隆過濾(Bloom Filter)-必須了解的優(yōu)化器算法 - wwicked - 博客園
http://www.cnblogs.com/wwicked/articles/4750071.html
吳軍博士赏胚,在《數(shù)學(xué)之美》一書中访娶,曾經(jīng)介紹過這個算法,以下內(nèi)容轉(zhuǎn)引自吳軍博士的文章:
假定我們存儲一億個電子郵件地址觉阅,我們先建立一個十六億二進制(比特)崖疤,即兩億字節(jié)的向量,然后將這十六億個二進制全部設(shè)置為零典勇。對于每一個電子郵件地址 X劫哼,我們用八個不同的隨機數(shù)產(chǎn)生器(F1,F2, ...,F8) 產(chǎn)生八個信息指紋(f1, f2, ..., f8)。再用一個隨機數(shù)產(chǎn)生器 G 把這八個信息指紋映射到 1 到十六億中的八個自然數(shù) g1, g2, ...,g8「铙希現(xiàn)在我們把這八個位置的二進制全部設(shè)置為一权烧。當我們對這一億個 email 地址都進行這樣的處理后。一個針對這些 email 地址的布隆過濾器就建成了伤溉。(見下圖)
算法分析:使用布隆過濾器(Bloom Filter)進行大數(shù)據(jù)量排序 - 苗哥的個人頁面 - 開源中國社區(qū)
https://my.oschina.net/bairrfhoinn/blog/209965
摘要: 移動公司需要對已經(jīng)發(fā)放的所有139段的號碼進行統(tǒng)計排序般码,已經(jīng)發(fā)放的139號碼段的文件都存放在一個文本文件中(原題是放在兩個文件中),一個號碼一行乱顾,現(xiàn)在需要將文件里的所有號碼進行排序板祝,并寫入到一個新的文件中;號碼可能會有很多走净,最多可能有一億個不同的號碼(所有的139段號碼)券时,存入文本文件中大概要占1.2G的空間;JVM最大的內(nèi)存在300以內(nèi)伏伯,程序要考慮程序的可執(zhí)行性及效率橘洞;只能使用Java標準庫,不得使用第三方工具说搅。
題目大意:移動公司需要對已經(jīng)發(fā)放的所有139段的號碼進行統(tǒng)計排序炸枣,已經(jīng)發(fā)放的139號碼段的文件都存放在一個文本文件中(原題是放在兩個文件中),一個號碼一行蜓堕,現(xiàn)在需要將文件里的所有號碼進行排序抛虏,并寫入到一個新的文件中;號碼可能會有很多套才,最多可能有一億個不同的號碼(所有的139段號碼)迂猴,存入文本文件中大概要占1.2G的空間;JVM最大的內(nèi)存在300以內(nèi)背伴,程序要考慮程序的可執(zhí)行性及效率沸毁;只能使用Java標準庫峰髓,不得使用第三方工具。 這是個典型的大數(shù)據(jù)量的排序算法問題息尺,首先要考慮空間問題携兵,一下把.2G的數(shù)據(jù)讀入內(nèi)存是不太可能的,就算把壹億條數(shù)據(jù)都轉(zhuǎn)換成INT類型存儲也要占接近400M的空間搂誉。當時做個題目我并沒有想太多的執(zhí)行效率問題徐紧,主要就考慮了空間,而且習(xí)慣性的想到合并排序炭懊,基本思想是原文件分割成若干個小文件并排序并级,再將排序好的小文件合并得到最后結(jié)果,算法大概如下:1侮腹、順序讀取存放號碼文件的中所有號碼嘲碧,并取139之后的八位轉(zhuǎn)換為int類型;每讀取號碼數(shù)滿一百萬個(這個數(shù)據(jù)可配置)將已經(jīng)讀取的號碼排序并存入新建的臨時文件父阻。2愈涩、將所有生成的號碼有序的臨時文件合并存入結(jié)果文件。
這個算法雖然解決了空間問題加矛,但是運行效率極低履婉,由于IO讀寫操作太多,加上步驟1中的排序的算法(快速排序)本來效率就不高(對于電話排序這種特殊情況來說)荒椭,導(dǎo)致1億條數(shù)據(jù)排序運行3個小時才有結(jié)果谐鼎。 如何能夠減少排序的時間呢?首當其沖的是減少IO操作趣惠,另外如果能夠有更加好排序算法也行。前天無聊再看這個題目時突然想到大三時看《編程珠璣》時上面也有個問題的需求這個這個題目差不多身害,記得好像使用是位向量(實際上就是一個bit數(shù)組)味悄,用電話作為index,心中大喜塌鸯,找到了解決此問題的最完美方案:用位向量存儲電話號碼侍瑟,壹個號碼占壹個bit,壹億個電話號碼也只需要大概12M的空間丙猬;算法大概如下:1涨颜、初始化bits[capacity];2茧球、順序所有讀入電話號碼庭瑰,并轉(zhuǎn)換為int類型,修改位向量值:bits[phoneNum]=1抢埋;3弹灭、遍歷bits數(shù)組督暂,如果bits[index]=1,轉(zhuǎn)換index為電話號碼輸出穷吮。
由于Java中沒有 bit 類型逻翁,一個 boolean 值占空間為 1byte(感興趣的可以自己寫程序驗證),我自己寫了個用 int 模擬 bit 數(shù)組的類捡鱼,代碼如下:
互聯(lián)網(wǎng)大數(shù)據(jù)采集與處理的關(guān)鍵技術(shù)研究金融大數(shù)據(jù)科技
http://www.cfc365.com/technology/bigdata/2015-03-04/13202.shtml
3.數(shù)據(jù)采集的關(guān)鍵技術(shù)——鏈接過濾
鏈接過濾的實質(zhì)就是判斷一個鏈接(當前鏈接)是不是在一個鏈接集合(已經(jīng)抓取過的鏈接)里面八回。在對網(wǎng)頁大數(shù)據(jù)的采集中,可以采用布隆過濾器來實現(xiàn)對鏈接的過濾驾诈。
布隆過濾器(Bloom Filter)的基本思想是:當一個元素被加入集合時辽社,通過K個散列函數(shù)將這個元素映射成一個位數(shù)組中的K個點,把它們置為1翘鸭。檢索時滴铅,我們只要看看這些點是不是都是1就(大約)知道集合中有沒有它了:如果這些點有任何一個0,則被檢元素一定不在就乓;如果都是l汉匙,則被檢元素很可能在。
布隆過濾器在空間和時間方面都有巨大的優(yōu)勢:
(1)在復(fù)雜度方面生蚁,布隆過濾器存儲空間和插入/查詢時間都是常數(shù)(即復(fù)雜度為O(k))噩翠; (2)在關(guān)系方面,散列函數(shù)相互之間沒有關(guān)聯(lián)關(guān)系邦投,方便由硬件并行實現(xiàn)伤锚; (3)在存儲方面,布隆過濾器不需要存儲元素本身志衣,在某些對保密要求非常嚴格的場合有優(yōu)勢屯援。
布隆過濾器的具體實現(xiàn)方法是,已經(jīng)抓取過的每個URL念脯,經(jīng)過k個hash函數(shù)的計算狞洋,得出k個值,再和一個巨大bit數(shù)組的這k個位置的元素對應(yīng)起來(這些位置數(shù)組元素的值被設(shè)置為1)绿店。在需要判斷某個URL是否被抓取過時吉懊,先用k個hash函數(shù)對該URL計算出k個值,然后查詢巨大的bit數(shù)組內(nèi)這k個位置上的值假勿,如果全為l借嗽,則是已經(jīng)被抓取過,否則沒有被抓取過转培。
海量數(shù)據(jù)處理利器之布隆過濾器 - 火星十一郎 - 博客園
http://www.cnblogs.com/hxsyl/p/4176280.html
四恶导、布隆過濾器應(yīng)用
布隆過濾器在很多場合能發(fā)揮很好的效果,比如:網(wǎng)頁URL的去重堡距,垃圾郵件的判別甲锡,集合重復(fù)元素的判別兆蕉,查詢加速(比如基于key-value的存儲系統(tǒng))等,下面舉幾個例子:
有兩個URL集合A,B缤沦,每個集合中大約有1億個URL虎韵,每個URL占64字節(jié),有1G的內(nèi)存缸废,如何找出兩個集合中重復(fù)的URL包蓝。
很顯然,直接利用Hash表會超出內(nèi)存限制的范圍企量。這里給出兩種思路:
第一種:如果不允許一定的錯誤率的話测萎,只有用分治的思想去解決,將A,B兩個集合中的URL分別存到若干個文件中{f1,f2...fk}和{g1,g2....gk}中届巩,然后取f1和g1的內(nèi)容讀入內(nèi)存硅瞧,將f1的內(nèi)容存儲到hash_map當中,然后再取g1中的url恕汇,若有相同的url腕唧,則寫入到文件中,然后直到g1的內(nèi)容讀取完畢瘾英,再取g2...gk枣接。然后再取f2的內(nèi)容讀入內(nèi)存。缺谴。但惶。依次類推,知道找出所有的重復(fù)url湿蛔。
第二種:如果允許一定錯誤率的話膀曾,則可以用布隆過濾器的思想。
在進行網(wǎng)頁爬蟲時煌集,其中有一個很重要的過程是重復(fù)URL的判別妓肢,如果將所有的url存入到數(shù)據(jù)庫中,當數(shù)據(jù)庫中URL的數(shù)
量很多時苫纤,在判重時會造成效率低下,此時常見的一種做法就是利用布隆過濾器纲缓,還有一種方法是利用berkeley db來存儲url卷拘,Berkeley db是一種基于key-value存儲的非關(guān)系數(shù)據(jù)庫引擎,能夠大大提高url判重的效率祝高。
布隆過濾器主要運用在過濾惡意網(wǎng)址用的栗弟,將所有的惡意網(wǎng)址建立在一個布隆過濾器上,然后對用戶的訪問的網(wǎng)址進行檢測工闺,如果在惡意網(wǎng)址中那么就通知用戶乍赫。這樣的話瓣蛀,我們還可以對一些常出現(xiàn)判斷錯誤的網(wǎng)址設(shè)定一個白名單,然后對出現(xiàn)判斷存在的網(wǎng)址再和白名單中的網(wǎng)址進行匹配雷厂,如果在白名單中惋增,那么就放行。當然這個白名單不能太大改鲫,也不會太大诈皿,布隆過濾器錯誤的概率是很小的。