JJUGクロスカンファレンスでの話
マルレク Googleの分散技術 第1回
仕事の関連で遅刻。。。かなりの大入りで完全に満席で立ち見も少しいた。
でも私の隣席2人はガン寝。。。寝るならくんなよともうね(ry
今回はMapReduceをがっつり2時間。ほんとはMapReduceとSawzallで2時間だったんですがSawzallは時間の都合次に延期。
- アルゴリズムは実現するハードウエアに依存する
- 例えば一般的な場合メモリの容量制約を受ける
- パイプでつないだシェル等はメモリの都合上2G以上のファイルを扱えない。
- MapReduceおさらい
- Map:入力からのKeyValueを生成する
- Sort:同じキーを纏めソートする
- Reduce:同一キーを合算する
- 分散処理
- 分散可能とは
- 4個でも10個でも任意のn分散が可能
- 分散の仕方に依存しない
- 極論アトミックに分散してもOK
- 結合律 (x+y)+z=x+(y+z)
- 可換律 x+y = y+z
- 効率よく分散するには
- 全てのノードが同じ動作である
- ノード間通信が存在しないこと
- 結果の同一性確認ができること
- nに対し同じ答えをだす。
- nが極大の時だけでなく任意のnで効率が良いことが求められる
- 分散≠並列
- 並列処理:単一CPU
- 分散処理:複数CPU
- メッセージパッシングしないことが重要
- MPIは遅い
- MasterWokerの欠点の回避
- MasterWoker自体をスケールアウトしてしまう。
- Map>シャッフル>Redeuce処理と呼ばれるやり方
- 詳細の流れは以下になる
- Split 入力ファイルを分割(16M程度)
- Map Mapにつめる
- Combine 同一キーが重複した場合MapWoker内でReduceを呼び出し効率化する
- Partition メモリ上のMap情報をローカルファイルに書き出し
- Sort ソート処理
- Reduce 集計
- ゾンビワーカーの対処
- M/RではMap処理が終了しソートする時点で同期する必要がある
- そのため1つのWokerでも処理遅延すると全体の処理が遅くなる
- 回避の為Map処理全体の6割が終わった時点でMap処理が全二重化される
- 早く終わったWokerが遅いのを助ける
- どちらのノードが終わった場合でもMasterは当該処理が終了したととらえる
- 回避の為Map処理全体の6割が終わった時点でMap処理が全二重化される
- これにより3割程度の性能改善が見込まれる
- 特定のソート処理は44%の改善が見られたらしい
- Master障害の対処
- 現時点(論文の時点)ではMaster障害が起こった場合は再実行としている
- チェックポイントを作成するのは簡単だが行っていないとのこと
- 任意コードへの対応
- 予想外のユーザーコードが登録されることによりWorkerが障害を起こすことがある
- このような場合Wokerは最後のあえぎとして障害対象レコードをMasterにUDP送信する
- Masterは再実行時には当該箇所をスキップさせる
- エラーを無視している
- エラーを無視するやりかたは面白い
- エラーを無視している
- MSがGoogleの論文を翻訳してリバースエンジニアリングした論文を発表しているらしい
- 論文に対する論文が認められる程凄い世界