企业官网建设流程全解析

TigerBeetle 内部架构：LSM 树存储引擎设计与增量压缩机制

【免费下载链接】tigerbeetleThe financial transactions database designed for mission critical safety and performance.项目地址: https://gitcode.com/GitHub_Trending/ti/tigerbeetle

导读

本文深入解析 TigerBeetle（一款面向关键任务场景的金融事务数据库）的核心存储引擎——基于日志结构合并树（LSM Tree）的实现。你将了解到 TigerBeetle 如何在 src/lsm 目录下通过"可变的 mutable 表 + 不可变 immutable 表 + 多层磁盘表"的三级结构组织数据，如何用音乐术语的 "bar/beat" 概念把压缩（compaction）拆解为增量步骤以规避写放大停顿，以及 snapshot 与 manifest 如何共同保证压缩期间查询的一致性。读完本文，你将掌握 TigerBeetle LSM 引擎的完整工作流程、关键配置参数（如lsm_growth_factor、lsm_compaction_ops、lsm_levels）的真实含义，以及从源码层面验证这些机制的方法。

从 LSM 说起：为什么 TigerBeetle 选择日志结构合并树

LSM（Log-Structured Merge Tree）是一种将随机写转化为顺序写的存储结构：所有写入先进入内存表，再批量落盘为不可变的有序表（SSTable），并通过后台压缩不断合并、下推数据。TigerBeetle 的事务负载以"高吞吐的转账、记账写入"为主，写入必须低延迟且可预测，因此采用 LSM 设计，在 src/lsm 目录中实现了完整的树（Tree）、森林（Forest）、压缩（Compaction）、清单（Manifest）与快照（Snapshot）体系。

TigerBeetle 中 LSM 相关的全局常量集中在 src/constants.zig 与 src/config.zig 中，生产配置的默认值如下：

这些参数属于ConfigCluster（按集群粒度可调），且集群内所有副本必须使用完全一致的配置；存储格式在不同ConfigCluster之间不兼容（见 src/config.zig 的注释）。测试配置test_min则将lsm_compaction_ops降为4、lsm_growth_factor降为4，用于在模拟器中更快地覆盖代码路径（src/config.zig）。

核心词汇表：理解 TigerBeetle LSM 的九个关键概念

lsm.md 给出了一套精确定义的术语，后续所有机制都建立在这套词汇之上：

• bar（小节）：lsm_compaction_ops个压缩节拍的总和，是增量压缩的一个完整周期单位。
• beat（拍）：op % lsm_compaction_ops，增量压缩中的一个单步；每完成一次 commit 就异步执行一拍。
• groove（沟槽）：一组 LSM 树的集合，用于存储对象（objects）及其索引（indexes）。
• immutable table（不可变表）：内存表，每棵树一张；用于周期性把 mutable table 冲刷（flush）到磁盘。
• level（层）：磁盘上表（on-disk table）的集合，编号为0到config.lsm_levels - 1（生产默认 7 层）。
• forest（森林）：groove 的集合，即整个 LSM 存储的顶层容器。
• manifest（清单）：每棵树一张，记录表（table）与层（level）的元数据索引。
• mutable table（可变表）：内存表，每棵树一张；所有树更新（如Tree.put）都直接写入这张表。
• snapshot（快照）：用于选择磁盘表可查询分区的序列号。

从源码结构看，这些概念一一对应到 src/lsm/forest.zig 中的ForestType（包含 groove 列表与共享的manifest_log）、src/lsm/tree.zig 中的TreeType（持有table_mutable、table_immutable、manifest与compactions数组），以及 src/lsm/groove.zig 中的 groove 类型。

Tree：内存表与磁盘表的分层结构

三类表的职责划分

一棵树（Tree）是内存表与磁盘表组成的层级结构，共分三类：

