每一個可以努力的日子,都是一份厚禮。
MapReduce
計算圓周率Approximating Pi – Map Reduce Program
2011 4月 11th
MapReduce主要應用於大規模數據處理,特別是在搜索引擎中各種鏈接的訪問統計,進而影響到頁面關鍵詞排名等等。今天這個例子卻是講的利用MapReduce來對圓周率Pi進行近似計算。考慮下面這張圖:
我們知道,正方形的面積 As = (2r)2 也就是 4r2. 內嵌圓形的面積 Ac = pi * r2. 於是 更多 >
學習MapReduce分布式程序設計方法
2011 2月 9th
MapReduce是Google提出的一個編程框架,用於大規模海量數據處理,其主要思想就是分治(divide and conquer)。我們希望程序有並行處理能力,於是就可以使用多台機器同時處理加快速度。
然而,怎樣分派任務給不同的計算機?如果任務單元的數量大於可執行任務的計算機的數量怎麼辦?計算需要使用到一些中間結果怎樣處理?如果某些計算機在處理任務時中途死掉了呢?怎樣才能知道任務已經處理完畢?問題主要來自於任務處理節點的交流(比如狀態信息),以及對共享資源(數據)的訪問。要解決這些棘手的問題,我們需要有一套完整的同步機制:同步鎖信號量、條件變量(等待、通告、廣播)等等。
現有的一些編程模型有共享內存(pthread)、消息傳遞(MPI)等,架構的設計模式有主從式(Master-Slaves)、生產者消費者流式(Producer-consumer flows)等。Map Reduce結合了函數式編程語言的思想,使用key-value對作為輸入和輸出。開發者只需要實現map(key, value)和reduce(key, value)兩個功能。map()會產生中間結果作為輸出,而這正是reduce()的輸入。中間結果經過reduce()產生最終結果。類似以下模型:
map (in_key, in_value) ->
(out_key, intermediate_value) listreduce (out_key, intermediate_value list) ->
out_value list
具體的原理可以參看Google發表的關於MapReduce的論文。從應用開發的角度,本站的MapReduce分類下有一些python示例,可以作為初步入門學習。最簡單的方法就是利用管道來進行代碼測試,例如: 更多 >
反向索引Inverted Index – Map Reduce Program
2011 1月 4th
Inverted Index (反向索引)是搜索引擎需要做的一件經常性工作。在Google提出Map Reduce分布式編程框架中,這是一件很容易完成的事情。下面就是一個python寫的示例。 更多 >
單詞統計Word Count – Map Reduce Program
2011 1月 4th
在學習Map Reduce方法時,Word Count(單詞統計)程序是最基礎的入門訓練。不同的寫法會有不同的執行效率,下面是用python寫的一個示例。 更多 >
Amazon EMR 雲計算服務編程實踐
2011 1月 4th
EMR是Amazon亞馬遜雲計算平台提供的一項服務,用戶可以在此平台使用亞馬遜強大的計算資源執行Map Reduce程序。由於Map Reduce很多情況下都是做的海量數據文本統計類的並行計算任務,需要耗費很多時間,使用雲計算則可以大大加快執行速度。
EMR建立在Amazon S3和Amazon EC2的基礎上。用戶提交一個map程序和一個reduce程序,同時提交需要處理的數據文件作為輸入。這些都上傳到Amazon S3雲端存儲平台,在EMR中指定相應的S3路徑,就可以開始做數據處理了。EMR會根據用戶指定的規模配置,開啟一個EC2集群,在每個節點上運行Hadoop。運行結束後用戶可以從S3獲取結果數據。下面以word count單詞統計任務為例,介紹具體操作過程。 更多 >