用 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)
三棵树 ───────┴─ 状态查询 = 两两比较四条最值得记住的判断:
- 哈希的输入必须包含类型和长度。 否则不同对象可能算出同一个地址,去重就会把两个不同的东西当成一个。
- 整个系统里唯一需要并发控制的,只有引用。 数据不可变带来的最大红利,不是省内存,而是让并发问题缩小到一个 40 字节的 CAS 上。
sync必须在rename之前。 顺序反了,断电后会得到一个"指向不存在对象"的引用——仓库直接损坏。- 不可达 ≠ 可以立刻删。 reflog、进行中的操作、并发读者都可能还在引用它。
这四条有一个共同的主题:内容寻址把"数据"这个维度上的所有问题都消灭了,于是剩下的问题全部集中在"引用"和"时机"上。 这也是这个系统最值得学习的地方——它不是靠更强的机制解决问题,而是靠改变数据的表示方式,让问题不再存在。
下一篇换到"期望状态和实际状态之间隔着什么"(集群调度器),那里没有一个"内容哈希"可以依赖,一切都要靠一个永不停止的循环去逼近。