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."
Good question. I had to look it up [wikipedia.org]. (Would it have killed the submitter or editor to include a link?)
Basically, the software gets its name from the list processing functions "map" (to take every item in a list and transform it, thus producing a list of the same size) and "reduce" (to perform an operation on a list that produces a single value or smaller list). The actual software has nothing to do with "map" and "reduce", but it does to tokenization and processing on massive amounts of data.
Presumably the Map/Reduce part comes from first normalizing the items being processed (a map operation) then reducing them down to a folded data structure (reduce), thus creating indexes of data suitable for fast searching.
Google's mapreduce framework has a native resource manager that's aware of what resources are available, aware of failures, and is prepared to reschedule failed processes and where (and when?) to direct finished tasks. Basically it's a job que for distributed processing using a private network. MapReduce is just one tool. You aren't going to get much out of it after you max out your local machine's processing until you start work on the rest of it. What's really scary is that MySQL announces that they final
I'm a little dyslexic. I immediately see the wheelbarrow as a MySQL icon (which is almost universally a MySQL article) and read _M_apReduce into SQL = MYSQL in the title. This is proof I'm a reactionary blowhard who often fails to comprehend the summary, much less read the article.
There is no link because my wrongometer is not working, it has melted through its resin casing.
Basically, the software gets its name from the list processing functions "map" (to take every item in a list and transform it, thus producing a list of the same size) and "reduce" (to perform an operation on a list that produces a single value or smaller list).
As does my Slashdot user name. Great, now everything is going to think I'm calling on people to "filter" this software somehow, which I'd never heard of before this story. And it's "highly controversial", that's helpful.
Map-Reduce is definitely a technique related to grid computing, but they are not one and the same.
The most popular (to my knowledge) open source Java library implementing MR is Hadoop [apache.org].
Here's the algorithm in a nutshell (anyone who knows more than me, please correct, and I'll be forever grateful). I have a bunch of documents and I want to generate a list of word counts. So I begin with the first document and map each word in the document to the value 1. I return each mapping as I do it, and it is merge-sorted by key into a map. Let's say I start with a document of a single sentence: John likes Sue, but Sue doesn't like John. At the end of the map phase, I have compiled the following map, sorted by key:
but - 1
doesn't - 1
like - 1
likes - 1
John - 1
John - 1
Sue - 1
Sue - 1
Now begins the reduce phase. Since the map is sorted by key, all the reduce phase does is iterate through the keys and add up the associated values until a new key is encountered. The result is:
but - 1
doesn't - 1
like - 1
likes - 1
John - 2
Sue - 2
Simple. Stupid. What's the point? The point is that the way this algorithm divides up the work happens to be extremely convenient for parallel processing. So, the map phase of a single document can be split up and farmed out to different nodes in the grid for processing, which can be processed separately from the reduce phase. The merge-sort can even be done at a different processing node as mappings are returned. Redundancy can be achieved if the same document chunk is farmed out to several nodes for simultaneous processing, and the first one that returns the result is used, the others simply ignored or canceled (maybe they're queued up at redundant nodes that were busy, so canceling means simply removing from the queue with very few cycles wasted). Similarly, because the resulting map is sorted by key, an extremely large map can easily be split and sent to several processing nodes in parallel. The original task of counting words across a set of documents can be decomposed to an ridiculous extent for parallelization.
Of course, this doesn't make much sense to actually do this unless you have a very large number of documents. Or, let's say you have a lot of computing resources, but each resource on its own is very limited in terms of processing power. Or both.
This is very close to the problem a company like Google has to solve when indexing the web. The number of documents is huge (every web page), and they don't have any super computers—just a whole ton of cheap, old CPUs in racks.
At the end of the day, Map-Reduce is only useful for tasks that can be decomposed, though. If you have a problem with separate phases, where the input of each phase is determined by the output of the previous phase, then they must be executed serially and Map-Reduce can't help you. If you consider the word-counting example I posted above, it's easy to see that the result required depends upon state that is inherent in the initial conditions (the documents)—it doesn't matter how you divide up a document or if you jumble up the words, the count associated with each word doesn't change, so the result you're after doesn't depend on the context surrounding those words. On the other hand, if you're interested in counting the number of sentences in those documents, you might have a much more difficult problem. (You might think you could just chunk the documents up at the sentence level, but whether or not something is a sentence depends upon surrounding context—a machine can easily mistake an abbreviation like Mr. for the end of a sentence, especially if that Mr. is followed by a capital letter which could indicate the beginning of a new sentence...which it almost always is. Actually...if you're smart you can probably come up with a very compelling argument that this
I'm not quite entirely sure what you mean by the verb "map", the noun "map", and in which sense you use it in each instance. Also, I'm unsure why you think sorting enters into it.
My understanding of MapReduce is that it's (surprise!) all about applying the higher-order functions map and then reduce. Here's what they do:
Map takes a function f and a list [x_1,..., x_n], then returns [f(x_1),..., f(x_n)]. That is, it applies f to all the elements of the list. [variants takes multi-argument functions and
I only have a passing familiarity with Map-Reduce, so I'm definitely not an authoritative source. It's definitely possible that sorting isn't part of the algorithm itself, but rather one example of context around how it's often implemented. It definitely makes sense, though—why not merge-sort the results as mappings are returned? If you do implement it this way, it just makes it possible to deal with really large maps that need to be spread over multiple nodes.
by Anonymous Coward
on Tuesday August 26 2008, @04:03PM (#24756451)
and can I run Linux on it? Or it on Linux?
Have you ever considered that it might itself be a distro? A, like, super-leet distro that the big Valley firms have been hacking together for the past ten years, only giving access to employees that sign a super-nasty NDA? A disto that traces back to a Photoshop 1.0 plugin for resizing GIFs?
MapReduce is just an idiom (pattern if you will) for processing collections (arrays, lists, trees, database tables...) of data. There is often another piece:filter that cuts out bits you don't want to do but that can easily be done in the reduce step, though sometimes it is done somewhere else.
For example, suppose you want to compute exp(x) using the usual Taylor series expansion and 20 terms. Start with the list [0,1,2,3,4,5,.. 19]. Then map the function:
f(i) = x^i / i!
to each entry in the li
Probably someone who read the post and knows how wrong he is. Like you traverse the web every time you want to look up a search term or how a map is really the same as load balancing...
Data warehousing (here I mean databases stored in column order for faster queries, etc.) may get a lift from using map reduce over server clusters. This would get away from using relational databases for massive data stores for problems where you need to sweep through a lot of data, collecting specific results.
I think that it is interesting, useful, and cool that Yahoo is supporting the open source Nutch system, that implements map reduce APIs for a few languages - makes it easier to experiment with map reduce on a budget.
Except that relational databases are not just indexed objects copied across a large network of cheap PCs. What's good for Google may not be suitable for other databases, who actually care about ACID properties of transactions and not necessarily have the infrastructure to run highly parallel select queries.
I'm currently working on a project where users will be able to apply different types of transformation and collection to timestamped data and map/filter/reduce style algorithms are perfect ways to give them that capability.
The kind of capability might look something like : give me the average temperature at hourly intervals for each day in the year for a dataset that spans multiple years. In this case there's no map, and the reduce does the work, in other cases this may be turned around.
Actually, MapReduce doesn't do anything in the way data's stored- it's just a pipe between two sets of stored data, and really just needs an interface on both ends to get the task into MapReduce (which is what it seems the projects TFS/A mention do). BigTable is the storage mechanism that's incompatible with most traditional row-based RDBMSs. GFS is just the underlying storage mechanism.
Note that all of those were published several years ago- I'd bet dollars to donuts that Google is _WAY_ beyond this internally if it's just reaching commercial use by their competitors.
Sawzall is essentially designed around the mapreduce framework. It's impossible to *not* write a mapreduction in Sawzall. The way it works:
Your program is written to process a single record. The magic part happens when you output: you have to output to special tables. Each of these table types has a different way that it combines data emitted to it.
So, during the map phase, your program is run in parallel on each input record. During the reduce phase, the reduction happens according to the way the output tables do whatever operation was specified.
There was some work to be done having enough different output tables to do everything that was useful, especially since you might want to take the output and plug it in as the input to another phase of mapreduction.
One of the biggest reasons this was a major innovation for Google was that it let some of the people who weren't really programmers still come up with useful programs, because the Sawzall language was pretty simple (especially when combined with some of the library functions that had been implemented to do common sorts of computations.) There were also some interesting ways in which the security model was implemented, but as far as I know they haven't been published yet.
There certainly are plenty of other technical things that can be done to improve a system like MapReduce (and I know that many of them were in various forms of experimentation when I left the company) but at least some of them are highly dependent on Google's infrastructure, and not really relevant to a general discussion. (I suspect that the papers linked above might have some hints, but it has been a while since I looked at them.)
Correct. I sometimes wonder how many/. readers are really developers? Mapreduce is old, old technology, Google just made it famous and, maybe, documented. It is not always useful in all cases but never worse than any other method in throughput. If you have to "map" information and the more they are unbalanced, the better it gets.
Actually the question about developers came because a lot of replies are talking about API - if you code, write your own, it is very easy once you understand the principle. And I c
The correct project name is Hadoop [apache.org]. It was factored out of Nutch 2.5 years ago. And Yahoo has been putting a lot of effort to make it scale up. We run 15,000 nodes with Hadoop in clusters of up to 2,000 nodes each and soon that will be 3,000 nodes. I used 900 nodes to win Jim Gray's terabyte sort benchmark [yahoo.com] by sorting 1 TB of data (100 billion 100 byte records) in 3.5 minutes. It is also used to generate Yahoo's Web Map [yahoo.com], which has 1 trillion edges in it.
Mahatma Gandhi actually said, "First they ignore you, then they ridicule you, then they fight you, then you win."
The tool custodians of the massively complex relational database warehouse tools are seeing their world turn obsolete as the lighter weight MySQL and the more flexible mapreduce and the BASE [neu.edu] worlds evolve beyond them, so yes, they are going to kick up a fight. Don't let the screen door hit you in butt on the way out, guys.
You [the articles authors] seem to be under the impression that MapReduce is a database. It's merely a mechanism for using lots of machines to process very large data sets. You seem to be arguing that MapReduce would be better (for some value of better) if it were a data warehouse product along the lines of TeraData. Unfortunately the resulting tool would be less effective as a general purpose mechanism for processing very large data sets.
Though this post is my introduction to both MapReduce and the argument, it strikes me that the people arguing are arguing the wrong problem.
While MapReduce might be used against some structured data, it looks to be something for unstructured data and dynamically inventing structures in unstructured data. Additionally, you might want to keep that new structure around for a while. You might want to load it up with terabytes of data. At the same time, this data is less and less useful over time.
Protocol buffers are now Google's lingua franca for data -- at time of writing, there are 48,162 different message types defined in the Google code tree across 12,183.proto files. They're used both in RPC systems and for persistent storage of data in a variety of storage systems.
If you think about it, Protocol Buffers are just about perfect for MapReduce applications. First, Protocol Buffers data streams are "flat" structures, very similar to database tables. If you need hierarchical data, I think that you'd tend to use multiple tables that incorporate foreign keys, rather than embedding the hierarchy every time
Stonebraker isn't exactly the one to complain about this: just as MapReduce is being overhyped these days, relational databases were being overhyped in the 1970's, and he rode that wave all the way to fame and fortune. 30 years later, although every database system in the world calls itself "relational", very few database applications actually are relational.
MapReduce is indeed a simple, decades-old parallel programming technique. It's not the be-all-and-end-all of parallel programming, but it's good for s
I don't think you can credit Bjarne with "compiled code is faster than interpreted code" (or the 21st century version: "compilers can perform better optimizations that JIT translators").
C++ happens to be the most popular fully compiled language, having edged Fortran out of that position some time near the end of the last century.
Back in the early '80s, when he was coming up with C++, the big Fortran savants were saying stuff like "Fortran is bigger than ever. There are more than X million Fortran programmers. Everywhere I look there has been an uprising... a lot of teaching was going to Pascal, but more are teaching Fortran again. There has been a backlash."
----
And that's not the only thing C++ has in common with Fortran, either.
" (or the 21st century version: "compilers can perform better optimizations that JIT translators").
Actually, JITters can do some optimizations that compilers can't--by splitting the compilation into a frontend and a backend. The front end is essentially just a parser, and the later the back-end compile happens, the more opportunities for optimizations actually open up (including such things as utilizing specific instruction sets for given architectures and fine tuning the compile based on run time statistics).
including such things as utilizing specific instruction sets for given architectures and fine tuning the compile based on run time statistics
1. That's a nice theory but in practice JIT implementations of interpreters are not actually anywhere near as fast as compilers for real world workloads.
2. When performance is critical (or even if you only THINK it's critical, see "Gentoo Linux"), compilers can use the same techniques, and still take advantage of the better regional and global optimizations they can do
If Java ( or Pyhton etc. for that matter ) were fast enough why did Google choose C++ to build their insanely fast search engine.
Because their developers knew it better? Because it had better 64-bit support when they started it? Because full GC's weren't compatible with their use case and IBM's parallel GC VM hadn't been released yet? Because they could get and modify all the source to all the libraries?
I don't know the answer, but there are a lot of possibilities besides speed. You're jumping to an awfully big conclusion there, Mr. Coward.
Only C++ can allow you to create applications as powerful as MapReduce which allows them to create fast searches.
Except that MapReduce is not an application, that it was originally codified in LISP, and that Google started using the technology because they bought AltaVista, where it was originally used for searching.
Except that AltaVista was bought by Overture [wikipedia.org] who were then bought by Yahoo!. Also, I wouldn't really call MapReduce a technology. The individual functions (Map and Reduce) come from functional programming, but the concept is becoming popular because Google's implementation and Hadoop have made it easy to write large scale data processing applications without having to worry about scaling or failures yourself. It also doesn't hurt that many problems can be solved with MapReduce.
The technology is not just mapreduce, it's how you manage multiple resources to leverage what is essentially brute force. Now, try to keep up, someone can buy the shell of a company after another buys the heart:
Well someone should tell that to the people working on Hadoop. I'm sure they'd love to know that their java mapreduce based framework is impossible. Maybe they'll even be able to use the paradox to built a perpetual motion machine and power the world.
Actually, the two are paired: programming model and implementation. The reason there's a programming model is that functional methods allow Google's implementation to automatically parallelize the input data for feeding to the cluster. So the implementation is very important, because that's actually how the data is processed and returned.
In that sense, Oracle's clustering optimizations are also a paired programming model and implementation, since, presumably, you need to know Oracle's SQL language exte
Yeah, that's why I speculated that SQL might be done so easily-- Oracle really is a rabbit hole. I've done some relational algebra in a database course (and also was exposed to set theory in my discrete maths course), but it was unclear to me whether query optimizers actually broke a query down into relational algebra or not. In fact, I remember that despite having had prior experience with SQL, relational algebra was much easier for me to wrap my head around than SQL. My professor was hesitant to go too
Um, first question: WTF is MapReduce? (Score:5, Funny)
and can I run Linux on it? Or it on Linux? Is it available for my iPhone?
Re:Um, first question: WTF is MapReduce? (Score:5, Funny)
MapReduce is the algorithm used to determine the optimum folding pattern used to reduce a standard road map back into its folded state. Duh.
Parent
Re: (Score:2, Funny)
Why can't they just look at the creases? Duuuuuuh.
Re:Um, first question: WTF is MapReduce? (Score:5, Funny)
Parent
Re: (Score:2)
That problem has already been solved by a collaboration of millions of computers! Haven't you ever heard of Folding@Home?
"Ok, what about accordion-style from the leftmost edge, with a vertical fold at the beginning!?
Re:Um, first question: WTF is MapReduce? (Score:5, Informative)
Good question. I had to look it up [wikipedia.org]. (Would it have killed the submitter or editor to include a link?)
Basically, the software gets its name from the list processing functions "map" (to take every item in a list and transform it, thus producing a list of the same size) and "reduce" (to perform an operation on a list that produces a single value or smaller list). The actual software has nothing to do with "map" and "reduce", but it does to tokenization and processing on massive amounts of data.
Presumably the Map/Reduce part comes from first normalizing the items being processed (a map operation) then reducing them down to a folded data structure (reduce), thus creating indexes of data suitable for fast searching.
Parent
Re:Um, first question: WTF is MapReduce? (Score:5, Informative)
Here is the connection between map and reduce.
In programming
map takes a function from A to B, a list of A's and produces a list of B's
reduce are associative fold functions. They take a list of B's and an initial value and produce a single C.
Like say for example MAP a collection of social security numbers to ages and then select (REDUCE TO) the maximum age from the collection.
Now there are results called "fusions" which allow you make computational reductions for example:
foldr f a . map g = foldr (f.g) a
So in other words the data set is being treated like a large array using array manipulation commands.
Parent
Re: (Score:3, Informative)
Google's mapreduce framework has a native resource manager that's aware of what resources are available, aware of failures, and is prepared to reschedule failed processes and where (and when?) to direct finished tasks. Basically it's a job que for distributed processing using a private network. MapReduce is just one tool. You aren't going to get much out of it after you max out your local machine's processing until you start work on the rest of it. What's really scary is that MySQL announces that they final
Re: (Score:2)
Got a link for the mysql thing you mentioned?
Re:Um, first question: WTF is MapReduce? (Score:5, Funny)
I'm a little dyslexic. I immediately see the wheelbarrow as a MySQL icon (which is almost universally a MySQL article) and read _M_apReduce into SQL = MYSQL in the title. This is proof I'm a reactionary blowhard who often fails to comprehend the summary, much less read the article.
There is no link because my wrongometer is not working, it has melted through its resin casing.
Parent
Re: (Score:2)
Basically, the software gets its name from the list processing functions "map" (to take every item in a list and transform it, thus producing a list of the same size) and "reduce" (to perform an operation on a list that produces a single value or smaller list).
As does my Slashdot user name. Great, now everything is going to think I'm calling on people to "filter" this software somehow, which I'd never heard of before this story. And it's "highly controversial", that's helpful.
Re:Um, first question: WTF is MapReduce? (Score:5, Informative)
Map-Reduce is definitely a technique related to grid computing, but they are not one and the same.
The most popular (to my knowledge) open source Java library implementing MR is Hadoop [apache.org].
Here's the algorithm in a nutshell (anyone who knows more than me, please correct, and I'll be forever grateful). I have a bunch of documents and I want to generate a list of word counts. So I begin with the first document and map each word in the document to the value 1. I return each mapping as I do it, and it is merge-sorted by key into a map. Let's say I start with a document of a single sentence: John likes Sue, but Sue doesn't like John. At the end of the map phase, I have compiled the following map, sorted by key:
Now begins the reduce phase. Since the map is sorted by key, all the reduce phase does is iterate through the keys and add up the associated values until a new key is encountered. The result is:
Simple. Stupid. What's the point? The point is that the way this algorithm divides up the work happens to be extremely convenient for parallel processing. So, the map phase of a single document can be split up and farmed out to different nodes in the grid for processing, which can be processed separately from the reduce phase. The merge-sort can even be done at a different processing node as mappings are returned. Redundancy can be achieved if the same document chunk is farmed out to several nodes for simultaneous processing, and the first one that returns the result is used, the others simply ignored or canceled (maybe they're queued up at redundant nodes that were busy, so canceling means simply removing from the queue with very few cycles wasted). Similarly, because the resulting map is sorted by key, an extremely large map can easily be split and sent to several processing nodes in parallel. The original task of counting words across a set of documents can be decomposed to an ridiculous extent for parallelization.
Of course, this doesn't make much sense to actually do this unless you have a very large number of documents. Or, let's say you have a lot of computing resources, but each resource on its own is very limited in terms of processing power. Or both.
This is very close to the problem a company like Google has to solve when indexing the web. The number of documents is huge (every web page), and they don't have any super computers—just a whole ton of cheap, old CPUs in racks.
At the end of the day, Map-Reduce is only useful for tasks that can be decomposed, though. If you have a problem with separate phases, where the input of each phase is determined by the output of the previous phase, then they must be executed serially and Map-Reduce can't help you. If you consider the word-counting example I posted above, it's easy to see that the result required depends upon state that is inherent in the initial conditions (the documents)—it doesn't matter how you divide up a document or if you jumble up the words, the count associated with each word doesn't change, so the result you're after doesn't depend on the context surrounding those words. On the other hand, if you're interested in counting the number of sentences in those documents, you might have a much more difficult problem. (You might think you could just chunk the documents up at the sentence level, but whether or not something is a sentence depends upon surrounding context—a machine can easily mistake an abbreviation like Mr. for the end of a sentence, especially if that Mr. is followed by a capital letter which could indicate the beginning of a new sentence...which it almost always is. Actually...if you're smart you can probably come up with a very compelling argument that this
Parent
Re:Um, first question: WTF is MapReduce? (Score:4, Informative)
This classic word count example by Google is exactly what Aster demonstrated in their webinar via a live demo of their In-database MapReduce software:
http://www.asterdata.com/product/webcast_mapreduce.html
Parent
Re: (Score:2)
I'm not quite entirely sure what you mean by the verb "map", the noun "map", and in which sense you use it in each instance. Also, I'm unsure why you think sorting enters into it.
My understanding of MapReduce is that it's (surprise!) all about applying the higher-order functions map and then reduce. Here's what they do:
Map takes a function f and a list [x_1, ..., x_n], then returns [f(x_1), ..., f(x_n)]. That is, it applies f to all the elements of the list. [variants takes multi-argument functions and
Re: (Score:2)
I only have a passing familiarity with Map-Reduce, so I'm definitely not an authoritative source. It's definitely possible that sorting isn't part of the algorithm itself, but rather one example of context around how it's often implemented. It definitely makes sense, though—why not merge-sort the results as mappings are returned? If you do implement it this way, it just makes it possible to deal with really large maps that need to be spread over multiple nodes.
Re:Um, first question: WTF is MapReduce? (Score:4, Funny)
and can I run Linux on it? Or it on Linux?
Have you ever considered that it might itself be a distro? A, like, super-leet distro that the big Valley firms have been hacking together for the past ten years, only giving access to employees that sign a super-nasty NDA? A disto that traces back to a Photoshop 1.0 plugin for resizing GIFs?
Parent
Re: (Score:2)
MapReduce is just an idiom (pattern if you will) for processing collections (arrays, lists, trees, database tables...) of data. There is often another piece :filter that cuts out bits you don't want to do but that can easily be done in the reduce step, though sometimes it is done somewhere else.
For example, suppose you want to compute exp(x) using the usual Taylor series expansion and 20 terms. Start with the list [0,1,2,3,4,5, .. 19]. Then map the function :
f(i) = x^i / i!
to each entry in the li
Re: (Score:3, Insightful)
Probably someone who read the post and knows how wrong he is. Like you traverse the web every time you want to look up a search term or how a map is really the same as load balancing...
Mmm.. MapReduce is LISP (Score:2, Insightful)
People who don't know LISP are bound to reinvent it, badly.
Re:Mmm.. MapReduce is LISP (Score:5, Funny)
Well done, AC. You've exposed their dirty little Scheme.
Parent
Perhaps a good addition to data warehousing (Score:5, Interesting)
Data warehousing (here I mean databases stored in column order for faster queries, etc.) may get a lift from using map reduce over server clusters. This would get away from using relational databases for massive data stores for problems where you need to sweep through a lot of data, collecting specific results.
I think that it is interesting, useful, and cool that Yahoo is supporting the open source Nutch system, that implements map reduce APIs for a few languages - makes it easier to experiment with map reduce on a budget.
Re: (Score:3, Interesting)
Except that relational databases are not just indexed objects copied across a large network of cheap PCs. What's good for Google may not be suitable for other databases, who actually care about ACID properties of transactions and not necessarily have the infrastructure to run highly parallel select queries.
Re: (Score:2)
I'm currently working on a project where users will be able to apply different types of transformation and collection to timestamped data and map/filter/reduce style algorithms are perfect ways to give them that capability.
The kind of capability might look something like : give me the average temperature at hourly intervals for each day in the year for a dataset that spans multiple years. In this case there's no map, and the reduce does the work, in other cases this may be turned around.
The data invol
Re:Perhaps a good addition to data warehousing (Score:5, Informative)
Actually, MapReduce doesn't do anything in the way data's stored- it's just a pipe between two sets of stored data, and really just needs an interface on both ends to get the task into MapReduce (which is what it seems the projects TFS/A mention do). BigTable is the storage mechanism that's incompatible with most traditional row-based RDBMSs. GFS is just the underlying storage mechanism.
http://labs.google.com/papers/gfs.html [google.com]
http://labs.google.com/papers/bigtable.html [google.com]
http://labs.google.com/papers/mapreduce-osdi04.pdf [google.com]
Note that all of those were published several years ago- I'd bet dollars to donuts that Google is _WAY_ beyond this internally if it's just reaching commercial use by their competitors.
Parent
Re:Perhaps a good addition to data warehousing (Score:5, Informative)
http://research.google.com/archive/sawzall.html [google.com]
Sawzall is essentially designed around the mapreduce framework. It's impossible to *not* write a mapreduction in Sawzall. The way it works:
Your program is written to process a single record. The magic part happens when you output: you have to output to special tables. Each of these table types has a different way that it combines data emitted to it.
So, during the map phase, your program is run in parallel on each input record. During the reduce phase, the reduction happens according to the way the output tables do whatever operation was specified.
There was some work to be done having enough different output tables to do everything that was useful, especially since you might want to take the output and plug it in as the input to another phase of mapreduction.
One of the biggest reasons this was a major innovation for Google was that it let some of the people who weren't really programmers still come up with useful programs, because the Sawzall language was pretty simple (especially when combined with some of the library functions that had been implemented to do common sorts of computations.) There were also some interesting ways in which the security model was implemented, but as far as I know they haven't been published yet.
There certainly are plenty of other technical things that can be done to improve a system like MapReduce (and I know that many of them were in various forms of experimentation when I left the company) but at least some of them are highly dependent on Google's infrastructure, and not really relevant to a general discussion. (I suspect that the papers linked above might have some hints, but it has been a while since I looked at them.)
Parent
Re: (Score:2)
Correct. I sometimes wonder how many /. readers are really developers? Mapreduce is old, old technology, Google just made it famous and, maybe, documented. It is not always useful in all cases but never worse than any other method in throughput. If you have to "map" information and the more they are unbalanced, the better it gets.
Actually the question about developers came because a lot of replies are talking about API - if you code, write your own, it is very easy once you understand the principle. And I c
Re:Perhaps a good addition to data warehousing (Score:5, Informative)
The correct project name is Hadoop [apache.org]. It was factored out of Nutch 2.5 years ago. And Yahoo has been putting a lot of effort to make it scale up. We run 15,000 nodes with Hadoop in clusters of up to 2,000 nodes each and soon that will be 3,000 nodes. I used 900 nodes to win Jim Gray's terabyte sort benchmark [yahoo.com] by sorting 1 TB of data (100 billion 100 byte records) in 3.5 minutes. It is also used to generate Yahoo's Web Map [yahoo.com], which has 1 trillion edges in it.
Parent
Re: (Score:2)
Cool!! And thanks for the correction.
Re: (Score:2)
The correct project name is Hadoop. It was factored out of Nutch 2.5 years ago
SPEAK
ENGLISH
First they attack it (Score:4, Interesting)
http://www.databasecolumn.com/2008/01/mapreduce-a-major-step-back.html [databasecolumn.com]
then they embrace it
Re: (Score:2)
Mahatma Gandhi actually said, "First they ignore you, then they ridicule you, then they fight you, then you win."
The tool custodians of the massively complex relational database warehouse tools are seeing their world turn obsolete as the lighter weight MySQL and the more flexible mapreduce and the BASE [neu.edu] worlds evolve beyond them, so yes, they are going to kick up a fight. Don't let the screen door hit you in butt on the way out, guys.
Re:First they attack it (Score:4, Interesting)
From a comment made about the article:
You [the articles authors] seem to be under the impression that MapReduce is a database. It's merely a mechanism for using lots of machines to process very large data sets. You seem to be arguing that MapReduce would be better (for some value of better) if it were a data warehouse product along the lines of TeraData. Unfortunately the resulting tool would be less effective as a general purpose mechanism for processing very large data sets.
Parent
wrong argument? (Score:2, Insightful)
Though this post is my introduction to both MapReduce and the argument, it strikes me that the people arguing are arguing the wrong problem.
While MapReduce might be used against some structured data, it looks to be something for unstructured data and dynamically inventing structures in unstructured data. Additionally, you might want to keep that new structure around for a while. You might want to load it up with terabytes of data. At the same time, this data is less and less useful over time.
Think about
just add Protocol Buffers (Score:2)
Anyone remember this story: http://tech.slashdot.org/tech/08/07/08/201245.shtml [slashdot.org]? According to Google:
Protocol buffers are now Google's lingua franca for data -- at time of writing, there are 48,162 different message types defined in the Google code tree across 12,183 .proto files. They're used both in RPC systems and for persistent storage of data in a variety of storage systems.
(See http://code.google.com/apis/protocolbuffers/docs/overview.html [google.com].)
If you think about it, Protocol Buffers are just about perfect for MapReduce applications. First, Protocol Buffers data streams are "flat" structures, very similar to database tables. If you need hierarchical data, I think that you'd tend to use multiple tables that incorporate foreign keys, rather than embedding the hierarchy every time
Re: (Score:2)
I suspect that this, rather than SQL compatibility, is the road to success with MapReduce processes.
Why not both? :-)
A lot of distributed databases already implicitly support functionality that's equivalent to mapreduce, especially greenplumb and netezza.
ie: map operation is just:
create table output as
select [cols] from [table] where [condition] distribute on (key1,key2,key3);
Which will scan the table stored on all nodes, and deposit the data across all the nodes in netezza distributed on key1,key2,key3---i
1970's style hype meets 2000's style hype (Score:2)
Stonebraker isn't exactly the one to complain about this: just as MapReduce is being overhyped these days, relational databases were being overhyped in the 1970's, and he rode that wave all the way to fame and fortune. 30 years later, although every database system in the world calls itself "relational", very few database applications actually are relational.
MapReduce is indeed a simple, decades-old parallel programming technique. It's not the be-all-and-end-all of parallel programming, but it's good for s
Re:MySQL has no common sense anyway. . . (Score:5, Funny)
Not like MySQL cared about data integrity in the past. . . whay start now?!
Gaaah! Data corruption!
Your post must have been stored in MySQL...
Parent
Re: (Score:2)
As a matter of fact, it was... :/
Got what right? (Score:4, Interesting)
I don't think you can credit Bjarne with "compiled code is faster than interpreted code" (or the 21st century version: "compilers can perform better optimizations that JIT translators").
C++ happens to be the most popular fully compiled language, having edged Fortran out of that position some time near the end of the last century.
Back in the early '80s, when he was coming up with C++, the big Fortran savants were saying stuff like "Fortran is bigger than ever. There are more than X million Fortran programmers. Everywhere I look there has been an uprising... a lot of teaching was going to Pascal, but more are teaching Fortran again. There has been a backlash."
----
And that's not the only thing C++ has in common with Fortran, either.
Parent
Re: (Score:3, Interesting)
" (or the 21st century version: "compilers can perform better optimizations that JIT translators").
Actually, JITters can do some optimizations that compilers can't--by splitting the compilation into a frontend and a backend. The front end is essentially just a parser, and the later the back-end compile happens, the more opportunities for optimizations actually open up (including such things as utilizing specific instruction sets for given architectures and fine tuning the compile based on run time statistics).
.NET for that matter--but we're anti-MS
See the LLVM for more info: http://llvm.org/ [llvm.org]
(or
Re: (Score:2)
including such things as utilizing specific instruction sets for given architectures and fine tuning the compile based on run time statistics
1. That's a nice theory but in practice JIT implementations of interpreters are not actually anywhere near as fast as compilers for real world workloads.
2. When performance is critical (or even if you only THINK it's critical, see "Gentoo Linux"), compilers can use the same techniques, and still take advantage of the better regional and global optimizations they can do
Re:Again Bjarne got it right (Score:5, Interesting)
If Java ( or Pyhton etc. for that matter ) were fast enough why did Google choose C++ to build their insanely fast search engine.
Because their developers knew it better? Because it had better 64-bit support when they started it? Because full GC's weren't compatible with their use case and IBM's parallel GC VM hadn't been released yet? Because they could get and modify all the source to all the libraries?
I don't know the answer, but there are a lot of possibilities besides speed. You're jumping to an awfully big conclusion there, Mr. Coward.
Parent
Re: (Score:2)
Except that MapReduce is not an application, that it was originally codified in LISP, and that Google started using the technology because they bought AltaVista, where it was originally used for searching.
An AC getting it all wrong? Unpossible.
Re: (Score:2)
Except that AltaVista was bought by Overture [wikipedia.org] who were then bought by Yahoo!. Also, I wouldn't really call MapReduce a technology. The individual functions (Map and Reduce) come from functional programming, but the concept is becoming popular because Google's implementation and Hadoop have made it easy to write large scale data processing applications without having to worry about scaling or failures yourself. It also doesn't hurt that many problems can be solved with MapReduce.
A five digit user getting it a
Re: (Score:2)
The technology is not just mapreduce, it's how you manage multiple resources to leverage what is essentially brute force. Now, try to keep up, someone can buy the shell of a company after another buys the heart:
http://arnoldit.com/wordpress/2008/01/18/map-reduce-the-great-database-controversy/ [arnoldit.com]
Hey look, we're both guilty of not being perfect. Thanks for the vote of confidence though!
Re:Again Bjarne got it right (Score:4, Informative)
Well someone should tell that to the people working on Hadoop. I'm sure they'd love to know that their java mapreduce based framework is impossible. Maybe they'll even be able to use the paradox to built a perpetual motion machine and power the world.
See: http://developers.slashdot.org/comments.pl?sid=900359&cid=24756761 [slashdot.org]
Parent
Re: (Score:3, Insightful)
To most people, C++ is C. :-) Unfortunate but true.
Re: (Score:2)
Re: (Score:3, Informative)
In that sense, Oracle's clustering optimizations are also a paired programming model and implementation, since, presumably, you need to know Oracle's SQL language exte
Re: (Score:2)