形式陈述
LSM式存储批量整理更新，实现字典的put、get、delete接口。本文采用现代SSTable教学模型：更新为(key,sequence,kind,value)，sequence全局递增，kind为PUT或DEL；单进程无并发事务，所有已发布更新都已提交，先只服务最新读。相同键取最大序号，DEL表示缺失。历史物理版本不等于bag中的多份现行值。
写入先进入内存有序表memtable；满后冻结，写成按(key升序,sequence降序)排列的不可变段SSTable。读取必须在memtable及可能含该键的所有段中，找最大有效序号，或使用已证明的新旧范围顺序安全提前停止。不同层可能有重叠文件，不能任意遇到一个值就返回。
压实compaction用多路有序归并读取选定段，把同键版本聚到一起并生成新段。只服务最新读时，若所有更旧覆盖版本都已包含或已证明不存在，可删旧PUT；DEL还必须保证外部未参与段没有可被它遮住的旧值，才可丢弃。允许快照后，还须保留每个活跃快照可能读取的版本；“最大序号”规则不再足够描述所有读。
持久化写路径仍需WAL或等价恢复协议。另明确元数据故障合同：新manifest可完整写入稳定存储，发布指针切换具有崩溃原子性，恢复只能选完整旧版或完整新版，已确认稳定的切换不回退。撕裂记录、目录持久化与设备错误需由实现满足该合同，不能仅凭文件写返回推定。
本文规定发布顺序：先让新段内容与所需文件名称稳定，再把引用新段、移除旧段的manifest变更可靠持久化，发布新的可读版本；最后在没有旧版本读者引用后回收旧文件。
flush完成且对应段已稳定发布后，只有某WAL前缀内全部更新都已具有恢复所需的稳定表示，才可回收该前缀；其他尚在memtable中的更新不能被顺带丢弃。排序和压实本身不是commit或持久化证明。
直觉
小更新先记到内存里，凑成批次再写大块有序文件，避免每次都随机修改旧页。代价是读者可能要检查几份文件，后台还要反复重写数据以减少重叠。
删除标记像贴在旧文件外的“这项已经作废”。如果只扔掉标记而旧文件仍在，下一次读就会让已删除值复活。
例子与边界
两个段与一次删除
设旧段A有(a,1,PUT,10)、(b,2,PUT,20)；新段B有(a,3,PUT,11)、(b,4,DEL)、(c,5,PUT,30)。最新读a必须得到11，b缺失，c得到30。按文件字母A先找到a=10就返回是错的；序号3才是最新。
压实A和B且证明再无更旧段，也无活跃历史快照，可以输出C={(a,3,PUT,11),(c,5,PUT,30)}。b的DEL与旧PUT同时消失，最新字典不变。若只压实B而A留在外部，必须保留(b,4,DEL)，否则读者会从A重新找到b=20。
若还有快照q=2，a应读10、b应读20，所以不能用只含最新a=11、c=30的C替代全部旧版本。回收条件必须从“服务最新读”升级为“服务所有仍允许的读视图”。这与MVCC版本回收相接，但本页序号模型不自动实现事务隔离。
Bloom放在哪里
段的键范围先排除明显不可能的文件；再用Bloom过滤器检查该段是否可能含查询键。过滤器返回否才可跳过；返回可能必须继续查段内索引与数据块。过滤器构建与查询必须使用一致的用户键/编码，并覆盖该段每一个PUT和DEL所用键；不能因为“这是删除”而漏插b，否则假阴性的跳过可能暴露更旧b=20。过滤器缺失、编码不一致、损坏或未同步发布时，应保守读取权威段，不能把它当作“不存在”的证据。
假设负查询d落在三个候选段的范围内，每段索引与过滤器已在内存，一次确认假阳性要读1个数据页。没有过滤器就读3页；三个过滤器都否则读0页；只有一个误报就读1页。若各过滤器误报概率为pᵢ，期望数据读数是Σpᵢ，此处线性期望不要求过滤器相互独立。读取过滤器本身的I/O与CPU另计。
压实与崩溃账本
仍用每页2条的教学段格式，A占1页、B占2页；压实读3页，C两条写1页，共4次数据I/O，另计manifest与同步。归并给A、B各1输入帧及1输出帧，至多3个数据帧；键和当前最大序号等控制状态另计。因为输入按键及序号有序，最新读模型只需保留当前键的胜出版本，不必把同键全部历史装入内存。一般r路压实需要r个输入缓冲和1个输出缓冲，或再分阶段；不能无视同时打开的段数。
若C已写出但manifest尚未稳定就崩溃，恢复继续引用旧A、B；C只是可清理的孤儿。若manifest已经稳定但旧A、B尚未删，恢复只按新manifest读C，额外旧文件不应当再次并入答案。先删旧文件再发布C会留下无法恢复的空窗。
推论与应用
分层压实可让多数非零层的文件键范围互不重叠，减少每层候选文件；tiered策略可保留多个run以少重写，读者需查更多候选。这是写放大、读放大和空间暂占之间的取舍，不存在与工作负载无关的固定优胜者。
写放大应定义分母：例如仅计数据段，初次flush写D字节、之后压实重写3D，则段写放大为4；若把WAL也计入，数值还会变。最坏单次写延迟、后台摊还吞吐与长时间压实欠账也不是同一指标。
Bloom不保存值，不决定最新版本，也不替代段内精确搜索；压实减少文件数也不能保证每次读只访问一页。检查系统应组合“删除不复活”“快照可重现”“发布前后崩溃有完整版本”三类测试。
参考资料
- Patrick O’Neil et al., “The Log-Structured Merge-Tree”，Acta Informatica 33, 1996，§§2–3：内存/磁盘组件与批量合并思想；原文结构不等同于本文所有现代SSTable细节。
- CMU 15-445/645 Fall 2025，Database Storage II，§3：memtable、SSTable与压实取舍。
- Google LevelDB，Implementation，Sorted tables、Manifest、Compactions、Recovery各节：有序文件、删除标记和版本目录。本文明确的崩溃发布合同为保守教学规格，不逐字套用该文的简略步骤。