[發(fā)明專利]用于MapReduce的中間結(jié)果數(shù)據(jù)排序方法及系統(tǒng)

在審

• 申請?zhí)枺?/td>: 201310305931.8
• 申請日: 2013-07-19
• 公開（公告）號: CN103440246A
• 公開（公告）日: 2013-12-11
• 發(fā)明（設(shè)計(jì)）人: 王猛;楊毅;王謙
• 申請（專利權(quán)）人: 百度在線網(wǎng)絡(luò)技術(shù)（北京）有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F12/08
• 代理公司: 北京清亦華知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11201
• 代理人: 宋合成

1.一種用于MapReduce的中間結(jié)果數(shù)據(jù)的排序方法，其特征在于，包括以下步驟：

從映射任務(wù)服務(wù)器獲取映射任務(wù)產(chǎn)生的多個(gè)中間結(jié)果數(shù)據(jù)；

根據(jù)多個(gè)所述中間結(jié)果數(shù)據(jù)所屬的分片將多個(gè)所述中間結(jié)果數(shù)據(jù)分為N組；

分別通過N個(gè)線程對所述N組內(nèi)的中間結(jié)果數(shù)據(jù)進(jìn)行排序；以及

將排序后的N組中間結(jié)果數(shù)據(jù)從內(nèi)存中寫入本地磁盤。

2.根據(jù)權(quán)利要求1所述的用于MapReduce的中間結(jié)果數(shù)據(jù)的排序方法，其特征在于，還包括：

簡化任務(wù)服務(wù)器從所述本地磁盤中獲取排序后的N組中間數(shù)據(jù)結(jié)果，并對所述N組中間數(shù)據(jù)結(jié)果進(jìn)行簡化任務(wù)處理。

3.根據(jù)權(quán)利要求1所述的用于MapReduce的中間結(jié)果數(shù)據(jù)的排序方法，其特征在于，所述根據(jù)多個(gè)所述中間結(jié)果數(shù)據(jù)所屬的分片將多個(gè)所述中間結(jié)果數(shù)據(jù)分為N組，進(jìn)一步包括：

創(chuàng)建分片索引二維數(shù)組；

將多個(gè)所述中間結(jié)果數(shù)據(jù)所屬的分片合并后存儲(chǔ)在所述分片索引二維數(shù)組的第一維存儲(chǔ)空間中；

將每個(gè)分片位置索引存儲(chǔ)在所述分片索引二維數(shù)組的第二維存儲(chǔ)空間中；

根據(jù)所述第一維存儲(chǔ)空間存儲(chǔ)的多個(gè)分片對存儲(chǔ)在第二維存儲(chǔ)空間中的每個(gè)分片對應(yīng)的多個(gè)分片位置索引進(jìn)行排序。

4.根據(jù)權(quán)利要求3所述的用于MapReduce的中間結(jié)果數(shù)據(jù)的排序方法，其特征在于，對存儲(chǔ)在第二維存儲(chǔ)空間中的每個(gè)分片對應(yīng)的多個(gè)分片位置索引通過一個(gè)線程進(jìn)行排序。

5.一種用于MapReduce的中間結(jié)果數(shù)據(jù)的排序系統(tǒng)，其特征在于，包括：本地服務(wù)器和映射服務(wù)器，其中，

所述映射服務(wù)器用于執(zhí)行映射任務(wù)以生成多個(gè)中間結(jié)果數(shù)據(jù)；

所述本地服務(wù)器用于從所述映射任務(wù)服務(wù)器獲取所述多個(gè)中間結(jié)果數(shù)據(jù)，并根據(jù)多個(gè)所述中間結(jié)果數(shù)據(jù)所屬的分片將多個(gè)所述中間結(jié)果數(shù)據(jù)分為N組，并分別通過N個(gè)線程對所述N組內(nèi)的中間結(jié)果數(shù)據(jù)進(jìn)行排序，以及將排序后的N組中間結(jié)果數(shù)據(jù)從內(nèi)存中寫入本地磁盤。

6.根據(jù)權(quán)利要求1所述的用于MapReduce的中間結(jié)果數(shù)據(jù)的排序系統(tǒng)，其特征在于，還包括：

簡化服務(wù)器，所述簡化服務(wù)器用于從所述本地服務(wù)器的本地磁盤中獲取排序后的N組中間數(shù)據(jù)結(jié)果，并對所述N組中間數(shù)據(jù)結(jié)果進(jìn)行簡化任務(wù)處理。

7.根據(jù)權(quán)利要求5所述的用于MapReduce的中間結(jié)果數(shù)據(jù)的排序系統(tǒng)，其特征在于，所述本地服務(wù)器根據(jù)多個(gè)所述中間結(jié)果數(shù)據(jù)所屬的分片將多個(gè)所述中間結(jié)果數(shù)據(jù)分為N組，包括：創(chuàng)建分片索引二維數(shù)組，將多個(gè)所述中間結(jié)果數(shù)據(jù)所屬的分片合并后存儲(chǔ)在所述分片索引二維數(shù)組的第一維存儲(chǔ)空間中，并將每個(gè)分片位置索引存儲(chǔ)在所述分片索引二維數(shù)組的第二維存儲(chǔ)空間中，以及根據(jù)所述第一維存儲(chǔ)空間存儲(chǔ)的多個(gè)分片對存儲(chǔ)在第二維存儲(chǔ)空間中的每個(gè)分片對應(yīng)的多個(gè)分片位置索引進(jìn)行排序。

8.根據(jù)權(quán)利要求7所述的用于MapReduce的中間結(jié)果數(shù)據(jù)的排序系統(tǒng)，其特征在于，所述本地服務(wù)器對存儲(chǔ)在第二維存儲(chǔ)空間中的每個(gè)分片對應(yīng)的多個(gè)分片位置索引是通過一個(gè)獨(dú)立的線程進(jìn)行排序的。