TigerBeetle 数据文件Data File内部布局WAL、Superblock 与 Grid 如何协作【免费下载链接】tigerbeetleThe financial transactions database designed for mission critical safety and performance.项目地址: https://gitcode.com/GitHub_Trending/ti/tigerbeetleTigerBeetle 将单个副本的全部持久化状态存放在一个名为 data file 的文件中惯例扩展名为.tigerbeetle。本文基于 data_file.md 展开从物理分区write-ahead log、superblock、grid讲到逻辑结构LSM 森林、manifest 日志并结合仓库源码给出字节级细节的索引帮助你理解一个文件如何承载数 TB 的确定性数据库状态。读完本文你将掌握 TigerBeetle 数据文件的整体布局、superblock 原子更新机制、grid 块寻址方式以及 LSM 树如何以事件日志的形式隐式存储在文件中。数据文件的三大部分WAL、Superblock 与 GridTigerBeetle 的每个副本将全部数据存放在一个单一文件中即 data file。该文件被划分为若干 zone区域最主要的三个是write-ahead logWAL预写日志存放 prepare代表应施加到 superblock/grid 所表示状态之上的逻辑增量superblock位于数据文件的固定位置保存逻辑根指针是启动时定位全部数据的入口grid占据数据文件的绝大部分体积可达数 TB是一个由 512KiB 块构成的弹性数组。在 src/config.zig 中可以看到两个关键编译期常量默认block_size 512 * KiB、superblock_copies 4而扇区大小sector_size 4096定义在 src/constants.zig。这些常量共同约束了数据文件的物理布局。Grid弹性块数组与块寻址Grid 是一个弹性elastic的 512KiB 块数组作为原始存储层为上层数据结构尤其是 LSM 树提供映射。其块与块指针的 Zig 定义与文档一致为pub const Block [constants.block_size]u8; pub const BlockPtr *align(constants.sector_size) Block;在源码 src/vsr/grid.zig 中实际定义更精确BlockPtr *align(constants.sector_size) [constants.block_size]u8即每个块按扇区对齐。由于 TigerBeetle 是确定性的deterministic所有同步到最新状态的副本其 grid 的已使用部分完全相同。这一存储确定性被用来在 grid 块粒度上实现状态同步sync与修复repair详见 VSR 文档中的 Protocol: Repair Grid。每个 grid 块由一个u64索引index加一个u128校验和checksum组成的二元组标识pub const BlockReference struct { index: u64, checksum: u128, };校验和存放在块外部而不是块内部——这是为了防止错位写入/读取misdirected write/read损坏数据。因此要读取某个块你必须先从别处另一块或 superblock得知该块的索引与校验和。grid 整体实现了纯粹的purely functional、持久化的、带垃圾回收的数据结构通过交换指向根节点的指针来原子更新——这正是文件系统中常见的 copy-on-write 技术。可以这样理解TigerBeetle 的 data file 本质上就是一个文件系统grid 是存储层superblock 保存着逻辑根指针。在 src/vsr/grid.zig 中可以看到地址与偏移的换算(address - 1) * block_size即 grid 块地址从 1 开始物理偏移为(地址 - 1) × 块大小。grid 同时维护了一个内存块缓存cache_map相关的Grid.Read/Grid.Write结构通过读写 IOP 并发访问底层存储。Superblock逻辑根指针与原子更新Superblock 保存逻辑根指针。物理上这个根指针由若干块引用BlockReference组成这些块合在一起指定了所有 LSM 树的 manifest清单。文档给出的抽象结构为pub const SuperBlock struct { manifest_oldest: BlockReference, manifest_newest: BlockReference, free_set: BlockReference, };Superblock 位于数据文件的固定位置因此副本启动时可以读取 superblock → 读取根块的索引与校验和 → 进而访问 grid 中的其余数据。除 manifest 外superblock 还引用一个压缩位图free set该位图本身也存放在 grid 中标记所有当前未分配的 grid 块。Checkpointsuperblock 在源码中的真实形态源码 src/vsr/superblock.zig 中的Checkpoint结构体比文档中的抽象描述更细它不仅包含manifest_oldest_address/checksum与manifest_newest_address/checksum还包括free_set_blocks_acquired与free_set_blocks_released两组字段各自的last_block_address、last_block_checksum、size、聚合checksum。acquired/released 的区分是因为 free set 通过获取/释放两个增量的方式记录分配变化。superblock.zig 还提供了manifest_reference()与free_set_reference()等辅助函数把 checkpoint 字段组装成文档中的 BlockReference 形态见 src/vsr/superblock.zig。低频批量刷新为什么 superblock 不能代表全部持久化状态Superblock 的持久化更新必须原子完成且要写入的数据量不小数 MB。为了摊薄这一成本superblock 相对不频繁地刷盘。正常操作模式是副本启动将当前 superblock 与 free set 读入内存随后持续分配并写入新的 grid 块从位图中挑选空闲项尽管新分配的 grid 块会被立即写盘但磁盘上的 superblock不会被同步更新superblock 可达的逻辑状态保持不变直到写入的新 grid 块积累到相当大的量副本才原子地写出新的 superblock附带新的 free set 与新的逻辑根指针superblock manifest。如果副本崩溃并重启它会从上一个 superblock 开始但得益于确定性崩溃后重放操作会得到与之前完全相同的磁盘与内存状态。4 份拷贝与仲裁读取对抗错位读为实现 superblock 的原子更新superblock 在物理上以4 份不同的拷贝存于磁盘superblock_copies 4见 src/config.zigsuperblock_zone_size superblock_copy_size * constants.superblock_copies见 src/vsr/superblock.zig。启动后副本挑选至少写入了 2 份拷贝的、最新的 superblock即 quorum 为 2。为什么不直接挑选最新的一份拷贝因为与 grid 块不同superblock 是自带校验和的它易受错位读misdirected read影响——一次错位读可能恰好藏起唯一的、最新的那份拷贝。多拷贝 仲裁读正是为了消除这一风险。源码还通过编译期约束保证superblock_copies只能是{ 4, 6, 8 }之一以支持弹性仲裁见 src/vsr/superblock.zig。Write-Ahead Log网格之外的逻辑增量由于 superblock以及它所代表的逻辑 grid 状态是低频、突发式更新的它无法单独代表全部持久化状态。其余状态存放在WAL中。WAL 是一个装着 prepare 的环形缓冲区代表应该施加到 superblock/grid 所表示状态上的逻辑 diff将其叠加才能得到系统的实际当前状态。WAL 的内部细节参见 VSR 文档 Protocol: Normal。高层来看副本处理一条 prepare 时将 prepare 写入磁盘上的 WAL将 prepare 带来的变更应用到代表当前状态的内存数据结构通过分配并写入新的 grid 块将变更应用到待定的pending磁盘状态。当积累的 prepare 足够多时superblock 被更新以指向累积到目前的新磁盘状态。至此WAL、superblock、grid 三个 zone 协作共同表示抽象的持久化逻辑状态。LSM 树值、表Table与分层TigerBeetle 的持久化状态具体是一个 LSM 树的集合forest。LSM 的整体结构在单独的文档中阐述这里只讨论磁盘上的高层布局。每个 LSM 树存储一组值values这些值具备以下特征大小统一uniform in size很小数百字节按键排序键内嵌在值本身中例如Account值用timestamp作为唯一键。表Table的物理形态从中间层开始理解值在磁盘上按表table组织。每张表是值的排序数组物理上存储在多个块中value block每块存一个值的排序数组index block存指向 value block 的指针以及边界键boundary keys。文档给出的三个关键结构体const TableValueBlock struct { values_sorted: [value_count_max]Value, }; const TableIndexBlock struct { value_block_checksums: [value_block_count_max]u128, value_block_indexes: [value_block_count_max]u64, value_block_key_max: [value_block_count_max]Key, }; const TableInfo struct { tree_id: u16, index_block_index: u64, index_block_checksum: u128, key_min: Key, key_max: Key, };要在一张表内查找某个值先在 index block 上做二分查找定位可能持有该值的 value block再在 value block 内部做二分查找。表的物理大小受限于单个 index block 能容纳的 value block 引用数量。此外表还被进一步人为限制为最多持有某个编译期常量数量的条目在 src/lsm/schema.zig 中体现为ManifestNode.entry_count_max等容量常量。表被组织成分层levels每一层包含的表数量指数级增加。分层与 Compaction同一层内的表两两不相交pairwise disjoint不同层的表可能重叠但遵循 LSM 的关键不变量浅层中的值覆盖深层中的值。这意味着所有修改都发生在第一层纯内存层。一个异步 compaction 过程负责重新平衡各层。Compaction 从 A 层取出一张表找出 A1 层中与该表相交的所有表把那些表从 A1 层移除并将相交结果插入。其效果可示意为一系列事件const CompactionEvent struct { label: Label table: TableInfo, // points to tables index block }; const Label struct { level: u6, event: enum(u2) { insert, update, remove }, };Manifest树状态如何以事件日志存储更关键的认识是一棵树的当前状态可以隐式地表示为一系列插入/移除事件且该序列从空表集合开始——这正是它在数据文件中的物理表示方式具体来说每个 LSM 树是一组 layer 的集合而这些 layer 以事件日志的形式隐式存储。日志由一串ManifestBlock组成const ManifestBlock struct { previous_manifest_block: BlockReference, labels: [entry_count_max]Label, tables: [entry_count_max]TableInfo, };Manifest 是网格内的链表on-disk, in-grid linked list每个 manifest 块持有对前一个块的引用。这一点在源码 src/lsm/manifest_log.zig 中得到印证写入新 manifest 块时会以当前最新块的地址与校验和填充previous_manifest_block_address与previous_manifest_block_checksum。LSM 文档的 Manifest Log 一节也说明每个 manifest 块引用其按时间顺序的前一个块且头块head manifest block上的引用会悬空——它所引用的块已经被压实掉了。Superblock 随后为所有树存储 manifest 日志的最旧与最新块const Superblock { manifest_block_oldest_address: u64, manifest_block_oldest_checksum: u128, manifest_block_newest_address: u64, manifest_block_newest_checksum: u128, free_set_last_address: u64, free_set_last_checksum: u128, };这与 src/vsr/superblock.zig 中 checkpoint 字段一一对应manifest_oldest_address/checksum、manifest_newest_address/checksum以及 free set 相关字段。全部串起来从 Superblock 到具体 Value 的寻址链将以上各部分串联TigerBeetle 数据文件的完整逻辑如下状态被表示为若干 LSM 树的集合而Superblock 是一切状态的根。对每棵 LSM 树superblock 都保存着构成该树 manifest 日志的各块指针——manifest 日志是一串对单张表添加/删除事件的记录。通过重放这段 manifest 日志可以在内存中重建 manifestManifest描述单棵 LSM 树的层与表表Table是指向其 index block 的指针index block是指向 value block 的指针的排序数组value block是值的排序数组。于是一次完整的数据访问路径是superblock → manifest 日志事件链→ Manifest → TableInfo → index block → value block → 排序后的 Value。而写入路径则是新值写为新的 grid 块 → 更新/追加 manifest 日志事件 → 待 prepare 积累足够后原子更新 superblock 并换新 free set。进一步阅读VSR 文档WAL 正常工作流见 Protocol: Normalgrid 块粒度的修复与同步见 Protocol: Repair GridLSM 文档树的表、compaction、快照与 manifest 的完整讨论源码索引src/vsr/grid.ziggrid 实现、src/vsr/superblock.zigsuperblock 与 checkpoint、src/lsm/manifest_log.zigmanifest 链表、src/config.zigblock_size 与 superblock_copies、src/constants.zigsector_size。提示本文呈现的是数据文件的高层布局为便于直觉而做了适度简化。字节级细节请以源码为准——正如原文档所言数据文件的精确定义最终都在源码的注释与断言之中。【免费下载链接】tigerbeetleThe financial transactions database designed for mission critical safety and performance.项目地址: https://gitcode.com/GitHub_Trending/ti/tigerbeetle创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
TigerBeetle 数据文件（Data File）内部布局：WAL、Superblock 与 Grid 如何协作
TigerBeetle 数据文件Data File内部布局WAL、Superblock 与 Grid 如何协作【免费下载链接】tigerbeetleThe financial transactions database designed for mission critical safety and performance.项目地址: https://gitcode.com/GitHub_Trending/ti/tigerbeetleTigerBeetle 将单个副本的全部持久化状态存放在一个名为 data file 的文件中惯例扩展名为.tigerbeetle。本文基于 data_file.md 展开从物理分区write-ahead log、superblock、grid讲到逻辑结构LSM 森林、manifest 日志并结合仓库源码给出字节级细节的索引帮助你理解一个文件如何承载数 TB 的确定性数据库状态。读完本文你将掌握 TigerBeetle 数据文件的整体布局、superblock 原子更新机制、grid 块寻址方式以及 LSM 树如何以事件日志的形式隐式存储在文件中。数据文件的三大部分WAL、Superblock 与 GridTigerBeetle 的每个副本将全部数据存放在一个单一文件中即 data file。该文件被划分为若干 zone区域最主要的三个是write-ahead logWAL预写日志存放 prepare代表应施加到 superblock/grid 所表示状态之上的逻辑增量superblock位于数据文件的固定位置保存逻辑根指针是启动时定位全部数据的入口grid占据数据文件的绝大部分体积可达数 TB是一个由 512KiB 块构成的弹性数组。在 src/config.zig 中可以看到两个关键编译期常量默认block_size 512 * KiB、superblock_copies 4而扇区大小sector_size 4096定义在 src/constants.zig。这些常量共同约束了数据文件的物理布局。Grid弹性块数组与块寻址Grid 是一个弹性elastic的 512KiB 块数组作为原始存储层为上层数据结构尤其是 LSM 树提供映射。其块与块指针的 Zig 定义与文档一致为pub const Block [constants.block_size]u8; pub const BlockPtr *align(constants.sector_size) Block;在源码 src/vsr/grid.zig 中实际定义更精确BlockPtr *align(constants.sector_size) [constants.block_size]u8即每个块按扇区对齐。由于 TigerBeetle 是确定性的deterministic所有同步到最新状态的副本其 grid 的已使用部分完全相同。这一存储确定性被用来在 grid 块粒度上实现状态同步sync与修复repair详见 VSR 文档中的 Protocol: Repair Grid。每个 grid 块由一个u64索引index加一个u128校验和checksum组成的二元组标识pub const BlockReference struct { index: u64, checksum: u128, };校验和存放在块外部而不是块内部——这是为了防止错位写入/读取misdirected write/read损坏数据。因此要读取某个块你必须先从别处另一块或 superblock得知该块的索引与校验和。grid 整体实现了纯粹的purely functional、持久化的、带垃圾回收的数据结构通过交换指向根节点的指针来原子更新——这正是文件系统中常见的 copy-on-write 技术。可以这样理解TigerBeetle 的 data file 本质上就是一个文件系统grid 是存储层superblock 保存着逻辑根指针。在 src/vsr/grid.zig 中可以看到地址与偏移的换算(address - 1) * block_size即 grid 块地址从 1 开始物理偏移为(地址 - 1) × 块大小。grid 同时维护了一个内存块缓存cache_map相关的Grid.Read/Grid.Write结构通过读写 IOP 并发访问底层存储。Superblock逻辑根指针与原子更新Superblock 保存逻辑根指针。物理上这个根指针由若干块引用BlockReference组成这些块合在一起指定了所有 LSM 树的 manifest清单。文档给出的抽象结构为pub const SuperBlock struct { manifest_oldest: BlockReference, manifest_newest: BlockReference, free_set: BlockReference, };Superblock 位于数据文件的固定位置因此副本启动时可以读取 superblock → 读取根块的索引与校验和 → 进而访问 grid 中的其余数据。除 manifest 外superblock 还引用一个压缩位图free set该位图本身也存放在 grid 中标记所有当前未分配的 grid 块。Checkpointsuperblock 在源码中的真实形态源码 src/vsr/superblock.zig 中的Checkpoint结构体比文档中的抽象描述更细它不仅包含manifest_oldest_address/checksum与manifest_newest_address/checksum还包括free_set_blocks_acquired与free_set_blocks_released两组字段各自的last_block_address、last_block_checksum、size、聚合checksum。acquired/released 的区分是因为 free set 通过获取/释放两个增量的方式记录分配变化。superblock.zig 还提供了manifest_reference()与free_set_reference()等辅助函数把 checkpoint 字段组装成文档中的 BlockReference 形态见 src/vsr/superblock.zig。低频批量刷新为什么 superblock 不能代表全部持久化状态Superblock 的持久化更新必须原子完成且要写入的数据量不小数 MB。为了摊薄这一成本superblock 相对不频繁地刷盘。正常操作模式是副本启动将当前 superblock 与 free set 读入内存随后持续分配并写入新的 grid 块从位图中挑选空闲项尽管新分配的 grid 块会被立即写盘但磁盘上的 superblock不会被同步更新superblock 可达的逻辑状态保持不变直到写入的新 grid 块积累到相当大的量副本才原子地写出新的 superblock附带新的 free set 与新的逻辑根指针superblock manifest。如果副本崩溃并重启它会从上一个 superblock 开始但得益于确定性崩溃后重放操作会得到与之前完全相同的磁盘与内存状态。4 份拷贝与仲裁读取对抗错位读为实现 superblock 的原子更新superblock 在物理上以4 份不同的拷贝存于磁盘superblock_copies 4见 src/config.zigsuperblock_zone_size superblock_copy_size * constants.superblock_copies见 src/vsr/superblock.zig。启动后副本挑选至少写入了 2 份拷贝的、最新的 superblock即 quorum 为 2。为什么不直接挑选最新的一份拷贝因为与 grid 块不同superblock 是自带校验和的它易受错位读misdirected read影响——一次错位读可能恰好藏起唯一的、最新的那份拷贝。多拷贝 仲裁读正是为了消除这一风险。源码还通过编译期约束保证superblock_copies只能是{ 4, 6, 8 }之一以支持弹性仲裁见 src/vsr/superblock.zig。Write-Ahead Log网格之外的逻辑增量由于 superblock以及它所代表的逻辑 grid 状态是低频、突发式更新的它无法单独代表全部持久化状态。其余状态存放在WAL中。WAL 是一个装着 prepare 的环形缓冲区代表应该施加到 superblock/grid 所表示状态上的逻辑 diff将其叠加才能得到系统的实际当前状态。WAL 的内部细节参见 VSR 文档 Protocol: Normal。高层来看副本处理一条 prepare 时将 prepare 写入磁盘上的 WAL将 prepare 带来的变更应用到代表当前状态的内存数据结构通过分配并写入新的 grid 块将变更应用到待定的pending磁盘状态。当积累的 prepare 足够多时superblock 被更新以指向累积到目前的新磁盘状态。至此WAL、superblock、grid 三个 zone 协作共同表示抽象的持久化逻辑状态。LSM 树值、表Table与分层TigerBeetle 的持久化状态具体是一个 LSM 树的集合forest。LSM 的整体结构在单独的文档中阐述这里只讨论磁盘上的高层布局。每个 LSM 树存储一组值values这些值具备以下特征大小统一uniform in size很小数百字节按键排序键内嵌在值本身中例如Account值用timestamp作为唯一键。表Table的物理形态从中间层开始理解值在磁盘上按表table组织。每张表是值的排序数组物理上存储在多个块中value block每块存一个值的排序数组index block存指向 value block 的指针以及边界键boundary keys。文档给出的三个关键结构体const TableValueBlock struct { values_sorted: [value_count_max]Value, }; const TableIndexBlock struct { value_block_checksums: [value_block_count_max]u128, value_block_indexes: [value_block_count_max]u64, value_block_key_max: [value_block_count_max]Key, }; const TableInfo struct { tree_id: u16, index_block_index: u64, index_block_checksum: u128, key_min: Key, key_max: Key, };要在一张表内查找某个值先在 index block 上做二分查找定位可能持有该值的 value block再在 value block 内部做二分查找。表的物理大小受限于单个 index block 能容纳的 value block 引用数量。此外表还被进一步人为限制为最多持有某个编译期常量数量的条目在 src/lsm/schema.zig 中体现为ManifestNode.entry_count_max等容量常量。表被组织成分层levels每一层包含的表数量指数级增加。分层与 Compaction同一层内的表两两不相交pairwise disjoint不同层的表可能重叠但遵循 LSM 的关键不变量浅层中的值覆盖深层中的值。这意味着所有修改都发生在第一层纯内存层。一个异步 compaction 过程负责重新平衡各层。Compaction 从 A 层取出一张表找出 A1 层中与该表相交的所有表把那些表从 A1 层移除并将相交结果插入。其效果可示意为一系列事件const CompactionEvent struct { label: Label table: TableInfo, // points to tables index block }; const Label struct { level: u6, event: enum(u2) { insert, update, remove }, };Manifest树状态如何以事件日志存储更关键的认识是一棵树的当前状态可以隐式地表示为一系列插入/移除事件且该序列从空表集合开始——这正是它在数据文件中的物理表示方式具体来说每个 LSM 树是一组 layer 的集合而这些 layer 以事件日志的形式隐式存储。日志由一串ManifestBlock组成const ManifestBlock struct { previous_manifest_block: BlockReference, labels: [entry_count_max]Label, tables: [entry_count_max]TableInfo, };Manifest 是网格内的链表on-disk, in-grid linked list每个 manifest 块持有对前一个块的引用。这一点在源码 src/lsm/manifest_log.zig 中得到印证写入新 manifest 块时会以当前最新块的地址与校验和填充previous_manifest_block_address与previous_manifest_block_checksum。LSM 文档的 Manifest Log 一节也说明每个 manifest 块引用其按时间顺序的前一个块且头块head manifest block上的引用会悬空——它所引用的块已经被压实掉了。Superblock 随后为所有树存储 manifest 日志的最旧与最新块const Superblock { manifest_block_oldest_address: u64, manifest_block_oldest_checksum: u128, manifest_block_newest_address: u64, manifest_block_newest_checksum: u128, free_set_last_address: u64, free_set_last_checksum: u128, };这与 src/vsr/superblock.zig 中 checkpoint 字段一一对应manifest_oldest_address/checksum、manifest_newest_address/checksum以及 free set 相关字段。全部串起来从 Superblock 到具体 Value 的寻址链将以上各部分串联TigerBeetle 数据文件的完整逻辑如下状态被表示为若干 LSM 树的集合而Superblock 是一切状态的根。对每棵 LSM 树superblock 都保存着构成该树 manifest 日志的各块指针——manifest 日志是一串对单张表添加/删除事件的记录。通过重放这段 manifest 日志可以在内存中重建 manifestManifest描述单棵 LSM 树的层与表表Table是指向其 index block 的指针index block是指向 value block 的指针的排序数组value block是值的排序数组。于是一次完整的数据访问路径是superblock → manifest 日志事件链→ Manifest → TableInfo → index block → value block → 排序后的 Value。而写入路径则是新值写为新的 grid 块 → 更新/追加 manifest 日志事件 → 待 prepare 积累足够后原子更新 superblock 并换新 free set。进一步阅读VSR 文档WAL 正常工作流见 Protocol: Normalgrid 块粒度的修复与同步见 Protocol: Repair GridLSM 文档树的表、compaction、快照与 manifest 的完整讨论源码索引src/vsr/grid.ziggrid 实现、src/vsr/superblock.zigsuperblock 与 checkpoint、src/lsm/manifest_log.zigmanifest 链表、src/config.zigblock_size 与 superblock_copies、src/constants.zigsector_size。提示本文呈现的是数据文件的高层布局为便于直觉而做了适度简化。字节级细节请以源码为准——正如原文档所言数据文件的精确定义最终都在源码的注释与断言之中。【免费下载链接】tigerbeetleThe financial transactions database designed for mission critical safety and performance.项目地址: https://gitcode.com/GitHub_Trending/ti/tigerbeetle创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
