LDBC SNB 系列：深入理解 Benchmark 的 Query 生成和执行

继上文的 LDBC 数据生成🔗之后，在这一篇我们主要介绍 SNB Workload 里的各个 Query 是如何生成的，以及在性能测试中 Driver 是如何执行 Workload。

Workload

在基准测试的准备阶段之后，总共生成了三类数据：

• Dataset：用于初始导入的数据
• Update Streams：用于 Driver 在性能测试阶段实时更新
• Parameters：用于 Driver 在性能测试阶段读请求的参数

写请求 Write Query

由于 SNB 生成的数据非常复杂，因此在性能测试阶段不可能通过 SNB Driver 实时生成更新请求，因此实时更新的数据实际是由 DataGen 来生成的。我们在上一篇也提到过，使用 LDBC 时 DataGen 需要指定生成多长时间的数据，以及社交活动是从哪一年开始。DataGen 会根据时间戳将所有数据进行切分，将 90% 数据作为 Dataset，剩下的 10% 数据作为 Update Streams 用于后续更新的写请求。

对于所有写请求，DataGen 都会将这次写请求（Update Query）调度执行的时间、相关更新的参数生成到一个 JSON 中。（至于为什么需要指定 Query 调度时间，我们后续会解释）

读请求 Read Query

SNB 的读请求分为两大类：14 个 Complex read-only queries 以及 7 个 Short read-only queries。

Complex 读请求都是以一个给定 Person 出发，查询一跳或者两跳子图内的相关信息。比如 Interactive Complex 9（简称 IC9）的查询 Pattern 如下：给定一个起始的人，查询这个人的朋友或者朋友的朋友创建的最近 20 条消息。如下图所示：

图注：Interactive / complex / 9

Short 读请求分为两大类：一类是给定一个人，查询这个人的姓名、年龄等信息，或者是这个人的朋友以及这些朋友发送的消息。另一类则是给定一个消息，返回这条消息是的发送者以及发送者的相关信息。类似下图这样：

图注：Interactive / short / 1

完整的请求描述可以参见《The LDBC Social Network Benchmark Specification》 的 6.1 和 6.2 章节，这里就不展开了。

请求参数

除了 Dataset 和 Update Streams 之外，DataGen 还会生成不同读请求的参数（比如上面 IC9 的起点 PersonId）。为了保证性能测试的结果能够稳定的衡量数据库的性能，SNB 保证生成读请求的参数满足以下性质：

1.查询时间有上限：Complex Read 和 Short Read 请求所涉及的数据会因为起点不同而不同，但从宏观上看，其查询的子图都是有限的，因此其查询时间也会有一个合理的范围。

2.查询执行时间满足稳定的分布：同一个读请求的各个起点不同，查询数据量会不一样，但最终查询时间分布是稳定的。

3.逻辑计划相同：给定一个查询，无论起点如何不同，最终经过优化器优化之后生成的逻辑查询计划是相同的。这条性质保证每一个查询，能够稳定测试到图数据库中的一些技术难点（比如大量 JOIN、基数估计等）。

其中前两条还比较好理解，但最后一条可能做到吗？我们都知道一个优秀的优化器会根据查询参数决定实际执行时的 JOIN 顺序。即便对于相同的查询 Pattern，由于查询参数不同，最终的执行计划也会千变万化。我们看下** DataGen 是如何筛选参数，使同一个查询最终采用相同的查询计划。**

首先，我们都知道查询数据量和查询时间是强相关的。对于每一个查询 Pattern，LDBC 在设计时都会有一个理想执行计划，在这个理想执行计划中，其数据量是可以通过起点预先计算出来的。

比如 Complex 2：

获取给定某个人的朋友发送的最近 20 个消息，其理想查询计划如下所示。

对于这个理想执行计划，我们可以预处理得到每个起点的 JOIN 的中间结果行数。比如对于 PersonID=1542 的起点，两次 JOIN 的中间结果的数量分别为 60 和 99。最终，对于每个 Query，会生成一个起点和中间 JOIN 结果行数的表，称为 Parameter-Count table。

这个 Parameter-Count table 是由 DataGen 在生成数据过程中一起生成的。有了这张表，挑选参数的问题就变成了在这张表中挑选若干最相近的行。在这一步中采用的方式是贪心的启发式搜索：首先根据 Join1 中间结果数量，挑选最相近的若干行（Join1 中值为 60 的几行），然后在这些行中再根据 Join2 的中间结果数量进行挑选（得到 Join2 值为 99、102、103 的几行），最终筛选出来的 PersonID 为1542、1673、7511。

