深入 Kudu 存储引擎：一行数据从 MemRowSet 到 DiskRowSet

Kudu 存储引擎 MVCC LSM Raft 源码分析

Kudu 最值得研究的地方，不是“支持 UPDATE 的列式存储”这句话，而是它如何把两种冲突的访问模式放进同一个 Tablet：新数据要低延迟写入，分析查询又希望读取紧凑、按列编码的数据；更新不能重写整列文件，历史版本还必须对快照读可见。

解决办法不是某一种神奇数据结构，而是一组分层结构：MemRowSet 接住新行，DiskRowSet 提供列式基线，Delta Store 承载更新，WAL 与 Raft 负责持久性和复制，MVCC 决定每个快照能看到什么。

本文基于 Kudu 1.18.1 源码，文件路径均相对于 src/kudu/。

Tablet 才是存储与一致性的边界

一张 Kudu 表先按 Hash 和 Range 规则切成 Tablet。每个 Tablet 管理一个连续主键范围，并由 Raft 副本组复制。Tablet Server 上的 tablet::Tablet 是本地存储核心，它并不是一个单独文件，而是以下对象的集合：

Tablet
├── 当前可写 MemRowSet
├── 若干只读 MemRowSet（正在或等待 Flush）
├── RowSetTree
│   └── 多个 DiskRowSet
│       ├── Base Data：按列保存的基线数据
│       ├── DeltaMemStore：内存中的更新
│       ├── Redo DeltaFiles：较新的变更
│       └── Undo DeltaFiles：较旧版本的反向变更
├── MvccManager
├── TabletMetadata
└── 行锁与操作状态

源码入口主要在：

  • tablet/tablet.h、tablet/tablet.cc
  • tablet/memrowset.h、tablet/memrowset.cc
  • tablet/diskrowset.h、tablet/diskrowset.cc
  • tablet/deltamemstore.h、tablet/deltamemstore.cc
  • tablet/delta_store.h
  • tablet/mvcc.h、tablet/mvcc.cc

RowSetTree 用主键区间索引 DiskRowSet。查询或更新给出编码主键后，不必逐个扫描全部 RowSet，而是先找出键范围可能相交的候选集合。

写入并不是先写 MemRowSet 再写 WAL

从客户端看，一次写入只是 KuduSession::Apply()。进入 Tablet Server 后，它会经历更长的状态机：

sequenceDiagram
    participant C as 客户端 Session
    participant S as TabletServerService
    participant L as Raft Leader
    participant W as WAL
    participant F as Followers
    participant T as Tablet
    participant M as MVCC
    C->>S: 批量写入 RPC
    S->>L: 预处理、行锁、分配时间戳
    L->>W: Group Commit
    L->>F: Replicate
    F-->>L: 多数副本确认
    L->>T: Apply 到 MRS / DMS
    T->>M: Commit 时间戳
    L-->>C: 返回写入结果

这里有两个顺序不能混淆。

第一，Kudu 的写入先进入 Raft 复制流程。Leader 不是改完 MemRowSet 才考虑副本，而是把操作作为 Replicate 消息进入一致性日志。consensus/consensus.cc、consensus/log_cache.cc 和 log/log.cc 共同完成排队、WAL 追加与副本复制。

第二，操作被复制和提交之后，才成为可稳定恢复的状态。Tablet 的内存结构是执行结果，不是唯一事实来源；崩溃恢复时可以通过 Tablet Metadata、已落盘 RowSet 和 WAL 重放重建状态。

WAL 为什么没有拖垮实时写入

如果每行都单独 fsync，延迟会很稳定地变差。Kudu 的日志层使用 Group Commit：多个并发操作先进入队列，合并为一批执行磁盘同步，然后分别唤醒等待者。

这带来一个重要效果：

单次同步成本 / 一批操作数量 ≈ 每个操作承担的同步成本

吞吐上升时，组提交能够摊薄固定的设备同步延迟。代价是低负载下仍然存在 WAL 持久化与 Raft 往返，这是强持久性写入无法消失的成本。

