LSM

B 树会在行所在的那一页上就地更新，于是「键随机到达」的写入模式就变成了「页随机写」的模式。LSM 树拒绝这笔交易：它只追加，把重写留到后面成批去做。这套设计里的其他部分——内存表、布隆过滤器、压实策略——全都从这一个拒绝里推出来。 支撑它的测量很容易复现。在同一张 20 万行的 sqlite 表上做同样 20 万次就地更新，配 2 MB 页缓存和一次持久提交：键按顺序到达时耗时 0.17 秒，打乱顺序到达时 2.60 秒——行完全一样、页数完全一样，差了 15.25 倍。多出来的时间花在散落的页重写，以及由此引发的缓存淘汰上。 先缓冲，再刷盘，再合并 写入先进预写日志保证持久性，再进内存表保证速度。内存表满了就作为一段不可变的有序段刷到磁盘；在 RocksDB 里这一段落在 level 0，而它下面的每一层只保存一段有序数据，且尺寸目标按指数增长。于是键层面随机的负载，落到磁盘上就变成了完全顺序的负载，无论应用在做什么，写路径都是一次大块的有序追加。 账单在读取路径上付。一次点查要考虑每一层，所以引擎给每段配了布隆过滤器，用来廉价地回答「不在这里」。在一次 40 万次写入、6 万个不同键的模拟里，2 万次点查平均探了 8.9 个段，但真正去读的只有 0.6 个：布隆过滤器在 177937 次探测里否掉了 166622 次，占 93.6%。查不存在的键时仍然要探 11.0 个段才能返回空——布隆过滤器让「未命中」变便宜，对「命中」则毫无帮助。 压实就是代价 写路径之所以便宜，是因为从来不做就地更新；代价是每个逻辑值都会被写不止一次。同一份模拟里，56000000 字节的逻辑数据变成了 149031040 字节的物理写入，来自 54 次刷盘和 4 次压实——写放大 2.66 倍，而且这还是在刻意放宽了压实预算的情况下。 ...