[發(fā)明專利]動態(tài)混洗重新配置

有效

• 申請?zhí)枺?/td>: 201480065416.X
• 申請日: 2014-10-01
• 公開（公告）號: CN105793822B
• 公開（公告）日: 2020-03-20
• 發(fā)明（設計）人: 亞歷山大·古爾科夫·巴利科夫;馬里安·德沃爾斯基;趙永剛
• 申請（專利權(quán)）人: 谷歌有限責任公司
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 中原信達知識產(chǎn)權(quán)代理有限責任公司 11219
• 代理人: 周亞榮;安翔

一種方法，所述方法包括接收對數(shù)據(jù)流執(zhí)行混洗操作的請求，所述請求包括初始鍵范圍的集合：生成混洗器配置，所述混洗器配置將來自混洗器的集合的混洗器指派至所述初始鍵范圍中的每一個；啟動所述混洗器的集合以對所述數(shù)據(jù)流執(zhí)行所述混洗操作；分析元數(shù)據(jù)統(tǒng)計以確定混洗器配置更新事件是否發(fā)生，所述元數(shù)據(jù)統(tǒng)計在所述混洗操作期間由所述混洗器的集合產(chǎn)生并且指示所述混洗器的集合中的每個混洗器的負荷統(tǒng)計；以及在所述混洗器配置更新事件發(fā)生之后并在所述混洗操作期間，至少部分基于所述元數(shù)據(jù)統(tǒng)計更改所述混洗器配置以產(chǎn)生混洗器至鍵范圍的指派，混洗器至鍵范圍的所述指派不同于混洗器至所述初始鍵范圍的指派。

技術領域

本說明書涉及分布式數(shù)據(jù)處理系統(tǒng)中的混洗操作。

背景技術

混洗操作是分布式數(shù)據(jù)處理系統(tǒng)中的中間步驟，其中寫入器產(chǎn)生的數(shù)據(jù)通過鍵數(shù)據(jù)被聚組用于通過讀取器消耗。利用混洗操作的分布式數(shù)據(jù)處理算法的一個示例是映射化簡算法。寫入器在映射階段被實現(xiàn)，在所述映射階段期間并行任務被創(chuàng)建以對數(shù)據(jù)操作從而生成中間結(jié)果。在混洗階段中，映射階段的部分計算結(jié)果被布置用于通過實現(xiàn)化簡操作的讀取器訪問。在化簡階段期間，每個讀取器執(zhí)行聚合了映射階段生成的數(shù)據(jù)的化簡任務。其他分布式數(shù)據(jù)處理算法也通過混洗操作混洗數(shù)據(jù)。

混洗操作包含根據(jù)包括在記錄中的鍵對記錄的流聚組。鍵可以是字母數(shù)字串或數(shù)字標識符。記錄可被混洗寫入器的集合以隨機順序呈現(xiàn)至混洗操作?；煜雌鹘M件的集合可接收記錄并根據(jù)它們包括的鍵對它們聚組?；煜雌鹘M件可以接著將現(xiàn)在通過鍵被聚組的記錄提供至混洗讀取器的集合。

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

本申請的主題涉及，當混洗操作激活時，諸如通過改變鍵范圍分配來重新配置混洗操作。本申請的主題還涉及在持久儲存器中存儲混洗操作的結(jié)果用于以后消耗。

一般地，本說明書中所描述的主題的一個創(chuàng)新的方面可以被體現(xiàn)在包括以下動作的方法中：響應于接收到對數(shù)據(jù)流執(zhí)行混洗操作的請求，所述混洗操作是通過鍵對所述數(shù)據(jù)流中設鍵的記錄進行聚組的操作，所述請求包括初始鍵范圍的集合，每個初始鍵范圍對應于所述數(shù)據(jù)流的部分；生成混洗器配置，所述混洗器配置將來自混洗器的集合的混洗器指派至所述初始鍵范圍中的每一個，每個混洗器被配置為從一個或多個寫入器接收與所指派的鍵范圍相關聯(lián)的數(shù)據(jù)流的部分，并且將所述數(shù)據(jù)流的所述部分提供至一個或多個讀取器；啟動所述混洗器的集合以對所述數(shù)據(jù)流執(zhí)行所述混洗操作；分析元數(shù)據(jù)統(tǒng)計以確定混洗器配置更新事件是否發(fā)生，所述元數(shù)據(jù)統(tǒng)計在所述混洗操作期間由所述混洗器的集合產(chǎn)生并且指示了所述混洗器的集合中的每個混洗器的負荷統(tǒng)計；以及在所述混洗器配置更新事件發(fā)生之后并在所述混洗操作期間，至少部分基于所述元數(shù)據(jù)統(tǒng)計更改所述混洗器配置以產(chǎn)生混洗器至鍵范圍的指派，混洗器至鍵范圍的指派不同于混洗器至所述初始鍵范圍的指派。

這方面的其他實施例包括被配置為執(zhí)行被編碼在計算機儲存器設備上的所述方法的動作的對應的系統(tǒng)、裝置和計算機程序。

通過在操作正在運行時重新配置混洗操作，可以獲得更好的效率和表現(xiàn)。此外，遠離初始鍵范圍建議而重新配置的能力在處理沒有限制的數(shù)據(jù)集或未知大小的數(shù)據(jù)集時尤其有用，因為最優(yōu)鍵范圍在混洗操作開始時可能無法辨別。因此，通過允許這樣的重新配置，可以對可能無限的記錄流有效地執(zhí)行混洗操作。

通過在持久儲存器中存儲混洗操作結(jié)果，混洗操作可被重復而不需要重復提供數(shù)據(jù)至混洗器的步驟。這在大數(shù)據(jù)集需要以不同方式(例如，被排序、碎片)被不同消耗者消耗的情況下會特別有用。持久性也允許數(shù)據(jù)生產(chǎn)者從消耗者被解耦合。生產(chǎn)者可以產(chǎn)生數(shù)據(jù)而不管數(shù)據(jù)將在何時被消耗。當數(shù)據(jù)以適合的格式被保持用于以后被混洗消耗者消耗時，整個產(chǎn)生階段可以完成并且生產(chǎn)者轉(zhuǎn)去做其他工作。持久數(shù)據(jù)集還可以被進一步重組(例如，被排序、被合并)以減少已攤銷的處理和儲存成本。此外，如描述的一樣保持數(shù)據(jù)可允許相比于先前方法有所提高的容錯性，例如，通過如果操作混洗器故障則允許混洗操作從故障點重新開始。