MapReduce：大規模並列処理を2つの関数に落とし込む

この論文が解いた問題

横にスクロール

2000年代初頭のGoogleは、Webページのクロール結果から検索インデックスを作る、大量のログを集計するといった、テラバイト級・ペタバイト級のデータ処理を日常的に抱えていた。1台のマシンでは到底終わらないため、処理を数百から数千台のマシンに分散させる必要がある。ところが、分散処理のプログラムを書くのは本質的に難しい。入力データをどう分割してマシンに配るか、各マシンの計算結果をどう集約するか、途中でマシンが故障したらどう復旧するか、負荷をどう均すか。こうした課題が、本来やりたい集計ロジックの上に覆いかぶさってくる。

問題は、この「分散の面倒ごと」が処理のたびに繰り返し現れることだった。単語を数えるだけの単純な処理でも、分散版を書こうとすると、数百行の通信・同期・障害処理コードの中に肝心のロジックが埋もれてしまう。エンジニアはデータ処理の中身ではなく、インフラの都合と格闘する羽目になる。

核心アイデア

MapReduce（2004年、Jeffrey DeanとSanjay Ghemawatが発表）の核心は、大規模データ処理を map と reduce という2つの関数だけで記述できるようにしたことだ。利用者はこの2つを書く。あとの並列化・分散・耐障害はフレームワークが引き受ける。

処理は3つの段階を通る。

典型例が単語の出現数え上げだ。map は各文書を受け取り、単語ごとに「その単語, 1」というペアを吐き出す。フレームワークが同じ単語のペアを集めて（shuffle）、reduce がその単語の総数を合計する。

map(key, value):
  # key: 文書名, value: 文書の中身
  for word in value:
    emit(word, 1)

reduce(key, values):
  # key: 単語, values: その単語について集まった 1 のリスト
  emit(key, sum(values))

この2つの関数のどこにも、通信も同期も障害処理も書かれていない。にもかかわらず、フレームワークがこれを数千台上で並列に実行してくれる。ここがMapReduceの発明の核だ。

実行時の全体像はこうだ。1つのマスターが処理全体を統括し、多数のワーカーが実際の計算を担う。マスターは入力を M 個の断片に分けて map タスクを作り、中間結果は R 個のまとまり（パーティション）に分けて reduce タスクへ割り当てる。各タスクの状態（待機中・実行中・完了）を追跡し、空いたワーカーへ次々と仕事を配っていく。数千台という規模では、どこかのマシンが壊れるのはもはや例外ではなく日常だ。だからこそ、処理を小さなタスクに刻み、失敗したものだけをやり直せる設計が効いてくる。障害を特別扱いせず、通常運転の一部として吸収する。この割り切りが大規模化の鍵だった。

フレームワークが自動で担うのは、おおむね次の4点である。第一に並列化。入力を多数の断片に分け、多くのワーカーで map を同時に走らせる。第二にデータ分散。中間データをキーで振り分け、reduce を担当するワーカーへ渡す。第三に耐障害。マスターが各タスクを監視し、ワーカーが故障したら、そのワーカーが処理していたタスクを別のワーカーで再実行する。map と reduce が副作用のない決定的な計算である限り、再実行は安全に結果を再現できる。第四にデータ局所性。入力データは分散ファイルシステム上に散らばって置かれており、フレームワークはそのデータを持つマシン、あるいはその近くのマシンで map を走らせようとする。計算をデータのある場所へ運ぶことで、ネットワーク越しの転送を減らすのだ。

MapReduceがこれほど素直に成り立つのは、土台に分散ファイルシステムのGFSがあるからだ。入力の分散配置も、局所性を活かしたスケジューリングも、GFSがデータの所在を管理しているからこそ実現できる（GFSの解説を参照）。

その後の影響

MapReduceの論文は、その後のデータ処理のあり方を決定づけた。最大の影響は、オープンソースのApache Hadoopとして広く実装されたことだ。HadoopはGFSに相当するHDFSと、MapReduce実行エンジンを組み合わせ、専用の高価な機材ではなく汎用サーバーを多数並べるだけで大規模処理を可能にした。これにより、それまで一部の巨大企業だけのものだった大規模データ処理が、多くの企業や研究者の手に届くようになり、いわゆるビッグデータ時代が幕を開けた。論文が実行モデルと障害処理の考え方を具体的に描いていたことも、こうした再実装を強く後押しした。

同時にこの論文は、関数型プログラミングの map と reduce という古典的な考え方を、分散処理の世界へ持ち込んだ点でも画期的だった。小さく決定的な関数を組み合わせるという枠組みが、たまたま並列化とも相性が良い。この気づきが、その後の分散処理フレームワーク設計の共通言語になった。

一方で、MapReduceには弱点もあった。各段階の中間結果をいちいちディスクに書き出すため、複数の処理を連鎖させる反復計算では入出力が重くなる。この課題に応えて登場したのが、中間データをメモリ上に保持して高速化するApache Sparkなどの後継エンジンだ。今日のデータ基盤ではSparkのようなエンジンが主流になったが、それらも「利用者は変換ロジックだけを書き、分散はフレームワークが担う」というMapReduceの発想の延長線上にある。データ処理の全体像はデータエンジニアリングから辿れる。

まとめ

MapReduceは、大規模並列処理という難題を、map と reduce という2つの関数に落とし込んだ。利用者はデータの変換ロジックだけを書き、並列化・データ分散・耐障害・データ局所性はフレームワークに委ねる。ワーカー故障は再実行で、遅いタスクはバックアップ実行で吸収するという実務的な設計も含めて、分散システム設計の一つの模範となった。何を計算するか（map と reduce）と、それをどう分散して走らせるか（フレームワーク）をきれいに切り離したことが、この論文の最大の遺産だと言える。この発想はHadoopからSparkへと受け継がれ、今日のデータ基盤の土台であり続けている。分散システムの古典は論文で辿る分散システムから読み進められる。