JavaScript mapreduce工作原理簡析_基礎知識

Google在2003到2006年間連續發表了三篇非常有影響力的文章，分別是2003年在SOSP上發布的GFS，2004年在OSDI上發布的MapReduce，以及2006年在OSDI上發布的BigTable 。 GFS是檔案系統相關的，其對後來的分散式檔案系統設計具有指導意義；MapReduce是一種平行運算的程式設計模型，用於作業調度；BigTable是一個用於管理結構化資料的分散式儲存系統，建構在GFS、Chubby、SSTable等Google技術之上。相當多的Google應用程式使用了這三種技術，例如Google Search、Google Earth和Google Analytics等等。因此這三種技術並稱為Google技術」三寶」。今天，D瓜哥班門弄斧，對MapReduce來個」庖丁解牛」！

MapReduce簡介
MapReduce是一個程式設計模型，也是一個處理和產生超大資料集的演算法模型的相關實作。使用者先建立一
個Map函數處理一個基於key/value pair的資料集合，輸出中間的基於key/value pair的資料集合；然後
再建立一個Reduce函數用來合併所有的具有相同中間key值的中間value值。
一圖勝千言，下面我們用一張圖來說明MapReduce：

 
程式設計實踐
常言道：」實踐出真知」 。是騾子是馬，拉出來遛遛才知道。所以，如果真的想搞清楚這個原理，還是親自寫程式碼實作一下才是硬道理。
最近和幾個朋友一起學習JavaScript，所以就比較關注JavaScript。昨天上網瞎逛時，驚訝地發現，竟然有牛人使用JavaScript實作了MapReduce演算法。然後轉過來和大家分享，同時再加上我自己的一些狗尾續貂的介紹，希望有助於大家理解MapReduce。具體程式碼實作如下：

複製程式碼 程式碼如下:

var Job = { //待處理的資料
data : [
"We are glad to see you here. This site is dedicated to",
"poetry and to the people who make poetry possible",
" poets and their readers. FamousPoetsAndPoems.com is",
"a free poetry site. On our site you can find a large",
"collection of poadems and quotes from over 631 poets" and Enjoy Poetry",
"I, too, sing America",
"I am the darker brother",
"They send me to eat in the kitchen",
"When company comes" ,
"But I laugh",
"And eat well",
"And grow strong",
"Tomorrow",
"Ill be at the table",
" When company comes",
"Nobodyll dare",
"Say to me",
"Eat in the kitchen",
"Then",
"Besides",
" Theyll see how beautiful I am",
"And be ashamed",
"I, too, am America"
],
//將資料中的每行字串用空格分隔開，
//並"重組"成諸如{key: 單字, value: 1}格式的對象，傳回物件陣列
map : function(line) {
var splits = line.split(" ");
var temp = [];
for(var i=0; itemp.push({key : splits[i], value : 1} );
}
return temp;
},
//計算每個單字在"資料"（data）中出現的次數
reduce : function(allSteps) {
var result = {};
for(var i=0; ivar step = allSteps[i];
result[step.key] = result[step. key] ? (result[step.key] 1) : 1;
}
return result;
},
//初始化，同時是運作的入口。
init : function() {
var allSteps = [];
for(var i=0; i//如果這裡能多執行緒呼叫Job.map函數就更逼真了。 ？ ？
allSteps = allSteps.concat(Job.map(Job.data[i]));
}
//美中不足，這裡不能多執行緒呼叫Job.reduce函數？ ？
var result = Job.reduce(allSteps)
console.log(JSON.stringify(result));
}
}; // Job
//開始執行
Job .init();


複製這些程式碼，直接貼上到瀏覽器的控制台（Console）中，或是放到一個HTML檔案中，用瀏覽器打開，就可以在控制台輸出中，看到效果如下：

美中不足
這篇文章發佈出來之後，就有網友「咆哮」：「一個連多線程都沒有的js 搞什麼MapReduce啊？」其實，這個問題，D瓜哥也發現了。在看到這個程式碼的解釋後，D瓜哥就納悶JavaScript不是單一進程嗎？怎麼還能模擬MapReduce？在認真閱讀程式碼，單步調試之後，更加印證了D瓜哥的看法。 （關於D瓜哥的疑問已經在程式碼中註解出來。）
不過，再想一下，這些並不影響我們去理解MapReduce的原理。這只是個單一進程，最基礎的版本。先理解了這個，再去整個多執行緒的也許就更容易理解了。

未完待續
其實，D瓜哥現在考慮在這個例子的基礎上，用Java實現一個多線程版本，那樣模擬的MapReduce更逼真。等D瓜哥把一些問題思考清楚之後，就把程式碼發出來。敬請期待！