Google MapReduce中的map和reduce與函數式編程中的map，reduce有何異同？

01-04

Google MapReduce的論文中寫到

the MapReduce 「abstraction is
inspired by the map and reduce primitives present in Lisp and many other functional languages」

我本人對函數式編程了解不多，想了解一下Google的MapReduce編程模型與函數式編程中的map，reduce有何異同？
補充：

搜到一篇論文Google』s MapReduce programming model

如果你只關心計算模型而不是具體實現的話，那惟一的區別就是，mapreduce的map等於haskell的map+groupBy，mapreduce的reduce等於haskell的fold

google的map和reduce是下圖這個意思

而函數式中的map是把一個函數應用到一個list的每個元素上，最後返回個list，reduce是把一個函數應用到一個list的每兩個元素上，返回一個聚合結果（以Clojure為例）。要說是有點相似之處，反正查不多是那個意思。但其實Google的MapReduce還有很多階段的，包括Split，Combine，Suffle，Sort等，不僅僅只是Map和Reduce

除去量數據大帶來的並行，分散式的技術特點，MapReduce語義上與函數式編程中的map和reduce相同。

只不過在二者之間系統插入了一個排序的過程。

分散式計算，分而自治。在mapreduce中都是通過key value對來實現的。所以核心在於中間的shuffle，reduce拿到的是同一個key的所有數據，換句話說就是子問題集，而map的主要作用就是對屬於同一問題集的數據打上相同key。如果數據本身藕合度很低，甚至可以直接通過inputformat實現一下輸入邏輯便可以實現並行，無需reduce。另外mapreduce框架其實在很多場合已經顯示出其弊端，特別是多輪的時候，很多框架其實都已經逐漸去掉map和reduce的差別，就是一個work的概念，中間的數據傳輸和子問題如何聚在一起才是關鍵。好比TEZ框架，MRR這樣的作業在一定程度上是打破傳統的MRMR的弊端。

MapReduce和fp中的map, reduce意思差不多，最大的區別是MapReduce中間多了排序的過程。

著作權歸作者所有。

商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。

作者：czw94

鏈接：MapReduce 與函數式編程

來源：CSDN博客

MapReduce 的抽象受到LIsp和其他函數式語言你中的map和reduce原語的啟發。map和reduce（fold）函數都是屬於在函數式編程語言中的高階函數。map函數的功能是接受一個列表list以及一個函數，將這個函數作用於這個列表中的所有成員，並返回所得結果。例如，下述函數將括弧中的三個數每個加一：
map(+1)[1,2,3]
這個表達式的輸出結果是[2,3,4]。
而fold函數的功能則是接收一個列表、一個初始值以及一個函數，將該函數作為特定的組合方式，將其遞歸地應用於列表的所有成員，並返回最終結果，比如，下述函數計算0+1+2+3的和：
fold(+)0[1,2,3]

其具體的操作流程是(((0+1)+2)+3)，並最終返回其總和。同樣，也可以用fold求一個列表的所有元素之積：
fold(*)1[1,2,3]
還繼續用上面統計單詞次數的例子，MapReduce計算模型里的map函數實際上相當於下述函數式編程語言的語句：
map(f)[&,&,&,...]
其中f為用戶實現的mapper函數里的操作，所以我們可以看出，它本質上就是函數式編程中的map函數合成的操作。
讓我們用Haskell的例子說明reduce函數，其功能就是分別求若干個數組中數字的積：
Prelude&> let a=[[1,2,3],[4,5,6],[7,8,9],[10,11,12]]
Prelude&> map(foldr(*)1)a
[6,120,504,1320]
作為類比，可以把MapReduce計算模型里的reduce抽象成下述形式，根據鍵將鍵值對分組，然後分別計算：

let Internediate=[[&,&,&...],[&,&,&...]...]
map(reduce(f)[])Intermediate
只不過這裡，map步驟是由partitioner來實現分發不同鍵組的動作，而實際上對於每一個reducer來說，它的工作方式正像是函數式編程里的reducer一樣，對每一個鍵值組採用用戶寫的f作為特定的組合方式。
綜上所述，函數式語言與Hadoop這類系統中的map和reduce函數並沒有本質區別。作為計算模型而言，MapReduce實際上就是函數式編程語言中的map和reduce函數的並行化拓展。另外，我們可以從MapReduce計算模型身上處處體會到函數式編程的哲學原理，即把數據抽象作為一個流來進行操作，而顯然這種抽象也正是並行化的基礎。
從抽象的觀點看，一個流也就是一個序列。流處理使我們可以模擬一些包含狀態的系統，但卻不需要利用複製或者變動數據。這一情況會產生一些重要的結果，既有理論的也有實際的。因為我們可以構造出一些模型，它們能避免由於引進賦值而帶來的內在缺陷。但是，流框架也造成了它自己的困難。

最近一直在寫MR，感覺MR就是K和V結構，把握好這點一切都OK， k,v 結構和redis一樣