MapReduce

いきなりMapReduceの概念的なことを言われても理解できない(できなかった)ので、具体例から入っていく。
MapReduceの使用例として、検索のインデックス作成がある。
インデックス作成の流れ。

• レポジトリにあるwebページを取ってくる
• docIDというIDをキーとしての形のリストを作る。また、urlをキーとしたというリストも作る
• webページの中にある単語をピックアップし、wordIDと対応づけさせたというリストを作る。webページには単語が複数あるので、複数ののリストが作られることになる。ここで、wordIDは、Lexlcon(用語集）という表から参照される。Lexlconでは、wordIDと単語が対応付けられている。

ここで、という一つのリストから複数のというリストが複数でき上がった。このようにリストを受け取って、新たに複数のリストを出力することを「Map」という。

• 作成された複数のリストの中で、wordIDが同じリストについてはまとめられる。

ここで、同じキーの値をまとめる作業を「シャッフル」と呼ぶ。

• この時点で、wordIDをキーにしてdocID参照できるような形に成っている、すなわち検索用の表が出来上がっている。この表をファイルに書き込めるように変換し、出力する。

ここで、ファイルを書き込めるように変換して出力する事を「Reduce」と呼ぶ。

以上の「Map」「シャッフル」「Reduce」がMapReduceの基本用語になる。

分散処理

MapReduceは「Map」「シャッフル」「Reduce」のそれぞれの処理を分散処理するように設計されている。プログラマは、「Map関数」と「Reduce関数」を書けば、MapReduceが分散処理部分を自動的に行ってくれるという仕組みになっている。

マスタとワーカー

「マスタ」と「ワーカー」というサーバーがある。
「マスタ」はMapReduce全体の動作を管理する。
「ワーカー」は「Map」「Reduce」のいずれかを実行する。

分散処理の流れ

マスタは、入力ファイルを断片化する。断片化する数は、ファイルの大きさにより、パラメータMによって決まる。
入力ファイルを断片化したマスタは、ワーカーに「Map」を行うように指示する。
ワーカーは、断片化された入力ファイルを自分のところへ引き寄せ、「Map」を行う。
「Map」が完了すると、ワーカーは出力として「中間ファイル」で蓄えられる。
ここで中間ファイルは、キーによってグルーピングされる。ここでは「分割関数」というものが用いられる。
分割関数でグルーピングされた中間ファイルは、同じグループごとで集められ、Reduceが行われる。

まだ、整理ができてない感じだ・・・