概要
本文是对 ben stopford 个人网站上对于 LSM tree 的博客的翻译，用于自己加强学习印象和理解深度，这里是原版博客。
注：里面有一些链接已经失效，我自己有更改过。
Log Structured Merge Trees
自 Google 推出 “Bigtable” 已经接近10年的时间了(文章于2015年2月14号所写)，它所特别的地方是采用了一种文件组织方法。这种方法被称之为日志结构合并树。日志结构合并树的文章发表于1996年，尽管它所描述的方法与现实中工程实现采用的方法有很大的不同。
LSM 作为核心的文件组织方法现在已经被应用到大量的产品中。HBase、Cassandra、LevelDB、SQLite，甚至 MongoDB 3.0 版本在收购 Wired Tiger 引擎之后都是由 LSM 算法驱动的。
LSM trees 的有趣之处就在于它背离了二进制风格的文件组织方式。当你第一次接触 LSM trees 的时候，它多少会看起来有点违背你的直觉，但当你更加深入的去思考它是怎么在模型和存储系统中工作的，你就会明白它为什么要这么设计。
一些背景
总的来说 LSM trees 被设计用来提供比传统的 B+tree 或 ISAM 方法更加良好的写的效率，这是通过移除更新分散数据的需求实现的。
所以这为什是一个好的方法？这归结于一个古老的问题：磁盘在处理顺序访问的速率往往要比处理随机访问的速率快很多。不管磁盘是固态硬盘还是机械磁盘，不管对于多小的主存，这两个速率的差距还是很大的。
在ACM的这个报告中的数据就证明了这一点。他们有点与直觉相背离地展示出磁盘的顺序访问比主存的随机访问还要快。同时还证明了对于机械磁盘或者固态硬盘，顺序访问比随机的IO至少快三个数量级。这意味着需要避免随机操作，而顺序的访问更值得被设计。
因此，基于这一点，我们考虑以下的思考实验：如果我们注重写的吞吐量，那么什么方法是最好的呢？一个很好的出发点是简单的对于文件延展数据。这种方法（通常被称作日志或者堆文件）是完全顺序的，所以它提供了非常快的写性能，这大概和理论的磁盘速率相等（通常为200-300M／s）。
由于既简单又高效，因此基于日志的方法理所当然的在很多的大数据工具中流行开来。但他们有明显的缺点。在日志中读取随机的数据比写入更加费时，这需要反时间顺序扫描，直到需要的 key 被找到。
这意味着日志只是适合于简单的工作，如数据已经完全可以访问的时候，如先写日志的数据库或者有已知偏移量，像简单的信息产品 Kafka 一样。
所以我们除了日志以外，我们需要一些别的方法去提高在如基于键的访问或者范围查找这样更加复杂的读取工作中的性能。总的来说这里有4种方法能帮助我们：二分查找、哈希、B+ 或者外部的文件。
1.搜索排序文件：存储数据到一个文件，并通过key来排序。数据被定义了宽度的时候使用二分查找，没有定义宽度的时候使用页索引+扫描。
2.Hash：通过哈希函数将数据拆分，之后能通过这个哈希函数直指向数据。
3.B+：使用可以导航的文件组织方式，如 B+tree 或者 ISAM 等。
4.外部文件：将数据存储成日志／堆，并创建一个单独的 hash 或者树索引用于找到数据。
所有的这些方法都能显著的提高读的性能（大多情况下 n->O(log(n)）。显然这些结构增加了顺序，然而顺序又阻碍了写的性能，所以我们的高速的日志处理方法似乎行不通。我猜你达不到你想要的效果。
很容易发现上面这四种方法都对数据的整体结构强加了约束。
数据被有意地储存在文件系统中特别的地方以方便我们使用索引快速找到它们。正是这些结构使得导航得以快速进行。也正是这些我们在写入时候需要遵循的结构，才会增加磁盘的随机访问所以降低了写的性能。
这里有几个具体问题，每次写都需要两次IO，一个去读取页一个写入数据。但是使用日志的时候不会这样，它只需要一次IO就能完成。
更糟的是，现在我们还需要去更新哈希或者B+的结构。这就是我们要对文件系统的特殊部分进行更新。而大家也知道这样的更新需要速率很慢的随机IO。这里有一点很重要：像这种很分散的更新方法是很局限的。
一种常用的解决方式是将索引也存储在日志中，让后将日志保存在内存中。例如，一个哈希表能够用来映射 key 到在日志中最新value 的位置（偏移量）。这种方法在处理相对较小的数据的IO下非常有效，比如储存在内存中，用来映射偏移量的key。这样我们查找一个值的时候就只需要一次IO。
但另一方面这会带来一些扩展性的限制，特别是当你有很多小的value，并且这些value只是一些简单的数字的时候，那么索引将会大于数据文件本身。尽管很多产品，如 Riak、Oracle Coherence 已经明智的接受了这些限制。
所以这就引出了Log Structured Merge Trees。LSMs 定义了一种与上面四个方法不一样的方法。它可以完全以磁盘为中心，只需要一点点的内存来提高效率，同时使用一个简单的日志文件来提高写的性能。
本质上来讲它使磁盘尽可能的产生顺序访问，而不是如上面所说的分散的随机访问。
存在许多不需要更新的树的结构，最流行的是只追加B树（ append-only Btree），也被称之为 copy-on-wirte 树。他们通过覆盖树的结构来工作，每次写操作发生的时候他们就顺序的在文件的最后追加覆盖。相关部分的树结构，包括最顶层的节点都会被遗弃。通过这种方法，这就避免了更新操作因为经过时间的推移，树会重新定义自己。然而这种方法是有代价的：每次写入的时候都要重写数据结构是很冗余的操作，会产生很多的写入放大，这也是它的一个缺点。
基本 LSM 算法
从概念上讲，基本 LSM 算法很简单。批量写入被顺序地保存到一组较小的索引文件而不是一个很大的索引结构（将会使文件系统内部分散或者增加写入放大）。所以每一个文件都包含一小段时间的变化。在写入后每一个文件都被排序，所以在之后查找的时候会快很多。文件是不可变的，它们也从不更新。新的更新将会被写入新的文件。读取检查所有的文件，并定期将文件合并从而减少文件的数量。
让我们更加深入的去看看这一个过程。当更新到来时候，将更新储存在内存缓冲区，为了保持 key 的顺序通常采用树的结构储存（如红-黑树等）。在大多数实现中，这个“memtable”在磁盘上作为预写日志被复制，仅用于恢复。当 memtable 装满了之后排序的数据会被刷新到磁盘上。这个过程在越来越多的写入操作到来时反复执行。重要的是，当文件不被编辑的情况下系统只执行顺序的 IO。新的写入或者编辑只是简单的创建新的连续的文件（见上图）。
所以当越来越多的数据进入系统的时候，越来越多的不可变的、排序的文件将会被创建。它们每一个都相当于一个小的、按时间排序的变化子集，并且是有序的。
因为旧的文件没有更新，所以需要创建一些重复的条目来取代先前的记录（或者删除标记）。这在最初会产生一些冗余。
系统定期执行压缩。这个压缩过程会选择一些文件进行合并，并删除所有重复的更新操作或者删除操作（至于具体是怎么工作的我们下面再说）。这不仅对减少冗余有重要的意义，更重要的是，当文件数量越来越多的时候这对写入性能是有帮助的。并且，由于文件是有序的，所以在执行合并文件的过程是非常高效的。
当请求读的操作时候，系统首先检查内存缓冲区，如果找不到 key那么将会按照时间顺序逐个检查文件，直到 key 被找到。每一个文件都按照顺序以便于导航。但是由于每个文件都要检查，所以读的速率会随着文件数量的增加变得越来越慢。这就是问题所在。
所以在 LSM trees 中读的速率是比其他多路查找树要慢的。幸运的是，这里有一些小技巧能提高性能。最常用的方式是在内存缓冲区中存入一个页索引。这就相当于提供了一个方便你查找到你的目标 key 的参照表。你在扫描的时候就像数据是排序的一样。 LevelDB , RocksDB 和 BigTable 通过在每个文件的末尾加入一个块索引来实现这个方法。因为允许使用可变长字段，同时又适合于数据压缩，所以这通常比直接二进制搜索要好。
即使使用每个文件的索引，读取速度依然会随着文件的增加而变慢。所以周期性的文件合并检查是很重要的，这可以使文件数量不会太多，同时读取将会更加高效并维持在可接受的范围内。
即使经过了压缩，读取的时候仍然要访问许多文件。大多数实现中通过 Bloom filter / Bloom filter - 简书 来解决这个问题。Bloom filter 是一种高效判断 key 是否在一个文件中的内存方法。
所以从写的角度来看，所有的写入操作只能以连续的形式批量写入。反复的文件合并会带来额外的周期性的IO开销。然而在寻找单一行的时候读取操作还是有可能需要访问大量的文件（读取的时候是分散的）。这只是算法的工作方式，我们在随机IO上进行随机IO写操作。如果我们使用像 bloom filter 这样的软件技巧或者大量文件缓存这样的硬件技巧来优化读取性能，那么这样的做法是很明智可行的。
基本压缩
想要保证 LSM 的读取相对较快，文件的数量的限制管理是很重要的，所以让我们更加深入的来看看文件合并这个过程。这个过程有点像垃圾回收：
当缺点数量的文件产生之后，比如说5个文件，每个文件10行，它们将被合并成为一个50行的文件（也许更小一点）。
每当10行的文件填满之后，继续将他们合并成50行的文件。
最终将会产生5个50行的文件，它们将被合并成一个250行的文件。这个过程会不断创建更大的文件。见图。
使用上述这种通用方法的问题是创建大量的文件：这些文件都必须单独读取，以便搜索结果。（至少在最糟的情况下是这样）
分级压缩
这里有一种新的实现方法，像 LevelDB, RocksDB 和 Cassandra 这些产品通过基于文件级别而不是通过基于文件大小的压缩方法解决这个问题。这减少了最糟情况发生时候需要查询文件的数量，同时减小了单个压缩的相对影响。
这种基于级别的方法与基于大小的方法有两个关键的不同：
1.每一个级别都包含许多文件，并且总体上保证里面不存在重复的关键字（key）。也就是说 key 在可用的文件中进行分区，因此在一个确定的级别（层）去寻找一个 key 的时候只用考虑一个文件。
第一级（层）是上述区别不成立的一个特例，key 可以跨越多个文件。
2.文件将被一次性合并到上一级中。当某一级满了的时候，将会从中抽取一个文件和上级的文件合并，为数据的添加腾出空间。这里与基于文件大小的方法（将几个差不多大小的文件合并成更大的一个文件）略有不同。
这些改变意味着基于等级的方法随着时间的推移会增加压缩的影响，并且会更加减少空间的占用。它同样有更良好的读性能。但是大多数工作负载下的总 IO 量都较高，这就意味着一些简单的面向写的工作负载将不会受益。
总结
因此，LSM trees 是日志方法和传统的固定索引的方法（如B+树 和 Hash 索引）的一个折中。它提供了管理一组较小的、单独索引文件的机制。
通过管理一组索引而不是单独的一个，LSM trees 将与B+ 、Hash 索引相关联的低效的随机 IO 替换成为更快的、顺序的IO。
这样的代价是在读取的时候将要定位大量的文件而不是简单的一个文件。这还有额外的压缩 IO 产生。
关于 LSM trees 的思考
所以 LSM 方法是否真的比传统的基于单一树的方法好呢？
我们已经知道 LSM 有更良好的写的性能尽管这要付出一些读的性能代价。LSM还有一些其他的好处。LSM 树创建的 SSTable（排序文件）是不变的。这就使锁的定义变得更加简单，唯一会争用资源的地方是内存中的 memtable，这与需要复杂的锁定机制来管理不同级别变化的单树形成鲜明的对比。
所以最终的问题是关于如何面向预期的工作负载来写。如果你关心写的性能那么 LSM 所能节省的成本是很可观的。大型互联网公司似乎在这个问题上毫不动摇。例如，雅虎公司报告称由于事件日志和移动数据的增加，系统工作负载从以前的主要是重视读稳步转变成为读写一致。许多传统的数据库产品看起来似乎依然更加适用于增强读取能力的结构。
和日志结构化系统一样[见脚注]，关键的争论源于越来越多的可用内存。随着更多的可用内存，读取性能自然而然通过操作系统提供的大文件缓存得以提升。写性能（不会随着内存的增加而提高）成为主要的关注点。所以换句话说，硬件的优化对于读取性能的优化比写性能的优化要好，因此选择更适用于优化写性能的文件结构是很有意义的。
当然，像 LevelDB、Cassandra 这样的 LSM 实现相较于单一树的方法提供了更加良好的写的性能。
Levelled LSM 的拓展
这里有一些在 LSM 的基础上做的一些工作。雅虎公司开发出来一个叫做 Pnuts 的系统，它结合了 LSM 和 B 树，并且表现出更良好的性能。虽然我没有看到这个算法公开可用的实现。IBM和Google也以类似的方式做了近期的工作，尽管路径不同。也有相似的方法具有相似的性质，但保留了总体结构。这包括了 Fractal Trees 和 Stratified Trees 。
当然这只是一种选择，数据库使用了许多不同的选择。越来越多的数据库为不同的工作负载提供了可以更换的数据引擎。 Parquet 是 HDFS 的一种流行的替代品，并且将其推向相反的发展方向（通过列格式的聚合性能）。MySQL有一个存储抽象，可以插入一些不同的引擎，如 Toku 的基于分形树的索引。这同样适用于 MongoDB。MongoDB 3.0 提供了支持 B+ 和 LSM 方法的 Wired Tiger 引擎。许多关系数据库都有可以配置的索引结构，他们利用不同的文件组织起来。
硬件的使用也是值得考虑的一件事，昂贵的固态磁盘，如 FusionIO，具有更好的随机写入性能，它就适合于原位置更新方法。相对便宜的 SSD 和机械磁盘更适用于 LSM 方法。LSM 避免了能消耗大量固态硬盘性能的小型随机访问。
尽管如此，LSM 方法依然是充满争议的。如垃 GC（圾回收机制），最大的问题是回收阶段对 IO 的影响。在这个黑客新闻网站上有一些有趣的讨论。
所以如果你正在看数据库产品，无论是 BDB 还是 LevelDb ，Cassandra 或
MongoDb，你都可以将他们相对性能的某个比例与他们使用的文件结构关联起来。测试似乎支持这个观点。当然，值得注意的你应该参考你所使用的系统来权衡性能。
在SSD中，每写入一个完整的512K块将会清除重写周期。因此，小的写入会导致驱动器上不合适的流失量。对块重写有固定的限制会显着影响他们的寿命。
扩展阅读
脚注：日志结构化文件系统
除了名称和侧重于写入吞吐量之外，就我所能看到的而言，LSM和日志结构化文件系统之间没有太多关系。
现在使用的常规文件系统往往是“日志记录”，例如ext3，ext4，HFS等都是基于树的方法。索引节点的固定高度的树表示目录结构，日志用于防止故障情况。在这些实现中，日志是合乎逻辑的，这意味着只有内部元数据才会被记录。这是出于性能考虑的原因。
日志结构化文件系统被广泛的用于闪存介质，因为它们的写入放大率较低。随着文件缓存开始主宰更一般情况下的读取工作负载，写入性能变得越来越重要，他们也得到了更多的关注。
在日志结构化的文件系统中，数据只写入一次，并且被直接发送到一个被按时间顺序推进的缓冲区中。缓冲区是垃圾收集区域并定期删除冗余的写入。与 LSM 一样，日志结构化文件系统的写入速度也会更快，但是读取速度要远远低于基于树的双重写入文件系统。在有大量内存可用于提供文件缓存的情况下，或者介质不能很好地处理更新的情况下，这也是可以接受的，就像闪存一样。
