MapReduce 論文ノート
起源
著者らは、膨大な量のデータを扱う業務において、何百ものデータ処理プログラムを書きました。それらには以下の特徴がありました：
- ビジネスロジックは単純
- データ量が膨大なため、何百台ものコンピュータ上で分散計算を行う必要がある
これにより、以下の課題が生じました：
- 並列計算の方法
- データの分散方法
- フォールトトレランスの実現方法
データ処理プログラムの多くのコードは、ビジネスロジックではなく、これらの類似した問題の処理に費やされていました。
そこで、エンジニアがビジネスロジックに集中し、上記の非機能要件を隠蔽できるようにするため、Lispやその他の関数型言語から借用した2つの概念に基づく新しい抽象化が提案されました。これがMapReduceです。
実装
実行ロジック
- 入力データをM個のスライスに分割し、M個のMapワーカーに割り当てる
- Masterはデータパイプラインとしてスケジューリングを行う
- Mapタスクはユーザー定義のMapメソッドを呼び出し、結果をローカルメモリに格納する
- 定期的にディスクにダンプし、さらにR個に分割してR個のReduceワーカーに割り当てる準備をする
- Reduceワーカーは、Masterからタスクを割り当てられた後、RPCでデータを読み取り、読み終わったらディスク上でソートする
- Reduceワーカーはソート済みデータに対してユーザー定義のReduceメソッドを呼び出し、反復処理を行い、インクリメンタルな計算を行う
- 計算が完了すると、ユーザーコードのロジックに戻る
Partition（分割）の方法が重要であり、不要なシャッフリングを避けることが望ましいことがわかります。
データ構造
- 各map/reduceタスクの状態（idle/in-progress/completed）を保存する
- 完了した各mapタスクについて、中間ファイルの位置とサイズを保存し、reduceワーカーに通知する
フォールトトレランス
- Masterは基本的に故障しないが、状態を定期的に保存し、故障後に復旧する方法も採用可能
- Masterは定期的にワーカーにpingを送信し、応答がない場合はそのワーカーを故障とみなす
- mapタスクについては、完了の有無にかかわらずすべてリセットして再スケジューリングする。これは、mapの結果がワーカーのローカルに保存されるため、ワーカーが故障すると結果にアクセスできなくなるためである。
- reduceタスクについては、未完了のもののみを再スケジューリングする。これは、reduceの結果はグローバルにアクセス可能なファイルシステムに保存されるためである。
- mapタスクが再スケジューリングされると、すべてのreduceワーカーに通知されるため、新しい位置からデータを取得する。
バックアップタスク
最後に実行されているいくつかのタスクがMapReduceの進行を大幅に遅らせる可能性があります。これは「ストラグラー（遅延タスク）」が存在するためで、様々な理由により実行速度が極端に遅くなることがあります。この場合、masterは最後に実行されているいくつかのタスクに対してバックアップタスクを起動します。これによりリソース使用率は数パーセント増加しますが、実行時間を大幅に短縮できます。
改良点
パーティション
出力ファイルは分散されているため、ユーザー提供のパーティション関数を使用して、関連するキーの結果を集約することが可能です。
ローカルデバッグ
ローカル環境で実行することができます。
性能
大規模な2つのクラスタでテストを実施しました。1つはソート用、もう1つはパターンマッチング用です。
grep
10^10個の100バイトファイルからパターンを検索しました。1,700台のマシンで150秒かかり、そのうちプログラムの配布に1分を要しました。
sort
10^10個の100バイトファイルをソートしました。
まとめ
非常に説得力のある内容でした。