[發(fā)明專利]基于MapReduce編程架構(gòu)的任務(wù)分配方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 200810241080.4
• 申請(qǐng)日: 2008-12-25
• 公開（公告）號(hào): CN101764835A
• 公開（公告）日: 2010-06-30
• 發(fā)明（設(shè)計(jì)）人: 李麗娟;陳浩華;嚴(yán)哲峰
• 申請(qǐng)（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號(hào): H04L29/08
• 分類號(hào): H04L29/08;H04L29/06
• 代理公司: 北京凱特來知識(shí)產(chǎn)權(quán)代理有限公司 11260
• 代理人: 鄭立明

1.一種基于MapReduce編程架構(gòu)的任務(wù)分配方法，其特征在于， 所述方法包括：

判斷第一節(jié)點(diǎn)是否空閑，如果是，則所述第一節(jié)點(diǎn)執(zhí)行下述步驟 A；否則，所述第一節(jié)點(diǎn)執(zhí)行下述步驟B；

步驟A，所述第一節(jié)點(diǎn)向外發(fā)送空閑消息，并接收第二節(jié)點(diǎn)返回 的所述空閑消息的響應(yīng)消息，所述響應(yīng)消息包括需要轉(zhuǎn)移的任務(wù)量和 所述任務(wù)量所對(duì)應(yīng)的所述第二節(jié)點(diǎn)的節(jié)點(diǎn)地址；在判斷出所述需要轉(zhuǎn) 移的任務(wù)量小于剩余能力時(shí)，將所述需要轉(zhuǎn)移的任務(wù)量對(duì)應(yīng)的所述第 二節(jié)點(diǎn)的節(jié)點(diǎn)地址存儲(chǔ)在過載節(jié)點(diǎn)列表中，向所述過載節(jié)點(diǎn)列表中的 一個(gè)節(jié)點(diǎn)地址發(fā)送任務(wù)轉(zhuǎn)移請(qǐng)求消息，接收轉(zhuǎn)移的任務(wù)并進(jìn)行計(jì)算處 理；

步驟B，在判斷出所述第一節(jié)點(diǎn)過載且未進(jìn)行任務(wù)轉(zhuǎn)移時(shí)，接收 到第三節(jié)點(diǎn)發(fā)送的空閑消息后，向所述第三節(jié)點(diǎn)回復(fù)響應(yīng)消息；在收 到第三節(jié)點(diǎn)發(fā)送的任務(wù)轉(zhuǎn)移請(qǐng)求消息后，將轉(zhuǎn)移的任務(wù)發(fā)送給所述任 務(wù)轉(zhuǎn)移請(qǐng)求消息所對(duì)應(yīng)的所述第三節(jié)點(diǎn)。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，預(yù)先將基于 MapReduce編程架構(gòu)下的底層存儲(chǔ)系統(tǒng)的數(shù)據(jù)分塊邏輯分片成多個(gè) 邏輯小塊，并以所述邏輯小塊為任務(wù)執(zhí)行和轉(zhuǎn)移的基本單元。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述向所述過載節(jié) 點(diǎn)列表中的一個(gè)節(jié)點(diǎn)地址發(fā)送任務(wù)轉(zhuǎn)移請(qǐng)求消息包括：

在過載節(jié)點(diǎn)列表中選擇最近的節(jié)點(diǎn)地址發(fā)送所述任務(wù)轉(zhuǎn)移請(qǐng)求 消息。

4.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述接收轉(zhuǎn)移的任 務(wù)并進(jìn)行計(jì)算處理包括：

如判斷出所述轉(zhuǎn)移的任務(wù)為未執(zhí)行的任務(wù)，則直接計(jì)算處理所述 轉(zhuǎn)移的任務(wù)；

如判斷出所述轉(zhuǎn)移的任務(wù)是執(zhí)行中的任務(wù)，則獲取執(zhí)行所述轉(zhuǎn)移 的任務(wù)時(shí)的中間數(shù)據(jù)后，再計(jì)算處理所述轉(zhuǎn)移的任務(wù)。

