(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210330043.0 (22)申请日 2022.03.31 (71)申请人 深圳普适智能有限公司 地址 518101 广东省深圳市宝安区新 安街 道龙井社区建安一路9号恒明珠金融 大厦东座304 (72)发明人 刘元弘　王畅　 (74)专利代理 机构 北京集佳知识产权代理有限 公司 11227 专利代理师 韩丽波 (51)Int.Cl. G06F 16/36(2019.01) G06F 9/50(2006.01) (54)发明名称 一种分布式集群下图计算的负载均衡方法、 系统及装置 (57)摘要 本发明公开了一种分布式集群下图计算的 负载均衡方法、 系统、 装置及计算机可读存储介 质， 根据图中各点对应的点边信息量设置度数阈 值； 从图的当前计算激活的点中确定度数大于度 数阈值的目标点； 将目标点膨胀成多个与目标点 携带相同信息的膨胀点， 并将原本与目标点关联 的边分散关联至多个膨胀点， 以将不同膨胀点对 应的点边信息一一分发至分布式集群的不同任 务执行器中处理。 可见， 本申请对图中度数较大 的点对应的点边信息进行数据打散处理， 使 得原 本应分发至一个任务执行器的数据可以分发至 分布式集群的多个任务执行器中处理， 以平衡分 布式集群中不同任务执行器 之间的计算负载， 提 高图计算的效率。 权利要求书2页 说明书8页 附图1页 CN 114661919 A 2022.06.24 CN 114661919 A 1.一种分布式集群下图计算的负载均衡方法， 其特 征在于， 包括： 根据图中各点对应的点 边信息量设置度数阈值； 从所述图的当前计算激活的点中确定度数 大于所述度数阈值的目标点； 将所述目标点膨胀成多个与 所述目标点携带相同信 息的膨胀点， 并将原本与 所述目标 点关联的边分散关联至多个所述膨胀点， 以将不同所述膨胀点对应的点边信息一一分发至 分布式集群的不同任务执 行器中处 理。 2.如权利要求1所述的分布式集群下图计算的负载均衡方法， 其特征在于， 根据图中各 点对应的点 边信息量设置度数阈值， 包括： 获取图中各点对应的点边信 息， 并估算所述图中所有点对应的点边信 息所占的第 一内 存量的最大值； 根据预设的点边信 息所占的内存量与度数阈值的对应关系， 确定与 所述第一内存量的 最大值对应的度数阈值； 其中， 越大的内存量对应的度数阈值越小。 3.如权利要求1所述的分布式集群下图计算的负载均衡方法， 其特征在于， 将所述目标 点膨胀成多个与所述目标点携带相同信息的膨胀点， 包括： 根据预设膨胀关系式n＝INT(degree/threshold)+1确定所述目标点需膨胀的膨胀点 数量n， 以将所述目标点膨胀成n个与所述目标点携带相同信息的膨胀点； 其中， INT表示取 整舍去小数位的函数； degre e表示所述目标点的度数； thresho ld表示所述度数阈值。 4.如权利要求3所述的分布式集群下图计算的负载均衡方法， 其特征在于， 将所述目标 点膨胀成n个与所述目标点携带相同信息的膨胀点， 包括： 获取用于描述所述目标点的点键值对描述信息(Va,InfoA)； 其中， Va表示所述目标点 的标识符； I nfoA表示所述目标点携带的信息； 将所述点键值对描述信息(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 对应的所有点边信息均分发至分布式集群的同一任务执行器中处理； 其中， 不同膨胀点对 应的点边信息被分发至所述分布式集群的不同任务执 行器中处 理。权　利　要　求　书 1/2 页 2 CN 114661919 A 27.如权利要求1 ‑6任一项所述的分布式集群下图计算的负载均衡方法， 其特征在于， 所 述分布式集群包括主任务执 行器和从任务执 行器； 所述分布式集群下图计算的负载均衡方法还 包括： 获取所述图当前对应的所有待分发的点边信 息， 并估算所有待分发的点边信 息所占的 第二内存量； 若所述主任务执行器的内存可用量大于所述第 二内存量， 则将所有待分发的点边信 息 全部拉取到所述主任务执 行器， 以由所述主任务执 行器进行点 边信息的分发。 8.一种分布式集群下图计算的负载均衡系统， 其特 征在于， 包括： 阈值设置模块， 用于根据图中各点对应的点 边信息量设置度数阈值； 点确定模块， 用于从所述图的当前计算激活 的点中确定度 数大于所述度 数阈值的目标 点； 负载均衡模块， 用于将所述目标点膨胀成多个与所述目标点携带相同信息的膨胀点， 并将原本与所述目标点关联的边分散关联至多个所述膨胀点， 以将不同所述膨胀点对应的 点边信息一 一分发至分布式集群的不同任务执 行器中处 理。 9.一种分布式集群下图计算的负载均衡装置， 其特 征在于， 包括： 存储器， 用于存 储计算机程序； 处理器， 用于在执行所述计算机程序时实现如权利要求1 ‑7任一项所述的分布式集群 下图计算的负载均衡方法的步骤。 10.一种计算机可读存储介质， 其特征在于， 所述计算机可读存储介质上存储有计算机 程序， 所述计算机程序被处理器执行时实现如权利要求1 ‑7任一项所述的分布式集群下图 计算的负载均衡方法的步骤。权　利　要　求　书 2/2 页 3 CN 114661919 A 3