这里存疑的是，按理来说应该先确定需要挑选参数的个数 k，然后再在 Parameter-Count table 进行筛选，否则按论文所说方法，可能会导致最终挑选的行数小于 k。这里没有深究，但整体思路是合理的。

通过上述步骤，对于每一个 Query 类型，都会挑选出来若干个最相近的参数，从而尽可能使得查询计划相同。不过还剩一个问题，如何确定每个查询需要多少个参数，也就是不同查询的数量呢？

Query Mix

首先，LDBC SNB Interactive Workload 期望数据库在性能测试过程中，**Update Query、Complex Query 和 Short Query **的执行时间比例依次是 10%、50% 和 40%。这个比例一方面是为了模拟真实的社交网络负载，一般来说读请求会远多于写请求，另外这个负载也要能够真实反映数据库的性能。

尽管在上一步中，DataGen 保证了同一个查询中的不同参数的执行时间相近。但不同查询的数据量和执行数据有巨大的差别。因此为了能够避免某一个类型的查询对最终测试结果起决定性作用，不同类型查询的数量需要精心的设计。

SNB Interactive Workload 主要认为 Complex Read Query 应该主导是性能测试分数。Complex Read Query 的数量是由 Update Query 的数量决定的，如下表所示：

比如在 SF100 中每执行 527 个 Update Query 之后应该执行一次 Complex Read Query 9。前面提过，每个 Update Query 的调度时间由 DataGen 已经决定了，因此每一个 Complex Read 的调度时间也就确定了。这里可以暂时将调度时间理解为相对于性能测试开始时间的一个相对时间，这个相对时间实际还会受到 SNB Driver 相关参数的影响。之所以是调度时间而不是执行时间的原因在于待测数据库可能已经满负载或者没有响应，导致某个 Query 可能已经到了调度时间，但无法及时执行 Query。

这里就可以理解为什么 SNB 号称其测试结果可重复，关键之处就是 DataGen 生成的数据是确定性的。一旦 Update Query 调度时间确定，也就确定了 Complex Read Query 的调度时间，进而确保其性能测试结果可重复。了解这一点对于后续理解性能测试的结果以及 SNB Driver 的相关参数是至关重要的。

而 Short Query 会被穿插在每一个 Complex Query 之后。前面提到过 Short Query 分为两大类，查询人的相关信息以及查询消息的相关信息。准确来说，不同类型的 Complex Query 可能会返回不同信息，根据 Complex Query 的查询结果，后续会从 Short Query 中挑选一类，并把 Complex Read 的结果（比如 Person 或者 Message 的标识符）作为 Short Query 的参数进行查询。

一个 Short Query 被调度之后，后续有可能会调度另一个 Short Query，每次概率逐渐降低。即一个 Complex Query 之后，可能调度一连串 Short Query（论文中称为 Short Read Random Walk）。不同的 Query 后面可能触发的 Short Query 类型不同，如下表所示，比如 IC10 之后就只能触发 IS1、IS2 和 IS3。

图注：IC 为 Interactive Complex query 的缩写，IS 为 Interactive Short query 的缩写

和 Complex Query 不同的时，Short Query 的调度时间是由 Driver 根据它所依赖的 Complex Read 的完成时间所动态决定的。但触发多少个 Short Query 就是由上面说的概率决定，而所有性能测试过程中使用的随机生成器是相同的，综上所述整个基准测试过程中所有 Query 的比例和顺序是确定的。

**Driver **

Driver 依赖 DataGen 生成的 Dataset、Update Streams 和 Parameters，它主要能完成两个任务：

• Validate：校验数据库的正确性
• Benchmark：验证数据库的性能

Validate 比较简单，根据 Update Streams 和 Parameters，生成若干用于校验的参数，为了验证数据库的结果正确性，Validate 依赖于确定的顺序执行查询，因此只能单线程执行。Driver 最终会在数据库输出是否通过验证的结果。

Benchmark 则是根据 Dataset、Update Streams 和 Parameters 以及相关配置，生成确定的 Workload（即一个 Operation 序列，其中包含 Query 和对应调度时间）。根据调度时间，按顺序发送给待测数据库，同时保存其调度时间、开始执行时间和结束执行时间，最终输出性能报告。

Driver 主要由 Runtime、Workload、Database Connector、Report 这几部分组成。

Runtime & Workload

