But in fact, the terms and concepts of map & reduce exist in programming language community long before G company's successful paper "MapReduce: Simplified Data Processing on Large Clusters", which appeared in OSDI04.
In this article, I want to summarize what this term pair means in functional programming literature and parallel processing literature respectively.
I - Map/Reduce in Functional Programming Perspective
Functional Programming has long history in academia, but not been massively accepted in developer communities yet. It has some beautiful features, compared with our daily use imperative language. Higher Order Function is one of them. Basically, it means that function can be used as input parameters or return value for a function definition.
Among various higher order functions, map, fold and filter are the most popular ones:
- Map is a higher order function that applies a given function(a.k.a transformer) element-wise to a list of elements and returns a list of results. Transformer is a function applies to each element and will produce one or more new elements.
for example: map (toLower) "abcDEFG12!@#" will produces output:"abcdefg12!@#"
- Fold (a.k.a. Reduce, Accumulate) is a higher order function that processes (using a combiner function) a list of elements in some order and build up a return value. Combiner is a function that is applied to two elements and produces a result that can be combined using combiner with the remaining elements in the list.
for example: fold (+) 0 [1..5] will produces output: 15, which is the sum of all the elements.
- Filter is a higher-order function that processes a list of elements in some order to produce a result containing exactly those original elements for which a given predicate returns the Boolean value true. Predicate is a function that takes one element as input parameter and return either true or false.
for example: filter (isAlpha) "$#!+abcDEF657" will produces output: "abcDEF"
Essentially, these three higher order functions apply an operation on some list/array and produce some results: map transform each element, filter filtering some elements and reduce combine all the elements.
Pure functional language, such as haskell/lisp, and some mixed language, such as python, have build-in functions named exactly as Map/Reduce. C# 3.0 introduces some functional features in LINQ subsystem, where Map is called Select and Reduce is called Aggregate.
More concrete examples can be found in [2].
II - Map/Reduce in Parallel Processing Perspective
Map/Reduce is a Programming Model & also an Implementation Runtime. The programming model is what you can use to express your computation tasks while implementation runtime is those software components that realize what the model claims.
This model is called map/reduce, but their meanings are somewhat different:
- the map semantic is the same as in functional programming language: the transformer (the mapper in Google's paper) is applied to each element of the list
- the reduce semantic differs. Here, the combiner(the reducer in Google's paper) is applied to multiple sub sections of the elements in the list and thus produces multiple reduce results, but in functional programming language it is applied to all the elements and only produces one result.
Conceptually, how the elements are divided into multiple sub sections?
To resolve this problem, this model introduces some structure on the elements that are produced by mapper and consumed by reducer - each element/record has two parts: key and value. Then all the elements are divided according to the key. The records with the same key form a sub section and are passed to a reducer function as a whole.
From implementation's perspective, the most important advantage of this Programming Model is that - it enables automatic parallelization and distribution of large scale data processing:
- mapper is applied to each record, it's a data parallel problem by itself, we just need to distribute input data in record boundary among processing nodes.
- reducer is applied to some sub section, we just need to distribute those sub sections among process nodes.
Another implementation problem is fail over - what to do when failure happened?
Simple! It just re-execute the failed specific mapper/reducer, other mappers/reducers won't be bothered at all. Because there is no communication among mappers and reducers respectively, this solution is semantically correct for mapper/reducer.
Since the input of mapper is persisted in reliable storage system, failed mapper only need to re-execute that mapper. But the input of reducer (also the output of mapper) is persisted in worker's local storage system, re-executed reducer may found some input unavailable (for example intermediate data node crashed). In this situation, failed reducer need to re-execute both some mappers and that reducer.
1. Functional Programming
2. higher order functions - map, fold and filter
3. Map/Reduce/Filter in Python
4. Map/Reduce in PHP
5. Google's MapReduce Programming Model — Revisited
6. MapReduce: Simplified Data Processing on Large Clusters
7. Map-Reduce-Merge: Simplified Relational Data Processingon Large Clusters
