返回文章列表

用 Rust 从零实现一个版本控制系统:内容寻址省掉了整个失效逻辑

1125 字·9 分钟阅读
Rust从零造轮子内容寻址

回顾前面几个系统,它们都在反复回答同一类问题:

时序库:  "这个段的时间范围过期了吗"
向量检索:"这个段需要合并了吗"
DNS:     "这个缓存条目还在 TTL 内吗"
IM:      "这条消息我是不是已经见过"
CRDT:    "这个墓碑可以回收了吗"

每一个都是"判断某份旧数据是否还有效"。 而现在这个系统,会给你一个完全不同的答案:让"失效"这个问题不存在。

它的做法非常朴素:用内容的哈希当身份。

第一步:三个对象,一个规则

版本控制系统的全部数据模型只有三个对象类型:

/// blob:一段文件内容。没有任何元数据,只有字节。
pub struct Blob {
    pub content: Vec<u8>,
}
 
/// tree:一个目录。名字 → 对象 id
pub struct Tree {
    pub entries: Vec<TreeEntry>,
}
 
pub struct TreeEntry {
    /// 文件或子目录的名字
    pub name: String,
    /// 模式:100644 普通文件 / 100755 可执行 / 40000 目录
    pub mode: u32,
    /// ★ 指向另一个对象的 id —— 这就是整棵树的链接
    pub id: ObjectId,
}
 
/// commit:一次提交。指向一棵 tree,加上父提交和历史信息
pub struct Commit {
    pub tree: ObjectId,
    pub parents: Vec<ObjectId>,
    pub author: String,
    pub message: String,
    pub timestamp: i64,
}

而唯一的规则是:

impl ObjectId {
    /// 对象 id = 对象内容的哈希
    /// 注意哈希的输入是"类型 + 长度 + 内容",不是只有内容
    pub fn compute(kind: ObjectKind, content: &[u8]) -> Self {
        let mut hasher = Sha1::new();
        hasher.update(kind.as_str().as_bytes());   // "blob" / "tree" / "commit"
        hasher.update(b" ");
        hasher.update(content.len().to_string().as_bytes());
        hasher.update(b"\0");
        hasher.update(content);
        ObjectId(hasher.finalize().into())
    }
}

为什么哈希的输入要包含"类型"和"长度"?

  • 类型:不加的话,一个内容恰好是合法 tree 编码的 blob,会算出和那个 tree 相同的 id——两个不同的对象得到同一个地址,整个系统的地址唯一性直接崩塌。
  • 长度:这是一个前缀攻击的防护。不加长度的话,("a", "bc") 和 ("ab", "c") 会拼成同样的哈希输入。

这两条都不是"防御性编程",而是"地址必须唯一"这个前提的一部分。 一旦地址可以不唯一,去重就会把两个不同的对象当成一个。

第二步:内容寻址免费给你的五件事

换掉"用名字定位数据"这个习惯之后,有五件事不再需要实现:

能力 命名寻址(需要额外机制) 内容寻址(天然获得)
去重 需要内容指纹 + 索引 相同内容 = 相同 id,天然一份
不可变 需要约定"不修改" id 就是内容,改了就不是原来的 id
完整性校验 需要额外校验和字段 重新算一次哈希即可
缓存失效 需要 ETag / mtime / version key 就是内容,不存在失效
幂等写入 需要去重判断 写两次 = 写一次

最值得展开的是第四项,因为它是整个系列里前面几个系统的核心痛点。

命名寻址的世界(比如按路径存缓存):
  /api/users/42 的响应可能变了 —— 我怎么知道?
    ① 靠 mtime:但 mtime 会误报(文件被 touch 但内容没变)
    ② 靠 ETag:但 ETag 本身是需要维护的元数据
    ③ 靠 TTL:过期了重新拉,但可能拉到同样的内容
  → 三种方式都不精确,都需要"额外的状态"来表达"变没变"
 
内容寻址的世界:
  对象的身份就是它的内容哈希
  → "变了吗" = "id 一样吗",一次比较,不需要任何元数据

这个差别可以概括成一句话:

命名寻址把"数据是否变化"变成了一个需要被维护的元数据;内容寻址把它变回一个可以随时重算的值。

