[發(fā)明專利]跨網(wǎng)絡(luò)執(zhí)行元組圖程序的方法

有效

• 申請?zhí)枺?/td>: 201880035919.0
• 申請日: 2018-05-17
• 公開（公告）號: CN110945481B
• 公開（公告）日: 2023-08-08
• 發(fā)明（設(shè)計(jì)）人: 戈塔姆·坦比多雷;馬休·羅森克蘭茲;桑杰·格瑪沃特;斯?fàn)栒病け说昧_維奇;伊凡·普斯瓦
• 申請（專利權(quán)）人: 谷歌有限責(zé)任公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/448
• 代理公司: 上海華誠知識產(chǎn)權(quán)代理有限公司 31300
• 代理人: 肖華

1.一種用于在分布式架構(gòu)中執(zhí)行程序的方法，其特征在于，包括：

由所述分布式架構(gòu)的一個(gè)或多個(gè)第一分片執(zhí)行一個(gè)或多個(gè)操作；

從所述一個(gè)或多個(gè)第一分片向至少一個(gè)第二分片發(fā)送元組，所述元組是流的一部分并且基于所述一個(gè)或多個(gè)操作；

當(dāng)所述流中的所述元組的發(fā)送完成時(shí)，從所述一個(gè)或多個(gè)第一分片中的每一個(gè)分片向所述至少一個(gè)第二分片發(fā)送令牌值；

由所述第二分片確定所述令牌值的總數(shù)是否與所述一個(gè)或多個(gè)第一分片的數(shù)量相匹配；和

響應(yīng)于確定所述令牌值的所述總數(shù)與所述一個(gè)或多個(gè)第一分片的所述數(shù)量相匹配，采取第一動作。

2.如權(quán)利要求1所述的方法，其特征在于，所述至少一個(gè)第二分片是所述一個(gè)或多個(gè)第一分片之一的接收分片，所述方法還包括：

由所述一個(gè)或多個(gè)第一分片中的一個(gè)第一分片生成所述一個(gè)或多個(gè)第一分片與之通信的所述接收分片的列表；和

由所述一個(gè)或多個(gè)第一分片中的所述一個(gè)第一分片將所述列表發(fā)送到控制器。

3.如權(quán)利要求2所述的方法，其特征在于，還包括：

由所述控制器跟蹤所有已開始處理的接收分片；

由所述控制器確定已經(jīng)開始處理的所述接收分片中的一個(gè)或多個(gè)接收分片是否不存在所述列表中；和

對于已經(jīng)開始處理并且不存在于所述列表中的每個(gè)接收分片，由所述控制器代表所述一個(gè)或多個(gè)第一分片中的所述一個(gè)第一分片向所述接收分片發(fā)送令牌值。

4.如權(quán)利要求1所述的方法，其特征在于，還包括：

由控制器確定是否有任何分片尚未開始處理；

由所述控制器確定所述程序的設(shè)計(jì)是否有意跳過尚未開始處理的所述分片；和

由所述控制器代表沒有開始處理的被有意跳過的任何分片，向所述第二分片發(fā)送令牌值。

5.如權(quán)利要求1所述的方法，其特征在于，采取所述第一動作包括將所述流標(biāo)記為完成或生成指示所述流完成的消息中的至少一個(gè)。

6.根據(jù)權(quán)利要求1所述的方法，其特征在于，還包括：

構(gòu)造圖，所述圖的每個(gè)節(jié)點(diǎn)代表分片；和

基于所述圖，驗(yàn)證所述程序是否將跨所述分布式架構(gòu)準(zhǔn)確地執(zhí)行。

7.如權(quán)利要求6所述的方法，其特征在于，還包括在執(zhí)行所述程序時(shí)，動態(tài)地構(gòu)建所述圖的激活。

8.如權(quán)利要求7所述的方法，其特征在于，還包括：

通過動態(tài)發(fā)送操作，向目的地圖的所有激活發(fā)送數(shù)據(jù)輸入流；

在所述動態(tài)發(fā)送操作，從控制器接收在檢測到所述目的地圖的附加激活時(shí)所接收到的新元組。

9.如權(quán)利要求6所述的方法，其特征在于，構(gòu)建所述圖包括構(gòu)建歸并圖。

10.如權(quán)利要求6所述的方法，其特征在于，所述圖是非唯一的。

11.如權(quán)利要求1所述的方法，其特征在于，執(zhí)行所述一個(gè)或多個(gè)操作是流水線數(shù)據(jù)處理流程的一部分。

12.一種用于在分布式計(jì)算環(huán)境中執(zhí)行程序的系統(tǒng)，其特征在于，包括：

分布式計(jì)算環(huán)境中的一個(gè)或多個(gè)第一分片；和

所述分布式計(jì)算環(huán)境中的至少一個(gè)第二分片，所述至少一個(gè)第二分片遠(yuǎn)離所述一個(gè)或多個(gè)第一分片；

其中所述一個(gè)或多個(gè)第一分片被配置為：

執(zhí)行一個(gè)或多個(gè)操作；

將元組發(fā)送到至少一個(gè)第二分片，所述元組是流的一部分并且基于所述一個(gè)或多個(gè)操作；

當(dāng)所述流中的所述元組的發(fā)送完成時(shí)，向所述至少一個(gè)第二分片發(fā)送令牌值；和

其中所述至少一個(gè)第二分片被配置為：

確定所述令牌值的總數(shù)是否與所述一個(gè)或多個(gè)第一分片的數(shù)量相匹配；和

響應(yīng)于確定所述令牌值的所述總數(shù)與所述一個(gè)或多個(gè)第一分片的所述數(shù)量相匹配，采取第一動作。