小红书图数据库多跳查询性能实测：时延降50%

REDgraph 如何将图数据库的多跳查询延迟降低 50% 以上？

在小红书的业务体系里，多跳查询是一项关键的数据洞察能力，为推荐、风控和电商等场景提供了支撑。但这类查询往往有一个不小的挑战：很难同时兼顾稳定的 P99 时延。基础架构存储团队针对这个问题，基于大规模并行处理（MPP）的思路，开发了一套图数据库上的分布式并行查询框架。这个方案把多跳查询的时延降低了 50% 以上，特别是让原本在在线场景中“用不了”的 3 跳查询，正式落了地。

本文的核心贡献在于：从框架层面提出了一种优化多跳查询时延的方案，既让在线场景中使用多跳查询成为可能，也在技术上实现了图数据库查询的框架级优化。

我们将从以下几个方面展开讨论：

• 小红书使用图数据库的背景，以及多跳查询在实际业务中因为时延过高而受到的限制；
• 深入分析 REDgraph 的架构，点出原有查询模式中存在的不足和可优化的环节；
• 详细阐述优化方案，并分享部分实现细节；
• 通过性能测试，验证优化措施的实际效果。

01 背景与挑战

1.1 图数据库在小红书的使用场景

小红书作为一个社区属性很强的产品，覆盖了多个领域，鼓励用户通过图文、短视频、直播等形式记录和分享生活点滴。在社交场景中，存在着用户、笔记、商品等多种实体，它们之间构成了复杂的关系网。为了高效处理这些实体间的一跳查询，小红书自研了图存储系统 REDtao，以满足极致性能的需求。

面对更复杂的多跳查询，我们又自研了图数据库系统 REDgraph，并将其应用于多个业务领域：

• 社区推荐：利用用户间的关系链和分享链，推荐可能感兴趣的好友、笔记和视频。这类推荐通常涉及多于一跳的复杂关系。
• 风控场景：通过分析用户和设备的行为模式，识别可能的欺诈行为（如恶意薅羊毛），保护平台不受滥用和作弊行为的侵害。
• 电商场景：构建商品与商品、商品与品牌之间的关联模型，优化商品分类和推荐，提升用户的购物体验。

在传统的 SQL 产品（如 MySQL）中，想实现这类多跳查询，往往需要在一条语句里写多个 JOIN，性能可想而知。键值存储 KV 产品虽然能实现，但需要分多次发送 get 请求，并自行处理中间结果，实现起来也比较麻烦。相比之下，图数据库的设计理念天生就适合处理这类查询。在图数据库中，数据表被抽象为顶点，表之间的关系被抽象为边，边作为一等公民被存储和处理。这样一来，执行 n 度关系查询，只需要查询 n 次边表，大大简化了查询过程，也提高了效率。

1.2 业务上面临的困境

虽然小红书在社交、风控及离线任务调度等场景中都采用了图数据库，但在实际应用中，却遇到了一些棘手的挑战。

场景一：社交推荐

在社交推荐中，我们希望能及时地把用户可能感兴趣的好友或内容推送给用户。例如，如果用户 A 关注了用户 B，而用户 B 点赞了笔记 C，那么用户 D（也点赞了笔记 C）就可能成为用户 A 的潜在好友，让小红书的社交网络建立更丰富的连接。业务当然可以使用离线任务分析，基于结果进行推荐，但社交图谱无时无刻不在变化，基于离线分析做出的推荐往往是滞后的。如果能推荐得更及时，就能更好地抓住潜在的用户关系，建立更完善的社交图谱，赋能其他业务（如社区兴趣小组、电商商品推荐）。业务希望能在用户当下使用时，即时推送可能感兴趣的“好友”或“内容”。如果即时推荐能实现，就能有效优化用户体验，提升留存率。然而，由于之前 REDgraph 在某些方面的能力还不够完善，导致三跳时延比较高，所以业务一直以来都只采用了一跳和两跳查询。

场景二：社区生态与风险控制

