一、RDF 和属性图

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

(相关资料图)

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

以上只是列举了一些常见的分析场景。事实上，关联分析的应用远远不止于这些场景，还有很多其它场景。比如企业的股权穿透分析，公安的安全案情分析，还有生物医药领域的基因分类和新药研发等等，这里就不一一赘述了。

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

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

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

随着行业的发展，我们看到越来越多的可能。知识图谱的表示在逐渐用属性图来完成。今年将正式投票、明年发布的 GQL 标准，也是基于属性图的一个查询语言标准。当然也有少量的图数据库是用 RDF 模型来做的，但是未来更多的新型图数据库都会用属性图模型。

二、图数据库存储的核心目标

不论是用 RDF 还是用属性图，作为一个图数据库，它的核心目标是什么？或者说数据库存储需要解决的一个根本问题是什么呢？那些需要用关联分析的图场景，往往是一些数据规模大、关联跳数深、实时要求高的场景。

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

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

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

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

第一类是使用原生图存储的方式，它的数据存储层就直接实现了免索引连接。上面的处理计算层和业务层都是以完全图的结构来描述，并且也不依赖于第三方存储组件，所以这种实现免索引连接的性能是最高效的。

第二种方式是非原生存储，数据存储层使用的是一个第三方的开源存储组件，但是它在处理过程中实现了近似免索引连接，在大多数情况下也能提供不错的性能。它的问题是由于使用了第三方存储组件，在某些场景下可能做得不是最优化。

第三种方式就是完全非原生的存储，底下可能是一个关系型数据库，或者是一个文档型或者其它类型的数据库，它的存储层其实并不是真正地实现了免索引连接，而是处理成通过索引或者一些其它技术手段，向上表达了一个图模型的查询接口。这种其实只是在接口层上实现了图的一个语义，而底下的存储和计算层都不是完全地使用免索引连接，所以它的性能也会相对低一些。

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

前文中已经明确了数据库存储的核心目标就是实现免索引连接。那么接下来就来看一些具体实现免索引连接的主流技术方案。这里主要介绍不同方案的设计思路，并不局限于某个产品的具体实现细节。

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

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

解决思路一般是两种，一种是使用额外的一个 offset 的记录，相当于是用一个偏移量记录，来记录每一个点或者边的起始位置。这个记录本身就可以是定长的了，因为它是个 offset 值。或者是提前划分好一些额外的区域，来预留给它增长的空间。

为了解决这种数组存储变长的问题，我们自然也可以想到用类似链表的方式来存储。在链表方式的存储模式中，点和边全部存的都是 ID，包括点 ID、边 ID、属性 ID 等等。通过属性 ID ，可以在另外一个属性存储里面找到它的位置以及具体的值。因为存的都是 ID，所以每个点和每条边的数据长度就是固定的了。通过 ID 可以直接计算出偏移量，然后用偏移量的位置去读取数据。所以每个数据本身也不需要保存自身的ID，因为偏移量的位置是能够反推出来自身 ID 的。

这是一个链表存储下进行边迭代的例子。

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

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

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

除了基于数组和链表的方法，还有其它一些格式可以实现 O(1) 时间的边迭代。比如，使用 LSM-Tree 的存储结构，这个结构是一种顺序写盘多层结构的 KV 存储。这里只简单介绍一下它的工作原理。

这个图忽略了像写 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。

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

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

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

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

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

四、Galaxybase 图数据库应用实践

接下来介绍 Galaxybase 图数据库的一些应用实践。

Galaxybase 是创邻研发的国产高性能分布式图平台，它的特点是速度快、高扩展、实时计算，支持一个知识中台，并且安全自主可控。

使用原生分布式并行图存储，实现了存储层的免索引连接，可以毫秒级完成传统方案无法完成的深链分析，较同类技术有数百倍的提升。使用完全分布式的架构，支持动态在线扩容，高效支持万亿级超级大图。也内置了非常丰富的图算法，包括分布式图算法和单机图算法，不需要 ETL 就能实现实时图分析。底层存储包含数据压缩的能力，可以优化资源利用，节省硬件和维护成本。有一个可视化交互的知识中台，便于业务理解和操作，帮助数据价值快速变现。同时也是完全自主可控的，全面兼容国产底层软硬件。

这是 Galaxybase 的架构图，中间部分是整体的核心部分。底层使用了数据分片动态压缩的分布式存储技术，支持属性图的存储模型，并且实现了原生图存储。

存储层之上是计算层，实现了内置的图计算引擎，包含了单机的图算法和分布式图算法，并且还可以由用户来自定义一些定制化函数，来实现自己的高效算法。

再往上是接口层，支持 Java、Python、Go、Rest 的 API。并且可视化的模块也可以以接口的方式嵌入到其它第三方页面中。

左侧可以看到，支持多源异构数据，比如传统关系库、CSV 文件、HDFS、实时流数据等等，都可以直接进行数据导入。

底层适配了各种操作系统，支持各种国产和非国产的主流操作系统。也支持国产的各种 CPU。

在上面可以构建一个图智能中台，包括图工作流管理和可视化分析。在中台之上，可以在各种的业务场景下提供不同的业务解决方案。