相关实现可以从 log/log.cc 的异步追加，以及 consensus/log_cache.cc 中的 AsyncAppendReplicates() 跟下去。LogCache 还缓存尚未从 WAL 回收的 Replicate 消息，让落后副本不必每次都从磁盘读取。

INSERT：新行为什么进入 MemRowSet

MemRowSet 是 Tablet 的可写行集合，适合低延迟随机写。它内部以编码主键建立并发索引，行数据放在内存中；在源码中可从 MemRowSet::Insert() 进入。

插入前需要解决三个问题：

  1. 主键是否已经存在；
  2. 是否与并发写发生冲突；
  3. 该行在当前时间戳下是否可见。

Kudu 会对主键取得行级锁，并同时检查当前 MemRowSet、正在 Flush 的 MemRowSet 和候选 DiskRowSet。不能只检查当前内存表，否则一行已经落盘后仍可能被重复插入。

成功插入后，行带着插入时间戳进入 MemRowSet。此时它已可被符合 MVCC 条件的读取看到，但还没有转换成按列编码的 DiskRowSet。

MemRowSet 解决的是写入延迟，不是长期存储效率。它达到内存或维护策略阈值后会被冻结并 Flush。

UPDATE 与 DELETE：为什么不能都塞进 MemRowSet

这是理解 Kudu 数据结构的关键。

  • 如果目标行仍在 MemRowSet，更新可以直接挂到该内存行的 Mutation 链；
  • 如果目标行已经在 DiskRowSet，Kudu 不会为了改一个字段重写整套列文件，而是把变更写入该 RowSet 的 DeltaMemStore；
  • DELETE 也是一种带时间戳的 Mutation，而不是立即从基线文件抹掉。

DeltaMemStore::Update() 接收时间戳、RowId、变更列表和操作 ID。这里使用的是 DiskRowSet 内部的行序号，而不是再保存一遍完整主键。定位阶段先由主键索引找到 RowSet 和 RowId，更新阶段即可在 Delta Store 中记录稀疏变更。

DiskRowSet Base Data
row 42: id=1001, name="A", score=80

DeltaMemStore
row 42 @ T2: score=85
row 42 @ T3: DELETE

这种设计避免了小更新放大成整列重写，却把成本推给了读取：扫描时必须把基线数据和对当前快照可见的 Delta 合并。

MemRowSet Flush：从行式内存变成列式磁盘

Flush 并不是把内存直接序列化成一个行文件。Tablet::Flush() 会选择 MemRowSet，构造 Compaction Input，再通过 DiskRowSet Writer 生成新的列式数据块及索引。

可以把过程理解为：

冻结 MemRowSet
  → 按主键顺序迭代行与 Mutation
  → 为每一列建立 ColumnBlock
  → 编码、压缩并写入 CFile
  → 写主键索引、Bloom Filter 与元数据
  → 原子更新 TabletMetadata
  → 将新 DiskRowSet 加入 RowSetTree
  → 释放旧 MemRowSet

写列文件时可以按列选择编码方式。整数、字典值、布尔值和字符串的分布不同，适合的编码也不同。压缩和编码降低扫描 IO，但 Flush 是 CPU 与磁盘密集操作，所以由 Maintenance Manager 在后台调度，而不是阻塞所有前台写入。

Flush 期间 Tablet 会切换到新的可写 MemRowSet，旧 MemRowSet 进入只读集合。这样前台写不必等待整个列式文件生成。

flowchart LR
    A[可写 MemRowSet] -->|冻结| B[只读 MemRowSet]
    A -. 前台继续写 .-> N[新的 MemRowSet]
    B --> C[按主键迭代]
    C --> D[按列编码与压缩]
    D --> E[CFile 与索引]
    E --> F[更新 TabletMetadata]
    F --> G[加入 RowSetTree]
    G --> H[DiskRowSet]

DiskRowSet 不只是一组列文件

一个 DiskRowSet 至少包含三类信息：

Base Data

每列通常写入独立 CFile，按 RowId 对齐。查询只需要少数列时，可以跳过其他列，这是分析扫描高效的基础。

主键与过滤索引