小红书致力于促进社区生态的健康发展，会对优质内容创作者给予奖励。然而，这也吸引了部分作弊用户想“薅羊毛”。例如，他们可能会通过组织点赞来提升低质量笔记的排名，把低质笔记伪装成优质笔记以骗取奖励。风控业务需要识别并防范这种行为。借助图数据库的多跳查询，可以构建出一个以用户和笔记为顶点、点赞为边的复杂关系图（“用户 -> 笔记 -> ... -> 用户 -> 笔记”）。然后，对每篇笔记查询其多度关系（笔记 -> 用户 -> 笔记 -> 用户）中作弊用户的比例。如果比例高于某个阈值，就给这篇笔记打上作弊标签，系统便不再对作弊用户和作弊笔记发放奖励。打标行为通常是实时消费消息队列去查询图数据库，如果查询动作本身比较慢，就会导致整体消费积压。比如，一个查询任务应该在 12:00 执行，但由于性能问题直到 12:10 才开始触发，那么在这十分钟的延迟里，一篇劣质笔记可能已经被当作优质笔记，作者成功“薅羊毛”。等到发现这是作弊用户时，损失已经造成了。

具体来说，社交推荐场景要求三跳的 P99 低于 50 毫秒，风控场景则要求三跳的 P99 低于 200 毫秒。这是目前 REDgraph 面临的一大难题。为什么一到两跳可行，三跳及以上就难以实现呢？我们基于图数据库与其他系统在工作负载上的差异，做了一些难点与可行性分析。

1.3 难点与可行性分析

首先看并发方面，OLTP 的并发度很高，而 OLAP 则相对较低。图的三跳查询，服务的仍然是在线场景，并发度也相对较高，这一点更贴近 OLTP 场景。其次看计算复杂度，OLTP 场景中的查询语句比较简单，包含一到两个 JOIN 操作就算比较复杂的了，所以计算复杂度相对较低。OLAP 则是专门为计算设计的，计算复杂度自然较高。图的三跳查询介于两者之间，虽然不像 OLAP 那样需要执行大量计算，但访问的数据量比 OLTP 要多不少，因此属于中等复杂度。第三看数据时效性，OLTP 对时效性要求很高，必须基于最新的数据提供准确且实时的响应。而在 OLAP 场景中，时效性要求就没那么高，早期的 OLAP 数据库通常提供 T+1 的时效。图的三跳查询，因为服务的是在线场景，对时效性有一定要求，但并不高。使用一小时或 10 分钟前的状态进行推荐，也不会产生太严重的后果。因此，我们把它定义为中等时效性。最后看查询失败的代价，OLTP 一次查询的成本较低，所以失败的代价也低；OLAP 由于需要消耗大量计算资源，失败代价很高。图查询在这方面更像 OLTP，能容忍一些失败，但因为访问的数据量较大，查一遍的代价稍高，也归属到中等。

总结一下：图的三跳查询具备 OLTP 级别的并发度，却又有比一般 OLTP 大得多的数据访问量和计算复杂度，所以很难在在线场景中使用。好在它对数据时效性的要求没那么高，也能容忍一些查询失败，所以我们可以尝试优化。另外，正如上文指出的，在小红书业务场景中，三跳查询的首要目标是降低延迟。有些系统会考虑牺牲一点时延来换取吞吐的大幅提升，但这在小红书业务上是不可接受的。如果吞吐上不去，还可以通过扩大集群规模来兜底；但如果时延高，就直接不能用了。

02 探索与优化之路

2.1 REDgraph 架构

REDgraph 的整体结构与当前比较流行的 NewSQL（如 TiDB）类似，采用了存算分离 + shared-nothing 的架构。它包含三类节点：

• Meta 服务：负责管理图数据库的元信息，包括数据模式（Schema）、用户账号和权限、存储分片的位置信息、作业与后台任务等。
• Graph 服务：负责处理用户的查询请求，包括查询的解析、校验、优化、调度、执行等环节。它本身是无状态的，方便弹性扩缩容。
• Storage 服务：负责数据的物理存储，架构分为三层。最上层是图语义 API，将 API 请求转换为对 Graph 的键值（KV）操作；中间层采用 Raft 协议实现共识机制，确保数据副本的强一致性和高可用性；最底层是单机存储引擎，使用 rocksdb 来执行数据的增删查等操作。

2.2 图切分方式

图切分的意思是说，如果拥有一个庞大的图，规模在百亿到千亿级别，应该如何把它存储在集群的各节点中。在工业界，主要有两种典型的切分策略：边切分和点切分。

