论文导读 | 超越宏基准：基于微基准的图数据库评估

图谱学苑 2022-10-29

644

一、方法

图数据库采用属性图模型。图数据是由节点（也称为顶点）组成的数据以及它们之间的连接，称为边缘。边有标签，每个节点或边都有一组属性或属性，即一组名称-值对。

1.1、系统

为了公平比较，我们需要所有系统支持一种公共访问方法。为此，我们考虑了通过官方认可的实现支持Gremlin查询语言的系统。Gremlin是图形数据库中最广泛支持的查询语言，可以被视为图形数据库系统的SQL。我们还要求我们所考虑的系统拥有许可证，允许在服务器上免费发布实验比较及其操作。此外，我们希望考虑在类似的先前研究中已经研究或提到的每个系统。考虑到这些需求，我们考虑了许多本机图数据库。其中包括Neo4J，它本机存储节点和边，但单独存储，并支持一些模式索引。我们还考虑了混合系统，即使用第三方存储引擎的图数据库。特别是，我们研究了过去从未考虑过的Sqlg和ArangoDB，以及Titan。我们的研究中排除了Caley和DGraph，它们是混合系统，但不支持Gremlin。

我们还考虑了一些RDF数据库，如BlazeGraph和Sparksee。尽管是为RDF数据定制的，但这些系统看起来非常类似于图形数据库。表1总结了上述系统的主要特征，我们将在下面对此进行扩展。注意，对于某些系统，我们考虑了两个版本。我们这样做是因为我们想说明这些系统从一个版本到另一个版本所取得的进展程度，并帮助利益相关者决定是否值得升级。最新版本采用了更新版本的Gremlin，它具有更清晰的语义、更少的重载运算符和更丰富的运算符集。Gremlin主要是一种语法，因此，在同一系统的不同版本中观察到的任何性能变化都很可能是由于更有效的实现，而不是由于实际语言本身。

1.2、架构和查询处理

有两种方法可以实现图形数据库。一种是从头开始构建（本地数据库），另一种是将一些功能委托给其他现有系统（混合数据库）。在这两种情况下，需要解决的两个挑战是如何存储图和如何遍历图。

1.2.1、本机系统架构

对于数据存储，一个常见的设计原则是将有关图结构（节点和边）的信息与其可能具有的其他信息（例如属性值）分开，以加速遍历操作。Neo4J有一个用于节点记录的文件、一个用于边缘记录的文件，一个用于标签和类型的文件，以及一个用于属性的文件。1.2.2、标识符映射到物理位置。

这允许在不改变其标识符的情况下改变对象的物理位置。在这两种情况下，给定一条边，获取其源和目的地需要恒定的时间操作，并且检查节点上的所有边，从而访问节点的邻居，其成本取决于节点度而不是图大小。例如，给定一个标签，可以扫描相应的位图以识别哪些边共享同一标签。此外，位图识别与节点相关的所有边。对于属性，使用了类似的机制。这种组织的主要优点是，许多操作成为位图上的按位操作，尽管像边缘遍历这样的操作没有恒定的时间保证。

1.2.3、混合系统架构

ArangoDB基于文档存储。每个文档都表示为一个自包含的JSON对象（以压缩二进制格式序列化）。

BlazeGraph是一个RDF数据库，将所有信息存储到主题谓词对象（SPO）三元组中。通过改变每个三元组中值的顺序，将每个语句索引三次，即为SPO、POS和OSP中的每一个构建B+树。

在Sqlg中，图结构由每个边类型的一个表和每个节点类型的一张表组成。每个节点和边由唯一ID标识，节点和边之间的连接通过连接检索。

最后，Titan将图表示为邻接列表的集合。

1.2.4、查询处理和评估

我们考虑的所有系统都支持Apache TinkerPop框架，该框架充当支持Gremlin的独立于数据库的连接层。Gremlin查询是一系列操作。例如，考虑表2中的Q28，它选择了具有至少k个传入边的节点。对于每个节点（g.V），它通过计算传入边（it.inE.count()）来应用过滤器（.filter｛…｝）。在ArangoDB中，每个步骤都被转换为AQL查询并发送到服务器执行，因此上述Gremlin查询将被执行为一系列两个独立的AQL查询，分别实现外部和内部。

二、查询

