Log Structured Merge Trees译文以及LSM调研心得
原文
直接看原文有些糊涂，所以翻译一下看，也为了和朋友分享一下。能力有限，所以翻译的会很蠢，求指点0.0
看完译文以后可以按照顺序浏览以下几篇博文。感觉讲的很透彻。
看完这些就循序渐进大致对leveldb有个基础了解了。如果后面工作有需要，我也会跟进一下源码分析。
译文
自从谷歌发表了他的"big table"论文以来已经过去了十年。论文中很酷的一点是他使用的文件组织方式。在1996年后，这个方式以LSM树被人所熟知（尽管并未被谷歌特别的提出）。
LSM现在被用于很多产品的主流文件组织策略。HBase,Cassandra,LevelDB,SQLite,甚至是MongoDB收购了Wired Tiger引擎后，其3.0附带了一个LSM引擎的选项。
使LSM树有趣的是他们离开二叉树风格文件组织主导的领域已经有几十年的历史了。当你第一次看到LSM，它看起来几乎是违反人类思维的，然而当你考虑到文件是如何工作在现代笨重的存储系统上一切就说得通了。
一些背景知识
简而言之，LSM树被设计来提供比传统的B+树和ISAM更好的写入性能。它通过消除随机的就地更新操作来实现这一点。
所以为什么这是一个好主意呢？其核心是磁盘的老问题：随机操作缓慢,但当顺序访问时很快。这一点分歧存在在两种不同的访问方式中间，不管磁盘是固态还是磁性材料，尽管这种影响在主存较小。
这一点在ACM的这篇报告中指明了。
他们表明的是违反直觉的，顺序操作在主存上比随机操作更快。他们也进一步表明了，在磁性或固态硬盘上，顺序操作比起随机操作快上三个数量级。这意味着随机操作应当被避免，顺序操作很值得设计。
所以记住这个考虑一个小猜想实验：如果我们对写吞吐量有兴趣，什么是最好的使用方法呢？一个好的出发点是鉴定的追加数据到文件里。这种方式经常被叫做日志，档案或者堆文件，是完全顺序化的因此能提供非常快的相当于理论硬盘速度的写性能（通常平均200-300MB/S）
受益于基于简单性和高性能的日志方法正在许多大数据工具中变的十分受欢迎。然而他们有一个很明显的缺点。从日志中读任意数据会消耗远多于写入的时间，这当中包括了反向的扫描，直到找到需要的关键字。
这意味着日志只适用于数据作为整体被访问的简单情况，例如大部分数据库的预写日志,（WAL,write-ahead logging),或者通过一个已知的偏移量来访问。简单的消息系统Kafka就是这么做的。
所以我们需要不只是日志这样的方式来高效执行更多的复杂读工作，例如基于关键字的访问或范围访问。一般来说，有四种方法在这种情况下是有用的：二分查找，哈希，B+或者外部文件。
1。二分查找：保存数据到文件的时候以关键字排序。如果数据已经确定宽度就使用二分查找，否则使用页标签+检索。？？？
2。哈希:用哈希函数把数据分片，而后可以直接访问读取
3。B+:使用文件组织如B+树，ISAM等等
4.外部文件：除数据本身按日志形式存储外，另对其单独建立索引加速读取。
所有的这些方式显著的提升了读性能（大部分是n->O(log(n))复杂度的）。可这些结构加入了顺序，而这些顺序阻碍了写入性能。所以我们的高速日志文件方式被放弃了。？？？鱼和熊掌不能兼得。
值得注意的是，上述四个选项利用了数据的某种总体结构。
数据被谨慎和特殊设计后放在文件系统上以便于能迅速的再次访问到。这种结构使得访问很迅速。这样的结构在写入数据后是很好的。我们开始通过增加磁盘随机访问来开始减少写性能。
有几个具体问题。对每次写都有两次IO要求,一次是读页面一次是写回这个页面。这不是我们的日志文件方式可以胜任的情况。
更糟的是，当我们需要更新哈希或者B+索引结构时，这意味着更新文件系统的特定部分。已知的例如就地更新操作需要缓慢的随机IO。有一点很重要：在文件系统执行的就地更新像机关枪一样多。这是瓶颈。
一个常见的解决方法是使用方法四对日志建立索引，然而把索引保存在内存中。例如一个哈希表能用日志文件的最后一个值的位移量来映射关键字。这种方法的确很好用，他把随机IO划分成为较小的段，然后在内存中去取键-位移量的映射。查找一个值就只需要在磁盘做一次IO了。
然而另一方面这种方法存在扩展性限制，特别是当你有很多小值，如果你的值只是一些简单的数字，那么索引将比数据文件本身还大。从Riak到Oracle Coherence的很多产品已经对这个缺陷妥协了。
所以这给我们带来了LSM树。LSM树带来了以上四种方法不同的方式。他能成为磁盘的中枢，只需要内存空间一点地方来提高效率，但是也使用了一个简单的日志文件来保证写入性能。一个缺陷是他的读性能比起B+树来说还是稍微弱了些。
本质上它尽可能的使磁盘顺序访问。这里再也没有机枪访问啦！
许多不需要就地更新操作的树存在着。最受欢迎的就是append-only Btree，也被叫做copy-on-write树。它通过每次写操作顺序的发生在文件末尾来覆盖原先的树结构。包括顶节点在内的老的树结构的一部分成为孤儿节点。尽管这种方式避免了以树的结构依次的重新构造本身，然而这样的操作本身存在成本。重写这些结构的每次写是冗长的，他的缺点是带来了大量的写操作。
基础的LSM算法
概念上LSM树是非常简单的，不同于有一个大的索引结构来存下批量的写操作（像机关枪一样在磁盘中扫描或者增加大量的写操作）。它顺序的，写入到一系列的更小的所有文件中。所以每个文件包含了一批在一段短时间内的变化。每个文件在被写入前都被排序以便于稍微快速的检索。这些文件都是不变的；他们从来不更新。每次更新都写入新的文件。会检查所有文件来定期合并，以降低文件的数量。
让我们看看一些细节吧。当更新到达时，他们被添加到一个内存缓冲区，通常是作为一棵树（红黑等等）来保证键值顺序。这“内存表”在大部分实现里以预写日志（WAL）的方式复制到磁盘中，以用作恢复。当排序的数据充满了内存表，会被刷入硬盘的一个新文件。这样的过程随着越来越多的写入不断重复着。重要的,文件无法被编辑,所以系统只做顺序IO。新的条目或者简单的编辑会建立新的文件（如图）。
随着越来越多的数据进入系统，越来越多的不可变的有序文件被创建。每个代表了一段时间内数据变化的排序集合。
旧文件不会去更新重复的条目来取代先前的记录（或被删除的记录）。所以开始出现了一些冗余。
系统定期的执行压缩操作。压缩操作把很多文件合并起来，消除其中重复的更新或者删除操作（更多的是当第一步操作完成以后）。这对于消除上面提到的冗余问题非常重要，但是更重要的是，通过减少文件的增长量来保证读操作的性能。值得庆幸的是,由于文件被排序了,所以合并文件的过程是相当高效的。
当请求读操作时，系统首先检查缓冲区（内存表）。如果这些关键字没找到，那么会一个接着一个反序检查一系列磁盘文件，直到关键字被找到。每个文件都被顺序排列所以很容易遍历，然而当文件越来越多的时候，会变得越来越慢，这是因为需要检查每一个文件。这是一个问题。
所以光看读性能，LSM比他的就地修改的同胞们慢一些。幸运的是有一些技巧可以提高性能。最常见的方法是在内存建立页索引，这提供了一个让你更接近目标关键字的查找。你在内存中的检索数据是被排序过了的。LevelDB，RocksDB和BigTable对每个文件的末尾做块索引来实现这一点。这通常比直接二分搜索好一些，因为他允许可变长字段的用户以及更适合压缩过后的数据。
即使是每个文件被索引了，读操作依然会随着文件的增长而变的缓慢。读操作被定期的合并文件来保证性能。这些合帮操作控制了文件的数量，使得读性能在一个可接受的范围内。
即使有压缩操作，读操作依然会访问多个文件。大部分实现通过布隆解析器(Bloom filter)来避免这一点。布隆解析器是一个使用内存判断文件是否包含一个关键字的有效方法。
所以从写的角度来看，所有的写操作被成批的写入连续的块中。并且存在一个额外的，周期性的压缩合并操作。然而读操作在寻找单个数据时有可能接触大量的文件（也就是机枪读法）。这是简单算法的工作方式。我们以随机写来交换随机读。如果我们能使用软件技巧如布隆解析器或者硬件技巧如大文件缓存来优化读取性能，这样的交换是明智的。
基本压缩法
控制文件的数量来保证LSM读取的相对较快是很重要的，所以让我们更加深入了解压缩方法。这过程有点像分代的垃圾收集：
当创建一定数量的文件，比如说5个文件，每个有10行，他们合并成一个单独的50行文件（或者稍微少些）。
这样的过程随着10行的文件被创建而不断进行着。这些文件每5个文件填满后合并成50行文件。
最终有5个50行文件。此时5个50行文件合帮成一个250行文件。这个过程将持续着创建越来越大的文件。如图：
这种方法的所带来的上述问题是大量的文件会被创建：为了获取最终的结果所有文件都必须被遍历搜索（至少在最坏的情况下）。
分级压缩法
更加新潮的实现，例如在LevelDB，RocksDB和Cassandra中，通过实现分级而不是大小来解决这个问题。这减少了最差情况下大量文件的读取，同样减少了单个压缩的（对整个数据集的）相对冲击。
这种分级法比起基本方法有以下两个不同的关键点：
1 每一层能包含大量的有保证的文件，作为一个整体，不会操作重复的关键字。也就是说关键字被分片在可用的文件中。因此在某个层级寻找一个关键字只需要查询一个文件。
第一级是一个以上性质不存在的特例。关键字可以跨不同的文件中。
2 文件一次被合并成高层级的一个文件。当一层满了，一个文件会从上抽离，并且合并进入上一级来创建加入更多数据的空间。这比起基本方法中，把相似大小的文件合并成一个单独的较大文件，略有些不同。
这些变化意味着基于层级的方法随着时间的推移来遍及压缩的影响，需要更少的整体空间。他也有更好的读性能。然而大部分的工作负载的IO会变高，这意味着对一些更简单的以写为目的的工作情况，并没有帮助。
总结
所以LSM树在日志文件方法和例如B+或者哈希索引这样的传统的单索引方法之间取得了均衡。他提供了一种机制来管理一组更小的独立索引文件。
通过管理一组索引而不是单独一个，LSM方法把与B+或哈希索引中开销较大的随机IO替换为了快速的顺序IO。
读操作不得不处理大量的索引文件而不只是一个，是这样的改变需要付出的代价。同时也增加了压缩操作的IO成本。
如果讲的还不是很清楚，那么这里有不错的描述:
leveled-compaction-in-apache-cassandra
LSM方法的思考
所以是否LSM方法真的比传统的单树方法要好呢？
我们已经看到，LSM有更好的写性能虽然有一些开销。但是LSM有其他方面的好处。被LSM树创建的SSTables(被排序的文件)是不能被修改的。这使得锁定语义容易实现的多。通常认为内存表是唯一的竞争资源。这比需要构造精巧的锁机制来管理变化的单树结构要好的多。
所以最终的问题是如何满足以写为主的情况。如果你关心写性能，那么除了LSM方法以外可能都是一个大问题。大型互联网公司看起来相当看中LSM。例如雅虎，报告在驾驭增长的事件日志和移动数据时，从大量的读负载操作（read-heavy）稳步向读和写的负载（read-write）上演变。而许多传统数据库依然提供了偏于更多的优化读的文件结构。
因为日志结构的文件系统（见脚注）的关键参数在于增加内存。通过操作系统提供的文件缓存，更多的可用内存自然能优化读性能。写性能（当内存不增加的情况下）因此成为了短板。所以换句话说，硬件的提升对读性能比对写性能提升的更多。因此选择一个写为主要目的的文件结构就说得通了。
当然诸如LevelDB和Cassandra的实现通常比单树的方法提高了更好的写性能（这里还有这里）。
超越分层LSM方法
在LSM方法的基础上有更多的工作。雅虎开发了叫做Pnuts的系统把LSM和B树结合并且演示出更好的性能。我任未看到这个算法的公开实现。IBM和谷歌最近也做了同样的工作，尽管是不同的思路。也有不少相关的方法有类似的性能，但是保留了和LSM一样的总体的结构。这些包括Fractal Trees和Stratified Trees.
硬件的使用方式也是值得去考虑的。昂贵的固态磁盘，例如FusionIO，有更好的随机写性能。这适合就地更新方法。稍微便宜的SSD和机械磁盘更适合LSM。LSM避免了少量的随机存取把SSD弄废（原文是把SSD蹂躏到神志不清）。
LSM也不是全无被批评。他的最大问题，例如全局缓存，在收集阶段对宝贵IO有影响。这里有一些有趣的讨论：讨论
所以如果你看数据产品，用BDB对比LevelDb，用Cassandra对比MongoDb。你要把他们的文件结构和他们的相关性能联系在一起（比如LSM适合写多读少，因此ldb和cassandra适合写多读少）。测试出来的数据支持这种看法，你使用的系统（以及场合）当然要考虑到系统选择的算法而造成的性能折扣。