[發(fā)明專利]并行計(jì)算框架中的Reduce端自適應(yīng)負(fù)載均衡方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210047028.1
• 申請(qǐng)日: 2012-02-27
• 公開（公告）號(hào): CN102629219A
• 公開（公告）日: 2012-08-08
• 發(fā)明（設(shè)計(jì)）人: 王林青;高軍;周家?guī)?/a>;李紅燕;王騰蛟
• 申請(qǐng)（專利權(quán)）人: 北京大學(xué)
• 主分類號(hào): G06F9/50
• 分類號(hào): G06F9/50
• 代理公司: 北京君尚知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11200
• 代理人: 余長(zhǎng)江

技術(shù)領(lǐng)域

本發(fā)明屬于信息技術(shù)領(lǐng)域，涉及一種在分布式計(jì)算的環(huán)境下進(jìn)行分布式節(jié)點(diǎn)負(fù)載均衡的方法，特別涉及一種并行計(jì)算框架中的Reduce端自適應(yīng)負(fù)載均衡方法。

背景技術(shù)

隨著數(shù)據(jù)量的增長(zhǎng)以及對(duì)數(shù)據(jù)處理能力需求的增加，傳統(tǒng)的并行計(jì)算已經(jīng)不能很好地應(yīng)對(duì)大數(shù)據(jù)量下的分布式計(jì)算。

目前Map-Reduce計(jì)算框架通過數(shù)據(jù)和任務(wù)的隨機(jī)分配以及硬件資源的并行利用，較好地解決大數(shù)據(jù)量下的分布式計(jì)算的任務(wù)分配以及調(diào)度的問題，但由于Map-Reduce的任務(wù)分配依賴于靜態(tài)哈希函數(shù)設(shè)定以及并行計(jì)算個(gè)數(shù)的設(shè)置，導(dǎo)致分布式計(jì)算不夠均勻，也不夠面對(duì)不同數(shù)據(jù)自適應(yīng)。我們以Map-Reduce的實(shí)現(xiàn)Hadoop系統(tǒng)為例說(shuō)明上述問題

如圖1所示，為傳統(tǒng)Map-Reduce架構(gòu)及流程示意圖。其中Hadoop文件系統(tǒng)(簡(jiǎn)稱HDFS，Hadoop?File?System)負(fù)責(zé)數(shù)據(jù)的備份、分布式存取，而Map-Reduce計(jì)算框架則根據(jù)數(shù)據(jù)的分布，首先把數(shù)據(jù)進(jìn)行Map階段的處理，每一個(gè)Hadoop文件交給一個(gè)Map進(jìn)行處理，輸出的記錄為key-value對(duì)，經(jīng)過劃分之后，同一個(gè)key下的所有value都將會(huì)進(jìn)入同一個(gè)Reduce中進(jìn)行處理。Reduce階段的輸出結(jié)果會(huì)重新被存放到HDFS中。具體流程為：

1、開始運(yùn)行Job。用戶書寫Map和Reduce程序，并且把程序作為Job提交運(yùn)行。

2、Job客戶端從Job?Tracker獲取分配的ID，獲得ID才能夠獲得計(jì)算資源。

3、把Job需要的資源復(fù)制到HDFS，需要的資源包括程序中可能使用到的代碼包或者其他數(shù)據(jù)。

4、提交Job給Job?Tracker，Job?Tracker將開始跟蹤Job的運(yùn)行情況。

5、Job的初始化，環(huán)境參數(shù)設(shè)置，計(jì)算資源獲取等。

6、從HDFS上獲取Job需要的所有輸入分片(split)。每一個(gè)輸入文件從邏輯上由多個(gè)split構(gòu)成。

7、任務(wù)(Task)開始返回心跳信息。為了跟蹤每一個(gè)Map或者Reduce任務(wù)的運(yùn)行情況，所有這些任務(wù)需要按照一定的周期向Task?Tracker和Job?Tracker匯報(bào)運(yùn)行狀態(tài)。

8、Task?Tracker開始從HDFS中獲取運(yùn)行資源，開始讀取輸入。

9、開始運(yùn)行Map或者Reduce任務(wù)。

10、運(yùn)行Map任務(wù)。

11、Map輸出數(shù)據(jù)開始進(jìn)行劃分。

12、運(yùn)行Reduce任務(wù)并把結(jié)果寫入HDFS。

在這個(gè)傳統(tǒng)的Map-Reduce運(yùn)行架構(gòu)圖中，Map輸出的數(shù)據(jù)經(jīng)過Partition劃分函數(shù)被分配到Reduce。具體做法是在用戶開始運(yùn)行Map-Reduce任務(wù)之前，必須設(shè)置好Reduce的個(gè)數(shù)，此時(shí)Partition將會(huì)根據(jù)key的哈希值對(duì)Reduce個(gè)數(shù)進(jìn)行取余運(yùn)算得到一個(gè)Reduce端的編號(hào)并且把這個(gè)key對(duì)應(yīng)的一條記錄(即一個(gè)key-value對(duì))分配到該編號(hào)的Reduce。其中在Map對(duì)所有key-value對(duì)進(jìn)行Partition之后首先按照塊為單位存放在本地內(nèi)存或者磁盤中，最后再把這些塊通過網(wǎng)絡(luò)傳輸或者直接磁盤復(fù)制(當(dāng)Reduce和Map在同一個(gè)節(jié)點(diǎn)上的時(shí)候)的方式發(fā)送到對(duì)應(yīng)Reduce所在的節(jié)點(diǎn)上，Reduce階段將會(huì)對(duì)來(lái)自不同Map的數(shù)據(jù)進(jìn)行排序(sort)、合并(merge)，使得具有相同的key的所有記錄能作為Reduce一次計(jì)算的輸入。Reduce處理結(jié)束之后再把所有結(jié)果輸出到HDFS中。在這個(gè)過程中，Map?Task?Tracker和Reduce?Task?Tracker分別需要定期到每一個(gè)Map和Reduce中收集相關(guān)的運(yùn)行情況反饋信息。

正是由于這種簡(jiǎn)單的劃分方式，當(dāng)不同的key對(duì)應(yīng)的記錄個(gè)數(shù)分布不均勻或者key對(duì)應(yīng)的value大小也不同的時(shí)候，導(dǎo)致了有一些Reduce獲得的數(shù)據(jù)過大，有一些獲得的數(shù)據(jù)過小，導(dǎo)致了偏斜。此外，由于在現(xiàn)實(shí)任務(wù)中Map輸出的數(shù)據(jù)量和Map輸入的數(shù)據(jù)量不盡相同，用戶無(wú)法估計(jì)Reduce所要處理的數(shù)據(jù)量而設(shè)置合適的Reduce個(gè)數(shù)，無(wú)法自動(dòng)適應(yīng)分布不同的數(shù)據(jù)。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種并行計(jì)算框架中自適應(yīng)的Reduce端負(fù)載均衡方法，解決上述偏斜問題，自動(dòng)適應(yīng)分布不同的數(shù)據(jù)。

本發(fā)明的并行計(jì)算框架中的Reduce端自適應(yīng)負(fù)載均衡方法，其步驟包括：

1、各Map接收相應(yīng)Hadoop文件，進(jìn)行Map處理；