RDF和属性图

首先来介绍 RDF 和属性图。大家知道世界万物是普遍联系的，Internet 带来了信息的连通，IoT 带来了设备的连通，像微信、微博、抖音、快手这些 APP 带来了人际关系的连通。随着社交、零售、金融、电信、物流等行业的快速发展，当今社会支起了一张庞大而复杂的关系网，在人们的生产和生活过程中，每时每刻都产生着大量的数据。随着技术的发展，我们对这些数据的分析和使用也不再局限于从统计的角度进行一些相关性的分析，而是希望从关联的角度揭示数据的一些因果联系。这里的关联，指的是相互连接的 connectivity，而不是统计意义上的 correlation。

关联分析的场景也非常多，覆盖我们生活的方方面面。比如从社交网络分析里，我们可以做精准营销、好友推荐、舆情追踪等等；金融领域可以做信用卡反欺诈的分析，资金流向识别；零售领域，我们可以做用户 360 画像做商品实时推荐，返薅羊毛；电力领域，可以做电网的调度仿真、故障分析、电台因子计算；电信领域，可以做电信防骚扰，电信防诈骗；政企领域，可以做道路规划、智能交通，还有疫情精准防控；在制造业，我们可以做供应链管理、物流优化、产品溯源等；网络安全行业，可以做攻击溯源、调用链分析等等。

在做关联分析的时候，我们往往需要一个图模型来描述。常见的图模型分为 RDF 和属性图两种。RDF 图中用点来表示唯一标识的资源或者是字面量的值，边则用来表示谓词。点和边之间组成一个 SPO 的三元组。属性图中，点表示实体，边表示关系，属性是点或边上的一个键值对。

相比之下，RDF 的优势是可以支持多值属性，因为它的属性也是一个点，所以一个点连出去，可以有多值的属性。也可以通过四元组的方式前面加上一个图的描述，来实现动态图。并且 RDF 开始的比较早，所以有一个比较统一的标准。

属性图的优势在于它两点之间可以表示同类型的多条边，因为它在边上是可以有区分属性的，边上的属性值也能让边上的表达能力更丰富。并且它支持复杂的属性类型，比如 list、set、map 等。

随着行业的发展，我们看到越来越多的可能。知识图谱的表示在逐渐用属性图来完成。当然也有少量的图数据库是用 RDF 模型来做的，但是未来更多的新型图数据库都会用属性图模型。

图数据库存储的核心目标

完成一个图查询或者图分析的核心操作，就是邻居的迭代遍历。

单独的访问点或者边，或者上面的属性并不是这里的关键。仅仅是单独访问，使用传统的数据库也可以提供很好的性能。在关联分析当中，不论是从一个起始点若干跳数内的邻域网络进行分析，还是对全图进行一些完整的计算，最核心的操作都是迭代遍历某个点的所有边，也就是所谓邻居的迭代遍历。在关系型数据库中是依赖外键，通过建立索引等方式来完成的。

在图数据库中，会直接存储边数据，也就是所谓的实现 index-free adjacency。写入的时候，保证一个点和它直接相连的边总是存储在一起。查询的时候，迭代遍历一个点的所有邻居可以直接进行，不需要依赖于其它数据结构，从而可以大幅提升邻居迭代遍历的性能。

性能对比

这里是跟关系型数据库做的一个深点查询的性能对比，用的是 who-trust-whom 的一个公开数据集，这个数据集也不是很大，约 7.5 万点，50 万边。我们想知道一个信任的人这样一个多跳关联的查询结果。使用关键性数据库的时候，对比了加索引和不加索引的情况。可以看出 2 跳的时候加索引可以明显提升关系型数据库的查询速度，到 3 跳的时候提升就不多了， 4 跳以上的时候加不加索引都会变得很慢。而使用图数据库，查询性能一直会保持在一个非常快的水平。这就是图数据库的 index-free adjacency 的特性，能够大幅提升邻居查询的速度。

图数据库的分类

分类

