第6章：索引、版本与 MVCC —— DM 上数据结构的工程化挑战

事务系统的两根支柱是索引和版本管理。在单机数据库这两个问题已经研究了 50 年——B+tree、hash、ARIES、MVCC——都有成熟答案。但 DM 把硬件假设全换了：远端 DRAM 无 active CPU、单 op 5–10µs RTT、atomic 8B 限制、MN 不主动 GC——这让单机的所有索引和 MVCC 设计都要从头思考。本章把 DM 上索引与 MVCC 的所有主流设计系统梳理：hash 怎么放、B+tree 怎么走 RTT、LSM 怎么 compaction、MVCC 一致版本表怎么协调。读完你应该能拿到 DM 数据结构的”设计目录”。

1. 为什么 DM 上的数据结构必须重新设计

1.1 单机 vs DM：每次访问的代价对比

   单机内存访问                 DM 远端访问
   ──────────────              ──────────────
   ① 检查 cache hit (ns)        ① 准备 RDMA WR (ns)
   ② cache miss → DRAM (50ns)   ② doorbell write (60ns)
   ③ 拿到 record                 ③ NIC 处理 (1µs)
                                 ④ 网络传输 (1-2µs)
                                 ⑤ MN DMA 读 (200ns)
                                 ⑥ 网络回 (1-2µs)
                                 ⑦ NIC 写 CQE
                                 ⑧ CN poll CQE (50ns)
                                 ⑨ 拿到 record
                                 ↑ 总 5-10µs，比单机慢 100-200×

🌟 核心后果：任何 log(N) 次访问的数据结构，在 DM 上都”贵 100×“——B+tree 单点 lookup 在单机 ~100ns，在 DM ~10–20µs。

1.2 DM 数据结构的 4 条优化原则

   原则 1：减少 RTT 数
        ──────────────
        把多个 op 摊到 1 次 RDMA 调用（doorbell batch / co-design 布局）
   
   原则 2：把热路径塞进单 cache line
        ────────────────────────────
        record header / metadata 64B 内 → 1 RDMA READ 拿全部
   
   原则 3：避免 atomic 路径
        ─────────────────────
        atomic 是 IOPS 瓶颈；能用 READ/WRITE 就别用 CAS
   
   原则 4：延迟敏感操作放本地
        ─────────────────────
        index lookup 多次跳转 → 在 CN 侧做缓存

1.3 4 个原则在不同数据结构上的体现

原则	Hash (RACE)	B+tree (Sherman)	LSM (SMART)	MVCC (Motor)
减 RTT	单 RDMA READ → 一个 bucket	跨层 prefetch	倒排合并	inline 版本
单 cache line	bucket 64B	leaf 节点 chunk	block table	record 头
避 atomic	写时少 atomic	hierarchical lock	log-only	masked CAS（合 op）
本地缓存	bucket cache	内部节点 cache	bloom filter	版本快照

2. Hash 索引：RACE

2.1 单机 hash 在 DM 上的问题

   单机 hash lookup
   ────────────────
   1. hash(key) → bucket_idx
   2. 读 bucket
   3. 线性查 bucket 找 key → return record_addr
   ↑ 3 步内存访问 ~100ns
   
   DM 上裸搬过来
   ────────────────
   1. hash(key) → bucket_idx
   2. RDMA READ bucket → CN
   3. 在 CN 里查 → 得到 record_addr
   4. RDMA READ record → CN
   ↑ 2 次 RDMA RTT ~10µs

2.2 RACE 的核心设计（ATC’20）

Open addressing + RDMA-friendly bucket layout：

   RACE bucket（64B = 1 cache line）
   ──────────────────────────────────
   ┌──────────────────────────────────┐
   │ slot_0: key | record_addr        │  16B
   │ slot_1: key | record_addr        │  16B
   │ slot_2: key | record_addr        │  16B
   │ slot_3: key | record_addr        │  16B
   └──────────────────────────────────┘
   ↑ 单 cache line 4 个 slot
   ↑ 1 RDMA READ 64B 拿到 4 个 entry

