## 3 MapReduce: Principles of Distributed Programming over Large-Scale Data Repositories  
MapReduce is both a programming model for expressing distributed computations on massive amounts of data and an execution framework for large-scale data processing on clusters of commodity servers [1; 34]. MapReduce's programming model was released to the computer science community in 2004, being described in [1] after Google was already using this technology for a couple of years. MapReduce's processing scheme soon became very popular, including a broad adoption due to its open-source implementation. A job from MapReduce programming model splits the input data set into several independent blocks that are processed in parallel. There are two seminal ideas that are encountered in MapReduce, which we report in the following. * There is a previous well-known strategy in computer science for solving problems: _divide-et-impera_. According to this paradigm, when we have to solve a problem whose general solution is unknown, then the problem is decomposed in _smaller sub-problems_, the same strategy is applied for it, and the results/partial solutions corresponding to each sub-problem into a general solution are combined. The decomposing process continues until the size of the sub-problem is small enough to be handled individually. * The basic data structures are _key-value pairs_ and _lists_. The design of MapReduce algorithms involves usage of _key-value_ pairs over arbitrary data sets. _Map_ and _Reduce_ concepts were inspired from _functional programming_. _Lisp_, in particular, introduces two functions with similar meaning, _map_ and _fold_. Functional operations have the property of preserving data structures such that the original data remains unmodified and new data structures are created. The _map_ function takes as arguments a function \(f\) and a list, and it applies the function \(f\) to each element of the input list, resulting in a new output list. The _fold_ function has an extra argument compared to the _map_: beyond the function \(f\) and the input list, there is an accumulator. The function  
Figure 1: Hadoop cluster architecture. is applied to each element of the input list, the result is added to previous accumulator, thus obtaining the accumulator value for the next step. Although the idea seems to be very simple, implementation details of a _divide-and-conquer_ approach are not. There are several aspects with which practitioners must deal. Some are the following ones:  
* decomposition of the problem and allocation of sub-problems to workers;
* synchronization among workers;
* communication of the partial results and their merge for computing local solutions;
* management of software/hardware failures;
* management of workers' failures. The MapReduce framework hides the peculiarities of these details, thus allowing developers to concentrate on the main aspects for implementation of target algorithms. Technically-wise, for each job, the programmer has to work with the following functions: _mapper_, _reducer_, _partitioner_ and _combiner_. The _mapper_ and _reducer_ have the following signatures:  
\[Map:(k_{1},v_{1}) \rightarrow[(k_{2},v_{2})]\] \[Reduce:(k_{2},[v_{2}]) \rightarrow[(k_{3},v_{3})]\]  
where \([\dots]\) denotes a list. The input of a MapReduce's job is fetched from the data stored in the target distributed file system. For each task of type _map_, a _mapper_ is created. This is a method which, applied to each input _key-value_ pair, returns a number of intermediary _key-value_ pairs. The _reducer_ is another method applied to a list of values associated with the same intermediary key in order to obtain a list of _key-value_ pairs. Transparently to the programmer, the framework implicitly groups the values associated with intermediary keys between the mapper and the reducer. The intermediary data reach the _reducer_ ordered by key, and there is no guarantee regarding the key order among different reducers. The _key-value_ pairs from each _reducer_ are stored in the distributed file system.