MapReduceのデータモデル

http://d.hatena.ne.jp/naoya/20080513/1210684438

MapReduceでMapからReduceに入るデータは、key-valuesペア。key-valueペアで
ないことに注意。

こんな感じ。

# key  => values (Iterator)
200    => [ 1,1,1,1,1,1,1,1,1,... ]
304    => [ 1,1,1,1,1,1,1,1,1,... ]
404    => [ 1,1,1,1,1,1,1,1,1,... ]
500    => [ 1,1,1,1,1,1,1,1,1,... ]

keyはsortされている。

しかし、Mapで出てきたデータをどうやってsortするのだろう。Mapは分散したノー
ドで計算されているわけでその結果も分散して入ってくる。Reduceの手前でsort
するのであれば、結局Reduceでsortするのと手間(消費メモリとか)は変わらない。

分散したデータをうまくsortする仕組みがあるのかなぁ。