[發(fā)明專利]動(dòng)態(tài)碎片分配調(diào)整

有效

• 申請(qǐng)?zhí)枺?/td>: 201580033526.2
• 申請(qǐng)日: 2015-07-06
• 公開（公告）號(hào): CN106663028B
• 公開（公告）日: 2021-05-25
• 發(fā)明（設(shè)計(jì)）人: J.S.赫維茨;E.R.基爾皮肖夫;J.普杰西瓦克-格爾博維克;K.J.戈德曼
• 申請(qǐng)（專利權(quán)）人: 谷歌有限責(zé)任公司
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48
• 代理公司: 北京市柳沈律師事務(wù)所 11105
• 代理人: 邵亞麗

1.一種由一個(gè)或多個(gè)處理器執(zhí)行的計(jì)算機(jī)實(shí)現(xiàn)的方法，該方法包括：

確定輸入數(shù)據(jù)集的批量數(shù)據(jù)處理作業(yè)的目標(biāo)完成時(shí)間，批量數(shù)據(jù)處理作業(yè)由多個(gè)任務(wù)執(zhí)行，多個(gè)任務(wù)的每個(gè)處理不同的輸入碎片，不同的輸入碎片包括輸入數(shù)據(jù)集的不同部分；

識(shí)別批量數(shù)據(jù)處理作業(yè)已經(jīng)進(jìn)入尾聲狀態(tài)，在尾聲狀態(tài)中，與輸入數(shù)據(jù)集相關(guān)聯(lián)的所有碎片正在由任務(wù)處理并且存在與批量處理作業(yè)相關(guān)聯(lián)的至少一個(gè)空閑任務(wù)；

在識(shí)別批量數(shù)據(jù)處理作業(yè)已經(jīng)進(jìn)入尾聲狀態(tài)之后，從多個(gè)任務(wù)中，識(shí)別第一任務(wù)，第一任務(wù)具有大于批量數(shù)據(jù)處理作業(yè)的目標(biāo)完成時(shí)間的估計(jì)完成時(shí)間，估計(jì)完成時(shí)間代表第一任務(wù)將完成處理由第一任務(wù)處理的第一輸入碎片處的輸入數(shù)據(jù)集的該部分的估計(jì)時(shí)間；以及

響應(yīng)于識(shí)別出所述第一任務(wù)，將第一輸入碎片分裂成第一分裂輸入碎片和不同于第一分裂輸入碎片的第二分裂輸入碎片，第一分裂輸入碎片包括第一輸入碎片的第一部分，并且第二分裂輸入碎片包括不同于第一部分的第一輸入碎片的第二部分。

2.根據(jù)權(quán)利要求1所述的方法，還包括：

指派第一分裂輸入碎片由第二任務(wù)處理；以及

將第二分裂輸入碎片插入到未指派的碎片的池中以等待由可用的任務(wù)處理。

3.根據(jù)權(quán)利要求2所述的方法，其中第二任務(wù)是第一任務(wù)并且可用的任務(wù)是與批量數(shù)據(jù)處理作業(yè)相關(guān)聯(lián)的空閑任務(wù)。

4.根據(jù)權(quán)利要求1所述的方法，其中多個(gè)任務(wù)的每個(gè)包括估計(jì)完成時(shí)間，估計(jì)完成時(shí)間代表任務(wù)將完成處理它的輸入碎片的估計(jì)時(shí)間。

5.根據(jù)權(quán)利要求4所述的方法，其中至少部分地基于批量數(shù)據(jù)處理作業(yè)的多個(gè)任務(wù)的估計(jì)完成時(shí)間而確定目標(biāo)完成時(shí)間。

6.根據(jù)權(quán)利要求4所述的方法，還包括至少部分地基于下面的至少一個(gè)，確定多個(gè)任務(wù)的每個(gè)的估計(jì)完成時(shí)間：對(duì)于多個(gè)任務(wù)的每個(gè)、剩余將要處理的輸入碎片的一部分的大小，對(duì)于已經(jīng)關(guān)于多個(gè)任務(wù)的每個(gè)而處理的輸入碎片的一部分、與多個(gè)任務(wù)的每個(gè)相關(guān)聯(lián)的處理速率，或者對(duì)于關(guān)于多個(gè)任務(wù)的每個(gè)在時(shí)間窗口內(nèi)處理的輸入碎片的一部分、與多個(gè)任務(wù)的每個(gè)相關(guān)聯(lián)的近期處理速率。

