What kind of problems does MapReduce solve?

Question

I have been reading about MapReduce for a while -- but what I can't understand is how someone would make a decision to use (or not use) MapReduce.

I mean, what are the problem patterns that signal that MapReduce could be used.

Answer 1

It's basically problems that are huge, but not hard. Travelling salesman depends crucially on the distance between any given pair of cities, so while it can be broken down into many parts, the partial results cannot be recombined so that the globally optimal solution emerges (well, probably not; if you know a way, please apply for your Fields medal now).

On the other hand, counting frequencies of words in a gigantic corpus is trivially partitionable, and trivially recombinable (you just add up the vectors computed for the segments of the corpus), so map-reduce is the obvious solution.

In practice, more problems tend to be easily recombinable than not, so the decision whether to parallelize a task or not has more to do with how huge the task is, and less with how hard it is.

Answer 2

Can the problem be solved efficiently using distributed computing?

If the answer to this question is yes, then you have a candidate problem for MapReduce. That is because the problem pattern lends itself to being split into smaller isolated problems.

Your task: Parse this book

An example works well to ilustrate this. You have a large document (Moby Dick by Herman Melville) and your job is to perform a frequency analysis of all the words used in it.

The sequential approach

You can do this sequentially by getting your fastest machine (you've got plenty lying around) and running over the text from start to finish maintaining a hash map of every word you find (the key) and incrementing the frequency (value) every time you parse a word. Simple, straightforward and slow.

The MapReduce approach

Approaching this from a different perspective, you note that you have all these spare machines lying around and you could split this task up into chunks. Give each machine a 1Mb block of text to parse into a hash map and then collate all the hash maps from each into a single result. This is a layered MapReduce solution.

The process of reading a line of text and gathering the words is the Map phase (you create a simple map representing the words in the line with their frequency 1,2,3 etc), then the Reduce phase is when each machine collates their line maps into a single aggregate map.

The overall solution comes from a further Reduce phase where all the aggregate maps are aggregated (that word again) into a final map. Slightly more complex, massively parallel and quick.

Summary

So, to summarise, if your problem lends itself to being represented by keys, values, aggregate operations on those values in isolation then you have a candidate problem for MapReduce.

Answer 3

The MapReduce pattern is taken from the world of functional programming. It is a process for applying something called a catamorphism over a data-structure in parallel. Functional programmers use catamorphisms for pretty much every simple transformation or summarization.

Assuming your data is a tree, the deciding factor is whether you can compute a value for a node using only the data contained in that node and the computed values for its children.

For example you can compute the size of a tree using a catamorphism; you would compute the sum of the computed values for all children plus one.

Answer 4

This WPI - Applications of Map Reduce (ppt) may be of interest to you. It discusses different applications of MR, and as one of the discussed cases, it shows how Using 100 EC2 instances and 24 hours, the New York Times was able to convert 4TB of scanned articles to 1.5TB of PDF documents.

Another set of examples where MR helped in speeding performance is at: Aster - SQL Map Reduce shows some case studies of SQL-Map Reduce technology including Fraud Detection, Transformations, and others.

Answer 5

Map/Reduce is a specific form of a specific kind of algorithm. You use it to transform one huge data set into another data set. (The result dataset may or may not be huge.) If you don't want a static data output set as a result of static data input, then Map/Reduce is not appropriate. Map/Reduce can easily tell you how many John Smiths are in the Manhattan phone book, but it is not well suited to build a web server.

The way Map/Reduce works is:

• Map takes pairs of keys (k1) and values (v1) and maps them into a new set of keys (k2) and values (v2).
• Reduce takes all the v2 values with the same k2 key and produces a new value (v3).

The result is that a list of (k1, v1) pairs is transformed into a list of (v3)s. (Of course, the value "v3" can be a composite that includes k2, which could be defined to be equal to k1.)

So you use it:

1. If you have so much data to start with that running it all sequentially through one or two servers would take too long, and

2. You can conceive of the output data of being a list of values or key value pairs (generally not too hard when you remember "key" only means "unique label"), and

3. Whatever the relationship, you are sure that each piece of input data only impacts the output value for one output key.

If your data can all be processed sequentially by a single server, then since that is the dominant computing paradigm (the ones servers are built for and programmers are trained on), use a single server.

The map stage has to partition all the input data by output key. It doesn't have to produce the output value associated with the output key (that's done by the reduce stage), but it does have to uniquely assign each input key value pair to contribute to at most one output key's value. If the data is too interrelated then map reduce might not be able to handle the problem. On the other hand, it may just be that you need to use multiple rounds of map/reduce.

If you can't figure out how to turn your data transformation into a map/reduce, then of course it's not a solution.

There is a real art to figuring out if a problem can be decomposed into something Map/Reduce can handle. For example v1 and v2 might not be in the input or output data sets at all. If you just want to count unique items in the input data, then k1 = k2 = an item and v1 = v2 = 1 or 0 or really anything. Reduce just produces v3 as the sum of the number of k2's it was given.

