---
# System prepended metadata

title: MapReduce

---

# MapReduce
contributed by `ilkclord`
## Background
In the past years , Google has to deal with many computation with a large scale of raw data , like crawled documents, web request logs, etc .The raw data are usually distibuted in diffrent machines ,so the computation needs to be done in a distributed system .MapReduce is the method for this problem .MapReduce aims to solve the issue like how to parallelize the computation, distribute the data, and handle failures . MapReduce will formed a libarary which solve all this issues . 
## Introduction
MapReduce is a method that execute a task by partition the task to many parts , and assign it to other machines to complete it .There are two steps in this method .The first step is **Map** , which distribute the samller task out ,and the machines execute the task .After all the task are done,we can do the last step ,**Reduce** , which merge the mutiple results into one results .
## Model
In the map_reduce mdoel , there exists a master machine , which handle the all the task  , and there are mutiple node machine which does the task , either **Map** or **Reduce** .The Mapreduce model has some features .

### Pure Funtion
Since MapReduce is used in computing in distributed system , there may occurred side effects . Some of them are unexpected and dangerous .The simple way to avoid the side effect is to make the funtion pure . So the function has expected to be a pure one in MapReduce libarary .
* **Map**
    The Map funtion that process the input data , the input data can be read by the file or in other way like reading in database and reading from virtual memory .
* **Combine**
    The Combine funtion merge all the results , in a key / value pair .The result will be stored in an intermediate file and send to the Reduce task
* **Reduce**
    The Reduce function has the similar purpose as Combine ,the only diffrence between them is that the Reduce stores the result into the final result in the Master machine .
### Input / Output type
Since the Map fuction must be a pure function  , the input and ouput type must be a key / value pair , so as the Reduce function .
### Result
One important feactures of results is that it has to be sorted . The sorted result helps the merge proces faster and it will be less complicate to serch for a specific data . 
During the Map_reduce process , there will be lots of result being generate , but the only one that matter is the Master result .All the results will finally merge into the copies in the Master.
### Master machine
A master machine has to handle all the state of the task and the id of each node machine . When the failure occured , Master machine has to handle it , and there are some way to recover from failure .
* **Worker failure**
    To deal with worker failure ,we reset the worker into idle state and reexecute it
* **Master failure**
    For more than one master machine program, we set a checkpoint and check it in period of time , when failure occured ,we set the state back to the checkpoint . For one Master machine program , we could only reexecute the program .
* **Straggler**
    When we are reaching the end of compute , if there are in-progressed task , we call another back up execution and wheither the primary one or back up one are done , we mark the task completed.
### Locality
In the partition of the task , we should also consider the locality ( for cloud computing ) , since the transfer of the data cost the network resources .The node machine will done the task which the partial task has the data stores on it .
### Skipping Bad Record
There may have some bugs in the program , and some of them are caused by third party issue .We provide a optional mode to make fprward progress . The implement of MapReduce provides a signal for master machine to detect the failure cause by specific record . When finished a task , the node machine returns a signal that shows the number of failure during execution , if more than one failure occured on the record , the record is marked . And the record will be skipped during the next re-execution. 
### Status
The master must handle a status page of computation state , which indicates how many workers are in-progressed and completed .It is useful , since the master can decide whether using more resource for the program or not by the status page . In addition , the top-level status page can also shows which worker has failed , and which task they are holding . It is useful to diagnose the bug .
## Work Flow
```graphviz
DIgraph G{
node[shape = box]
Master -> node1_Map->node1_Combine->node12_Result
Master -> node2_Map->node2_Combine->node12_Result
Master -> node4_Map->node3_Combine->node34_Result
Master -> node3_Map->node4_Combine->node34_Result
node34_Result->node1234_Reduce
node12_Result->node1234_Reduce->Master_Result
rankdir = LR
}
```
## Usage
Here are some problem that can be solved by using MapReduce method .
### **Distributed Grep**
### **Distributed Sort**
### Inverted Index
### Word Count
To count the word in a document , we can read the file character by character , and count it when it forms a word .Keep doing the process , we can get the word-count pages of the document.But we can do this process faster ! Since the number of word can represent as a the form of ( word , count ) , MapReduce method is suitable for this problem .