为我们的测试选择的查询集遵循微基准方法，该方法在许多情况下重复使用。该列表是对文献和许多实际场景进行广泛研究的结果。在我们发现的许多复杂场景中，我们确定了组成它们的非常基本的操作。通过这种方式，我们获得了一组独立于模式和底层数据语义的通用操作，因此，它们具有通用的适用性。在查询列表中，我们考虑不同类型的操作。我们考虑节点、边、标签及其属性的所有“CRUD”类型，即创建、读取、更新、删除。特别是对于创建，我们将数据集的初始加载和单个对象创建视为单独的情况。原因是第一种情况发生在空实例上的批量模式下，而第二种情况则发生在数据库中已有数据的运行时。读取操作的类别包括统计操作、内容搜索和过滤内容。我们还考虑跨节点和边的遍历操作，这是图数据库中的特征。我们记得，寻找中心性或计算强连通组件等操作在图分析系统中是典型的，而不是在图数据库中。我们遵循的分类与其他类似工作和基准中的分类一致。查询的完整列表可在表2中找到，详情请看论文。除了这些查询，我们还运行一组复杂查询，以便将它们提供的见解与其他操作员的结果进行比较，并测试系统的查询优化能力。这些查询来自社交网络应用基准。

2.1、复杂查询集

为了比较使用微基准方法和使用宏基准方法获得的见解，并测试系统优化复杂查询的能力，我们还基于LDBC社交网络基准创建了13个查询的工作负载。这些查询模拟了系统中新用户可能执行的任务，从创建帐户（创建具有属性的新节点）和填充配置文件（连接到代表学校、出生地和工作场所的节点），到检索项目或其他用户推荐的任务。对于这些操作，我们在由多个基本运算符、多个连接谓词、排序、top-k和max查找组成的工作负载查询中包括。

三、价值评估方法

公平性、可复制性和可扩展性是我们评估不同系统的三个基本原则。特别是，所有系统都采用了数据的通用查询语言和输入格式。我们确保每个查询执行都是独立执行的，这样就不会受到外部因素的影响。在一个系统中进行的任何随机选择（例如，为了查询节点而对节点进行的随机选择）在其他系统中保持相同。目标是进行比较评估，而不是绝对评估。已经使用了真实和合成数据集，特别是大容量的数据集，以便实验能够突出不同系统之间在可伸缩性方面的差异。我们的评估方法已在一个开源测试套件中具体化，该套件包含脚本、数据和查询，并可扩展到新的系统和查询。

类的假定函数

在本研究中，我们创建了一个子图（Frb-O），只考虑与组织、商业、政府、金融、地理和军事主题相关的节点，以及它们各自的边缘。此外，我们通过从完整图中随机选择0.1%、1%和10%的边来创建其他3个图数据集，分别生成Frb-S、Frb-M和Frb-L数据集。ldbc是唯一具有边和节点属性的数据集。其他仅在节点上具有属性。表3提供了上述数据集的特征。它报告节点数（|V|）、边数（|E|），标签数（|L|））、连通组件数（#）、最大连通组件的大小（最大值）、图密度（密度）、网络模块化（模块化）、平均连通度（Avg）、最大连通度（最大值）和直径（Δ）。如表所示，MiCo和Frb稀疏，而ldbc和酵母密度高一个数量级，这反映了它们的性质。ldbc是唯一具有单个组件的数据集，而Frb数据集是最分散的。报告平均和最大程度是因为大型集线器成为遍历的瓶颈。评估指标。我们评估了系统，考虑了磁盘空间、数据加载、查询执行时间以及我们的使用经验。

四、实验结果

我们首先概述了针对各种操作类型进行的实验评估结果，然后在表4中，我们提供了总体评估和主要见解。在整个测试过程中，我们注意到MiCo和ldbc给出的结果与Frb-M和Frb-O类似。酵母非常小，没有突出任何特别的问题，特别是与Frb-S的结果相比。我们还尝试加载完整的自由基图（有314M条边和76M个节点），但只有Neo4J、Sparksee和Sqlg成功加载，并且只有Neo4J（v.3.0）成功完成了所有查询。此外，完整数据集上记录的运行时间符合其子样本的总体趋势。因此，在下文中，我们仅关注Frb-S、Frb-O、Frb-M和Frb-L的结果，并仅在其他样本表现出与Freebase不同的行为时才参考其他样本。

4.1、数据加载

实验结果如图1（a）和1（b）所示。数据集Frb-O、Frb-M和Frb-L的结果表明，Titan是空间性能最好的。它的策略是用增量编码的形式压缩每个邻接列表中的节点标识符，这种策略在具有高次节点的图中非常有效。相反，对于ldbc数据集，其中许多文本信息由许多对象共享，OrientDB和Sparksee实现了最小的空间消耗，因为它们消除了属性值的重复。最后，我们可以看到BlazeGraph在所有数据集上平均需要三倍于任何其他系统的大小。

