专家观察| 高并发图数据库系统如何实现？

独孤飞宇

作者丨教授老边
来源|AI科技评论
随着越来越多的开源软件、微服务架构的出现，所有的软件都在宣称自己是高性能的，大量的软件在滥用市场宣传混淆视听，把完全不具备高性能特征的系统鼓吹成无所不能，这让大众很难甄别出哪些是真材实料，哪些是狗皮膏药，哪些是滥竽充数。更有别有用心的厂家，打着符合国际、国内标准旗号的发布的颠倒黑白的性能评测报告——例如某互联网大厂与另外一家同城的图数据库创业公司就先后鼓吹自家的图数据库系统性能全球第一，但实际上所有测试结果都采用接口预先封装的模式，无论多复杂的查询逻辑，结果永远是几毫秒返回，既无查询语句，也没有查询结果的正确性验证，这就属于典型的盗名欺世。
那么，有没有什么便捷的方式来甄别一款图数据库是真正具有较高的性能呢？
提供以下锦囊要诀：

• 是否采用原生图存储？
  
• 是否采用原生图计算？
  
• 是否采用原生图查询与优化器？
  
• 是否支持高并发图查询、操作、分析、算法？
  

关于前两点，我们用几个例子来直观的说明。以开源的图数据库项目JanusGraph为例，它就是用典型的外接第三方的存储引擎作为底层，但是在具体的图数据加载、查询与分析时效率非常低下。类似的Oracle Labs的PGX的持久化层也依托自家的关系型数据库，这导致其所能适配的场景大大受限。
还有像国内某开源图数据库，并不自研图计算引擎，而是采用封装Apache Spark或腾讯Pluto的方式，前者可以说和图没有多大关系，而后者作为一个开源项目已经名存实亡。非原生的存储或计算引擎的最大的弊病在于性能低下，而这种性能低下直接导致大量的场景无法进行高效处理。
第三点也是衡量一款图数据库系统是否主打高性能的试金石——我们知道任何数据库系统的查询语言都与其自身的功能特点相匹配，这也是为什么直到今天，关系型数据库系统的主要厂家都还在与SQL国际标准兼容的同时保留了自身的一些特殊语法与功能，以体现自家系统的特性。
同样地，如果一款图数据库只兼容其他家的标准（例如：OpenCypher与Gremlin），却没有自己的任何语法、语言特色，可以断定该系统既不是高性能，也不是自研的——在实际商业应用中的效果一定是一塌糊涂且不尽人意的。
那么，为什么高性能的图数据库系统一定是支持高并发的呢？原因很简单，因为高并发是最直接的实现对底层硬件资源并发处理能力的释放，实现高效数据处理的不二法门。
高并发的系统实现有三大维度：
一是，高并发架构；
二是，高并发数据结构；
三是，高并发的查询与算法实现。
以上三者，缺一不可。在图数据库的并发架构（数据结构及算法逻辑）设计中，不仅要支持在多用户、多查询的条件下的并发，也要支持单个查询的并发实现。
实际上，很多naively-designed的图数据库系统只能做到多用户访问的并发，但是根本没有做到支持单个查询的高并发实现——其所反映出来的是一种系统架构设计与工程实现能力的不足。
我们用具体的例子来说明什么叫做单个图查询的并发化。在下图中示意的是K邻查询的并发逻辑，从图中某个顶点出发，查询其K步邻居全集（结果需去重）：

• 定位被查询起始顶点；
  
• 记录该顶点全部（1度）邻居，如果满足并发条件，分而治之（进入多线程、多任务模式）；
  
• 每个线程分配到的顶点作为起点，继续向下遍历（注意已经遍历过的顶点需要被标注，不会重复遍历）；
  
• 如果当前查询深度已经抵达K步，记录并返回，统计最终结果（含去重），如果没有，继续向下遍历。
  

一种典型的K邻查询的并发化逻辑

K邻查询的计算（时间）复杂度与底层的数据结构息息相关，例如第一步中定位顶点所需的时间、第二步中找到全部邻居的时间复杂度，这个地方原生图的近邻无索引存储就显得至关重要，因为用O(1)的时间复杂度获得全部邻居的效率，显然会比任何串行化访问的数据结构要高效得多。而且因为需要多次迭代，任何更高的时间复杂度都会在反复迭代、循环的过程中被放大，进而导致指数级的性能落差。
以性能对标评测中常见的Twitter-2010数据集为例（15亿点边规模，其中有大量1度邻居达到百万以上规模的超级节点），1-Hop的平均查询时间就能反映出一套图系统的性能指标，例如下图中所示ArangoDB需要1.7秒，这代表着它可能在磁盘上进行某种低效的遍历操作后，才获得全部1度邻居结果，而最快的Ultipa（嬴图）仅需要0.0006秒（600微秒），较第二名Tigergraph（24毫秒）快了足足40倍，显然Ultipa与Tigergraph都用到了某种内存加速的数据结构，因此在时效上可以做到仅1度查询就会有10倍以上的性能差异。
这种差异会在2度、3度、6度及更深的查询中被逐级放大——在下图中，可以看到在3度邻居查询时，Ultipa较JanusGraph和ArangoDB快8000倍以上，更深层的查询，这种新能落差稳定在1万倍以上，而后者多半是在耗尽计算资源之前无法返回有效的查询结果。



