前面十一篇建立的索引有一个隐含假设：文档集合是静态的。建完索引就不变了。但实际场景中，文档会增加、修改、删除。一篇文档改了标题，搜索结果应该反映新标题；一篇文档被删除，搜索不应该返回它。

在倒排索引上直接修改代价很高——删除一篇文档意味着遍历它包含的每个词项的 posting list，逐一移除对应的 docID。10,000 篇文档的索引里删除一篇，可能要修改上千个 posting list。

本篇解决三个问题：怎样标记删除、怎样安全地提交新版本索引、怎样在崩溃后恢复到一致状态。

标记删除：Tombstone

不直接修改 Posting List

直接从 posting list 中移除 docID 需要：

  1. 找到该文档包含的所有词项（需要正向索引或重新分析文档）
  2. 在每个词项的 posting list 中定位并删除对应 docID
  3. 如果 posting list 用了 delta 编码，删除一个元素需要重新编码后续所有 gap

这个操作的代价与文档包含的词项数成正比——对一篇包含 1,500 个不同词项的文档，要修改 1,500 个 posting list。如果频繁删除，索引性能不可接受。

Tombstone 位图

换一种思路：不改 posting list，只在旁边放一个标记。

1
2
3
4
5
6
BitSet deletedDocs; // 第 i 位为 true 表示 docId=i 已删除

void deleteDocument(int docId) {
    deletedDocs.set(docId);
    persistDeletions(); // 写入磁盘
}

查询时加一个检查：

1
2
3
4
5
for (int docId : postingList) {
    if (deletedDocs.get(docId)) continue; // 跳过已删除
    double score = bm25(queryTerms, docId);
    updateTopK(heap, docId, score);
}

开销：每个文档一个 bit。10,000 篇文档的 tombstone 位图只需要 1.25 KB。

更新 = 删除 + 插入

更新文档不是原地修改，而是：

  1. 标记旧版本为已删除（在 tombstone 位图中置位）
  2. 在新段中写入新版本（分配新的 docID）

这意味着同一篇文档可能有多个版本散布在不同的段中，但只有最新版本未被标记删除。

Lucene 的做法完全一样：IndexWriter.updateDocument() 内部就是 deleteDocuments(term) + addDocument(doc)。每个段有一个 .liv 文件记录存活文档的位图。

物理清理

Tombstone 标记的文档仍然占磁盘空间和查询时的遍历开销。段合并（第 10 篇的 k-way merge）时顺便清理——已删除的 docID 不写入合并后的新段。这就是为什么段合并不只是性能优化，也是空间回收的手段。

提交清单

问题

索引由多个段文件和删除位图组成。哪些文件属于当前有效的索引？需要一个元数据文件来记录——这就是提交清单（commit point）。

1
2
3
4
5
6
7
8
{
  "generation": 3,
  "segments": [
    {"name": "seg-0", "docCount": 5000, "delCount": 120},
    {"name": "seg-1", "docCount": 3000, "delCount": 0},
    {"name": "seg-2", "docCount": 2000, "delCount": 0}
  ]
}

每个段记录名称、文档总数和已删除文档数。generation 是递增的版本号——每次提交，generation +1。

Lucene 用 segments_N 文件（N 是 generation 编号），记录当前索引包含哪些段、每个段的状态、删除计数等。

为什么需要 Generation

如果只有一个 commit.json，修改它的过程中崩溃会留下损坏的文件。用 generation 编号：

  • 当前有效提交是 commit-003.json
  • 新提交写到 commit-004.json
  • 如果写入过程中崩溃，commit-003.json 仍然完好
  • 启动时找到最大 generation 的有效提交文件即可

原子切换

写入新提交的流程

1
2
3
4
5
6
1. 将新段文件写入磁盘 → seg-3
2. fsync seg-3（确保数据从 OS 缓存落到磁盘）
3. 将新提交清单写入临时文件 → commit-004.tmp
4. fsync commit-004.tmp
5. rename commit-004.tmp → commit-004.json（原子操作）
6. 删除不再需要的旧文件

关键在 step 5：POSIX rename() 在同一文件系统内是原子操作。要么完成（commit-004.json 存在且完整），要么没发生（只有 commit-004.tmp）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void atomicCommit(CommitData data, Path indexDir) throws IOException {
    int gen = data.generation();
    Path target = indexDir.resolve("commit-%03d.json".formatted(gen));
    Path tmp = indexDir.resolve("commit-%03d.tmp".formatted(gen));

    // 写临时文件
    try (var out = new BufferedOutputStream(Files.newOutputStream(tmp))) {
        writeJson(data, out);
        out.flush();
    }

    // fsync 临时文件
    try (var ch = FileChannel.open(tmp, StandardOpenOption.READ)) {
        ch.force(true);
    }

    // 原子 rename
    Files.move(tmp, target, StandardCopyOption.ATOMIC_MOVE);

    // fsync 目录（确保 rename 在目录项中可见）
    try (var dirCh = FileChannel.open(indexDir, StandardOpenOption.READ)) {
        dirCh.force(true);
    }
}