"需要维护的元数据"永远会有 bug——因为它和内容之间存在一个"必须保持同步"的隐含约定(缓存的 ETag 必须和文件内容一致),而这个约定只要有一次没被遵守,缓存就会返回错误的数据。而"可以重算的值"没有这个问题——它要么对,要么当场就能发现不对。

内容寻址的代价也必须说清楚

代价 具体表现
必须能负担重算哈希 一个大文件每次读都要校验,成本不低(所以实践中可以跳过)
无法"原地修改" 改一个字节 = 一个新对象,旧对象还得留着(否则历史就断了)
需要 GC 旧对象堆积,必须有人判断哪些可以删
需要额外的"名字"层 人不能记住哈希,所以必须有 ref(分支名)、tag、路径这些"可读的别名"

第四条是最容易被忽略的:内容寻址必须配一套"命名系统"来给人用。

/// ref:人的名字 → 对象 id 的映射
pub struct Ref {
    pub name: String,     // "refs/heads/main"
    pub target: ObjectId, // 指向一个 commit
}

而一旦引入了 ref,就引入了这个系统里唯一可变、唯一需要并发控制的东西。 后面第六步会看到:整套系统里所有关于"原子性"和"锁"的内容,都是围绕 ref 展开的。

内容寻址把数据本身变得完全不可变,于是所有并发问题都被压缩到了"那一小撮可变的引用"上。 这是一个非常划算的交易:用一个 40 字节的 CAS 操作,换来了几百 GB 数据的无锁读取。

第三步:Merkle Tree——让"比较两棵树"从 O(内容) 变成 O(变化)

这里必须停下来讲清楚一件事:为什么 tree 对象存的是"子对象的 id",而不是子对象本身。

tree(根)  id = hash(它自己的内容)
  ├─ "src"      → tree id = hash(...)  ← 子树的哈希
  │                 ├─ "main.rs" → blob id = hash(内容)
  │                 └─ "lib.rs"  → blob id = hash(内容)
  └─ "README.md" → blob id = hash(内容)

因为 tree 的内容里包含了子对象的哈希,所以"根 tree 的哈希"间接覆盖了整棵树的全部内容。 这就是 Merkle Tree。

它带来的直接好处是"比较两棵树"的成本被大幅降低:

/// 比较两棵 tree,返回差异
pub fn diff_trees(
    store: &ObjectStore,
    a: Option<&ObjectId>,
    b: Option<&ObjectId>,
    path: &mut Vec<String>,
    out: &mut Vec<DiffEntry>,
) -> Result<()> {
    // ★ 第一步:如果两个 id 相同,整棵子树完全相同 —— 立即返回
    if a == b {
        return Ok(());
    }
 
    // 一个是"不存在"(新增或删除)
    match (a, b) {
        (None, Some(id)) => return collect_all_as_added(store, id, path, out),
        (Some(id), None) => return collect_all_as_removed(store, id, path, out),
        (Some(_), Some(_)) => {}
    }
 
    let tree_a = store.read_tree(a.unwrap())?;
    let tree_b = store.read_tree(b.unwrap())?;
 
    // 第二步:按名字收集两侧的条目
    let map_a: HashMap<&str, &TreeEntry> = tree_a.entries.iter()
        .map(|e| (e.name.as_str(), e)).collect();
    let map_b: HashMap<&str, &TreeEntry> = tree_b.entries.iter()
        .map(|e| (e.name.as_str(), e)).collect();
 
    // 第三步:只对"id 不同"的条目递归 —— 这是剪枝的关键
    for (name, eb) in &map_b {
        path.push((*name).to_string());
 
        match map_a.get(*name) {
            Some(ea) if ea.id == eb.id => {
                // 名字相同、id 相同 → 整个子树没变,不递归
            }
            Some(ea) => {
                // id 不同 → 要么是同一个子目录继续往下走,要么是文件内容变了
                if eb.mode == MODE_DIR && ea.mode == MODE_DIR {
                    diff_trees(store, Some(&ea.id), Some(&eb.id), path, out)?;
                } else {
                    out.push(DiffEntry::Modified { path: path.clone() });
                }
            }
            None => out.push(DiffEntry::Added { path: path.clone() }),
        }
 
        path.pop();
    }
 
    Ok(())
}

复杂度是怎么降下来的:

场景 朴素做法 Merkle Tree
两棵树完全相同 O(条目总数) O(1)(根 id 相等)
只改了一个文件 O(条目总数) O(树的深度)(只在变化的那条路上递归)
完全不同的两棵树 O(条目总数) O(条目总数)(无法避免)

"根 id 相等就整棵树相同"这一条,是最有价值的那一行代码。 它把一个 O(n) 的问题在绝大多数情况下变成了 O(1)——因为在实际使用中,"两次比较的大部分内容是相同的"才是常态。

而这也是分布式系统里用 Merkle Tree 做数据同步的原因:

两个节点各有一份数据,想知道它们是否一致:
  ① 先比根哈希 → 相同就结束(大多数情况)
  ② 不同 → 递归比较子节点,直到定位到不同的那一小块
  ③ 只同步不同的那一小块
 
总传输量 ≈ 变化的数据量,而不是全量

Merkle Tree 的价值不在于"更快地比较",而在于"让比较的成本正比于差异的大小"。 这个性质在任何"两份大体相同的数据需要对齐"的场景里都能用上——文件同步、区块链、反熵协议、以及这里的版本控制,都是同一个结构。

第四步:对象的存储——为什么不能一个对象一个文件

最直观的存储方式是"一个对象一个文件":

.git/objects/
  ab/cdef1234567890...      ← 一个 blob
  cd/ef1234567890ab...      ← 一个 tree
  ...

文件名的前两个字符当目录,是为了避免单个目录里放几百万个文件(有些文件系统在目录条目数很大时查找会明显变慢)。

但这个方案在规模上会崩:

问题 表现
inode 消耗 一个十万文件的项目,每次提交都产生几万个新对象
空间浪费 每个文件至少占一个块(通常 4KB),而对象平均可能只有几百字节
元数据放大 每个文件的 inode、目录项、权限都是一份额外开销
读取慢 打开一个文件要查目录、读 inode、再读数据——三次磁盘寻址

所以需要 packfile:把很多对象塞进一个大文件,再加一个索引。

pub struct PackFile {
    /// 整个 pack 文件的内存映射 —— 不全部读进内存
    mmap: Mmap,
    /// 索引:对象 id → 它在文件里的位置和长度
    index: PackIndex,
}
 
pub struct PackIndex {
    /// 排序后的对象 id 数组,用于二分查找
    ids: Vec<ObjectId>,
    /// 和 ids 平行:每个对象的数据在 pack 里的偏移量
    offsets: Vec<u64>,
}
 
impl PackFile {
    /// 读一个对象:O(log n) 定位 + 一次顺序读
    pub fn read(&self, id: &ObjectId) -> Result<Vec<u8>> {
        // ① 二分查找定位(ids 是排好序的)
        let idx = self.index.ids
            .binary_search(id)
            .map_err(|_| Error::ObjectNotFound(*id))?;
 
        let offset = self.index.offsets[idx];
 
        // ② 从 mmap 里读 —— 注意这是"按需分页"
        //    只读需要的字节,操作系统负责把页从磁盘带进来
        let raw = &self.mmap[offset as usize..];
 
        // ③ 解码:可能是压缩对象,也可能是 delta
        self.decode_at(raw, self.index.ids[idx])
    }
}

mmap 在这个场景里是关键的一步:读一个对象不需要"打开文件 + seek + read"三次系统调用,而是一次内存访问触发缺页——操作系统会按页把数据带进来,而且同一个 pack 里相邻的对象往往会被一起带进来(因为顺序访问有局部性)。

这就是"用一次映射换掉每次打开文件的开销"——和前面讲零拷贝时是同一个思路,只是这里的"零拷贝"发生在"读对象"这个动作上。

为什么还需要 zlib,又需要 delta

这是两种不同维度的压缩,经常被混为一谈:

zlib(每个对象内部):
  压缩的是"同一个对象内部的冗余"
  比如一个文本文件里的重复单词、JSON 里的重复 key
 
delta(对象之间):
  压缩的是"同一份内容在不同版本之间的冗余"
  比如 v1 和 v2 只差三行,但两行都要存的话就浪费了
pub enum PackEntry {
    /// 完整对象(可能内部是 zlib 压缩的)
    Full { kind: ObjectKind, compressed: Vec<u8> },
    /// delta 对象:由"基准对象 + 一段指令"重建
    Delta {
        /// 相对哪个对象的 delta(用偏移量表示,不是 id)
        base_offset: u64,
        /// 重建指令
        instructions: DeltaInstructions,
    },
}
 