根据实现免索引连接的方式，可以把图数据库分成三类。

  1. 第一类是使用原生图存储的方式，它的数据存储层就直接实现了免索引连接。上面的处理计算层和业务层都是以完全图的结构来描述，并且也不依赖于第三方存储组件，所以这种实现免索引连接的性能是最高效的。
  2. 第二种方式是非原生存储，数据存储层使用的是一个第三方的开源存储组件，但是它在处理过程中实现了近似免索引连接，在大多数情况下也能提供不错的性能。它的问题是由于使用了第三方存储组件，在某些场景下可能做得不是最优化。
  3. 第三种方式就是完全非原生的存储，底下可能是一个关系型数据库，或者是一个文档型或者其它类型的数据库，它的存储层其实并不是真正地实现了免索引连接，而是处理成通过索引或者一些其它技术手段，向上表达了一个图模型的查询接口。这种其实只是在接口层上实现了图的一个语义，而底下的存储和计算层都不是完全地使用免索引连接，所以它的性能也会相对低一些。

图数据库存储的主流技术方案

前文中已经明确了数据库存储的核心目标就是实现免索引连接。那么接下来就来看一些具体实现免索引连接的主流技术方案。

数组存储

首先我们能想到的最直接的一个方案，就是用一个数组把每个点上的边按照顺序一起存储。在这一存储方案中，点文件就是由一系列的点数据组成的。每个点的存储内容包括点的 ID、点的 Meta 信息，以及这个点的一系列属性。在边文件中，是按照起始点的顺序存储点上对应的边，每条边存储的内容包括终止点 ID、边的 Meta 信息、边的一系列属性。这里所谓的 Meta 信息包括点边的类型、方向，还有一些为了实现事务的额外字段，这对于整体的存储来说不是特别重要，在这里就不详细展开了。在这个存储方案中，可以直接从起始点开始遍历相邻边的所有数据，读取性能是非常高的。 array

数组存储劣势

这种存储需要处理的一个比较棘手的问题，就是数组变长的情况。这里的变长是由很多因素导致，比如两个点可能属性数量不一样，属性本身如果是字符串，长度也会不一样。属性长度不一样会导致每条边的存储空间也不一样，这样在边文件中就不能用一个简单的数组来进行寻址了。如果仅仅是属性导致的变长，还是有比较简单的解决方案的，比如可以把属性单独的再放到另一个存储文件中，这样点文件和边文件里面的内容，是不是定长的呢？其实也不一定，因为每个点上边的数量也是不一样的，所以在边文件里面，每个点触发的边序列的总长度也是不一样的。所以还是要处理数组变长的问题。

处理变长

解决思路一般是两种：

  • 一种是使用额外的一个 offset 的记录，相当于是用一个偏移量记录，来记录每一个点或者边的起始位置。这个记录本身就可以是定长的了，因为它是个 offset 值。或者是提前划分好一些额外的区域，来预留给它增长的空间。
  • 为了解决这种数组存储变长的问题，我们自然也可以想到用类似链表的方式来存储。在链表方式的存储模式中，点和边全部存的都是 ID，包括点 ID、边 ID、属性 ID 等等。通过属性 ID ，可以在另外一个属性存储里面找到它的位置以及具体的值。因为存的都是 ID，所以每个点和每条边的数据长度就是固定的了。通过 ID 可以直接计算出偏移量，然后用偏移量的位置去读取数据。所以每个数据本身也不需要保存自身的ID，因为偏移量的位置是能够反推出来自身 ID 的。

linklist

链表存储

这是一个链表存储下进行边迭代的例子: 假设有一个起始点 A，需要迭代它的所有边。首先在点文件中找到点 A 的首个边，α。然后去边文件中找到 α 对应偏移量的位置，就可以读出这条边的数据。可以看到，是一个从点 A 到点 B 的边，A 是一个起始点，我们就去找起始点下一条边的 ID，就找到边 θ。然后去边 θ 的位置，找到偏移量，就找到边 θ。这里我们看到它是一个 C 到 A 的边，A 是终止点。我们就去找终止点的下一条边，是 ω。再去找到边 ω 的位置，看到是起始点 A 终止点 D，通过这样的方式就可以不断地去迭代边。 迭代边

我们看到，用链表存储的方式很好地解决了数组变长的问题，因为新增边的时候，只需要新增固定长度的结构组成链表即可。每一次迭代也是在 O(1) 的时间内直接找到了下一条边，也不依赖于外部的索引或者其它结构。