4.2、复杂查询

ArangoDB和Titan（v.0.5）通常是最慢的，这表明它们无法有效利用索引结构，也没有采用任何高级优化。Titan（v.1.0）对于一些涉及短连接的查询和一些具有单标签选择的查询非常快。然而，微观基准分析（见下文）表明，这一结果并不普遍。这种类型的性能是由于特定的查询和Cassandra后端缓存的帮助。正如我们将在下面的微基准测试结果中看到的，Titan（v.1.0）的速度始终较慢当图形变得更大并且查询无法利用任何缓存时，比其他系统更安全。在几乎一半的查询中，Sqlg是最快的。微基准测试分析确定了Sqlg中性能最好的运算符的特征，这些查询可以利用这些特征转换为单个关系运算符或条件连接查询，而无递归和短连接链只遍历有限基数的少数边缘标签。在这些查询中，系统不会产生昂贵的连接，并且能够利用关系优化器并利用索引。相反，Sqlg速度较慢的情况是，查询遍历多条边，并且不在单个边标签上过滤，因此会生成较大的中间结果。

4.3、微观基准结果

在图1(c)).中说明了结果。在两个版本中，Neo4J是唯一一个成功完成所有数据集所有参数测试的系统（图中省略）。OrientDB是第二好的，在大型Frb-L上只有几次超时。

对于添加新对象（节点、边或属性）的操作，我们体验了Sparksee、Neo4J（v.1.9）和ArangoDB的极快性能，时间低于100ms，其中Sparksee通常最快（图3(b))。另一方面，BlazeGraph是最慢的，时间在10秒到1分钟之间，因为每个操作都需要多次索引更新。Titan的两个版本都是第二慢的系统，插入节点的时间约为7秒，插入边或属性的时间为3秒，而插入具有所有边的节点(Q.7)需要30秒以上。Sparksee、ArangoDB、OrientDB、Sqlg和Neo4J（v.1.9）在不到一秒钟内完成插入。OrientDB对于节点插入（Q.2）和节点和边上的属性（Q.5和Q.6）来说是最快的，但对于边插入来说，速度慢得多，表现出不一致的行为。Sqlg是插入节点最快的方法之一，另一方面，OrientDB、Sqlg和Sparksee的节点移除性能（Q.18）似乎受到图的结构和大小的高度影响（图3（c））。最后，对于删除节点、边和节点属性，Titan通过利用列存储中数据组织的优势，获得了几乎一个数量级的改进。请注意，ArangoDB也是最快的。

一般选择。对于读查询，会出现一些异构行为。按ID进行搜索（图4（b））与所有其他选择查询（图4（a））有很大不同，而且通常要快得多。BlazeGraph再次是最慢的。在计算节点和边（Q.8和Q.9）时，Sparksee的性能最好，其次是Neo4J（v.3.0）。对于BlazeGraph和ArangoDB，节点计数是此类别中在超时之前完成的少数查询之一。在这里，Neo4J的两个版本是最快的数据库，而Sparksee则稍慢一些。由于之前的实验表明Sparksee在边缘上迭代速度很快。

我们还注意到，对于这些查询，Sqlg是最慢的引擎，当比较Q.28到Q.31的查询性能时，如图5（b）所示，它们遍历整个图，根据节点周围的边过滤节点，Neo4J（v.3.0）表现出最佳性能，其旧版本是第二快的。如图6所示，未标记版本的BFS的性能突出了Neo4J在所有深度的良好可伸缩性。OrientDB和Titan提供了深度2的第二快时间，比Neo4J慢50%

对于深度3及更高（图6（b、c、d）），OrientDB比Titan快一点。对于没有标签约束的最短路径（Q.34，图7（a）），系统的性能与上述类似，尽管BlazeGraph和Sparksee在这种情况下非常相似，但Sqlg仍然是最慢的。在ldbc上运行相同的查询时，我们仍然观察到（图7（b）），Neo4J是速度最快的引擎，而Sparksee是第二快的。Neo4J（v.1.9）、Sparksee和OrientDB是CUD运行速度最快的系统。

4.4、整体评价和洞察

表4总结了我们实验中观察到的不同GDB的性能。勾号符号

表示系统达到或接近最佳性能。警告符号

表示系统性能接近低端或指示执行问题。通过该表，从业者可以为特定的工作负载或场景确定最佳系统。例如，我们可以看到本地图数据库Neo4J、OrientDB和部分Sparksee是图遍历操作符（T）的更好候选。

文章转载自图谱学苑，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

论文导读 | 超越宏基准：基于微基准的图数据库评估

评论