无论最终性能测试在什么环境、待测图数据库是什么，只要 Driver 的输入（数据和配置）相同，其生成的 Workload 就是相同的。为了得到最高的吞吐量，一般会把 Workload 拆成多个 Stream。对于图来说，多个操作是有前后依赖关系的，比如好友存在才能添加好友关系。因此，Driver 支持由多个线程来执行这个序列（由 thread_count 参数控制），但也需要保证即便有多个线程来执行，操作之前的依赖关系没有被破坏，仍然满足 DataGen 生成的调度时间关系。这部分原理就不展开介绍，感兴趣的可以阅读论文中的相关部分。

Workload 中的每个 Operation 包括以下信息：

• Query 类型

• Query 参数

• 调度时间

• 期望结果（只在 Validate 中使用）

前面提到过所有 Update Query 和 Complex Query 的调度时间都是 DataGen 预先确定好的，Driver 会根据调度时间通过 Database Connector，把 Query 发送给数据库执行。显然，如果这些调度时间都是一个固定值，我们是无法获知数据库的真实性能的。

在 Driver 中有一个参数 time_compression_ratio（默认为 1），可以在时间维度上拉伸或者压缩整个 Workload，比如 time_compression_ratio 为 2.0 代表这个 benchmark 的运行持续时间会变成默认的两倍，也就是将 Query 之间的间隔时间变为原来的两倍。同理，time_compression_ratio 为 0.1 代表 Driver 发送 Query 的速度是默认情况下的 10 倍。简而言之：

• time_compression_ratio > 1，比默认慢
• time_compression_ratio < 1，比默认快

注意，修改 time_compression_ratio 不会影响 Query 序列中各个类型 Query 的比例、Query 的参数和执行顺序。

Database Connector

为了将数据库对接至 SNB，厂商需要实现对应的 Database Connector。其主要任务就是对接目标数据库：

1.将 Driver 框架的 Query 类型和参数，转换为目标图数据库的 Query 2.将 Query 通过 Database Connector 发送给目标图数据库 这部分都只需要实现 Driver 的若干接口即可，可以参考：**https://github.com/ldbc/ldbc_snb_interactive_v1_driver **以及相关集成文档。

Driver Configuration

Benchmark 的主要目的就是在保证大于 95% 的及时率前提下，得到最优的 time_compression_ratio（越小代表性能越高）。Operation 如果在期望调度时间过后的 1 秒之内被 Driver 调度，就认为是及时的：

actual_start_time − scheduled_start_time < 1 second

此外，一次有效的 Benchmark 需要至少需要测试两个小时（预热的半个小时期间，性能是不计入在结果之内）。

为了运行一次有效的 Benchmark，Driver 有几个重要的参数需要调整：

• time_compression_ratio：调整 Workload 的执行速度，准确说是期望执行速度
• operation_count：Driver 总共需要生成多少个 Operation，配合 - time_compression_ratio 修改，以保证 Benchmark 的时长
• thread_count：执行 Operation 的线程池大小，根据待测数据库的性能，可能也需要调整并发执行 Query 的数量

Report

最终 Driver 会生成如下性能指标：

• Start Time：开始时间，第一个 Operation 开始时间
• Finish Time：完成时间，最后一个 Operation 完成时间
• Total Run Time：运行时间，Finish Time 和 Start Time 的差值
• Total Operation Count：Operation 总数，总共执行了多少个 Operation

系统的 QPS 可以通过 Total Operation Count / Total Run Time 得到。

对于每个类型的 Query，Driver 也会输出每个 Query 的总数，执行时间的平均值、中位数、P95、P99等、以及调度时间的延迟分布等。

图注：LDBC 报告示意图

参考文献

有关 LDBC SNB Interactive 的介绍基本就到这了，后续可能还会总结一下这个基准测试的一些设计思想。另外我们自己系统在测试过程中，也出现了一些因为对 SNB 本身不够理解而当时看来十分诡异的现象，这也是花时间总结这几篇文章的初衷。

• ldbc-snb-interactive-sigmod-2015.pdf (ldbcouncil.org)
• The LDBC Social Network Benchmark Specification
• GitHub - ldbc/ldbc_snb_interactive_v1_driver: Driver for the LDBC SNB Interactive workload

关于 NebulaGraph

NebulaGraph 是一款开源的分布式图数据库，自 2019 年开源以来，先后被美团、京东、360 数科、快手、众安金融等多家企业采用，应用在智能推荐、金融风控、数据治理、知识图谱等等应用场景。GitHub 地址：https://github.com/vesoft-inc/nebula