链表存储的劣势

这看似是一个比较好的方案，但实际的使用中，也存在着一些问题。不要忘记，现在讨论的是一个存储格式，而不是一个内存结构。存储格式意味着最终是要在磁盘 IO 上进行读写的。在链表存储方案下，每一次边迭代的时候，由于边 offset 的位置是随机的，所以会有大量的随机读操作。而磁盘对于随机读操作并不是很友好。 所以虽然这里理论上的迭代邻居找到下一条边的复杂度是 O(1)，但 O(1) 的单位时间是磁盘随机读的时间，而不是顺序读的时间，这两者在性能上是会有非常大的差别的。所以使用这种链表的存储方式，通常来说会依赖一个非常高效实现的缓存机制，需要把大量的磁盘数据放到内存缓存中来读，在内存中进行随机访问的性能就会提升很多。 除了基于数组和链表的方法，还有其它一些格式可以实现 O(1) 时间的边迭代。比如，使用 LSM-Tree 的存储结构，这个结构是一种顺序写盘多层结构的 KV 存储。这里只简单介绍一下它的工作原理。

LSM 存储

lsm 这个图忽略了像写 WAL 这样的细节，是 LSM 树读写的核心操作流程。 LSM 树是一种常用的键值存储结构，处理写请求的性能很高。它的读写操作流程如下：当一个请求进来的时候，直接写入内存中的一个 MemTable，如果 MemTable 没写满，就直接返回请求。因此它处理写请求的性能是很高的。当 MemTable 满的时候，会生成一个不可写的、只读的 Immutable MemTable，同时生成新的可写的 MemTable，以供后续使用。然后 Immutable MemTable 就会写到磁盘上，形成一个 SST 文件。SST 文件在写盘的时候，会根据 Key 排序，从而实现顺序的边迭代。其落盘结构的 SST 文件也是分层来组织的。从内存中直接写出来的第 0 层达到一定数据量大小的时候，或者触发某种条件的时候，就会进行一个归并排序，归并排序就是一个 Compaction 的过程。合并出来的第一层的 SST 文件，都是按照 Key 的顺序写排的。读取的时候是先去内存中的 MemTable 查找，找到了就返回，如果没有找到就去第 0 层的 SST 文件中查找，找不到再去第 1 层，这样逐层查找，一直到找到需要读取的 Key 为止。

使用 SST 文件进行存储的一个关键就是设计边的 Key。因为在 SST 文件中，Key 是有序排列的，所以我们需要通过 LSMTree 来实现免索引连接的能力。关键点就是合理地设计边的 Key，使一个点所有边在排序后是相邻的。说起来比较拗口，其实实现起来并不难。

我们看一下这个例子。只要把边 Key 的最高位放起始点 ID，那么后面无论是边的其它什么信息，都可以让从起始点 ID 出发的边自然地排序排在一起。这里也可以加入一个编号的字段，因为两点之间，起始点和终止点 Meta 这些是固定的，编号字段加入之后，就可以支持在两点之间同类型的多条边共存。因为这是一个 KV 结构。如果只有起始点、终止点和 Meta，两点之间同类型的边只能存在一条。所以比如转账交易或者是访问记录这些具有事件性质的边要存多条，可以加一个编号。当然也不一定都是必须从起始点开始来做边的 Key。 lsm-key

比如在例 2 中，把 type 边类型放在高位。它就可以先以 type 进行划分，后面才是起始点。这种方法也比较适合在分布式场景下按类型做分片，这样同一类型的边就会排在相邻的分片中，有利于提高分布式查询的性能。使用这个方式，有非常高的写入性能，并且读取的时候也能提供免索引连接的能力。

  • nebula 点 nebula-lsm-vertex
  • nebula 边 nebula-lsm-edge
  • nebula 解读 nebula-complete-edge

