マルレク Googleの分散技術 第2回

JJUGクロスカンファレンスでの話
マルレク Googleの分散技術 第1回

仕事の関連で遅刻。。。かなりの大入りで完全に満席で立ち見も少しいた。
でも私の隣席2人はガン寝。。。寝るならくんなよともうね(ry

今回はMapReduceをがっつり2時間。ほんとはMapReduceとSawzallで2時間だったんですがSawzallは時間の都合次に延期。

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