欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

图数据库和图计算系统有什么区别?

程序员文章站 2022-04-12 11:44:24
对于广大刚刚接触“图数据分析”的用户而言,一个十分具有迷惑性的问题是:图数据库和图计算系统有什么区别?今天,我们就从技术层面来简单地说一说两者的不同之处。 图数据库适合需要对子图进行并发操作的场景;图计算系统适合需要对全图进行迭代式计算的场景。 图计算系统 我们先从图计算系统开始。 图计算系统面向的 ......

对于广大刚刚接触“图数据分析”的用户而言,一个十分具有迷惑性的问题是:图数据库和图计算系统有什么区别?今天,我们就从技术层面来简单地说一说两者的不同之处。 

 

图数据库适合需要对子图进行并发操作的场景;图计算系统适合需要对全图进行迭代式计算的场景。

 

图计算系统

 

我们先从图计算系统开始。

 

图计算系统面向的场景主要是全图分析类的任务,例如:计算每个顶点的pagerank;计算从某(几)个顶点出发到其它所有顶点的最短路径;获悉整个图包含了哪些连通分量;发现图中包含的社区等等。这些任务背后的算法需要对整个图进行迭代式的处理,而计算过程中我们需要在每个顶点上维护一些状态(变量),根据边向邻居顶点传递消息,并依据收到的消息再更新顶点的状态。

 

由于这些计算面向的通常是静态的拓扑结构,因此图计算系统一般都会使用紧凑的表示方法来管理图数据,例如使用稀疏矩阵表示中常见的csr/csc(compressed sparse row/column)等格式。这样做的优势很明显:减少了读取时需要访问的数据量,且不必/不太需要考虑并发修改拓扑结构引入的开销。诚然,这样做会导致一个显著的缺陷:无法/只能以高昂的代价来修改图的拓扑结构。幸运的是,我们已知的大多数图计算问题都不需要或者可以通过其它方式来避免修改图的拓扑结构[1]

 [1]尽管有些分析过程如强连通分量、最小生成树等,会在计算过程中删除某些顶点/边,但是这类操作可以通过标记的方式来提示相应对象的删除,而无需真的修改图的拓扑结构。

 

静态的拓扑结构使得我们可以应用很多技术来优化图计算的过程:例如,将一个大图划分成若干较小的子图并分配给不同的计算单元(节点/处理器/核/线程)进行并行处理;根据每一轮迭代的特点使用不同的方式来驱动计算/通信过程等等。当然,可选的技术细节较多也意味着最终的系统可能由于任何一个环节的拖累导致糟糕的性能;甚至很多原本的优化没有产生良好的化学反应反倒变成了弱化[2]

[2]图的划分就是一个简单的例子:复杂的划分策略有可能减少分布式计算过程中的通信量,但是带来的代价是高昂的预处理开销以及顶点映射表的维护和频繁使用。pandagraph使用的块式划分十分简单,却能有效地避免这些不必要的开销。

 

图数据库

 

图数据库的主要职能是管理图数据,因此需要支持高效的对顶点/边的查询与更新;为了方便用户的使用,通常还需要增加对事务(transaction)的支持,从而保证并发操作下的正常运作。

 

持久化是所有数据库的立足之本。由于图的拓扑结构以及顶点/边上依附的属性数据可能会不断发生改变,因此图数据库就不适合使用csr/csc之类的表示方法来管理图数据了:即使它们的读取效率非常高,但是写入效率实在太低了(即使只修改一条边,最坏情况下也可能需要改写整个图的数据)。因此,图数据库需要采用读/写效率更均衡的存储结构,例如b+树、lsm树、链表、哈希表等。尽管这么做会使得读取效率在所难免地有一定下降,但换来的是高效得多的写入性能。

 

基于使用的存储结构,我们还需要在此之上构建完善的并发控制机制来管理对图中顶点/边的并发访问。这使得我们不得不在每次操作中存储一部分额外的信息(例如乐观并发控制需要的读写集、多版本并发控制产生的多份数据)或是触及一些需要竞争的资源(例如悲观并发控制中的锁),而这些都会或多或少地在访问图数据库中的数据对象时引入一定开销。

 

在图数据库中进行的分析通常都只涉及一小部分子图的数据,例如从一个顶点出发找所有的几度内邻居,或是给定两个顶点找出它们之间限定距离的最短路径等等。这些任务都很轻量级,且可能会同时有大量请求并发进入系统。因此,使用单个线程处理单个任务是比较常见的做法,这样能够获得更高的吞吐率,且避免了由并行处理的调度/同步引发的开销[3]。这与图计算系统对每个任务都使用并行处理的方式形成了鲜明的对比。又由于每个任务的处理时间可能很短,因此其它部分的开销例如客户端与服务器端之间的通信效率等等也会变得十分重要(例如restful的接口在有些场景下就会变成瓶颈)。

[3]随着图数据的增大,以及涉及子图区域的增大,这类轻量级任务也会逐渐变得重量级,此时,使用并行处理的方式减少延迟也是十分重要的。lightgraph提供了对单个只读事务进行并行处理的能力;对于时间消耗过长的任务,用户也可以通过相应接口提前中止。

 

总结

 

图计算系统面向的任务通常具有更高的复杂度,需要对整个图进行反复的访问来完成计算;而图数据库,无论是更新还是分析,通常都只涉及一部分子图的数据,且单个任务一般只需访问一遍即可。因此,图计算系统通常采用不可变(immutable)的数据布局,使得读取效率可以最大化,但是需要更精细地安排和组织并行的处理过程;图数据库则不得不选择读/写性能更均衡的存储方式来管理数据,并从并发控制、访问接口等众多角度尽可能地减少系统设计和实现引入的开销。

图数据库和图计算系统有什么区别?

从上面的架构图可以看到,费马科技的图数据库产品lightgraph和图计算系统pandagraph从底层的存储、使用的技术优化方向到上层的用户接口、提供的应用和工具等都有十分明显的区别。在实际场景中,很多情况下同时需要图数据库和图计算系统,依靠两者的良好交互才能达到最佳效果。

 

目前,一些同类竞品公司会在宣传时对图数据库及图计算系统进行混淆,增加了用户选择的难度,从而没有定位到最优的产品。了解这些不仅能让我们对图计算和图数据库更好的应用,而且可以更精确地根据实际需求寻找到更契合的产品。