1. mutable table（可变内存表）

   • 每棵树仅一张，位于 src/lsm/table_memory.zig。
   • 所有树的更新、插入、删除操作（Tree.put/Tree.remove）都直接作用于这张表（见 src/lsm/tree.zig）。
   • 表的大小按容纳整整一个 bar 的更新量来分配：在 src/lsm/tree.zig 中，value_count_limit = options.batch_value_count_limit * constants.lsm_compaction_ops，即"一批值上限 × 每 bar 的拍数"。

2. immutable table（不可变内存表）

   • 每棵树仅一张，同样实现在 src/lsm/table_memory.zig。
   • mutable table 的内容周期性搬移到这里，在冲刷到第 0 层期间暂存。
   • 在 src/lsm/table_memory.zig 的模块注释中说明了两种搬移路径：若上一张 immutable 表已冲刷完成，则compact()直接把 mutable 表的存储与排序 run 跟踪器交换进来；若尚未冲刷，则absorb()保留原有 run 并把 mutable 的 run 追加合并，从而避免为一张很小的表产生一次磁盘 flush。

3. 第 0 层到第lsm_levels - 1层（磁盘表）

   • 每层包含数量呈指数增长的不可变磁盘表。
   • 每棵树的第level层最多有config.lsm_growth_factor ^ (level + 1)张表（生产默认增长因子 8）。
   • 在同一层、同一 snapshot 内，各表的键区间是互不相交的（disjoint），这一不变量由 src/lsm/manifest_level.zig 维护。

每层表数量的精确公式实现在 src/lsm/tree.zig：table_count_max_for_level(growth_factor, level) = growth_factor^(level+1)，table_count_max_for_tree为各层之和。文件末尾的单元测试（src/lsm/tree.zig）给出了 8 倍增长因子下的具体数值：第 0 层 8 张、第 1 层 64 张、第 2 层 512 张……第 6 层 2,097,152 张，7 层合计约 240 万张。这也解释了增长因子的权衡：src/constants.zig 指出，更高的增长因子会增加写放大（因为一次压缩要合并的 B 层表更多），但会降低读放大（树更矮、需要探测的层更少）；由于读放大更容易靠缓存优化，TigerBeetle 选择 8 而不是更常见的 10。

为什么选择 8 作为增长因子

从 src/lsm/tree.zig 的断言可以看到设计边界：growth_factor必须落在[4, 16]区间（"限制过度的写放大"），levels_count必须在[2, 10]（"限制过度的读放大"）。这与 lsm.md 中"第level层有growth_factor^(level+1)张表"的说明完全一致，是理解后续压缩选择策略的基础。

Compaction：在音乐节拍中完成的增量压缩

bar 与 beat：压缩的节奏单位

"Tree compaction runs to the sound of music!"——TigerBeetle 用音乐记谱法的术语来描述压缩节奏：

• 压缩 LSM 树就是把表合并并下移到更深层。为避免写放大停顿（write amplification stalls）并让延迟有界，压缩必须增量进行。
• 一个完整的压缩阶段称为一个bar（小节），由lsm_compaction_ops个beats（拍）（也叫"压缩 tick"）组成。
• 每个压缩 tick 在每次 commit 之后异步执行，beat = commit.op % lsm_compaction_ops。

一个 bar 被"first beat（第一拍）"和"middle beat（中间拍）"对半切开：bar 的前半段压缩偶数层，后半段压缩奇数层。mutable table 的变更会被排序并压缩进 immutable table；immutable table 则在奇数层半段被压缩到第 0 层。

并发度与输入输出

• 任意时刻最多有⌈levels/2⌉个压缩并发运行（lsm_levels=7时即 4 个）。对应地，src/lsm/tree.zig 中compactions数组长度为constants.lsm_levels，注释解释了 "+1 来自 immutable table 压到第 0 层，但被 −1 抵消（最后一层没有目标层）"。
• 源层记作level_a，目标层记作level_b。LSM 树的最后一层没有目标层，因此永远不会成为源层。
• 每次压缩把level_a的一张表（选择策略见下节）与level_b中键区间与其相交的所有表合并。

