YappoLogs

GoogleのMapReduceをいまさら妄想した

ブームとかそういうのはあんまり関係無いけど、MapReduceについての妄想だけしてみた。

主要コンポーネント

MapReduceには大体6つのパーツから構成される。

client	shellから叩かれるコマンド的な何か
manager	各種 worker を管理する。といっても投げっぱなしで結果がいつまでも帰ってこなかったらworkerを捨てるだけ。同じjobを複数のworkerに投げてる。
map worker	mapの処理
combiner	mapの直後に実行出来るreduceのような物、無くても構わない、出力はmapと同じ？
shuffle(Group by Key)	map workerから帰って来たkey/valueを集約する
reduce worker	reduceの処理
fs	分散システムに対応したfsと、local disk

処理内容

mapに対しては任意のデータが与えられる。 mapはkeyとvalueからなる大量のデータを戻す。 shuffleにて、全てのmapのkeyをまとめあげて、keyごとにreduce workerにkeyとvalue listを渡す。 reduceは、受け取ったkey/value listを処理する。

key/valueなデータに特化したPlaggerってことで間違いないのかなぁ？ mapperで大量のデータから必要な物をフィルタリング(Subscription,Aggregator)して、reducerで実際の処理(Filter,Publish,Notify)を行うというPlaggerみたいな感じ。

全てのmapやreduceに大しての各workerの仕事量は平均的になる様にバランス良く配置する。 多分、mapやreduceの直前で、それぞれのjobの大きさを計測してmanagerに渡したりしてるのかな。

shuffuleなんかはBig Tableとか使ってるのかもしれんね。 それか集計処理自体MapReduce使ってたり？

map workerの処理が全て終わったら reduce worker が走り出す。 これは、あるいみ無駄な気もするからmap workerが終わるのを待たずにreduce worker走らせてるだろうなぁ。(どうもそうでもないらしい。) mapとshuffuleは同時に処理出来るけど、reduceは他と一緒に処理出来ないそうな。key/value単位で処理するというMapReduceの設計的な制約かな？ map,reduceが終わりそうになったら、まだ終わってないworkerのjobをそのまま空いてるwokerに投げて速く終わったworkerの方のresultを採用する事で、途中でworkerがコケても泣かないですむ。

mapとreduceの粒度は細かくした方がよい。 mapperでserialize、reducerでdeserialize。 mapだけ繰り返し呼びたい時はreduceからmapを呼び出す。

オレオレ実装するとしたら

この仕組み自体は対した事無くて、肝は大量のデータを、たくさんのmap workerやreduce workerへjobを投げたりresultを受け取る仕組みとshuffleする処理にある。 ちゃちいものだったらDanga::Socketとかで実装出来るレベルっぽいな。 もちろんGFSも肝だけど、memcachedとかでとりあえずいい気がする。(可用性おいとくという事) というかMapReduce自体もGearmanで構成出来たりしね？

実際問題としてオレオレでMapReduce作る時に考える事は、データとコードを各worker serverに送る仕組みを真っ先に考えなければいけない。 単純にjobを分散出来た所で、それはMQとかに毛が生えた程度の面白さしかないから、分散ストレージ的な物もセットにしないとオレオレMapReduceもどきとは言えないだろうけど、memcachedとか使えば解決するよね？よね？

CPANにMapReduceってモジュールが有ったんだけど、何故か削除されてる。。。backpanには残ってる。

もっとも忘れてはならないMapReduceの肝は、1 serverで並列処理をしてCPUがmulti coreしてる恩恵を受ける為に有るのではなく、大量のworkerを使う事によって大量のメモリを利用したり、大量のdiskを使う事によるi/o負荷を分散させる事に意味が有る。 それなんで、WebからMapReduce使う用な事はないのかね？

でも少数serverでMapReduceやったって良いじゃないか！

Posted by Yappo at 2007年12月25日 21:31 | TrackBack | tech