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 选择日志结构合并树LSMLog-Structured Merge Tree是一种将随机写转化为顺序写的存储结构所有写入先进入内存表再批量落盘为不可变的有序表SSTable并通过后台压缩不断合并、下推数据。TigerBeetle 的事务负载以高吞吐的转账、记账写入为主写入必须低延迟且可预测因此采用 LSM 设计在 src/lsm 目录中实现了完整的树Tree、森林Forest、压缩Compaction、清单Manifest与快照Snapshot体系。TigerBeetle 中 LSM 相关的全局常量集中在 src/constants.zig 与 src/config.zig 中生产配置的默认值如下参数默认值语义lsm_levels7磁盘层的层数编号0到lsm_levels - 1lsm_growth_factor8相邻层间的表数量增长倍数lsm_compaction_ops32一个完整压缩小节bar包含的拍数beats必须为偶数lsm_snapshots_max32支持的持久化快照数量上限lsm_manifest_compact_extra_blocks1每个半小节额外压缩的 manifest 块数lsm_scans_max6并发扫描数上限这些参数属于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是内存表与磁盘表组成的层级结构共分三类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 的拍数。immutable table不可变内存表每棵树仅一张同样实现在 src/lsm/table_memory.zig。mutable table 的内容周期性搬移到这里在冲刷到第 0 层期间暂存。在 src/lsm/table_memory.zig 的模块注释中说明了两种搬移路径若上一张 immutable 表已冲刷完成则compact()直接把 mutable 表的存储与排序 run 跟踪器交换进来若尚未冲刷则absorb()保留原有 run 并把 mutable 的 run 追加合并从而避免为一张很小的表产生一次磁盘 flush。第 0 层到第lsm_levels - 1层磁盘表每层包含数量呈指数增长的不可变磁盘表。每棵树的第level层最多有config.lsm_growth_factor ^ (level 1)张表生产默认增长因子 8。在同一层、同一 snapshot 内各表的键区间是互不相交的disjoint这一不变量由 src/lsm/manifest_level.zig 维护。每层表数量的精确公式实现在 src/lsm/tree.zigtable_count_max_for_level(growth_factor, level) growth_factor^(level1)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^(level1)张表的说明完全一致是理解后续压缩选择策略的基础。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 tableimmutable table 则在奇数层半段被压缩到第 0 层。并发度与输入输出任意时刻最多有⌈levels/2⌉个压缩并发运行lsm_levels7时即 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 详细规定了每个半小节首尾拍必须满足的不变量前半小节第一拍first beat断言当前没有压缩在运行。允许各层表数上限临时溢出例如要把表从 A 层压到已满的 B 层时。从达到表数上限的偶数层启动压缩。从 Free Set 为整个半小节将写入的所有块上界获取预留reservation。前半小节最后一拍完成任何未跑完的偶数层压缩。回调完成时断言所有压缩均已结束。释放 Free Set 预留。后半小节第一拍middle beat断言当前没有压缩在运行。从达到表数上限的奇数层启动压缩。若 immutable table 包含已排序的值可能为空则压缩它。从 Free Set 获取本半小节写入块的预留。后半小节最后一拍完成未跑完的奇数层与 immutable table 压缩。断言所有压缩完成、没有层的表数溢出。冲刷、清空并把 mutable table 的值排序进 immutable table供下一个 bar 使用。移除对当前及已持久化 snapshot 均不可见的输入表。释放 Free Set 预留。源码中的调度实现src/lsm/forest.zig 的compact_trees_start展示了上述节奏的实现骨架half_bar lsm_compaction_ops / 2compaction_beat op % lsm_compaction_opsfirst_beat compaction_beat 0half_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_factor2时的直观例子大写字母表将被选中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_factorsrc/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_factorA 层 1 张 B 层至多lsm_growth_factor张输出表上界与之相同src/lsm/compaction.zig。同时它也是压缩每拍所需块数下限的推导基础compaction_block_count_beat_min (11) (12) lsm_compaction_queue_read_max即输出表的 indexvalue 各一块、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 1snapshot_max在表被压缩处理作为输入时被设置为compaction.snapshot。而尚未删除的表用snapshot_max maxInt(u64)表示因此 src/lsm/tree.zig 定义了snapshot_latest maxInt(u64) - 1保证查询快照永远不会精确等于表边界的最大值见 src/lsm/tree.zig 的注释。压缩不会原地修改表——它复制数据。快照的作用正是区分哪些副本还有用、哪些可以删除。快照还可以被持久化从而支持对树过去状态的查询该功能目前标注为未实现、未来工作。快照与压缩的交互考虑从opX12开始的半小节压缩lsm_compaction_opsM8。每个半小节有NM/24拍下一个半小节从YXN16开始。在压缩半小节X期间每个输入表的snapshot_max被截断为Y-115每个输出表的snapshot_min被初始化为Y16每个输出表的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)从压缩之后的下一 opY16开始上述压缩X的输出表变为可见输入表变为不可见因此查询将从输出表查找、忽略输入表调用方不得在压缩半小节结束前即 beatY-115结束前查询X的输出表因为那时这些表尚未写完、是不完整的。此刻若输入表对所有持久化快照均不可见就可以被删除。快照查询与取值语义每次查询都针对特定快照要么是当前快照snapshot_latest要么是持久化快照。持久化快照一节在原文档中标注为 TODOPersistent Snapshots属于未实现、规划中的能力。关于快照值有一个容易混淆的点对快照B可见的磁盘表并不包含op 为B的 commit 的更新相反快照B首次可见于从 opB开始的 commit 的预取prefetch。以下图为例lsm_compaction_ops80 4 8 12 16 20 24 28 (op, snapshot) ┼───┬───┼───┬───┼───┬───┬───┬ ,,,,,,,,........ ↑A ↑B ↑C压缩由 opB→C16…23的 commit 驱动在该区间提交期间op0→A0…7的更新已落盘opA→B8…15的更新位于 immutable table 中——它们在 opB-115结束时从 mutable 搬入并一直存在到 opC-123结束时被重置opB→C16…23的更新由各自的 commit 追加进 mutable tabletree.lookup_snapshot_max在提交 opB时为B在提交 opxx ∈ {16,…,23}时为x。在压缩 bar 最后一拍op 23结束时op0→B0…15的更新全部落盘opB→C16…23的更新从 mutable 搬入 immutable之后tree.lookup_snapshot_max在提交 opxx ∈ {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 中的设计提供了直接的可验证证据层表数公式table_count_max_for_level与table_count_max_for_tree的单元测试给出了 8 倍增长因子、7 层配置下的精确数值src/lsm/tree.zig。snapshot_latest 边界snapshot_latest maxInt(u64) - 1以及未删除表snapshot_max maxInt(u64)的约定src/lsm/tree.zig。压缩资源上界compaction_tables_input_max 1 lsm_growth_factor、compaction_block_count_beat_min的推导src/lsm/compaction.zig。bar 均摊调度compact_trees_start中按剩余拍数均摊半小节输入量src/lsm/forest.zig。增量排序每拍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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
TigerBeetle 内部架构：LSM 树存储引擎设计与增量压缩机制
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 选择日志结构合并树LSMLog-Structured Merge Tree是一种将随机写转化为顺序写的存储结构所有写入先进入内存表再批量落盘为不可变的有序表SSTable并通过后台压缩不断合并、下推数据。TigerBeetle 的事务负载以高吞吐的转账、记账写入为主写入必须低延迟且可预测因此采用 LSM 设计在 src/lsm 目录中实现了完整的树Tree、森林Forest、压缩Compaction、清单Manifest与快照Snapshot体系。TigerBeetle 中 LSM 相关的全局常量集中在 src/constants.zig 与 src/config.zig 中生产配置的默认值如下参数默认值语义lsm_levels7磁盘层的层数编号0到lsm_levels - 1lsm_growth_factor8相邻层间的表数量增长倍数lsm_compaction_ops32一个完整压缩小节bar包含的拍数beats必须为偶数lsm_snapshots_max32支持的持久化快照数量上限lsm_manifest_compact_extra_blocks1每个半小节额外压缩的 manifest 块数lsm_scans_max6并发扫描数上限这些参数属于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是内存表与磁盘表组成的层级结构共分三类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 的拍数。immutable table不可变内存表每棵树仅一张同样实现在 src/lsm/table_memory.zig。mutable table 的内容周期性搬移到这里在冲刷到第 0 层期间暂存。在 src/lsm/table_memory.zig 的模块注释中说明了两种搬移路径若上一张 immutable 表已冲刷完成则compact()直接把 mutable 表的存储与排序 run 跟踪器交换进来若尚未冲刷则absorb()保留原有 run 并把 mutable 的 run 追加合并从而避免为一张很小的表产生一次磁盘 flush。第 0 层到第lsm_levels - 1层磁盘表每层包含数量呈指数增长的不可变磁盘表。每棵树的第level层最多有config.lsm_growth_factor ^ (level 1)张表生产默认增长因子 8。在同一层、同一 snapshot 内各表的键区间是互不相交的disjoint这一不变量由 src/lsm/manifest_level.zig 维护。每层表数量的精确公式实现在 src/lsm/tree.zigtable_count_max_for_level(growth_factor, level) growth_factor^(level1)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^(level1)张表的说明完全一致是理解后续压缩选择策略的基础。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 tableimmutable table 则在奇数层半段被压缩到第 0 层。并发度与输入输出任意时刻最多有⌈levels/2⌉个压缩并发运行lsm_levels7时即 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 详细规定了每个半小节首尾拍必须满足的不变量前半小节第一拍first beat断言当前没有压缩在运行。允许各层表数上限临时溢出例如要把表从 A 层压到已满的 B 层时。从达到表数上限的偶数层启动压缩。从 Free Set 为整个半小节将写入的所有块上界获取预留reservation。前半小节最后一拍完成任何未跑完的偶数层压缩。回调完成时断言所有压缩均已结束。释放 Free Set 预留。后半小节第一拍middle beat断言当前没有压缩在运行。从达到表数上限的奇数层启动压缩。若 immutable table 包含已排序的值可能为空则压缩它。从 Free Set 获取本半小节写入块的预留。后半小节最后一拍完成未跑完的奇数层与 immutable table 压缩。断言所有压缩完成、没有层的表数溢出。冲刷、清空并把 mutable table 的值排序进 immutable table供下一个 bar 使用。移除对当前及已持久化 snapshot 均不可见的输入表。释放 Free Set 预留。源码中的调度实现src/lsm/forest.zig 的compact_trees_start展示了上述节奏的实现骨架half_bar lsm_compaction_ops / 2compaction_beat op % lsm_compaction_opsfirst_beat compaction_beat 0half_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_factor2时的直观例子大写字母表将被选中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_factorsrc/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_factorA 层 1 张 B 层至多lsm_growth_factor张输出表上界与之相同src/lsm/compaction.zig。同时它也是压缩每拍所需块数下限的推导基础compaction_block_count_beat_min (11) (12) lsm_compaction_queue_read_max即输出表的 indexvalue 各一块、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 1snapshot_max在表被压缩处理作为输入时被设置为compaction.snapshot。而尚未删除的表用snapshot_max maxInt(u64)表示因此 src/lsm/tree.zig 定义了snapshot_latest maxInt(u64) - 1保证查询快照永远不会精确等于表边界的最大值见 src/lsm/tree.zig 的注释。压缩不会原地修改表——它复制数据。快照的作用正是区分哪些副本还有用、哪些可以删除。快照还可以被持久化从而支持对树过去状态的查询该功能目前标注为未实现、未来工作。快照与压缩的交互考虑从opX12开始的半小节压缩lsm_compaction_opsM8。每个半小节有NM/24拍下一个半小节从YXN16开始。在压缩半小节X期间每个输入表的snapshot_max被截断为Y-115每个输出表的snapshot_min被初始化为Y16每个输出表的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)从压缩之后的下一 opY16开始上述压缩X的输出表变为可见输入表变为不可见因此查询将从输出表查找、忽略输入表调用方不得在压缩半小节结束前即 beatY-115结束前查询X的输出表因为那时这些表尚未写完、是不完整的。此刻若输入表对所有持久化快照均不可见就可以被删除。快照查询与取值语义每次查询都针对特定快照要么是当前快照snapshot_latest要么是持久化快照。持久化快照一节在原文档中标注为 TODOPersistent Snapshots属于未实现、规划中的能力。关于快照值有一个容易混淆的点对快照B可见的磁盘表并不包含op 为B的 commit 的更新相反快照B首次可见于从 opB开始的 commit 的预取prefetch。以下图为例lsm_compaction_ops80 4 8 12 16 20 24 28 (op, snapshot) ┼───┬───┼───┬───┼───┬───┬───┬ ,,,,,,,,........ ↑A ↑B ↑C压缩由 opB→C16…23的 commit 驱动在该区间提交期间op0→A0…7的更新已落盘opA→B8…15的更新位于 immutable table 中——它们在 opB-115结束时从 mutable 搬入并一直存在到 opC-123结束时被重置opB→C16…23的更新由各自的 commit 追加进 mutable tabletree.lookup_snapshot_max在提交 opB时为B在提交 opxx ∈ {16,…,23}时为x。在压缩 bar 最后一拍op 23结束时op0→B0…15的更新全部落盘opB→C16…23的更新从 mutable 搬入 immutable之后tree.lookup_snapshot_max在提交 opxx ∈ {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 中的设计提供了直接的可验证证据层表数公式table_count_max_for_level与table_count_max_for_tree的单元测试给出了 8 倍增长因子、7 层配置下的精确数值src/lsm/tree.zig。snapshot_latest 边界snapshot_latest maxInt(u64) - 1以及未删除表snapshot_max maxInt(u64)的约定src/lsm/tree.zig。压缩资源上界compaction_tables_input_max 1 lsm_growth_factor、compaction_block_count_beat_min的推导src/lsm/compaction.zig。bar 均摊调度compact_trees_start中按剩余拍数均摊半小节输入量src/lsm/forest.zig。增量排序每拍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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考