LSM 树：永远不原地改，写一张新的排好序的文件，后台再合并

它是干嘛的。 扛住很重的随机写负载，而不用每次写都付一次随机写的代价。B-tree 是原地改：找到页、插进去、满了分裂、再改父节点。LSM 是把这笔账换一种付法：把随机的结构写换成顺序追加，代价是读变贵了。

先看全图。 写先进内存，写满刷成新表，读从新往旧翻表，合并在后台归并：

写路径。 每次写先写 WAL（保掉电不丢），再进 memtable，那是内存里排好序的结构（一般是跳表），插进去只改指针，不搬数据。memtable 满了，就按 key 顺序遍历一遍，顺序写成一张全新的不可变 SSTable：排好序，带索引块和布隆过滤器。旧 SSTable 一个字不动，永远不改。

为什么插入永远不用挪。 往排好序的数组里插，后面全要挪；往跳表里插，只改指针：

读路径。 先查 memtable，再从新往旧查 SSTable，找到就停：新版赢。在一张表里，布隆过滤器先上：它不读任何数据块就能回答“这个 key 在这张表里吗”。说没有就一定没有，整张表直接跳过，零磁盘 IO。说可能有，才二分查索引块拿到块的字节偏移，seek 直接跳过去，再在块里二分找 key。所以布隆过滤器定查哪张表，二分查找定表里查哪。光靠索引干不了过滤器的活：索引只能说“如果这个 key 在这张表里，它会在哪一块”，说不了“它在不在这张表里”。

实测例子：一次读，两个可能，一次扑空，一次命中。 磁盘上有三张表，从新往旧：T3 里是 grape、lemon、peach；T2 里是 apple、mango、sun；T1 里是 book、dog、kite。读 sun。memtable 里没有。T3 的布隆过滤器说可能有：打个比方，sun 算出来是 3 号和 7 号位，grape 置了 3 号位、lemon 置了 7 号位，过滤器被骗了。二分查 T3 的索引、seek、块里二分：sun 不在。这就是一次误判，代价就是多读了一块，什么都没漏。T2 的过滤器也说可能有，这回二分找到了 sun。返回，停。T1 碰都没碰。如果哪张表的过滤器说了没有，那张表连一次磁盘都不用读就跳过了。实际系统里，过滤器块、索引块、数据块读之前都先看共用的块缓存，缓存里有就不用碰磁盘；上面走的是缓存没命中的那条路，为简单起见这么画。

更新和删除也是写。 一个 key 的新版就是一张新表里的一条记录，盖住所有旧版。删除是一条 tombstone 记录：读到 tombstone 就停，报没有。tombstone 要等合并的时候、确认它盖住了底下所有旧版，才会被清掉。

tombstone 的一生。 删除也是一次写，旧版要等后面的合并才真正清掉：

合并：唯一真正排成一条线的地方。 每张 SSTable 自己内部是排好序的，但表和表之间根本没有全局顺序，表之间只有新旧关系。全局顺序是读的时候现算出来的（从新往旧归并），物理上只有后台合并才产出：读几张表、按 key 归并排序、写新表、删旧表。插入永远不重写旧文件，只有合并才写新文件。两种策略：leveling 每层只留一个排好序的 run（读便宜，写放大高），tiering 每层留多个 run（写放大低，读放大高）。

三个放大。 写放大：合并要重抄数据。读放大：一个 key 可能要翻 memtable 加好几张表。空间放大：旧版和 tombstone 在合并清掉之前一直占着地方。

L0 和写停顿。 写路径有个速度上限，就在 L0。刷盘落到 L0，L0 是唯一文件互相重叠的层，因为刷下来的表没经过归并。从 L1 往下，合并保证文件不重叠，读一层最多查一张表；L0 的文件随便重叠，读可能要翻所有 L0 文件。写来得比合并清得快，背压就来了，分两档：先故意把写拖慢，给后台争取时间；L0 再涨下去，写就直接停下，等合并把 L0 降下来再放开。这就是你说的限流 queue：写是进水，合并是漏水，memtable 加 L0 是桶的大小，合并速度是漏水速度。进水比漏水快，桶满了入口就得限流。所以 LSM 的写不是免费，代价是后台合并的活加偶尔的刹车；负载低于合并速度，写感觉就是免费的，超过就刹车。

版本号和快照。 表不可变，旧版一直躺着，读怎么知道哪个版才是“我该看到的”？每个写带一个递增的版本号，读开始先记一个快照号，就是当时最新的版本号，读只认版本号小于等于快照号的版本，从新往旧找到第一个就是答案。所以“新版赢”前面要加定语：是对你的快照来说最新的那个赢，不是全局最新的赢。合并也不能随便清旧版，只要还有快照可能看到它，就得留着，快照一关才能清。这就是 MVCC 穿了件 LSM 的衣服：版本号就是事务时间戳，快照就是 MVCC 快照，旧版留着就是为了还没结束的读。

