Googleの大規模な分散処理技術の中で、大きな役割を果たしている
のが、MapReduceというアルゴリズムです。このアルゴリズムは、
Jeffrey Dean とSanjay Ghemawatによって「発見」されたものです。
http://209.85.163.132/papers/mapreduce-osdi04.pdf
ここでは、「あるテキストの中で、出現するwordの数を数える」という、
いわゆるWord Countの例で、このアルゴリズムを説明したいと思います。
話を簡単にするために、ここでのテキストは、次のものとしましょう。
TEXT = "TO BE OR NOT TO BE"
もちろん答えは、この例でしたら「人間computing」をすれば、
すぐ分かるのですが
TO:2, BE:2, OR:1, NOT:1
ということになります。
MapReduceは、次の三つのステップで、この結果を導きます。
第一段階 Map
Word Countの例でしたら、Mapは、テキスト中のwordを一つ見つけるたびに、
そのwordに"1"という値を割り当てます。
| TO ｜ BE | OR | NOT | TO | BE |
Map +-----+----+----+-----+----+----+
| 1 | 1 | 1 | 1 | 1 | 1 |
keyとvalueのペアを、key;valueであらわせば、このMapの処理は、
"TO BE OR NOT TO BE"というテキストから、次のようなkey:valueの
集まりを作り出すことです。
Map: "TO BE OR NOT TO BE" ---> [ TO:1, BE:1, OR:1, NOT:1, TO:1, BE:1 ]
第二段階 Sort
Mapの出力をkeyでSortして、同じkeyを持つもの同士が
隣り合うグループを作るようにします。
| TO ｜ BE | OR | NOT | TO | BE | | BE ｜ BE | NOT | OR | TO | TO |
Sort +-----+----+----+-----+----+----+ --> +-----+----+-----+----+----+----+
| 1 | 1 | 1 | 1 | 1 | 1 | | 1 | 1 | 1 | 1 | 1 | 1 |
Sort: [ TO:1, BE:1, OR:1, NOT:1, TO:1, BE:1 ]
----> [ BE:1, BE:1, NOT:1, OR:1, TO:1, TO:1 ]
ですね。
この処理は、人間computingで、同じwordを探す処理に対応しています。
第三段階 Reduce
同じkeyを持つものを束ねます。このとき、valueにある操作が必要です。
Word Countの場合には、同じkeyのvalueは、足し合わせるだけです。
| BE ｜ BE | NOT | OR | TO | TO | | BE | NOT | OR | TO |
Reduce +-----+----+--- -+----+----+----+ --> +-----+----+-----+----+----+----+
| 1 | 1 | 1 | 1 | 1 | 1 | | 1 | 1 | 1 | 1 | 1 | 1 |
| BE | NOT | OR | TO | | BE | NOT | OR | TO |
--> +---------+-----+----+---------+ --> +-----+-----+----+----+
| 1 + 1 | 1 | 1 | 1 + 1 | | 2 | 1 | 1 | 2 |
結局、
Reduce: [ BE:1, BE:1, NOT:1, OR:1, TO:1, TO:1 ]
----> [ BE:2, NOT:1, OR:1, TO:2 ]
もちろん、この結果は、人間computingの
TO:2, BE:2, OR:1, NOT:1
に一致しています。これだけです。
ここでは、MapReduceが、実際には、Map+Sort+Reduceという
三段階の処理だということに、注目してください
