实时性提升4000倍？图数据库在腾讯的应用实践！

2021 年 12 月 31 日 专知

分享嘉宾：李晓森腾讯大数据专家工程师

编辑整理：王彦磊

出品平台：DataFunTalk

导读：现实中的人和人、人和物、物和物构成了各种复杂多样的关系，这些关系可以通过图进行建模和表达：比如转账网络、社交网络等。对图（图模型）的理解和应用尤为重要。今天分享的主题整体比较发散，除了图数据库的相关内容，还会分享一些我们在其他方向的思考，包括图的技术栈、图的智能平台，以及图数据库与图智能平台的关系，最后分享下图数据库在腾讯内部业务场景中的应用。主要内容：

像图一样思考
图Young！图Simple？
图数据库与图智能平台
图数据库应用

像图一样思考

除了图数据库，我们还自研了图计算框架、图可视化引擎和图分析组件等，也和公司内的Flink（Oceanus）产品进行打通，目的是完善图流融合的一些功能。

1. 图论

图论在1738年由欧拉开创，解决柯尼斯堡七桥问题，用图将不同区域建模成点，把桥建模成边，通过图解决了实际问题并发展出了图论。

目前对图的分类一般为属性图模型和RDF图模型。我们自研的EasyGraph图数据库、Angel-Graph图计算框架以及Graph-Idex图可视化平台是基于有向属性图模型实现的。其中顶点用来表示实体或实例，如人、设备、抽象的IP等，边用来表示顶点之间的关联关系，最终通过图平台组件完成图数据的建模、存储、计算、可视化分析和应用。

2. 转账场景

在使用图数据库、图计算、图可视化等图技术前，需要先从业务角度定义和思考构图问题。比如在转账支付网络场景，首先识别图中哪些是实体（顶点），如用户的ID、银行卡、设备、手机号、证件号、WIFI、地理信息等都可以看作顶点，顶点之间的关系则可以通过用户行为序列或顶点间的依赖关系生成，这些关系包括用户转账信息、用户在设备上面的登录行为以及绑定手机号/银行卡等操作。通过对业务场景的理解建模构造整体图模型网络，进一步识别出图中的同构或异构关系。如UID与UID之间的转账同构网络，UID和设备之间的异构二部图。

准确详尽的构图建模有利于用图计算、图查询、图可视化、图分析等技术挖掘图数据的价值。

3. 万物互联

如今是万物互联的时代，早期大数据时代不只是数据量的增长，数据之间的联系也更加复杂多样化，如社交APP中关注、点赞、评论等行为构成的社交网络，移动通信的短信、电话构成的通信网络，移动支付场景如微信支付、红包、面对面的支付、扫码等构成了支付网络，电商场景的浏览、购买、收藏、评论行为构成了用户和物品之间的购物网络。

万物互联的时代使得图无所不在，因此对图数据的挖掘尤为重要，以往传统的单点分析技术逐渐难以准确或完整的刻划个体，针对图数据的关联性计算和查询分析成为常态需求。

4. 以图治图

值得思考的是如何通过图技术解决图的应用问题？作为一种特殊的数据结构，《算法导论》的第六部分的第21-25章介绍了图的基础知识，如图的存储用到了邻接表（链表）、邻接矩阵，以及图的遍历，最大流等算法问题。

不同格式的数据需要的存储组件不同，HDFS存储非结构化数据，Hive存储有字段清晰的结构化数据。图既然也是一种特殊的数据结构，也需要高效的存储系统— —Graph Database。图数据库在存储图数据时充分考虑到数据查询遍历时的局部性问题，解决了一跳扩展甚至子图级的数据邻近存储。

传统的MapReduce任务假设数据之间的联系较弱，使得数据的划分和并行计算较为容易。但是对图而言，数据之间的耦合性较强，往往需要先对图进行划分，不同的划分方式对计算效率影响较大。MapReduce的粗粒度划分会导致负载计算不均衡等问题，最终导致图的计算效率较低，所以2010年Google提出Pregel分布式图计算框架，并提出了以顶点为中心的编程思想：Think like a vertex 像顶点一样思考，每个点都可以接收邻居发送的信息，并结合自身的属性和更新函数进行更新操作，并把更新后的信息沿着邻边发送给邻居，通过不断迭代完成整个计算过程。在做计算时站在顶点的角度思考整个图计算过程，可以灵活表达多种图算法，提升开发效率。

图可视化则是天然地把点边构成的网络呈现出来，用顶点大小、边的粗细表达权重信息，通过颜色或形状表达不同点边类型，这种视觉捕获的信息不仅直观，而且更容易被理解。

图Young！图Simple？

回顾图技术的发展应用历程，图是不是一门比较年轻的技术呢？图技术是不是很简单？

1. 发展历程

① 图理论

回答是不是年轻的问题，可以从图理论的发展历程来看。

自1738年欧拉提出图论至今已有200多年的历史，中间也有一些图算法如旅行者背包等问题，但并没有对工业界造成很大的影响，偏理论研究性质的算法一般短期难以看到效果。