块里面：前缀压缩和 restart 点。 块里 key 是排好序的，相邻的 key 前缀经常一样，比如 user:1001、user:1002、user:1003，共用 user:10。块里就只存不同的后缀加一个“前面几个字跟上条一样”的数，省不少地方。但这样就没法直接二分了，因为你要从头一条一条还原才能知道每条 key 是什么。所以每隔 N 条（一般 16 条）存一个完整 key，叫 restart 点：先在 restart 点上二分，再在两个 restart 点之间往前扫着还原，块就又小又能查。块本身还可以再压一遍，Snappy、LZ4、Zstd 这种，拿 CPU 换磁盘 IO。

合并怎么挑文件。 合并从来不是整层重写，整层重写写放大就炸了。触发条件就三条：L0 文件数超了、某层大小超了、等合并的字节数超了。每次只挑一个文件，加上下一层里所有跟它 key 范围重叠的文件，归并完写到下一层。L0 到 L1 特殊，因为 L0 文件互相重叠，一次要把 L1 里所有跟选中范围重叠的文件都带上；L1 往下每层文件不重叠，挑一个文件加下层重叠的几个就行。leveled 里每层大小约是上一层的 10 倍，所以层数就是数据量的对数，读放大有界。合并还顺手干清理的活：tombstone 在确认盖住旧版、且没有快照还需要它的时候清掉，快照都看不见的旧版清掉，TTL 到期的记录平时没人主动删，合并时顺手清掉。

MANIFEST：文件集的账本。 数据有 WAL 保，文件集本身也要账本，叫 MANIFEST。每次刷盘、合并完成，先写一条 edit 到 MANIFEST：新文件进了、旧文件出了，然后再删旧文件。崩溃在中间怎么办：edit 没写，等于合并没发生，旧文件还在，新文件是孤儿，恢复时清掉；edit 写了，新文件集生效，再删旧文件。原子切换靠的就是 edit 先行这个顺序。

范围扫描。 点查是找一个 key，范围扫描是把 memtable 加各表里这个范围的 key 归并着吐出来：每路一个迭代器（memtable 和每张表），都按顺序吐 key，一起喂给 k 路归并堆，堆顶永远是当前最小的、快照可见的、最新版。每吐一个就推进那一路。快照规则跟点查一样，只认快照号以内的版本，同一 key 多版只吐最新可见版，tombstone 截断后面的旧版。

谁在用，谁不用。 Cassandra、HBase、ScyllaDB 清一色是 LSM；LevelDB、RocksDB 是 LSM 存储引擎，CockroachDB、TiKV 底层就是拿它们；InfluxDB 也是 LSM。同族不同名：Lucene 的段、ClickHouse MergeTree 的 part，都是不可变块加后台合并。不是 LSM 的：PostgreSQL、MySQL 的 InnoDB，那是 B-tree。选型规矩：写重走 LSM，点查重加事务走 B-tree。

布隆过滤器，一段话讲完。 位数组加 hash 函数：它存的不是 key 本身，是 key 留下的痕迹。加入一个 key 就置几个位，查的时候验这几个位。有一个位是 0，这个 key 一定没加入过：没有漏判。几个位全是 1，这个 key 可能加入过，也可能是别的 key 的痕迹凑巧盖住了这几个位：误判可能有，一个 key 大概 10 个位的时候误判约 1%。每张表的过滤器跟表一起存在磁盘上，查的时候读进数据库共用的那一个块缓存，不是每张表各一个缓存。经典过滤器不能删，因为一个位可能被好几个 key 共用，但在这里不是问题：表是不可变的，表删了过滤器跟着扔。还有个语义上的亲戚，distance-sensitive Bloom filter（LSH hash 加布隆位），承诺“集合里肯定没有语义相近的东西”，但实践中漏判确实会出现，消灭漏判的变种存储随半径指数涨，所以很少人用。精确的存在判断走经典布隆，语义找邻居走向量索引。

Transfer。 跟 wal 是同一笔套利：顺序赢过随机；跟 b-tree 是对位关系，LSM 就是来替 B-tree 原地改那笔账换付法的。nosql 宽列库是头号用户，columnar-storage 跟它是同一个不可变块加合并的哲学。

Kin。 b-tree、wal、nosql、columnar-storage

给 agent 的检查清单。读完本节点，按每一条去验一个存储系统，验出结果要带证据。

写路径顺序：先 WAL，再 memtable，再刷成新文件；任何写都不动旧文件。
读顺序：memtable，再从新往旧查 SSTable，找到就停；读数据块之前先过布隆过滤器。
布隆语义：说没有就是没有，说有就是可能有；误判率和每个 key 几个位要写明。
删除：有 tombstone，读到就停，合并时确认盖住旧版了才清。
合并策略写明是 leveling 还是 tiering，以及它压的是哪个放大。
选型规矩用上：写重还是点查重，拿负载的数字说话。
刹车线：L0 文件数和待合并字节数的上限写明，先变慢再停下的行为写明。
快照门：还有快照能看到的版本不能清。
MANIFEST 顺序：先写 edit 再删旧文件；edit 没写之前崩溃，旧文件集还有效。