编码主键索引用于定位范围，Bloom Filter 用于快速排除“不可能包含此键”的 RowSet。点查和更新都会受益。

DeltaTracker

DeltaTracker 管理当前 DeltaMemStore、Redo Delta Files 和 Undo Delta Files。它把频繁变化的数据与稳定基线分开，是 Kudu 能对列式数据做行级更新的核心。

Delta 的两次 Compaction 解决不同问题

Delta 不能无限增长。Kudu 有 Minor 和 Major 两类 Delta Compaction，名字相近，行为完全不同。

flowchart TB
    B[DiskRowSet Base Data]
    DMS[DeltaMemStore]
    R1[Redo DeltaFile 1]
    R2[Redo DeltaFile 2]
    RM[合并后的 Redo]
    NB[新的 Base Data]
    U[Undo Delta]
    DMS -->|Flush| R1
    R1 -->|Minor Delta Compaction| RM
    R2 -->|Minor Delta Compaction| RM
    B -->|Major Delta Compaction| NB
    RM -->|合入选定列| NB
    B -. 保存旧版本 .-> U

Minor Delta Compaction

Minor Compaction 把多个较小的 Redo DeltaFile 合并成更少、更大的 DeltaFile。Base Data 不变。

Redo 1 + Redo 2 + Redo 3 → Redo merged
Base Data                 → 不变

它主要减少读取时需要打开和合并的 Delta Store 数量，控制元数据和随机 IO 成本。

Major Delta Compaction

Major Compaction 把选定列的 Redo Delta 合并进 Base Data，同时生成相应 Undo 信息，使旧快照仍能回到历史值。

旧 Base + Redo → 新 Base
                └→ Undo Delta 保存旧版本

Major Compaction 的写放大更大，但能够把热点更新重新整理为连续列数据，恢复扫描效率。源码入口在 Tablet::CompactWorstDeltas()、Tablet::DoMajorDeltaCompaction() 以及 tablet/delta_compaction.cc。

RowSet Compaction：控制重叠，而不只是控制文件数

MemRowSet 每次 Flush 都会产生 DiskRowSet。如果写入主键范围彼此重叠，查询一个范围时就要合并多个 RowSet。RowSet Compaction 会选择一组候选 RowSet，按主键归并并写成新的 RowSet。

Kudu 的 Compaction Policy 关注的不只是“文件是不是太多”，还考虑 RowSet 的键区间重叠。BudgetedCompactionPolicy 在给定 IO 预算下选择收益较高的候选集合。

读取放大的直观近似是：

读取成本 ≈ 命中的 RowSet 数量
         + 每个 RowSet 的 Delta Store 数量
         + 实际读取列与数据块数量

RowSet Compaction 降低第一项，Minor Delta Compaction 降低第二项，Major Delta Compaction 则把 Delta 重新吸收到 Base Data。

MVCC：同一行为什么能返回不同版本

Kudu 为操作分配 HybridTime 时间戳，并用 MvccManager 跟踪尚未完成和已经提交的事务。一次扫描会取得 MVCC Snapshot，判断哪些时间戳可见。

对某个快照读取 DiskRowSet 时：

  1. 读取当前 Base Data；
  2. 应用快照时间之前可见的 Redo Delta；
  3. 如果 Base 已经包含比快照更新的值，则利用 Undo Delta 回退；
  4. 根据插入与删除时间戳决定行是否存在。

Undo Delta 的价值就在这里。Major Compaction 可以更新基线而不立即破坏历史快照。等到历史保留窗口之外，不再有读取需要旧版本，History GC 才能回收相应 Undo 数据和已删除行。

读取路径：点查和扫描并不是一回事

点查

点查先编码主键，然后：

检查 MemRowSet
  → RowSetTree 筛选候选 DiskRowSet
  → Bloom Filter 排除不命中者
  → 主键索引定位 RowId
  → 合并 Snapshot 可见 Delta
  → 物化请求列

范围扫描

范围扫描需要同时打开相交 RowSet 的 Iterator，读取目标列并合并有序结果。谓词会尽量下推到列迭代器，利用块级索引、Zone Map、Bloom Filter 或编码信息跳过数据。

