问题由来
最近在梳理业务中所使用的存储时脑子里突然冒出一个问题：为什么大部分 NewSQL 的践行者们在选择底层的存储模型时不约而同的选择了 LSM-Tree？在数据存储领域除了 LSM-Tree 之外另一个常用的存储模型就是 B-Tree（这里将 B+Tree 看做是 B-Tree 的一种），相比于 B-Tree，LSM-Tree 有哪些优劣之处？
什么是 NewSQL，它要解决的问题是什么
要回答这个问题首先要弄清楚什么是 NewSQL 以及它要解决的问题是什么。在Matthew Aslett 2011 年的一篇论文中第一次提出 NewSQL 的概念，它用来指代提供类似 NoSQL 高吞吐、高可用支持，同时仍然保持 ACID 特性的新一代数据库系统。旨在解决传统关系型数据库在大规模数据处理、高并发和分布式环境下的性能瓶颈。与 NoSQL 一样都是为了解决传统关系数据库的瓶颈问题，但NewSQL更注重于保持数据的一致性和可靠性，而NoSQL则更注重于可扩展性和高性能。
从上述描述可以看出 NewSQL 所要解决的问题之一就是高并发下的性能瓶颈，对于关系型数据库的高并发读取业内已经有比较成熟的解决方案，而在数据写入上需要寻找更好的解决方案。
明白了 NewSQL 的核心目标后，我们接下来将深入探讨 LSM-Tree 的特性以及它如何成为解决高并发写入瓶颈的关键。至于分布式场景下的一些其他问题，例如：分布式事务、全局时间戳、高可用等问题就不在本次讨论的范围之内
LSM-Tree 的写入优势
写友好可以说是 LSM-Tree 身上最明显的一个标签，我们通过一张关于 LSM-Tree 经典的图来看看在写入过程中都做了哪些操作，并跟 B-Tree 做个对比：
LSM-Tree 和 B-Tree 的数据写入过程对比
第一步：写 WAL 日志
WAL(Write Ahead Log)日志在各类数据库中都存在，只是名字有所不同，例如：InnoDB 中的Redo Log。他们作用都是一样：为数据库提供 crash-safe 的能力，在数据库宕机之后通过该日志可以保证数据的恢复。
通过WAL的名字可以看出该日志是以顺序写入的方式不断追加，因此 LSM-Tree 和 B-Tree 在这一步中性能开销是比较接近的。
第二步：树结构操作
在这一步中 LSM-Tree 主要是将数据写入 Memtable 中，而 B-Tree 是要将数据插入到合适的位置。这一步成为了二者在数据写入方面性能差异的关键：
首先数据的写入都是内存操作，有 WAL 的加持两种存储结构都不需要数据落入磁盘之后才算写入成功
LSM-Tree 可以看做是在内存中进行顺序追加，而 B-Tree 则是从索引根节点开始找到记录行应该存储的数据页，写入该数据。如果在此过程中任何页不在缓存中则需要发生磁盘 IO 操作，如果发生页分裂则可能会产生更多的磁盘 IO。由此来看 B-Tree 的维护就慢了，尽管像 MySQL 等数据库通过 buffer pool 的方式来减少磁盘的 IO 但整体而言其速度还是低于 LSM-Tree。其原因之一是 B-Tree 为了提升查询的速度在数据写入时便进行了数据的规整，正如一条谚语所说：如果你把东西整理的井井有条，下次就不用查找了。但也因此降低了写入性能。
原地更新于异位更新间的差别。原地更新是指直接覆盖旧记录来存储新更新，例如：B-Tree，但因为更新通常会带来随机 IO 因此牺牲了写入的性能，而且可以发现 B-Tree 实际是一种读后写。异位更新是指总是将更新存储到新的位置而不是覆盖旧的条目，例如LSM-Tree，它通过顺序 IO 操作来提升了写入的性能。
通过上面的分析可以看出 LSM-Tree 在写入方面存在一定的优势，但同时细心的你也会发现一些问题，这些问题也会成为技术选型过程中的一些担忧点：
异位更新会导致同一条数据存在多个文件中的任意一个或多个，获取数据时需要读取多个地方，读取性能是否会受到影响？
LSM-Tree 通过追加写的方式代替读后写，那么在需要对已有数据做检查才能判定能否写入/更新的场景该如何解决，性能又如何？
以上两个问题我们会在后面会继续讨论
第三步：脏数据落盘
无论是 LSM-Tree 还是 B-Tree 这一步都是异步执行，本身不会对写入性能造成太大影响。但也正因为是异步操作，所以给数据库提供性能优化空间，比如：InnoDB 的 inset merge、LSM-Tree 的 compact 等
三、关于 LSM-Tree 的读取性能
从上面的图可以看出从 read 这个方块出发的线有多条，带来的直观感受就是 LSM-Tree 的读取性能肯定不行。读多次性能肯定是受损的，但是损失有多大还需要具体来看。
首先，如果读取的数据命中 cache 或者刚写入 memtable 那么读取不涉及到磁盘操作，速度肯定是快的。
另外，前面我们说过在异步的流程中 LSM-Tree 会做数据的 compact，在 compact 的过程中除了有多版本数据去重、老数据删除等为了防止数据量不断增长的清理机制外，compact 的过程中会将多个文件中的数据按KEY排序写入新的文件中。也就是说SSTable 内部是排序的，每个 SSTable 文件中除了存放数据外还有该文件中 KEY 的起始值，以及数据对应的索引，因此即便是从文件中读取也并非是简单的按块扫描。
除此之外，每个 SSTable 中都有一个 bloom filter 用来判断要查找的 KEY 是否在文件中，避免无效的数据读取
由此看见 LSM-Tree 并未完全放弃读性能，相反在异步操作的流程里暗暗的优化读性能，通过将数据分成很多小的顺序分组并配合 bloom filter 可以快速找到数据在磁盘中的位置，大大减少磁盘 IO，在大范围的的随机查找时还可以使用 SSTable 中的索引提升查找速度。
但这并不是说 LSM-Tree 整体的读取性能要比 B-Tree 要好，而是通过一些其他的优化方法缓解读取性能的损耗，使其处于一个可接受的范围内。
四、关于读后写的问题
说完 LSM-Tree 的读性能，我们再来看下关于读后写的问题，在实际的开发过程中经常会遇到根据现有数据做逻辑运算后更新数据的情况，例如使用select value from table where id = 1 for update语句进行当前读。在这种情况下仍然要对比的是 B-Tree 和 LSM-Tree 的读取性能，而且使用该语句本身就是考虑到并发冲突，因此该数据应该是一个更新比较频繁的数据，在这种情况下 SSTable 的读取数量会比较多，一定程度上削弱了 LSM-Tree 的优势。
五、关于存储模型的思考
其实 LSM-Tree 的出现并不完，为何近些年才备受大家的关注呢？个人猜测是跟行业的发展有关，在信息科技发展初期数据产生的量小、变更少，但会被多次读取，是读远大于写，对于读友好的 B-Tree 结构刚好能够满足需求。但随着时代的发展，数据生成速度和量级远超过去，因此对于写友好的 LSM-Tree 逐步的走向更多大众的视野。
实际开发中到底是选择 B-Tree 还是 LSM-Tree 需要将业务场景代入之后进行判断，比如：你的系统数据写入规模如何，是相对稳定还是快速膨胀的？写入之后会被频繁读取吗？如果读取较少那么即便它读取时要分别读取 N 多个文件对你的系统又有什么影响呢，反正你也不怎么读它，对吧？
六、总结
回到文章最开始的那个问题，相比于 B-Tree LSM-Tree 在数据写入方面带来质的提升，并且对于近期写入数据的查询性能也有不错的表现，虽然在读性能方面受到了一定的影响，但是数据库的读写性能平衡性变得更为合理。
从某种角度讲，使用 LSM-Tree 是对数据库写入进行了一种 scale up 的提升，另外通过分布式集群等 scale out 的方式来解决读的问题总是比解决写的问题更容易，这就是 NewSQL 在解决大规模数据问题时选择 LSM-Tree 的底层逻辑。