边切分以顶点为中心，每个顶点会根据其 ID 进行哈希运算，并路由到特定的分片上。每个顶点上的每条边在磁盘中都会被存储两份，一份与起点位于同一分片，另一份与终点位于同一分片。点切分则相反，以边为中心做哈希打散，每个顶点会在集群内保存多份。

这两种方式各有利弊。边切分的优点是每个顶点与其邻居都保存在同一个分片中，查询某个顶点的邻居时，访问局部性极佳；缺点是容易负载不均，由于节点分布不均匀，可能引发热点问题。点切分则正好相反，负载比较均衡，但每个顶点会被切成多个部分，分配到多台机器上，容易出现同步问题。REDgraph 作为一个在线的图查询系统，选择了边切分方案。

2.3 优化方案 1.0

之前我们做过一些优化，可以称为方案 1.0。当时主要考虑的是如何快速满足用户需求。方案包括：根据常用的查询模式提供一些定制化的算法，这些算法可以跳过解析、校验、优化和执行等繁琐步骤，直接处理请求，实现加速。此外，我们对每个顶点的扇出操作进行优化，在向外扩展时限制扩展数量，避免超级点的影响，降低时延。我们还完善了算子下推策略，例如 filter、sample、limit 等，让它们尽可能在存储层完成，以减少网络带宽消耗。同时，我们还允许读从节点、读写线程分离、提高垃圾回收频率等优化。

然而，这些优化策略有一个共性，就是每个点都比较局部和零散，通用性较低。比如，第一个优化，用户如果发起新的查询模式，之前编写的算法就无法满足需求，需要另行编写。第二个优化，如果用户需要的是顶点的全部结果，那这项优化也不再适用。第三个优化，如果查询中不存在这些运算符，自然也无法进行下推。诸如此类，通用性较低，因此需要寻找一种更通用、能减少重复工作的优化策略。

2.4 新方案思考

我们对一个耗时接近一秒的三跳查询进行了 profile 分析。结果发现，在每一跳产出的记录数量上，第一跳至第二跳扩散了 200 多倍，第二跳至第三跳扩散了 20 多倍。体现在结果上，需要计算的数据行数从 66 条直接跃升至 45 万条，增长速度惊人。此外，三跳算子在整个查询过程中占据了很大比重，在查询层的耗时更是占了整个查询的 80% 以上。

那么，应该如何优化呢？在数据库性能优化方面，有很多方案，主要分为三大类：存储层的优化、查询计划的优化以及执行引擎的优化。由于耗时大头在查询层，所以我们重点关注这里。查询计划的优化是一个无止境的工程，用户可能写出各种查询语句，产生各种算子，很难找到一个通用且可收敛的方案来覆盖所有情况。执行引擎则可以有相对固定的优化方案，因此我们优先选择了优化执行引擎。

图数据库的核心就是多跳查询执行框架，因为数据量大、计算量大，导致查询时间较长。我们借鉴了 MPP 数据库和其他计算引擎的思想，提出了分布式并行查询的解决方案。

2.5 原多跳查询执行流程

原有的多跳查询执行流程，可以这样理解：假设要查询 933 顶点的三跳邻居节点 ID，即检索到蓝圈中的所有顶点。经过查询层处理后，会生成一个执行计划。START 表示计划的起点，本身没有实际操作。GetNeighbor 算子负责实际查询顶点的邻居，例如根据 933 找到 A 和 B。后续的 Project、InnerJoin 以及 Project 等操作，都是对先前产生的结果进行数据结构的转换、处理及裁剪，确保整个计算流程顺利进行。正是后续这些算子耗费了较高的时延。

2.6 可优化点分析

那么，问题到底出在哪里？

2.6.1 Barrier 等待增加时延

从物理执行过程可以看出：查询节点必须等所有存储节点的响应返回后，才会执行后面的算子。这样一来，即使大多数存储节点很快返回，只要有一个“慢存储节点”存在，整个查询都得阻塞。在图计算（AP）场景中，一次计算往往要经过很多轮迭代（Epoch），每轮迭代后都需要进行全局指标更新，更新完再继续下一轮迭代，这种在 Epoch 之间插入 Barrier 同步的做法是必要的。但在图查询（TP）场景中，通常不需要全局性更新，只是在下发请求时对起点 ID 做去重，即使有，也往往是在查询的最后一步，因此没有必要设置 Barrier。此外，图数据库负载往往呈现“幂律分布”现象，少数顶点邻居边多，多数顶点邻居边少；REDgraph 本身也是以边切分方式存储数据，这就使得“慢存储节点”很容易出现。再加上某个存储节点的网络抖动或负载高等因素，响应时间会更长，进一步影响查询效率。如果查询层收到一个响应就处理一个（类似于 pipeline 机制），就能避免无意义的空等，从整体上加速查询。