src/lsm/compaction.zig 的模块注释给出了完整流程：给定层 A 的一张表和层 B 中与其相交的表集合 → 若键区间完全不相交则直接移动表 → 否则用 sort-merge 迭代器归并（相同键取 A 的值）→ 写出新表 → 在 Manifest 中更新输入表的snapshot_max使其对后续读事务不可见 → 把新表插入 Manifest。注释还特别说明了一个细节：当 A 的值是 tombstone（墓碑）时，若 B 是最后一层或 A 的键不存在于 B 及更深层，则 tombstone 会从压缩输出中省略（垃圾回收），对应compaction_must_drop_tombstones逻辑。

一个 bar 的四个关键时间点

lsm.md 详细规定了每个半小节首尾拍必须满足的不变量：

1. 前半小节第一拍（first beat）：

   • 断言当前没有压缩在运行。
   • 允许各层表数上限临时溢出（例如要把表从 A 层压到已满的 B 层时）。
   • 从达到表数上限的偶数层启动压缩。
   • 从 Free Set 为整个半小节将写入的所有块（上界）获取预留（reservation）。

2. 前半小节最后一拍：

   • 完成任何未跑完的偶数层压缩。
   • 回调完成时断言所有压缩均已结束。
   • 释放 Free Set 预留。

3. 后半小节第一拍（middle beat）：

   • 断言当前没有压缩在运行。
   • 从达到表数上限的奇数层启动压缩。
   • 若 immutable table 包含已排序的值（可能为空）则压缩它。
   • 从 Free Set 获取本半小节写入块的预留。

4. 后半小节最后一拍：

   • 完成未跑完的奇数层与 immutable table 压缩。
   • 断言所有压缩完成、没有层的表数溢出。
   • 冲刷、清空并把 mutable table 的值排序进 immutable table，供下一个 bar 使用。
   • 移除对当前及已持久化 snapshot 均不可见的输入表。
   • 释放 Free Set 预留。

源码中的调度实现

src/lsm/forest.zig 的compact_trees_start展示了上述节奏的实现骨架：

• half_bar = lsm_compaction_ops / 2，compaction_beat = op % lsm_compaction_ops；
• first_beat = compaction_beat == 0，half_beat = compaction_beat == half_bar；
• 在 first/half beat 时调用compaction.half_bar_commence(op)汇总整个半小节的输入量（half_bar_input_size），再按剩余拍数均摊：trees_beat_input_size = div_ceil(half_bar_input_size, beats_remaining)——这正体现了"增量"的落地方式：把半小节的总工作量在拍之间平滑分摊，随后compact_trees_reserve_grid_blocks预留下一次输出的网格块。

Tree.compact也在每拍执行：它调用table_mutable.sort_suffix()，把排序+去重工作摊到各拍之间，避免在 bar 末尾（或扫描前）出现延迟尖峰（src/lsm/tree.zig）。

压缩选择策略（Compaction Selection Policy）

最少重叠策略

压缩时选择level_a中与level_b可见表重叠最少的那张表。lsm.md 给出了lsm_growth_factor=2时的直观例子（大写字母表将被选中）：

Level 0 A─────────────H l───────────────────────────z Level 1 a───────e L─M o───────s u───────y Level 2 b───d e─────h i───k l───n o─p q───s u─v w─────z (Keys) a b c d e f g h i j k l m n o p q r s t u v w x y z

例如上表中 A 表只与第 1 层的a───────e重叠，是第 0 层中重叠最少的候选，因此会被优先选中。TigerBeetle 实现的是文献中被称为 "least overlapping with parent"（与父层最少重叠）的策略；这一策略与 RocksDB 的 compaction priority 选项探讨的是同一类数据移动取舍问题（原文引用的论文为《Constructing and Analyzing the LSM Compaction Design Space》）。

选择策略的实现位置为 src/lsm/manifest.zig 中的Manifest.compaction_table。

