Hadoop MapReduce，作為分散式計算的第一代引擎，其經典的地位是不容動搖的，而越是經典越是有代表性的東西，也就越需要去深入理解其中的原理和執行機制。今天的大資料開發分享，我們主要來講講MapReduce排序的相關問題。

排序是MapReduce的靈魂，MapReduce在Map和Reduce的兩個階段當中，都在反覆地執行排序。快速排序和歸併排序在MapReduce中有兩種排序方式，分別是快速排序和歸併排序——快速排序：透過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分別進行快速排序，整個排序過程可以遞迴進行，以此達到整個資料變成有序序列。歸併排序：歸併排序（MERGE-SORT）是建立在歸併操作上的一種有效的排序演算法，該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為二路歸併。

MapReduce過程中的幾次排序在MapReduce的shuffle過程中通常會執行三次排序，分別是：Map的溢寫階段：根據分割槽以及key進行快速排序Map的合併溢寫檔案：將同一個分割槽的多個溢寫檔案進行歸併排序，合成大的溢寫檔案Reduce輸入階段：將同一分割槽，來自不同Map task的資料檔案進行歸併排序此外，在MapReduce整個過程中，預設是會對輸出的KV對按照key進行排序的，而且是使用快速排序。Map輸出的排序，其實也就是上面的溢寫過程中的排序。Reduce輸出的排序，即Reduce處理完資料後，MapReduce內部會自動對輸出的KV按照key進行排序。MapReduce如何執行排序在Map端：每個Map任務都有一個環形的記憶體緩衝區用於儲存任務輸出。緩衝區達到一定的閾值(預設80%)，一條後臺執行緒便開始把內容溢位(spill)到磁碟。每次記憶體緩衝區達到溢位閾值，就會新建一個溢位檔案(spill file)。在寫磁碟之前，執行緒首先根據資料最終要傳的Reduce把資料劃分成相應的分割槽(partition)。在每個分割槽中，後臺執行緒按鍵進行記憶體中排序(排序是在Map端進行的)。如果有combiner函式就會在排序後的輸出上執行，為了讓Map輸出結果更加緊湊。在任務完成之前，溢位檔案被合併成一個已分割槽且已排序的輸出檔案。如果溢位檔案多於設定的數量，combiner就會在輸出檔案寫到磁碟之前再次執行。

在Reduce端：複製階段，如果Map的輸出相當小，會被複制到Reduce任務的JVM記憶體中；否則Map輸出被複制到磁碟。隨著磁碟上副本增多，後臺執行緒會將它們合併為更大的、排好序的檔案。排序階段，準確的說是合併階段。複製完成Map的輸出後，將合併Map輸出，維持其順序排序。最後一趟的合併來自記憶體和磁碟片段。Reduce階段，執行Reduce任務，把最後一趟合併的資料直接輸入Reduce函式，從而省略了一次磁碟往返行程。關於大資料開發，MapReduce排序的相關問題，以上就為大家做了詳細的介紹了。MapReduce在執行過程中，排序是一個重要的操作，理解了排序對於MapReduce計算流程也會有更清晰的認識。