2.6.2 查询层串行执行效率低

在整个查询计划中，只有 GetNeighbor 算子是在多个存储节点上并行执行的，其他算子都是在查询节点上串行执行。这带来两个问题：串行执行的效率天然低于并行执行，只有在数据量太少或计算逻辑太简单的情况下，上下文切换的开销才会超过并行收益。而在正常负载的图查询场景中，数据量和计算逻辑都相当可观。此外，当多个存储节点的响应数据汇聚到查询节点时，数据量仍然很大。如果能在 Storage 节点上完成这些计算，将显著减少查询节点需要处理的数据量。

业务线上的集群和性能测试显示：GetNeighbors 和 GetVertices 并不是所有算子中最耗时的，反倒是不太起眼的 Project 算子常常耗费更多时间，特别是那些紧随 GetNeighbors 和 GetVertices 之后的 Project 算子，因为它不仅要执行数据投影，还负责将 map 展平。这表明整个查询的主要瓶颈在于计算量大。而查询计划中大部分都是纯计算型算子，将它们并行化对于提升查询效率很有必要。

2.6.3 查询结果转发浪费 IO

如前所述，在图查询场景中一般不需要做全局性更新。查询节点收到各存储节点的响应后，只是简单地再次分区然后下发，所以存储节点的结果转发到查询层，再从查询节点分发到各存储节点，这个过程比较浪费。如果存储节点自身具备路由和分发的能力，那可以这样：存储节点执行完 GetNeighbors 算子后，接着执行 Project、InnerJoin 等算子，每当遇到下一个 GetNeighbor 算子时，自行组织请求并分发给其他存储节点。其他存储节点收到后接着执行后面的算子，以此类推，直到最后一步将结果汇聚到查询层，统一返回给客户端。

2.7 改造后的执行流程

改造之后，查询服务器（Query Server）会将整个执行计划以及所需的初始数据传输到存储服务器（Store Server），之后由 Store Server 自身来驱动整个执行过程。以 Store Server 1 为例，当它完成首次查询后，会根据结果 ID 所在的分区，将结果转发到相应的 Store Server。各个 Store Server 可以独立地继续进行后续操作，从而实现整个执行动作的并行化，没有同步点，也无需额外转发。需要说明的是，图中右侧白色方框比左侧要矮一些，这是因为数据由上方转到下方时，进行了分区下发，数据量比在查询服务器上接收到的总数据量要少。可以看到，各部分独立驱动后，没有出现等待或额外转发的情况，Query Server 只需要在最后一步收集各个 Store Server 的结果并聚合去重，然后返回给客户端。这样一来，整体时间比原始模型显著缩短了。

03 实现细节与关键挑战

3.1 如何保证不对 1-2 跳产生负优化？

一个很现实的问题是：改造过程中，如何确保不影响原有的 1-2 跳查询？在企业内部进行新改造和优化时，必须谨慎评估，不能让新方案还没带来收益，反而破坏了原有系统。因此，总体架构与原来保持一致。在 Store Server 内部插入了一层，称为执行层，具有网络互联功能，主要用于分布式查询的转发。Query Server 层则基本保持不变。这样，当接收到用户的执行计划后，可以根据跳数选择不同的处理路径。对于 1 到 2 跳，沿用原有流程（原有的流程能满足业务需求），而 3 跳及以上则采用分布式查询。

3.2 如何与原有执行框架兼容？

原有代码中每一个操作都是用算子方式实现的。为了让分布式并行查询与原有框架兼容，我们把“转发”也定义成一个算子，取名为 Forward。这个算子的功能类似于 Spark 中的 Shuffle 算子，或 OceanBase 中的 Exchange 算子，关键在于它能确保查询在分布式环境中顺畅执行。

我们对查询计划进行了以下关键改写：

