[發明專利]一種分布式集群下圖計算的負載均衡方法、系統及裝置

在審

• 申請號: 202210330043.0
• 申請日: 2022-03-31
• 公開（公告）號: CN114661919A
• 公開（公告）日: 2022-06-24
• 發明（設計）人: 劉元弘;王暢
• 申請（專利權）人: 深圳普適智能有限公司
• 主分類號: G06F16/36
• 分類號: G06F16/36;G06F9/50
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 韓麗波

1.一種分布式集群下圖計算的負載均衡方法，其特征在于，包括：

根據圖中各點對應的點邊信息量設置度數閾值；

從所述圖的當前計算激活的點中確定度數大于所述度數閾值的目標點；

將所述目標點膨脹成多個與所述目標點攜帶相同信息的膨脹點，并將原本與所述目標點關聯的邊分散關聯至多個所述膨脹點，以將不同所述膨脹點對應的點邊信息一一分發至分布式集群的不同任務執行器中處理。

2.如權利要求1所述的分布式集群下圖計算的負載均衡方法，其特征在于，根據圖中各點對應的點邊信息量設置度數閾值，包括：

獲取圖中各點對應的點邊信息，并估算所述圖中所有點對應的點邊信息所占的第一內存量的最大值；

根據預設的點邊信息所占的內存量與度數閾值的對應關系，確定與所述第一內存量的最大值對應的度數閾值；其中，越大的內存量對應的度數閾值越小。

3.如權利要求1所述的分布式集群下圖計算的負載均衡方法，其特征在于，將所述目標點膨脹成多個與所述目標點攜帶相同信息的膨脹點，包括：

根據預設膨脹關系式n＝INT(degree/threshold)+1確定所述目標點需膨脹的膨脹點數量n，以將所述目標點膨脹成n個與所述目標點攜帶相同信息的膨脹點；其中，INT表示取整舍去小數位的函數；degree表示所述目標點的度數；threshold表示所述度數閾值。

4.如權利要求3所述的分布式集群下圖計算的負載均衡方法，其特征在于，將所述目標點膨脹成n個與所述目標點攜帶相同信息的膨脹點，包括：

獲取用于描述所述目標點的點鍵值對描述信息(Va,InfoA)；其中，Va表示所述目標點的標識符；InfoA表示所述目標點攜帶的信息；

將所述點鍵值對描述信息(Va,InfoA)膨脹成n個點鍵值對描述信息，并將0至n-1作為后綴一一添加至n個所述點鍵值對描述信息中的鍵值(Va)上，且將添加后綴的n個點鍵值對描述信息一一作為用于描述n個所述膨脹點的點鍵值對描述信息；其中，用于描述第n個膨脹點的點鍵值對描述信息為(Va_n-1,InfoA)；Va_n-1表示第n個膨脹點的標識符。

5.如權利要求4所述的分布式集群下圖計算的負載均衡方法，其特征在于，將原本與所述目標點關聯的邊分散關聯至多個所述膨脹點，包括：

根據預設隨機數計算關系式r＝random[0,degree/threshold]計算所述目標點對應的隨機數范圍r＝[0,1……n-1]；

獲取用于描述所述目標點關聯的任一目標邊的邊鍵值對描述信息(Va,Eax)，并從所述隨機數范圍內取一個整數作為隨機數r，且將所述隨機數r作為后綴添加至所述邊鍵值對描述信息(Va,Eax)中的鍵值(Va)上，得到新鍵值對描述信息(Va_r,Eax)；其中，Eax表示所述目標邊的標識符；

根據所述新鍵值對描述信息(Va_r,Eax)確定所述目標邊Eax關聯至膨脹點Va_r。

6.如權利要求5所述的分布式集群下圖計算的負載均衡方法，其特征在于，將不同所述膨脹點對應的點邊信息一一分發至分布式集群的不同任務執行器中處理，包括：

獲取同一膨脹點Va_r對應的所有點邊信息(Va_r,(InfoA,Eax))，并將同一膨脹點Va_r對應的所有點邊信息均分發至分布式集群的同一任務執行器中處理；其中，不同膨脹點對應的點邊信息被分發至所述分布式集群的不同任務執行器中處理。

7.如權利要求1-6任一項所述的分布式集群下圖計算的負載均衡方法，其特征在于，所述分布式集群包括主任務執行器和從任務執行器；

所述分布式集群下圖計算的負載均衡方法還包括：

獲取所述圖當前對應的所有待分發的點邊信息，并估算所有待分發的點邊信息所占的第二內存量；

若所述主任務執行器的內存可用量大于所述第二內存量，則將所有待分發的點邊信息全部拉取到所述主任務執行器，以由所述主任務執行器進行點邊信息的分發。