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ライブラリがやってくれること

  • 自動的に並列化
  • 実行時のシステムが↓の管理の面倒を見る
    • 入力データ分割
    • マシン群での実行スケジュール
    • マシン故障への対応
    • マシン間のコミュニケーション

プログラマはmapとreduceの使い方さえ分かればよい→EOD(Ease of Development)

分散処理のアルゴリズムとしてのMapReduce

適用例:分散grep

grepの場合
map:行が与えられたパターンにマッチする文字列を含んでいるならその行を出力
reduce:中間出力をそのまま最終出力にコピーする


この例の場合、mapを1行ずつやろうと2行ずつやろうと10行ずつやろうと同じ結果になる
・全てのデータをアトミックに分割しても結果は変わらない(1行ずつ)

・結果は分割の仕方に依存しない(1行ずつ、2行ずつ、10行ずつ)
これが分散可能であるということ


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がお仕事する

  1. M個のMapWorkerがそれぞれ
    1. 処理
    2. 中間結果をメモリにバッファリング
    3. ディスクに書き出し
    4. 書き出した場所の情報はMasterに送られる
  2. M個のMapWorker全てのお仕事が終了
  3. R個のReduceWorkerがそれぞれ
    1. Masterに中間結果の場所を問い合わせる
    2. 中間結果をsort等する(実はこれが一番重い)
    3. Reduce
    4. 終結果を出力する

終結果は一箇所にまとめられたりはしない
R個のReduceWorkerがあればR個の最終結果が出力される
そのR個全体が最終結果ということになる


ちなみに実際にはどれくらいの規模かというと↓こんな感じだそうな

  • マシン:2000台
  • MapWorker数:20万個
  • ReduceWorker数:5000個

FaultTolerance

  • MapWorkerがコケたら、他のWorkerに割り当てなおす
    • 該当Workerでのすでに終了したタスクの結果も捨てる(MapWorkerがコケた≒ディスクがコケた=中間結果が読めない)
  • 死に掛けWorker(コケてはいないが極端にパフォーマンスが落ちてるWorker)はどうする?
    • Map工程の終わりのほうでは、空いたWorkerで処理を多重化する
    • 全体が終了したとき処理が遅れていたWorkerは無視してしまう
    • これで最大44%パフォーマンスが向上した
  • ユーザーコードのバグでMapReduce処理全体が止まってしまう可能性がある場合
    • 特定コードでエラーが起きたら次回以降はスキップしてしまう
    • (大規模統計等の場合少数は捨ててしまってかまわない)