Coming from http://blog.sina.com.cn/s/blog_693f08470101njc7.html
今天来聊聊lsm tree，它的全称是log structured merge tree ，简单来说，lsm tree可以认为是针对传统b树在磁盘写入上低劣表现的一种优化，其核心思想的核心就是放弃部分读能力，换取写入的最大化能力。所以你可以看到几乎所有的nosql都在跟b树拼写入速度和延迟。这是为什么呢？ 看了今天的文章大家就应该能够有个比较清晰的认识了：）
要了解lsm面临并解决的问题，那么就需要先随我一起回顾两个问题:
1、磁盘的技术特性。对磁盘来说，能够最大化的发挥磁盘技术特性的使用方式是:一次性的读取或写入固定大小的一块数据，并尽可能的减少随机寻道这个操作的次数。
2、b树的写入过程。对b树的写入过程是一次原位写入的过程，主要分为两个部分，首先是查找到对应的块的位置，然后将新数据写入到刚才查找到的数据块中，然后再查找到块所对应的磁盘物理位置，将数据写入回去。当然，在内存比较充足的时候，因为b树的一部分可以被缓存在内存中，所以查找块的过程有一定概率可以在内存内完成，不过为了表述清晰，我们就假定内存很小，只够存一个b树块大小的数据吧。可以看到，在上面的模式中，需要两次随机寻道（一次查找，一次原位写），才能够完成一次数据的写入，代价还是很高的。
这就是下面了解LSM所需的必要前置知识了，可以很容易的看出，传统b树在写入的时候需要两次的随机寻道，这两次寻道会导致写入性能存在比较大的瓶颈，导致传统B树的写入效率比较低。
那么，有没有办法能够对这个bad case进行调优呢？自然而然的就会想到，如果能够减少或不进行随机寻道，不就能够自然而然的提升写入效率了么？
这就需要我们来进行一下分析，看看这些寻道主要做了什么事儿，以及如果省略了会有什么不良的影响。
第一次随机寻道的主要作用是找到那个块的数据需要被替换。
如果我们省去第一次随机寻道这个操作，那么会有以下的两个影响:
1，无法完成sql中insert类的语意，该语义要求如果待插入的数据存在就抛异常说主键冲突，如果不存在就插入。 这个操作要求先找到当前数据的最新值并进行存在性判断后才能完成插入。而如果不进行第一次查找，则这个操作是无法进行的。
2，无法保证数据块内的有序性，原因是一个数据块其实是包含了一组个数有限的有序数据的(包括待写入的数据本身)，如果没有取出待写入的目标块，那么自然就不知道要待写数据的前后都是哪些数据了。
举个例子： 开始的时候有9个数据，0，1，2|3，4，5|6，7，9。 每三个组织成一个块，也就是0，1，2组成一个块;3，4，5组成一个块；6，7，9组成一个块。 那么，对一个b树而言，如果他要写入一个数据8，他需要先取出第三个block(6，7，9)，然后判断这个block是否有足够的空间写入，发现最大只有仨位置，于是就需要进行分裂。变成俩block，然后将新的数据写入。最后写出来的样子可能类似0，1，2|3，4，5|6，7，空|8，9，空
然而，如果没有查找这个步骤，那么我们自然的就不知道8这个数的周围是哪几个数了，也就不可能进行分裂等操作了。
第二次随机寻道的作用是在内存满了的情况下，将数据刷写回到磁盘的原有位置。
当内存写满之后，我们面临的最主要问题就是如何解决刷磁盘的时候有哪些策略。
第一种策略可以叫做原位写入，也就是把数据尽可能的写回到原来的位置。 这种方式的最大好处是不会有空间的过多浪费，原来占用多大的空间，那么只要不分裂，还是占用那么多空间，没有过多的空间浪费。同时，查询也能保证是O(log2n)不会过多劣化，这个我们在队尾写的时候再进行比较。 这也是目前innodb等常见数据库在使用的B-Tree结构。
第二种模式叫做队尾写入，也就是不做原位替代，只将新写入的数据追加到整个数据的尾部。使用这种方式的好处是可以减少一次写入时的随机寻道时间，加快写入的速度，不过，这样做会有个最大的问题在于，数据的老值还存在于数据块中，这些数据也会占用额外的空间。。
例如，开始的时候有9个数据，0，1，2|3，4，5|6，7，9。 每三个组织成一个块，也就是0，1，2组成一个块;3，4，5组成一个块；6，7，9组成一个块。那么这时候要写一个数据8 ，再写个数据9'，再写个数据比如5'，在队尾写的时候，他就是很简单的直接将数据按照3个一组的方式放在队尾，那么最后数据可能类似这样： 树1:0，1，2|3，4，5|6，7，9; 树2:5'，8，9' 。
这样我们就必须处理两个问题，一个是如何读取到数据的最新值，另外一个问题在于如何解决空间额外浪费比较严重的问题。
对于数据最新值的问题，
第一种能想到的做法是每次都将内存中的树和硬盘中的树做合并后写到新的位置，并更新父节点的指针。 这种方的好处是查询可以得到很好的性能，劣势在于磁盘增删次数多了以后，会存在磁盘空洞比较严重的问题，需要在compaction的时候做好磁盘整理，同时对范围查询不友好，因为数据在多次增删之后是随机跳跃存在的，所以读取时候的随机io会变的更多。
第二种能想到的做法是分开大的有序树和小的有序树，对于上面的例子而言，我们可以认为，“0，1，2|3，4，5|6，7，9” 是一棵大的有序树，而5'，8,，9' 是一颗小的有序树。内存内也可以有一个或多个有序树的结构。这样，在每颗树的时间复杂度都是O(log2n) ，而如果写入比较重，那么存在了N个小的有序树没有合并，那么读取一个数据的时候，可以根据时间顺序倒着去多个树中依次查找，那么只要能找到数据，就一定是该数据的最新值了。
而对于空间额外浪费比较严重的问题，一般的解决方式就是再开一个线程， 利用合并排序的方式将多个小的有序数树进行合并后的追加写。 因为这个操作也是后台异步并行进行的，并且写出来的数据也是顺序有序的，所以也可以尽可能的降低磁盘的随机寻道次数。 如使用上面的例子，那么这次归并就是把 “0，1，2|3，4，5|6，7，9” 这个有序树与"5'，8,，9' " 这个有序树做归并排序，最后得到的磁盘结构类似 “树1：0，1，2|3，4，5|6，7，9;树2:5'，8，9' ;树3:0，1，2|3，4，5'|6，7，8|9'" ，然后因为树3已经合并完成并包含了树1和树2 的最新值，于是树1和树2就可以被标记为删除了，最后磁盘中留下的就是”树3:0，1，2|3，4，5'|6，7，8|9'" ，一般我们会有一个专门的英语单词来代表这个过程：compation。使用队尾追加的数据结构的人就太多了， cassandra , levelDB , hbase 等等都是使用这种结构来写入数据的，因此你会发现使用这样的数据结构的存储引擎，在写入效率上都明显的好于原位写，而读取则因为需要查找更多棵在磁盘的树而会使用更多的磁盘io.
然后把这两两次随机寻道做一次结合。就能发现几个合理的解决思路:
解1. 如果需要sql中的insert操作，那么就必须进行第一次随机寻道。
解2. 如果使用队尾写入的时候，是不需要进行第二次随机寻道的。结合解1，就可以完全的避免在写入时的随机寻道了，代价是读效率的降低或者更多的碎片问题。
解3. 针对原位写，可以进行将原来单独写回的操作变成批量写回操作。这样就可以提升顺序写的概率，从而提升写入效率。
这基本上就是目前我们能够为磁盘做的一切了：）
了解了核心思路之后，下面我们来看看我们经常看到的三个词汇的具体含义，就比较容易的可以理解了:
第一个是LSM Tree ，这个概念就是结构化合并树的意思，它的核心思路其实非常简单，就是假定内存足够大，因此不需要每次有数据更新就必须将数据写入到磁盘中，而可以先将最新的数据驻留在磁盘中，等到积累到最后多之后，再使用归并排序的方式将内存内的数据合并追加到磁盘队尾(因为所有待排序的树都是有序的，可以通过合并排序的方式快速合并到一起)。这就是LSM Tree的核心定义。
对应到上面的就是解2的所有可能性实现。
第二个概念是Merge-Dump 模型的LSM Tree， 就我目前理解而言，这个概念表述的是一种特殊的LSM tree实现，对应在LSM Tree论文里应该是 Multi-Component LSM Tree 。LSM Tree有个最大的问题就是如果合并速度比较慢，写入速度比较快，那么可能一次合并周期内用户所写入的数据会远远大于内存的大小，这样就不得不需要一个非常大的内存空间才能满足lsm tree的写入要求，这明显是不可能的。为了解决这一矛盾，能够想到的方案就是定期将内存数据直接刷写到磁盘尾部并将内存清空，这样就可以保证数据以磁盘最大吞吐量写入而不会出现内存溢出的情况。 并且可以让合并操作异步化，从而让写入更平滑。代价则是在查询时会消耗更多的随机io查询。
对应到上面就是解2的一个特例。
第三个概念就是SSTable. 就我目前理解而言，这个概念表述的是一种特殊的Merge-Dump模型的LSM Tree , 关键特征是key是按照字典序排好的”字符串“的merge-dump树:)。
也对应上面的解2特例的一个特例。
第四个概念是传统b树，
一般来说传统b树的优化策略是解3，也就是原位更新，使用分裂合并的策略来完成数据数据在磁盘上的扩展。
对应上面策略中的解3.
了解了核心概念，我们再分别针对几个标志性的场景做一下扩展性分析。
首先回答的一个问题是为什么原位的存储结构，例如innodb，会在写入删除多次之后性能下降呢？
在大家经常能够看到的性能指标中，都会看到innodb这类原位写的磁盘存储结构会在使用一段时间以后出现效率下降的问题，而hbase/cassandra 等所使用的sstable则不会出现这类的下降，那么自然就会有个疑问，这是为什么呢？ 其实原因不复杂，核心的问题在于磁盘空洞，在多次写入之后，数据在磁盘上可能是类似这样的 ”0，1，2|空洞|8，9，11|空洞|4，5，6|"，虽然在逻辑上，B树是个有序的树状结构，但是在实际磁盘上数据却是按照块组织的， 在进行分裂的时候，会从空池中找出一个能放下数据的块，然后就进行写入，这样如果经过多次写入擦除轮回之后，可进行连续写入的空间就会变的很少，于是就会导致一些看起来是顺序写的过程，在磁盘上变成了随机写。从而导致了写入性能的下降。需要做后台数据整理，把空闲块变得更连续，才有可能再次提升写入性能。
第二个问题是针对Merge-Dump结构的存储结构，是不是读取都是烂的没法要了？
这个问题的答案是否定的，因为虽然因为是队尾追加小树，所以要找到数据的最新值的时候，读取的时间复杂度从原来的O(log2n)变成了O(N*log2n) ,效率直线下降了很多，不过我们仍然有很多方式来对读取进行一些优化，让这件事变得没有那么的夸张。
那么为了能够提升读取效率，可以考虑去做的事情有以下几个：
第一件事就是一个设计良好的数据缓存系统，在大部分情况下，如果你的查询能够命中缓存，那么将在内存以O(log2n)即可命中并返回数据。在目前内存越来越大的机器上而言，这是一个最直接而简单的提升Merge-Dump结构的读取效率的方式。
第二件事是一个设计良好的compaction实现，这其实才是Merge-Dump数据结构写入效率的关键，因为在大部分情况下，compaction过程会与写入线程争抢磁盘的io资源，如果两个事情同时进行，甚至还会额外的增加随机io次数。因此，如何能够平衡和高效的完成磁盘compaction的过程，是一个存储引擎实现好坏的关键。另外的一个关键的问题是在什么时候触发compaction. 触发的时间早了，会造成资源争抢，而触发的时间晚了。会造成大量磁盘空间的浪费，目前主流的实现中，基本上都会以sstable的个数或者时间点作为触发条件。各位可以按照自己的实际需要进行配置，以达到最佳的处理效果。
第三件事就是可以考虑增加bloom-filter来提升查找效率，我在这里只说bloom-filter能做到的事情和具体举一个例子，不展开具体实现方式，各位感兴趣可以自行查询。bloom-filter在这里的作用在于能够以O(1)的效率判断一个待查的数据是否在一个小树中。 那么在一大堆小树中，我们要查找某个数据是否在某个小树中，只需要以O(N)的效率遍历这些小树就可以快速的找到这个数据具体在哪个树中，比使用O(N*log2n)的查找效率就快了不少，代价是额外的写入时cpu消耗，以及额外的一些空间。
第三个问题是，是不是用了Merge-Dump模型的LSM Tree实现的存储结构实现的数据库，效率就一定会有很大的提升了？
是，也不是
首先，假定没有任何其他优化，那么使用Merge-Dump模型的LSM Tree实现的数据库的在实现"insert"这个语义的时候，也是需要一次随机寻道来判断“数据是否存在”的， 这额外增加了成本。所以你会发现NoSQL里面默认提供的语义是put ， 也就是无论数据是否存在，都将数据以覆盖写入的方式写入到存储中，这种方式是针对merge-dump而言消耗最小的写入模式。
其次，数据库中还有一块比较重的逻辑在事务关系，也就是以MVCC的方式保证针对一条或多条数据的多次更新能够保持一个统一而一致的用户状态。 这会额外的增加一些开销，从而降低了系统的整体性能。
最后一个问题是：我应该选择哪个？
答案还是选合适的。没有一种数据结构能够包打天下，Merge-Dump类的数据结构（如sstable)，优势在写入速度快，劣势在读取消耗资源大。而原位写的数据结构，如innodb类的结构，优势在于读写比较平衡，尤其对于读取有比较大的优化。
就阿里集团的实际使用经验来说，如果你日常的写入与读取操作的比率小于1:2，那么选择写优化的存储结构是非常合适的。而如果超过这个阈值，那么选择面向读取优化的数据结构是最为合适的。
做一下简单的小结，LSM Tree和传统B树最大的区别就在于数据合并的策略，是采用原位替换的模式，还是采用合并追加到队尾的方式来进行数据合并。采用追加队尾的方式，对于磁盘写入来说会有极大的性能提升，代价一般是读取效率的降低。而对于传统B树来说，读取和写入则更为平衡，适合一般性场景，不适合写入读取比率比较高的场景。
最后，还是老规矩，让我们以综合评价作为本篇的结束。
1.是否支持范围查找
因为是有序结构，所以能够很好的支持范围查找。
2.集合是否能够随着数据的增长而自动扩展
可以，与Btree的方式一致
3.读写性能如何
对于写入来说，Merge-Dump类的数据结构能够尽可能的减少写入时的磁盘寻道次数，所以写入能够到达磁盘吞吐量的上限，写入比较平稳，而原位写的数据结构则会存在磁盘空洞问题，导致写入性能有一定下降。
对于读取来说，Merge-Dump不占优势，当然因为有cache和compaction ，所以效率不会下降很多，但是因为每次读取需要与写入线程争用磁盘随机寻道次数，所以他们之间也会相互影响，从而降低性能。
对于原位写的数据结构来说，查询的效率能够做到固定的随机寻道次数，比较理想。
4.是否面向磁盘结构
一般来说，在有内存的情况下，root层和branch里面的一部分都会被缓存在内存中，所以如果树的高度是三层，那么前两层一般都会被缓存在内存中，所以查询基本上只需要一次随机寻道时间，是一个面向磁盘的结构
5.并行指标
对于LSM类数据结构来说，并行指标主要由两个部分组成，第一个部分是内存中树的并行指标，第二个是在磁盘中树的并行指标。
以目前主流的实现而言，都可以做到比较好的并行。
6.内存占用
这个主要看在内存中选择了哪个数据结构，以及在内存中维持了几个小树，小树越多，那么内存额外消耗的就多，而如果内存中小树比较少，那么内存中的消耗就少。