• 在每个需要“切换分区才能执行”的算子前（例如 GetNeighbors、GetVertices 等），我们添加一个 FORWARD 算子。FORWARD 算子负责记录分区的依据，通常是起点 ID。
• 为了将分布式节点的查询结果有效汇总，我们在查询计划的末端添加了 CONVERGE 算子，它指示各节点将结果发送回 DistDriver 节点（即最初接收用户请求的节点）。
• 随后，我们引入了 MERGE 算子，它对所有从节点收到的结果进行汇总，并将最终结果返回给客户端。

通过这种方式，当 REDgraph-Server 准备执行 GetNeighbors、GetVertices 算子时，会先执行 FORWARD、CONVERGE 算子，将必要的数据和查询计划转发到其他服务器。其他服务器收到请求后，就能明确自己的任务和所需数据，从而推动查询计划执行。

值得注意的是，FORWARD 和 CONVERGE 算子都有“转发/发送”数据的含义，但侧重点不同：FORWARD 强调路由转发，需要指定转发的依据（即 partitionKey 字段），不同的数据行会根据 partitionKey 字段值的不同转发到不同的节点；CONVERGE 强调发送汇聚，具有单一确定的目标节点（DistDriver）。因为它们只是做转发/发送工作，我们统称为“路由”算子。

在改造后的查询计划中，从 START 算子开始，直到遇到“路由”算子，这多个算子可以在某个节点本地执行。因此，我们将这一系列算子划分到一个 stage 内。整个查询计划由多个 stage 组成，首尾两个 stage 在 DistDriver 上执行，中间的 stage 在 DistWorker 上执行。需要注意的是，stage 是一个逻辑概念，具体执行时，每个 stage 会依据分区和所属节点产生多个 task，这些 task 会分布在多个节点上执行，每个节点只访问本节点内的数据，无需跨网络拉取数据。这种结构化的方法极大地提高了查询的并行性和效率。

3.3 如何做热点处理？

在原查询模式中，每次发起 GetNeighbors 算子前，查询层会对起点 ID 去重（查询计划中 GetNeighbors 算子的 dedup 为 true），收到存储节点的响应后，再依靠后续算子将结果按需展平，因此存储节点不会产生重复查询。举个例子：原查询模式的执行流程是，第一跳从存储层查到 A->C 和 B->C，返回到查询层；查询层 Project 得到两个 C，准备做 InnerJoin；准备执行第二跳时，构造起点集合，由于 dedup 为 true，仅保留一个 C；第二跳从存储层查到 C->D 和 C->E，返回到查询层；查询层执行 InnerJoin，因为此前有两个 C，所以 C->D 和 C->E 也各变成两个；查询层再次 Project 取出 dstId2，得到结果 D、D、E、E。可以看到，存储层不会产生重复查询。

改造为分布式查询后，我们只能在每个 stage 内去重。但由于缺乏全局 barrier，多个 stage 先后往某个 DistWorker 转发请求时，多个请求之间可能有重复的起点，会在存储层产生重复查询和计算，导致 CPU 开销增加和查询时延增加。如果每一跳产生的重复终点 ID 很多，分布式查询反而会带来劣势。

为了解决这个问题，我们引入了一套起点 ID 去重机制——NeighborCache。具体方案是：因为没有全局 Barrier，无法在下发请求之前去重，我们选择在存储节点上提供一个 NeighborCache，本质上是一个 map，可表示为 map。在执行 GetNeighbors 算子前，存储节点会首先检查 NeighborCache，如果找到了相应的条目，就直接使用这些数据填充结果集；如果没有找到，就访问存储层获取数据，并更新 NeighborCache。读取和更新 Cache 需要用读写锁做好互斥。此外，NeighborCache 还有以下特点：

• 每当有更新 vid + edgeType 的请求时，都会先 invalidate cache 中对应的条目，以此保证缓存与数据的一致性。
• 即使没有更新操作，cache 内的每个 kv 条目存活时间也很短，通常为秒级，超过时间就会被自动删除。为什么这么短？从充分性来说，在线图查询（OLTP）的特性决定了用户的多跳查询通常在几秒到十几秒内完成，而 NeighborCache 只是为了去重而设计，来自不同 DistWorker 的 GetNeighbors 请求大概率不会相隔太久到达，所以 cache 本身也不需要存活太久。从必要性来说，从 map 结构的 key 就能发现，当 QPS 较高、跳数多、顶点邻居边多时，这个 map 要承载的数据量非常大，所以也不能让存活时间太长，否则容易 OOM。
• 在填充 cache 前会做内存检查，如果本节点当前的内存水平已经比较高，则不会填充，避免节点 OOM。

