阿男聊技术

CR3、HEAD 与 Catalog：分页、Git、Iceberg 共用的「可变指针 + 不可变树」

最近在对照 Linux 分页、Git 对象模型和 Iceberg 表格式，发现它们在解同一道题：底层存储块一旦写下就不改，逻辑状态却要持续变。答案都是「一枚可变指针 + 一棵不可变树」。在这里把三套源码并排看一下。

一、当前状态只是一枚指针

共通做法是：数据本身不可变，真正会改的只有「现在指向谁」。切换可见状态，就是改这枚指针。

Linux：CR3 指向页表根

x86-64 上，CR3 存的是当前地址空间顶层页表（PGD）的物理地址，外加 PCID 等控制位。切到另一个进程的 mm_struct 时，内核把新的 next->pgd 装进 CR3：

// arch/x86/mm/tlb.c:565-582
static void load_new_mm_cr3(pgd_t *pgdir, u16 new_asid, unsigned long lam,
			    bool need_flush)
{
	unsigned long new_mm_cr3;

	if (need_flush) {
		invalidate_user_asid(new_asid);
		new_mm_cr3 = build_cr3(pgdir, new_asid, lam);
	} else {
		new_mm_cr3 = build_cr3_noflush(pgdir, new_asid, lam);
	}

	/*
	 * Caution: many callers of this function expect
	 * that load_cr3() is serializing and orders TLB
	 * fills with respect to the mm_cpumask writes.
	 */
	write_cr3(new_mm_cr3);
}

参见 arch/x86/mm/tlb.c。switch_mm_irqs_off() 在真正换 mm 时走到这里¹：

