05 · 从追加日志理解 LSM 与合并

目标：解释日志结构存储如何查找最新值，以及合并为何不能随意丢弃删除标记。

先让写入简单，再支付读取成本

活动标题被反复修改。最直接的持久化方法是把每次变化追加到文件末尾；旧值仍存在，读取时找到最新版本。这适合顺序追加，却会让全文件扫描越来越慢。内存索引可以记住每个键的位置，但索引可能太大，也需要在故障后恢复。

LSM 的典型做法是先写预写日志以支持恢复，同时更新内存表；内存表刷成按键排序、不可变的 SSTable。读取可能要查内存和多个文件，合并（compaction）把多个有序文件整合，清理旧版本。排序使范围扫描和归并成为可能。真实实现还包含块索引、缓存和恢复协议，本课只模拟版本合并。

Bloom filter 可以快速判断某文件肯定没有一个键，或者可能有它。正确构建且匹配该文件版本时允许假阳性、不应有假阴性；它能减少无效查找，不负责返回值。层级合并和分层合并在写放大、读放大与空间占用之间选择不同平衡。

被删除的活动为什么会复活

保存 log_storage.py。None 在这个实验中特指 tombstone，即删除标记，不是普通业务值。先预测移除删除标记之后会读到什么。

older = {"a1": (1, "旧标题"), "a2": (2, "仍在举办")}
newer = {"a1": (3, None)}

def read(segments, key):
    versions = [s[key] for s in segments if key in s]
    return max(versions, key=lambda pair: pair[0])[1] if versions else None

def compact(segments):
    merged = {}
    for segment in segments:
        for key, version in segment.items():
            if key not in merged or version[0] > merged[key][0]:
                merged[key] = version
    return dict(sorted(merged.items()))

assert read([older, newer], "a1") is None
wrong_newer = {k: v for k, v in newer.items() if v[1] is not None}
assert read([older, wrong_newer], "a1") == "旧标题"
merged = compact([older, newer])
assert read([merged], "a1") is None
print("after_bad_cleanup:", read([older, wrong_newer], "a1"))
print("after_merge:", read([merged], "a1"))

uv run --python 3.12 --no-project log_storage.py

预期输出：

after_bad_cleanup: 旧标题
after_merge: None

读取按版本号选最新值。版本号是本例预先分配的单调序号，不是随意取各机器墙上时钟。删除标记的作用是遮住旧版本；只清理新文件中的标记，旧文件的标题就重新可见。

引导修改：① 在 newer 中增加 a2: (4, "已改期")；② 运行；③ 增加断言，确认合并后的 a2 是新值；④ 交换两个段的输入顺序，结果应不变，因为版本号决定覆盖关系。

独立练习：已经把所有旧段合成一个完整段，且没有读旧版本的快照、落后副本或备份恢复需求。在这个受限模型里，如何安全地清除 a1 的墓碑？为什么现实里条件更复杂？

参考解答

在 merged 生成后创建 clean = {k: v for k, v in merged.items() if v[1] is not None}，原子地用 clean 替换全部旧段；验证 read([clean], "a1") is None。只替换一个局部段不够。现实里还需确认不存在可能重新引入旧值的副本、快照读取或旧文件引用，因此清理依赖系统的版本与保留策略。

如果交换输入顺序影响结果，检查是否误用了简单的后遍历覆盖。若用 None 保存合法业务值，应把删除编码为独立操作类型。合并会重写未被用户直接修改的数据，所以高写入吞吐也可能伴随高写放大和后台抖动，不能把“追加”理解成“每份数据只写一次”。

在 design.md 写下活动数据的更新频率、范围查询需求，以及为何需要测量合并期间的尾延迟再选择引擎。

参考资料

DDIA 第二版第 4 章：日志结构存储、SSTable、Bloom filter 与合并。