Move Table 优化

当从层 A 选出的输入表与层 B 的任何输入表都不重叠时，就不需要 sort-merge，只需在 manifest 中更新该表的元数据即可把它"移动"到层 B。这就是move table 优化。

src/lsm/compaction.zig 的步骤 2 明确写道："如果表 A 的键区间与层 B 的键不相交，就把表 A 移到层 B，全部完成！"这种场景下，一棵以有序插入为主、极少更新的树，其性能可以接近追加写日志（append-only log）。compaction_tables_input_max = 1 + lsm_growth_factor（src/lsm/compaction.zig）这个上界也正是由"最少重叠选择 + move table"共同保证的。

重叠上界分析：为什么最坏情况恰好是lsm_growth_factor

把最少重叠策略应用到"从 A 层压到 B 层"时，被选中的 A 层表最多与多少张 B 层表重叠？答案令人惊讶地正好是lsm_growth_factor，证明过程如下：

• 层内表键区间互不相交。
• B 层最多有 A 层lsm_growth_factor倍的表数量。
• 触发压缩的前提是 A 层可见表数超过table_count_max_for_level(lsm_growth_factor, level_a)。
• 选择策略选的是与 B 层可见表重叠最少的 A 层表。
• 若某张 A 层表与 B 层超过lsm_growth_factor张表重叠，则必然存在另一张 A 层表重叠数少于lsm_growth_factor——后者会被优先选中。

这一结论直接决定了压缩资源上界：compaction_tables_input_max = 1 + lsm_growth_factor（A 层 1 张 + B 层至多lsm_growth_factor张），输出表上界与之相同（src/lsm/compaction.zig）。同时它也是"压缩每拍所需块数下限"的推导基础：compaction_block_count_beat_min = (1+1) + (1+2) + lsm_compaction_queue_read_max，即输出表的 index+value 各一块、A 层 index 一块、B 层两个 index（允许预取）以及两个输入表各lsm_compaction_queue_read_max/2个 value 块（src/lsm/compaction.zig）。

Snapshots：让压缩"复制而非覆盖"

快照可见性规则

每张表带有一对整数快照边界snapshot_min与snapshot_max。一次查询针对特定 snapshotS，表T对S可见当且仅当：

T.snapshot_min ≤ S ≤ T.snapshot_max

否则不可见。该判定在源码中实现在 src/lsm/manifest.zig 的visible/invisible方法：snapshot_min在表创建（作为压缩输出）时被设置为compaction.snapshot + 1，snapshot_max在表被压缩处理（作为输入）时被设置为compaction.snapshot。而"尚未删除的表"用snapshot_max = maxInt(u64)表示；因此 src/lsm/tree.zig 定义了snapshot_latest = maxInt(u64) - 1，保证查询快照永远不会精确等于表边界的最大值（见 src/lsm/tree.zig 的注释）。

压缩不会原地修改表——它复制数据。快照的作用正是区分哪些副本还有用、哪些可以删除。快照还可以被持久化，从而支持对树过去状态的查询（该功能目前标注为未实现、未来工作）。

快照与压缩的交互

考虑从op=X=12开始的半小节压缩，lsm_compaction_ops=M=8。每个半小节有N=M/2=4拍，下一个半小节从Y=X+N=16开始。

在压缩半小节X期间：

• 每个输入表的snapshot_max被截断为Y-1=15；
• 每个输出表的snapshot_min被初始化为Y=16；
• 每个输出表的snapshot_max被初始化为∞。

0 4 8 12 16 20 24 (op, snapshot) ┼───┬───┼───┬───┼───┬───┼ #### ····────────X────────···· (input tables, before compaction) ····──────────── (input tables, after compaction) Y────···· (output tables, after compaction)

从压缩之后的下一 op（Y=16）开始：

