5.1 LSM-Tree 写入、SSTable 与读取合并
Log-Structured Merge Tree 把在线更新先写入 WAL 与 memory-resident sorted structure，再把有序 runs flush 到 storage。它减少了前台对随机 page 的原地修改，却没有消灭写入成本：flush、compaction、metadata 与 garbage collection 会在后台偿还债务。
本课目标
- 描述 WAL、mutable/immutable memtable、SSTable 的状态转换；
- 解释 sequence number、tombstone 与 snapshot visibility；
- 理解 block index、Bloom filter 和 block cache 的职责；
- 分析 point lookup 与 range scan 为什么需要 merge；
- 避免“LSM 所有 I/O 都是顺序写”的错误结论。
写入管道
一个简化流程：
write batch
-> append WAL record
-> insert internal entries into mutable memtable
-> acknowledge according to durability option
mutable memtable reaches threshold
-> freeze as immutable memtable
-> create a new mutable memtable
-> background flush immutable memtable to SSTable
-> install new file through version/manifest metadata
-> retire WAL segments no longer needed for recovery不同 engine 对 WAL sync、batching、memtable implementation、file installation 和 atomicity 有不同契约。不能从“调用 Put 返回”自动推出数据已经 power-loss durable；要看 write options 与 storage stack。
前台写不保证永不阻塞
若 immutable memtables 或 Level 0 files 积压，engine 必须 slowdown 或 stop writes，否则内存和读取成本会无限增长。LSM 提高 burst absorption，却不能让长期 logical write rate 超过 storage 能完成的 flush + compaction rate。
Internal key：用户 key 之外还有版本
同一个 user key 会被多次更新。SSTables immutable，旧值不能原地覆盖，因此 engine 通常用类似结构排序：
(user_key ascending, sequence_number descending, value_type)sequence number 建立全局/局部 update order，value type 区分 value、deletion 等。读取 snapshot S 时，只考虑 sequence <= S 的最新可见 entry。
这是概念模型，具体 encoding 与 snapshot semantics 由 engine 决定。
Delete 是 tombstone
Put(k, v1) at seq=10
Delete(k) at seq=20delete 不能立刻从所有旧 SSTables 擦掉 k，而是写 tombstone。对 S >= 20 的快照，读取发现 seq=20 tombstone 后不能返回 seq=10 的值；对 10 <= S < 20 的旧快照，删除还不可见，仍应读到 v1。
tombstone 只有在 compaction 能证明更旧版本不再被 snapshot、lower level 或 replication/backup boundary 需要时才能丢弃。过早删除会让旧值“复活”。
range tombstone、merge operator 和 column-family drop 又会增加更复杂的覆盖规则。
MemTable
memtable 需要支持 ordered insert 和 lookup，常用 skip list、tree 或 hash+ordered variant。它位于内存，但 entry 仍包含 allocator、key/value 与 version metadata，不应只按用户 payload 估算容量。
freeze 后 immutable memtable 不再接受更新，后台按 key order flush。系统可同时存在多个 immutable memtables；数量上升是 flush 跟不上写入的直接信号。
SSTable 是 immutable sorted run
典型 block-based SSTable：
data blocks
index block: separator/last key -> block handle
filter block or partitioned filters
properties/metadata
metaindex
footer: locating top-level metadata实现还可能有 compression dictionary、range-deletion block、checksum、partitioned index/filter。SSTable 不是一个固定标准格式，LevelDB、RocksDB、Cassandra/ScyllaDB 等不可互换读取。
Data block
entries 按 internal key 排序。为了压缩重复 key prefix，block 可周期保存 restart point，其余 entry 保存 shared-prefix length + unshared bytes。这样 lookup 先定位 restart 区域，再局部解码，而不是必须从 block 开头重建全部 keys。
Block index
index 把 key ranges 映射到 data-block offsets/handles。index 自身可能常驻 memory/block cache，也可能 partition，避免巨大 database 的单层 index 占满内存。
Bloom filter 的准确边界
Bloom filter 对“构建时加入的 key”：
- negative 表示 definitely not present；
- positive 表示 possibly present；
- false positive 可能导致多读一个 file/block；
- 正确实现中不应出现 false negative。
但最后一条有前提：filter 必须覆盖正确 key domain，读取使用相同 prefix extractor/comparator/config，文件没有 corruption。prefix Bloom 只回答 prefix 查询；配置改变或不兼容 extractor 会使 filter 无法按预期使用。
bits-per-key 与 false-positive rate 有数学关系，但真实收益还取决于 hash/probe count、cache、query mix 和 CPU。不能写成“10 bits 一定过滤 99% SSTables”。
普通全键 Bloom filter 回答某个键是否可能存在，不能直接证明整个任意范围为空。Prefix filter 可跳过不含目标前缀的文件，但其作用范围取决于 extractor 和查询边界，不能当成通用范围索引。
Point lookup
概念路径：
1. mutable memtable
2. immutable memtables, newest first
3. overlapping Level 0 files, newest relevant first
4. lower levels / runs according to compaction layout
5. stop when newest visible value/tombstone has been resolved每个候选 file 可先用 key range、filter、index 缩小，再读取 data block。block cache hit、filter/index residency、checksums 和 compression 都影响 latency。
“每层固定读一次”不是普遍公式：
- Level 0 files 常有 overlapping ranges，可能检查多个；
- leveled lower levels 同层 ranges 通常不 overlap，可定位至至多一个 relevant file；
- tiered/universal layout 同一 key range 可能跨多个 runs；
- tombstone/snapshot/merge operand 可能要求继续寻找旧 entry；
- filter negative 可避免 data read，但仍有 filter/index 工作。
Range scan 是多路归并
每个 memtable/SSTable 提供 ordered iterator，再用 heap/loser-tree 等方式 merge：
iterator(memtable) ---\
iterator(L0 file A) ----\
iterator(L0 file B) -----> merge by user key/version -> visibility -> output
iterator(L1 file) ------/对同一 user key，只输出 snapshot 下最新有效 value；tombstone 和旧 versions 被抑制。active iterators 多、files overlap 大时，CPU、cache miss 与 I/O 都会上升。
range query 是 LSM 设计的重要成本，不能只用 Bloom filter 的 point-lookup 优势代表全部读取。
WAL 与 SSTable installation
flush 生成新 SSTable 后，engine 不能只靠“rename 文件”就宣称持久完成，还要原子/可恢复地更新当前 version metadata，并确保 file contents、directory/manifest ordering 满足 crash contract。
RocksDB 使用 MANIFEST/version edits 等机制管理 live files。孤立的 .sst 文件不一定属于当前 database version，不能用目录中文件数量直接推断可见数据。
Cache 层次
LSM engine 可能同时拥有：
- memtables；
- uncompressed block cache；
- compressed cache/OS cache；
- table reader/index/filter metadata；
- row cache；
- application cache。
给 block cache 加内存可能挤压 memtable，导致更频繁 flush；给 memtable 太多内存又会扩大 recovery/WAL/flush burst。memory budget 应整体规划。
本课小结
LSM-tree 把更新表达为带版本的 immutable runs。WAL 与 memtable 承接前台写，SSTable 提供有序持久结构，读取通过 filter/index 和多路归并解析最新可见版本。下一课讨论 compaction 如何控制 file 数量与旧版本，同时产生读、写、空间和尾延迟之间的取舍。