关键设计：

开放寻址（不是 chaining）→ bucket 大小固定，可预读
slot 数 = cache line / slot 大小 → 一次 RDMA 拿全
碰撞用 linear probing → 简单可预读

2.3 RACE 的性能特征

操作	RTT
Lookup（命中第一个 bucket）	1 RTT
Lookup（碰撞探测多 bucket）	1.X RTT（线性 probing）
Insert	1-2 RTT
Delete	1-2 RTT

🌟 结论：RACE 是 DM hash 索引的”标准答案”——后续 DM 系统几乎都用 RACE 风格。

   B+tree lookup 路径
   ─────────────────
   root → internal → internal → leaf → record
        ↑ log(N) 次跳转，DM 上每跳 ~5µs
   
   总延迟：log_B(N) × 5µs ≈ 30–50µs

🌟 核心问题：深度决定延迟。1B records, B=128 → 高度 ~5 → 单次查找 25µs，比单机慢 250×。

3.2 Sherman 的核心设计（SIGMOD’22）

3 个关键优化：

优化 1：Wide branching factor

把 B 值开大（数百到数千），减少树高：

   单机 B+tree: B=128, 1B records → 高度 5
   Sherman:    B=1024, 1B records → 高度 3
   ↑ 节省 40% RTT

优化 2：Hierarchical lock

不同层级用不同锁策略：

层级	锁策略	理由
Root	RDMA atomic	全局共享
Internal	optimistic	改动少
Leaf	OCC	改动多

优化 3：CN side internal node cache

internal node 改动少 + 反复访问 → CN 侧缓存减少 RTT：

   CN cache hit rate ~99% (TPC-C workload)
   ↑ 实际 RTT 数从 5 → 1.05

3.3 Sherman 的性能数字

Workload	Lookup latency
单机 B+tree	~100ns
朴素 DM B+tree	~30µs
Sherman	~5µs

🌟 结论：Sherman 是 DM B+tree 的当前 SOTA——后续 OLTP 系统都参考它。

3.4 Sherman 的局限

⚠️ 限制：

internal cache 一致性管理复杂（CN 改了 root 时其他 CN 缓存失效）
大写并发下 leaf 锁仍是瓶颈
跨 CN 协调 split / merge 复杂

4. Learned 索引：XStore

4.1 Learned index 的思路

用 ML 模型代替树结构——给定 key，模型直接预测 record_addr。

   Traditional B+tree
   ──────────────────
   key → tree traversal → leaf → record_addr
   
   Learned index
   ──────────────────
   key → ML model → predicted_addr (with error bound)
                  → fix-up search → record_addr

4.2 XStore 的核心设计（OSDI’20）

关键 insight：在 DM 上，learned index 减少了 RDMA 跳转次数——直接预测大致位置，少几次 RDMA READ。

布局：

   XStore 布局
   ──────────────
   - Top-level model（CN 侧缓存）→ 预测大致 leaf_id
   - Leaf-level model（CN 侧缓存）→ 预测 record offset
   - 1 RDMA READ → 拿到 leaf chunk + record

4.3 性能数字

Workload	RTT	备注
朴素 B+tree	5 RTT
Sherman	1-2 RTT	加 cache
XStore	0-1 RTT	learned 模型在 CN

4.4 Learned index 的局限

⚠️ 限制：

需要训练（写多时模型过期）
数据分布变化时退化
数据更新代价高（要重训）

🌟 结论：learned index 在 数据相对稳定 的场景下很强——读密集 OLAP > 写密集 OLTP。

5. LSM-tree：SMART

5.1 LSM-tree 是什么

LSM = Log-Structured Merge-tree。RocksDB / LevelDB / Cassandra 用的存储结构。

   LSM 写路径
   ──────────
   1. Memtable（DRAM）：append
   2. Memtable 满 → flush 到 SSTable Level 0（SSD）
   3. Compaction：合并多个 SSTable，移到下一层
   4. 后台持续 compaction
   ↑ 写顺序、读放大、写放大 trade-off