// arch/x86/mm/tlb.c:947-956
	if (ns.need_flush) {
		VM_WARN_ON_ONCE(is_global_asid(ns.asid));
		this_cpu_write(cpu_tlbstate.ctxs[ns.asid].ctx_id, next->context.ctx_id);
		this_cpu_write(cpu_tlbstate.ctxs[ns.asid].tlb_gen, next_tlb_gen);
		load_new_mm_cr3(next->pgd, ns.asid, new_lam, true);

可以看到，进程切换并不搬页表，也不拷物理页。它改的是 CPU 手里那枚「当前页表根」指针。write_cr3 还是一条串行化指令，后面的 TLB 填充会按新根走。

Git：HEAD 先指分支，分支再指 commit

.git/HEAD 通常不是 commit hash，而是一条符号引用，例如 ref: refs/heads/main。真正存 hash 的是分支文件。detach 时 HEAD 才直接写 object id。git commit 先写出新的 commit 对象，再把当前分支指针推过去：

// builtin/commit.c:1938-1946
	if (commit_tree_extended(sb.buf, sb.len, &the_repository->index->cache_tree->oid,
				 parents, &oid, author_ident.buf, NULL,
				 sign_commit, extra)) {
		rollback_index_files();
		die(_("failed to write commit object"));
	}

	if (update_head_with_reflog(current_head, &oid, reflog_msg, &sb,
				    &err)) {

参见 builtin/commit.c。update-ref 的手册把这件事说得很干净：给定新旧 oid，验证旧值后再写入新值²。files backend 先把 hex oid 写进 lockfile，再 rename 成正式 ref：

// refs/files-backend.c:2059-2077
static enum ref_transaction_error write_ref_to_lockfile(struct files_ref_store *refs,
							struct ref_lock *lock,
							const struct object_id *oid,
							struct strbuf *err)
{
	static char term = '\n';
	int fd;

	fd = get_lock_file_fd(&lock->lk);
	if (write_in_full(fd, oid_to_hex(oid), refs->base.repo->hash_algo->hexsz) < 0 ||
	    write_in_full(fd, &term, 1) < 0 ||
	    fsync_component(FSYNC_COMPONENT_REFERENCE, get_lock_file_fd(&lock->lk)) < 0 ||
	    close_ref_gently(lock) < 0) {

// refs/files-backend.c:1864-1892
static int commit_ref(struct ref_lock *lock)
{
	char *path = get_locked_file_path(&lock->lk);
	...
	if (commit_lock_file(&lock->lk))
		return -1;
	return 0;
}

如上所示，读者看见的「当前分支」，始终是那枚 ref 指针；对象库里的 commit/tree/blob 写完就不会改。

Iceberg：Catalog 存 metadata 路径

Iceberg 规范把表状态放在 metadata 文件里，每次变更都写一份新文件，再用原子交换替换旧指针³：

All changes to table state create a new metadata file and replace the old metadata with an atomic swap.

指针落在哪，取决于 Catalog 实现。

Hadoop 路径表没有外部 metastore。原子提交是把临时 metadata rename 成下一版本号文件（vN.metadata.json）。源码把这句话写在注释里：

// core/src/main/java/org/apache/iceberg/hadoop/HadoopTableOperations.java:157-167
    int nextVersion = (current.first() != null ? current.first() : 0) + 1;
    Path finalMetadataFile = metadataFilePath(nextVersion, codec);
    FileSystem fs = getFileSystem(tempMetadataFile, conf);

    // this rename operation is the atomic commit operation
    renameToFinal(fs, tempMetadataFile, finalMetadataFile, nextVersion);

    LOG.info("Committed a new metadata file {}", finalMetadataFile);

    // update the best-effort version pointer
    writeVersionHint(nextVersion);

参见 HadoopTableOperations.java。version-hint.text 只是 best-effort 加速查找，丢了可以扫目录恢复；真正互斥的是「vN 这份文件是否已经存在」。renameToFinal() 发现目标已在，就当并发提交失败⁴。

Hive / JDBC 这类 metastore Catalog，指针是表属性里的 metadata_location：

// core/src/main/java/org/apache/iceberg/BaseMetastoreTableOperations.java:46-50
  public static final String TABLE_TYPE_PROP = "table_type";
  public static final String ICEBERG_TABLE_TYPE_VALUE = "iceberg";
  public static final String METADATA_LOCATION_PROP = "metadata_location";
  public static final String METADATA_HASH_PROP = "metadata_hash";
  public static final String PREVIOUS_METADATA_LOCATION_PROP = "previous_metadata_location";

Hive 提交前先核对「我看到的 base 路径」是不是 HMS 里当前那条，对不上就拒掉：

// hive-metastore/.../HiveTableOperations.java:304-310
      String metadataLocation = tbl.getParameters().get(METADATA_LOCATION_PROP);
      String baseMetadataLocation = base != null ? base.metadataFileLocation() : null;
      if (!Objects.equals(baseMetadataLocation, metadataLocation)) {
        throw new CommitFailedException(
            "Cannot commit: Base metadata location '%s' is not same as the current table metadata location '%s' for %s.%s",
            baseMetadataLocation, metadataLocation, database, tableName);

参见 HiveTableOperations.java。通过之后再把 metadata_location 写成新文件路径⁵。读者刷新 Catalog，拿到的就是新的 metadata.json。

三套系统并排看：

flowchart LR
    subgraph Linux["Linux x86"]
        CR3["CR3"] --> PGD["mm.pgd / 页表根"]
    end

    subgraph GitBox["Git"]
        HEAD["HEAD"] --> Branch["refs/heads/*"]
        Branch --> Commit["commit object"]
    end

    subgraph IcebergBox["Iceberg"]
        Cat["Catalog / vN.metadata.json"] --> Meta["metadata.json"]
        Meta --> Snap["current-snapshot-id"]
    end

    style CR3 fill:#87CEEB,stroke:#333,stroke-width:2px
    style HEAD fill:#87CEEB,stroke:#333,stroke-width:2px
    style Cat fill:#87CEEB,stroke:#333,stroke-width:2px

二、多层漏斗：按图索骥，不扫整片海

指针只解决「当前是哪一棵树」。树本身还得能快速缩小范围，否则每次访问都要遍历全部底层小块。这里的复杂度差就是 O(log N) / 分区裁剪 vs O(N) 全扫。

页表：PGD → P4D → PUD → PMD → PTE

x86-64 默认 4 级；LA57 打开后是 5 级。位移写在 pgtable_64_types.h 里：PGD、P4D（P4D_SHIFT 39）、PUD（30）、PMD（21）、PTE。每一级 512 项。

缺页时，内核按这棵树往下走，缺哪一级就分配哪一级：

// mm/memory.c:6466-6549
	pgd = pgd_offset(mm, address);
	p4d = p4d_alloc(mm, pgd, address);
	if (!p4d)
		return VM_FAULT_OOM;

	vmf.pud = pud_alloc(mm, p4d, address);
	...
	vmf.pmd = pmd_alloc(mm, vmf.pud, address);
	...
fallback:
	return handle_pte_fault(&vmf);

参见 mm/memory.c。已知地址已经落到 PMD 时，还有一条折叠助手，把四级偏移写成一行⁶：

// include/linux/pgtable.h:165-168
static inline pmd_t *pmd_off(struct mm_struct *mm, unsigned long va)
{
	return pmd_offset(pud_offset(p4d_offset(pgd_offset(mm, va), va), va), va);
}

MMU 硬件走同一条路径。它不会扫进程的全部物理页，只按虚拟地址切出每一级索引。

Git：commit → tree → blob

对象类型就三种常用的（再加上 tag）⁷：

// object.h:99-104
enum object_type {
	OBJ_BAD = -1,
	OBJ_NONE = 0,
	OBJ_COMMIT = 1,
	OBJ_TREE = 2,
	OBJ_BLOB = 3,
	OBJ_TAG = 4,

commit 只记住一棵根 tree，以及 parent 链：

// commit.h:27-39
struct commit {
	struct object object;
	timestamp_t date;
	struct commit_list *parents;
	struct tree *maybe_tree;
	unsigned int index;
};

tree 是目录项列表，项指向下一层 tree 或 blob。git commit 用 index 上的 cache_tree 当根 tree oid，不会为没改过的子树重写对象。查一个文件是「沿路径走目录项」，不是枚举整个对象库。

Iceberg：metadata → snapshot → manifest list → manifest → Parquet

规范里的快照结构是³：

1. metadata.json 记下 schema、partition spec，以及 current-snapshot-id
2. 每个 snapshot 有一份 manifest list
3. manifest list 里是若干 manifest，带分区统计和文件计数
4. manifest 里才是 data file / delete file 路径和列度量
5. 数据文件本身通常是 Parquet（也可以是 Avro / ORC）

Java 里当前快照就是按 id 取：

// core/src/main/java/org/apache/iceberg/TableMetadata.java:536-538
  public Snapshot currentSnapshot() {
    return snapshotsById.get(currentSnapshotId);
  }

扫描规划明确写了可以跳过整份 manifest⁸：

Manifests that contain no matching files, determined using either file counts or partition summaries, may be skipped.

实现上，ManifestEvaluator 用 manifest 的分区摘要判断这份文件里有没有可能命中的分区；过了这一关，再用 InclusiveMetricsEvaluator 看单个 data file 的列上下界。eval 返回 false，这份文件就可以不读。

叶子上的 Parquet 自己又是一层漏斗。文件尾部是 FileMetaData，里面是 row group 列表；读者先读 footer，再只打开关心的 column chunk / page⁹：

4-byte magic number "PAR1"
<Column chunks / row groups>
File Metadata
4-byte length of file metadata
4-byte magic number "PAR1"

struct FileMetaData {
  1: required i32 version
  2: required list<SchemaElement> schema
  3: required i64 num_rows
  4: required list<RowGroup> row_groups
  ...
}

参见 parquet.thrift。Iceberg 决定读哪些文件，Parquet footer 再决定读文件里的哪些列、哪些 row group。

三棵树并排：

flowchart TB
    subgraph PT["页表"]
        VA["虚拟地址"] --> PGD2["PGD"]
        PGD2 --> P4D["P4D"]
        P4D --> PUD["PUD"]
        PUD --> PMD["PMD"]
        PMD --> PTE["PTE / 物理页"]
    end

    subgraph GT["Git"]
        BR["branch / HEAD"] --> CM["commit"]
        CM --> TR["tree"]
        TR --> TR2["tree"]
        TR --> BL["blob"]
        TR2 --> BL2["blob"]
    end

    subgraph IB["Iceberg + Parquet"]
        CAT["Catalog"] --> MD["metadata.json"]
        MD --> SN["snapshot"]
        SN --> ML["manifest list"]
        ML --> MF["manifest"]
        MF --> PQ["Parquet file"]
        PQ --> FT["footer / row group / page"]
    end

三、先写影子，再原子切换

修改不能直接打在别人正在读的那份数据上。三套系统都是：在旁边做好新版本，最后一步才让指针看见它。

缺页分配物理页，和写时复制（COW）不是同一条路径。前者是「这页还没有」；后者是「这页有，但是只读共享，写就要拷一份」。内核把它们分成两条 fault 路径。

Linux：do_wp_page 拷页，再换 PTE

私有映射上的写过错到 do_wp_page()。能复用就复用；必须拷的时候走 wp_page_copy()¹⁰：

// mm/memory.c:4291-4320
	if (folio && folio_test_anon(folio) &&
	    (PageAnonExclusive(vmf->page) || wp_can_reuse_anon_folio(folio, vma))) {
		...
		wp_page_reuse(vmf, folio);
		return 0;
	}
	...
	return wp_page_copy(vmf);

拷完之后，先清旧 PTE 并冲 TLB，再挂上新页。注释写得很清楚：必须先切换页表项，才能把旧页的 mapcount 减掉，否则别的进程可能在窗口里写进旧页¹¹：

// mm/memory.c:3918-3929
		ptep_clear_flush(vma, vmf->address, vmf->pte);
		folio_add_new_anon_rmap(new_folio, vma, vmf->address, RMAP_EXCLUSIVE);
		folio_add_lru_vma(new_folio, vma);
		BUG_ON(unshare && pte_write(entry));
		set_pte_at(mm, vmf->address, vmf->pte, entry);

对这个进程来说，写操作成功了；共享这份旧页的其他进程，页表还指着原来的只读页。可见性切换发生在这一条 PTE，不是整棵页表重写。

fork 之后父子共享只读页、一方先写再触发上面这条路径，就是教科书里的进程级 COW。进程切换本身仍然只写 CR3。

Git：对象先落盘，ref 后移动

commit_tree_extended() 先拼 commit 缓冲区，校验 tree 类型，再写入对象库：

// commit.c:1729-1760
int commit_tree_extended(const char *msg, size_t msg_len,
			 const struct object_id *tree,
			 const struct commit_list *parents, struct object_id *ret,
			 ...)
{
	...
	odb_assert_oid_type(the_repository->objects, tree, OBJ_TREE);
	...
	write_commit_tree(&buffer, msg, msg_len, tree, parent_buf, nparents, author, committer, extra);

参见 commit.c。这一步失败，HEAD 不动。写成功之后，update_head_with_reflog() 才去锁 ref、写 lockfile、commit_lock_file() rename。并发更新用「期望的旧 oid」做 CAS，对不上就失败——和 Iceberg 核对 metadata_location 是同一类约束。

没改过的 blob / 子 tree 继续被新 tree 引用，这就是 Git 的 COW：只为变化路径分配新对象。

Iceberg：数据文件不可变，提交只换 metadata 指针

规范要求：文件写下去就不改；表不需要随机写。Hadoop 表才依赖 rename 实现 metadata 提交³。一次 append 大致是：

1. 写出新的 Parquet（以及需要的 delete file）
2. 写出新的 manifest；旧 snapshot 里还能用的 manifest 直接复用
3. 写出新的 manifest list 和 metadata.json
4. Catalog 原子替换指针

SnapshotProducer.commit() 先 apply() 得到新 snapshot，再 taskOps.commit(base, updated)；撞上 CommitFailedException 就按 commit.num-retries 重试¹²：

// core/src/main/java/org/apache/iceberg/SnapshotProducer.java:480-522
  public void commit() {
    AtomicLong newSnapshotId = new AtomicLong(-1L);
    ...
                taskOps -> {
                  Snapshot newSnapshot = apply();
                  newSnapshotId.set(newSnapshot.snapshotId());
                  TableMetadata.Builder update = TableMetadata.buildFrom(base);
                  ...
                  TableMetadata updated = update.build();
                  if (updated.changes().isEmpty()) {
                    return;
                  }
                  taskOps.commit(base, updated.withUUID());
                });

重试时序列号会重分，但新 manifest 可以复用——规范把这件事设计进了「从 manifest list 继承 sequence number」³。读者在指针切换前一直看着旧 snapshot，不会看见半成品文件。

sequenceDiagram
    participant W as Writer
    participant Shadow as 影子文件
    participant Ptr as 指针CR3或HEAD或Catalog
    participant R as 并发读者

    R->>Ptr: 读当前指针
    Ptr-->>R: 旧根
    W->>Shadow: 写新页或新对象或新metadata
    Note over W,Shadow: 读者仍走旧根
    W->>Ptr: 原子切换
    W-->>R: 下次刷新才看到新根

四、历史还在，回收另做

指针往前走以后，旧树不必立刻消失。历史查询靠「还有没有人引用」；物理回收是另一次显式动作。

Linux：进程退出拆掉页表

exit_mmap() 在 mm 的最后一个用户离开后，unmap 全部 VMA，再释放页表页¹³：

// mm/mmap.c:1273-1313
void exit_mmap(struct mm_struct *mm)
{
	...
	unmap_vmas(&tlb, &unmap);
	...
	free_pgtables(&tlb, &unmap);
	tlb_finish_mmu(&tlb);

物理页不是「进程一退就全扔」。文件页、共享库、还被别的 mm 指着的 COW 页，refcount 掉到 0 才回 buddy。这更像「丢掉这棵页表」，而不是格式化整台机器的内存。

内核没有 git log 那种地址空间时间旅行。fork 出来的 COW 页是分叉，不是同一份 mm 的快照链。

Git：reflog 可查，gc 清孤儿

commit 的 parents 就是历史链。git log 顺着它走。失去所有 ref / reflog 引用的对象，才是 gc 的对象。git gc 会跑 prune-packed，把已经打进 pack 的松散对象删掉¹⁴：

// builtin/gc.c:973-983
static int prune_packed(struct maintenance_run_opts *opts)
{
	struct child_process child = CHILD_PROCESS_INIT;

	child.git_cmd = 1;
	strvec_push(&child.args, "prune-packed");
	...
	return !!run_command(&child);
}

对象不可变，所以回收很朴素：还被 ref 指着的留下，没人指的删除。

Iceberg：time travel 与 expireSnapshots

snapshot 带 parentId() 和 timestampMillis()，规范里的 snapshot references 就是 branch / tag¹⁵。expireSnapshots 先提交一份去掉过期 snapshot 的新 metadata，再按引用关系删文件：

// core/src/main/java/org/apache/iceberg/RemoveSnapshots.java:360-379
  public void commit() {
    Tasks.foreach(ops)
        ...
            item -> {
              TableMetadata updated = internalApply();
              ops.commit(base, updated);
            });
    ...
    if (CleanupLevel.NONE != cleanupLevel && !base.snapshots().isEmpty()) {
      cleanExpiredSnapshots();
    }
  }

参见 RemoveSnapshots.java。和 Git 一样：先让指针和引用集合不再指向旧 snapshot，再物理删 Parquet / manifest。还被别的 branch、tag 或保留窗口钉住的文件不能删。

对照一下这四件事：

间接层做的事，就是在逻辑名字和物理块之间放一张会原子更新的地图。CR3、HEAD、Catalog 都是这张地图的入口。地图本身分层，是为了把「找一块」从扫全表收成按路径走。写入先发生在影子里，最后一步才换入口，读者才看不到半成品。

LSM-Tree 也可以用同一副眼镜看：WAL / memtable 是新影子，SST 是不可变块，compaction 是后台重写树，manifest 是那枚指针。那是另一篇的事。

References

• 上一篇 IDT、SYSCALL 与 FRED：三条内核入口，同一份 pt_regs？