目录

mace 记录 --- page checkpoint & old version undo

阅读时间约 6 分钟

背景

在 kv_bench 的 W4 测试中发现 mace 的 ops 只有 rocksdb 的 1⁄3 但数据的空间占用确是 rocksdb 的 3 倍(大约 12GB)

先说 old version undo

这个 W4 的测试是 95% 的随机插入 + 5% 的随机查询, 很显然一定是插入哪里太慢了, 于是分析到 Node 的锁上, 虽然负载是随机的但由于样本不是很大,因此 Node 上的锁竞争确实是一个问题, 锁持有范围内还有可见性检查 + WAL记录, 这些都会延长锁持有, 其中可见性检查大部分是小数据的纯内存读, 而 WAL 记录涉及到内存拷贝, 拷贝的数据量和 key-value 大小有关。很明显，WAL 记录就是问题所在，因为对于 update 来说， 记录WAL时不仅要记录新的 value 还需要记录 old value，因为 undo 时会用到 old value

于是优化的思路就出现来了：能不能再 WalUpdate 记录中去掉 old value，而是记录 old value 的 lsn 呢？ 当然可以！ 原因很简单，恢复是从最后的一个 checkpoint 开始的，这意味着在这个checkpoint之前的所有数据都已经持久化了，因此可以在 WalUpdate 的 payload 中存放 old version 即可，然后在恢复时通过在持久化的数据中查找对应 version 的value即可。不过有一点需要注意：gc 不能把这个 old version 的数据给回收掉。这个条件是天然满足的，因为需要 undo 说明事务没有提交，事务没有提交数据就没办法被标记为垃圾

修改很快就完成了，测试发现 WAL 文件的大小确实下降明显，但 W4 测试发现 ops 反而下降了

再说 page checkpoint

前面优化后的 W4 测试结果违反了常识，这说明 W4 的 ops 低下不是单一因素造成的，而是多因素相互影响的！考虑到 mace 在 W4 测试中的数据文件占用太大，这肯定是个问题，而且原因也很清楚：对于随机插入来说，大量的数据会以 delta page 的形式挂在 Node 上，而由于是随机插入，Arena 内部的 recycle 机制的效果就很糟糕，这两者叠加的结果就是 Arena 内部的有效载荷很低，但刷盘是以 Arena 为单位的，因硬盘上的数据文件中绝大部分都是垃圾

那么要如何优化呢？问题是 Arena 的有效载荷低，那么就想办法提高有效载荷，比如把 Arena 的容量调大，这样就更不容易被塞满，从而 delta page 在 consolidate 后Arena 如果还没塞满，那么就可以通过 recycle 回收掉，这样 Arena 中有效载荷就会变多。但问题是：

这个问题的本质是：很快就会失效的delta page 和 不容易失效的 base page 或 delta page 都被绑在了一个容器中，并且“很快就会失效”的时机无法确定。

我们不妨换一种思路，既然 “很快就会失效”的时机无法确定，那我们就找确定的，对于修改的 Node 来说 page table 中 page id 映射到的 addr 是确定的，我们可以通过这个 addr 找到这个 Node 的所有 delta page 和 base page (也包括 sibling page) 至少在我们拿到 addr 的这一瞬间这条链路上的所有 page 都是有效载荷。如果能在这一瞬间做一个快照就好了

dirty page generation

我们确实可以做一个快照！

为了做到这一点，需要对原来的 Pool 进行大改，完全可以去掉 Arena 在 Pool 中直接管理说有的 page，当活跃的 page 的总大小超过配置的阈值时，对当前的写入冻结，新的写入分配到下一代，这里需要一个 RwLock 同步，冻结时获取当前的 txid 作为快照的上界，称为 snap_id 而快照内容就是：上一代所有 page 中能通过 page id 映射的 addr 可达的所有 txid 小于 snap_id 的 page。这里天然的过滤掉了已经持久化的部分，因为它们不再上一代的所有page的集合内

在完成重构后，继续对 W4 进行测试

& abby @ chaos in ~/kv_bench (scale *)
λ /usr/bin/time -f 'maxrss_kb=%M elapsed=%E' ./target/release/kv_bench --workload W4 --threads 4 --key-size 32 --value-size 4096 --prefill-keys 200000 --warmup-secs 3 --measure-secs 5 --read-path snapshot --durability relaxed --path /nvme/mace_bench --no-cleanup
engine=mace workload=W4 mode=mixed durability=relaxed threads=4 total_op=1126183 ok_op=1126163 err_op=20 ops=225226.92 p99_us=32 result_file=benchmark_results.csv
maxrss_kb=2110112 elapsed=0:11.09
& abby @ chaos in ~/kv_bench (scale *)
λ cd /nvme/mace_bench/data/ 
& abby @ chaos in /n/m/data
λ du -sh 
3.4G    .
& abby @ chaos in /n/m/data
λ cd - 
& abby @ chaos in ~/kv_bench (scale *)
λ cd rocksdb/ 
& abby @ chaos in ~/k/rocksdb (scale *)
λ /usr/bin/time -f 'maxrss_kb=%M elapsed=%E' ./build/release/rocksdb_bench --workload W4 --threads 4 --key-size 32 --value-size 4096 --prefill-keys 200000 --warmup-secs 3 --measure-secs 5 --read-path snapshot --durability relaxed --path /nvme/rocksdb_bench --no-cleanup
engine=rocksdb workload=W4 mode=mixed durability=relaxed threads=4 total_op=704695 ok_op=704688 err_op=7 ops=140937 p99_us=64 result_file=benchmark_results.csv
maxrss_kb=1796868 elapsed=0:10.20
& abby @ chaos in ~/k/rocksdb (scale *)
λ cd /nvme/rocksdb_bench/ 
& abby @ chaos in /n/rocksdb_bench
λ du -sh 
3.6G    .

