7.1 概述

7.1.1 分布式并行編程

目前遇到的問題：1）摩爾定律開始失效，單個CPU的性能提升速度放緩；2）但需要處理的數(shù)據迅速增加
兩種解決的途徑：1）CPU由單核變?yōu)槎嗪耍?）分布式并行編程
MR之前：已有MPI等成熟的并行計算框架，但MPI有以下缺點：① 使用共享式集群，容錯性差、② 硬件價格高且擴展性差、③ 學習難度大。相對來說MR在上述問題上進行了改進。但是，在適用場景上，MPI可以用于實時、細顆粒度、計算密集型場景，而MR適用于離線非實時批處理。

7.1.2 MapReduce模型簡介

1）把過程高度抽象為Map和Reduce兩個函數(shù)
2）從而降低了學習難度，變成很容易
3）分而治之的策略：把數(shù)據分片，由多個Map任務并行處理
4）計算向數(shù)據靠攏的設計理念：數(shù)據分布存儲到多臺機器上，map任務被發(fā)送到數(shù)據所在機器或盡可能臨近的機器，避免了數(shù)據傳輸?shù)拈_銷。
5）Master/Slave架構
6）支持多種語言

7.1.3 Map和Reduce

Map：1）把小數(shù)據集進一步解析成一批k-v對，并輸入到Map函數(shù)；2）每一個輸入的k1-v1對經過Map函數(shù)處理后，輸出一批新的k2-v2對，k2-v2對是中間結果。
Reduce：把中間值根據鍵值（k2）進行聚合輸出。
具體的Map處理過程和聚合過程，則由用戶編程完成

7.2 MapReduce的體系結構

主要由以下四個部分構成。
1）Client
用戶編寫的程序通過Client提交到JobTracker端
用戶可以通過Client提供的API查看作業(yè)運行狀態(tài)
2）Job Tracker
負責資源監(jiān)控和作業(yè)調度
監(jiān)控所有的TaskTracker和Job的健康狀況
跟蹤任務進度、資源使用情況等，并告知TaskScheduler，由后者進行合適的資源調度
3）TaskTracker
將本節(jié)點任務進度、資源使用情況等發(fā)給JobTracker，并接受后者命令進行啟動新任務、殺死任務等操作。
4）Task
分為Map Task和Reduce Task兩種，均由TaskTracker啟動

7.3 MapReduce工作流程

7.1 概述

大致流程是：原始數(shù)據分片 → 每個分片啟動一個Map任務，進行并行處理 → shuffle：對Map的輸出進行分區(qū)、排序、歸并等 → 發(fā)送給Reduce任務進行處理 → 輸出并進行分布式存儲
有以下特點
1）不同的Map任務間不會通信
2）不同的Reduce間也不會有通信
3）用戶不能顯式地操作不同機器間地消息發(fā)送，一切都由MapReduce框架自身實現(xiàn)

7.3.2 MapReduce各個執(zhí)行階段

1. 基本過程
1）預處理：由InputFormat模塊完成數(shù)據的格式驗證，文件的邏輯切分（切分為多個InputSplit）等工作。
2）數(shù)據加載和轉換：由RecordReader模塊根據InputSplit信息加載數(shù)據，并轉換成適合Map任務讀取的鍵值對，然后輸入給Map任務。
3）Map任務：把輸入的kv對轉換成另一堆kv對，具體的轉換規(guī)則由用戶編程完成。
4）Shuffle：對Map任務的輸出進行分區(qū)、排序、合并、歸并等操作，然后發(fā)送給Reduce任務
5）Reduce：把接收的kv對根據k進行聚合，具體聚合方式由用戶編寫的Reduce任務完成
6）輸出、保存：由OutputFormat模塊驗證結果，并把結果保存到分布式文件系統(tǒng)
2. 重點概念
1）分片（Split）：在HDFS中，一個文件并分為很多個物理分塊（block）。對于MapReduce而言，其處理單位是Split，是一個邏輯概念，只包含一些元數(shù)據信息，如數(shù)據起始位置、數(shù)據長度、數(shù)據所在節(jié)點等。每個分片對應一個Map任務，設置多少分片就會有多少個Map任務，太多耗費管理資源，太少則降低并行度，通常會把分片大小設置成一個HDFS塊的大小。
2）任務數(shù)量：Map任務數(shù)量上文已描述。Reduce任務數(shù)量取決于集群可用的Reduce任務槽（slot）的數(shù)目，通常設置成略小于可用數(shù)的數(shù)

