[發明專利]跨網絡執行元組圖程序的方法

有效

• 申請號: 201880035919.0
• 申請日: 2018-05-17
• 公開（公告）號: CN110945481B
• 公開（公告）日: 2023-08-08
• 發明（設計）人: 戈塔姆·坦比多雷;馬休·羅森克蘭茲;桑杰·格瑪沃特;斯爾詹·彼得羅維奇;伊凡·普斯瓦
• 申請（專利權）人: 谷歌有限責任公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/448
• 代理公司: 上海華誠知識產權代理有限公司 31300
• 代理人: 肖華

編程模型提供了一種用于在分布式架構中執行程序的方法。分布式架構的一個或多個第一分片執行一個或多個操作，并且將元組發送到至少一個第二分片，所述元組是流的一部分并且基于所述一個或多個操作。當流中的元組的發送完成時，一個或多個第一分片向至少一個第二分片發送令牌值。至少一個第二分片確定所述令牌值的總數是否與一個或多個第一分片的數目匹配，并且響應于確定令牌值的總數與一個或多個第一分片的數目匹配而采取第一動作。第一動作可以包括將流標記為完成和/或生成指示流完成的消息。

相關申請的交叉引用

本申請是2017年8月24日提交的美國專利申請No.15/685,022的延續申請，其公開內容通過引用并入本文。

技術領域

本申請涉及云計算，尤其涉及跨網絡執行元組圖程序的方法。

背景技術

云計算允許具有各種計算能力的用戶為了成本和計算效率而使用可配置資源的共享池來存儲和處理數據。用于云計算的當前編程模型包括MapReduce,Dryad和批量同步并行云處理。面向分布式計算的一個問題是性能。分布式計算中的性能與數據與計算單元的接近程度以及計算單元之間的數據傳輸成本有關。

發明內容

本公開描述了一種用于云計算的新的編程模型。新的編程模型可用于編寫分布式低延遲非批處理(non-batch)程序。應用在模型下構造程序，然后提交它以供執行。該程序由運算符的有向非循環圖組成。值的流沿著圖中的邊從一個運算符流到另一個運算符。通過流發送的每個值都是元組。相同程序中的不同運算符可以在不同的機器上運行。編程模型協調這些運算符在不同機器上的執行并將數據從一個運算符傳播到另一個運算符。

所述編程模型的一個方面提供了一種用于在分布式架構中執行程序的方法，包括：通過所述分布式架構的一個或多個第一分片執行一個或多個操作；從所述一個或多個第一分片向至少一個第二分片發送元組，所述元組是流的一部分并且基于所述一個或多個操作。當在所述流中的元組的發送完成時，從所述一個或多個第一分片中的每一個分片將令牌值到發送到至少一個第二分片。該方法還包括由第二分片確定令牌值的總數是否與一個或多個第一分片的數量相匹配，并且響應于確定令牌值的總數與一個或多個第一分片的數量相匹配而采取第一動作。第一動作可以包括將流標記為完成和/或生成指示流完成的消息。

所述至少一個第二分片可以是所述一個或多個第一分片中的一個的接收分片。該方法還可以包括：由所述一個或多個第一分片中的一個第一分片產生與所述一個或多個第一分片通信的接收分片的列表；以及由所述一個或多個第一分片中的一個將所述列表發送到控制器。另外，控制器可以跟蹤已經開始處理的所有接收分片，確定已經開始處理的一個或多個接收分片是否不存在于列表中，并且對于已經開始處理并且在列表中不存在的每個接收分片，代表一個或多個第一分片中的一個第一分片向接收分片發送令牌值。在一些示例中，該方法還可以包括：由控制器確定是否任何分片還沒有開始處理；由控制器確定還沒有開始處理的分片是否被程序的設計有意地跳過；以及由控制器代表還沒有開始處理的任何有意地跳過的分片向第二分片發送令牌值。

本發明的另一方面提供一種系統，其包括分布式計算環境中的一個或一個以上第一分片和所述分布式計算環境中的至少一個第二分片，所述至少一個第二分片遠離所述一個或一個以上第一分片。所述一個或多個第一分片被配置為執行一個或多個操作，將元組發送到至少一個第二分片，所述元組是流的一部分并且基于所述一個或多個操作，并且當在所述流中的元組的發送完成時將令牌值發送到所述至少一個第二分片。所述至少一個第二分片被配置為確定所述令牌值的總數是否與所述一個或多個第一分片的數目匹配，并且響應于確定所述令牌值的總數與所述一個或多個第一分片的數目匹配而采取第一動作。

該系統還可以包括與所述一個或多個第一分片，所述至少一個第二分片或所述控制器中的至少一個通信的客戶端設備?？蛻舳嗽O備可以被配置為構造圖，其中該圖的每個節點代表分片，且基于該圖來驗證該程序是否將在分布式架構上被準確地執行。客戶端設備還可以被配置成在執行程序時動態地建立圖的激活。