Slashdot Log In
Open Source Solution Breaks World Sorting Records
Posted by
Soulskill
on Sat May 16, 2009 09:18 AM
from the out-of-sorts dept.
from the out-of-sorts dept.
allenw writes "In a recent blog post, Yahoo's grid computing team announced that Apache Hadoop was used to break the current world sorting records in the annual GraySort contest. It topped the 'Gray' and 'Minute' sorts in the general purpose (Daytona) category. They sorted 1TB in 62 seconds, and 1PB in 16.25 hours. Apache Hadoop is the only open source software to ever win the competition. It also won the Terasort competition last year."
Related Stories
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
Overlords (Score:3, Funny)
Re:Overlords (Score:5, Funny)
I for one welcome our new datasorting overlords!
With a name like Apache Hadoop, I wouldn't be surprised if they came from Star Wars.
Parent
Re:Overlords (Score:4, Informative)
I wouldn't be surprised if they came from Star Wars.
Actually, it came from Google. Sorta.
Apache Hadoop is an implementation of MapReduce that Google uses in their search engine. I believe the details were found in a paper Google released on it's implementation of MapReduce.
Parent
Re:Overlords (Score:4, Informative)
"MapReduce: Simplified Data Processing on Large Clusters [google.com]." Jeffrey Dean and Sanjay Ghemawat, OSDI '04.
They wrote about it in Beautiful Code, too (great book). MapReduce isn't complex, in fact the name comes from a feature that a lot of functional languages provide (yeah, I know, it's not exactly the same thing).
There are many implementations of it. The wikipedia article is pretty informative: http://en.wikipedia.org/wiki/MapReduce [wikipedia.org]. I didn't know about "BashReduce"... Heh.
Parent
Re: (Score:3, Funny)
Fastest implementation of BubbleSort EVER!
Re:Overlords - Trivia (Score:5, Informative)
Parent
Re:Overlords (Score:5, Funny)
Parent
Is it settled? (Score:5, Funny)
So, it appears they have finally sorted out whether open source beats proprietary.
Re: (Score:2)
When's it going to be 1.0? (Score:3, Insightful)
Re: (Score:2)
Software is done when it's good and ready!
Re:When's it going to be 1.0? (Score:5, Informative)
Parent
Re: (Score:3, Insightful)
Isn't 1.0 production for most software jargon?
Nah, that's 6.0
MS DOS 6.0
IE 6.0
Visual Studio 6.0
I doubt anybody would want to use an earlier version than that!
Re: (Score:3, Insightful)
I'm only wish more programs were open source (Score:2, Interesting)
... truth be told, a lot of good engineering could happen if many of peoples favorite commercial applications could have the souce distributed with them, a lot of old games for instance coudl be updated and maintained.
I think what holds the progress of open source back is interesting projects that exist that people want to work on but are locked away under corporate lock and key.
Re: (Score:2)
People maintaining old games is now what the companies that produced those games want... They would rather sell you new games, or sell the old ones to you again..
Corporations will always put their own interests first, and those interests will often be detrimental to everyone else.
Great! It's open source! (Score:2)
But has anyone patented it yet? Patents trump copyright after all.
Re: (Score:2)
You can't patent Apache 2.0 licensed stuff.
Also, you can't patent software*.
*in Europe
Re:Great! It's open source! (Score:5, Interesting)
Not yet, but they are working on it. They tried to snuck it through by hiding it in the amendments of an agricultural bill. Luckily Poland kept watch and rose a stink about it.
It's not over. There is too much money to be gained for that.
Parent
Re: (Score:3, Interesting)
Re:Great! It's open source! (Score:5, Interesting)
Why isn't this illegal - adding unrelated legislation to a ? Is there anywhere in the world why this practice is not permitted, or better yet, prosecuted?
The GP is confusing a bunch of things. First, the Council of Ministers threw out all limiting amendments from the European Parliament and reached an Political Agreement on a shoddy text through backdoor maneuvering by Germany and the European Commission [google.com]. That text would have turned the European Patent Office's practice of granting software patents into EU legislation.
A Political Agreement has no juridical nor legislative value, but it has never happened that a political agreement was later on annulled and that negotiations were reopened. So also in this case, even though the German, Dutch, Spanish and Danish parliaments afterwards passed motions asking to reopen the discussions, the Council's bureaucrats did not want to do that because it "would undermine the efficiency of the decision making process".
Anyway, once you have a Political Agreement (which is reached by the representatives of the ministries responsible for the matter at hand) and nobody "wants" to discuss it anymore, the agreement can be placed as an "A item" on any EU Council of Ministers meeting, since it only needs rubber stamping in that case. In the case of the Software Patents Directive, it appeared several times as an A item on the agenda of an Agriculture and Fisheries meeting (which is presumably where the GP's confusion stems from).
In principle, there would have been nothing wrong with that, but in this case there was no actual political agreement, and in particular Poland was very unhappy with the way it had been treated. So 4 times in a row, Poland either had this "A item" removed from the agenda (sometimes at the last minute, because the responsible Polish minister had to be informed that they were again trying to get it through at a meeting he had no business with), or turned it into a "B item", which means that it can't be rubber stamped but that they first have to talk a bit about it (which nobody wanted to do).
In the end it still did get approved, but that whole circus helped with in convincing the EU Parliament to table a resolution asking the Commission to restart the directive's process [ffii.org], and when the Commission refused to later on squarely reject it [ffii.org].
You can find some more of my thoughts on the Council's behaviour here [ffii.org].
Parent
Re: (Score:3, Interesting)
There was an episode of the Simpsons where Springfield is going to be destroyed by a meteor. Congress meets to quickly pass legislation to fund the evacuation of the city. At the last moment, a Congressman steps up to the podium and says "I'd like to add a rider providing $30 million for the perverted arts". The bill is defeated.
It's funny because it's true.
Re:Great! It's open source! (Score:4, Funny)
"Why isn't this illegal"
Because they made it legal by passing it on a Totally Unrelated Bill.
Parent
Re:Great! It's open source! (Score:4, Informative)
Here in the UK, the patent office has been issuing software patents for some time in "anticipation" of them becoming legal at some point in the future.
No, I don't understand that either.
Parent
Re: (Score:2)
But has anyone patented it yet? Patents trump copyright after all.
There are a number of patent applications related to MapReduce from Google and Yahoo.
They won the "Who has the most moneys" award. (Score:5, Insightful)
Re:They won the "Who has the most moneys" award. (Score:4, Interesting)
If its not written to disk, then there is no achievement here (you don't perform 1 minute+ sorts and then throw the result away in real-world scenarios)
Parent
Re: (Score:2)
Java (Score:5, Insightful)
Re: (Score:2)
Waiting for similar hardware to become available for other languages.
I think Tim Bray is on the right track with his widefinder idea.
See Widefinder 1 [tbray.org] and Widefinder 2 [sun.com] for details.
Re:Java (Score:5, Insightful)
Well, not to endorse the "Java is slow" meme or anything, but starting from a red light I can beat most cars across the intersection on my bike.
Likewise if I had to drive across country in the shortest time possible, I'd choose a Ford F250 if the challenge stipulated I had to bring 3000 pounds of bricks with me.
Speed is a very task specific notion.
Parent
Re: (Score:2)
Something doesn't seem right.
Yahoo's cluster had 3,800 nodes with 4 disks per node giving it roughly 15,200 drives plus or minus the dead nodes/drives in the cluster.
The Google cluster had 4,000 nodes with 48,000 hard drives. 12 drives per node doesn't sound like the typical Google servers [youtube.com] I've seen. That one looks like 2-4 drives. This other video [youtube.com] seems to show the storage node which looks like it has 5-10 drives.
The reason I bring up drives is that sorting 1PB likely involves hd access the more drives, th
Re: (Score:3, Informative)
But how much of those libraries exist to achieve Java's religious beliefs on abstraction?
Wow, how did this get modded insightful? For one, calling the design of a programming language a "religious belief", then asking a vague question about it without providing even a basis of an answer is just inflammatory.
But the answer that anybody who knows what they're talking about will tell you is, none of them. Java's abstraction mechanisms are built into the language. None of the standard libraries are necessary to support it. They take advantage of it, of course, and you'd be crazy to not take adv
The benefits of parallelizing everything! (Score:2, Informative)
2005 winner used only 80 cores and achieved it in 435 seconds. So with 800 cores what 2007 winner achieved is 297 seconds ?
Its not only number of cores its how the logic to use parallel nodes properly to do a particular task is important.
Hadoop won with 1820 cores (910 nodes w/ 2 cores each) at 209 seconds.
I'm all for better sorting algorithms, but eventually the cost of parallelizing something overtakes the profit made. That being said, Hadoop's internal filesystem made to be redundant, which is an important feature whenever you're dealing with large amounts of data.
Hadoop uses Google's MapReduce, by the way, whereas the competition didn't. It's nice to see MapReduce being used in a more public eye.
While better sorting algorithms -do- matter, I have to
Not quite as impressive as it sounds (Score:4, Informative)
Google's sorting results from last yeat (link [blogspot.com]) are much faster; they did a petabyte in 362 minutes, or 2.8 TB/sec. They minute sort didn't exist last year, but Google did 1TB in 68 seconds last year, so I think it may be safe to assume that they could do 1 TB in under a minute this year. Google just hasn't submitted any of their runs to the competition.
From the sort benchmark page [sortbenchmark.org], the list the winning run as Yahoo's 100TB run, leaving out the 1PB run; that implies the 1PB run didn't conform to the rules, or was late, or something.
People have commented that this is a "who has the biggest cluster" competition; the sort benchmark also includes the 'penny' sort, which is how much can you sort for 1 penny of computer time (assuming your machine lasts 3 years), and 'Joule' sort, how much energy does it take you to sort a set amount of data. Not surprisingly, the big clusters appear to be neither cost efficient nor energy efficient.
Re:Not quite as impressive as it sounds (Score:5, Interesting)
In sorting a terabyte, Hadoop beat Google's time (62 versus 68 seconds). For the petabyte sort, Google was faster (6 hours versus 16 hours). The hardware is of course different. (from Yahoo's blog [yahoo.net] and Google's blog [blogspot.com])
Terabyte:
Machines: Yahoo 1,407 Google 1,000
Disks: Yahoo 5,628 Google 12,000
Petabyte:
Machines: Yahoo 3658 Google 4000
Disks: 14,632 Google: 48,000
Yahoo published their network specifications, but Google did not. Clearly the network speed is very relevant.
The two take away points are: Hadoop is getting faster and it is closing in on Google's performance and scalability.
Parent
Google Sort (Score:2, Interesting)
Im looking forward to sorting my search results by Date, Title, Description, Author, etc..
My algorithm can sort anything in 1 second (Score:2)
Re:I'm sure that I can rock their scores (Score:5, Funny)
My sort [wikipedia.org] will totally beat yours!
Parent
Re: (Score:3, Funny)
Bogosort: for when you have you are paid by the hour, but aren't penalised for being late.
Re: (Score:3, Funny)
Bogosort: for when you have you are paid by the hour, but aren't penalised for being late.
with my luck, bogosort would get it right the first time.
Re:I'm sure that I can rock their scores (Score:4, Funny)
I've asked lots of interview candidates to implement randomSort. They've never heard of it, so then I describe the algorithm.
Watching their eyes go wide is the highlight of the interview, typically.
Occasionally some person who has overcome their interview nervousness will, with eager honesty, try to implore to me that this is not a very good sort algorithm, and that much better ones are taught in universities these days.
Good Times.
Parent
Re: (Score:2)
I've asked lots of interview candidates to implement randomSort. They've never heard of it, so then I describe the algorithm.
Did you change roles from developer to HR?
Re:I'm sure that I can rock their scores (Score:4, Funny)
No, he clearly changed roles from developer to Evil HR. He's probably directly subservient to Catbert.
Parent
Re: (Score:2)
100 bytes, 10 byte keys. (Score:5, Informative)
Parent
Re: (Score:2, Insightful)
Re:What data? (Score:5, Funny)
This doesn't say anything if we don't know what kind of records were supposed to be sorted.
It's amazing what you can learn if you actually RTFA.
All of the sort benchmarks measure the time to sort different numbers of 100 byte records.
If that's not good enough for you, post your email address and maybe someone will be kind enough to send you the 100TB and 1PB data files they used.
Parent
Re: (Score:2)
It would be interesting to do it.
I'm willing to volunteer if you're starting a port. Just mail me (my email is on my user page).
Re: (Score:3, Informative)
It usually outperforms its Java sibling in an order of magnitude.
Do you have any actual benchmarks for that? According to the benchmarks page at the official cLucene wiki [sourceforge.net], cLucene is roughly twice as fast as the Java Lucene at indexing, and it's only about 10% faster at the actual searching. That's not even close to an order of magnitude.