[發明專利]分布式圖計算的方法、裝置、設備及存儲介質

在審

• 申請號: 202010219704.3
• 申請日: 2020-03-25
• 公開（公告）號: CN113448692A
• 公開（公告）日: 2021-09-28
• 發明（設計）人: 趙尚宇;陳哲嘉
• 申請（專利權）人: 杭州海康威視數字技術股份有限公司
• 主分類號: G06F9/46
• 分類號: G06F9/46;G06F9/48
• 代理公司: 北京三高永信知識產權代理有限責任公司 11138
• 代理人: 謝冬寒

本申請公開了一種分布式圖計算的方法、裝置、設備及存儲介質，屬于圖計算領域。該方法包括：確定所述目標任務的初始子任務；基于待執行的目標任務的各子任務之間的依賴關系，自初始子任務開始執行所述目標任務的各子任務；當所述目標任務的第一子任務執行完畢時，基于所述依賴關系，確定第一子任務下一步的第二子任務，確定第二子任務的輸入數據所存儲的第二設備，向第二設備發送任務繼續執行通知，其中，所述任務繼續執行通知中攜帶有第一子任務的輸出數據和第二子任務的標識。本申請通過向其他執行圖計算任務的設備發送需要執行任務的任務標識，能夠使任務實現計算本地化，從而不需要在網絡中傳輸大量的頂點數據，能夠提高分布式圖計算的效率。

技術領域

本申請涉及圖計算領域，特別涉及一種分布式圖計算的方法、裝置、設備及存儲介質。

背景技術

圖是用于表示對象之間關聯關系的一種抽象數據結構，使用頂點和邊進行描述：頂點表示對象，邊表示對象之間存在關聯。在一個圖中，可以包括多個頂點，每個頂點可以與多個頂點相關聯，其中任意兩個相關聯的頂點存在一個邊，這樣，可以形成一個網狀的圖數據結構。圖計算便是以圖作為數據模型來表達不同數據之間的問題，并解決數據之間的問題的一種計算。

在現有技術中，經常采用分布式圖計算來解決一些較為復雜的圖計算問題。進行分布式圖計算，首先需要將一個復雜的圖進行切分，分別存儲在不同的設備上，然后在每個設備上存儲有進行圖計算的方法，當設備執行圖計算方法時，當需要其他設備上存儲的頂點數據時，可以向其他設備發送獲取請求，收到獲取請求的設備可以將相應的頂點數據，送給到該設備中，供該設備繼續執行圖計算任務。

在實現本申請的過程中，發明人發現現有技術至少存在以下問題：

由于每個頂點可以與多個頂點相關聯，在進行分布式圖計算的過程中，隨著計算頂點的數量增加，存儲子圖的各個設備之間需要傳輸的頂點數據量可能呈指數上漲，容易造成傳輸數據的網絡擁堵，導致圖計算的效率低下。

發明內容

本申請實施例提供了一種分布式圖計算的方法、裝置、設備及存儲介質，能夠提高分布式圖計算的效率。所述技術方案如下：

一方面，提供了一種分布式圖計算的方法，所述方法應用于第一設備，包括：

確定所述目標任務的初始子任務；

基于待執行的目標任務的各子任務之間的依賴關系，自所述初始子任務開始執行所述目標任務的各子任務；

當所述目標任務的第一子任務執行完畢時，基于所述依賴關系，確定所述第一子任務下一步的第二子任務，確定所述第二子任務的輸入數據所存儲的第二設備，向所述第二設備發送任務繼續執行通知，其中，所述任務繼續執行通知中攜帶有所述第一子任務的輸出數據和所述第二子任務的標識。

可選的，所述基于待執行的目標任務的各子任務之間的依賴關系，確定所述目標任務的至少一個初始子任務之前，所述方法還包括：

對應所述目標任務的各子任務建立輸入緩存隊列和輸出緩存隊列，其中，所述輸出緩存隊列用于緩存所屬子任務的輸出數據，所述輸入緩存隊列用于緩存所屬子任務的上一步的子任務的輸出數據。

可選的，所述方法還包括：

當所述目標任務的第三子任務的輸出緩存隊列中緩存的輸出數據的數目達到預設的第一數目閾值時，停止執行所述第三子任務的處理；

當所述目標任務的第三子任務的輸出緩存隊列中緩存的輸出數據的數目小于預設的第一數目閾值時，重新開始執行所述第三子任務的處理。

可選的，所述方法還包括：