5.2 LSM 在 DM 上的核心挑战

   DM 上的 LSM 难点
   ─────────────────
   1. Compaction 在哪里做？
      MN: ✗ MN 不能跑代码
      CN: ✓ 但 compaction 要读大量数据，RDMA 代价高
   
   2. SSTable 文件怎么放？
      MN 内存：✗ 太占
      MN PMEM：✓ 但持久化代价
   
   3. Bloom filter 怎么放？
      CN 侧：✓ 可缓存
      MN 侧：✗ 远端查询代价高

5.3 SMART 的核心设计（FAST’24）

Compaction 在 CN 侧：CN 读多个 SSTable → 合并 → 写新 SSTable
Bloom filter 全部 CN 侧缓存：避免每次 lookup 都打 RDMA
Memtable 在 CN 本地 DRAM

   SMART 路径
   ─────────────
   Write:  CN memtable → flush → MN（SSTable）
   Read:   CN bloom filter check → MN（SSTable read）
   Compact: CN reads → merge → CN writes（消耗 RDMA 带宽）

5.4 性能特征

操作	代价
Write	1 RTT（memtable 内）+ 周期 flush
Read	1-3 RTT（bloom filter 命中决定）
Compaction	大量带宽（异步背景任务）

5.5 LSM 的工程局限

⚠️ 限制：

写放大严重（compaction 重写多次）
范围查询需要遍历多个 level
compaction 期间消耗大量 RDMA 带宽

6. 单版本 vs MVCC：架构对比

6.1 单版本架构

   单版本 record 布局
   ─────────────────
   ┌──────────────────────┐
   │ key                  │
   │ lock_word (8B)       │
   │ version (8B)         │
   │ data                 │
   └──────────────────────┘
   ↑ 一个 record 只有一个版本
   ↑ 写时持锁 → 读阻塞

适合：写多 + 短事务（OLTP 主流）。

6.2 MVCC 架构

   MVCC record 布局（version chain）
   ─────────────────────────────────
   ┌──────────────────────────────┐
   │ key                          │
   │ ┌──────────────────────────┐ │
   │ │ v_n:   ts=42 | data_n    │ │ ← latest
   │ │ v_n-1: ts=40 | data_n-1  │ │
   │ │ v_n-2: ts=38 | data_n-2  │ │
   │ │ ...                      │ │
   │ └──────────────────────────┘ │
   └──────────────────────────────┘
   ↑ 多个版本共存
   ↑ 读取选择 ≤ ts 的最大版本 → 不阻塞

适合：长事务 + 读密集 / SI 隔离。

6.3 关键 trade-off

维度	单版本	MVCC
内存	低	高（多版本）
写阻塞读	是	否
GC	无	必须
隔离	SR	SI / SR
复杂度	低	高

6.4 派系归属（DM 系统）

派系	系统
单版本	FaRM, FORD, AURA-baseline
MVCC	CREST（cell-level + write_ts + 一致快照）, Motor（一致版本表）
MVCC	Motor

7. MVCC 在 DM 上的核心问题

7.1 三大核心问题

   问题 1：版本表布局
        ──────────────
        inline（在 record 内 chain）
        vs
        out-of-line（独立 version 区）
   
   问题 2：一致快照（snapshot）
        ──────────────────────
        如何让所有 CN 看到同样的"过去某时刻"
        → 全局 timestamp
   
   问题 3：GC 协调
        ────────────────
        谁来删除无人引用的老版本
        → CN 主导（MN 不参与）

7.2 问题 1：版本表布局

Inline（FaRM 思路）：

   单 record 内有 N 个版本槽
   ──────────────────────
   优点：1 RDMA READ 拿全部历史
   缺点：record 大（固定大小，浪费）

