MapReduceとSawzall　〜Wakhok マルレク・サブセミナー「Googleの分散処理技術」二日目〜

先日に引き続き、秋葉原の稚内北星学園大学東京サテライト校で行われたマルレク・サブセミナーに行ってきました。

http://www.wakhok.ac.jp/tyo-sat/subsemi2007.html

今日は二日目で「MapReduceとSawzall」。

今回は前回の反省を活かし、早めに到着して良い席をGETできました。開始を待つ間にMapReduceの論文を眺めて予習。前回の講義スピードと同じだとすると、とても予習ナシでは内容についていけないので。

今回も内容が盛りだくさんで、講義はハイスピード。途中会場からの質問なんかも軽く盛り上がり、残念ながら予定していたSawzallの話は全く出来ませんでした。

では簡単に、興味深かったことをノートから抜粋。

「MapReduce」

  • 関数型プログラミングモデルに基づき、大規模なデータセットの処理／生成を行う。
  • keyとvalueのペアを処理して、中間マップを作成するmap関数。
  • 中間マップを処理／マージするreduce関数。
  • RDBMSがシステム全体のボトルネックになっている⇒注目されている分散キャッシュ⇒メモリ上でkey/valueを持つ効率のよさ。
  • DHT（分散ハッシュテーブル）
  • 自動並列・安価で大量のマシン・大規模なクラスタ。
  • 数千のマシンから数テラのデータを処理している。
  • map関数はkey/valueからkey/valueを出力する。
  • 同じkeyを持つ中間出力をまとめて(ソートして)次に渡す。
  • reduce関数はkey/valueを処理。
  • Map　⇒　GroupBy　⇒　Reduce。この一連の処理が必要。
  • 分散処理に向く処理とそうでない処理がある。
  • MapReduceは分散処理の本質をついている。
  • 適用可能例：分散grep
    • map：行内に与えられたパターンがあればその行を出力する。⇒対象データを分割すれば分散処理が可能。
    • reduce：入力をそのまま出力するだけ。
    • ⇒ 全てのデータをアトミックに分割しても同じ結果が得られる。
    • 結合律と可換律。
  • 適用可能例：LogからURLの頻度を累計する。
    • map：ファイルを読んでURLごとに（URL、１）を出力。
    • sort：URLでソート。
    • reduce：URL数をカウント、出力。
    • ⇒ mapは完全に分割可能。
    • ⇒ reduceは同一keyを複数に分割してはいけない。（コレ結構ポイントだよね）
  • mapの結果をどのように分割してreduceに渡すかが重要。
  • ⇒ Partition関数：中間データをreduceワーカーの数に分割する際に、keyでオーダーをかけて出力する。その後にソート。
  • 適用可能例：Webリンクの逆グラフ
    • Webページのソースに含まれるリンク先targetを（target,source）と出力する。（sourceとtargetを逆にするのがミソ）
    • targetでソート。
    • (target,list(source))をreduceは出力。 ⇒ ページランクを作成する基本。
    • ページ毎に分割すればmapは分割可能。
    • reduceはkeyをまたがっていなければ分割可能。
  • MapReduceの処理速度は内部のソートの速度に依存する。

「分散処理可能性とMapReduce」

  • 分散処理のメタファ
    • １，０００人で巨大な鶴を折れ。
    • １，０００人で千羽鶴を俺。　　　⇒　この違い
  • 大事なのは、以下の３点。この条件が大切。
    1. 全員が同じことをする。
    2. 会議／会話をしない。
    3. 結果が同じである。
  • 分散処理で大切なのは、メッセージパッシングをしないこと。⇒ 並列処理ではメッセージパッシングが必須。
  • MapReduceはワーカー間で通信をしない。コレが大切。 ⇒ Master-Workerパターン。
  • 同一のプログラム、情報の交換を行わない、任意のnに対して同一の結果。
  • データを分割してmap処理。
  • 同じkeyのデータを同じノードに集めてShuffling処理。 ⇒ 全体で最も処理時間がかかる。
  • 同じkeyを持つデータを整理するreduce処理。
  • それぞれの処理。
    • Split：入力ファイルをM個に分割。
    • MasterとWorker：仕事の割り当て。
    • Map：メモリ上に書き出し。
    • Partition：R個に分割されたローカルディスクへ書き出し(定期的に)。⇒ hash(key) mod R
    • Sort：中間ファイルを読んでソート（RPCで読み込み）。
    • Reduce：整理統合。
    • Complete/Output File：R個のファイルに出力。
    • Combiner：mapの結果同一keyが大量の場合、利用されるオプション。reduceに渡されると大きすぎるデータの場合、mapの段階でreduce処理を行ってしまう。URLカウントの場合等でmap処理で（URL,1）と出力するところを（URL,5)とかにしてしまう。　⇒ ネットワーク負荷を下げることになる。
  • FaultTlerance
    • Masterが死んだら全体を再実行（abort）
    • BackupTask：遅いmap処理は他のworkerにも同一処理を依頼し、早く結果が帰ってきたほうを採用する。
    • SkippingBadRecords：おかしなデータをスキップする仕組み（オプション）。⇒ Masterがそれを制御している。（workerがシグナルハンドラを持ち、masterに飛ばす）

う〜む、当日つけた３ページにわたるノートをつらつらと書き連ねてみました。図に関してはとりあえずパス。

MapReduceは面白かった。あらためて「並列処理」と「分散処理」の違いを再認識できたし、メッセージパッシングの有無とか、全員が同じ仕事同じ結果とか、結合律と可換律といった数学的な(？)裏づけとか、非常に勉強になりました。

これまでの経験上、エンタープライズ系システムには分散処理は不向きだとは思うけど、この辺を再度きちんと認識した上で分散処理可能性を考えていくというのは意味のあることだと思う。
完全な分散処理ではなくても、部分的な適用とかもできればそれはそれでいいしね。


さて、次回は12月25日(クリスマス！)に実施されます。次は「Apache HadoopとAmazon EC2/S3」。今回のセミナーの中でもAmazonの話はちょこちょこ出てきたけど、Amazonの技術も興味深いものが多いですよね。実際に動くMapReduceとしてのHadoopも気になるし。

楽しみなしだいであります！