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

有效

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

本公開(kāi)涉及在并行處理操作期間動(dòng)態(tài)調(diào)整碎片分配。一種示例方法包括確定由多個(gè)任務(wù)執(zhí)行的輸入數(shù)據(jù)集的批量數(shù)據(jù)處理作業(yè)的目標(biāo)完成時(shí)間，多個(gè)任務(wù)的每個(gè)處理不同的輸入碎片，不同的輸入碎片包括輸入數(shù)據(jù)集的不同部分；識(shí)別估計(jì)的完成時(shí)間大于批量數(shù)據(jù)處理作業(yè)的目標(biāo)完成時(shí)間的第一任務(wù)；以及將第一輸入碎片分裂成第一分裂輸入碎片和不同于第一分裂輸入碎片的第二分裂輸入碎片，第一分裂輸入碎片包括第一輸入碎片的第一部分，并且第二分裂輸入碎片包括不同于第一部分的第一輸入碎片的第二部分。

背景技術(shù)

大規(guī)模數(shù)據(jù)處理可以包括并行處理，其通常涉及同時(shí)在大數(shù)據(jù)集的每個(gè)元素上執(zhí)行一些操作。數(shù)據(jù)集可以分裂成較小的集合，稱(chēng)作“碎片”，并且由單獨(dú)的處理和/或設(shè)備并行處理。

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

本公開(kāi)涉及在并行處理操作期間動(dòng)態(tài)調(diào)整碎片分配。

一般來(lái)說(shuō)，在本說(shuō)明書(shū)中描述的主題的一個(gè)革新方面能夠在方法中實(shí)施，方法包括下面的動(dòng)作：確定輸入數(shù)據(jù)集的批量數(shù)據(jù)處理作業(yè)的目標(biāo)完成時(shí)間，批量數(shù)據(jù)處理作業(yè)由多個(gè)任務(wù)執(zhí)行，多個(gè)任務(wù)的每個(gè)處理不同的輸入碎片，不同的輸入碎片包括輸入數(shù)據(jù)集的不同部分；從多個(gè)任務(wù)中，識(shí)別具有大于批量數(shù)據(jù)處理作業(yè)的目標(biāo)完成時(shí)間的估計(jì)的完成時(shí)間的第一任務(wù)，估計(jì)的完成時(shí)間代表第一任務(wù)將完成處理由第一任務(wù)處理的第一輸入碎片處的輸入數(shù)據(jù)集的該部分的估計(jì)時(shí)間；以及將第一輸入碎片分裂成第一分裂輸入碎片和不同于第一分裂輸入碎片的第二分裂輸入碎片，第一分裂輸入碎片包括第一輸入碎片的第一部分，并且第二分裂輸入碎片包括不同于第一部分的第一輸入碎片的第二部分。

該方面的其他實(shí)施例包括相應(yīng)的系統(tǒng)、裝置以及編碼在計(jì)算機(jī)存儲(chǔ)設(shè)備上、被配置為執(zhí)行方法的動(dòng)作的計(jì)算機(jī)程序。

能夠?qū)崿F(xiàn)在該說(shuō)明書(shū)中描述的主題的特定實(shí)施例以實(shí)現(xiàn)下面的優(yōu)點(diǎn)的一個(gè)或多個(gè)。通過(guò)在處理作業(yè)期間動(dòng)態(tài)地適配碎片分配，可以更好地優(yōu)化碎片分配，因?yàn)殛P(guān)于每個(gè)特定碎片的更多信息可用，諸如它的大小、復(fù)雜度、平均處理速率或者其他信息。以這種方式適配碎片分配也允許分配響應(yīng)觀察到的條件而改變，諸如任務(wù)(例如，計(jì)算資源)處理碎片比預(yù)期更慢或者另外的處理資源正在變得可用。

在該說(shuō)明書(shū)中描述的主題的一個(gè)或多個(gè)實(shí)施例的細(xì)節(jié)在下面的附隨附圖和描述中陳述。主題的其他特征、方面和優(yōu)點(diǎn)將從描述、附圖和權(quán)利要求書(shū)中變得明白。

附圖說(shuō)明

圖1是在并行處理操作期間動(dòng)態(tài)調(diào)整碎片分配能夠發(fā)生的環(huán)境的框圖。

圖2A-2B是在碎片分裂之前和之后的系統(tǒng)配置的框圖。

圖3是在并行處理操作期間動(dòng)態(tài)調(diào)整碎片分配的示例處理的順序圖。

圖4是在并行處理操作期間動(dòng)態(tài)調(diào)整碎片分配的示例處理的流程圖。

圖5是示例計(jì)算設(shè)備的框圖。

在各種附圖中相同的附圖標(biāo)記和名稱(chēng)指示相同的元素。

具體實(shí)施方式

大規(guī)模并行數(shù)據(jù)處理應(yīng)用必須分發(fā)大的輸入數(shù)據(jù)集用于由任務(wù)池(例如，計(jì)算資源)進(jìn)行處理。這可以通過(guò)將輸入數(shù)據(jù)集劃分成較小的集合或者“碎片”，并且將碎片指派給可用的任務(wù)來(lái)執(zhí)行。在涉及異質(zhì)性輸入數(shù)據(jù)集、任務(wù)執(zhí)行環(huán)境、網(wǎng)絡(luò)條件或者其他變化因素的情況下，可能難以均勻地劃分輸入數(shù)據(jù)集，使得每個(gè)任務(wù)在相似量的時(shí)間內(nèi)處理它的被指派的碎片。大相徑庭的碎片處理時(shí)間可以導(dǎo)致比其他碎片花費(fèi)更長(zhǎng)時(shí)間進(jìn)行處理的“落后者”碎片。如果特定作業(yè)在完成之前需要所有碎片被處理，那么落后者碎片可以主導(dǎo)該特定作業(yè)的總體運(yùn)行時(shí)間。而且，如果任務(wù)的計(jì)算結(jié)果沒(méi)有提交到諸如遠(yuǎn)程磁盤(pán)這樣的永久存儲(chǔ)器，那么落后者碎片可能是成問(wèn)題的。因?yàn)榍笆霎愘|(zhì)性，輸入數(shù)據(jù)集的特定區(qū)段可能處理起來(lái)非常慢或者可能包含比預(yù)期的更多的記錄。如果處理該碎片的任務(wù)在輸出持久化之前失敗，那么所有的進(jìn)展可能丟失。如果系統(tǒng)等待直到在提交工作之前處理整個(gè)碎片，那么大量的工作可能需要重做。大的碎片大小可以加劇這種問(wèn)題。