[發明專利]MapReduce計算框架中的高性能排序方法

有效

• 申請號: 201410145069.3
• 申請日: 2014-04-10
• 公開（公告）號: CN103995827B
• 公開（公告）日: 2017-08-04
• 發明（設計）人: 蔣達晟;陳薇;王騰蛟
• 申請（專利權）人: 北京大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京君尚知識產權代理事務所(普通合伙)11200
• 代理人: 馮藝東

1.一種MapReduce計算框架中的高性能排序方法，其步驟包括：

1)Map任務從HDFS上讀取文件，構造輸入數據的key/value對；

2)對輸入數據執行用戶自定義Map函數并輸出中間結果的key/value對，并計算key所對應的partition；對內存中每個partition設置對應的緩沖鏈，將中間結果的key/value對首先計算長度，然后插入到緩沖鏈中；

3)當內存無法放下所有中間結果的key/value對時，按照partition的順序，輸出所有緩沖鏈到本地文件；

4)對經過上述步驟后在內存和本地磁盤上形成的一個或多個未排序的結果按照partition的順序進行歸并，輸出成一個完整的按照partition進行分段的本地文件；

5)Reduce任務通過任務調度器獲得Map任務結束的信息，向負責該Map數據托管的進程發送http請求，拖取該Map輸出的中間數據中屬于該Reduce的部分，將這些數據根據其大小選擇放于內存或放于本地磁盤；

6)將內存或磁盤中的中間數據讀入內存中的排序緩沖池，當排序緩沖池滿時，對整個緩沖池進行排序；

7)對于中間數據無法全部放在一個排序緩沖池中的情況，在排序后將數據寫出到本地文件中。

2.如權利要求1所述的方法，其特征在于，還包括如下步驟：

8)對內存和本地文件中的有序結果進行歸并，歸并結果作為用戶自定義Reduce函數的輸入；

9)Reduce函數對相同key下的所有value執行操作，生成輸出數據的key/value對并寫入HDFS。

3.如權利要求1或2所述的方法，其特征在于：步驟6)還包括：對于大多數作業使用的整形或者字符數組類型的key，抽取key中能夠保序的4字節作為低32位，和該條記錄本身4字節的二級索引作為高32位進行拼接，形成一個8字節的長整形作為新的key。

4.如權利要求3所述的方法，其特征在于：在所述8字節上使用基數排序，使得其從key中抽取的4字節有序。

5.如權利要求4所述的方法，其特征在于：所述基數排序為非遞歸版本，輸入為兩個長整形的數組，一個用于存放原始數據，一個用于算法的臨時空間，算法執行后的結果為長整形數組中低32位整形有序。

6.如權利要求4所述的方法，其特征在于：獲取基數排序后的二級索引，再對其進行快速排序保證整體記錄的有序性。

7.如權利要求3所述的方法，其特征在于：抽取key中4字節的方法是：對于整數即其本身；對于字符數組類型的key為其排序序列的前4個字節，以整數對待，并在最高位取反。

8.如權利要求3所述的方法，其特征在于：步驟6)還包括：對于無法抽取保序4字節的key類型，構建二級索引，使用快速排序進行整體記錄的排序。

9.如權利要求1或2所述的方法，其特征在于，步驟6)還包括：采用雙緩沖結構將傳輸的內容添加到排序緩沖池中，以避免阻塞：當某一個排序緩沖滿后，異步地進行排序并寫出，同時另一個排序緩沖繼續接收傳輸的數據。