So it's hard to say for sure that a data transformation cannot be done using Map/Reduce, but the above gives you some guideposts.

Answer 6

MapReduce works on any problem that is made up of exactly 2 functions at some level of abstraction. The first function is is applied to each of the items in the input set, and the second function aggregates the results.

So, any time you want to get (1) result from (n) inputs, and all inputs can be examined/used by (1) function, you can use MapReduce. Again, this is at some specific level of abstraction. The (1) function may be some grouping function that checks the input and decides which of several other functions to use.

This is useful when you don't know in advance how much input you will have, when you need to share out discreet "units" of work, or when you want a single return to represent the entire result (I.E. running five thousand unit tests, and if less than x% fail, return success).

Answer 7

Most of the answers here seem to be some variation of explaining what map reduce does, which is valid. But to answer the question, which was which pattern would signal where you might be able to use map reduce is not really addressed by that.

If the naive, non functional, implementation of the problem you are looking at involves looping over something and then updating something outside the loop with some state from inside the loop, chances are you have something that ports well to map reduce. Especially if you can generalize the updating of the central state to a function that works with just two parameters and can guarantee this function is commutative and associative.

The reason you would might want to use map reduce if that is true is two fold: 1) it might be a bit cleaner and easier to test and debug if you break things into map and reduce functions. 2) map reduce functions are stateless and may be run concurrently, which speeds things up if you have multiple cpus available and something like hadoop or spark that makes use of that to run things in a cluster.

This is nice if you are looping over a lot of stuff but your mileage may vary depending on how complex your map/reduces are. It's quite common to end up with a sequential chain or tree of map reductions where in the end everything is still bottlenecked on some complex reduction step at the end of the chain. For example many graph algorithms are difficult to scale efficiently with just map reduce.

The simplest example that works well with map reduce, is counting stuff, which is a very cheap reduction. This is why word count is an often used example for map reduce. You can pretty much expect linear scalability for performance with that usecase: every cpu you add makes it faster.

Answer 8

Is it parallelisable?

Any parallelisable problem is essentially map and fold; conversely, the map step is inherently parallelisable (and the fold step might be, depending on the structure over which it's folding), so this is a bidirectional property.

Answer 9

If you do much functional programming, you start running into situations that call for a general map and reduce. You probably even see them in imperative programming, but don't recognize them behind the mask of loops and accumulators.

As an example of one that came up for me recently, I've been working on a parser in Haskell. To test my parser, I pump a list of string fragments through the parser, and then I want to get a single string that I can output of my results to see if it parsed right. So that looks like:

--my initial set of test data, a list
tests = ["string1", "string2", "string3", ...]

--Map Step: turn strings into parsed results
--note the type, which demonstrates the map
applyParser :: [String] -> [Token]
--The actual function
applyParser input = map parser input

--Second map, turn tokens into output
showTokens :: [Token] -> [String]
showTokens t = map show t

--Reduce step, concat the results
combineResults :: [String] -> String
--In haskell, reduce is the foldl function, which takes an operation to fold with, a starting element, and a list to fold on
combineResults strings = foldl concat "" strings

--Finished program
testParser = print (combineResults(showTokens(applyParser tests)))

Of course, this is just pedagogical. My actual code looks a bit different, and uses more internal functions (like fold concat isn't needed since Haskell already includes unlines that does [String]->String). My main point was that I didn't anticipate using a map/reduce when I started, it just aligned to my needs. I wanted to do some stuff with lists, then turn my list into a single element of output. The use of map/reduce emerged naturally.

String processing (like parsing) is one very obvious use of map reduction, mapping is the application of various transformations on the input text, and reduce it putting the result text back together again as output. Likewise, a compiler could be similar, using folds to turn a stream of Abstract Syntax Tree elements into a better form (optimizing).

Answer 10

Here's the major questions I use to probe a decision to use (or not use) MapReduce.

• Is achieving reasonable parallel execution performance with minimal programmer effort important for a given problem?
• Do I have a large number (hundreds) of parallel execution elements available?
• Is there excellent communication bandwidth/throughput among the parallel execution elements?
• Do I need to process a huge amount (TB) of data?

• Does the problem I am trying to solve decompose into Map and Reduce operation?

  • Map: Execute the same operation on all data.
  • Reduce: Execute the same operation on each group of data produced by Map.

Answer 11

Say you are searching a cluster of servers and one is unable to respond at that moment. What mapReduce will do is since it could not access that tree node to the larger Map is it will reschedule it for later and perform either the Map or the Reduce then. Essentially it tries to guarantee all information is available with the unpredictability of software and hardware in environments.

Answer 12

in effect, it's a generic "divide and conquer" pattern, so that solutions for distributing the computation can be written generically.

a simple example is like a large document. the problem is you want to count the number of letters in that document. instead of running on a single machine, you can break it down into an array of all words in the document. then you can process each word individually, and the results back together.

the pattern is useful, because once you get a generic map/reduce implementation working you can solve any problem using that same software layer, you just need to express your problem in terms of it.