pub enum DeltaOp {
    /// 从基准对象里复制一段:(偏移量, 长度)
    Copy { offset: u64, len: u64 },
    /// 插入新数据
    Insert(Vec<u8>),
}

重建一个 delta 对象的代码:

impl PackFile {
    fn reconstruct(&self, mut offset: u64) -> Result<(ObjectKind, Vec<u8>)> {
        // 收集 delta 链:从当前对象一路往回找基准
        let mut chain = Vec::new();
 
        loop {
            let entry = self.entry_at(offset)?;
            match entry {
                PackEntry::Full { kind, compressed } => {
                    // 链的底部:解压得到基准对象
                    let mut data = zlib_decompress(&compressed)?;
                    // 从底部往上依次应用 delta
                    for (base_offset, delta) in chain.into_iter().rev() {
                        let _ = base_offset;
                        data = apply_delta(&data, &delta)?;
                    }
                    return Ok((kind, data));
                }
                PackEntry::Delta { base_offset, instructions } => {
                    chain.push((base_offset, instructions));
                    offset = base_offset;   // 继续往上找
                }
            }
        }
    }
}
 
/// 应用一段 delta:复制 + 插入
fn apply_delta(base: &[u8], delta: &DeltaInstructions) -> Result<Vec<u8>> {
    let mut out = Vec::with_capacity(base.len());
 
    for op in &delta.ops {
        match op {
            DeltaOp::Copy { offset, len } => {
                let start = *offset as usize;
                let end = start + *len as usize;
                // 边界检查不能省:delta 是外部输入
                if end > base.len() {
                    return Err(Error::DeltaOutOfBounds);
                }
                out.extend_from_slice(&base[start..end]);
            }
            DeltaOp::Insert(bytes) => out.extend_from_slice(bytes),
        }
    }
 
    Ok(out)
}

注意 Copy 是"从基准对象里复制一段"——这正是"移动指针而不是移动数据"的又一次出现。 一个只改了三行的文件,它的 delta 大概是"复制前 500 字节 + 插入 30 字节 + 复制后 800 字节",总共几十字节。

但 delta 有一个必须被限制的性质:链长。

v1 ← v2 ← v3 ← v4 ← ... ← v100
 
读 v100 需要:
  重建 v99 → 重建 v98 → ... → 重建 v1
  = 100 次 delta 应用

链越长,读一个对象要解压的数据越多。 所以真实的实现会限制 delta 链的深度(常见值 50 左右),超过就存一个完整对象来"打断"链条。

delta 深度 存储空间 读取成本
无 delta(全存完整对象) 大 低(一次解压)
浅链(深度 ≤ 10) 中 中
深链(深度 ≤ 50) 小 高(最多 50 次应用)

这是一个和"B 树的高度"完全同构的取舍: 链更深 = 空间更省、读取更慢。而打断链条的那个完整对象,就相当于 B 树的一个节点——它把"一路走到底"变成"走几层就到"。

"压缩"和"索引"在存储系统里是同一个天平的两端。 压缩得越狠,重建的步骤越多;索引得越细,占用的空间越多。而所有成熟的实现最终都会收敛到"分层的、带深度上限的结构"——因为无上限的优化总会在某个规模上变成灾难。

第五步:引用更新——整个系统里唯一需要并发控制的地方

前面说过:内容寻址让所有数据都不可变,于是整个系统里可变的东西只剩下一小撮引用。

不可变的(无锁读取,随便并发):
  blob / tree / commit 对象
  packfile
 
可变的(必须原子更新):
  refs/heads/main       ← 分支指针
  refs/tags/v1.0        ← 标签
  HEAD                  ← 当前分支

所以整个版本控制系统的并发设计可以浓缩成一句话:怎么原子地更新一个 40 字节的引用。

引用更新的实现:CAS + 文件系统原子操作

pub struct RefStore {
    root: PathBuf,   // 通常是 .git/refs 或 .git
}
 