但在1998年，PageRank算法的提出以及对Google搜索引擎的影响使得人们意识到图算法的重要性。特别是最近几年，如2014年、2015年、2016年出现图的表示学习算法，DeepWalk借鉴Random Walk的思想学习图的Embedding，再到GCN、Graphsage的出现，将卷积思想扩展到图领域，促进了图神经网络方向的研究，GNN也是目前图最火热的研究方向。

② 图计算框架

从图计算框架而言，自2010年Pregel发表后，分布式图计算系统成为工业界主流研究方向，一些知名的图计算框架如2012年PowerGraph，2014年Spark的GraphX以及2016年的Gemini等。腾讯在2019年也实现了Angel-Graph和Plato。2019年Facebook也开源了Pytorch-BigGraph，它是基于Pytorch实现的图神经网络框架。从图计算框架的发展历程来看只有十几年的历史。

③ 图数据库

2007年Neo4j的出现发展处了图数据库方向，到2012年的Titian、TigerGraph以及后面的JanusGraph等图数据库。

纵观图算法理论、图计算框架和图数据库系统的发展历程，图技术既年轻又充满活力。

2. 发展趋势

在2019和2021年Gartner数据和分析技术趋势预测中，都将图作为十大技术趋势之一（参考下图），工业界对图的应用以及学术界对图的研究也成为趋势，并在实际应用场景落地较多。而图数据库管理系统在DBEngine Ranking也扶摇直上，成为发展趋势最快的方向。

3. 需求与挑战

从腾讯内部业务的需求和痛点进一步说明，腾讯在QQ、微信、广告、支付、游戏、视频、音乐等场景有着丰富多样的图数据，某些业务场景单个网络可达十亿级顶点、千亿级边，如此庞大的图数据蕴藏着价值，也给图的存储、计算、分析提出了更高的的要求，特别是超级顶点的存在成为存储和计算的的共同难题，也是亟需解决的问题。为了提升组件的易用性，需要和内部大数据生态打通，如TDW、HDFS、Spark、Flink、调度系统等，最终围绕图数据库、图计算框架、图可视化平台组件等构建图智能平台。

图数据库与图智能平台

目前图智能平台引擎包括三部分：图计算框架、图数据库系统和图可视化引擎。外部对接了流计算引擎，腾讯内部使用Oceanus把流计算与图计算、图查询进行融合。

图智能平台的定位是在解决百亿顶点、万亿边的图存储，包括图库管理、权限管理、图查询分析等功能，以便大幅提升业务的查询使用效率。以及为了微信支付、游戏、广告的计算需求提供高性能的图计算能力。解决图数据之上的TP和AP问题。

1. 图的三驾马车

① 图计算

图的三驾马车中我们在2019年自研了图计算框架Angel-Graph，解决了传统图挖掘、图表示学习和图神经网络的高性能计算问题，包括经典的PageRank ，Closeness等算法，以及图表示学习Deepwalk、Node2Vec的Embeeding算法，以及GNN算法，将三大类图计算问题融合成一个框架 —— “三位一体”。目前已开源在Github上的Angel-ML项目中，也是业界第一个比较全面覆盖图计算问题的开源图计算框架，我们的研究成果也发表在ICDE 2020顶会上，感兴趣的同学可以看下这篇论文。

在实现图计算框架时首先考虑图的分布式切分问题。因为百亿级甚至千亿级的图，单机是难以存下的。目前Angel-Graph基于参数服务器的架构，将顶点信息存储在全内存的ps上，在图计算或图算法如PageRank的迭代计算过程中，边结构是不变的，数据的频繁更新发生在顶点上。Graphx低效的原因之一是RDD的immutable特性，RDD的每次更新需要生成新的RDD，因此占用了大量的内存开销。为了保障在受限共享资源环境下图计算任务的稳定运行，Angel-Graph引入了batch计算的逻辑，业务侧可以根据资源配置调整计算速度，保障资源不足的情况下仍能稳定运行。

在百亿级的图数据上对比Graphx 和Angel-Graph的性能，Angel仅用1/3的资源，性能可以达到Graphx的10倍以上。因为同样融合了spark生态，Angel-Graph也可以像Graphx一样保障图计算的ETL能力，即图数据读取、预处理和结果保存可以在一个图计算任务中，从而避免了中间数据的中断、落盘和二次加载。

② 图存储

图数据库一般解决对图数据的查询需求，以及对重新结果的子图分析。图是一种非欧空间的数据，在社交网络场景中往往符合小世界模型，如六度空间理论。所以比较远的查询如3跳以上查询到的数据较多，难以高并发执行。一般对图数据库的的应用主要为1/2阶查询，以及更多跳的带条件遍历，通过条件约束查询到的数据量。图数据库也可以和图计算、图可视化引擎融合打通，解决全量的AP分析，以及查询结果的的可视化。

2. EasyGraph

目前EasyGraph采用了存储计算分离架构，查询层既支持无状态的TP查询需求，也支持有状态的AP分析，比如刚才提到的3跳以上的查询计算问题，单点的server的计算性能较差，难以满足业务需求，因此可以采用分布式的server来解决。

