Sapling 的 Indexed Log：一份从 Revlog 到 Append-Only 索引存储的设计解析-北京尧图网络

开发工具CLI后端【免费下载链接】saplingA Scalable, User-Friendly Source Control System.项目地址https://gitcode.com/gh_mirrors/sa/sapling点击查看免费下载导读Indexed Log索引日志是 Sapling 源码库eden/scm/lib/indexedlog中一套带完整性校验的追加写存储自动索引的核心数据结构它解决了传统版本控制存储格式中按哈希查找慢、文件数过多、维护成本高的三大痛点。本文以 Sapling 仓库中的技术幻灯片 201808-indexedlog 为骨架结合其 Rust 实现源码从问题背景、设计目标、磁盘布局、读写模型、事务与修复机制五个层面讲清 indexedlog 的完整设计与落地细节。读完本文你将掌握 indexedlog 的日志/索引分离架构、O(log N) 插入与查找的原理、以及它在 Sapling 中的真实用途。一、背景为什么需要一个新的存储格式1.1 Revlog传统 Mercurial 的单体数据结构幻灯片开篇指出Revlog 是驱动传统 Mercurial 的单体数据结构每个文件对应.i索引与.d数据两个文件采用 delta 链存储。rev 0存全量文本后续rev n存相对于前一个版本的 delta.i | .d ------------------ | ------------------- | rev 0 metadata | -- points to - | rev 0 full text | ------------------ | ------------------ | rev 1 metadata | -- points to - | rev 1 delta | ------------------ | --------------- | rev 2 metadata | -- points to - | rev 2 delta | ------------------ | ----------------按Revision Number修订号查找是 O(1)插入也是 O(1)并带有 SHA1 哈希做完整性校验。问题也随之而来按 SHA1 哈希查找是 O(N)在无索引的首次遍历时Filelog 产生的 inode 数量过多由于修订号按拓扑排序稀疏sparse很难支持。当时的用法客户端用它存 Changelog服务端几乎所有数据Changelog、manifest、filelog都依赖它且强制依赖 hgsql。1.2 Loose file 与 Pack fileGit 的两类格式Git 没有修订号采用两类格式Loose file每个文件每个修订一个文件无 delta。借助内核/文件系统按 SHA1 查找约 O(log N)。但空间极其低效且inode 数量过多。Pack file将一段范围内的文件修订打包成一个.pack文件配合.idx索引采用 delta 编码。.idx是两级结构——Level 1 按首字节分桶Level 2 是排序后的 SHA1 列表.pack则与 revlog 的.d类似.idx | .pack Level1 Level2 | Similar to 1st byte Sorted SHA1s | revlog.d ---- ------ | ----------- | 00 | -- | 0000 | --------- | full text | ---- | 0002 | ---. | ---------- | 01 | | ... | \ .-- | delta |Pack 的查找约 O(log N)对同一文件的插入约 O(N/256)新建文件插入约 O(1)。但问题在于Pack 文件数量M过多会拖累性能查找退化为 O(M·log(N/M))若 pack 文件自包含则空间变大delta 链效率下降必须定期repack维持性能而 repack 可能非常昂贵。1.3 Obsstore 与 Changelog 的多索引问题Obsstore变更观测存储不使用修订号但没有索引任何访问 obsmarkers 的操作都要付出 O(N) 加载全部标记的代价且由于需要按前驱predecessors或后继successors双向查找需要多个索引。Changelog 同样需要多个索引nodemap 哈希表、parent-child 父子关系映射。1.4 问题总结幻灯片用一张对比表总结了各类格式的取舍emoji 表情cry差smiley好slightly_smiling_face一般scream极差thinking存疑维度RevlogLoosePackRevnum 修订号差好好Insertion 插入好一般存疑Lookup 查找差好一般Space 空间一般极差一般Inode 数量差极差好Maintenance 维护好好差除此之外Obsstore 需要多索引Changelog 需要多索引nodemap、parent-child map。这正是设计 Indexed Log 的直接动机。二、Indexed Log 的设计目标与总体架构2.1 设计目标针对上述问题幻灯片明确提出 Indexed Log 的目标摆脱对修订号的依赖Decouple from revision numbersO(log N) 插入O(log N) 查找除了修复损坏之外任何情况下都避免 O(N)无需任何维护操作即可保持上述时间复杂度强完整性Strong integrity。一句话概括把日志即真相索引即缓存这一现代存储思想引入版本控制场景。2.2 总体架构一个通用目的的存储组件幻灯片强调 Indexed Log 是**通用目的general purposed**的存储组件其内部结构分为四层.--------------------------------------------. | File Storage | | | | .-----------------------------. | | | Indexed Log | | | | | | | | .-------------------------. | | | | | Append Only Radix Index | | | | | | | | | | | | .-----------------. | | .-------. | | | | | Integrity Check | | | | Zstd | | | | | | for append only | | | | Delta | | | | | | files | | | ------- | | | | ----------------- | | | | | ------------------------- | | | ----------------------------- | --------------------------------------------最外层是File Storage文件存储中间是Indexed Log本身Append-only只追加的 Radix Index基数树索引承载查找底层部件包括为追加写文件设计的Integrity Check完整性校验以及可选的Zstd Delta 压缩。在 Sapling 的 Rust 实现中这一架构对应eden/scm/lib/indexedlog/src/lib.rs里声明的模块log主日志、index索引、rotate轮转、multi多日志、repair修复、lock目录锁等。库的 crate 文档将它的核心定义为一句话Indexed Log provides an integrity-checked, append-only storage with index support提供带完整性校验的追加写存储并支持索引参见 lib.rs。2.3 核心公式Indexed Log Log真相源 Indexes缓存这是全文最关键的抽象Log日志真相的唯一来源source of truth存储一串entry每个 entry 是bytes的一个切片内部维护校验和Indexes索引纯粹的可重建缓存cache用户定义0 个或多个索引函数Index Function类型为entry - Vecbytes即从 entry 提取若干索引键Indexed Log 会根据索引函数自动构建索引索引可以仅凭 Log 完整重建且无需网络访问。2.4 磁盘布局一个目录即一个 IndexedLog幻灯片给出磁盘上的目录结构log真相源追加写的主日志文件index.{foo}名为 foo 的索引文件index.{foo}.sum索引 foo 的分块校验和文件meta根节点指针、逻辑文件长度pointers to root nodes, logical file lengths。在 Rust 实现中文件名略有演进但仍一一对应主日志文件为log常量PRIMARY_FILE元数据文件为meta常量META_FILE索引文件以index2-为前缀常量INDEX_FILE_PREFIX索引的元数据名以2-为前缀参见 log.rs 与 open_options.rs。Log::open会按需创建上述文件create(true)选项并逐步构建指定索引见 log.rs。三、The Index追加写基数树与无锁读3.1 简化示意图根指针原子替换幻灯片用一个简化例子展示索引的插入过程连续插入81c2与82ee两个键时每次插入都生成新的根节点版本Root v1、Root v2而叶子节点中保留各自的 valueInsert 81c2 | Insert 82ee | .----------------------. .------. | | | | | v | | | v ------------- | ----|-----|- ------------- | value: 81c2 | | | 1 | * | 2 | * | | value: 82ee | ------------- | ------------ ------------- ^ | ^ ---. | ---. ----|- | ----|- | 8 | * | | | 8 | * | ------ | ------ Root v1 | Root v2这张图传达的要点幻灯片原文追加写索引原子替换的根指针。读路径无锁Read is lock-free修改先在内存中累积直到显式调用flush才落盘O(log N) 插入与查找不产生新文件、无需维护。3.2 源码印证Index 的关键机制从 index.rs 的实现看索引按节点类型组织为 Radix、Leaf、Link、Key、ExtKey 与 Checksum 等节点TypedOffset枚举支持四种值操作Prepend(offset)把新值插到同键链表的头部PrependReplace替换链表后再插入新头部Tombstone为指定键删除关联值TombstonePrefix为指定前缀下的所有键删除关联值。这些定义见 index.rs。可以看到索引本身也是追加写的——删除通过墓碑Tombstone标记实现索引键的写入同样以 append-only 方式落地。索引对外提供的查询 API 与幻灯片承诺的 O(log N) 查找一一对应get(key)精确查找一个键返回LinkOffset见 index.rsscan_prefix(prefix)/scan_prefix_hex(hex_prefix)按前缀或十六进制前缀扫描见 index.rsrange(range)按字节范围扫描见 index.rsremove/remove_prefix对应墓碑操作见 index.rs。3.3 索引函数与 IndexDef索引函数定义由IndexDef承载见 open_options.rs关键设计约束函数输入是一条 entry 的字节输出零到多个索引键一个 entry 可以对应同索引的多个键例如一条 commit 可以有多个 parent 哈希函数必须纯函数且快速不能依赖网络、文件系统或外部随机源索引键可以是Reference指向 entry 内部某个区间生成更小的索引或Owned独立字节序列适用于键不在 entry 内、如数据被压缩的情形另有Remove/RemovePrefix两个删索引不动日志的操作定义见 open_options.rs索引名必须与索引函数一一对应一旦改变索引函数必须改名否则旧索引会被错误复用。IndexDef::new还带一个默认的lag_threshold滞后阈值默认 25×500 字节允许磁盘索引滞后于日志一定字节数以减少写放大、节省磁盘滞后的部分会在Log::open时于内存中按需补齐见 open_options.rs。四、The Log带校验和的追加写条目流4.1 条目的物理格式Log 把数据看作一串 entry 的追加写序列。根据 log.rs 的注释主日志文件的格式为LOG : HEADER ENTRY_LIST HEADER : indexedlog0\0 12 字节PRIMARY_START_OFFSET12 ENTRY : ENTRY_FLAGS LEN(CONTENT) CHECKSUM CONTENT CHECKSUM : XXHASH64(CONTENT) 或 XXHASH32(CONTENT)整数采用 VLQ变长整数编码XXHASH 校验和采用 LittleEndian 编码。read_entry_from_buf在读取每个 entry 时都会逐条验证校验和失败即报数据损坏错误integrity check failed见 log.rs。4.2 校验和策略Auto 自动选择校验和类型由ChecksumType控制见 open_options.rsXxhash6464 位平台效率高Xxhash32体积更小适合短 entryAuto按数据大小自动选择——实现中给出了 x64 平台的实测吞吐对比并以88 字节为阈值数据 ≥88 字节用 xxhash64否则用 xxhash32见 log.rs。4.3 内存缓冲与显式 flushLog::append只是在内存中追加 entry并同步更新内存中的索引其他进程甚至同进程的其他Log实例看不到该变更。只有调用Log::sync旧名flush才会把内存内容真正写盘见 log.rs 与 log.rs。OpenOptions提供一组与场景匹配的配置项见 open_options.rs配置项默认值作用createfalse目录不存在时是否自动创建 Log 及初始文件fsyncfalsesync返回前是否把日志与索引落盘到物理设备checksum_typeAuto条目校验和算法见 4.2auto_sync_thresholdNone内存缓冲超过阈值自动调syncSome(0)表示每次 append 后立即同步flush_filterNone在sync时过滤/重写待写入条目可跳过重复内容btrfs_compressionfalse开启 btrfs 透明 zstd 压缩感知模式4.4 sync 的五步流程Log::sync是唯一的写盘入口设计上刻意保持简单以便验证正确性见 log.rs只读快速路径若无内存脏数据只重读 meta 判断磁盘是否变化取目录锁flock重读 meta校验日志只能增长check_append_only追加主日志从 meta 记录的primary_len处 seek 后写入内存缓冲可选 fsync然后清空内存缓冲回填/刷新索引update_indexes_for_on_disk_entries让索引追上日志随后flush_lagging_indexes只落盘真正滞后超阈值的索引原子写 metawrite_meta记录新的主日志长度与各索引逻辑长度。若上一次写盘被中断如系统崩溃sync会从 meta 记录的长度处 seek 并覆盖残留的损坏字节——物理上这是覆盖写但对所有读者而言log在 meta 长度范围内仍是追加写且不可变因此无锁读的安全性不被动摇见 log.rs。4.5 读取 APILog 暴露三类读取接口均由索引或日志迭代器实现lookup(index_id, key)按索引精确查找返回按插入逆序的 entry 迭代器见 log.rslookup_prefix(index_id, prefix)/lookup_prefix_hex按前缀/十六进制前缀查找见 log.rslookup_range(index_id, range)按字节范围查找见 log.rsiter()顺序遍历全部 entry见 log.rs。所有基于索引的读取在index_out_of_sync标记被设置时都会返回错误索引不再可信宁可报错也不返回错误数据见 log.rs。五、轻量事务meta 文件即提交点幻灯片提出一个优雅的事务模型既然每个数据结构都是追加写的、都由meta掌控那么事务就只是不同的 meta 文件例如meta.tr{name}。这允许多个事务同时进行。这一思想在实现中得到体现OpenOptions::open的文档把Log实例类比为绑定到一个数据库事务——数据在 open 时快照并冻结写入被缓冲直至Log::sync相当于 commit丢弃Log实例相当于放弃事务见 open_options.rs。meta文件本身由LogMetadata描述包含主日志长度primary_len、各索引长度indexes、epoch 以及索引滞后时间戳整体用 xxhash 校验并原子写入见 meta.rs。epoch是检测非追加写变更的关键字段概念上类似创建时间截断/重建数据会生成新 epoch读者据此判断索引是否还能复用见 meta.rs 与 log.rs。六、维护与修复把 O(N) 留给修复损坏设计目标中除了修复损坏之外避免一切 O(N)意味着日常读、写、查询绝不做全量扫描但允许在修复损坏时进行全量操作。indexedlog为此提供两类修复接口见 repair.rsRepair修复给定路径下的存储结构OpenWithRepair::open_with_repair打开时若遇数据损坏自动 repair 一次后重新 open。它只修复由操作系统崩溃/硬重启造成的那类损坏并且为安全起见若存在其他正在读取的进程则跳过修复——因为无锁读依赖追加写性质而 repair 不是追加写可能让其他进程拿到静默错误的数据。Log::rebuild_indexes(force)则负责仅凭 Log 重建索引forcefalse时跳过通过校验和检查的索引forcetrue时无条件重建更费时但可缩小索引文件体积返回人类可读的修复报告见 log.rs。这与幻灯片索引可以从 Log 完整重建、无需网络访问的设计相互印证。在 Sapling 的 Python 侧eden/scm/sapling/commands/doctor.py的runglobalindexedlogdoctor会把 indexedlog corruptions (usually after hard reboot)通常是硬重启导致的 indexedlog 损坏列为检查项之一见 doctor.py。七、计划用途与实际落地幻灯片列出的计划用途Planned Use CasesFile Storage文件存储Changelog Nodemap 与 ChildmapObsstore 的多个索引Bookmark 索引Undo 索引。这些规划在今天的 Sapling 源码中已大量落地可以从源码结构逐一印证DAG 层eden/scm/lib/dag/src/dag/indexedlog_dag.rs定义了Dag AbstractDagIdDagIndexedLogStore, IdMap, IndexedLogDagPath, DagState即 iddag修订号 DAG、idmap哈希↔编号映射与 dag state 均以 indexedlog 为后端见 indexedlog_dag.rs。文件/历史存储File Storageeden/scm/lib/revisionstore/src/indexedlogdatastore.rs与indexedloghistorystore.rs分别是内容存储与历史存储的 IndexedLog 实现eden/scm/lib/revisionstore/src/indexedlogauxstore.rs是文件元数据aux存储。它们统一由 indexedlogutil.rs 的Store封装——Store抽象了永久IndexedLog或可轮转的RotateLog两种形态上层的IndexedLogHgIdDataStore、IndexedLogHgIdHistoryStore均基于它实现。Nodemap见eden/scm/lib/dag/src/iddagstore/indexedlog_store.rs等模块对索引化存储的封装。Python 命令行诊断sl debugindexedlogdatastore与sl debugindexedloghistorystore命令可分别打开并检查 IndexedLog 内容存储与历史存储见 remotefilelog/debugcommands.py。轮转Rotation让日志有界幻灯片要求无需维护但缓存类场景如远端文件内容的本地缓存需要控制体积。RotateLog正是为这一目的提供的上层组件写入总是进入活跃的 Log读取则扫描所有 Log单个 Log 超过max_bytes_per_log即被轮转到下一位置超出max_log_count的旧日志被删除无 LRU 语义见 rotate.rs。轮转配置暴露给用户例如eden/scm/sapling/helptext.py中记录的[indexedlog]配置段[indexedlog] data.max-bytes-per-log 10GB data.max-log-count 4 manifest.max-bytes-per-log 100MB manifest.max-log-count 4 aux.max-bytes-per-log 100MB aux.max-log-count 4该文档说明data/manifest/aux 每类缓存都存放在一组轮转的 indexedlog 文件中以避免无限增长max-log-count越大缓存读取的潜在工作量越大max-bytes-per-log越大缓存文件被删除时可能产生越大的远程访问尖峰[scmstore] auxindexedlog false可禁用 aux 缓存见 helptext.py。IndexedLogHgIdDataStoreConfig同样接收max_log_count/max_bytes_per_log/btrfs_compression等字段见 indexedlogdatastore.rs。八、小结Indexed Log 的设计可以用一句话概括以追加写保证低成本写入与无锁读以日志为真相源、索引为可重建缓存以校验和与原子 meta 保证强完整性以允许滞后并自动回填的索引消除维护负担。它把 Revlog 的 O(1) 修订号定位、Git Pack 的哈希定位优势与多索引原生支持、免 repack、可任意重建结合了起来成为 Sapling 在文件存储、DAG 与元数据索引层的公共底座。如果你希望继续深入建议从以下源码路径入手核心实现eden/scm/lib/indexedlog/src/log.rsLog 与 sync 流程、eden/scm/lib/indexedlog/src/index.rs基数树索引、eden/scm/lib/indexedlog/src/log/meta.rsmeta 格式上层落地eden/scm/lib/revisionstore/src/indexedlogutil.rs、eden/scm/lib/dag/src/dag/indexedlog_dag.rs诊断与运维eden/scm/sapling/ext/remotefilelog/debugcommands.py、eden/scm/sapling/commands/doctor.py。赞分享开发工具CLI后端【免费下载链接】saplingA Scalable, User-Friendly Source Control System.项目地址https://gitcode.com/gh_mirrors/sa/sapling点击查看免费下载相关推荐FastGPT Workflow 节点响应持久化改造Append-Only 存储与交互恢复 NodeResponse ID 设计解析FastGPT Workflow 节点响应持久化改造Append Only 存储与交互恢复 NodeResponse ID 设计解析 FastGPT 的 wo人工智能AI AgentRAG大模型工作流自动化后端前端Orama索引结构深度解析从倒排索引到向量索引的完整存储设计指南Orama索引结构深度解析从倒排索引到向量索引的完整存储设计指南 Orama是一个强大的开源搜索引擎支持全文搜索、向量搜索和混合搜索其独特的索引结构设计使向量数据库RAGElectric 1.1 新存储引擎深度解析从 CubDB 到自研 Shape Log 存储架构Electric 1.1 新存储引擎深度解析从 CubDB 到自研 Shape Log 存储架构本篇文章基于 Electric 官方 1.1 发布博客 ht后端数据同步数据库人工智能AI AgentMCP 服务上一篇PostgreSQL高可用集群插件管理Patroni扩展安装与升级终极指南下一篇mangos-v1性能优化指南提升消息吞吐量与降低延迟的10个最佳实践创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

Sapling 的 Indexed Log：一份从 Revlog 到 Append-Only 索引存储的设计解析

相关推荐

CouchDB 集群内部 RPC 机制深度解析：rexi 分布式调用框架的原理、源码与配置

PufferLib Bat 环境耳方向性（Ear Directivity）研究：从蝙蝠声学生物学到低成本 per-ear 增益模型的实现指南

12.【Linux系统编程】动静态库制作与使用

更多资讯

停车场管理系统课程设计：用栈、队列、链表一题通关

仿微信聊天系统源码解析：WinForm桌面端IM开发实战指南

阿里 Qoder 智能体工作台实战：用 TaoToken 统一 Key 打通 Harness 与 Agent 工作流

OpenClaw Talk 模式实战：TaoToken 统一 Key 打通 Voice Call 语音链路配置指南

工控数据类型与值范围详解：从PLC到Modbus的解析避坑指南

新电脑装机指南：从系统初始化到效率工具的科学配置思路

今日更新

PHP htmlentities()函数用法讲解

AI Agent工程实战：从七要素到七个决策点的系统设计指南

AI入局芯片设计验证：验证收敛50倍加速的真相与应对

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？