###### tags: Distributed Systems
# MapReduce
## 概述
主要目標是解決如何去平行化資料處理與運算，運用 Map 將資料產生出一組 Key/Value Pair，然後 Reduce 將 Key 相同的 Pair 組合再一起，而為了要將資料平行運算，會有一個 Master 去分派 Map 或 Reduece 的工作給不同的 Worker。

## 系統架構
MapReduce 這樣的 model 可以在一般的電腦、 NUMA 架構的多核心系統
或者是電腦叢集，下面會用電腦叢集的模式來介紹 MapReduce 的架構設計
在 MapReduce 下會有一個 Master 去分配工作給 Worker 去負責 Map 或 Reduce。

### Master Data Structures
Master 須記錄以下資料
1. Task 狀態 (idle, in-progress, compeled)
2. Map 後的 intermediate 資料位置

### 執行流程
1. 將資料切分成 M 個，M 代表 Master 可分配的 Worker 數量去做 Map 的動作。
2. 做 Map 的 Worker 會將其結果存在 Local Disk 並將其位置傳給 Master。
3. Master 分配 Reduce 的工作給 Worker，並將資料位置的數量分成 R 個，R 代表做 Reduce 的 woker 數量，將資料位置給指定的 Worker。
4. Reduce 將做出來的結果輸出，R 有多少就有幾個輸出。

### Fault Tolerance
MapReduce 的框架用來可以透過切割資料與多台 Server 達到大量資料的處理，而多台 Server 使用就會有機會遇到 Server 掛掉的狀態，而如何要處理這樣的狀況就會是這樣框架下非常巨大的挑戰。
在 MapReduce 會遇到兩種狀況
1. **Worker Failure**
Master 會持續 ping Worker，當 Worker 超過一段時間沒有回應就會把這個 Worker 的狀態改成 idle，而 Map task 跟未完成的 reduce task 都會需要重新執行，因為其資料都是存在 Worker 的 local disk，在將這些需要重新執行的 Task 分配給其他 Worker。
2. **Master Failure**
在 MapReduce 的框架下，Master 是相當重要的，以下有幾個在 Paper 中提到如果 Master Failure 的處理方式
1. 在資料中新增檢查點，如果掛掉重啟就從檢查點開始
2. Worker 放棄目前的所有工作，等待 Master 重啟