impl RefStore {
    /// ★ 比较并交换:只有当当前值等于 expected 时才更新
    pub fn compare_and_swap(
        &self,
        name: &str,
        expected: Option<&ObjectId>,   // 期望的旧值(None 表示"必须不存在")
        new: &ObjectId,
    ) -> Result<()> {
        let path = self.path_of(name);
        let lock_path = path.with_extension("lock");
 
        // ① 创建锁文件 —— 这是互斥的实现方式
        //    用 O_CREAT|O_EXCL 保证"只有一个人能创建成功"
        let mut lock = OpenOptions::new()
            .write(true)
            .create_new(true)     // ★ 原子:已存在就失败
            .open(&lock_path)
            .map_err(|e| if e.kind() == ErrorKind::AlreadyExists {
                Error::RefLocked(name.to_string())
            } else {
                e.into()
            })?;
 
        // ② 读当前值,和 expected 比较
        let current = self.read_raw(&path)?;
        if current.as_ref() != expected {
            // 值变了 —— 拒绝这次更新
            // 注意:锁文件必须删掉,否则引用会永久锁死
            drop(lock);
            let _ = fs::remove_file(&lock_path);
            return Err(Error::RefConflict {
                name: name.to_string(),
                expected: expected.copied(),
                actual: current,
            });
        }
 
        // ③ 写入新值到锁文件
        lock.write_all(format!("{}\n", new).as_bytes())?;
        lock.sync_all()?;   // 落盘,防止断电后引用指向不存在的对象
        drop(lock);
 
        // ④ 原子 rename —— 这是唯一一步"要么全做要么全不做"的操作
        fs::rename(&lock_path, &path)?;
 
        Ok(())
    }
}

四步里有三个关键点:

点一:create_new(true) 就是"锁"。 它依赖文件系统的 O_CREAT|O_EXCL 语义是原子的——这是一个几乎所有本地文件系统都保证的性质,也是整个方案不需要额外依赖的原因。

点二:失败时必须删除锁文件。 这段代码里 drop(lock); remove_file() 的顺序是有意的——Windows 上文件被打开时不能删,所以要先关再删。 而如果这里漏了,那个引用会被永久锁定,所有后续操作都失败,且报错信息是"锁被占用"——而占用它的进程早就死了。

点三:sync_all() 之后才 rename。 如果先把新值 rename 上去再 sync,那么断电之后会出现"引用已经指向新对象,但对象本身还在页缓存里没落盘"。结果是引用指向一个不存在的对象——仓库彻底损坏。

这就是"先保证数据可持久,再保证引用可见"的顺序,和前面 WAL 那篇的道理完全一致。

push 是一个"检查 + 更新"的复合操作

单机的 CAS 还不够,因为一次 push 要同时做几件事:

impl Remote {
    pub fn push(&self, branch: &str, new_head: &ObjectId, expected_old: Option<&ObjectId>) -> Result<()> {
        // ① 先校验:new_head 的祖先里能不能找到 expected_old
        //    这就是"快进检查"——不能快进说明有别人的提交,需要先合
        if let Some(old) = expected_old {
            if !self.is_ancestor(old, new_head)? {
                return Err(Error::NonFastForward);
            }
        }
 
        // ② 再更新引用:用 CAS,期望值就是客户端看到的那个旧值
        //    ★ 关键:这里必须再检查一次!
        //    "① 检查通过"和"② 更新成功"之间,别人可能推了新的提交
        //    所以 ② 的 expected 必须还是 ① 里用的那个值
        self.refs.compare_and_swap(&format!("refs/heads/{branch}"), expected_old, new_head)
    }
}

注意 ① 和 ② 之间那个窗口:

时间轴:
  T1  A 检查:new_head 的祖先是 expected_old ✓
  T2  B 推了一个提交,把 main 从 expected_old 推进到 X
  T3  A 更新引用:如果无条件写 → 把 B 的提交覆盖掉(B 的工作丢失)
 
  用 CAS:A 的 expected 是 expected_old,但当前值是 X
       → CAS 失败 → A 被要求先合再推

"检查"和"提交"必须用同一个期望值串起来,否则检查就白做了。 这是乐观并发控制的标准形态——和集群调度器里那套 resourceVersion 是同一个模式,也和所有"用版本号做 CAS"的地方一样。

乐观并发控制成立的条件是"冲突能被检测到",而不是"冲突不会发生"。 所以它的正确性完全依赖于"检查用的那个版本号和提交时比对的那个是同一个"——中间任何一次"重新读取最新值"都会让检查失效。