在15亿点、边规模的图数据集上，各家图数据库的性能对比（32核X86-CPU、256GB内存、1TB HDD硬盘）

或许有读者对于高性能、高并发的数据结构与算法心存疑惑，甚至会质疑其意义何在？
以国产CPU为例，其在硬件层面本身和国外产品的差异普遍认为在10倍上下。但是，这种差异是可以通过软件层面对底层精简算力的释放得以弥补。
例如在下图中，我们看到同款的嬴图软件在国产芯片上的性能基本上是Intel X86的十分之一，但是因为嬴图在X86平台上百倍以上的性能优势，因此，即便是在国产芯片运行嬴图对标其它厂家在X86上的性能，依然可以有显著的性能优势。


实现高并发系统是一项系统工程，涉及到数据的全生命周期，从数据入库、更新、查询不一而足，可以说能通过并发来实现加速的地方无所不在——同时还要考虑到系统资源的消耗的问题，要在资源使用与最大化并发之间维系一个微妙的平衡。
随着开源框架、微服务架构、云计算框架的登堂入室，让很多人认为100台机器 x 每台单线程的系统的性能会超越1台机器 x 100线程——确切地说，100台机器的I/O的能力会更强，但是计算能力要弱100倍以上。
这也是所有BSP（大规模同步处理系统）的难言之隐——会产生这种错误认知的根本原因在于把互联网的短链交易类型的操作与复杂深链查询混为一谈！
在实操过程中，短链操作可以很好地通过大规模分布式系统架构来实现并发、提速处理，但是对于深链操作，越分布效果越糟糕，因为分布式所造成的多实例间的数据同步、处理等待会比在同一实例上的操作有指数级的性能损耗。
因此，如果我们把所有的图数据库上的操作进行分门别类地剖析，我们可以分为如下几类来分而治之（找到最优、可能且合理的并发加速方式）：

• 元数据处理：数据加载（导入）、更新、删除；
  
• 高维图查询操作：K邻、模板路径、组网等操作；
  
• 浅层图算法：典型的浅层图算法有度（中心性）计算、PageRank、三角形计算、联通分量、相似度算法等；
  
• 深层图算法：全图K邻、深度游走、Louvain社区识别、标签传播（及其变种算法）、中间中心度、各类图嵌入算法等。
  

元数据与浅层图算法都有比较大的概率可以通过大规模分布式来实现多实例+多线程的加速处理，并能取得很好的效果。而深层图算法与面向高维数据的图查询类操作，集中式的处理（即某个查询在单个实例上，通过多线程并发来处理）会取得更高的吞吐率，这个时候，通过多个实例的来进行负载均衡，可以取得高并发加速的效果（反之，这类复杂查询采用大规模分布式系统来应对就会有事倍而功半的负面效果）。
对于可扩展的分布式系统存在的性能问题，有兴趣延展阅读的可以看一下这篇论文：
Scalability, but at what cost?www.usenix.org/system/files/conference/hotos15/hotos15-paper-mcsherry.pdf



高并发图计算

综合以上探讨，构造一款真正（同时）具备高性能与可扩展性的图数据库系统是一件非常有挑战的事，我们甚至可以说：没有任何一种单一的架构可以同时满足高性能与可扩展性。现有市场上的所有产品（无一例外）的存在以下问题：

• 有扩展性，但性能低下 （20%）；
  
• 有性能，但扩展性受限 （10%）；
  
• 既无性能，亦无可扩展性 （70%）；
  
• 兼具扩展性与性能 （0% as of 2022年底）。
  

但是，我们知道构建高性能+可扩展的图系统体系架构的原则：

• 在能充分的进行垂直扩展的情况下，先垂直扩展 （Scale-up first)；
  
• 在可以水平扩展的时候，水平扩展 (Scale-out second)；
  
• 水平扩展用于可以大规模分布式计算的场景 （例如浅层查询、元数据处理类场景）；
  
• 垂直扩展用于更适合集中式数据处理的场景（例如深度遍历的场景）。
  

事实上，大多数的真实用户的数据量根本没有达到海量，只需要采用垂直扩展的架构就已经可以完全满足业务需求，这种情形下去盲目追求大而全（且空泛）的水平分布式架构得不偿失。
我们可以列出3种分布式架构，及其各自的优缺点：


事实上，第二种模式可以看作是第一种模式的一种水平化扩展，它区别于纯水平分布式的主要地方在于集群的管理逻辑和图分片逻辑的不同——类比传统的关系型数据库的分布式架构设计，也可以找到与第二、第三种分布式相比的案例，其中前者更贴近业务，很多业务逻辑对于NameServer/Proxy是非透明的，包括分图、分片的逻辑也是如此。



实现高性能图数据库系统的要素

最后，我们来总结下实现高性能的图系统的要素：

• 高密度并发计算的能力——任何不具备高密度并发能力的系统，绝无可能实现高性能计算。
  
• 超深度遍历（下钻）的能力——没有深度下钻能力的系统根本不能算作是一款图系统。
  
• 动态剪枝的能力——动态剪枝需要底层数据结构的支持，它意味着计算时间复杂度的大幅（动态）降低。
  
• 线性可扩展的能力——在尽可能不牺牲（深度）计算性能的前提下的可扩展性才是有的放矢。
  
• 极致工程的能力——实现有真正工业化价值的图系统。