很显然，W4 的测试中在 ops/p99 上 mace 已经完全吊打 rocksdb 了，但这就结束了吗？

现在的问题是什么

mace 为了可靠，在很早就增加了故障注入 （failpoint) 特别是在 crash-safety 方面有很多故障注入。于是 ./prod_test.sh all 就发现了问题： gc_rewrite_* 测试很大概率会出现 Data Corruption 这是绝对不能容忍的错误！

既然我把 old version undo 和 page checkpoint 放在一起（分析过程就省略了），那么肯定是这两者结合的问题。原因很简单：old version undo 依赖已经持久化的 data 文件，这点没问题，问题是 page checkpoint 不会把中间过程的 dirty page 写到 data 文件中，而这些被过滤掉的 dirty page 恰好是 undo 依赖的部分，而由于 WAL 中只记录了 old version 因此在 WAL 中也找不到 undo 依赖的数据

知道了问题就很简单了，要么回滚 old version undo 的修改，要么增加新的机制保证 undo 依赖的数据不会被丢弃。前者的代价是 WalUpdate 需要写两份 value （一份新的一份旧的），后者的代价是

  1. 大量的 dirty page 无法被过滤而导致 page checkpoint 优化效果丢失
  2. 大量的 dirty page 无法被过滤而写到 data 文件中
  3. 大量的 dirty page 无法被过滤导致查询链变长，不得不对这些版本做可见检查，影响查询时延
  4. 新的机制需要pin住 old version 会导致事务路径变长，并需要占用额外的内存
  5. 对于随机更新hot key的场景吞吐下降和磁盘膨胀都明显
  6. 严重影响 WAL checkpoint 的推进，甚至可能造成 WAL 无法回收
  7. …

结果是什么

本着两害取其轻的原则，最终选择了回滚 old version undo 的修改。但这并不是说没有其他办法：1. 目前 mace 的 update 是直接更新到 tree 上的，完全可以先在本地更新在 commit 时做冲突检测然后再更新到 tree 上，这样可以完全不需要 undo。但这样也会带来其他问题，比如：查找需要先查本地再查全局，可见行检测也会变复杂，iterator 也需要 merge 等。2. 除此之外，还可以利用 MVCC 继续保持现在的 steal + no-force 实现，不过利用 MVCC 让 abort 的事务不可见，这样也不需要 undo，这样的确定是可见性检查需要多一层判断，还需要对 abort 的记录进行清理。这些都需要做取舍的

但目前实现，看起来是足够了的

& abby @ chaos in ~/kv_bench (scale *)
λ /usr/bin/time -f 'maxrss_kb=%M elapsed=%E' ./target/release/kv_bench --workload W4 --threads 4 --key-size 32 --value-size 4096 --prefill-keys 200000 --warmup-secs 3 --measure-secs 5 --read-path snapshot --durability relaxed --path /nvme/mace_bench --no-cleanup
engine=mace workload=W4 mode=mixed durability=relaxed threads=4 total_op=852971 ok_op=852956 err_op=15 ops=170589.08 p99_us=32 result_file=benchmark_results.csv
maxrss_kb=2320964 elapsed=0:11.49
& abby @ chaos in ~/kv_bench (scale *)
λ cd /nvme/mace_bench/data/
& abby @ chaos in /n/m/data
λ du -sh 
2.3G    .

2026-04-28 更新，目前已经对 2 实现了一版 no-undo 实测下来结果是要比 master 分支的好一些，但这个测试是“无冲突”的场景，目前仍然不合入到主线中，仅作为后续版本迭代的一个候选方向

Workload Mace wins (ops) ops median ratio (Mace/RocksDB) Mace wins (p99) p99 median ratio (Mace/RocksDB)
W1 (95R/5U, uniform) 16 / 16 2.5x 6 / 16 1.0x
W2 (95R/5U, zipf) 14 / 16 1.6x 14 / 16 0.5x
W3 (50R/50U) 15 / 16 1.7x 10 / 16 0.5x
W4 (5R/95U) 15 / 16 1.6x 8 / 16 0.8x
W5 (70R/25U/5S) 15 / 16 2.6x 16 / 16 0.2x
W6 (100% scan) 16 / 16 5.0x 15 / 16 0.2x