GES图计算引擎HyG揭秘之图切分

π 发表于 2022/06/23 16:28:51 2022/06/23
【摘要】 对于超大规模图数据,点、边数量可以达到百亿甚至千亿、万亿,存储如此规模的图数据往往需要几百GB甚至几TB的存储空间,为了高效的图计算分析,往往需要将图数据存储于内存中,因此,对于超大规模的图数据,是没有办法将整张图存放在单机之上的,这就需要图计算框架对原始图进行切分,将一张大图切割成多个子图,然后将这些子图运行于一个集群之上,进而完成各种各样的图分析、图查询任务。GES大规模图计算引擎HyG通过实

摘要:

对于超大规模图数据,点、边数量可以达到百亿甚至千亿、万亿,存储如此规模的图数据往往需要几百GB甚至几TB的存储空间,为了高效的图计算分析,往往需要将图数据存储于内存中,因此,对于超大规模的图数据,是没有办法将整张图存放在单机之上的,这就需要图计算框架对原始图进行切分,将一张大图切割成多个子图,然后将这些子图运行于一个集群之上,进而完成各种各样的图分析、图查询任务。GES大规模图计算引擎HyG通过实现不同的点边分区算法,可以灵活地供用户选择多种多样的切分策略,进而达到更好的运算性能。

 

一个好的图切分算法对于图计算引擎性能至关重要:

  • 合理的切分可以使每个子图负载更加均衡,进而加快每轮的迭代速度
  • 合理的切分可以大大降低子图之间的通信开销

 

图切分算法主要有两大分支:

  • 离线切分 :需要加载完整的图数据,根据图整体的拓扑结构,进行多次迭代、聚类等方法,来获得高质量的分区边界
  • 流式切分:在对点/边的划分过程中,被划分对象数据流式地传输到图划分模块中,当前对象的分区策略至多依赖于之前对象的分区状态,而与后续流式传输来的对象的信息无关

 

流式的图分区算法的优点

1) 内存占用小。流式的图分区算法每个分区只需要加载部分的图数据即可进行划分,各分区之间只需要较小的通讯代价即可完成对分区状态的同步。而离线的图分区算法需要加载完整的图数据,并且例如XtraPuplMetis对整个图进行多次迭代,细化其分区,产生大量内存开销。

2) 分图效率高。流式的图分区算法中,对象流式地传入,即刻可以决定分区结果,对每个分区对象只需要遍历一次。并且支持多线程多个对象并行流式输入、分区,分区完成之后线程间同步分区状态,实现高效率的分区。而类似XtraPuplMetis的离线分区算法,由于需要多次迭代,对一个对象的分区需要对遍历不止一次,并且由于其分区算法对图整体拓扑结构的依赖性高,导致其可开发的并行度不高,分图效率不如流式的图分区算法。

3) 分图质量相当,部分情况下更优。在对多种图计算算法和多个数据集的测试中,图计算推理时间开销各有优劣,但流式图分区中总有数个具体分区算法,其在图计算推理的时间开销优于离线图分区算法XtraPupl,用户使用流式图分区算法具有更高的灵活度,可以针对不同的算法、数据集、分区数量,选择合适的具体分区算法,获得更好的图计算推理性能。

我们的HyG图计算引擎就是采用流式切分算法进行图切分。

 

HyG图计算引擎如何实现图切分?

图切分最核心的就是两个步骤。1、如何将点分配到各个主机;2、如何将边分配到各个主机。HyG对这两个步骤进行了抽象,定义了以下两个方法:

getMaster(nodeID) //给定一个点ID,返回这个点需要分配给哪个主机

getEdgeOwner(edgeSrcID, edgeDstID) // 给定一条边,返回这个边需要分配给哪个主机

一旦给出了以上两个函数,HyG的切分器就可以完成大图的切分。业界和学术界有大量的图切分算法,本质的区别就是getMaster和getEdgeOwner的实现不同,几乎所有的图切分算法都可以重写成这种模式。下面我们举一个出边切(OEC)的例子,看看HyG是怎么通过重定义getMaster和getEdgeOwner两个函数完成图切分的。

                               1.png                                 2.png

                                                          图1                                                                              图2

首先我们定义

GetMaster(nodeID)
    return floor(nodeID / hostNum)

这个函数很简单,就是点ID除以主机数量然后向下取整,图1我们有4个顶点,假设我们有4个主机,这样的话就为每个主机分配了一个点。

然后我们定义

GetEdgeOwner(edgeSrcID, edgeDstID)
    return masterOf(edgeSrcID)

这个函数也很简单,就是获取边的源顶点所在的主机ID,因为GetMaster已经完成了点的划分,因此这一步直接查询就可以得到结果。这样的话切分器就明确了这条边应该分配给哪个主机。

在完成GetMaster和GetEdgeOwner的定义后,HyG就可以将原始的图切分成4个子图,如图3所示。

                                                 3.png

                                                                                     图3

上面提到的切分示例是最简单的一种切分方法,在现实应用场景下,往往需要更为复杂的切分策略才能达到有效、均衡的切分效果。

HyG实现的点分区算法主要分为两类:ContiguousEBFennelEB

1) ContiguousEB直接将点分配给在读图阶段读取该点的分区,不进行额外的分区操作。

2) FennelEB在分区时会维护当前的分区状态,流式读取到顶点后,会根据各分区的已分配数量、该顶点在各分区的局部性,为每个分区生成一个评分,将顶点分配到评分最高的分区中。

HyG实现的边分区算法主要分为三类:SourceHybridCartesian

1) Source直接将边分配给其对应顶点所在的分区,如果是以出边划分的算法,即将其划分给源顶点所在的分区,如果是以入边划分的算法,即将其划分给目标顶点所在的分区。

2) Hybrid设定一个阈值threshold,顶点度数低于阈值的称为低度顶点,高于阈值的视为高度顶点。这种边分区算法保证了低度顶点的局部性,同时将高度顶点分散开来,避免了少数高度顶点带来的负载不均衡问题。

3) Cartesian将邻接矩阵切分为数个二维网格,每个网格对应一个分区,将边按照网格划分,这种分区算法保留了一定的局部性,同时可以获得更好的负载均衡。

HyG通过实现不同的点分区算法(GetMaster)和不同的边分区算法(GetEdgeOwner),可以实现多种多样的切分策略,非常的灵活好用,用户可以根据自己图数据的特点选择不同的切分策略,进而达到更好的运算性能。

 

HyG已上线至华为云GES服务,欢迎大家上手体验~

4.png

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。