Out-of-line（Motor 思路）：

   record 头指向版本表
   ──────────────────
   record:   header → version_table_addr
   version table: chain of versions
   ──────────────────
   优点：record 小，灵活
   缺点：2 RDMA RTT（先读 header，再读 version table）

7.3 问题 2：一致快照

思路：每个事务有 snapshot ts，读到所有 ≤ ts 的最大版本。

   Tx_A starts at ts=100
   ───────────────────────
   Tx_A reads record_X:
     找到 v with ts ≤ 100 → 选最大 ts 的版本
   Tx_A reads record_Y:
     同样选 ts ≤ 100 的版本
   ──────────────────────
   ↑ 整个事务看到一个"时间快照"

Motor 的 ts 来源：epoch + lease（不是 TrueTime）。

7.4 问题 3：GC

版本何时可以删？

   v 可以删 ⟺ 没有 active 事务的 snapshot ts ≥ v.ts

但 MN 不知道”哪些事务还 active”——必须 CN 协调：

周期性收集所有 CN 的 active ts
找到全局最小 active ts → 称 watermark
删除所有 ts < watermark 的版本

⚠️ 挑战：长事务会永久 hold version——版本累积。

8. Motor：DM MVCC 的当前 SOTA

8.1 Motor 的核心创新

一致版本表（Consistent Version Table）：

   Motor 设计
   ─────────────
   - 版本表 inline 在 record（小固定大小，超出溢出）
   - 用 masked CAS 同时验证多个字段
   - epoch + lease 作为全局 ts

8.2 Masked CAS 在 Motor 中的作用

   record 8B header
   ────────────────
   ┌──────┬────────┬───────┬─────────┐
   │tx_id │epoch   │version│ flags   │
   │16b   │16b     │16b    │ 16b     │
   └──────┴────────┴───────┴─────────┘
   
   Masked CAS：只比较/修改 epoch + version 字段
   ↑ 一个 atomic 同时做：
     - 验证 (epoch == expected)
     - 验证 (version == expected_version)
     - 更新 (version → new_version)

8.3 Motor 性能数字

指标	FORD（单版本）	Motor（MVCC）
单事务延迟	~10µs	~12µs
TPC-C 吞吐	250 KTPS	240 KTPS
TPC-C SR	✓	✓
TPC-C SI	✗	✓
Snapshot 读	✗	✓

关键：Motor 牺牲少量吞吐（5%）换 SI 支持——值得。

8.4 Motor 的局限

⚠️ 限制：

锁仍在 MN（atomic IOPS 瓶颈未解）
长事务仍会 hold version（GC 限制）
版本溢出后处理复杂

🌟 结论：Motor + AURA 合体（MVCC + 锁分离）是开放方向。

9. 版本 GC 的工程困境

9.1 GC 的三个困难

   困难 1：MN 不主动 GC
        ──────────────
        MN 没有 CPU 决定哪些版本可删
   
   困难 2：CN 协调代价高
        ────────────────
        每个 CN 报告 active ts → 全局协调
   
   困难 3：长事务卡住 GC
        ─────────────────
        一个长事务 ts=100，老版本一直不能删

9.2 不同系统的 GC 策略

系统	GC 策略
FaRM	epoch-based（epoch 过期后版本可清）
Motor	watermark + CN 报告
通用做法	后台 worker 周期性 GC

RACE (Zuo et al., ATC’20) —— Hash 索引
Sherman (Wang et al., SIGMOD’22) —— B+tree 索引
XStore (Wei et al., OSDI’20) —— Learned 索引
SMART (Luo et al., FAST’24) —— LSM-tree
Motor (Wu et al., OSDI’24) —— DM MVCC

综述

Modern B-Tree Techniques (Graefe, 2011) —— B+tree 经典
The Log-Structured Merge-Tree (O’Neil et al., 1996) —— LSM 原创
Concurrency Control and Recovery in Database Systems (Bernstein et al., 1987) —— MVCC 经典

相邻领域

RocksDB：单机 LSM 参考
PostgreSQL MVCC：单机 MVCC 参考

搜索