Map-Reduce

Map-Reduce処理は以下の3つのステップからなる.

• マップステップ：入力データ $[x_1, x_2, \ldots, x_n]$ の各要素にマップ関数 $f$ を適用して中間データ $[y_1, y_2, \ldots, y_n]$ を生成する.\[\text{map}(f, [x_1, x_2, \ldots, x_n]) = [f(x_1), f(x_2), \ldots, f(x_n)]\]
• シャッフルステップ：中間データを適切なグループに分ける.\[S([y_1, y_2, \ldots, y_n]) = \{ [y_{i_1}, y_{i_2}, \ldots, y_{i_k}] \}_{k=1}^m\]
• リデュースステップ：各グループにリデュース関数 $g$ を適用して最終結果を生成する.\[\text{reduce}(g, [y_{i_1}, y_{i_2}, \ldots, y_{i_k}], y_0) = g(g(\ldots g(g(y_0, y_{i_1}), y_{i_2}) \ldots ), y_{i_k})\]
• 最終結果の統合：リデュースステップの結果を統合する.\[\text{Final Result} = [ \text{reduce}(g, \text{Group}_1, y_0), \text{reduce}(g, \text{Group}_2, y_0), \ldots, \text{reduce}(g, \text{Group}_m, y_0) ]\]

Map-Reduceは,大規模データ処理の問題を解決するために,Googleのエンジニアである Jeffrey Dean と Sanjay Ghemawat により2004年に開発.この2人により,OSDI '04 [6th Symposium on Operating Systems Design and Implementation]において,"MapReduce: Simplified Data Processing on Large Clusters"として発表.この発表により,Map-Reduceの基本概念と実装の詳細が公開された.なお,この2人はMapReduce以外にも,大規模構造化データの効率的な保存と取得を可能とするBigTable[2006],高性能なキー・バリューストアの実装を提供するLevelDB[2011],グローバルスケールでの一貫性のあるトランザクション実現により分散データベースの新たな可能性を示したSpanner[2012]などの開発でも知られる.

Google内部での利用に続いて,2006年からApache Hadoopプロジェクトが開始.Doug Cutting と Mike Cafarella が中心となって開発が進められる.このHadoop Map-Reduceは,Yahoo!,Facebook,Twitterなどに採用されていった.

2010年代前半になると,バッチ処理に最適化されている点などのMap-Reduceの限界が認識され始めた.そこで,2010年代中盤以降,Map-Reduceの概念を拡張し,より柔軟な処理を可能とするApache Spark,Apache Flinkなどの新しい分散処理フレームワークが登場.

しかし,Map-Reduceはビッグデータ処理の基礎を築き,分散コンピューティングの考え方を大きく変えた重要な技術であることには変わりがない.また,機械学習やLLMの分野においても,データ前処理などにMap-Reduceの概念が活かされている.

INDEX