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