MapReduce

MapReduceは，Google社内でクラスタ上のデータ処理に用いられている並列分散プログラミングモデルである．ちょうど今サンフランシスコで開催されるOSDI 2004に発表予定の論文が，すでに公開されているが，これが非常に面白い．

http://labs.google.com/papers/mapreduce.html

概要は次のような感じ．

• データ処理を，MapとReduceの2つに分割する．なお，この名前は同様な機能を持つLispの関数名が由来．
• Mapでは，あるキーと値の組から，中間のキーと値の組のリストを生成し，ローカルディスクに書き込む．
• Reduceでは，Mapが生成したキーと値の組をリモートディスクから読み出し，値のリストを返す．
• MapとReduceは，複数のワーカによって分散したマシン上で並列に実行される．
• たとえば，細分化された入力ファイルをMapを処理するワーカが並列に処理して，その中間結果からReduceのワーカが解としてまとめるような感じで，大量データのさまざまな処理に適用可能な汎用なデザインパターンである．
• 各ワーカの中断は，自動的に検出され，再実行される．
• マシンの異常（例，ディスクの不良）などの理由で一部のタスクの実行時間が長くなることがある問題に対処するために，MapRecude処理が終わりに近づくと，現在実行中のタスクのバックアップタスクを実行することができる．これは，膨大な処理をおこなう場合の実行時間を短縮する効果がある．
• Recudeタスク/出力ファイル数を指定することができ，どのように分割するかも関数で指定できる．たとえば，この関数を変更することで，同一ホストに対するデータを同一ファイルに出力することができる．
• Mapが大量のデータを生成する時には，リモートファイルの読み出しに掛かる通信コストを削減するために，中間データサイズを削減するCombinerを実行できる．CombinerはReduceと基本的に同じだが，中間ファイルとして出力する点だけが異なる．

これはLindaなどよりも，よりアプリケーションに近いモデルであり，実際にGoogleでは全文検索索引作成だけでなく，グラフ構造の計算，ログからのGoogle Zeitgeistなどのレポート生成などに用いられている．C++のサンプルコードも，論文の最後にあるので，興味ある人は一度論文に目を通して頂きたい．

この論文を読んで特に強く感じたのは，「問題にはアルゴリズムの改良で対処する」という計算機科学者の基本的な精神がGoogleの本質であり，残念ながらそれは私の会社で失われつつあることである．

私がまだ若い時に，当時はまだICOTで活躍していた東大の近山先生から送られてきたDVIドライバの高速化パッチを見て目から鱗が落ちたことがある．それはなんとDVIファイルのスキャンを1回から2回にする！のだが，フォントの読み込みを効率化することで実行時間を大幅に短縮できるものであった．この時，問題を解決するのは力ではなく智恵であることを実体験として学んだ．

私の会社が，いくらGoogleに追いつこうとがんばっても，本来研究開発者としてあるべきものを忘れて，サービスの種類などの表層しか見ていない限りは，それは難しいように思う．