日前，百度宣布将其自主研发的图数据库HugeGraph捐赠给Apache软件基金会，成为Apache孵化项目。成功孵化的HugeGraph有望成为Apache Software Foundation的全球首个顶级图形数据库项目。

图数据库已经成为目前最热门的数据库类别，但图数据库的发展还处于起步阶段，机遇与挑战并存。本文整理自DTCC 2021中国数据库技术大会嘉宾演讲，与嘉宾张艳分享。他是HugeGraph图计算的贡献者之一，前百度高级研发，目前在Zoom担任Java业务架构师。

本文包括以下几个部分：

1.什么是图计算，它能解决什么业务问题？

2.图形计算与传统计算的区别。为什么需要图形计算？

3.图计算行业现状，如何应对挑战？

4、如何应对挑战——自学图形计算

5.图算法发展及应用简介。

图是什么，它能解决什么业务问题？

什么是图形数据库？一般如果按照存储模型对数据库进行分类，可以分为文档模型、图模型、关系模型等。在文档模型中，文档之间通常没有关联，但图和文档模型是相反的，所有连接点都可能与任何其他节点关联。由于这一特点，图形数据库在图形模型处理中非常复杂。

根据目前主流的数据模型，图可以分为属性图和RDF图，通常所说的属性图基本都是属性图。属性图包含顶点、边，边和顶点都有一组KV属性，Label用作类型的唯一标识符。通常，顶点表示实体，而边表示实体之间的关系。图的任何顶点都可以相互关联，形成各种形状的数据结构，如线、树、环、叉和网。

HugeGragh是百度安全部门开发的图形数据库。2018年开源，采用APL 2.0开源协议。它迭代了几个版本。

HugeGragh根据应用场景分为OLTP和OLAP。OLTP主要做即时图查询，OLAP做离线分析。最近，针对我们遇到的一些问题，推出了一种新的图计算框架，该框架使用多轮迭代计算算法，并专注于大规模数据处理和计算稳定性。HugeGragh内置了很多算法。普通用户只需调用API就可以直接使用这些内置算法，简单易用。

1什么是图计算？

以图模型的形式对现实世界的问题进行建模，然后对问题进行分析，选择合适的算法进行求解，这些过程就是图计算。比如量化一个人在社交网络中的重要性，每个人可以用一个顶点来表示，人与人之间的关系用顶点之间的边来表示。图模型建立后，可以直观判断。如果这个人很重要，有很大概率会和很多人联系，每个人之间的联系路径很短。图计算对上述场景有一个接近中性的算法，每个顶点的得分都可以通过算法计算出来。分数越高，这个人的重要性越高。如果一个人和所有人都有直接关系，这个人肯定是最重要的人之一。总之，用图的模型来描述一些问题是简洁的，也是符合我们直觉的。

图2计算可以解决哪些业务问题？

一般来说，图计算可以解决的常见问题有网络安全、情报关系、智能营销、智能推荐、智能运维等。用图模型建模，可以发现特殊点，发现问题，用合适的算法解决问题。比如循环保证问题，图计算可以使用循环检测来识别是否存在循环保证问题。如果有循环，说明有循环保障。

图计算和传统计算的区别，为什么需要图计算？

图形计算与传统计算有以下主要区别：

处理的数据有很多

多轮迭代算法导致上下游任务无法分离，需要相互同步。

