前幾回學習到硬體虛擬化及資料叢集平行運算的概念，整個infrastructure建立後，要怎麼開發平行運算的程式呢? 最著名的應用就是MapReduce了，MapReduce的概念並不新穎，甚至還有人提出他是一種倒退[1]，是的，這種處理方式不會有關聯性資料庫常用的特性, 如:
資料型別 : int varchar …等
更新 Update : 更新某筆資料
索引(index) : PK 及 FK
資料關聯性及一致性
交易Transcation : 每個Transcation 可以在資料受損時rollback
視圖View : 改變View 不用更新資料結構
MapReduce 本來就不是來取代關聯性資料庫的，他是用來處理大型的資料分析，他不太需要上述的特性，舉個例來說，Google每天去Crawl 上億的網站資料，如果全存在資料庫裡來分析，還要同時應付全球用戶的搜尋，用過DBMS的都知道，整個系統只會越來越慢，花大錢擴充資料庫的話是相當高額的成本。因此MaprReduce是有存在的必要的。
MapReduce 怎麼運做呢?以下圖[2]為例
1. 用戶程式裡的MapReduce Libary 會先把輸入的檔案資料切成M等份，每個等份16 MB-64MB , 然後會複製好幾份存在整個機器叢集
2. 其中一份特別的資料會指派給Master. 再由Master主機去找閒置的機器當Worker機，會指派M個Map task 和 R個Reduce task到worker主機,至於哪些Worker機做Map哪些做Reduce,也是由Master機來指派 。
3. 負責做Map的Worker機，會根據input資料的 key/value 的配對傳到開發者設計的Map function並將其Map結果存在暫存記憶體裡
4. 由Map function做出的暫存資料存在本機的 Intermediate file,由Partition function 分割成R 個區塊後把區塊位址交還給Master主機
5. 負責執行reduce 的Worker 接到由Mater傳來的Map處理完的資料位址後，會遠端讀取這些資料並依照key做排序，把相同的Key再群組(Group)起來.
6. Reduce worker 會計算sort 和 group 後的單一key的數量，在把這些直丟給用戶定義的Reduce function處理，處理後的資料會附加(append)到reduce 區的output 檔案。
7. 全部處理完後，Master主機會叫醒用戶程式
以上是流程圖，如果再參考資料流成圖[3]會更清楚
原本的資料
Deer Bear River
Car Car River
Deer Car Bear
經過MapReduce 後就變成
Bear,2
Car,3
Deer,2
River,2
這部分的應用，我直覺的想到，要做熱門關鍵字排行，只要將一段時間的大量查詢輸入的資料丟進此系統，很快的就可排出結果。
其他的應用為:
1 分散式的Grep : 做分散式的關鍵字搜尋
2. 計算某個URL被執行的頻率 : Key/value 在Map是<URL,1> , Reduce 後就是<URL,total count>
3. 反向網路連結圖 : 由<target, source> 去推出連到這個網站的連結量 <target,list(source)>
如果要直接測試MapReduce 程式，Amazon Elastic MapReduce似乎是不錯的選擇，試玩過在跟大家分享 http://aws.amazon.com/elasticmapreduce/
參考資料
[2]Introduction to Parallel Programming and MapReduce
[3] http://blog.jteam.nl/wp-content/uploads/2009/08/MapReduceWordCountOverview1.png
其他:
Dean, Jeff and Ghemawat, Sanjay. MapReduce: Simplified Data Processing on Large Clusters http://labs.google.com/papers/mapreduce-osdi04.pdf
Lammal, Ralf. Google's MapReduce Programming Model Revisited. http://www.cs.vu.nl/~ralf/MapReduce/paper.pdf
Open Source MapReduce: http://lucene.apache.org/hadoop/
沒有留言:
張貼留言