IT 技書の森

MapReduce

大規模データを Map (分割・変換) と Reduce (集約) の 2 段階で並列処理する分散処理モデル

分散システムデータ分析

MapReduce とは

MapReduce は、Google が 2004 年の論文「MapReduce: Simplified Data Processing on Large Clusters」で発表した分散処理モデルである。大規模データを Map (分割・変換) と Reduce (集約) の 2 段階で並列処理する。開発者は Map 関数と Reduce 関数だけを記述すれば、データの分散、並列実行、障害復旧はフレームワークが自動的に処理する。

Hadoop の基盤技術として広く普及し、ビッグデータ処理の基礎概念として定着した。関数型プログラミングの map と reduce (fold) から着想を得ている。

動作の流れ

入力データ (テラバイト級)
    ↓ 分割
[チャンク1] [チャンク2] [チャンク3] ...
    ↓ Map (並列実行)
[(k1,v1), (k2,v2)] [(k1,v3), (k3,v4)] [(k2,v5)] ...
    ↓ Shuffle (同じキーをグループ化)
[k1: [v1,v3]] [k2: [v2,v5]] [k3: [v4]]
    ↓ Reduce (並列実行)
[k1: result1] [k2: result2] [k3: result3]

ワードカウントの例

入力: "hello world hello foo world hello"

Map フェーズ (各ワーカーが並列実行):
  ワーカー1: "hello world hello" → ("hello",1), ("world",1), ("hello",1)
  ワーカー2: "foo world hello"   → ("foo",1), ("world",1), ("hello",1)

Shuffle フェーズ:
  ("hello", [1,1,1]), ("world", [1,1]), ("foo", [1])

Reduce フェーズ (各キーを並列集約):
  ("hello", 3), ("world", 2), ("foo", 1)

MapReduce が解決した問題

2004 年以前、大規模データの分散処理は以下の課題を開発者が個別に解決する必要があった。

  • データの分割と各ノードへの配布
  • 並列実行の制御とスケジューリング
  • ノード障害時のリトライと復旧
  • 中間結果のシャッフルとソート
  • 結果の集約

MapReduce はこれらを抽象化し、開発者は「各レコードに何をするか (Map)」と「グループ化された結果をどう集約するか (Reduce)」だけを記述すればよくなった。

現代での位置づけ

MapReduce は革新的だったが、以下の制約から、現在は Apache Spark や Flink に置き換えられつつある。

観点 MapReduce (Hadoop) Apache Spark
処理モデル バッチのみ バッチ + ストリーミング
中間データ ディスクに書き出し インメモリ処理
速度 遅い (ディスク I/O がボトルネック) 10〜100 倍高速
プログラミング Map/Reduce の 2 段階に制約 SQL、DataFrame、柔軟な DAG
反復処理 苦手 (毎回ディスクから読み直し) 得意 (メモリにキャッシュ)

MapReduce の最大の弱点は、各フェーズの中間結果をディスクに書き出すことだ。機械学習のように同じデータを何度も反復処理するワークロードでは、毎回ディスクから読み直すオーバーヘッドが致命的になる。Spark はデータをメモリに保持するため、反復処理が桁違いに速い。

AWS での MapReduce

AWS では EMR (Elastic MapReduce) が Hadoop/Spark のマネージドサービスを提供している。ただし、多くのユースケースでは EMR よりも以下のサーバーレスサービスの方がコスト効率が良い。

  • Athena: S3 上のデータに SQL でクエリ (MapReduce の集計処理を SQL で代替)
  • Glue: ETL ジョブを Spark ベースで実行 (サーバーレス)
  • Lambda + Step Functions: 小〜中規模のデータ処理を並列実行

JavaScript の map/reduce との関係

JavaScript の Array.prototype.map() と Array.prototype.reduce() は、MapReduce と同じ概念をシングルマシンで実行するものだ。

const orders = [
  { category: 'books', amount: 1500 },
  { category: 'electronics', amount: 30000 },
  { category: 'books', amount: 2000 },
];

// Map: 各要素を変換
const mapped = orders.map(o => ({ key: o.category, value: o.amount }));

// Reduce: 集約
const totals = orders.reduce((acc, o) => {
  acc[o.category] = (acc[o.category] || 0) + o.amount;
  return acc;
}, {} as Record<string, number>);
// { books: 3500, electronics: 30000 }

実務での活用方法は関連書籍にも詳しい。

関連用語