Wakhok マルレク・サブセミナー 第二回「MapReduceとSawzall」
はじめに、サブタイトル後半のSawzallはMapReduce用のDSLでこれが結構凄い上に、
GFSやMapReduceのようにオープンソースの代替物がないのだそうですが、
時間がないので詳しい話は聞けませんでした。
後日公開される講演資料に載ってるみたいです。
2007/12/31追記
2007/12/20に資料が公開されました。
丸山先生レクチャーシリーズ2007-2008第1回「Googleの分散処理技術」
こちらの下にある「サブセミナー第2回ハンズアウト」というPDFです。
MapReduceの位置付け
関数型プログラミングモデルに基づいて、大規模なデータセットの処理・生成を行うもの
MapReduceというのはアルゴリズムの名前であり、
Googleで実際に稼動しているその実装の名前でもある。
MapReduce:数万台規模の分散処理が実際にちゃんと動いている
(一方、grid:あんまりうまく行っていない)
MapReduceって実際何なの
RDBはエンタープライズシステムのパフォーマンスのネック
→ディスク上のFileSystemのindexから発展したため
→オンメモリならリレーショナルじゃなくてkey/valueでいいじゃん
map関数:(IN)key/valueペア→(OUT)中間的なkey/valueペア
reduce関数:中間的なkey/valueペアから、同じkeyに関連した値をマージ
MapReduceライブラリがやってくれること
- 自動的に並列化
- 実行時のシステムが↓の管理の面倒を見る
- 入力データ分割
- マシン群での実行スケジュール
- マシン故障への対応
- マシン間のコミュニケーション
強い意味での分散処理可能性
スケールアウトする分散処理って何?
単純な処理の方がスケールアウトする
例えば、千羽鶴を折るというタスク
- みんな同じことをする
- 各人割り当てられた数だけもくもくと鶴を折る
- お互いに通信しない
- 隣の人と相談する必要はない
- 結果は同じ
- 誰が折っても同じ鶴が出来上がる
指示を出す人一人と、鶴を折る人たちn人で必ず同じように千羽鶴が完成する
つまり、1人でも10人でも100人でも1000人でも同じように千羽鶴が完成する
(千羽鶴なのでn≦1000に限定されるけど)nが大きければ大きいほど早く完成する
この分散処理パターンをMaster-Workerパターンという
並列と分散の違い
- 並列…単一マシン上で動く
- 分散…複数の違ったマシン上で動く
並列の代表はErlangで、基本はメッセージパッシング⇔分散のMaster-Workerパターンでは、Worker同士は「お互いに通信しない」
並列と分散はまったく違うということ
出力の分散
結果は同一か?
ばらんばらんに出力されていると同一だとしても確認しにくい
↓分かりやすくする
Shuffling処理:同じキーを持つデータ(Reduceはこの単位で行われる)を同じノードに集めて整列する
小部分に分割されたものの全体、というデータのあり方が重要
(GFSも一緒。物理的なノードはばらばらだけど全体で一つのデータとみなす)
処理の流れ的なもの
Sprit
入力ファイルをM個に分割する(各数十MBくらい)
M個のMapWorkerとR個のReduceWorkerがお仕事する
- M個のMapWorkerがそれぞれ
- 処理
- 中間結果をメモリにバッファリング
- ディスクに書き出し
- 書き出した場所の情報はMasterに送られる
- M個のMapWorker全てのお仕事が終了
- R個のReduceWorkerがそれぞれ
- Masterに中間結果の場所を問い合わせる
- 中間結果をsort等する(実はこれが一番重い)
- Reduce
- 最終結果を出力する
最終結果は一箇所にまとめられたりはしない
R個のReduceWorkerがあればR個の最終結果が出力される
そのR個全体が最終結果ということになる
ちなみに実際にはどれくらいの規模かというと↓こんな感じだそうな
- マシン:2000台
- MapWorker数:20万個
- ReduceWorker数:5000個
FaultTolerance
- MapWorkerがコケたら、他のWorkerに割り当てなおす
- 該当Workerでのすでに終了したタスクの結果も捨てる(MapWorkerがコケた≒ディスクがコケた=中間結果が読めない)
- 死に掛けWorker(コケてはいないが極端にパフォーマンスが落ちてるWorker)はどうする?
- Map工程の終わりのほうでは、空いたWorkerで処理を多重化する
- 全体が終了したとき処理が遅れていたWorkerは無視してしまう
- これで最大44%パフォーマンスが向上した
- ユーザーコードのバグでMapReduce処理全体が止まってしまう可能性がある場合
- 特定コードでエラーが起きたら次回以降はスキップしてしまう
- (大規模統計等の場合少数は捨ててしまってかまわない)