通过这种起点 ID 去重机制，我们可以有效减少重复查询，提高分布式查询的效率和性能。

3.4 如何做负载均衡？

负载均衡包括存储的均衡和计算的均衡。首先，存储的均衡在以边切分的图存储里面其实是很难的，因为这种设计天然就把顶点和其邻居都存到了一起，这是图数据库相比其他数据库的优势，也是要承担的代价。目前没有一个彻底的解决方法，只能在遇到问题时扩大集群规模，让数据的哈希打散更均匀一些，避免多个热点落在同一台机器上。从目前的业务场景来看，负载不均衡的现象并不算严重，例如风控的一个比较大的集群，磁盘用量最高和最低的也不超过 10%，所以问题并没有想象中那么严重。另一个优化方法是在存储层及时清理过期数据，清理得快也能减少一些不均衡。

计算均衡方面，存储层采用了三副本策略。如果业务能够接受弱一致的读取（实际上大多数业务都能接受），我们可以在请求转发时，查看三副本中哪个节点负载较轻，把请求转发到该节点，尽量平衡负载。此外，正如前文所述，热点结果缓存也是一种解决方案，只要热点处理速度足够快，计算的不均衡现象就不容易显现。

3.5 如何做流程控制？

在分布式查询架构中，由于取消了全局 Barrier，各个 DistWorker 自行驱动查询进行。这种设计提高了灵活性，但也带来新的挑战：各个 DistWorker 上 stage3 的结果需要汇聚到 DistDriver 后才能返回给客户端，但是 DistDriver 只在 stage0 的时候给 Node2 发送了请求，后面的所有转发都是由 DistWorker 自行完成的，脱离了 DistDriver 的“掌控”。这样一来，DistDriver 就不知道最后有多少个节点在执行 stage3，也就不知道该等待哪些 DistWorker 发送结果，以及何时可以开始执行 stage4。

为了解决这个问题，我们引入了一个进度汇报机制：在 DistDriver 上实现一个 Acker，负责接收各个 DistWorker 上报的 stage 执行进度信息。每个 stage 向外扩散时，向 Acker 发送一条消息，记录当前完成的 stage 和即将开始的 stage 的节点数量。具体来说，包含两个键值对：

• 当前的 stage 编号 -> -1；
• 下一个 stage 的编号 -> 执行下一个 stage 的节点的数量。

例如，Node2 上的 stage-1 扩散到 stage-2 时，目标节点有 3 个：Node1、Node3、Node5，于是就发送 {stage-1: -1，stage-2: 3} 的消息到 DistDriver，表示有一个节点完成了 stage-1，有 3 个节点开始了 stage-2。由于 stage-1 此前由 Node1 登记过 {stage-1: 1}，这样一正一负就表示所有的 stage-1 都已经执行完毕。stage-2 和 stage-3 的更新和判定方式类似，当 DistDriver 发现所有前置 stage 数量都为 0 时，就可以驱动 stage-4。

我们实际想要的是每个 stage 数量的正负抵消能力，而不是 {stage-1: -1，stage-2: 3} 这样的字符串。为了简化这个过程，我们采用异或运算（相同为 0，相异为 1）来跟踪各个 stage 的状态。举例说明：

