Slashdot Log In
Google Sorts 1 Petabyte In 6 Hours
Posted by
Soulskill
on Sun Nov 23, 2008 11:53 AM
from the sort-of-fast dept.
from the sort-of-fast dept.
krewemaynard writes "Google has announced that they were able to sort one petabyte of data in 6 hours and 2 minutes across 4,000 computers. According to the Google Blog, '... to put this amount in perspective, it is 12 times the amount of archived web data in the US Library of Congress as of May 2008. In comparison, consider that the aggregate size of data processed by all instances of MapReduce at Google was on average 20PB per day in January 2008.' The technology making this possible is MapReduce 'a programming model and an associated implementation for processing and generating large data sets.' We discussed it a few months ago. Google has also posted a video from their Technology RoundTable discussing MapReduce."
Related Stories
[+]
MapReduce Goes Commercial, Integrated With SQL 99 comments
CurtMonash writes "MapReduce sits at the heart of Google's data processing — and Yahoo's, Facebook's and LinkedIn's as well. But it's been highly controversial, due to an apparent conflict with standard data warehousing common sense. Now two data warehouse DBMS vendors, Greenplum and Aster Data, have announced the integration of MapReduce into their SQL database managers. I think MapReduce could give a major boost to high-end analytics, specifically to applications in three areas: 1) Text tokenization, indexing, and search; 2) Creation of other kinds of data structures (e.g., graphs); and 3) Data mining and machine learning. (Data transformation may belong on that list as well.) All these areas could yield better results if there were better performance, and MapReduce offers the possibility of major processing speed-ups."
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.
Kudos to Google (Score:5, Funny)
for knowing how important the Library of Congress metric is to us nerds!
Re:Kudos to Google (Score:5, Funny)
for knowing how important the Library of Congress metric is to us nerds!
But at least now we know Google can sort out petafiles.
Parent
Re:Kudos to Google (Score:5, Funny)
Parent
Re:Kudos to Google (Score:4, Funny)
So Google can sort through 12 LoCs in 6 hours.
Wow, that's 2 LoC/pH
Parent
Unit conversion (Score:5, Funny)
Yay! We finally have unit conversion from 1 LoC to bytes! So...20 PB = 6LoC, means that 1 LoC = 3,333... PB :)
Re: (Score:3, Informative)
Re:Unit conversion (Score:4, Informative)
No, 1 PB = 12 LoC, so 1 LoC = 0.0833... PB
Also, I'd like to make some kind of swimming pool reference.
Parent
Re: (Score:2, Interesting)
Assuming it was written in binary in a font that allows for 1 digit per 2mm, the length of the data would be 183251938 m, or 1145324 times the perimeter of an olympic-sized swimming pool.
Re: (Score:3, Informative)
Oh darn. Clearly I was converting pound-congresses to kilos first.
Re: (Score:2)
What format are they using for the books when doing this calculation as to the size of the LoC?
Raw Text?
PDF?
JPEG? ....
Re: (Score:3, Funny)
Sure, it's -4.15 Edsels.
That's Easy (Score:5, Interesting)
Re:That's Easy (Score:5, Insightful)
I came here to post the same thing. If they sorted a petabyte of Floats, that might be pretty impressive. But if they're sorting 5-terabyte video files, their software really sucks.
Not enough info to judge the importance of this.
Parent
Re:That's Easy (Score:5, Informative)
I think this is the data set. I could be wrong though. The article (yeah yeah) says that
In our sorting experiments we have followed the rules of a standard terabyte (TB) sort benchmark.
Which lead me to this page [hp.com] that describes the data (and it's available for download).
Parent
Re:That's Easy (Score:5, Informative)
From TFA: they sorted "10 trillion 100-byte records"
Parent
Re:That's Easy (Score:5, Funny)
And yet google don't even convert petabytes to libraries of congress in the google calculator.
Or perhaps I got the syntax wrong.
Parent
Re:That's Easy (Score:5, Funny)
Huh? This isn't the parent post I was trying to reply to.
Parent
Need to benchmark against the best sorts (Score:5, Insightful)
Sorts have been parallelized and distributed for decades. It would be interesting to benchmark Google's approach against SyncSort [syncsort.com]. SyncSort is parallel and distributed, and has been heavily optimized for exactly such jobs. Using map/reduce will work, but there are better approaches to sorting.
Re: (Score:2)
And Google is trying to make money off mapreduce(as an api of sorts), so now you're surprised they're using their massive resonance over the market, especially geeks, in order to heighten awareness of their product?
On the other hand, what they're trying to prove is mapreduce's worth, as a workload divider(how to break-up 20PB for sorting), not necessarily how optimal it is in the current situation. They have a better test/sample of mapreduce, but it's a trade secret to them(how it's used to index the pages
Re: (Score:3, Interesting)
Parallel/distributed sorting doesn't eliminate the need for map/reduce, it just helps spread the problem set across machines.
Here's the thing though...its the distributing of the problem set and the combining of the results that is the hard part - not map/reduce.
Map and reduce are simple functional programming paradigms. With map, you apply a function to a list - which could be either atomic values or other functions. With reduce, you take a single function(like add or multiply, for instance) and use that t
Re:Need to benchmark against the best sorts (Score:4, Insightful)
>>Using map/reduce will work, but there are better approaches to sorting.
It kinda bugs me that Google trademarked (or, at least, what they named their software) after a programming modality that has been in parallel processing for ages. In fact, MPI has a mapreduce() function that, well, does a map/reduce operation. I.e., farms out instances of a function to a cluster, then gathers the data back in, summates it, and presents the results to someone.
It kind of bugs me (in their Youtube video linked in TFA, at least) that they make it seem that this model is their brilliant idea, when all they've done is write the job control layer under it. There's other job control layers that control spawning new processes, fault tolerance, etc., and have been for many, many years. Maybe it's nicer than other packages, in the same way that Google Maps is nicer than other map packages, but I think most people like it just because they don't realize how uninspired it is.
It'd be like them coming out with Google QuickSort(beta) next.
Parent
Finally... (Score:5, Funny)
I will be able to catalog my pr0n in my lifetime:
Blondes, Brunettes, Red heads, Beastial^H^H^H^H^H "Other"
tagging (Score:5, Interesting)
It's not enough to sort by blond, black, gay, scat, etc. Some categories are a combination that don't belong in a hierarchy.
That is where tagging comes in. Sorting can be done on-the-fly, with no one category intrinsically more important.
Parent
Re:tagging (Score:5, Funny)
pr0n for Geeks, volume 18: Sorting On-the-Fly
Parent
Re: (Score:2, Funny)
One ups Yahoo & Hadoop (Score:3, Interesting)
Let's see if Yahoo responds!
Re: (Score:2)
Hadoop uses MapReduce :) From their site:
Re:One ups Yahoo & Hadoop (Score:4, Informative)
Parent
Re:One ups Yahoo & Hadoop (Score:5, Interesting)
Parent
Its About Time.... (Score:2, Funny)
Finaly... A system with enough power to run vista efficiently.
Re:Its About Time.... (Score:4, Informative)
Are you sure? It wasn't marked Vista capable.
Parent
Re:Its About Time.... (Score:4, Funny)
Not only that the extra processors aren't covered under the EULA and require special extra licenses.
Parent
Not impressive... (Score:5, Funny)
Is it new data (Score:2)
0s and 1s (Score:2, Funny)
That's a lot of computing power to use just to get 4,000,000,000,000 0s and 4,000,000,000,000 1s.
Libraries of congress? (Score:3, Insightful)
Honestly, How am i supposed to know what "..the amount of archived web data in the US Library of Congress as of May 2008." Looks like!? I've been to the library of congress, i've seen it, its a metric shit-ton of books (1 shit-ton = Shit * assloads^fricking lots), but i have no clue what the LoC is archiving, what rate they're going at it, and what the volume is of it.
clever strategy (Score:3)
They clearly have the ability to respond to emergencies. And this puts it out there that they can...
eg;
1) Foot n mouth out break in cattle
2) A supliment to census data
3) Finding information of dissidents/traitors(bloggers)
Amazing feat... (Score:5, Funny)
Today from Google, the god of all things and doer of all things good in the universe, many millions of dollars in computer equipment were able to sort lots of things, in about the amount of time you would think it would take for millions of dollars of equipment to sort things.
In other news, a woodchuck was found chucking wood as fast as a woodchuck could chuck wood.
Congrats Google, you have a HUGE data set, and an even bigger wallet.
MapReduce = map + reduce (Score:4, Interesting)
If you feel the urge to play with MapReduce (or reade the paper), you don't need a fancy Linux distro [apache.org] to do it. MapReduce is simply the map() and reduce() functions, exactly as implemented in Python. Granted, Google implementation can work with absurdly large data sets, but for small data sets, Python is all you need.
Re: (Score:3, Informative)
True, but not quite the point. The map and reduce functions as you say are implemented in python (and a great many other languages), but what makes MapReduce special is that you replace the Map function with one which distributes it out to other computers. Because any map function can be implemented in parallel you get a speed boost for however many machines you have (dependant on network speeds etc....).
So yeah, you can do it in Python but you arent going to be breaking any records untill you implement you
Re: (Score:3, Informative)
Exactly. There is nothing special to map and reduce.
Here's an example. Map and reduce are functional programming tools that work with lists. So we'll start with a simple list.
1 2 3 4 5
Now we'll take a function - x^2, and map it to the list. The list now becomes:
1 4 9 16 25.
Now, we'll apply a reduce function to our list to combine it to a single value. I'll use "+" to keep it simple. We end up with:
55
And that is pretty much all there is to map and reduce.
Re: (Score:3, Informative)
Almost, but not quite. MapReduce has a slightly different format than just map() and reduce(). Here is the signature of map and reduce from a theoretical functional language:
map(): A* -> B*
reduce(): B* -> C
Whereas in MapReduce:
map: (K, V)* -> (K1, V1)*
reduce: (K1, (V1)*)* -> (K2, V2)*
I think that is mostly accurate. Read more accurate/detailed report in MapReduce revisited [cs.vu.nl][PDF].
Re:Sort? Sort what? (Score:5, Informative)
I realize, slashdot..., but maybe you could glance at the article which states:
10 trillion 100-byte records
Parent
Re: (Score:3, Insightful)
You do have to merge them all back together at the end...
But I'm sure you can do better tonight.
Re: (Score:3, Insightful)
Re: (Score:2)
Odds are they're using the mythical "google algorithm", so they're probably going to keep what they're doing quiet.
Re:Sort? Sort what? (Score:5, Funny)
Parent
Re:20,111 Servers ?? (Score:4, Insightful)
Parent
Re:20,111 Servers ?? (Score:4, Insightful)
Oh dear. 4000*362 ~= 1440*20111 / 20. So you assumed that the sorting would scale linearly. fail.
Parent
Re:MapReduce (Score:5, Informative)
The individual functions map and reduce are quite standard. The innovation here is the systems work they've done to make it work on such a large scale. All the programmer needs to worry about is implementing the two functions, they don't have to worry about distributing the work, ensuring fault tolerance, or anything else for that matter. That is the innovation.
They mention in the article that if you try and sort a petabyte you WILL get hard disk and computer failures. Hell, you can only read a terabyte hard disk a few times before you encounter unrecoverable errors. The system for executing those maps and reduces is what is important here. The important parts are in the design details, such as dealing with stragglers. If you have 4000 identical machines, you won't necessarily get equal performance. If a few of those machines have a bit flipped and started without disk cache, they might see a huge decrease in read/write performance. The system needs to recognize this and schedule the work differently. That can make a huge difference in execution time. If you graph the percentile complete of a MR job, you'll often see that it quickly reaches 95% and then plateaus. The last 5% may take 20% of the time, and good scheduling is required to bring this time down.
But like I said, the innovation isn't in the idea of using a Map and Reduce function, it is the system that executes the work.
Parent