• 上述压缩X的输出表变为可见；
• 输入表变为不可见；
• 因此查询将从输出表查找、忽略输入表；
• 调用方不得在压缩半小节结束前（即 beatY-1=15结束前）查询X的输出表，因为那时这些表尚未写完、是不完整的。

此刻，若输入表对所有持久化快照均不可见，就可以被删除。

快照查询与取值语义

每次查询都针对特定快照：要么是当前快照（snapshot_latest），要么是持久化快照。持久化快照一节在原文档中标注为 TODO（Persistent Snapshots），属于未实现、规划中的能力。

关于快照值有一个容易混淆的点：对快照B可见的磁盘表并不包含op 为B的 commit 的更新；相反，快照B首次可见于从 opB开始的 commit 的预取（prefetch）。以下图为例（lsm_compaction_ops=8）：

0 4 8 12 16 20 24 28 (op, snapshot) ┼───┬───┼───┬───┼───┬───┬───┬ ,,,,,,,,........ ↑A ↑B ↑C

压缩由 opB→C（16…23）的 commit 驱动，在该区间提交期间：

• op0→A（0…7）的更新已落盘；
• opA→B（8…15）的更新位于 immutable table 中——它们在 opB-1=15结束时从 mutable 搬入，并一直存在到 opC-1=23结束时被重置；
• opB→C（16…23）的更新由各自的 commit 追加进 mutable table；
• tree.lookup_snapshot_max在提交 opB时为B，在提交 opx（x ∈ {16,…,23}）时为x。

在压缩 bar 最后一拍（op 23）结束时：

• op0→B（0…15）的更新全部落盘；
• opB→C（16…23）的更新从 mutable 搬入 immutable；
• 之后tree.lookup_snapshot_max在提交 opx（x ∈ {24,25,…}）时即为x。

这一机制保证了：任何时刻 mutable table 都有空间容纳下一拍的更新，压缩的输出表直到压缩完成才对查询可见——正是 lsm.md 开头列出的三条不变量。

Manifest：树的表索引与元数据

Manifest 是一棵树的表位置与元数据索引，由两部分组成：一个由所有树和层共享的ManifestLog，以及每个磁盘层各一个的ManifestLevel。

Manifest Log：压缩事件的持久日志

Manifest log 是磁盘上的日志，记录对树表索引的所有更新：

• 压缩输出而创建的表；
• 压缩输入而更新的表（修改其snapshot_max）；
• 压缩在层间移动的表；
• 压缩后删除的表。

更新先在内存中累积，再成批刷出：要么在压缩期间增量刷出，要么在 checkpoint 时整体刷出。Manifest log 会被周期性压缩，以移除已被更新条目取代的旧条目——例如一张表先创建后删除，日志压缩最终会从日志块中抹去对它的所有引用。

日志块的链式结构：每个 manifest 块都带有一个指向（时间上）前一个 manifest 块的引用；superblock 存储这条链表的头尾地址/校验和。头部的 manifest 块头引用是"悬空"的——它所引用的块已经被压缩掉了。对应实现位于 src/lsm/manifest_log.zig。

Manifest Level：内存中的层元数据

ManifestLevel是一棵树单个层表元数据的内存集合（src/lsm/manifest_level.zig）。对于给定层和快照，可见表的键区间之间可能有空隙，但互不相交。Manifest level 供"目标快照 + 键区间"的查询使用。

原文档用一张 13 张表的例子（值仅为可视化选取、非真实数据）说明 2D 可视化的分区矩形：

label A B C D E F G H I J K L M key_min 0 4 12 16 4 8 12 26 4 25 4 16 24 key_max 3 11 15 19 7 11 15 27 7 27 11 19 27 snapshot_min 1 1 1 1 3 3 3 3 5 5 7 7 7 snapshot_max 9 3 3 7 5 7 9 5 7 7 9 9 9

以快照为纵轴、键范围为横轴，每张表画成一个矩形：左边界是table.key_min（闭区间），右边界是table.key_max（图示为开区间、实际字段为闭区间），下边界snapshot_min（闭）、上边界snapshot_max（闭）：

