整理し直し - ハトムネメモ

MapReduceは、複数のマシンを使って分散的にデータ処理を行う仕組みである。MapReduceには、大きく分けて２つのフェーズがあり、それぞれ「Map」「Reduce」と呼ばれる。MapReduceは、この２つの処理を複数のマシンに同時に行わせる形で、分散処理を行なう。

「Map」は、まとまったデータが入力されるとそのデータを加工して出力する、という機能を持っている関数である。Mapには

<キー,値>

というリストの形でデータが渡される。Mapは、これを加工し、出力もまた<キー,値>のリ
ストの形になる。一つのリストの入力に対して、複数のリストを出力する。
ここで、Mapから出力されたリストは、キーが同じもの同士でまとめられる。例えば、

というリストが出力されていたら、

というふうにまとめられる。この過程を「シャッフル」と呼ぶ。
「Reduce」は、シャッフルされた「Map」の出力をまとめあげ、最終的な形でデータを出力する機能を持っている。
「Map」と「Reduce」が具体的にどのようなデータ処理を行なうかは、プログラマ次第となる。

「Map」には、

が渡される。「Map」は、webページから単語を抽出し、新たに

というリストを複数作り出して出力する。出力されたリストは、シャッフルによってまとめられ、「Reduce」に渡される。「Reduce」は、複数ののリストからインデックス表を作り出して出力する。

「Map」には、

が渡される。「Map」は、webページから単語を抽出し、新たに

というリストを作る。この結果をシャッフルすると、

といったリストが出力される。「Reduce」は、各リストの値の部分の１を数える。その結果「Reduce」の出力は、単語の出現回数となる。

MapReduceは「Map」「Reduce」を複数のマシンで行なわせる仕組みを持っている。

サーバには、「マスタ」と「ワーカー」がある。
「マスタ」は分散処理全体を監視し、「ワーカー」いデータを割り当てる。「ワーカー」は、割り当てられたデータに対して「Map」か「Reduce」を行なう。

「マスタ」はまず入力ファイルを分割する。分割数は、入力ファイルのサイズやパラメータMによって決まる。ファイルサイズやMの値が大きくなるにしたがって、細かく分割される。

マスタはファイルを分割すると、ワーカーにMapを行なうように指示する。ワーカーは、その結果を受け、マスターから分割ファイルを取ってきて、Mapを実行する。

Mapの出力結果は「中間ファイル」として保存される。その後、中間ファイルはキー値によってグループ分けされる。ここでグループ数は、パラメータRによって決まる。具体的に

hash(キー) mod R

という計算によってグループ分けがされる。ここで用いられる計算は「分割関数」と呼ばれる。
出力された中間ファイルは、順次シャッフルされる。すなわち、シャッフルはMap処理と並列で行なわれる。

すべてのMap処理、シャッフルが終了すると、次にマスターは中間ファイルのイテレータをワーカーに渡して、Reduce処理を行なうように命令する。Reduceが終わると出力結果が出る。この後、他のMapReduceに出力結果を渡すか、統合してファイルに書き込むかに分かれていく。

以上が、MapReduceの分散処理の概要となる。
MapReduceはこの他に、高速化するための処理や耐障害処理を行なっている。