1. Acker 上有一个初始的 checksum 值 0000；
2. stage-0 在扩散到 stage-1 时，生成了一个随机数 0010（这里用 4 位二进制数表示），这个 0010 是 Node2 上的 stage-1 的 Id，然后把这个 0010 随着 Forward 请求发到 Node2 上，同时也发到 Acker 上，表示 0010 这个 stage 开始了。Acker 把收到的值与本地 checksum 做异或运算，得到 0010，并以此更新本地 checksum；
3. stage-1 执行完后扩散到 stage-2 时，因为有 3 个目标节点，就生成 3 个不同的随机数 0101、0001、1010（需要检查这 3 个数异或之后不为 0），分别标识 3 个目标节点上的 stage-2，然后把这 3 个数随着 Forward 请求发到 Node1、Node3、Node5 上，同时在本地把自身的 stage Id（0010）和这 3 个数一起做异或运算，再把运算的结果发到 Acker。Acker 再次做异或运算，也就是 0010 ^ (0010 ^ 0101 ^ 0001 ^ 1010），这样 0010 就被消除掉了，也就表示 stage-1 执行完成了；
4. 重复上述过程，最后 Acker 上的 checksum 会变回 0，表示可以驱动 stage-4。

需要注意的是，尽管在某个节点的 stage 扩散时检查了生成的随机数异或不为 0，但多个节点间生成的随机数异或到一起还是可能为 0。比如 Node1 的 stage-2 生成的 3 个数异或后为 0001，Node3 的 stage-2 异或后为 0010，Node5 的 stage-2 异或后为 0011，0001 ^ 0010 ^ 0011 = 0。这样就会导致 stage-3 还在执行中时，DistDriver 就误认为它已经执行完毕，提前驱动 stage-4 的执行。不过考虑到实际使用 int32 整数，出现这种情况的概率非常低。在未来的优化中，我们可以考虑给每个 Node 生成一个 16 位的随机 Id（由 metad 生成），并保证这些 NodeId 异或结果不为 0，当 stage 扩散时，将 NodeId 置于随机数的高位，确保分布式查询的每个阶段都能被准确跟踪和协调。

另一个重要的问题是全程链路的超时自检。例如，在 stage2 或 stage3 的某一个节点上运行时间过长，不能让其余所有节点一直等待，因为客户端可能已经超时了。因此，我们在每个算子内部的执行逻辑中都设置了一些埋点，用来检查算子的执行是否超过了用户侧的限制时间。一旦超过，就立即终止自身的执行，迅速自我销毁，避免资源浪费。

04 性能测试与效果

改造工程完成后，我们进行了性能测试。采用 LDBC 组织提供的 SNB 数据集，生成了一个 SF100 级别的社交网络图谱，规模达到 3 亿顶点，18 亿条边。主要考察了一跳、二跳、三跳、四跳等多项查询性能。

测试结果显示：在一跳和二跳情况下，原生查询和分布式查询性能基本相当，没有出现负优化。从三跳起，分布式查询相比原生查询实现了 50% 到 60% 的性能提升。例如，在 Max degree 场景下，分布式查询已将时延控制在 50 毫秒以内。在带有 Max degree 或 Limit 值的情况下，时延均在 200 毫秒以下。虽然数据集与实际业务数据集存在差异，但都属于社交网络领域，所以仍具有参考价值。四跳查询，无论是原始查询还是分布式查询，时延基本上都在秒到十余秒的范围。因为四跳查询涉及的数据量实在太大，已经达到百万级别，仅靠分布式并行查询难以满足需求，还需要其他策略。但即便如此，我们提出的改进方案相比原始查询模式仍能实现 50% 到 70% 的提升，效果非常可观。

05 总结与展望

在相对较短的时间内，我们基于 MPP 理念，对 REDgraph 在分布式并行查询方面进行了深入探索和实践。这个方案能够显著优化多跳查询的性能，对业务逻辑完全兼容，没有使用限制条件，属于框架级的通用优化。测试结果显示，时延降低了 50% 以上，满足了在线业务场景的时延要求，验证了方案的有效性。

目前，很多公司的图数据库产品在在线场景中仍只使用两跳及以下的查询，因为多跳查询的时延无法满足在线业务的需求，导致失去了很多潜在的业务价值，也未能充分发挥图数据库的技术优势。随着小红书 DAU 的持续增长，业务数据规模朝着万亿级递增，业务上替代方案的瓶颈会逐渐显现。我们计划在今年上半年完成开发工作，下半年开始将这套新架构逐步应用于相关业务场景。

这个方案虽然针对的是图数据库，但其探索实践对公司其他数据库产品也有重要的参考价值。例如，REDtable 在处理用户请求时，经常需要应对复杂或计算量大的查询，以往会建议用户修改代码来适应。现在，我们可以借鉴这个方案，为这些“具有重查询需求”的产品打造高性能执行框架，增强自身的数据处理能力。我们将继续提升 REDgraph 的多跳查询能力，并将其与 REDtao 融合，打造成统一的数据库产品，赋能更多业务场景。

来源：互联网