第六步:GC——可达性分析,和内存 GC 一模一样

对象只会增加,不会减少。 所以必须有人判断"哪些对象可以删"。

pub struct Gc {
    store: PackedObjectStore,
}
 
impl Gc {
    /// 标记阶段:从所有 ref 出发,找出可达的对象
    pub fn mark(&self) -> Result<HashSet<ObjectId>> {
        let mut reachable = HashSet::new();
        let mut stack: Vec<ObjectId> = Vec::new();
 
        // ① 所有 ref 是根集合(roots)
        for r in self.all_refs()? {
            stack.push(r.target);
        }
        // ② reflog 也是根!(见下面)
        for r in self.all_reflog_entries()? {
            stack.push(r.target);
        }
        // ③ 索引(staging area)也是根
        if let Some(tree) = self.index_tree()? {
            stack.push(tree);
        }
 
        // ④ 标准 DFS 标记
        while let Some(id) = stack.pop() {
            if !reachable.insert(id) {
                continue;   // 已经标记过,剪枝
            }
 
            // 展开这个对象指向的所有子对象
            match self.store.read_object(id)? {
                Object::Commit(c) => {
                    stack.push(c.tree);
                    for p in c.parents {
                        stack.push(p);
                    }
                }
                Object::Tree(t) => {
                    for e in t.entries {
                        stack.push(e.id);
                    }
                }
                Object::Blob(_) => {}   // 叶子,没有子对象
            }
        }
 
        Ok(reachable)
    }
 
    /// 清除阶段:不可达的删除
    pub fn sweep(&self, reachable: &HashSet<ObjectId>, grace: Duration) -> Result<usize> {
        let mut removed = 0;
 
        for obj in self.store.all_objects()? {
            if reachable.contains(&obj.id) {
                continue;
            }
 
            // ★ 宽限期:不能立刻删
            if obj.mtime.elapsed() < grace {
                continue;
            }
 
            self.store.remove(obj.id)?;
            removed += 1;
        }
 
        Ok(removed)
    }
}

这段代码和内存 GC 的 mark-sweep 完全同构。 而它有两个容易被忽略的地方:

地方一:根集合比"refs"要大。

谁是根?
  ✓ refs(分支、标签)
  ✓ HEAD
  ✓ reflog(引用变更的历史!)
  ✓ 索引(暂存区,可能包含还没提交的对象)
  ✓ 正在进行中的操作(merge / rebase 的临时状态)

reflog 是最容易漏的一个。 它的语义是"这个引用的历史位置",所以一个"刚从分支上被撤掉、但 reflog 还记得"的提交,仍然是可达的。 这正是"改错了还能找回来"的实现基础——如果 GC 只看当前 refs,那么任何一次 reset 都会立刻让旧提交被回收,撤销就成了不可能。

地方二:宽限期(grace period)。

为什么不能立刻删不可达对象?
  ① 另一个进程正在读它(比如一个并发的 fetch 已经开始,但还没读完)
  ② 一个正在进行的 merge 可能已经算好了目标 tree,但还没更新 ref
  ③ 用户刚做完的操作,可能马上要撤销
 
宽限期的选择:
  太短 → 上面三种情况都会变成"文件缺失"错误
  太长 → 磁盘空间回收不及时
  常见做法:默认不自动 GC,让用户显式触发;或者宽限期 2 周

"不可达"和"可以删除"是两个不同的判断,中间隔着一个时间窗。 这个模式在这个系列里已经出现过好几次:DNS 缓存过期后的宽限、LSM 的墓碑、CRDT 的墓碑回收。原因总是一样的:有别的并发活动可能还在引用这份数据,而它不在这份"当前状态"里。

第七步:工作区、索引、HEAD——"三棵树"的比较

到这里,数据模型还剩一块没讲:用户的工作区怎么和这套对象模型对接。

工作区(working tree)    ← 用户实际在编辑的文件,随时会变
      ↓ 阶段(stage)
索引(index / staging)    ← 一个"待提交的快照",也是内容寻址的
      ↓ 提交(commit)
HEAD                      ← 最后一次提交的 tree

"查看状态"其实就是比较这三棵树:

比较 结果 含义
工作区 vs 索引 有差异 改动了但还没 stage
索引 vs HEAD 有差异 已经 stage 了,还没提交
工作区 vs HEAD 有差异 总共有未提交的改动
pub struct Index {
    /// 路径 → (blob id, 元数据)
    entries: BTreeMap<String, IndexEntry>,
}
 
pub struct IndexEntry {
    pub path: String,
    /// ★ 指向一个 blob 对象 —— 索引里存的是"内容的地址",不是内容
    pub id: ObjectId,
    pub mode: u32,
    pub mtime: i64,
    pub size: u64,
}
 
impl Index {
    /// 判断一个工作区文件是否需要重新哈希
    pub fn needs_refresh(&self, path: &str, meta: &FileMeta) -> bool {
        match self.entries.get(path) {
            None => true,   // 索引里没有 → 新文件
            Some(e) => {
                // ★ 快速判断:先用 (mtime, size) 筛
                //    只有它们变了,才真的去重算哈希
                e.mtime != meta.mtime || e.size != meta.size
            }
        }
    }
}

needs_refresh 这个"先用 mtime/size 筛,再算哈希"的两级判断,是一个纯粹的性能优化,也是一个经典的取舍:

策略 成本 风险
每次都比对内容哈希 读所有文件(大仓库几 GB) 无
先比 mtime + size,可疑才算哈希 只读 stat 极小概率漏判(内容变了但 mtime 和 size 恰好没变)

漏判的场景是真实存在的——比如把文件改成同样的长度、然后又手动把 mtime 改回去(有些构建工具会做这种事)。所以索引里必须能强制要求"重新比对内容",而这个开关的存在,正说明这个优化是有代价的。

但索引真正的设计价值不在性能,在于它让"提交"变成了一个 O(1) 的动作。

没有索引的话:
  commit 的动作 = 扫描整个工作区 → 生成所有 blob → 生成 tree → 生成 commit
  问题:扫描过程中工作区可能被改动 → 提交的是一份"撕裂"的视图
        而且每次提交都要重新算所有文件的哈希(即使只有 1 个文件改了)
 
有索引的话:
  commit 的动作 = 把索引里已经准备好的 tree 写成一个 commit 对象
  索引是一份"冻结的视图" —— 它在你 stage 的那一刻就固定了

这就是"把易变的东西变成一个不可变快照,然后对快照操作"的又一次出现。 而且它一举解决两个问题:性能(不用重算)+ 一致性(不会被并发修改干扰)。

"先冻结,再操作"是一个几乎万能的模式。 数据库的 MVCC 快照、流处理的 checkpoint barrier、这里的分支提交——它们都在做同一件事:把"操作的对象"从"一个会变化的状态"变成"一个不变的快照"。 而一旦这么做了,"并发修改"这个维度就从问题里消失了。

第八步:一次完整提交的路径

把前面所有部件串起来:

用户执行:  add src/main.rs  →  commit -m "修个 bug"
 
① add:读 src/main.rs 的内容
       → 算 hash → 得到一个 blob id
       → 把 (路径, blob id) 写进索引
 
② add 的落盘:blob 写进 .git/objects(或稍后打包)
       → 索引文件也持久化(下次会话能看到 staged 状态)
 
③ commit:从索引生成 tree 对象(目录 → 子目录递归)
       → 每个 tree 的 id 都是它内容的哈希
       → 得到一个根 tree id
 
④ commit 对象:{ tree: 根tree id, parents: [HEAD], message, ... }
       → 算出 commit id
 
⑤ 更新 ref:CAS 把 refs/heads/main 从旧 commit 改成新 commit
       → 期望值就是"③ 之前读到的 HEAD"
       → 如果这期间别人更新了引用,CAS 失败,重新来

这条路里值得单独说的是 ③ 的"生成 tree"。 它有一个不显然的细节:

impl Index {
    /// 把扁平的索引(一串路径)重建成树形的 tree 对象
    pub fn write_tree(&self, store: &mut ObjectStore) -> Result<ObjectId> {
        // 索引是"路径 → id"的扁平结构,但 tree 是嵌套的
        // 所以要按目录分组,从叶子往上构建
        let mut builder = TreeBuilder::new();
 
        for (path, entry) in &self.entries {
            // "src/lib/parser.rs" 要拆成 [src, lib, parser.rs]
            let parts: Vec<&str> = path.split('/').collect();
            // ★ 从叶子往根走,每一层目录都变成一个 tree 对象
            builder.insert(&parts, entry.id, entry.mode);
        }
 
        // 递归写出来:最深的目录先写,因为父 tree 需要子 tree 的 id
        builder.write_recursive(store)
    }
}

