深度解析：阿里云图数据库GDB V3引擎，性能何以百倍提升？
2022-04-21 10:27:47
2022年1月19日阿里云图数据库GDB V3引擎正式发布。导读：无论是学术界还是产业界，都对图数据库有比较高的预期。Gartner发布的《2021年十大数据和分析技术趋势》中提到：“到2025年图技术在数据和分析创新中的占比将从2021年的10%上升到80%。”应用需求推动着技术的发展，在GDB V3的引擎设计过程中，通过重建并改进数据存储架构、优化数据流转过程、自研计算引擎、重写执行引擎，以及资源池化、无锁化编程等一系列性能优化方法，从而逐步逼近物理硬件的极限性能。提供超越传统图数据库百倍的查询能力，为图技术的应用，解锁了更多的可能性。随着互联网时代的快速发展，企业的数据呈现爆发式的增长，数据之间的关联也越来越复杂，图数据库应运而生。重要的是如何运用技术方式帮助业务发挥辅助的决策作用，从而运用到新冠疫情、社交推荐、信用卡交易反欺诈等场景中。技术创新与产业应用，遵循着双螺旋上升的发展趋势，促使图技术到达了爆发式增长的边缘。从技术角度出发，图数据库的运用是针对解决数据的高度关联带来的严重的随机访问问题；从业务角度出发，图的价值在于融合数据、技术、打破生态位屏蔽产生高维认知。在了解图数据库时，我们不得不提到“知识图谱”这个概念。计算机在智能发展路径上，遵循着从数据-信息-知识-智慧的演进过程，知识图谱是其中认知智能发展的基础，而图数据库是承载知识图谱的佳底座，帮助我们实现智能决策。图数据库目前已经应用在金融、社交、互联网等领域，这个部分会更多分享阿里巴巴的图数据库的应用场景，更多探讨如何利用图帮助客户解决问题。以社交关系为例，图技术在好友查询中仅需要几毫秒的时间，它将好友定义成节点，将好友与好友之间的关系定义成边，图数据库这样以“点、边”的查询方式，速度远远快于关系型数据库。不仅是好友查询，在“初始用户推荐、好友精细推荐、点赞查询、关联话题推荐”等场景中都能运用图来建模。图神经网络等图技术已经是阿里巴巴智能营销中必不可少的组件。接下来将分享两个在智能营销中的图技术应用。个是One-ID，它的核心思路是借助联通子图等图算法，将不同数据源的多个实体实际代表的是同一个真实实体进行合并，从而识别到不同行为路径的ID隶属于同一个用户。第二个是智能营销。它的本质是是协同过滤算法思想为核心，通过计算共同邻居数进行相似节点推荐。同时图技术还运用在金融领域中，实现信用卡欺诈检测。与此同时，图技术也在保险反欺诈中发挥了作用。在某头部保险公司的案例中，运用图技术的测算，使得关联查询性能是原有保险反欺诈方案的10-100倍（客户实际测试反馈）。由于游戏业务成长周期的特殊性，运营促活效率至关重要。一旦出现用户流失，之后用户活跃几乎不可逆。通过使用图数据库GDB的自动机器学习组件，可以更加准确的预测付费、7日内留存玩家，帮助运营人员更准确的投放点卡、道具等权益。图数据库GDB为企业提供从“知识存储”到“推理分析”，一站式智能决策方案为了帮助企业更好地解决业务问题进行智能决策，阿里云GDB从“知识存储”到“推理分析”，为企业提供了一站式智能决策方案。在知识图谱技术在解决智能决策的问题过程中，包含着四个重要的环节：知识构建、知识存储、推理分析、可视化展示。在知识存储的环节中，我们需要将提取出来的信息进行有效存储与管理，以及使用时能够快速筛选及查询。为复杂环节是推理分析，如何在相互关联的信息中抽取并推理分析出高度有价值的信息，后要在数据分析推理后如何进行可视化展示。这其中知识存储产品化程度高，推理分析价值潜力大。性能，相较于传统图数据库提升近百倍。通过自研算子体系、计算引擎、执行引擎，逐步逼近物理硬件的极限性能，提供超越传统图数据库百倍的查询性能，只为解锁更多可能性。
兼容并包，集多种图查询语言于一身。高度兼容Neo4j、JanusGraph等图数据库引擎，支持 OpenCypher 、Gremlin 查询语言，降低迁移成本和研发门槛。
快速弹性、高可用、易运维，尽享云原生技术普惠。基于云原生架构的图数据库引擎，可快速扩缩容，应对突增业务负载；支持高可用实例、节点故障自动切换，保障业务连续性；提供备份恢复、自动升级、监控告警、故障切换等丰富的运维功能，免去繁琐的运维烦恼。
低构建成本、灵活计费，满足不同成本需求。产品构建、运维成本，仅为国外图数据库友商的 40%；支持按量付费、包年包月多种计费形式，无论创新探索，亦或生产应用都能自由掌握。
国内进入Forrest Wave评测报告的图数据库产品Forrest Wave在2020年底公布了一次评测报告，在全球遴选了十余款图数据库产品进行评审，其中阿里云GDB是国内进入评测报告中的图数据库产品，同时在高可用灾难恢复评测项目中取得了高的成绩。不同于关系型数据库的设计目标，图数据库诞生是为了解决高度关联数据带来的随机访问问题，这就注定了在这一领域上没有太多的现成方法可供直接参考。我们以影响查询请求性能的三大因素“硬件间性能墙”、“数据管理开销”、“硬件效能利用”出发，在GDB V3的引擎设计过程中，通过重建并改进数据存储架构、优化数据流转过程、自研计算引擎、重写执行引擎，以及资源池化、无锁化编程等一系列性能优化方法，从而逐步逼近物理硬件的极限性能。提供超越传统图数据库百倍的查询能力，为图技术的应用，解锁了更多的可能性。硬件间性能墙：数据处理会涉及到CPU、CACHE、MEMOERY、SSD、NETWORD等部件，各部件的处理延迟差异巨大；
数据管理开销：CPU利用率中90%左右的时间都在花费在优化内存和硬盘之间性能墙、数据一致性、持久性等方面；
硬件效能利用：传统的执行调用逻辑相比面向硬件特性实现逻辑可能会有比较大的性能差异
2、 图数据库架构分类从目前业界流行的图数据库产品来看，主流的架构主要分为两类：计算、存储分离的分布式架构和以主-备架构为代表的高可用架构。
前者的典型代表包括Tiger、Janus、Nebula等。这种架构下系统一般包括计算节点、存储节点和元数据管理节点。优势是通过Share Nothing的方式可以实现存储规模和计算能力弹性扩展，非常适用面向海量数据万亿大图场景。缺点是计算和存储一般跨节点部署，查询时会带来较大的跨网络数据交互开销，另外可能有数据热点问题。后者的典型代表包括阿里云GDB、Neptune、Neo4j等。这种架构下系统一般只有主节点和备节点。主节点提供读、写服务，备份通过提供stand-by形式提供主异常时服务切换。优势是架构轻量, 用户使用体验好，比较适合中小规模的用户。缺点是存在存储规模和计算能力的瓶颈， 另外如果存储模型和计算逻辑不一致的话，会存在数据转换，开销会比较大。对阿里云GDB而言，由于采用Cloud Native的架构，存储和计算实质上也可以独立扩缩容， 存储规模一般可以达到数百亿规模，计算既可以垂直升配，也可以水平扩容到多15个只读节点。GDB V3引擎基于主-备架构做了深度优化，主要体现在两点：计算、存储紧耦合，大化执行效率
设计图原生存储层，省掉数据转换开销
数据库的基础包括: 数据模型以及基于数据模型之上的各类数据操纵算子。关系数据库的逻辑模型是E-R模型，该模型主要包括：Entity、Releation、Property。用户将业务场景建模为逻辑模型后，再转换为关系表并存储在关系数据库中，然后利用基于关系代数衍生而出的操纵算子例如：扫描、投影、过滤等对其数据进行业务洞察。图数据库的模型包括属性图和RDF图，以属性图为例其包含关键信息为：Vertex、Edge、Property。本质上和E-R模型是一致的。但不同于关系模型将逻辑模型转换为一张张物理表，属性抽象为列，用表的外键来描述表之间的关系，属性图直接将逻辑模型利用邻接矩阵(表)等技术进行图原生存储。存储模型的简洁使的操纵算子非常灵活和丰富。以Gremlin图查询语言为例，操纵算子有map(flatmap)、filter、sideEffect、branch四大类共有110多个。考虑到Tinkerpop通用执行框架效率低下，GDBV3自研算子体系可以进行高效优化并大幅提升请求执行效率。定义算子执行体系后，需要通过计算引擎先将Gremlin请求翻译为物理算子树，GDBV3中由这三个模块构成：解析引擎：相比Tinkerpop原生引擎性能提升1000倍，同时极大提升用户体验，增强数据库安全能力。
翻译引擎: Gremlin每个算子都有对应的算子或者表达式，翻译过程中实时优化，多轮优化。
优化引擎：相比基于策略的优化存在依赖性、低效性等问题，基于Cascade子树匹配模型自上向下多层匹配优化，支持谓词下推、子查询打平、算子Schema融合等。
存算一体的架构：传统基于开源组件构建的非原生图数据库系统一般都是存算分离架构，无法避免跨网络数据交互等问题。V3采用存算一体解决方案，将这个执行算子树下推到图原生存储层，大化的减少了算子和数据之间的距离，提升了数据处理的效率。同时图原生存储本身就是针对图算子设计的存储结构，也会让算子的每个操作执行时延降到低。
数据驱动：传统的基于Volcano执行引擎调度过程类似下图中间左侧，算子自上向下调用，每次每个算子只获取处理一条数据，大量Cache Miss、数据转换、函数调用开销、内存浪费等问题导致数据执行效率低下。V3采用数据驱动的策略，每个算子会对一批数据进行集中处理，并生成新的一批数据。父子算子间通过Producer-Consumer模型共享同一批结果集合，极大减少数据跨算子传输。
动态执行技术：图原生存储基于Tree结构保存了各个属性的相关统计信息，系统并不需要额外的统计模块进行代价估算。静态优化后直接将整个物理算子树下推到图原生存储层，利用算子进行执行时实时优化。
资源池化：为解决系统运行时频繁new(delete)开销，自研内存管理系统并构建数组、树等基础数据结构，同时将系统中关键数据结构资源池化
无锁化编程：基于快照的MVCC技术避免读请求进行锁等待；通过多级缓存池解决高并发下线程资源分配竞争；使用线程局部变量，解决数据可见性与多线程资源争抢的矛盾；基于CAS原子操作解决高并发下多线程资源同步、日志记录等并发冲突
使用<指针, 引用计数> 思路解决复杂数据结构跨算子数据传输中编解码性能问题
自研Binary数据编解码算法解决复杂结果集Encoding(Decoding)开销
2跳查询中，相比Neo4j性能提升95倍，相比友商N性能提升258倍；
3跳查询中，相比Neo4j性能提升87倍，相比友商N性能提升214倍；
6跳查询中，GDB V3单线程消耗266s，其他测试产品均已超时，平均几十纳秒扫描一条数据；
从存储方式来讲，目前市面上的图数据库，可以分为原生图和非原生图两大类。非原生图使用现有的关系型数据库或者NoSQL数据库存储图数据，在查询时把图查询语句映射到底层系统的查询语言或者算子上。典型的例子是使用HBase/Cassandra作为存储后端的JanusGraph和HugeGraph。还有一些以插件形式内嵌到传统关系数据库里，实现图查询功能的系统，也可以归为这一类，比如Apache Age，Oracle PGX等。非原生图的优势是可以充分利用现有系统中比较成熟的基础设施，减少开发工作量。但是缺点也很明显：首先，非原生图数据库架构在其他系统之上，软件栈往往更加复杂，调用层次更深，可能还需要进行跨进程通信，带来额外的开销；其次，由于底层存储引擎并不是专门针对图数据的设计的，并不能很好的支持图查询的I/O访问模式。总而言之，非原生图数据库通常很难发挥硬件的佳性能。原生图数据库针对这些问题进行了重新设计，从数据结构和数据布局上进行了优化，数据访问的效率大大提升。除此之外，原生图数据库还可以从存储引擎的层面为图计算提供定制化的算子支持，从而将计算任务下推到存储层，减少不必要数据交互，进一步提升性能。也正是因为这些优势，GDB一直坚持采用原生图存储。其他使用原生图存储的产品还包括neo4j、Nebula Graph、TigerGraph等。图查询是I/O比较密集的操作，计算高度依赖数据，因此数据的访问效率对于查询性能非常重要。不仅如此，对于多跳图遍历这一类常见的查询模式，还存在数据局部性差的问题。在图遍历中，每向外一跳，需要访问的数据量都会成倍增加，并且这些数据通常是随机分布的，访问效率低并且对缓存不友好。所以图数据库的查询性能通常会随着跳数的增加急剧下降。GDB V3针对这些问题，设计了新的原生内存图存储引擎，以内存为存储介质来承载图数据，解决随机I/O性能差的问题，同时从数据结构、遍历算法、动态更新和垃圾回收等几个方面进行了优化。3. 优化的核心数据结构GDB V3的核心数据结构是改进的压缩邻接矩阵。以行位单位进行存储和更新。邻接矩阵中的一行，就是一个顶点关联的所有边。在实际数据中，大部分点的度数都比较小。比如twitter数据集，80%以上的顶点，出度和入度在30以内。把他们作为一个单元在内存中连续存储，可以保证高效的读取，也比较容易更新，更加适合动态图的存储。
以树状结构存储超级顶点。对于度数很大的超级顶点，用连续内存空间存储的方法并不适用。因此我们把它进一步拆分成树结构，以解决超级顶点的更新问题。
对相同类型（标签）的边进行聚合。在实际业务场景中，一次图查询往往只会选取特定类型的边进行遍历，把相同类型的边存放在一起，可以有效的提高这种访问模式下的性能表现。
基于GDB V3所使用的邻接矩阵结构，我们在实现图查询的过程中，使用矩阵计算的思想。图的多跳遍历问题，可以转换成邻接矩阵的乘法问题：将邻接矩阵跟自身多次相乘，可以得到顶点之间的多跳邻接关系。GDB V3在图查询的实现中，借鉴了矩阵乘法中的优化方法，以达到更高的性能。GDB V3的内存存储引擎支持细粒度的快照，并以此为基础实现了乐观的MVCC事务。更新操作不会直接修改现有数据，而是创建一个新版本的快照。读事务都基于某一个版本的快照来进行，保证了数据的一致性和事务之间的相互隔离，彻底杜绝dirty-read、non-repeatable等异常现象的出现。读事务也不会被写事务阻塞，可以做到无锁并发，达到很高的读性能。写事务在执行阶段先把更新数据记录到自身的事务缓存里，仅对自己可见，事务之间互不干扰，在事务提交阶段，才会处理并发冲突。在低冲突率的情况下，这种方式可以充分利用处理器多个核心的并行能力。在GDB的MVCC机制下，随着数据的不断更新，会产生多个版本的快照，而不再需要的快照需要及时回收以释放空间。如前文所述，大部分数据都是在多个快照之间共享的，所以在删除快照时，需要知道每个数据单元的生命周期[start, end)，其中start是当前版本的创建时间，end则是它从逻辑上被删除的时间。在删除快照Si时，如果一个数据单元同时满足start > i - 1（①） 且 end <= i + 1（②） （即该单元在前一个版本和后一个版本均不可见），它就可以被安全删除。在大数据量的情况下，全量扫描逐个去检查快照中的所有数据单元是很耗时的。因此，GDB为每个快照引入了一个失效列表来加速这个过程。快照Si的失效列表，记录的是在Si中从可见变为不可见的所有数据单元，也即生命周期end = i的数据单元。通过失效列表，可以快速拿到满足上述条件②的数据，只需要再检查是否满足条件①，就可以快速找出可以删除的数据。为了提升内存分配和释放的效率，GDB在内部维护了轻量级资源池，垃圾回收中收集到的内存不会马上释放，而是放入资源池等待复用，以减少跟操作系统和内存管理器之间的交互，提升效率。图数据库要解决的问题是将大规模，多元异构的数据有效连接起来之后产生高维决策。不同于关系型数据库，图数据库背后目前没有指导进行决策的思想与规则，也是导致图数据库技术至今没有被大规模应用的核心原因。图的意义在于信息升维，因此我们将图技术与自动机器学习结合，使用机器学习算法，探寻数据规律并找到佳分析路径，实现数据升维到规律总结。通过GDB自动学习机器的任务，可以实现在不写任何代码的情况下，去帮助开发选取业务模型、实现模型调优，从而形成相应的超级模型。以此帮助客户进行辅助判断，降低模型研发周期。来源 https://www.modb.pro/db/240231
