MapReduce is a computing model for processing big data with a parallel, distributed algorithm on a cluster.
It was invented by Google and largely used in the industry since 2004. Many applications are based on
MapReduce such as distributed pattern-based searching, distributed sorting, web index system, etc.
MapReduce is inspired by the
reduce functions, which commonly used in functional programming.
Reduce are not a new programming term, they are operators come from Lisp, which invented in 1956.
Let’s begin with these operators in a programming language, and then move on to
MapReduce in distributed computing.
Map and reduce in Python
A funny pic shows the meaning of them:
map in the functional programming applies another function to a list, convert each element to another value, then finally returns a new list. We can use map to any data structure of sequence type, such as an array.
Suppose we want to multiple 2 to each element in a List, this could be finished in Python:
def num2(lst): newList =  for x in lst: x = x * 2 newList.append(x) return newList
After run it with input, we will get another list:
lst = [1,2,3,4,5,6,7,8] print num2(lst) => [2, 4, 6, 8, 10, 12, 14, 16]
Python has a builtin function
map for this kind of task:
def num2(x): return x * 2 print map(num2, lst) => [2, 4, 6, 8, 10, 12, 14, 16]
reduce applies a function to every two elements of a list, but it returns an aggregate result. It’s called
fold in some programming languages.
def sum2(x, y): return x + y print reduce(sum2, lst, 0) => 36
We may implement it from scratch like this:
def reduce(function, sequence, initial=None): result = initial for x in sequence: result = function(result,x) return result
A programming model: MapReduce
Of course, the concept of
MapReduce is much more complicated than the above two functions, even they are sharing some same core ideas.
MapReduce is a programming model and also a framework for processing big data set in distributed servers, running the various tasks in parallel.
It is a technology which invented to solve big data problems. Nowadays, the data volume is so huge that we can not solve it on one server.
The whole idea of
MapReduce is a split-apply-combine strategy. We split the big data set into multiple parts and processing them parallelly on multiple servers, then combine the result with all outputs from servers.
Let’s make an analogy, we have a lot of ingredients, after the procedure of shredding and recombine, we make a lot of hamburgers.
Figure 2: https://reberhardt.com/cs110
MapReduce‘s users will implement the
reduce functions, and the framework will call them on a large cluster of machines.
In practice, except for
reduce, there are some other processing stages in the whole procedure, including Split, Combine, Shuffle, Sort, etc.
Suppose we want to count the numbers of each word from a big file, we split the file into 3 sub-files, then finish the word counting task in each server, then we use the words as keys for shuffling, and finally combine the results from the same key.
Figure 3: Source from dreamshutter.tistory.com
The framework will also support with redundancy and fault tolerance, since errors may happen on any server. In the original implementation of Google, they use the architecture of the master-worker pattern. The master node will assign jobs to workers and maintain their status.
The master pings every worker periodically. If no response is received from a worker in a certain amount of time, the master marks the worker as failed. Then reschedule the job for anther healthy worker.
Figure 4: Source from MapReduce 2004 paper: Simplified Data Processing on Large Clusters
In recent years, Google has moved on to some other technologies which offer streaming data operation instead of batch processing, but there is still much existing software such as Hadoop use the
MapReduce computing model.
The major contributions of
MapReduce are a simple and powerful interface that enables automatic parallelization and distribution of large-scale computations.
Split-apply-combine is a general strategy in the world of distributed computing,
MapReduce is a great example which confirms:
Technologies come and faded, but the principle tends to remain more constant.