fsync 的必要性

没有 fsync，数据可能还在 OS 的页缓存中。断电时页缓存丢失——文件看起来写完了，但磁盘上可能是空的或半截的。

fsync 的代价：一次 fsync 在 SSD 上约 0.1-1 ms，在 HDD 上约 5-15 ms。频繁 fsync 会拖慢写入。教学场景不用在意这个延迟。

启动恢复

恢复流程

程序启动（或崩溃重启）时：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
IndexState recover(Path indexDir) throws IOException {
    // 1. 扫描所有 commit-NNN.json 文件，按 generation 降序
    List<Path> commitFiles = findCommitFiles(indexDir);
    commitFiles.sort(Comparator.reverseOrder());

    // 2. 找到第一个有效的提交
    CommitData commit = null;
    for (Path cf : commitFiles) {
        try {
            commit = readAndVerifyCommit(cf);
            break; // 找到有效提交
        } catch (IOException e) {
            // 这个提交文件损坏，尝试上一个 generation
        }
    }
    if (commit == null) {
        throw new IOException("无有效提交，索引不可恢复");
    }

    // 3. 加载提交中列出的段文件，验证 CRC32
    List<Segment> segments = new ArrayList<>();
    for (SegmentInfo info : commit.segments()) {
        Segment seg = loadAndVerifySegment(indexDir.resolve(info.name()));
        segments.add(seg);
    }

    // 4. 删除孤儿文件
    Set<String> validFiles = commit.allReferencedFiles();
    for (Path f : Files.list(indexDir).toList()) {
        String name = f.getFileName().toString();
        if (!validFiles.contains(name) && !name.startsWith("commit-")) {
            Files.deleteIfExists(f);
        }
    }

    return new IndexState(segments, commit);
}

崩溃场景覆盖

崩溃时刻 磁盘状态 恢复结果
写新段文件过程中 新段不完整，旧 commit 有效 回到旧 commit，新段被清理
新段 fsync 完成，commit 未写 新段完整但不可见 回到旧 commit，新段被当孤儿清理
commit tmp 写完，rename 未执行 tmp 文件存在 回到旧 commit，tmp 被清理
rename 完成 新 commit 生效 使用新 commit
删除旧文件过程中 旧文件部分残留 新 commit 有效，下次启动继续清理

每种情况都回到最后一个成功的 commit——不会丢失已提交的数据，不会看到半提交的状态。

删除不复活

被标记删除的文档不会因崩溃恢复而重新出现。删除操作写入 tombstone 位图并持久化，位图文件被提交清单引用。只要 commit 包含了最新的 tombstone，恢复后删除仍然有效。

反例验证：删除文档 42，提交，崩溃，重启——文档 42 仍然被标记删除，搜索不会返回它。

验证

验证方法是在每个关键步骤注入崩溃（模拟进程退出），然后检查恢复结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void testCrashDuringSegmentWrite() {
    // 开始写新段，中途抛异常模拟崩溃
    // 重启恢复，验证索引回到提交前状态
}

void testCrashAfterSegmentBeforeCommit() {
    // 新段写完但 commit 未 rename
    // 重启恢复，验证新段被清理，索引不变
}

void testCrashAfterCommit() {
    // commit rename 完成
    // 重启恢复，验证新数据可见
}

void testDeleteSurvivesRecovery() {
    // 删除文档，提交，模拟崩溃
    // 重启恢复，验证已删除文档不出现在搜索结果中
}

当前局限

  • 没有实现预写日志（WAL）——本篇的恢复只保证回到最后一次提交，提交之间的操作会丢失
  • 没有实现并发控制——单线程写入，多线程读取需要用快照隔离（第 14 篇处理）
  • tombstone 位图在内存中是完整的——对百万级文档仍然只需要约 125 KB，不是瓶颈
  • 提交频率没有策略——何时触发提交（按时间、按文档数、手动）留给应用层决定
  • 段合并时的物理清理没有实现并发安全——正在搜索的线程可能引用即将被删除的段

练习

  1. 实现 tombstone 位图的持久化：写入一个 .del 文件，格式为位图的字节数组
  2. 在写新段和 commit rename 之间插入 System.exit(1)，验证重启后索引回到上一次提交
  3. 删除 3 篇文档后提交，崩溃重启，验证这 3 篇文档搜索不到
  4. 构造一个场景：两个 generation 的 commit 文件同时存在，验证恢复选择最新的有效 generation
  5. 测量 fsync 的延迟：对一个 1 MB 的段文件，比较有 fsync 和无 fsync 的写入时间

延伸阅读

  • Introduction to Information Retrieval, Chapter 4.5: Dynamic indexing
  • Lucene 源码：org.apache.lucene.index.IndexWriter（commit 流程）
  • Lucene 源码：org.apache.lucene.index.SegmentInfos（segments_N 格式）
  • POSIX rename(2) man page（原子性保证）