0 1 2 0 4 8 2 6 0 4 8 9┌───┬───────┬───┬───┬───┬───┐ │ │ K │ │ L │###│ M │ 7│ ├───┬───┤ ├───┤###└┬──┤ │ │ I │ │ G │ │####│ J│ 5│ A ├───┤ F │ │ │####└┬─┤ │ │ E │ │ │ D │#####│H│ 3│ ├───┴───┼───┤ │#####└─┤ │ │ B │ C │ │#######│ 1└───┴───────┴───┴───┴───────┘

#表示空隙——该快照下没有表覆盖这些键。示例迭代结果验证了查询语义：

visibility snapshots direction key_min key_max tables visible 2 ascending 0 28 A, B, C, D visible 4 ascending 0 28 A, E, F, G, D, H visible 6 descending 12 28 J, D, G visible 8 ascending 0 28 A, K, G, L, M invisible 2, 4, 6 ascending 0 28 K, L, M

注意：图中未绘出的情况包括table.key_min == table.key_max的表，以及最新一批表snapshot_max == maxInt(u64)（即从未被删除、对当前快照始终可见）。

Manifest 层的查询在 src/lsm/tree.zig 的lookup_from_levels_storage中体现：先用manifest.lookup(snapshot, key, level_min)得到可能包含该键的所有表，再逐层读取 index 块与 value 块；若键在浅层表未命中，则advance_to_next_level进入下一层（src/lsm/tree.zig）。Tombstone 内部以特殊值存储，对用户表现为null，从而允许把"缓存中的空结果"编码为墓碑（src/lsm/tree.zig）。

从源码验证：关键不变量与测试

本仓库为 lsm.md 中的设计提供了直接的可验证证据：

1. 层表数公式：table_count_max_for_level与table_count_max_for_tree的单元测试给出了 8 倍增长因子、7 层配置下的精确数值（src/lsm/tree.zig）。
2. snapshot_latest 边界：snapshot_latest = maxInt(u64) - 1以及"未删除表snapshot_max = maxInt(u64)"的约定（src/lsm/tree.zig）。
3. 压缩资源上界：compaction_tables_input_max = 1 + lsm_growth_factor、compaction_block_count_beat_min的推导（src/lsm/compaction.zig）。
4. bar 均摊调度：compact_trees_start中按剩余拍数均摊半小节输入量（src/lsm/forest.zig）。
5. 增量排序：每拍sort_suffix()摊平排序与去重开销，避免延迟尖峰（src/lsm/tree.zig）。

若需在本地运行相关测试，可在仓库根目录执行 Zig 测试命令（仓库使用 Zig 工具链，见 zig/download.sh），例如对table_count_max_for_level等纯函数测试可直接运行zig build test相关目标；LSM 各模块（如 src/lsm/manifest_log_fuzz.zig、src/lsm/manifest_level_fuzz.zig、src/lsm/segmented_array_fuzz.zig）还配有独立的模糊测试，用于验证 manifest、层管理等高并发路径的不变量。

总结

TigerBeetle 的 LSM 引擎是一套自洽且高度工程化的设计：mutable → immutable → 多层磁盘表的三级写入路径让随机写变成批量顺序写；bar/beat 节奏把压缩拆成每次 commit 后的一拍，配以 Free Set 预留与输入量均摊，使写放大导致的停顿有界可预测；snapshot 可见性让压缩可以放心地"复制而非覆盖"，保证查询始终看到一致的数据；manifest 的双组件结构（共享日志 + 每层内存索引）则提供了崩溃后可恢复、可压缩的表元数据索引。这些机制环环相扣，共同支撑起 TigerBeetle 面向关键任务场景的低延迟事务写入能力。

【免费下载链接】tigerbeetleThe financial transactions database designed for mission critical safety and performance.项目地址: https://gitcode.com/GitHub_Trending/ti/tigerbeetle