跳到主要内容
分离式内存事务系统全景调研

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

拆解 DM 上的索引（hash / B+tree / learned / LSM）、版本管理（单版本 vs MVCC）、版本表布局与 GC 协调。每条主线列代表论文 + SOTA + 仍未解的部分

DM 事务 索引 MVCC B+tree Hash LSM 调研

事务系统的两根支柱是索引和版本管理。在单机数据库这两个问题已经研究了 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 linebucket 64Bleaf 节点 chunkblock tablerecord 头
避 atomic写时少 atomichierarchical locklog-onlymasked CAS（合 op）
本地缓存bucket cache内部节点 cachebloom 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）
Insert1-2 RTT
Delete1-2 RTT

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

2.4 Hash 的局限：不支持范围查询

⭕ 互补：hash 不能做 WHERE key BETWEEN A AND B。这种查询需要 B+tree 或 LSM。

3. B+tree 索引：Sherman

3.1 B+tree 在 DM 上的核心挑战

   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

不同层级用不同锁策略：

层级锁策略理由
RootRDMA atomic全局共享
Internaloptimistic改动少
LeafOCC改动多

优化 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 的性能数字

WorkloadLookup 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 性能数字

WorkloadRTT备注
朴素 B+tree5 RTT
Sherman1-2 RTT加 cache
XStore0-1 RTTlearned 模型在 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 性能特征

操作代价
Write1 RTT（memtable 内）+ 周期 flush
Read1-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无必须
隔离SRSI / SR
复杂度低高

6.4 派系归属（DM 系统）

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

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 KTPS240 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 策略
FaRMepoch-based（epoch 过期后版本可清）
Motorwatermark + CN 报告
通用做法后台 worker 周期性 GC

9.3 工程经验

⭕ 互补：实战中长事务很少（OLTP 通常 < 100ms 事务）→ GC 一般不是瓶颈。只有长 OLAP 混在 OLTP 里时 GC 才成问题。

🌟 结论：GC 是 DM MVCC 仍未完美解决的问题——但工程上有 acceptable 的解。

✅ 自我检验清单

  • DM vs 单机：能用 RTT 数字解释 DM 数据结构慢 100×
  • 4 条优化原则：能列出（减 RTT / cache line / 避 atomic / 本地缓存）
  • RACE 设计：能描述 64B bucket + 4 slot 布局
  • Sherman 3 个优化：能列出 wide B / hierarchical lock / CN cache
  • Sherman 性能：能说明从 30µs 压到 5µs 的关键
  • XStore learned：能描述 ML 模型如何减少 RTT
  • SMART LSM：能说明 compaction 在 CN 侧的设计
  • 单版本 vs MVCC：能列出 4 个 trade-off 维度
  • MVCC 三大问题：能默写版本布局 / 快照 / GC
  • Motor masked CAS：能描述同时操作多字段的语义
  • Motor 牺牲：能解释为什么 Motor 比 FORD 慢 5%
  • GC 困难：能列出 3 个 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 参考