# MapReduce ## 概要 [[Google]]が開発した長時間実行バッチジョブ向けの大規模計算フレームワークであり、原論文は[[Jeffrey Dean]]・[[Sanjay Ghemawat]]による[[@2004__OSDI__MapReduce - Simplified Data Processing on Large Clusters]](OSDI 2004)。利用者が指定するmap関数とreduce関数だけで並列化・耐障害性・データ分散・負荷分散の詳細を隠蔽するプログラミングモデルである。[[@2010__VLDB__Dremel - Interactive Analysis of Web-Scale Datasets]]では、MapReduce(MR)はDremelと競合するものではなく補完関係にあるシステムとして位置づけられる。Dremelは、従来MRの一連のジョブを要していた対話的分析を数秒で処理できるが、MR自体を置き換える設計ではなく、MRパイプラインの出力を分析したりMR以前のプロトタイピングに使われたりする(Source: [[@2010__VLDB__Dremel - Interactive Analysis of Web-Scale Datasets]] §1, §10)。 Dremel論文の実験では、Sawzallで書かれたMRジョブをrecord-oriented・columnar-orientedの2通りのストレージで実行し比較しており、MR-on-recordsが87TBを読むのに対し、カラム型ストレージへの変更だけでMR-on-columnsは約0.5TBしか読まず、実行時間が1桁短縮される(時間→分)ことが示された。DremelへのさらなるMR-native実行への切り替えでもう1桁短縮される(分→秒)(Source: [[@2010__VLDB__Dremel - Interactive Analysis of Web-Scale Datasets]] §7 MR and Dremel, §8 Observations)。 MRの成功はHadoopをはじめとする多数のサードパーティ実装や、並列DBMSとMRを組み合わせたハイブリッドシステム(HadoopDBなど)を生んだ(Source: [[@2010__VLDB__Dremel - Interactive Analysis of Web-Scale Datasets]] §9 Related Work)。 ## Hiveによる高水準化 Facebookのデータウェアハウスでは、MapReduceを多様な処理を表す最低限の共通基盤として使い、その上に[[Apache Hive]]を置いた。 HiveはSQL・表・列・パーティションをMapReduceジョブ列とHDFS操作へ変換し、パーティション枝刈り、述語プッシュダウン、部分集約、結合順序の変更などを自動化した。 この構成はMapReduceのスケーラビリティを保ちながら、非エンジニアリング利用者が数時間から数日かかる低水準プログラムを書かずに分析できるようにした。(Source: [[@2010__SIGMOD__Data Warehousing and Analytics Infrastructure at Facebook]]) ## SREの視点: 周期パイプラインの実装フレームワークとしてのMapReduce [[@2016__OReilly__SRE Book - Chapter 25 Data Processing Pipelines]]では、MapReduceはFlumeと並んで、Googleで日常的に運用される周期パイプラインを書くためのフレームワークの例として言及される。同章は、MapReduceのようなフレームワークで書かれた周期パイプライン自体がスケール時に脆いモデルであると論じ、ワーカー数がデータ量に対して十分でジョブ間の相対スループットが均一な間は安定するが、有機的な成長とともにハングしたチャンクやモアレ負荷パターンといった問題を蓄積すると指摘する。同章はMapReduceの内部実装には立ち入らず、あくまで周期パイプラインという設計パターンの代表的な実装手段として引用するにとどまる。(Source: [[@2016__OReilly__SRE Book - Chapter 25 Data Processing Pipelines]]) ## WSC規模での実運用データとテール耐性(『Computer Architecture: A Quantitative Approach』6章) 本書6章はGoogleのMapReduce運用実績を2004年8月から2016年9月まで11時点にわたり集計した表(図6.2)を示す。月間ジョブ数は2004年8月の29,000件から2016年9月には9,577万件へ3300倍に増加し、同期間で入力データ量は0.2PBから1兆1553PBへ拡大した。平均ジョブはサーバ数百台を使用し、HPC分野の高度チューニング済みアプリケーションを除けば総CPU時間・利用サーバ数のいずれで見ても現代で最も並列度の高いアプリケーション群と位置づけられる。(Source: [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Chapter 6 Warehouse-Scale Computers to Exploit Request-Level and Data-Level Parallelism]] §6.2) MapReduceのスケジューラは、性能ばらつきの大きい数百台規模のノード群を扱うため、タスクの完了速度からノードごとの遅延を検知し、ジョブ終盤で未完了タスクのバックアップ実行を他ノードへ投入して先着した結果を採用する。この設計は[[Jeffrey Dean]]・[[Luiz André Barroso]]が[[@2013__CACM__The Tail at Scale]]で定式化した「テールレイテンシ」問題への初期の実装的対処例であり、リソース使用率を数パーセント増やす代償として大規模タスクの完了時間を30%短縮した。ノードは定期的にマスタへ完了タスクを報告し、期限内に応答がなければマスタは当該ノードを「死亡」とみなし作業を再割り当てする——障害が日常的に起きる前提で耐障害性を最初から組み込んだ設計である。(Source: [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Chapter 6 Warehouse-Scale Computers to Exploit Request-Level and Data-Level Parallelism]] §6.2) MapReduceは[[Google File System]](GFS)またはColossusに依存してどのノードからでもファイルを供給できるようにし、WSCのオーバーサブスクリプションが強い上位ネットワーク階層(アレイ・WSC全体)ではなく、帯域の太いラック内・ローカルでのデータ局所性を活かす設計を前提とする。(Source: [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Chapter 6 Warehouse-Scale Computers to Exploit Request-Level and Data-Level Parallelism]] §6.2, §6.3) ## 関連 - ソース: [[@2010__VLDB__Dremel - Interactive Analysis of Web-Scale Datasets]] / [[@2004__OSDI__MapReduce - Simplified Data Processing on Large Clusters]] / [[@2016__OReilly__SRE Book - Chapter 25 Data Processing Pipelines]] / [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Chapter 6 Warehouse-Scale Computers to Exploit Request-Level and Data-Level Parallelism]](§6.2、2004〜2016年の運用実績データとテール耐性の実装例) - エンティティ: [[Google]] / [[Jeffrey Dean]] / [[Sanjay Ghemawat]] / [[Luiz André Barroso]] / [[Google File System]] - 概念: [[列指向OLAPデータベース]] / [[並列データベース]] / [[タスク並列フレームワーク]] / [[周期パイプライン]] / [[テールレイテンシ耐性技術]] ## 出典 - [[@2010__VLDB__Dremel - Interactive Analysis of Web-Scale Datasets]] - [[@2004__OSDI__MapReduce - Simplified Data Processing on Large Clusters]] - [[@2016__OReilly__SRE Book - Chapter 25 Data Processing Pipelines]](周期パイプラインの実装フレームワーク例としての言及) - [[@2019__MorganKaufmann__Computer Architecture - A Quantitative Approach - Chapter 6 Warehouse-Scale Computers to Exploit Request-Level and Data-Level Parallelism]] §6.2, §6.3