性能优先

此文档主要介绍 TuGraph 性能优先的设计理念。

1.简介

TuGraph目前是世界上最快的图数据库，在图数据库标准评测LDBC SNB Interactive位居榜首（2023.3）。TuGraph的设计基于性能优先，致力于打造高性能的单机图数据库。该文档是TuGraph基于性能优先在存储层的核心设计。

2.图操作的特性

在属性图上的操作涉及读、写及其属性，对一些特殊的属性比如时间戳也访问模式也会影响到整体性能。这里通过对一些图操作特性的规律总结，来指导最终的性能。

我们观察到很多图应用有类似的数据访问模式。例如，在信贷风险控制中，我们使用递归路径过滤搜索多对一模式，以找到可疑的信用欺诈用户和行为。针对网络赌博，可以通过识别短时间内的多笔资金转移，来发现涉赌的资金账号。股权穿透场景对实体间的股权关系进行递归计算。这些场景具有多跳实体和关系访问、时间窗口约束和读写事务等常见模式。 更进一步，从介绍中的讨论和图负载的分析中，归纳出以下特征:

规律一 KHop是图中最典型的操作，它基于点和边的图拓扑的数据访问模式，和关系型数据库有着本质的区别。KHop 的典型性除了表现在数据访问模式不同，它同时也是图数据库最需要关注的性能点。

规律二 图负载的数据访问在拓扑上有一定的局部性，同一个点的边通常会被同时访问。当这些边的标签相同时，有更大的概率会被同时访问。

规律三 图负载在访问点边时，通常会访问其对应的属性，来作为遍历过滤的条件。

规律四 在基于时序的图负载，对点边的过滤通常是在某个时间范围，比如最近的一周。

规律五 写操作可能伴随着大量的读操作，需要在单个事务周期里处理。

通过对实际线上图应用的分析，图负载的读写比率大约为 20:1，虽然场景局限在金融场景，集群数也有限，但涉及的数据规模和用户量非常庞大，具有一定代表性。20:1 的图负载读写比率，说明读工作负载对整体性能的影响更大， 而写工作负载的性能也不能忽视。

3.存储数据结构

TuGraph底层采用B+树来支持实时的增删查改事务。

在排序树的数据结构中，B+树和LSM树为主要代表。B+树在树节点中使用拆分和合并式来更新排序数据，而 LSM 树在日志中追加更新，以进行延迟数据合并。B+ 早期用在文件系统的实现中，通过将数据保存 在自适应长度的叶子节点中，解决硬盘顺序操作和随机操作性能存在数据量级差别的问题，有较均衡的读写性能。LSM 树的主要优势使用 WAL(Write Ahead Log) 进行更新，将更新操作变成顺序操作，在键值较小时性能优势尤为突出。WAL 意味着将数据的更新合并推迟，批量更新能提升综合效率，也使得系统的调度变得复杂。如果更新合并完成前，恰好对其中的数据继续读取，LSM 树就需要读取几个层级局部合并的日志，会导致读取放大和空间放大，从而影响读效率。

总结来说，B+ 树有较好的顺序读写性能，而 LSM 树在数据随机写方面占优。此外 LSM 树采用后台合并的方式，使得性能的波动难以预期，性能波动和上层存储和计算的关联性较弱，增加了整体设计的成本。综上考虑，TuGraph 选用 B+ 树作为读性能优先的实现。

4.数据编码

对于属性图模型而言，除了图拓扑编码外，属性数据也会很大程度影响功能和性能，我们先讨论属性数据如何与拓扑数据共存的编码格式。从目前的调研来看，属性编码有两种方式，我们称之为基于指针索引将属性数据单独存储的离散编码，和将属性数据和拓扑数据打包在一起的紧凑编码。离散编码根据程度的不同，可以每个属性都单独存储，或者每条边的属性打包后各自存储，下面的讨论对两种情况都适用。

点查询。属性编码主要针对边，不涉及点查询。

单边查询。离散编码通过指针定位边，紧凑编码则需要二分查找定位边的位置，离散编码有略微的优势。

边遍历。离散编码在边遍历过程需要不断地进行指针跳转进行随机数据访问，而紧凑编码提前把数据排列在一起，顺序访问的特性使得效率大大提升。 由规律三知对边的遍历操作很普遍，紧凑编码在边遍历的优势明显。

单边更新。离散编码对边的更新仅需找到对应的指针位置，插入数据后修改前后指针指向。紧凑编码则需要对紧凑排列的数据进行重编码，对整个边值进行重新写入，开销显著大于离散编码的情形。

批量边更新。批量更新可以在内存中预先构建点的所有边属性，一次性编码写入，离散编码和紧凑编码相当。但紧凑编码不需要存储指针变量，更少的存储空间效率也会更高。

以上离散编码和紧凑编码在某一类的查询的性能问题，可以通过优化的来缓解。整体上说，由于图负载读写 20:1 的特性，读性能在整体性能中占比更高。以及规律三所揭示的对属性访问的特征，TuGraph 更倾向于采用紧凑编码来保证读性能。其主要弱势为单边更新时重编码的开销，可以用自适应映射的技术来解决。