上图以最简单的两个点和一条边为例，起点 SrcVertex 通过边 EdgeA 连接目的点 DstVertex，形成路径(SrcVertex)-[EdgeA]->(DstVertex)。这两个点和一条边会以 6 个键值对的形式保存在存储层的两个不同分片，即 Partition x 和 Partition y 中，详细说明如下：

  • 点 SrcVertex 的键值保存在 Partition x 中。
  • 边 EdgeA 的第一份键值，这里用 EdgeA_Out 表示，与 SrcVertex 一同保存在 Partition x 中。key 的字段有 Type、PartID（x）、VID（Src，即点 SrcVertex 的 ID）、EdgeType（符号为正，代表边方向为出）、Rank（0）、VID（Dst，即点 DstVertex 的 ID）和 PlaceHolder。SerializedValue 即 Value，是序列化的边属性。
  • 点 DstVertex 的键值保存在 Partition y 中。
  • 边 EdgeA 的第二份键值，这里用 EdgeA_In 表示，与 DstVertex 一同保存在 Partition y 中。key 的字段有 Type、PartID（y）、VID（Dst，即点 DstVertex 的 ID）、EdgeType（符号为负，代表边方向为入）、Rank（0）、VID（Src，即点 SrcVertex 的 ID）和 PlaceHolder。SerializedValue 即 Value，是序列化的边属性，与 EdgeA_Out 中该部分的完全相同。

EdgeA_Out 和 EdgeA_In 以方向相反的两条边的形式存在于存储层，二者组合成了逻辑上的一条边 EdgeA。EdgeA_Out 用于从起点开始的遍历请求，例如(a)-[]->()；EdgeA_In 用于指向目的点的遍历请求，或者说从目的点开始，沿着边的方向逆序进行的遍历请求，例如例如()-[]->(a)。

如 EdgeA_Out 和 EdgeA_In 一样，NebulaGraph冗余了存储每条边的信息，导致存储边所需的实际空间翻倍。因为边对应的 key 占用的硬盘空间较小，但 value 占用的空间与属性值的长度和数量成正比，所以，当边的属性值较大或数量较多时候，硬盘空间占用量会比较大。

  • nebula 的存储如何迭代边 NebulaGraph 的点和边在同一个 partition，虽然没有存在同一个 key-value 中，但是永远在同一个地方，所以：
  1. 遍历1hop的出入边（不需要点属性信息的时候），就是一个 prefix scan（只需要给边上左边的那个 id ，两个方向的边都能高效扫出来，边多存了一次换来这里）
  2. 获取点与边的属性的情况下，prefix scan 之后获取了点边信息，在用点边的vertex id, get_value(key_of_id)

LSM 的劣势

首先是读性能，在读的时候，如果内存没有命中，下面是一个逐层的 SST 文件，去找 Key 的最坏情况，可能要把所有层的 SST 文件全部找完，才能找到合适的 Key。所以它的免索引连接是比较依赖于Compaction 操作的。只有在理想情况下，比如在一个完整的 Compaction 完成的情况下，它才能真正实现免索引连接，否则会在各个 SST 文件内部去查找。在整体上，它并没有完整地达到不去利用其它结构就能够进行快速的领域迭代。

而做 Compaction 又是一个有比较大的磁盘 IO 的操作，并且如果使用的是第三方的存储结构，那么做 Compaction 的操作是不受图数据库本身控制的，可能是由一些其它的机制触发的，比如是在前台负载压力比较大的情况下触发了 Compaction，这样实际在使用的时候会出现一些瓶颈，所以必须要对第三方存储进行比较深度的改动，才能够更好地优化。

optimize

可以看到，各种实现免索引连接的存储方式都不是一劳永逸的，而是有各自的优势和短板。通过数组的方式读取速度快，但是写入因为涉及到变长的问题，可能会比较慢。通过 LSM 树的方式写入速度快，但是读的时候又依赖于 Compaction 操作，在 Compaction 没有完成的情况下，它的读取速度也比较慢。通过链表的方式读取和写入速度都不占优，但是它的灵活性却最高，因为它是以 offset 形式的指针来实现的。

在实际商业图数据库的实现过程中，需要根据设计理念去做取舍。也可以结合两种或者多种方案的优点，在不同的数据形式下，灵活地实现不同类型的存储。还有一些其它的问题，比如分区分片、反向边一致性、如何支持事务、数据索引怎么做、数据过期等等，都是要解决的问题，实现起来还是比较复杂的。