开发工具CLI后端【免费下载链接】saplingA Scalable, User-Friendly Source Control System.项目地址https://gitcode.com/gh_mirrors/sa/sapling点击查看免费下载IndexedLog 是 Sapling 的核心磁盘存储格式被 dag有向无环图、revisionstore修订存储等大量组件使用。它以Log追加式主存储 多 Index纯函数驱动索引的架构同时实现了 O(log N) 哈希查找、无拓扑序约束的按哈希插入、无锁读取与数据完整性校验。本文基于官方内部文档 website/docs/dev/internals/indexedlog.md 并结合 eden/scm/lib/indexedlog 源码实现完整解析其设计动机、磁盘格式、并发模型、修复机制与实际应用帮助你理解 Sapling 底层数据如何被组织、加速与自愈。设计背景为什么不能沿用 Revlog、Git 与 SQLiteIndexedLog 并非凭空发明而是在评估了三类既有存储方案Mercurial 的 Revlog、Git 的 loose/pack 文件、SQLite的局限性之后专门设计的产物。理解这些局限是理解 IndexedLog 每一项特性取舍的前提。Revlog 的三大限制历史上Sapling 的前身使用 revlog 作为主要存储格式但它存在三个结构性缺陷修订必须满足拓扑序Revlog 只允许追加且要求追加的修订必须是已有修订的祖先。当按需拉取修订时如果先取到了较新的修订就无法再追加作为其祖先的较老修订导致数据无法落盘。按哈希查找可能退化为线性扫描当修订数量很大时通过 hash 定位一条记录需要线性遍历性能明显劣化。虽然可以用额外构建的索引绕开但那是补丁式的权宜之计。通用性不足Revlog 中一条记录只能有一个 SHA1 作为 key。但像 obsstore废除修订存储这样的场景需要同时用前驱predecessor和后继successor多种索引去查找记录且一条记录可能对应多个前驱或后继Revlog 无法表达。Git loose / pack 文件的问题Git 的格式loose 对象与 pack 文件没有拓扑序限制理想情况下按哈希查找是 O(log N)。但它有两个不足依赖周期性的repack才能维持查找性能pack 文件过多时性能会下降属于需要人工/定时维护的方案。同样不支持多索引、多 key 的通用场景。SQLite 的问题SQLite 功能强大天然支持多索引且无需 repack 即可维持时间复杂度。但它的核心问题在于锁模型Sapling 历史上采用只追加append-only策略来达成无锁读取而 SQLite 无论读还是写都需要加锁与这一策略冲突。结论IndexedLog 就是为同时满足无锁读 O(log N) 查找 无拓扑序追加 多索引通用性这四个目标而生的自有格式。设计目标一览IndexedLog 明确追求以下核心属性源自 indexedlog.mdO(log N) 查找且不需要repack来维持性能按哈希插入不受拓扑序限制无锁读取通过较大的文件只追加 较小的文件原子替换来实现依赖现代文件系统 API事务性文件系统或块级写时复制理论上更好但普遍不可用通用性支持多索引、每条记录多 key数据完整性锦上添花在硬重启或误操作如对仓库数据执行sed -i后能精确定位损坏的数据范围并提供恢复手段。整体架构Log 与多个 Index一个 IndexedLog 由一个 Log和多个环绕它的 Index组成源码中由Log结构体持有indexes: VecIndex体现Log 是数据的唯一事实来源single source of truthIndex 完全由 Log 与索引函数派生而来——只要 Log 完好损坏的 Index 可以删除后重建。在 lib.rs 的模块说明中官方将其概括为an integrity-checked, append-only storage with index support带索引支持、带完整性校验的追加式存储并建议先看log::Log索引可独立使用index::Index。Log追加式的主存储语义模型Log 按插入顺序保存条目每条目是一个字节切片。接口语义上类似于LinkedListVecu8但只允许push_back不允许push_front。支持的操作只有两个按插入顺序迭代所有条目在末尾追加一条新条目。明确不支持的操作按偏移量随机读取某条随机访问删除某条记录。与关系型数据库或文档数据库不同Log 自身不定义条目内字节的含义字节的语义完全由上层应用决定。官方文档原话是The meaning is up to the application to decide.磁盘布局源码级从 log.rs 的格式注释可以看到Log 在磁盘上由一个目录构成包含三类文件主日志文件log追加式文件每条记录格式为ENTRY_FLAGS LEN(CONTENT) CHECKSUM CONTENT即标志位 内容长度 校验和 内容校验和可以是空的、XXHASH64 或 XXHASH32多个用户自定义索引文件每个索引使用追加式的 radix-tree 磁盘表示外加一个小的、非追加式的校验和文件一个小的元数据文件meta记录 log 与 index 文件的逻辑长度逻辑长度用于识别哪些尾部字节属于未完整刷新的垃圾数据。文件命名常量可参见 log.rs主文件名为log头部魔数为indexedlog0\012 字节因此有效数据从偏移 12 开始元数据文件名为meta。索引文件前缀为index2-元数据前缀为2-见 open_options.rs。日志本身的写耗时会记录到indexedlog.log.write_ms计数器sync次数记录到indexedlog.sync见 log.rs这些指标可供上层观测磁盘写入压力。Index纯函数驱动的多索引一个 Log 可以挂多个索引。每个索引由两部分组成索引名name索引函数index function一个接收条目字节切片、输出一组IndexOutput的纯函数。IndexOutput 的四种指令IndexOutput是一个枚举用于指示 IndexedLog 执行以下操作之一定义见 open_options.rs变体语义适用场景Reference(Rangeu64)索引 key 是输入条目内的一段字节切片相对引用优先使用生成的索引更小Owned(Box[u8])索引 key 是与输入无关的一段独立字节key 不在条目内如条目被压缩时使用Remove(Box[u8])在索引中移除该 key 关联的所有值删除操作只影响索引条目仍留在 Log 中RemovePrefix(Box[u8])在索引中移除所有以该前缀开头的 key批量删除每条记录可以产生零个或多个key。文档中给出了一个直观例子若 Log 存的是 Git 提交索引用于根据父提交哈希找子提交则索引函数解析提交元数据后把 0、1、2 个甚至更多父提交哈希都输出为 key。索引函数必须是纯 Rust 函数与数据库不同索引函数是原生 Rust 代码而非 SQL 或 JSON 这类可序列化的独立语言。这意味着编译后的 Rust 函数无法序列化到磁盘因此每次从磁盘加载 IndexedLog 时应用必须提供完全相同的索引函数索引函数应当纯净且快速——不应依赖网络、文件系统或外部随机源见 open_options.rs。索引命名约定修改索引函数时必须同时修改索引名否则 IndexedLog 可能错误地复用旧的索引数据。源码中对索引名还有两条硬性约束见 open_options.rs名字会作为索引文件名的组成部分因此不能用用户生成的内容也不能包含..或/这类路径穿越字符。Standalone Index可独立使用的索引Index 可以不依赖 Log 单独使用。其接口语义类似于BTreeMapVecu8, LinkedListu64但主存储是文件系统而非内存。支持的操作插入 (key, value)value 被插入到该 key 对应链表的前端也可以直接丢弃现有链表按范围查找 key范围查询按范围删除 key范围删除。内部结构radix tree 单向链表key 部分是一棵radix tree基数树每个节点有16 个孩子4 bit专门为了支持 hex十六进制前缀查找。源码 index.rs 说明RADIX 条目有 16 个孩子主要服务于源码控制场景的十六进制哈希缺失的孩子在跳转表中对应偏移为 0。value 部分是单向链表支持push_front不支持push_back。无锁读取持久化数据结构Index 的磁盘格式采用**持久化数据结构persistent data structure**来实现无锁读取主索引文件只追加指向根树节点的指针是一小块独立数据通过**原子替换atomic-replace**更新。与 Log 配合时的 lag滞后机制当与 Log 一起使用时LinkedListu64中的u64就是文件偏移。这些偏移不出现在 Log 的公共 API 中以防止误用。由于为单条记录更新索引需要 O(log N) 的磁盘空间频繁的小写入很不划算因此Log 允许磁盘上的索引对部分条目滞后滞后部分的索引会在内存中按需构建Log::open时补齐见 open_options.rs 对lag_threshold的说明。这正是IndexDef中lag_threshold字段的用途——它表示磁盘上允许未被索引的字节数实际效果与该索引函数的执行速度正相关。并发写入模型快照语义与 sync 锁IndexedLog 的并发模型可以概括为读快照、写缓冲、sync 落盘加载即快照当 IndexedLog或独立的 Index从磁盘加载时相当于拍了一张快照。之后磁盘上的变化不会影响已加载的实例前提是所有文件写入都经由 IndexedLog 的 API。写入先在内存缓冲无锁内存中的写入对其他进程、以及其他已加载的 IndexedLog 实例完全不可见。sync才触碰磁盘sync操作会先获取文件系统锁阻止其他写入者然后拾取磁盘上最新的文件系统状态若有变化把更新的 Log 和索引写到磁盘最后释放锁。两个进程或同一进程内的两个 IndexedLog 实例并发sync()同一个磁盘 IndexedLog 时双方的待写入内容都会落盘但写入顺序不确定取决于谁先拿到文件系统锁。这是文档明确说明的行为边界。代码层面Log在 flush 时会通过ScopedDirLock对目录加flock见 log.rs 的注释Flushing in-memory parts to disk requires taking a flock on the directory并借助基于 mmap 的跨进程廉价变更检测器SharedChangeDetector判断磁盘是否真的变了见 log.rs。数据完整性xxhash 校验与 repair 修复校验策略Log 与 Index 都使用 xxhash 保证数据完整性但粒度不同Log按条目计算校验和根据条目大小自动选择 XXH32 或 XXH64对应ChecksumType::Auto也可显式指定Xxhash64或Xxhash32见 open_options.rs其中 XXH64 在 64 位平台更快、占用空间更大XXH32 更省空间、适合短条目Index内部每 1MB 数据维护一条校验和源码常量INDEX_CHECKSUM_CHUNK_SIZE_LOGARITHM: u32 20即 2^20 字节见 log.rs。所有数据读取都会触发完整性校验错误会报告给应用层。此外Index 旁边会生成一个index.verified缓存文件魔数ilogvrf1记录当前操作系统启动后哪些校验块已被验证过使后续进程可以跳过重复哈希每验证 16 个新块即保存一次缓存以降低突然退出时的损失见 index.rs。repair 修复流程IndexedLog 支持repair修复操作将 Log截断到通过完整性校验的条目为止丢弃尾部损坏数据重建损坏或过期的索引因为索引可由 Log 索引函数重新派生。repair的语义在源码 repair.rs 中有详细定义Repairtrait 的repair(path)负责修复指定路径的结构可递归OpenWithRepair::open_with_repair约定先 open若遇到数据损坏错误则修复一次再 open。两点重要限制它只修复打开过程中发现的一类损坏通常由 OS 崩溃或硬重启导致不修复 open 之后读取数据时可能发生的损坏出于性能考虑它不会全量验证所有数据如果还有其他读者repair 会被跳过——因为 IndexedLog 依赖追加式保证无锁读取而 repair 是非追加的破坏性写入可能让正在读取的其他进程静默拿到错误数据。修复过程会向目录下的repair.log追加诊断信息超过 1MB 时自动截断重写见 repair.rs。RotateLog有界的客户端缓存RotateLog 把**日志轮转log rotation**的思想应用到 IndexedLog 上源码 rotate.rs维护一个Log 列表当某个 Log 超过大小上限时创建新 Log并可选地删除最老的 Log磁盘上表现为一个目录内含0/、1/、2/...每个 Log 一个子目录外加一个latest文件记录当前活跃目录见 rotate.rs。RotateLog 的定位是客户端缓存客户端希望磁盘占用有界且数据可从服务器重新拉取。其默认配置见 rotate.rs为保留 2 个 Logmax_log_count 2值越大越伤查找性能单个 Log 达到 2GB 触发轮转max_bytes_per_log 2_000_000_000无索引、不自动创建、追加后不自动 sync。RotateLog 的OpenOptions还支持auto_sync_threshold内存缓冲超过阈值自动 sync约束内存占用、flush_filtersync 时过滤/改写内容例如避免写回最新 Log 中已存在的内容、btrfs_compressionbtrfs 透明压缩下按物理大小而非表观大小判断轮转等选项见 rotate.rs。在 Sapling 中的实际应用IndexedLog 不是纸面设计而是 Sapling 大量底层组件的存储地基。以下是仓库内可验证的两大应用场景。1. DAG修订图存储Sapling 的 DAG 层直接构建在 IndexedLog 之上。indexedlog_dag.rs 中Dag::default_open_options通过multi::OpenOptions::from_name_opts声明了两个命名 Logidmap2IdMapid ↔ 顶点哈希映射的日志iddagIdDagid 级有向无环图的索引化日志存储。打开 DAG 时调用open_with_repair获得自动修复能力indexedlog_dag.rs写入则通过MultiLog的锁 write_meta完成元数据持久化。这里同时用到了本篇文章讲过的多 Log、索引、repair 等全部机制——DAG 的高效祖先查询O(log N)正是靠这些索引支撑的。2. RevisionStore修订数据存储revisionstore模块是 IndexedLog 的另一个重要用户indexedlogdatastore.rs以 IndexedLog 存储修订数据内容indexedloghistorystore.rs以 IndexedLog 存储修订历史hg 风格的父/子关系索引天然是多 key 场景。这两处恰好印证了文档所说的多索引、多 key 通用性价值一条修订记录的父提交、子提交可以同时被多个索引覆盖而无需像 Revlog 那样只能有一个 SHA1 key。延伸阅读与 IndexedLog 紧密相关的还有 metalog.md元数据日志同样基于 IndexedLog/追加式存储思想与 zstdelta.md压缩增量格式常与 IndexedLog 配合存储大数据。总结IndexedLog 用一组极其克制的原语只追加的 Log 纯函数派生的多 Index 原子替换小文件 文件锁 sync换来了版本控制场景下最想要的三件事无锁读取读进程永不等待写进程无拓扑约束的按哈希插入服务端数据可按需、乱序地落盘O(log N) 查找且免 repack借助 radix tree 与持久化数据结构无需周期性维护即可保持性能稳定。在此基础上xxhash 分块校验与 repair 机制让它在面对硬重启、磁盘位翻转甚至误sed -i时具备可定位、可自愈的能力。理解 IndexedLog等于同时理解了 Sapling 的数据存储哲学——它并不追求做一个通用的数据库而是把追加式 索引 完整性这套组合拳精准地打在版本控制工作负载最痛的地方。赞分享开发工具CLI后端【免费下载链接】saplingA Scalable, User-Friendly Source Control System.项目地址https://gitcode.com/gh_mirrors/sa/sapling点击查看免费下载相关推荐Apache Doris存储引擎深度剖析列式存储与索引优化Apache Doris存储引擎深度剖析列式存储与索引优化 本文深入解析Apache Doris存储引擎的核心技术重点剖析列式存储架构的优势与实现原理详细数据库OLAP大数据数据仓库分布式数据库实时分析列式数据库存储与检索从日志结构到 B 树、列式存储与向量索引的存储引擎全景解析DDIA 第四章存储与检索从日志结构到 B 树、列式存储与向量索引的存储引擎全景解析DDIA 第四章 本文基于 content/zh/ch4.md https://lin文档教程OpenTrack性能优化终极指南多GPU并行训练与JAX加速技巧OpenTrack性能优化终极指南多GPU并行训练与JAX加速技巧 OpenTrack作为Any2Track的官方实现是一个专注于机器人运动跟踪的开源项目。上一篇LeetCode 1055 Shortest Way to Form String 四种解法全解析子序列判定、双指针、倒排索引与 2D 下一出现位置表下一篇深入理解 Terraform AWS Provider 的 aws_iam_saml_provider 数据源读取 IAM SAML 联合身份元数据创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考