7.3.3 Shuffle過程 ☆

1. Map端的shuffle過程
1）輸入數(shù)據和執(zhí)行Map任務：每一個Map接受一個分片，并進行處理。
2）寫入緩存：MapReduce默認100MB的緩存，Map任務的輸出先往緩存里進行存儲。
3）溢寫
當緩存用到一定比例（常見0.8，即已用了80MB空間）時，啟動溢寫操作，把數(shù)據寫入磁盤。但是溢寫并不是直接寫到磁盤里，而是首先進行了分區(qū)、排序、合并等操作。
分區(qū)：因為每個Map的輸出都會分發(fā)到多個Reduce任務上，所以先對這些kv對們進行分區(qū)。最常用的分區(qū)方式是對key進行哈希后再用Reduce任務數(shù)取模。
排序：每個分區(qū)的數(shù)據根據key值進行排序，是MR的默認操作。
合并（可選操作）：如果有兩個<"a",1>鍵值對，可以合并成<"a",2>，相當于把值相加，這是用戶自己定義的合并方式。合并是為了減少寫入磁盤的數(shù)據量，但必須保證不影響后續(xù)的Reduce結果。
完成上述操作后，緩存的數(shù)據被寫入磁盤
4）文件歸并：Map任務全部完成后，進行歸并操作。若存在兩個<"a",1>鍵值對，則把它歸并成<"a",<1,1>>，（注意合并與歸并的區(qū)別，歸并就是把值合成一個列表）。歸并操作也不一定執(zhí)行，只有在溢寫文件數(shù)量大于預設值時才會執(zhí)行。
上述操作全部完成后，Map端的shuffle就完事了。
2. Reduce端的shuffle過程
1）Reduce任務通過RPC向JobTracker詢問任務是否已完成，若完成則領取數(shù)據
2）歸并、合并、排序 ：Reduce任務從不同的Map任務領取了多份數(shù)據，放入緩存，先歸并，再合并（可選），然后寫入磁盤
3）多個溢寫文件歸并成一個大文件
4）發(fā)送給Reduce處理

7.3.4 MapReduce應用程序的執(zhí)行過程

籠統(tǒng)描述為 輸入文件 → Map階段 → 中間文件 → Reduce階段 → 輸出文件。其中Map和Reduce任務是由用戶編寫，中間的shuffle是自動完成的。其它略。

7.4 WordCount示例

WordCount示例之于分布式編程，就像Hello World之于編程。

7.4.1 任務分析

不是所有任務都能用MR去做，只有能執(zhí)行分而治之的策略的任務才可以。

7.4.2 程序設計

1）原始數(shù)據處理：把原始數(shù)據分片，把每片中的內容按行拆分成鍵值對，以行號作為鍵，以行內容作為值。這樣就可以作為Map的輸入了。
2）Map任務：舉例來說，輸入是<1, "hello world bye world">，輸出是<hello, 1>、<world, 1>、<bye, 1>、<world, 1>四個鍵值對。
3）Shuffle：如果未定義合并操作，則shuffle進行歸并和排序，上述輸出變成了<bye, 1>，<hello,1>，<world,<1,1>>。（如果定義了合并操作，最后一項可以變成<world, 2>）
4）Reduce任務：歸并、排序、求和（因為是count任務，所以是求和操作進行聚合）
5）輸出與存儲

7.5 MR的具體應用

MR可以應用于關系代數(shù)運算、分組聚合運算、矩陣-向量乘法、矩陣乘法等。
所謂關系代數(shù)運算，就是指關系型數(shù)據庫的篩選、并交差、連接等操作。Hadoop中的hive工具，就是把SQL語句轉換成MapReduce任務。
不太懂，略過。

7.6 MR編程實踐

學會java后再寫，掠過。