3. 图的可视化

图可视化通过展示实体、关系帮助用户获取对查询结果数据的洞悉能力，目的是为了使得图数据可看、可理解和可分析。图可视化系统已广泛应用在知识图谱、金融风控、网络安全、调度依赖等领域。如金融支付场景的团伙欺诈判定，图可视化可以对事中或是事后进行分析，从而判断模型检测结果的正确性，或者观察欺诈团伙形成的过程，从而对业务策略或规则进行修正。

可视化一般支持搜索、过滤、渲染、布局、计算等功能，也提供点级、边级、子图级不同视角的转化。在实际场景中百万级以上的图在浏览器端已经难以渲染，坐标计算等比较重的计算为成为瓶颈，可以把前端计算的逻辑下推到后端执行，这也是我们在做的一些优化。

4. 图的应用概览

总结而言，图的普遍应用需求便是图智能平台需要解决的问题，技术层面可以归纳为存储、计算(离线、在线)、可视化以及易用的开发工具等。场景的应用如可视化分析、统计画像、模式识别、图学习、知识图谱、查询分析等。

图数据库应用——以图治图

最后回归正题，分享下图数据库的应用，这也是今天的主题。首先介绍图数据库在整个腾讯业务中的应用。

1. 统一调度系统

作为平台团队，最能体会到图数据的价值，特别是对调度系统而言。调度系统相当于平台的管家，负责数据的入库、出库、计算、挖掘、分析等，每天有大概有1050w的任务被调度，300W+的SQL查询，以及300P+的数据搬迁。在这样高效的调度系统中任务并非独立运行，而是存在各种依赖关系，而且有很多的任务不一定是临时创建和临时去调用的，很多任务被例行化执行。

以右边的图（参下图）为例，假如C这种天级任务依赖于A、B这两个小时级任务，当A，B两个任务1-24小时的任务执行成功之后才会触发C任务的执行，它本身有一个静态依赖图和动态执行图。我们将任务依赖关系存储到图数据库，并对多阶依赖关系进行实时查询，从而解决高并发的依赖判断问题，将图查询的依赖判断和事件触发机制进行有效结合，对统一调度系统的实时性进行优化。

相比采用MySQL存储依赖关系的解决方案，图数据库使得之前两分钟轮训调度耗时下降到了30毫秒，整个调度实时性提升了4000倍，在没有用图数据库之前，我们看到在整点的时候这个波峰效应非常明显，采用图数据库后波峰效应大幅度降低，任务调度的实时性也得到了保障。

2. 金融支付

图可视化引擎可以应用在资金链路分析中。左图大概一千多个点，两千多条边，这是一个完整的图。为了更方便对局部信息可视化分析，我们做了很多优化，一方面能对点、边的属性进行颜色、大小的调整，另外也提供了一些聚合的算法，比如通过一些社区发现算法或者业务给定聚合规则对点或局部的子图进行聚合，聚合后图中顶点自然包含了很多统计信息。也可以点击展开分析某个聚合点，这样帮助用户清晰的判断局部交易情况。

3. 欺诈团伙判断

欺诈团伙的判定用到了图智能平台多个组件的功能。在做欺诈团伙检测时，首先需要图计算框架运行Louvain算法，为了满足业务需求，我们自研了带有先验知识的PKLouvain算法（Prior Knowledge Louvain）。因为在安全风控场景中图算法有很强的业务逻辑，这些业务规则也可以用在社团挖掘算法中。比如通过用户登录的ID，wifi等信息去构图，业务侧事先知道哪些点肯定属于一个社团，哪些点肯定不在同个社团结构中。通过将这些信息构造正负边关系输入到Louvain算法中，然后控制社团的合并逻辑，相比传统的Louvain算法，PKLouvain算法在准确率上有11%~22%的提升。

PKLouvain算法的计算结果也可以存储在图数据库中，然后根据用户id或社区id查询完整的社团结果，通过图可视化引擎还原和展示整个的社团结构。业务同学根据可视化结果进行业务判定，判断查询到的社团是否为欺诈团伙，这里面会涉及到许多的业务规则和对业务的理解。如果发现一个新型的欺诈团伙结构，也可以从里面提取出来一些新的规则或者策略，并将这些规则或策略加入图算法中，进一步的优化图计算的结果。

这种从图计算=>图数据库=>图可视化=>业务模型/策略/规则=>图计算=>…，整个过程形成了闭环，也用到了图智能平台的图计算框架、图数据库、图可视引擎。例如以赌博庄家为例，像传统关系型数据库做这种关联分析，需要写复杂的sql查询语句，并引入大量的表join操作，严重影响计算性能，对一个赌博庄家的两阶的判定需要17分钟才能做完，但是结合图数据库、图可视化可以轻松实现秒级的业务研判，比如右图的赌博庄家的二阶的关系，红色的点标识赌博用户，可以看到很多用户都是这种红色，那么这个顶点周围很大程度上存在赌博团伙。