本頁使用了標題或全文手工轉換

MapReduce

維基百科,自由的百科全書
跳至導覽 跳至搜尋

MapReduceGoogle提出的一個軟件架構,用於大規模數據集(大於1TB)的並列運算。概念「Map(對映)」和「Reduce(歸納)」,及他們的主要思想,都是從函式語言程式設計語言借來的,還有從向量程式語言借來的特性。[1]

目前的軟件實現是指定一個Map(對映)函數,用來把一組鍵值對對映成一組新的鍵值對,指定並行的Reduce(歸納)函數,用來保證所有對映的鍵值對中的每一個共用相同的鍵組。

對映和歸納[編輯]

簡單來說,一個對映函數就是對一些獨立元素組成的概念上的列表(例如,一個測試成績的列表)的每一個元素進行指定的操作(比如,有人發現所有學生的成績都被高估了一分,他可以定義一個「減一」的對映函數,用來修正這個錯誤。)。事實上,每個元素都是被獨立操作的,而原始列表沒有被更改,因為這裏建立了一個新的列表來儲存新的答案。這就是說,Map操作是可以高度並列的,這對高效能要求的應用以及平行計算領域的需求非常有用。

而歸納操作指的是對一個列表的元素進行適當的合併(繼續看前面的例子,如果有人想知道班級的平均分該怎麼做?他可以定義一個歸納函數,通過讓列表中的奇數(odd)或偶數(even)元素跟自己的相鄰的元素相加的方式把列表減半,如此遞歸運算直到列表只剩下一個元素,然後用這個元素除以人數,就得到了平均分)。雖然他不如對映函數那麼並列,但是因為歸納總是有一個簡單的答案,大規模的運算相對獨立,所以歸納函數在高度並列環境下也很有用。

分佈和可靠性[編輯]

MapReduce通過把對數據集的大規模操作分發給網絡上的每個節點實現可靠性;每個節點會周期性的把完成的工作和狀態的更新報告回來。如果一個節點保持沉默超過一個預設的時間間隔,主節點(類同Google檔案系統中的主伺服器)記錄下這個節點狀態為死亡,並把分配給這個節點的數據發到別的節點。每個操作使用命名檔案的不可分割操作以確保不會發生並列線程間的衝突;當檔案被改名的時候,系統可能會把他們複製到任務名以外的另一個名字上去。(避免副作用)。

歸納操作工作方式很類似,但是由于歸納操作在並列能力較差,主節點會儘量把歸納操作排程在一個節點上,或者離需要操作的數據儘可能近的節點上了;這個特性可以滿足Google的需求,因為他們有足夠的頻寬,他們的內聯網沒有那麼多的機器。

其他實現[編輯]

參考[編輯]

  • Dean, Jeffrey & Ghemawat, Sanjay (2004)."MapReduce:大規模叢集上的簡單數據處理方式" 2005年4月6日。

^ "我們的靈感來自lisp和其他函式語言程式設計語言中的古老的對映和歸納操作." -"MapReduce:大規模叢集上的簡單數據處理方式"

外部連結[編輯]