GraphScope的图计算之旅
内容介绍：
一、早期方案：面向特定任务的图计算系统
二、一站式图计算系统Graph Scope及其发展
三、持续迭代：向GraphScope Flex演进
四、GraphScope持续建设开源社区
本节课的主题是GraphScope的图计算之旅，由通义实验室系统研发总监徐静波分享。
图是现实世界中无处不在的一种数据结构，用点表示现实世界中的实体，用连接点与点之间的边表示现实世界中实体之间的关系。如网页链接图、生物结构图、社交网络图、知识图谱、用户交互图、交通网络等。对于网页链接图，每个点都表示一个网页，每条边都表示网页之间的一个超链接。对于社交网络，每个点都表示一个人，然后用边表示人与人之间的朋友关系。
各种各样的图中有各种各样的计算任务，即图计算。在互联网的场景下，图计算可以很多业务赋能。在阿里中，淘宝、天猫、飞猪、高德、菜鸟等各类业务部门可能都离不开图计算。我们可以在方方面面使用图计算解决现实中的问题，如图分析、图查询、图遍历、图神经网络等。也可以为各项服务赋能，如商品推荐、交易风控、广告、好友关系预测、路径规划等。
本节课将围绕阿里巴巴图计算技术栈的发展历程，分享阿里云在图计算中总结的经验及相应的设计。
阿里巴巴的图计算大致分为三个阶段。第一阶段是早期的图计算方案，大致从2013年到2020年。在这个过程中，诞生了很多图计算系统，如MaxGraph、GAIA、ODPSGraph、GRAPE、GraphLearn等。第二个阶段把前期的系统整合成了一站式的系统，即GraphScope，大致从2018年开始至今，其中最主要的两个系统是GraphScope和Vineyard。第三个阶段始于2024年，即GraphScope的2.0版本叫GraphScope Flex。这个过程中也围绕GraphScope诞生了其他周边系统，如GRIN、GraphAr、GART等。
一、早期方案：面向特定任务的图计算系统
十年前，互联网高速发展，随着业务的快速扩张，阿里巴巴内部的数据量迅速增长，很多业务数据能够自然建模为图，如电商的交易网络、路线导航、优酷中视频创作的评分等等。此时，从业务的角度出发，业务部门根据自身需求建立图计算方案。
1、图遍历
图遍历的英文名称是Graph Traversal，它是交互式图查询应用中的一种关键原语，是指从图上的一个或若干个顶点出发，按照一定的规则，沿着边遍历图中其他顶点。它常用于知识图谱中的搜索与发现、电商场景下的风控以及网络安全检测，应用范围较广。
（1）查询语言
Apache Gremlin是图遍历中最常用的一种查询语言，它提供了一系列图的原子操作，允许用户对各种图操作进行高层次的声明式编程。
如要在交易网络中找环。在交易网络中环非常重要，如果金钱流动是环的状态，说明可能存在洗钱的风险。使用Gremlin语言找环：首先使用g.V()has.找到起点有“name=tom”的属性，把它指定为“a”，再经过若干的repeat下面找simplePath,一直找到边又指回向a的路径，这就是环。可以看到，Gremlin查询语言非常灵活，可以像SQL一样进行声明式的查询，也支持filtering、循环和条件判断。
（2）MaxGraph和GAIA，具有高扩展性的Gremlin图查询系统
早期，为了支持Gremlin查询，我们研发了MaxGraph系统。MaxGraph系统架构上层是应用层，支持Graph Traversal操作；支持Gremlin语言；执行引擎层有分布式的dataflow引擎，支持控制流、stored procedure；存储层是分布式的图存储，能够支持实时的图写入、快照隔离、fault tolerance。最后，基于MaxGraph，我们在它的语言层和执行层之间引入了compile层GAIA，它发表在NSDI2021系统的峰会上。
（3）Gremlin查询的编译与执行
GAIA把Gremlin查询分解成类似于语法树的结构，交给底层分布式的数据流引擎执行。其中有一些特别的算子，如repeat、where等，可以对它们做特殊的处理，如给它上下文的contest，方便它能在底层分布式数据流引擎上的各个worker进行分布式执行，最后将结果汇总输出。这是处理图遍历图计算任务的方式。
2、图分析
图分析有别于图遍历，图遍历只会touch图中的局部数据，而图分析往往会involve全图的数据，所以也称其为基于全图计算的图分析。
如找实体分析，即是在不同的数据集中识别和找到它们表示相同的实体。这些数据可能源于电商平台、外卖平台、流媒体服务、线下超市等等，它们有不同的账号系统，如何识别某些账号是否属于同一人？这些服务中存在多少独特的用户或者商品？这也是很多互联网公司需要研究的普遍问题。
但这个问题存在很大的挑战。首先，它是全图迭代式的密集计算；其次，有海量异构的数据，且会动态变化，如该数据有数十亿条记录和PB级的数据，每天的数据更新可能达TB级；同时，两个实体之间可能有各种各样的链接关系，可能是相同的手机号，可能来自于同一地域等等；此外，数据中还有可能有噪声，可能并不完整；等等。
（1）点中心的编程模型
对如何做图分析，业界之前较为成熟、应用较广的点中心模型——Think like a vertex，即用户如顶点一样思考。它能够提供简单的API，且API的编写十分优雅，在工业界也有代表性的系统，如google的Pregel、开源实现ApacheGiraph、Spark GraphX等等。阿里巴巴也在较长的时间内采用了点中心编程模型，它有一个ODPSGraph系统，能够并行执行全图迭代式的图计算。
但随着业务的增长，点中心系统的局限性逐渐暴露了出来。首先，其编程难度大。因为点中心模型与传统的图算法有很大差异，需要用户针对自身业务需求重新设计算法。其次，它需要在性能和算法的准确度之间取舍，因为点中心的表达能力与传统的以图数据结构的表达能力不同，为了使其能够高效地并行执行，还需要牺牲一定的精度。同时，耗时和成本巨大，工程师可能需要花费几个月的努力才能够完成算法、研发和上线。此外，还有性能问题，在90亿条边的图上进行实体分析，这样的算法可能需要运行数天。
基于此，阿里云研发出了点中心编程模型的替代方案。
（2）PIE编程模型和GRAPE系统
在2017的SIGMOD和VLBD数据库领域的峰会上，阿里云提出了GRAPE系统以及PIE编程模型。在这个编程模型下，用户只需要提供三个函数，即PEval、IncEval和Assemble。具体的途径是：首先，进行数据分区，根据图G分成G1到Gn，在每个分片上同时调用PEval算法。然后，根据产生的消息调用单机增量版本IncEval，在每个分区上迭代进行IncEval的调用，直到达到Fixpoint，这个过程之中可能有worker之间的数据交互。当算法达到固定点时，调用Assemble函数把结果聚合起来。这三个函数都支持是即插即用。
（3）图算法的增量化
PEval也存在于传统的图计算，如单元最短路径SSP、WCC等。IncEval是它的单机增量版本，Assemble也只是一般的聚合函数。PEval比较常见的标准算法，但相对于图的批量性单机算法，图的增量算法IncEval可能比较少，且编写也相对复杂，因此，阿里云期望有一种系统性的方法将现有的单机算法进行增量化。
围绕这个问题，阿里云做了一系列的工作，在SIGMOD和VLBD也发表了很多论文，最后在SIGMOD 2021上的一篇论文Ingress系统。阿里云将其集成在GRAPE系统之中，与GRAPE一起完成分布式的大规模全图迭代计算，从而补上了GRAPE系统对于增量化算法缺失的一环。
3、图学习
（1）基于GNN类型的图计算
它使用的是基于GNN的推荐系统，有比较相似的范式。从图出发，先执行图采样操作，然后输出embedding，输出的embedding再应用于下游的各项任务，如items Recommendation、Social Network Analysis、风控、Link Prediction等。
Graph embedding进行图的嵌入表示，向量可以将图上的顶点和边用低维的向量表示，从而完成图从高维稀疏数据结构到以向量为主的低维稠密数据结构的转变。输出的向量（Graph embedding）再与下游的其他机器学习算法配合，从而在其他众多的业务中发挥作用。
（2）Graph-Learn，高性能的分布式GNN框架
阿里巴巴在VLDB 2019提出了阿里Graph，后来在Github开源的系统是Graph-Learn。它能提供分布式的高性能GNN计算。Graph-Learn支持了很多阿里巴巴内外的业务，至今也在持续的迭代。
前面介绍了各种图计算的类型，分别针对不同的图计算类型研究了不同的图计算系统，但同时也使图系统成为了一个孤岛，每个图系统只能解决一种类型的图计算问题。基于此，图计算进入了第二个发展阶段。
二、一站式图计算系统Graph Scope及其发展
1、背景
除了图系统孤岛问题之外，其实还存在其他的问题。
现实世界中的图计算往往是复杂的工作流，而不只是单独的图分析或图查询，可能是各种图计算的彼此结合。对于简化的电商平台欺诈检测工作流，首先，我们需要用SQL或ETL工具从原始的数据中构建出属性图的结构；接下来，要用Gremlin提取子图；然后，用全图迭代标签传播的算法识别欺诈的实体；如果要进行图采样，可以按权重如top k进行采样；此外，可能还要用Tensorflow训练GNN模型。
通过上面的工作流可以看到，在这样的流程中，它会跨越多个系统，如Spark、Giraph、DGL和Tensorflow。此外，在各个系统这个跨越的过程中，数据不断地写入写出到硬盘，完成数据的流转和交换。
2、功能特性
为如何一站式地解决这两个问题，这也是研发Graph Scope一站式超大规模分布式图计算框架的初衷。Graph Scope现已在Github上开源，地址是github.com/alibaba/graphscope，它能提供一种简单、统一的编程接口，一站式处理图分析、图遍历、图学习等各种图相关的任务。在统一的分布式数据流运行时，它可以使得每个图算子在精心设计的框架中进行单独的优化。在分布式的框架中，它也支持内存数据管理，它的Vineyard内存数据管理框架能够自动管理中间的数据表示、转换和移动。它还充分拥抱Python生态，能够使Graph Scope与其他Python生态的数据处理框架无缝衔接。最后，它也具备云原生设计的弹性伸缩，能够在K8s上方便地拉起资源，执行大型的分布式图计算任务。
3、Python上的易用性：NetworkX
Python作为Graph Scope的交互语言有很多好处。首先，Python支持交互式的计算，所见即所得。如它支持Jupyter Notebook，在Jupyter Notebook中，数据科学家和分析师可以直接编写代码，分析、建模、提取，还能进行可视化。其次，Python有非常丰富的生态系统，能提供端到端的解决方案，支持各种任务和各种数据的处理，包括json、文本、Tensor、图像、视频、科学计算等等。同时，它也支持高层次的数据和操作的抽象，能直接操纵Tensor、Dataframe、图等。因此，我们所选择了Python作为Graph Scope的interface。
NetworkX是在Python上处理图数据结构的常用框架，其易用性很高，唯一的缺点是它只能支持特别小规模的图。如仅能运行不超过2000的算法。用户通过pip install graphscope，Graph Scope能够完全兼容NetworkX的API。使用NetworkX写一段图处理的逻辑，从csv中载入一张图，进行图数据的构建和操作，算出相应的PageRank。如果用graphscope写同样的逻辑，只要文件import的地方稍作修改即可。所以，Graph Scope的API可以完全兼容NetworkX。
4、Vineyard：管理内存不可变数据
除了自身的易用性，Graph Scope要与其他PyData中的数据操作系统进行互操作和交互，需要使用到Vineyard系统，它能够管理分布式系统中的内存的不可变数据。这个系统也是开源的，且已捐给了CNCF。许多大数据系统都是在不可变的内存数据上进行工作的，但这其中有很多功能上的垄余，如每个系统都要适配不一样的I/O，实现数据的分区分块的策略，如容错机制、数据访问的RPC以及扩缩容所需要的功能。尽管I/O的成本非常高，但系统之间的数据分享还是免不了需要依赖于外部的文件系统，且目前仍没有高效的方法能够将不可变的数据与外部的可变数据进行动态同步。
Vineyard能提供开箱即用的高级抽象，直接有图、Tensor、Dataframe等数据类型。高级的开发人员可以定制需求中低级的API，并通过共享内存的方式零拷贝地进行本地的数据共享。Spark或Graph Scope系统在同一台机器之间的数据流转不用落盘，它们可以直接在内存中共享。它也能提供无感的远程数据访问和本地数据访问，还支持更加广泛的数据源和数据分区策略。此外，它也支持常见的功能，如容错机制、与可变数据源的快速同步等。
当有了Vineyard之后，我们前面提到的工作流会有相应变化。如原本的工作流是Dataframe或Tensor的数据结构，需要用科学计算，科学计算之后可以在Mars系统中做运算。运算完之后数据不需要落盘，可以在Vineyard中进行下一步的计算。如在Graph Scope中把Dataframe数据通过transformation变成graph data，graph data可以做embedding操作产出Dataframe或Tensor。此时，它仍旧无需落盘，这个数据还在分布式的内存中被Vineyard一起管理。它下一步可能给Tensorflow或Py Torch，只要加上它们的extension或adapter，它们就可以直接使用存在Vineyard中的Tensor数据，由于整个工作流端到端的数据都无需落盘，大大节省了端到端的时间。
三、持续迭代：向GraphScope Flex演进
从2024年开始，我们一直也在向下一代2.0版本GraphScope Flex演进。
1、背景
在现实世界中应用图计算系统时，我们发现一站式的概念仍旧比较理想化。因为它需要支持各种图计算，而图计算又是特别碎片化的需求。
（1）复杂的业务场景和工作负载
当图计算系统同时支持五种工作任务时，第一个工作任务与ranking相关，可能是OLAP的任务，其程序可能会使用C++或者PIE编程模型，这要求图必须简单，只有顶点和边。同时，该系统可能还需要支持第二种工作负载，如反风控的，其数据结构可能是Tensor。此外，图的存储位置可能也不同，它可以是存储在内存中的in-memory图，也可能是存储在硬盘里的图，还有可能是流式的图，这个图可能每天还要接受Data Stream的updates等。因此，图计算可能有各种各样的业务场景，也有各种各样的工作负载，还有不同格式的图需要在同一图计算系统中完成。
（2）多样的图模型和图组织方式
即便是同样数据集，由于上层的应用不同，上层对图格式要求的不同，就会以不同的方式建模。如可能建成简单的图，只有点和边；也可能是带权重的图，即除点和边之外，边上还有权重；也有可能使用矩阵或用张量，使用连接矩阵的方式建图；也有可能是RDFs建图；还有可能以属性图的方式建图，其中属性图是更加复杂的一种方式，但却是图数据库或图的数据查询中常常会用到格式。无论是图的模型还是图的组织方式，都具有丰富的多样性。
（3）多样化的图计算工作负载
有全图迭代式的图分析，如常见的PageRank、LPA标签传播的算法，还有图查询、图遍历、图模式匹配、图学习。
（4）多样性的编程接口
如图查询语言，除了最开始介绍的Gramlin，还有Cypher、ISO的GQL；如图分析的编程接口，有点中心编程模型think like a vertex，也有基于子图的编程模型，还有其他的domain specific language，如FLASH、Ggraphit等等；如图学习框架，它可能相对统一，一般都是Python，但在它的框架上也有不同，如PyG、DGL等。
（5）性能的考量
如用户追求不同，可能是系统的高吞吐、单个查询的低延迟、计算任务是OLAP或OLTP、系统性能极致的或是资源利用率最高、计算是全内存或是基于硬盘的计算、是否支持高可用等等。
2、新架构GraphScope Flex
基于此，GraphScope Flex希望使用类似于乐高的模块化设计，让每个组件变成如乐高积木块，可以跟其他组件一起协同工作，进而提供整个系统的部署。同时，提供了命令行工具flex build，可以帮助用户选择所需的组件，构建所需的个性化系统。
（1）存储层
最底层的GRIN、Vineyard、Graph AR、GART、MCSR，GraphScope Flex通过这些方式应对图模型和组织方式的多样性。
图的建模的多样性会带来存储的多样性。存储上可能有不同的需求，如图是静态图还是动态图要支持更新；或图的分区是何种策略，是切点的Vertex-cut还是切边的Edge-cut；图是属性图还是简单图；等等。这些在存储上可能有不一样的体现。
①GRIN：统一的图访问接口
针对各种各样的图存储，市面上以及Graph Scope内部有针对不同的特性设计的图存储。为访问不同的图存储中的数据，提出了统一的图访问接口GRIN，它的目标是将不同计算引擎和存储引擎之间的交互从M*N降低到M+N。具体来说，四个查询引擎底层是四个不同的图存储，它们分别针对于不同的特性做了优化。要互相访问，原先可能要写16个adapter或接口、访问，但利用GRIN统一的图访问接口，无论是上面的引擎或下面的存储，都向中间的统一访问接口接入，降低了接口的复杂性，只需要8种适配即可。GRIN在Github上是开源的。
②GraphAr：用于图数据归档和交换的开源文件格式标准
在存储方面，GraphScope Flex提出了GraphAr的系统文件格式，它主要用于图数据的归档和交换，是一种开源的文件格式，捐赠给了Apache,也是Apache孵化器中的项目。GraphAr是Graph Archive的缩写，它旨在让各种应用程序和系统能够更加方便、高效地构建、访问和共享它们之间的图数据。原先，六个系统之间有六个图相关的系统，都有不同的数据格式，它们之间可能数据不互通。用户在更换系统时成本很高，或者根本无法实现。提出开源的图数据归档格式和交换格式之后，每个系统都支持这种格式，用户在更换系统时，可以通过GraphAr文件格式进行方便的数据转入和转出。
除了作为一种标准的文件格式，它也是一种外存的图的存储格式，外存的图计算引擎可以直接用GraphAr中的图数据进行计算。除了格式的定义，GraphAr还提供了丰富的library，能够在Spark和C++的library的基础上方便地使用。
（2）技术栈
引擎层分为查询引擎栈和其他的几个引擎栈。
①查询引擎技术栈
查询引擎技术栈的前端层同时支持Gremlin和Cypher查询语言，用户可以按需选择。
在执行层，所有的查询语言都会转化为一种统一的中间表示Graph IR，即Intermediate Representation。在转化为Graph IR后，它还会进入下一环的查询优化器，进行基于规则或开销的优化。优化后的physical plan可能会通过Codegen给对应的引擎生成可执行的代码。此时还可以选择引擎，如GAIA引擎是基于数据流模型的查询引擎，适用于OLAP查询,再如Hiactor引擎，它是基于actor并行模型的查询引擎，它主要适用于OLTP的查询。
②全图分析技术栈
其前端层提供了100多种开箱即用的常用算法，基本上涵盖了所有的图分析的算法。同时，也支持Python接口、JAVA SDK、C++的SDK。在执行层，它最主要使用GRAPE高性能的分布式查询引擎，也集成了Ingress增量化组件和Flash编程模型组件。
③图学习技术栈
其前端层支持GNN模型，而且这些GNN模型兼容PyG的AP，也可以复用PyG中提供的各种模型。在引擎层，主要的创新点是采样与训练的解耦设计。为了高效的利用资源，我们用CPU采样，用GPU训练，而且采样和训练节点可以按需配比，可以独立伸缩。在训练部分，支持Tensorflow或者PyTorch。
在性能上，Graph Scope有国际权威的图计算基准测试IDBC，这个基本测试上保持着世界纪录，特别是在SVB的榜单上的Interactive workloads上排名第一，打破了该榜单的最高吞吐记录，提升约2-6倍，而且是首次在超大规模的数据（scale factor=1000，数据量约4T）上完成了严苛测试。
四、GraphScope持续建设开源社区
GraphScope仍在持续建设开源社区，其开源地址在github.com/alibaba/graphscope，现在在github上约有3000多个star，内置了100多个算法，日均在阿里内支持了五万多个图计算任务。GraphScope的核心技术也获得了Sigmod、VODB等国际权威的学术会议的奖项。
未来，阿里云还会持续夯实GraphScope的能力，推进它在GraphScope Flex上的演化，可能会支持更多的查询语言，GRIN会支持更多的存储，让GraphAr持续在Apache孵化器中孵化，可能也会探索面向图的HTAP的能力。还要对其他系统的互操作性做改进，如设计针对图的ETL操作原语，来简化、同数据集但不同图建模之间的转化，以及在其他应用的集成，可能也会研究图任务与关系型数据的互操作场景中如何引入跨引擎的统一编译，优化端到端的流程和资源利用率。
以上就是本次分享的全部内容。
