企业官网建设流程全解析

• 开发工具
• CLI
• 后端

导读

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 file：Git 的两类格式

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=存疑）：

除此之外：Obsstore 需要多索引；Changelog 需要多索引（nodemap、parent-child map）。这正是设计 Indexed Log 的直接动机。

二、Indexed Log 的设计目标与总体架构

2.1 设计目标

针对上述问题，幻灯片明确提出 Indexed Log 的目标：

• 摆脱对修订号的依赖（Decouple from revision numbers）；
• O(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 -> Vec<bytes>，即从 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），而叶子节点中保留各自的 value：

Insert 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.rs；
• scan_prefix(prefix)/scan_prefix_hex(hex_prefix)：按前缀（或十六进制前缀）扫描，见 index.rs；
• range(range)：按字节范围扫描，见 index.rs；
• remove/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_OFFSET=12） 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.rs：

• Xxhash64：64 位平台效率高；
• Xxhash32：体积更小，适合短 entry；
• Auto：按数据大小自动选择——实现中给出了 x64 平台的实测吞吐对比，并以88 字节为阈值：数据 ≥88 字节用 xxhash64，否则用 xxhash32，见 log.rs。

4.3 内存缓冲与显式 flush

Log::append只是在内存中追加 entry，并同步更新内存中的索引；其他进程（甚至同进程的其他Log实例）看不到该变更。只有调用Log::sync（旧名flush）才会把内存内容真正写盘，见 log.rs 与 log.rs。

OpenOptions提供一组与场景匹配的配置项，见 open_options.rs：

4.4 sync 的五步流程

Log::sync是唯一的写盘入口，设计上刻意保持简单以便验证正确性，见 log.rs：

1. 只读快速路径：若无内存脏数据，只重读 meta 判断磁盘是否变化；
2. 取目录锁（flock），重读 meta，校验"日志只能增长"（check_append_only）；
3. 追加主日志：从 meta 记录的primary_len处 seek 后写入内存缓冲，可选 fsync，然后清空内存缓冲；
4. 回填/刷新索引：update_indexes_for_on_disk_entries让索引追上日志，随后flush_lagging_indexes只落盘真正滞后超阈值的索引；
5. 原子写 meta：write_meta记录新的主日志长度与各索引逻辑长度。

若上一次写盘被中断（如系统崩溃），sync会从 meta 记录的长度处 seek 并覆盖残留的损坏字节——物理上这是覆盖写，但对所有读者而言log在 meta 长度范围内仍是追加写且不可变，因此无锁读的安全性不被动摇，见 log.rs。

4.5 读取 API

Log 暴露三类读取接口，均由索引或日志迭代器实现：

• lookup(index_id, key)：按索引精确查找，返回按插入逆序的 entry 迭代器，见 log.rs；
• lookup_prefix(index_id, prefix)/lookup_prefix_hex：按前缀/十六进制前缀查找，见 log.rs；
• lookup_range(index_id, range)：按字节范围查找，见 log.rs；
• iter()：顺序遍历全部 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.rs：

• Repair：修复给定路径下的存储结构；
• OpenWithRepair::open_with_repair：打开时若遇数据损坏，自动 repair 一次后重新 open。它只修复由操作系统崩溃/硬重启造成的那类损坏，并且为安全起见，若存在其他正在读取的进程则跳过修复——因为无锁读依赖追加写性质，而 repair 不是追加写，可能让其他进程拿到静默错误的数据。

Log::rebuild_indexes(force)则负责仅凭 Log 重建索引：force=false时跳过通过校验和检查的索引，force=true时无条件重建（更费时但可缩小索引文件体积），返回人类可读的修复报告，见 log.rs。这与幻灯片"索引可以从 Log 完整重建、无需网络访问"的设计相互印证。

在 Sapling 的 Python 侧，eden/scm/sapling/commands/doctor.py的runglobalindexedlogdoctor会把 "indexedlog corruptions (usually after hard reboot)"（通常是硬重启导致的 indexedlog 损坏）列为检查项之一，见 doctor.py。

七、计划用途与实际落地

幻灯片列出的计划用途（Planned Use Cases）：

• File Storage（文件存储）；
• Changelog Nodemap 与 Childmap；
• Obsstore 的多个索引；
• Bookmark 索引；
• Undo 索引。

这些规划在今天的 Sapling 源码中已大量落地，可以从源码结构逐一印证：

• DAG 层：eden/scm/lib/dag/src/dag/indexedlog_dag.rs定义了Dag = AbstractDag<IdDag<IndexedLogStore>, IdMap, IndexedLogDagPath, DagState>，即 iddag（修订号 DAG）、idmap（哈希↔编号映射）与 dag state 均以 indexedlog 为后端，见 indexedlog_dag.rs。
• 文件/历史存储（File Storage）：eden/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.rs（Log 与 sync 流程）、eden/scm/lib/indexedlog/src/index.rs（基数树索引）、eden/scm/lib/indexedlog/src/log/meta.rs（meta 格式）；
• 上层落地：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
• 后端