四、MapReduce中的排序

一、排序概述

1、在MapReduce的shuffle過程中執行了三次排序，分別是：
map的溢寫階段：根據分區以及key進行快速排序
map的合并溢寫文件：將同一個分區的多個溢寫文件進行歸并排序，合成大的溢寫文件
reduce輸入階段：將同一分區，來自不同map task的數據文件進行歸并排序

2、在MapReduce整個過程中，默認是會對輸出的KV對按照key進行排序的，而且是使用快速排序。
map輸出的排序的，其實也就是上面的溢寫過程中的排序。
reduce輸出的排序，即reduce處理完數據后，MapReduce內部會自動對輸出的KV按照key進行排序

以上排序都是根據KV中的Key進行排序的。所以當我們自定義的類作為Key時，需要實現WritableComparable 接口，也就是實現里面的 compareTo() 方法，用于排序時進行比較。
比較規則如下：

public int compareTo(object other) {
    this>other 返回1，正序，返回 -1，逆序。
}

二、二次排序的定義

而在依據key進行排序時，如果key是一個復合對象，即該對象中包含多個成員屬性，那么在進行key比較時，就會涉及到多個屬性間的比較，而如果compareTo() 方法中，比較條件為兩個的話，就稱為二次排序。

三、輔助排序的定義

輔助排序也叫分組排序，是指在reduce前的group過程中根據排序規則進行的分組，因為分組的時候是需要比較KV中key是否相同，如果相同才會歸為同一個組，如果不相等，就歸為不同的組，所以就涉及到key比較方法了。總的來說其實定義key在什么情況下才相等。這個過程可以自己定義分組的方法，也就是分組排序的實現類。
使用方法：
1、自定義分組類，繼承 WritableComparator
2、調用父類的構造方法，創建實例
3、重寫父類的 compare方法

例子：

public class OrderGroupCompartor extends WritableComparator {

    protected OrderGroupCompartor() {
        super(OrderBean.class, true);
    }

    /**
     * 以orderbean對象中的ID為分組依據。
     * 同一ID的認為是同一個group，一個group只會調用一次reduce
     *
     * @param a  比較對象1
     * @param b  比較對象2
     * @return
     */
    @Override
    public int compare(WritableComparable a, WritableComparable b) {
        OrderBean aOrderBean = (OrderBean) a;
        OrderBean bOrderBean = (OrderBean) b;

        if (aOrderBean.getID() > bOrderBean.getID()) {
            return 1;
        } else if (aOrderBean.getID() < bOrderBean.getID()) {
            return -1;
        } else {
            return 0;
        }
    }
}

我們要注意的是，在進行分組時，同一個分組內的key是以第一個進入該分區的KV對中的key為準的。如：

有兩個KV對：
1、<[1,褲子]，20>
2、<[1,襪子]，21>
其中key由id和物品名稱組成的，value則是物品價格
假設分組依據是根據key中的id來分組的，那么上面兩個KV是屬于同一個group，但是實際上這兩個KV
的key是不相等的。當1號KV先進入該group，那么就會以1號的key作為該group的key，分組的結果為：
<[1,褲子]，[20,21]>
如果2號KV先進入，則按照前面的規則，分組結果為：
<[1,襪子]，[20,21]>

就會有這樣的情況的發生，我們要注意利用好這點。

那么誰先進入該group的呢？很簡單，是按照事先排序的順序，在前面的自然先進入。這里的排序其實就是前面reduce端的歸并排序的結果，而使用的排序依據其實就是key的包裝類中compareTo方法，屬于普通排序里面的東西。

編寫好自定義的分組排序類之后，需要在job中指定好自定義的分組類：

job.setGroupingComparatorClass(OrderGroupCompartor.class);

四、排序實例

普通排序請看 “MapReduce-統計手機號流量”
二次排序和輔助排序請看 “MapReduce--獲取價格最高的商品”