5.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述方法在進(jìn)行計(jì) 算處理后，還包括：

如判斷出剩余能力還大于剩余的需要轉(zhuǎn)移的任務(wù)量時(shí)，向剩余的 需要轉(zhuǎn)移的任務(wù)量所對(duì)應(yīng)的節(jié)點(diǎn)地址發(fā)送任務(wù)轉(zhuǎn)移請(qǐng)求消息。

6.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述方法在將轉(zhuǎn)移 的任務(wù)發(fā)送給所述任務(wù)轉(zhuǎn)移請(qǐng)求消息所對(duì)應(yīng)的所述第三節(jié)點(diǎn)之后，還 包括：

通知MapReduce編程架構(gòu)下的master回收垃圾空間。

7.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述將轉(zhuǎn)移的任務(wù) 發(fā)送給所述任務(wù)轉(zhuǎn)移請(qǐng)求消息所對(duì)應(yīng)的所述第三節(jié)點(diǎn)包括：

將未被執(zhí)行的任務(wù)發(fā)送給所述任務(wù)轉(zhuǎn)移請(qǐng)求消息所對(duì)應(yīng)的所述 第三節(jié)點(diǎn)；

或?qū)⒄趫?zhí)行任務(wù)中的最后一個(gè)任務(wù)發(fā)送給所述任務(wù)轉(zhuǎn)移請(qǐng)求 消息所對(duì)應(yīng)的所述第三節(jié)點(diǎn)。

8.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述方法在計(jì)算處 理之后還包括：根據(jù)MapReduce編程架構(gòu)下的map任務(wù)的個(gè)數(shù)自行設(shè) 定多個(gè)reduce任務(wù)并進(jìn)行reduce計(jì)算，將所述多個(gè)reduce任務(wù)的計(jì)算結(jié) 果根據(jù)用戶指定需要輸出的文件數(shù)量進(jìn)行合并后輸出最終計(jì)算結(jié)果。

9.一種基于MapReduce編程架構(gòu)的任務(wù)分配裝置，其特征在于， 所述裝置包括：

判斷單元，用于判斷空閑或過載；

發(fā)送單元，用于在所述判斷單元判斷出空閑時(shí)，發(fā)送空閑消息；

接收單元，用于接收所述空閑消息的響應(yīng)消息，所述響應(yīng)消息包 括需要轉(zhuǎn)移的任務(wù)量和所述任務(wù)量所對(duì)應(yīng)的節(jié)點(diǎn)地址；

存儲(chǔ)單元，用于在所述需要轉(zhuǎn)移的任務(wù)量小于剩余能力時(shí)，將所 述需要轉(zhuǎn)移的任務(wù)量對(duì)應(yīng)的節(jié)點(diǎn)地址存儲(chǔ)在過載節(jié)點(diǎn)列表中，

所述發(fā)送單元還用于向所述過載節(jié)點(diǎn)列表中的一個(gè)節(jié)點(diǎn)地址發(fā) 送任務(wù)轉(zhuǎn)移請(qǐng)求消息，

所述接收單元還用于接收轉(zhuǎn)移的任務(wù)；

計(jì)算單元，用于對(duì)所述轉(zhuǎn)移的任務(wù)進(jìn)行計(jì)算處理；

所述判斷單元判斷出過載且未進(jìn)行任務(wù)轉(zhuǎn)移時(shí)；通知所述發(fā)送單 元對(duì)所述響應(yīng)消息進(jìn)行回復(fù)；

任務(wù)轉(zhuǎn)移單元，用于在所述接收單元收到任務(wù)轉(zhuǎn)移請(qǐng)求消息后， 將轉(zhuǎn)移的任務(wù)發(fā)送給所述任務(wù)轉(zhuǎn)移請(qǐng)求消息所對(duì)應(yīng)的節(jié)點(diǎn)。