注意"从深处往浅处写"这个顺序:因为一个 tree 的内容里包含子对象的 id,所以子 tree 必须先被算出 id 并写入对象库。

这个"依赖关系决定执行顺序"的模式,在流处理那篇也出现过(barrier 必须对齐)、在 CRDT 那篇也出现过(因果依赖要等)。 这里它体现为"目录树的写入顺序"——只要数据模型里有"整体依赖部分"的结构,就一定有这个顺序约束。

整个系统的一致性边界

顺便说清楚一件事:这套系统的一致性保证到哪为止。

本地仓库:
  引用更新是原子的(CAS + 原子 rename)
  但"多个引用同时更新"不是原子的(比如同时更新两个分支)
 
远端仓库:
  单次 push 是原子的(一个引用的 CAS)
  但"推送多个分支"不是原子的 —— 可能第一个成功第二个失败
 
对象写入:
  每个对象写进去就是完整的(内容寻址 + 原子 rename)
  不存在"半个对象"的状态

"每个对象独立原子、整体操作不原子"这个性质,带来一个重要的实践结论:

一次失败的 push 不会损坏仓库,但会留下已经上传的对象。 那些对象成了不可达垃圾,等 GC 回收。而这个"宽松的一致性"是可以接受的——因为对象是内容寻址的,重复上传同一个对象不会产生冲突(幂等),所以在推失败之后直接重试就行。

一个宽松的一致性模型能不能接受,取决于"重试是否安全"。 这里安全的原因是内容寻址带来的幂等性——而这又回到了这篇文章开头那句话:把数据变成不可变的,很多问题就自己消失了。

结论

这个系统的形状是:

              ┌─ 三个对象:blob / tree / commit
数据模型 ──────┴─ 一个规则:id = hash(类型 + 长度 + 内容)
                  (类型和长度必须入哈希,否则地址不唯一)
 
              ┌─ 去重、不可变、可校验、无失效、幂等写入
免费得到的五件事┴─ 最值钱的是"无失效"
 
              ┌─ 根 id 相同 → O(1) 判定整棵树相同
Merkle Tree ──┴─ 不同 → 只在变化的那条路径上递归
 
              ┌─ 松散对象 → packfile(mmap 读 + 索引二分)
存储的演化 ────┴─ zlib(对象内)+ delta(对象间),delta 链有深度上限
 
              ┌─ 引用更新:CAS + 原子 rename(系统里唯一可变的地方)
唯一需要并发控制 └─ push = 检查 + CAS,两处必须用同一个期望值
 
              ┌─ 根集合:refs + reflog + 索引 + 进行中的操作
GC ──────────┴─ 宽限期:不可达 ≠ 可以立刻删
 
              ┌─ 索引是"冻结的视图":让 commit 变成 O(1)
三棵树 ───────┴─ 状态查询 = 两两比较

四条最值得记住的判断:

  1. 哈希的输入必须包含类型和长度。 否则不同对象可能算出同一个地址,去重就会把两个不同的东西当成一个。
  2. 整个系统里唯一需要并发控制的,只有引用。 数据不可变带来的最大红利,不是省内存,而是让并发问题缩小到一个 40 字节的 CAS 上。
  3. sync 必须在 rename 之前。 顺序反了,断电后会得到一个"指向不存在对象"的引用——仓库直接损坏。
  4. 不可达 ≠ 可以立刻删。 reflog、进行中的操作、并发读者都可能还在引用它。

这四条有一个共同的主题:内容寻址把"数据"这个维度上的所有问题都消灭了,于是剩下的问题全部集中在"引用"和"时机"上。 这也是这个系统最值得学习的地方——它不是靠更强的机制解决问题,而是靠改变数据的表示方式,让问题不再存在。

下一篇换到"期望状态和实际状态之间隔着什么"(集群调度器),那里没有一个"内容哈希"可以依赖,一切都要靠一个永不停止的循环去逼近。