Galaxybase 的一个性能优势，是能够高效地进行分布式图计算，并且实现了当前最大规模的图数据处理，实现了 5 万亿超大规模的分布式图存储。在线查询仅使用了 50 台机器的集群，出入度最大有 1000 万的超级节点，6 跳的平均查询时间仅为 6.7 秒。这是与中山大学携手共建的一个图计算项目。

Galaxybase 还具备非常高效的查询性能。在 LDBC 的 SNB 测试里面，去年我们做了一个官方的 Audit，打破了一项世界记录，较之前的吞吐量提升 70%，平均查询性能有 6 倍以上的提升，最高的 95 分位查询性能提升达到 72 倍。

Galaxybase 支持非常丰富的图算法，包括 57 种图算法，其中 28 种已经支持了分布式，其它一些分布式算法也正在实现中。我们也是首家完成信通院图计算评测的一个图计算平台。

我们的产品里面还包括一个图智能中台，主要是通过可视化界面的方式来进行交互式的探索，完成图的一些定性分析，包括搜索顶点、点边位置扩展、查找路径，还有各种混合的布局。布局模式有各种方式混合的搭配，还可以和自定义的地图进行匹配，支持时序演进分析等功能。

Galaxybase 是一款完全国产自主可控的产品。内核的存储、计算、查询的代码完全都是自研的，不依赖于其它第三方开源框架。也完成了各种操作系统和 CPU 的国产信创适配认证，并且获得了信创的一些相关奖项。

我们提供各种图场景的解决方案，有很多合作伙伴，有很多已经在金融、能源、教育、互联网、政府多个行业中的头部客户落地的使用场景，并且已经服务了几年时间。

五、问答环节Q1：针对大 value，比如大于 4K 的数据，随机读取的时候会非常耗 IO，这块有什么优化吗？

A1：一般来说，图数据库里如果是一个属性值，单个属性值大于 4K，其实我们不建议把它放到图数据库中来，因为图数据库主要是做点边的关联邻居查找的。如果单个属性大于 4K，可能是一个很长的文本。在这个上面做图的分析，价值并不大。如果这个是要作为一个存储放进来的话，最好是把它单独放在一个另外的区域中，不要跟点边正常的这些属性来放在一起。

如果指的是点边的结构，可能某一个点的邻居特别多，会就这种超级节点的情况把它存在一起。针对邻居存储的数量非常大的情况，涉及到一个图切分的概念。通常情况下我们更多使用的是一个边切割，所以所有点的邻居都会存在一起，这样能更高效地来访问一个点的所有邻居。

当一个点的邻居数量特别大的时候，这里可能都不只是 4K 量级，可能会有 400M 或者 4G 这样的量级，这种情况下的切割就会形成单个非常大的文件。这种时候也可以考虑动态的点切割的方式，就是把一个点的邻居，再切割成多个存储文件，存储文件可以在不同的分区里，可以在不同的分片下，这样就可以实现并行迭代的方式。

当然这里的技术会更复杂，需要首先有对边进行唯一定位的能力，有这个能力之后，就可以在这一个点的所有邻居边上，再进行进一步的切割，然后把大文件再分成不同的小文件。这也是常见的处理超级节点的一个方式。

Q2：在查询路径时，如果有超级节点，返回所有的路径会不会有问题？一般怎么处理？

A2：这要结合业务需求查询所有路径。比如有的图很大的时候，全部路径的数量会是一个天文数字，那么返回所有路径可能就没有意义了。这时候更好的方式是，要了解我们要路径去做什么。在路径上可能要做一些计算，或者做一些聚合，做一些其它的操作。在做这些计算的时候，就不是简单地返回路径，而是把路径上面的计算也一起做了，得到一个最后的计算结果。如果是路径数量没有那么大的情况下，也是可以逐条返回的。通常我们可以用写输出一个文件或者其它的方式，来返回所有路径。

Q3：底层数据压缩对图性能的影响有多大？

A3：肯定是有影响的，因为压缩毕竟也要占 CPU，所以这其实是个可选项，要看我们的需求是对读写性能更敏感，还是对磁盘空间更敏感。因为也有一些应用，不是实时的情况下，其实对延迟没有那么敏感，但它的数据量可能很大。这时候我们可以通过底层数据压缩的方式来节省磁盘空间。当然，如果是对实时性能要求比较高的情况下，肯定是不压缩，直接读写性能更高。因此可以根据场景来决定。

Q4：怎么做无 ETL 的实时图计算？如果直接从存储层迭代出来的数据怎么解决一致性的问题？如果用 snapshot 就会有 ETL。

A4：可能要这样解释一下我们这个产品，它是存储、计算都包含的，它是自带了存储层和计算层，所以用 snapshot 不需要 ETL 过程，相当于我们自己的计算引擎可以去加载存储里面的数据，也不需要再做一个数据清理或者是转换的过程。可以选择你需要用的一些点边类型或者属性类型做筛选，去生成一个图计算引擎。

一般我们在做一个图计算的时候，其实都是在一个 snapshot 上做图计算，不然整个计算结果也没有一致性。所以我们会加载图存储的某一个时间切片的一个时间点的 snapshot 到图计算引擎中，来做图计算。