昨日の丸山先生のMapReduceのレクチャーのメモを記す。自己中心的なまとめかたであることをご容赦願いたい。
MapReduceは以下の動作とほぼ同じ
cat $* | woWord | sort | uniq -c
Mapは分割可能性（≒どう分割しても並列処理できる）があるがReduceは条件付で分割可能性がある。reduceの分割可能性はキー境界をまたがないこと。Reduceに渡す結果の束ね方重要。
map部分の処理は、複数のマシン上で分割可能である。
同様に、reduce部分の処理も、URL_AやURL_Kのようなデータの繰り返しの境界を破らなければ、容易に分割可能である。
問題は、mapの出力を分割してsortして、reduceに渡す方法である。
このとき、mapの出力を、同じキーは同じグループに属するように分割すればいい。
それで、（reduceが分散可能なように）キー境界を破らないようなpartitionを別ける。
代表となるMasterを選出してWorkerに指示をするパターンをMaster/Workerパターンといい、並列処理システムではオーソドックスなパターン。
MapReduceのライブラリは、まず、入力ファイルを、M個にsplitする。
沢山のマシンのクラスタ上で、 MapReduceのプログラムのコピーを起動する。
プログラムの一つは、特別で、MapReduceのmasterとなる。
残りは、masterによって仕事が割り当てられるworkerになる。
M個のmapのタスクとR個のreduceのタスクが割り当てられる。
masterは、仕事をしていないworkerに、これらの仕事を割り当てる。
map関数の産み出す中間出力のkey/valueのペアは、メモリ上にバッファされる。
バッファ上のペアは、partition関数によって、R個に分割されたの領域のローカル・ディスクに、定期的に書き出される。
Mapはメモリに保持＝＞Partition関数によってR個（Reduce個数）に分割されたDISKに保存される (※１）＝＞Reduce処理
※1 ・・ ここではMapが動作するローカルマシンに保存されるといわれていたが、Reduceが動作するリモートマシンに保存するのかもしれない。Mapがすべて完了するまでReduceは動作しないのでReduceのマシンまで転送してあげた方が効率的か？
SortはReduce側で行う。Reduceの最初の仕事。中間データ量が収まらなかったらDISKに書く。すべてのMap処理が終わらなければ開始されない。
Combinerは典型的には、reduceで実行されるコードと同じものである。Reduceに渡す前に可能な限りMap側でやっておく。reduce関数の出力は最終の出力となるが、combine関数の出力は、reduceに送られる中間出力に書き出される。
2 件のコメント:
map → reduce へのデータ転送部分ですが、map 側から push するか reduce 側から pull するか、というところですよね。
push, pull どちらでも実装できるかとは思います。 ただ push する場合、送り先の reduce node でのディスク容量が足りているかどうか、とか、受け入れ可能かどうか、とか、正しく転送が終わったときの通知をどうするか、とか、あまりに並列にコピーさせるとコンテキストスイッチや write 時のランダムアクセスなどで遅くなる、とか、いろいろとありそうです。
pull する場合なら、pull して良いものを master 側に聞くなり map側のあるファイルを見て判定するなりして、あとはひたすら取りに行く、できるものならスレッド 2,3 個あげて並列に取りに行く、とかにすれば、シンプルに実装できるかと思います。
Blogのpingみたいに、「ちょうど今pull 側が取りに行くべき場所が分からない」といった場合などには push は有効かな、とか考えると、pull|push の使い分けのおおよその線引きができるのかな、なんて思います。
あ、あと、map と shuffle/combine は同時にやっているんじゃないのかな、なんて思ったりします。 iterator まわすコストは削れるし、map済みのデータを一旦書いて shuffle/combine で読み込んで処理してまた書く、みたいなところが省けそうですし。
その辺のところは Hadoop の MapReduce の実装読め、とか言われればそれまでですがｗ
コメントを投稿