7.根據(jù)權(quán)利要求1所述的方法，其中基于下面的至少一個(gè)確定目標(biāo)完成時(shí)間：與批量數(shù)據(jù)處理作業(yè)相關(guān)聯(lián)的歷史信息，或者與其他批量數(shù)據(jù)處理作業(yè)相關(guān)聯(lián)的歷史信息。

8.根據(jù)權(quán)利要求1所述的方法，其中目標(biāo)完成時(shí)間是由批量數(shù)據(jù)處理作業(yè)的管理員指定用于結(jié)束批量數(shù)據(jù)處理作業(yè)的截止時(shí)間。

9.根據(jù)權(quán)利要求1所述的方法，其中識(shí)別第一任務(wù)和分裂第一輸入碎片由第一任務(wù)本身執(zhí)行。

10.根據(jù)權(quán)利要求9所述的方法，其中識(shí)別第一任務(wù)包括：

由第一任務(wù)從與批量數(shù)據(jù)處理作業(yè)相關(guān)聯(lián)的監(jiān)管器處理接收目標(biāo)完成時(shí)間；以及

由第一任務(wù)比較目標(biāo)完成時(shí)間與估計(jì)完成時(shí)間以確定在目標(biāo)完成時(shí)間之前第一任務(wù)將不會(huì)完成。

11.根據(jù)權(quán)利要求10所述的方法，其中分裂第一任務(wù)包括：

由第一任務(wù)將在目標(biāo)完成時(shí)間之前第一任務(wù)將不能夠處理的第一輸入碎片的一部分的指示發(fā)送給監(jiān)管器處理；以及

由監(jiān)管器處理將第一輸入碎片的該部分指派給空閑任務(wù)進(jìn)行處理。

12.根據(jù)權(quán)利要求1所述的方法，其中確定批量數(shù)據(jù)處理作業(yè)的目標(biāo)完成時(shí)間包括計(jì)算多個(gè)任務(wù)的估計(jì)完成時(shí)間以及與批量數(shù)據(jù)處理作業(yè)相關(guān)聯(lián)的一個(gè)或多個(gè)空閑任務(wù)的估計(jì)完成時(shí)間的平均，其中一個(gè)或多個(gè)空閑任務(wù)的估計(jì)完成時(shí)間具有值0。

13.一種系統(tǒng)，包括：

存儲(chǔ)器，用于存儲(chǔ)數(shù)據(jù)；以及

一個(gè)或多個(gè)處理器，可操作以執(zhí)行操作，包括：

確定輸入數(shù)據(jù)集的批量數(shù)據(jù)處理作業(yè)的目標(biāo)完成時(shí)間，批量數(shù)據(jù)處理作業(yè)由多個(gè)任務(wù)執(zhí)行，多個(gè)任務(wù)的每個(gè)處理不同的輸入碎片，不同的輸入碎片包括輸入數(shù)據(jù)集的不同部分；

識(shí)別批量數(shù)據(jù)處理作業(yè)已經(jīng)進(jìn)入尾聲狀態(tài)，在尾聲狀態(tài)中，與輸入數(shù)據(jù)集相關(guān)聯(lián)的所有碎片正在由任務(wù)處理并且存在與批量處理作業(yè)相關(guān)聯(lián)的至少一個(gè)空閑任務(wù)；

在識(shí)別批量數(shù)據(jù)處理作業(yè)已經(jīng)進(jìn)入尾聲狀態(tài)之后，從多個(gè)任務(wù)中，識(shí)別第一任務(wù)，第一任務(wù)具有大于批量數(shù)據(jù)處理作業(yè)的目標(biāo)完成時(shí)間的估計(jì)完成時(shí)間，估計(jì)完成時(shí)間代表第一任務(wù)將完成處理由第一任務(wù)處理的第一輸入碎片處的輸入數(shù)據(jù)集的該部分的估計(jì)時(shí)間；以及

響應(yīng)于識(shí)別出所述第一任務(wù)，將第一輸入碎片分裂成第一分裂輸入碎片和不同于第一分裂輸入碎片的第二分裂輸入碎片，第一分裂輸入碎片包括第一輸入碎片的第一部分，并且第二分裂輸入碎片包括不同于第一部分的第一輸入碎片的第二部分。