Re:Official Google Blog: Sorting 1PB with MapReduce
by lutorm on Saturday November 22, 2008 @11:36AM
(#373001)
Isn't the mapreduce sort NlogN in the number of entries? That would make 1e13 log 1e13/(1e10 log 1e10) 68s/4 = 6.1h. So they were actually faster than the possible scaling? Doesn't sound right...
Re:Official Google Blog: Sorting 1PB with MapReduce
by jwilliams on Saturday November 22, 2008 @10:41PM
(#373464)
This is a really good point.
I was assuming that the sort was actually a partial sort - returning the top "x" (admittedly - even then isn't linear). However, I was also assuming (n << x), which would almost certainly be the case with a large data set. It's a fairly common approach, but not sure why I automatically assumed it.
If the sort is complete, then yeah, that changes things.
Re:Official Google Blog: Sorting 1PB with MapReduce
by russell on Saturday November 22, 2008 @01:43PM
(#373063)
Sounds dead on to me. The typical sort is O(N logN). O can be slightly different between the 1T runs and 1P runs, e.g. slightly difference latency or pattern of disk failures. Every sort is sensitive to the data distribution. There is probably an interesting distribution of results across the runs.
(68sec * 1024) / 60 / 60 / 4 --- (68 sec for 1TB) (1024 to make 1TB) /60/60 (hours) and /4 as there are 4x as many computers....
So ideally taking the 1TB sort to 1PB on 4x the hardware would be 4.83hrs.
Google's 1PB sort was in 6 hours - So that's fairly linear. Impressive.