MapReduce

IS

今日は言語処理学会2日目。発表練習してからいったので、ほとんど終わってたが、おーくらの発表は聞けた。それはさておき、本大会が終わってからおなじみ（？）googleの工藤さんがMapReduceについて解説してくれた。
いってない人のためにばさっと解説。データ処理をmapとreduceの枠組みの中に入れてプログラムを書くと、分散環境に容易に移行できるよというライブラリ。入力 --> map --> reduce --> 出力 という処理を経る。入力データはノードごとに「ばらまか」れて、mapでその入力データにある種の変換を加える。reduceの前にデータを一度「まとめて」（shuffleっていってたか？）、reduceでもう一度変換して出力する感じ。「まとめる」ために中間データは、key * valueの様な連想型で表される。つまり、同じkeyのデータを1カ所の計算ノードに「まとめて」、ひとつのkeyごとにreduce処理をする。
具体的に型を書けば、map処理が input -> (key * value) list な処理。inputはたくさんあるので、各mapの出力をkeyでまとめて (key * (value list)) list に変換。keyごとに再度計算ノードにばらまく。つまり、key * (value list)を渡して、各ノードでreduce処理 key * (value list) -> output を行うという寸法。全然わかりやすくないなぁ。
気になるのは「ばらまく」と「まとめる」という、ふつうにやるとシーケンシャルになる部分。で、おもしろいのは最初にデータを「ばらまく」部分はgoogle file systemによって分散ファイルシステムになっているため、そこでボトルネックになるわけじゃないというと。なるほど、考えたな。まとめる方は何もしてないみたいだが、keyごとにまとめればいいので、そこまで問題にならないんだろう。
たしかに、耐故障性とか堅牢性とかすごいけど、それ以外だったらOS演習で作れそうですねとか言ってみる。MPIに取って代わるかといえば、少し微妙というか少し用途も違うし。どっちかってと、シーケンシャルアクセスで超超巨大データを扱うことを考えてるしな。今度ローカルに入れてみようかなぁ。