迭代中的中间结果量巨大，图算法的复杂度O(n * O(n *(degree depth))随着深度呈指数级增长。

针对多次迭代导致的上下游任务需要相互协作同步，不能分离的问题，我们在设计系统时会尽量增加并发的数量。随着图模型深度的增加，复杂度也会增加，一些项目的中间结果会爆炸。我们会在设计的时候尽量平衡的处理这些问题，打磨每一个细节来迎接这些挑战。

数字计算行业的现状，如何应对挑战？

理论上，为了支持大规模的图形计算，系统必须通过划分来扩展，这包括

图的切分。现在业界对于图的切分一般分为两种：一种是边切法，一种是点切法。

边切法是把某条边剪断，顶点和边存储在一起，每一个顶点反映在不同分区。优点是计算方便，缺点是数据分布不平衡。因为这种分区方式是把点和边放在一起，所以计算的时候只需要考虑单个节点就好，现在业界很多都是采用边切法的方式做切分。

点切法是将某个点进行划分，每个区都有不同的边，但顶点存在于多个节点、多个分区。优点是边分布均衡，缺点是由于每个存储都在不同地方，计算时需要汇总同步这些数据。

HugeGraph采用边切法。对于某些边特别多的超级点，有可能导致分区不均衡，我们针对超级点问题通过Partition调整来进行优化。比如如果某个Worker分布的超级点比较多，从而导致数据量比较大，这时可以根据负载情况将该Worker其它的Partition挪到其他Worker节点来平衡负载。总之也是通过数据进行分区，每个分区落在不同的Worker节点, 同时会根据数据量情况动态调整，以解决超级点问题。

前面说的多轮迭代图计算的框架就是DSP迭代计算，将算法分成不同的超级步，每个超级步需要迭代所有顶点，所有的顶点全部迭代之后会发消息(根据算法特征，根据一个初始值、计算值，需要发给相邻的节点，即发消息)，再开启下一轮迭代。即下一轮超级步依赖于上一轮计算结果。最终所有节点全部变成Inactive就说明迭代结束，输出结果。

目前现有的图计算框架会有一些问题，百亿以上的图难以计算，而且不太稳定，图随机访问多，邻接边幂律分布导致任务划分难以均衡负载;图算法复杂度高，消息与中间结果指数级增长;现有的一些框架超过十亿规模图时，计算性能差、OOM严重。

如何应对挑战 -- 自研图计算

HugeGraph自研图计算平台对相关问题进行了优化，比现有一些图计算框架实现了更好的性能，能够支撑迁移大规模图并行计算，高稳定性运行。

1 自研图计算架构

1.1图查询&图计算-整体架构

HugeGraph整体架构如上图，采用存储与计算分离架构。从底层到上层分别为存储层、计算层、接口层和生态组件。最上面是生态资源，现在已有的Loader组件可以将数据导入导出，此外也提供了一个Hubble平台，能够以可视化的方式查询和分析数据，图计算结果可以在Hubble上显示。

计算层OLAP和OLTP分开。OLAP是今天分享的主要框架，大体上分为Master和Worker两个角色。因为是分多轮迭代，所以需要一个协调者，以及信息流的汇总者，而Master角色就是来承担这些任务;Worker负责加载和输出，以及具体算法的执行。Worker数据加载采用分片方式，所以通过扩展Worker数量可以增加OLAP计算容量和并行计算能力。

存储层目前支持很多内置的存储组件，比如 HBase，Cassandra, MySQL, RocksDB 等等，同时框架也提供了插件化能力，如果用户有自己自研的存储组件，那么只需要实现对应的插件接口，就能够在存储层集成自定义的存储。目前HugeGraph的OLTP和OLAP底层采用同一套存储组件。

1.2 图计算架构-组件架构

上图为组件架构。用户可以根据自己的数据量和算法配置参数信息，通过API的方式提交任务，任务会通过driver模块启动k8s集群创建对应的图计算组件，执行对应的算法，输出结果。

1.3 图计算架构-技术架构

Master的角色主要是做流程调控，BSP同步，数据分片等，Worker角色主要是做对应数据的加载以及计算，Worker加载的数据都是通过Master分配，Worker和Master并行加载对应的数据，Master再进行数据汇总。对于Worker的消息发送，数据的存储都是采用自定义格式，通过设计自己的消息和数据存储结构，提高大数据存储量以及并行化处理能力，解决面临的挑战。

为了提升并行计算的能力，我们对底层做了很多优化。比如收发消息和迭代之间是并行的，不会等上一轮的计算结束才会收发消息。底层数据存储都是根据Partition分片的粒度分开，同时对所有数据进行排序，以减少随机访问。同时所有数据都是经过顺序访问进行计算，这样可以减少同步开销，更好的提高并行计算能力。

我们的主要目的是提升大数据量下的并行能力和稳定性，所以必然不会依赖于内存。比如对于超级点处理，并不会把所有数据都加载在内存中进行计算，而是加载一部分、计算一部分，所以稳定性可以得到保证。在迭代计算中发消息，收消息以及计算之间是并行，异步处理的，比如虽然下一轮迭代开始的时候所有消息需要保证接收完毕，但在每一轮迭代中，每一次收发消息都不会阻塞到计算逻辑。

在设计的时候我们极致的追求并行化，从存储到消息，再到上层的BSP框架的设计，包括请求、消息发送和计算，都充分考虑到并行方式，以充分利用计算机的处理能力。

2 图计算关键技术挑战及解决方案

图计算框架面临以下关键技术挑战：并行计算不均衡、消息传输量巨大、内存OOM严重、分布式节点部分失败。针对这些挑战HugeGraph采取了相应解决方法。

并行计算不均衡挑战。我们采用存算分离架构，使用 K8S 扩展，多 Worker并行计算。每个Worker负责部分Partition数据，按照点粒度分区。Worker 根据边总数量分配 Partition 个数，确保性能与负载均衡。Worker 内部采用多 Partition 多线程并行计算，同时计算与消息异步并行，充分利用了CPU多核能力。总之从底层到上层设计，各个组件之间的交互充分考虑到并行能力。

消息传输量巨大挑战。随着迭代速度增加，中间数据、中间结果和消息可能会大量增加。我们采取以下措施保证稳定性：发往远程的消息在本地 Combine 合并，超级点消息延迟到目标 Worker 分发。消息传输与计算并行，消息传输通过 Pipeline 方式提升吞吐。自定义协议与格式，分离数据面与控制面，利用压缩编码减少数据传输量。大规模消息利用基于磁盘/内存文件的堆排序/败者树进行动态多路归并，控制消息文件数量。

内存OOM严重挑战。不依赖内存容量来存储图计算的输入和中间结果，从根本上解决 OOM问题。内存-磁盘自适应，不依赖内存 Map，通过顺序 Join 内存/磁盘列存文件。重用内存对象，自分配内存方式管理内存，使用JVM堆外内存降低GC压力。通过Pipeline方式进行批式向量计算，平衡性能。

分布式节点部分失败问题。部分节点失败，将导致整个集群计算中断，造成时间、计算资源的极大浪费。要建立全链路负载反馈机制，尽可能避免部分节点因瞬时负载过高导致的失败。建立故障恢复机制，每一轮计算的中间结果快照到分布式文件系统上。部分节点失效时，无需从头计算，通过启动新的节点替代故障节点即可。

图算法开发与应用简介

关于HugeGraph算法开发，只需要通过引入API的依赖包，然后实现对应的框架接口，再将该包传到后台，同时根据计算的数据量、算法类型调整参数即可。计算的输入及输出格式均与算法本身解耦，采取HugeGraph标准的OLTP接口访问计算结果，不需要关注框架流程与算法的执行细节，仅关注算法逻辑本身，专注每个顶点收到的消息及其处理。总之HugeGraph内置了很多算法，同时如果用户需要自己开发一个算法，只需要关注算法本身的问题，具体数据怎么封装、怎么输出，这些都不需要关心，非常易于使用。