从跳表到 B+ 树:让 Valkey 有序集合更节省内存
有序集合用于描述元素顺序所消耗的内存,可能比存储元素本身还多。
在 Valkey 9.2 中,这种情况改变了:跳表被一种称为 fbtree 的高扇出 B+ 树变体取代。
fbtree 将传统 B+ 树的高扇出和连续存储,与多项针对 Valkey 工作负载和内存分配器设计的优化结合起来,包括基于特征的查找、SIMD 搜索、叶子节点链接,以及顺序插入和弹出操作的快速路径。在一项 500 万成员的测试中,它将每个成员的内存开销降低了 36–43%,最多节省 109 MB。
下面来看看为什么会发生这一变化,以及它是如何工作的。
为什么要替换跳表?
超过 listpack 阈值的大型有序集合由跳表与哈希表共同支撑(较小的有序集合使用紧凑的 listpack 表示,在连续内存中按顺序存储元素)。哈希表提供按成员 O(1) 查找,而跳表提供按排名或分数 O(log n) 的有序查找。这种搭配在架构上很简单,但跳表带来了显著的内存成本。它在每个节点中只存储一个元素,这些节点作为由指针连接的独立分配散布在内存中。
内存开销
Valkey 的跳表为此付出的是实打实的内存。每个节点都有一个后向指针(8B),再加上平均 1.33 层的前向指针和 span 值,因为跳表是概率性的(每个节点有 25% 的概率再增加一层)。每一层需要 8B 的指针加上 8B 的 span 值,因此每个节点大约有 29B 的指针和 span 开销。加上 8B 的分数,在计入成员字符串之前,每个节点的总开销约为 37B。
缓存未命中与依赖访存
现代 CPU 使用硬件缓存层次结构(L1、L2 和 L3)将频繁访问的数据保存在处理器附近。这些缓存比主存(RAM)小得多也快得多,因此当 CPU 无法在其缓存中找到所需数据时,就必须从内存层次中较慢的一层取数据。粗略举例来说,一次 L1 缓存命中大约需要 1 ns,而一次 DRAM 访问大约需要 100 ns。依赖访存会让核心等待;实际延迟以及能隐藏多少工作会因系统和工作负载而异 1。
跳表中的每个节点都是单独的分配,可能散布在堆恰好放置它的任何位置,因此沿着结构前进可能需要反复从互不相关的内存位置取数据。由于每一步都可能决定下一步走向哪里,这些取数彼此依赖,导致在内存层次中往返更多次。一项 2025 年关于并发内存索引的研究发现,在其测试的工作负载上,传统跳表经历的缓存未命中大约是可比较 B 树的 2.4–4.8 倍,吞吐量则低 2–8 倍 2(测试的是不同的数据结构实现,而非 Valkey)。
取代它的是什么:fbtree
B+ 树将条目有序地保存在固定大小的节点中:叶子节点保存条目或指向条目的指针,内部节点只保存恰好足够的路由数据,用于选择要下降到哪个子节点。将许多条目打包进每个节点解决了上述两个问题:每个成员的指针开销少得多,每次查找的依赖访存也少得多。
内存布局
fbtree 是 Feature B+ Tree 的简称,使用 61 路扇出:每个节点最多可容纳 61 个条目或子指针。叶子节点和内部节点的大小经过调整,以适配 jemalloc 的分配类别,在 64 位构建上不会浪费空间;在受支持的 32 位构建上,innerNode 会向上取整到 1280 字节类别。
一个 512-byte 的叶子节点最多容纳 61 个值指针,因此 61 个成员共享一个节点,而不是每个成员各自拥有一个节点。fbtree 不单独存储分值和成员,而是将它们一起存储为单个打包值:规范化的 8-byte 分值后跟成员字节。这将比较所需的数据保持在一起,并消除了另一层指针间接寻址。
更少的内存获取
skiplist 的每层 25% 规则使其有效分支因子约为 4,而 fbtree 的扇出为 61。两种结构都保持 O(log n) 的搜索复杂度,但 B+ 树需要遍历的层数少得多,因此昂贵内存获取的机会也更少。
现代 CPU 在数据连续布局时也能高效地获取若干相邻缓存行,部分原因在于内存访问方式以及硬件预取 1。因此,当一个 B+ 树节点跨越几个缓存行时,CPU 扫描其内容可以高效读取。
优化
在该结构之上,fbtree 还添加了针对特定操作的优化。
在以可变长度字符串为键的 B+ 树中(例如有序集合成员),选择子节点意味着将查找键与每个子节点的锚点(该子节点中最大的成员)进行比较,而读取这些字符串需要付出内存获取的代价。fbtree 的内部节点存储每个锚点以及一个小的 four-byte“特征”。由于锚点通常共享公共前缀,fbtree 将该共享前缀单独存储,并使用四个特征字节来区分子节点。然后,该实现可以使用 SIMD 并行比较这些特征,通常可以在获取子节点本身之前识别出正确的子节点。如果特征能唯一标识一个子节点,搜索可以立即向下进行;否则,它们仍然会缩小需要进行完整二分搜索的范围。
诸如 ZRANGE 之类的范围命令按顺序遍历集合。fbtree 将其叶子节点链接成双向链表,因此扫描可以从一个叶子节点移动到下一个叶子节点,而无需爬回树的上层。skiplist 请求一个项,等待接收它,并且只有在收到第一个项后才知道要获取的下一个项。B+ 树可以并行处理多达 61 个项,并且在处理这些项的同时,它可以获取包含接下来 61 个项的下一个叶子节点。
诸如 ZPOPMIN 之类的命令在集合的两端工作。fbtree 缓存其最左侧和最右侧的叶子节点,因此查找它们是 O(1),与 skiplist 一样,而不是 O(log n)。这使弹出和追加操作保持同等水平,而不会退步。
范围删除会移除一段连续的成员,fbtree 处理它们时无需重建周围结构。
对你来说实际有什么变化
在功能上,没有任何变化。
这一变化是内部的:有序集合命令及其行为保持不变。唯一可见的区别是,对于大型有序集合,OBJECT ENCODING 返回 btree 而不是 skiplist。如果你有监控、测试或工具检查字面字符串 skiplist,那就是需要更新的一个地方。低于 listpack 阈值的小型有序集合无论如何都不受影响,因为它们从一开始就从未使用过 skiplist 编码。
基准测试
内存效率
以下数字仅比较有序索引:skiplist 与 fbtree,而哈希表和成员嵌入保持不变。
顺序插入 500 万个 20-byte 成员,将每个成员的内存开销(不包括成员数据本身)从 50.3B 降低到 28.5B,减少了 43%。同样的 500 万成员以随机顺序插入,将每个成员的开销从 50.3B 降低到 32.
命令性能
下面的基准测试是在 PR #4206 的 oi/pr3-fbtree-v2 分支上测得的,未针对合并后的提交重新运行。测试在配备 64 核的 Graviton3 c7g.metal 系统上运行,使用九个 I/O 线程、流水线深度 10,以及一个 300 万成员的有序集合。每个测试重复五次;除 ZRANDMEMBER 外,所有命令报告的置信区间均 ≤2%。
相同的底层设计变更还提升了几种有序集合操作的吞吐量:
| 命令 | 工作负载 | 吞吐量提升 |
|---|---|---|
| ZADD | 分数更新(全部命中) | +105% |
| ZREM | 50/50 随机添加/删除 | +76% |
| ZCOUNT | 分数范围计数 | +27% |
| ZRANK | 单点排名查找 | +19% |
| ZRANGE | 100 元素排名扫描 | +6% |
| ZRANDMEMBER | 100 个随机样本 | +2% |
| ZSCORE | 单点分数查找 | +2% |
| ZRANGEBYSCORE | 100 元素分数扫描 | +1% |
| ZPOPMIN | 弹出最小值 + 追加新成员 | ~0% |
ZADD 和 ZREM 会在树中重新定位元素,因此它们从 fbtree 更浅的结构和更少的指针更新中获益最多。范围操作获得的提升较小,因为一旦索引遍历变得廉价,生成并返回所请求的元素就会在总成本中占更大比例。ZSCORE 和 ZRANDMEMBER 几乎没有变化,因为它们使用哈希表,而不是有序索引。
在 GA 之前测试 Valkey 9.2
重要结论:命令没有变化,但在我们的测试中,大型有序集合的每成员开销降低了 36–43%,ZADD 和 ZREM 吞吐量分别提升了 105% 和 76%。
目标并不是单纯让数据结构本身更快:该实现通过完整的 Valkey 服务器反复与现有跳表进行基准测试,并不断加入优化,直到 fbtree 在测试过的有序集合命令上与跳表持平或超越跳表。
Valkey 9.2 目前正在进行发布候选测试。在 GA 之前,请