Kudu 的“实时”不是所有查询都始终很快。大量随机更新会堆积 Delta；主键分布不合理会产生热点；RowSet 高度重叠会增加归并成本。后台维护跟不上写入时，读延迟必然上升。

Raft、WAL 和 MVCC 各自保证什么

这三个概念经常被混在一起：

机制 解决的问题
WAL 节点崩溃后能重放操作
Raft 多副本对操作顺序和提交结果达成一致
MVCC 并发读写时决定快照可见性

Leader 给操作排序并复制，Follower 以相同顺序应用。多数副本确认后，操作才能形成已提交的一致状态。读取若要求更强一致性，还需要考虑 Leader、Safe Time 和外部一致性模式。

Kudu 使用 Hybrid Clock 将物理时间与逻辑顺序结合。它不是说机器时钟永远准确，而是通过最大误差和等待机制约束时间戳，使客户端传播时间戳与快照读能够建立可解释的顺序。

所谓“实时性”到底来自哪里

Kudu 的实时性不是取消持久化，而是把昂贵工作移出写入关键路径：

  • 新行先写 WAL 和 MemRowSet，不同步生成完整列文件；
  • 多个 WAL 操作通过 Group Commit 摊薄同步成本；
  • 更新先进入稀疏 Delta，不立即重写 Base Data；
  • Flush 和 Compaction 在后台执行；
  • Tablet 分区和 Raft 副本组允许并行扩展；
  • 查询直接读取 MemRowSet 与 Delta，无需等待批量 ETL。

代价同样明确：更多内存、更复杂的后台维护、更高的写放大，以及对主键和分区设计的严格要求。

从源码排查写入延迟

遇到延迟升高，不能只看“磁盘慢不慢”。可以沿链路分段：

客户端排队与批大小
  → RPC 排队
  → 行锁等待
  → Leader WAL Group Commit
  → Raft 多数副本延迟
  → Apply 到 MRS / DMS
  → 内存压力触发 Flush
  → Maintenance Queue 堆积

常见观察点包括：

  • WAL Group Commit 延迟与批大小；
  • Leader 到 Follower 的复制延迟；
  • MemRowSet 与 DeltaMemStore 内存占用；
  • Flush 队列、Compaction 队列和 Maintenance Manager 饱和度；
  • RowSet 数量、重叠度和 Delta Store 数量；
  • 磁盘吞吐、fsync 尾延迟与数据盘分布；
  • 热点 Tablet 的写入倾斜。

如果写入均集中在递增主键末端，而 Range 分区又没有配合 Hash 分区，一个 Tablet 会先成为瓶颈。增加 Tablet Server 并不会自动拆散这个热点。

设计 Kudu 表时真正影响存储层的选择

主键顺序

主键既决定唯一性，也参与行排序和分区。最常用的过滤字段应靠近前缀，但不能让所有新写入都落到同一范围。

Hash 与 Range 分区

Hash 用于打散并发写，Range 用于裁剪时间或业务范围。两者组合通常比只用一种更稳，但 Tablet 数量会相乘，不能无限增加 Bucket。

更新比例

更新越多，Delta 生成越快，读合并与后台 Compaction 压力越大。如果数据绝大多数只追加，Parquet 可能更经济。

行宽与访问列

列式存储的收益来自“只读需要的列”。如果每次都读取整行宽表，压缩和 IO 优势会被削弱。

结语

Kudu 的存储模型可以概括为一条持续变化的链：

新行 → MemRowSet → Flush → DiskRowSet Base
                         ↑
更新 → DeltaMemStore → DeltaFile → Major Compaction
                         ↓
                     Undo / History GC

但真正让它可用的，是这条链之外的 WAL、Raft、MVCC 和后台维护调度。MemRowSet 提供低延迟入口，DiskRowSet 提供列式扫描，Delta 避免小更新重写整列，Compaction 偿还累积的读取成本。

所以 Kudu 的实时性不是“没有代价的快”，而是把写入、查询和整理的成本分开支付。理解每笔成本落在哪里，才知道一张表为什么快、什么时候会慢，以及该从哪一层开始排查。