MapReduce的shuffle機制

shuffle過程（簡單了解）：從map的輸出到reduce的輸入之間的過程。

概念：Map是映射，負責資料的過濾分法，将原始資料轉化為鍵值對；Reduce是合并，将具有相同的key值的value進行處理後再輸出新的鍵值對作為最終結果。為了讓Reduce可以并行處理Map的結果，必須對Map的輸出進行一定的排序與分割，然後再交給對應的Reduce，Map端的輸出作為Reduce的輸入的過程叫做Shuffle.

注意點：一個分片對應一個 Map 任務，每個 Map 任務裡面會根據分片中的記錄執行多次 mapper 函數。一個分區對應一個 reduce 任務，每個 Reduce 任務中根據分區中的鍵來執行多次 reducer 函數。

1、Map端：每個map任務維護着一個環形緩沖區，用于存儲任務的輸出，預設100MB。當map輸出資料時，先寫到記憶體緩沖區，當記憶體緩沖區達到設定的門檻值之後，始溢出成spill檔案，然後進行分區（ partion）排序（快速排序），對每個分區的資料按key進行排序，如果有 combiner函數，則會在排序後的輸出上運作，使map的輸出結果更加緊湊，然後寫入磁盤。map任務輸出量很大時，可能進行好幾次分割，這樣spill檔案就會分布在不同的磁盤上。當最後一個spill檔案寫完之後，将多個spill檔案進行合并到一個已經分區并排序的大檔案，如果有combiner函數，在合并spill時，也會運作。将壓縮的Map輸出寫到磁盤是不錯的，可以減少磁盤的IO量，減少傳輸給的資料量。

2、 Reduce端：Reduce通過HTTP方式從map擷取資料， Reduce有少量的複制線程并行從map端複制資料到 Reduce端。一般需要從多個map端複制資料，有一個map完成就可以開始複制了。

如果map輸出比較小，會直接複制到記憶體。如果資料大，當達到記憶體緩沖區的門檻值後，會合并溢出到磁盤。如果有 combiner，合并期間運作，降低寫入磁盤的資料量。

最後一次合并結果作為 reduce函數的輸入，最後一次合并不一定合并成一個大檔案，可能會直接合并到 reduce上。合并因子預設是10，一趟合并的檔案數。

對已經排序輸出中的每一個鍵調用reduce函數，然後輸出到檔案系統（HDFS）。