1) 在Reduce階段進(jìn)行Join,這樣運算量比較小.(這個適合被Join的數(shù)據(jù)比較小的情況下.)
2) 壓縮字段,對數(shù)據(jù)預(yù)處理,過濾不需要的字段.
3) 最后一步就是在Mapper階段過濾,這個就是Bloom Filter的用武之地了.也就是需要詳細(xì)說明的地方.
下面就拿一個我們大家都熟悉的場景來說明這個問題: 找出上個月動感地帶的客戶資費的使用情況,包括接入和撥出.
(這個只是我臆想出來的例子,根據(jù)實際的DB數(shù)據(jù)存儲結(jié)構(gòu),在這個場景下肯定有更好的解決方案,大家不要太較真哦)
這個時候的兩個個數(shù)據(jù)集都是比較大的,這兩個數(shù)據(jù)集分別是:上個月的通話記錄,動感地帶的手機(jī)號碼列表.
比較直接的處理方法有2種:
1)在 Reduce 階段,通過動感地帶號碼來過濾. 優(yōu)點:這樣需要處理的數(shù)據(jù)相對比較少,這個也是比較常用的方法.
缺點:很多數(shù)據(jù)在Mapper階段花了老鼻子力氣匯總了,還通過網(wǎng)絡(luò)Shuffle到Reduce節(jié)點,結(jié)果到這個階段給過濾了.
2)在 Mapper 階段時,通過動感地帶號碼來過濾數(shù)據(jù). 優(yōu)點:這樣可以過濾很多不是動感地帶的數(shù)據(jù),比如神州行,全球通.這些過濾的數(shù)據(jù)就可以節(jié)省很多網(wǎng)絡(luò)帶寬了.
缺點:就是動感地帶的號碼不是小數(shù)目,如果這樣處理就需要把這個大塊頭復(fù)制到所有的Mapper節(jié)點,甚至是Distributed Cache.(Bloom Filter就是用來解決這個問題的)
Bloom Filter就是用來解決上面方法2的缺點的.
方法2的缺點就是大量的數(shù)據(jù)需要在多個節(jié)點復(fù)制.Bloom Filter通過多個Hash算法, 把這個號碼列表壓縮到了一個Bitmap里面. 通過允許一定的錯誤率來換空間, 這個和我們平時經(jīng)常提到的時間和空間的互換類似.詳細(xì)情況可以參考:
http://blog.csdn.net/jiaomeng/article/details/1495500
但是這個算法也是有缺陷的,就是會把很多神州行,全球通之類的號碼當(dāng)成動感地帶.但在這個場景中,這根本不是問題.因為這個算法只是過濾一些號碼,漏網(wǎng)之魚會在Reduce階段進(jìn)行精確匹配時顧慮掉.
這個方法改進(jìn)之后基本上完全回避了方法2的缺點:
1) 沒有大量的動感地帶號碼發(fā)送到所有的Mapper節(jié)點.
2) 很多非動感地帶號碼在Mapper階段就過濾了(雖然不是100%),避免了網(wǎng)絡(luò)帶寬的開銷及延時.
繼續(xù)需要學(xué)習(xí)的地方:Bitmap的大小, Hash函數(shù)的多少, 以及存儲的數(shù)據(jù)的多少. 這3個變量如何取值才能才能在存儲空間與錯誤率之間取得一個平衡.