丝析发解丨LSM树原理

图书馆每天都有很多用户借书、还书，图书馆里有两类管理员：勤快的，懒惰的。

勤快管理员的方法是：有人来还书时，立即把这本书放到了正确的书架上。有人来借书的时候，他径直走到放这本书的书架前，直接把书取出来。

懒惰管理员的做法不一样。有人来还书时，他把书先堆到自己的办公桌上。下午五点钟的时候，他统一处理办公桌上今天的还书，把他们分门别类排序，然后放到正确的书架上。当有人来借书的时候，他先在自己办公桌的书堆里找，如果找不到，再去对应的书架上找。

如果把数据库看作一个图书馆，B+树就像一个勤快管理员，它总是为新写入的记录找到唯一的正确位置来存放，查找这个记录的时候，只到这个唯一正确位置找就行了。

B+树

LSM树就是一个懒惰管理员，新写入的记录暂时存放到内存里。内存里面新记录数量足够多的时候，再把这些记录统一刷写到硬盘上的数据文件中上去。

实际上，LSM树并不是把内存中的新记录逐个插入到硬盘原有的数据文件中。LSM树先把内存中的记录排序，然后把硬盘上原有的数据文件中的记录读入内存，与内存中新记录合并，然后再一并写入硬盘上的一个新数据文件中。这样做的好处是：（1）读写文件都是顺序IO，没有随机IO。（2）因为不修改已经存在的文件，处理流程简单很多，例如：不需要加锁。

对LSM树来说，如果内存很小（1GB），但硬盘上数据文件很大（100TB），性能就会很差。因为每次合并都需要把一个大文件的内容全部读出来，合并了很少一点内容之后，再全部写回硬盘。硬盘IO和CPU处理能力都用于读写早已存在的内容，这会影响新写入性能和查询性能。解决这个问题的一个方法是“分层合并”（leveling merge policy），在硬盘上有多个排序的数据文件，尺寸不同，从小到大依次合并。例如：1GB内存作为L0层，一个10GB的硬盘文件作为L1层，一个100GB的硬盘文件作为L2，1TB为L3层，…，1000TB为L6层。这样当内存中数据记录满了1GB的时候，这个1GB数据只合并到L1层，此时需要读写的旧数据不超过10GB。当L1层满了10GB的时候，合并到L2层，……。也许这就是LevelDB名字的由来。

多层LSM树解决了对原有数据读写多次的问题，但是带来新问题：查找速度慢。因为要查找一条记录，需要先在内存（L0层）中找，如果找不到再到L1层找，然后再找L2层，…，直到找到为止，这就需要很多次硬盘IO，查找速度当然就慢了。于是有人想到了使用布隆过滤器（Bloom Filter）来帮助缓解查找速度慢的问题，具体来说，就是在每个数据文件中存一个布隆过滤器，它占用空间不大，可以用来快速判断某个记录在这个数据文件中是否存在，如果不存在，就不用继续查找了。但是这个办法只能用来解决点查询的问题，对范围查询的效果不好。

总结一下，与B+树相比LSM树的优势是：写入速度快。因为不需要为每个记录都找到硬盘上对应的位置，写入新记录的不需要随机IO，定期合并操作也只有顺序IO。LSM树的缺点也很多：（1）查找速度慢。因为一次查找操作可能需要先在内存里面找，找不到再到硬盘上去找。如果是多层的LSM树，那么在硬盘上可能需要查找多个数据文件。（2）空间放大，LSM在硬盘上有很多层数据文件，当更新比较多的时候，这些文件中就会有大量key相同的数据记录。合并过程中也会出现有两份相同数据同时存在的情况。（3）读写放大，因为存在多次合并的过程中，所以就会对一个数据记录多次读写，而B+树只会读写一次。（4）后台的合并任务导致前台操作（put/get/del）响应时间不稳定。

LSM树的这些缺点并不总是成立的，只有在一定条件下才成立的。例如，B+树也有读写放大，因为B+树更新一个很小的记录（加入16Byte）也至少需要读写一个8KB的页面，这个读写放大就8192/16 = 512倍。如果某个应用随机更新特别多，记录尺寸又很小，那么B+树的读写放大就比LSM树更严重。

1996年LSM树出现之后，人们对它做了很多改进，目前最常见的两个改进是：（1）用多级结构来缓解写放大；（2）用布隆过滤器来提高点查询速度。

上面是LSM树的简单发展历史，现在还发展之中。最近一个值得关注的对LSM树的改进是WiscKey。它的主要思路是把原始数据的value写到一个append-only的文件中，把二元组（key, offset）放到LSM树上，这样就减小了LSM树的大小，这样读写放大、空间放大就都减小了。查询速度也提高，因为数据文件的尺寸小了，所需IO数量也就少了。这个改进也不是免费的，当很多记录被删除（或者被更新）之后，需要对这个append-only文件进行垃圾搜集（GC），这是一个实现特别复杂并且IO开销很大的操作。TiKV(https://docs.pingcap.com/zh/tidb/stable/tikv-overview)和Badger(https://dgraph.io/badger)就实现了这个优化。

作者简介

黄岩，云和恩墨分布式存储软件总架构师，十余年存储研发经验，在NAS和备份领域有深入钻研，曾担任某NAS产品性能SE，负责产品性能调优工作，该产品在2011年打破了SPESsfs性能测试世界纪录。

「墨读时刻」特别节目黄岩人物专访即将上线，听一位存储老兵讲述摸爬滚打的这些年和对未来自研存储的洞察，敬请期待... ...

数据驱动，成就未来，云和恩墨，不负所托！

---

云和恩墨创立于2011年，以“数据驱动，成就未来”为使命，是智能的数据技术提供商。我们致力于将数据技术带给每个行业、每个组织、每个人，构建数据驱动的智能未来。

云和恩墨在数据承载（分布式存储、数据持续保护）、管理（数据库基础软件、数据库云管平台、数据技术服务）、加工（应用开发质量管控、数据模型管控、数字化转型咨询）和应用（数据服务化管理平台、数据智能分析处理、隐私计算）等领域为各个组织提供可信赖的产品、服务和解决方案，围绕用户需求，持续为客户创造价值，激发数据潜能，为成就未来敏捷高效的数字世界而不懈努力。