使用 Rails 高效处理数据库树遍历
最近，我们在 Rails API 中解决了一个有趣的性能问题：执行树遍历时的性能优化。
我们有一部分代码是用于对数据库架构进行三方合并（3-way merge）。为了实现这一点，我们需要在两个架构之间计算一个合并基准（类似于 Git！）。
在我们的 Rails API 中，我们会跟踪每个 PlanetScale 数据库架构的更改。这些更改被称为“架构快照”（Schema Snapshot），类似于 Git 提交（commit），记录特定时间架构的状态。每个快照可以有一个或两个父节点。当合并分支时，我们会对每个变更的历史记录执行广度优先搜索，直到找到两个分支的共同祖先，这个祖先就是合并基准（Merge Base）。
如下图所示，合并基准是两个分支的交汇点：
- 一个分支执行了
alter table teams操作 - 另一个分支执行了
alter table users，之后还有create table payments操作。
按逐步方式运行的效率问题
在寻找合并基准时，需要检查两个分支历史中的每个快照。
通常来说，这个操作很快，因为大多数数据库只有少数几次更改。然而，对于那些有数千个更改的情况，就会遇到性能问题。我们在遍历树的过程中对每一步操作都执行数据库查询，而即使每次查询都很快，仅网络传输时间就会迅速累积起来。
示例数据库查询如下：
select * from schema_snapshots where id = 20; select * from schema_snapshots where id = 21; select * from schema_snapshots where id = 22; select * from schema_snapshots where id = 23; select * from schema_snapshots where id = 24; // *还有数千次查询*
解决 N+1 问题
这是一个典型的“**N+1 性能问题**”。每个处理步骤都会触发另一个查询。
通常，在 Rails 中修复此类问题相对简单——可以使用 includes 方法预加载所需的数据。然而，由于数据结构的特殊性，常规的预加载技术在这里不起作用，因此我们必须研发新的解决方案。
内存缓存解决方案
首先，我们创建了一个用于存储快照的内存缓存。这是一个临时的缓存，仅用于查找合并基准。使用内存的重要性在于，我们的主要性能问题是由大量的网络请求造成的。
class SnapshotMergeBaseCache
attr_reader :store, :hits, :misses
def initialize
@store = {}
@misses = 0
@hits = 0
end
def get(id)
if @store[id]
@hits += 1
return @store[id]
end
@misses += 1
add(SchemaSnapshot.find(id))
end
def add(node)
@store[node.id] = node
end
end
这个内存缓存使用一个简单的哈希结构，其中快照的 id 作为键，快照数据作为值。
add方法用于将快照添加到缓存中。get方法用于从缓存中检索数据，并统计命中次数（hits）和未命中次数（misses）。我们使用这些统计数据来了解代码在生产环境中的效果。
预加载缓存
有了内存缓存后，下一步是将快照批量加载到缓存中。幸运的是，在寻找合并基准时，快照的历史记录是很容易预测的。我们可以预加载每个分支的最近 X 个快照，大幅减少返回数据库查询的次数。
cache = SnapshotMergeBaseCache.new from_branch.recent_snapshots.limit(FROM_PRELOAD_COUNT).each do |snap| cache.add(snap) end into_branch.recent_snapshots.limit(INTO_PRELOAD_COUNT).each do |snap| cache.add(snap) end
现在，当运行广度优先搜索时，我们可以使用 cache.get(id) 查找下一个节点。在多数情况下，这能命中缓存，避免网络请求，从而解决性能问题。
推出与测试
对代码进行这样的改动可能会很复杂，通常实际效果和预期之间会有很大差距。
首先，我们需要确保新方法的正确性。我们运行了一些测试，用旧方法和新方法分别计算合并基准，在数千个数据库上进行比对。这让我们确信新代码能返回正确结果。
接着，我们通过**功能开关（Feature Flags）**逐步推出新代码路径，并记录其性能数据。命中与未命中统计数据帮助我们调整预加载快照的数量。经过几轮迭代优化后，我们向所有客户发布了新方案。
其他解决方案
添加内存缓存只是解决这个问题的一种方法。由于部分数据库需要遍历的快照较多，这种方案对我们来说效果最佳。此外，这种方案可以简单地叠加到现有代码中，而不需要大量改动，降低了上线风险。
数据库递归 CTE
一种解决方案是让数据库来完成工作。这可以通过**递归公共表表达式（Recursive Common Table Expression, CTE）**实现。在这种方式下，数据库会沿着记录指针逐步查询，直到找到共同的合并基准。
物化路径
物化路径（Materialized Path）是一种在 SQL 数据库中表示图的技术。它通过在一个列中存储关系历史，例如 "20/19/15/10/5/3/1"，以表示从当前节点到根节点的路径。使用这种方法，可以通过检查两个节点的历史记录来找到共同的祖先。
这个方案对于节点数量有限的树结构非常适合。然而，在我们的场景中，存储数千个关系使此方法不太可行。
关注公众号：程序新视界，一个让你软实力、硬技术同步提升的平台
除非注明，否则均为程序新视界原创文章，转载必须以链接形式标明本文链接
