译文
自从谷歌发表了他的”big table“论文以来已经过去了十年。论文中很酷的一点是它使用的文件组织方式。在1996年后，这个方式以LSM树（Log-Structure Merge Tree）被人所熟知。
LSM现在被用于很多产品的主流文件组织策略。HBase，Cassandra，LevelDB，SQLite，甚至是MongoDB收购了Wired Tiger引擎后，其3.0附带了一个LSM引擎的选项。
使LSM树有趣的是他们离开二叉树风格文件组织主导的领域已经有十几年的历史了。当你第一次看到LSM，它看起来几乎是违反人类思维的，然而当你考虑到文件是如何工作在现代笨重的存储系统上一切就说的通了。
背景知识
二分查找：又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，二分查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一字表。重复上述过程，直到找到满足条件的记录，使查找成功，或直到子表不存在位置，此时查找不成功。
哈希（HASH）：（散列）函数，是将任意长度的数据映射到有限长度的域上。直观解释来说，就是对一串数据a进行杂糅，输出另一端固定长度的数据h，作为这段数据的特征（指纹）。也就是说，无论数据块a有多大，其输出值h为固定长度。到底是什么原理？将a分成固定长度（如128位），依次进行hash运算，然后用不同的方法迭代即可（如前一块的hash值与后一块的hash值进行异或）。如果不足128位怎么办？用0补全或1补全随意，算法中的约定好就可以。
由于用途的不同，hash在数据结构中的含义和密码学中的含义并不相同，所以在这两种不同的领域里，算法的设计侧重点也不同。
预备小知识：
抗碰撞能力：对于任意两个不同的数据块，其hash值相同的可能性极小；对于一个给定的数据块，找到和它hash值相同的数据块极为困难。
抗篡改能力：对于一个数据块，哪怕只改动其一个比特位，其hash值的改动也会非常大。在用到hash进行管理的数据结构中，比如hashmap，hash值（key）存在的目的是加速键值对的查找，key的作用是为了将元素适当的放在各个桶里，对于抗碰撞的要求没有那么高。换句话说，hash出来的key，只要保证value大致均匀的放在不同的桶里即可。但整个算法的set性能，直接与hash值产生速度有关，所以这个时候的hash值的产生速度就尤为重要。
在密码学中，hash算法的作用主要是用于消息摘要和签名，换句话说，他主要用于对整个消息的完整性进行校验。举个例子，登陆简书的时候都需要输入密码，那么简书如果明文保存这个密码，那么黑客就很容易窃取大家的密码来登陆，特别不安全。那么简书就想到了一个方法，使用hash算法生成一个密码的签名，简书后台只保存这个签名值。由于hash算法是不可逆的，那么黑客即便是得到这个签名，也丝毫没有用处；而如果你在网站登陆界面上输入你的密码，那么简书后台就会校验你密码生成的签名值是否匹配。如果匹配，证明你拥有这个账户的密码，那么就允许你登陆。银行也是如此，银行是万万不敢保存用户密码原文的，只会保存密码的hash值而已。
在这些应用场景里，对于抗碰撞和抗篡改能力要求极高，对速度的要求在其次。一个设计良好的hash算法，其碰撞能力是很高的。以MD5为例，其输出长度为128位，设计预期碰撞概率为1/2的64次方，这是一个极小的数字，而即便是在MD5被王小云教授破解之后，其碰撞概率上限也高达1/2的41次方。
在密码学中，hash算法有不少有意思的改进思路，以应付不同的使用场景。例如变色龙Hash（ChameleonHash），它有一个有趣的特性。在普通情况下，ChameleonHash可以当作普通的hash算法使用，从明文（用a表示）得到hash值（用h表示）抗碰撞能力依然特别强；但是如果使用者在计算这个hash值时预先计算一个值（用s表示）并保存，那么通过这个值很容易计算出另一个hash值也为h的明文 a！也就是说，如果你保留这个值的话，hash算法的抗碰撞能力完全被解除了。这意味着，如果某个网站想要作恶的话，那么他可以很容易的替换他们自己的hash算法ChameleonHash，方便地伪造出一个密钥来窃取用户的所有数据，而这个公司完全可以在对外宣传的时候，依然声称对用户信息严格保密--《教网站如何优雅的耍流氓》。
B+树：是应文件系统所需而出的一种B-树的变型树，通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。
1.有n颗子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子结点上。
2.所有的叶子结点中包含了全部关键字的信息，及指向这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的非终端结点可以堪称是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。
ISAM（带索引序列存取法）（Indexed Sequential Access Method缩写）是IBM公司发展起来的一个文件操作系统，可以连续的（按照他们进入的顺序）或者任意的（根据索引）记录任何访问。每个索引定义了一次不同排列的记录。一个职工数据库基于搜寻的信息可以有几个索引。例如，按照职工所属科室的部门索引中，同时还有按照职工姓氏字母顺序排名的名字索引。每个索引中的关键字都是制定的。对于职工名字字母顺序索引，姓就是指定的关键词。
简而言之，LSM树被设计来提供比传统的B+树和ISAM更好的写入性能。他通过消除随机的就地更新操作来实现这一点。
所以为什么这是一个好主意呢？其核心是磁盘的老问题：随机操作缓慢，但当顺序访问时很快。这一点分歧在两种不同的访问方式中间，不管磁盘是固态还是磁性材料，尽管这种影响在主存较小。
顺序操作在主存上比随机操作更快。他们也进一步表明了，在磁性或固态硬盘上，顺序操作比起随机操作快上三个数量级。这意味着随机操作应当被避免，顺序操作很值得设计。
一个小猜想实验：如果我们对吞吐量有兴趣，什么是最好的使用方法呢？一个好的出发点是鉴定的追加数据到文件里。这种方式经常被叫做日志，档案或者堆文件，是完全顺序化的，因此能提供非常快的相当于理论硬盘速度的写性能（通常平均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和Big Table对每个文件的末尾做块索引来实现这一点。这通常比直接二分搜索要好一些，因为它允许可变长字段的用户以及更适合压缩后的数据。
即使是每个文件按被索引了，读操作依然会随着文件的增长而变得缓慢。读操作被定期的合并文件来保证性能。这些合并操作控制了文件的数量，使得读性能在一个可接受的范围内。
即使有压缩操作，读操作依然会访问多个文件。大部分实现通过布隆解析器（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成本。
如果讲的还不清楚，那么这里有不错的描述：
leveldb
leveled-compaction-in-apache-cassandra
LSM方法的思考
所以是否LSM方法真的比传统的单树方法要好呢？
我们已经看到，LSM有更好的写性能，虽然有一些开销。但是LSM有其他方面的好处。被LSM树创建的SSTables（被排序的文件）是不能被修改的。这使得锁定予以容易实现的多。通常认为内存表是唯一的竞争资源。这比需要构造精巧的锁机制来管理变化的单树结构要好很多。所以最终的问题是如何满足以写为主的情况。如果你关心写性能，那么除了LSM方法以外可能都是一个大问题。大型互联网公司看起来相当看重LSM。例如雅虎，报告在驾驭增长的事件日志和移动数据时，从大量的读负载操作（read -heavy）稳步向读和写的负载（read-write）上演变。而许多传统数据库依然提供了偏于更多的优化读的文件结构。
因为日志结构的文件系统的关键参数在于增加内存。通过操作系统提供的文件缓存，更多的可用内存自然能优化读的性能。写性能（当内存不增加的情况下）因此成为了短板。所以换句话说，硬件的提升对读性能比写性能提升的更多。
因此选择一个写为主要目的的文件结构就说的通了。
当然诸如levelDB和Cassandra的实现通常比单树的方法提高了更好的写性能。
超越分层LSM方法
在LSM方法的基础上有更多的工作。雅虎开发了叫Pnuts的系统把LSM和B树结合并且演示出更好的性能。
硬件的使用方式也是值得去考虑的。昂贵的固态磁盘，例如FusionIO，有更好的随机写性能。这适合就地更新方法。稍微便宜的SSD和机械磁盘更适合考虑LSM。LSM避免了少量的随机存取把SSD弄废。
LSM也不是全无被批评。他的最大问题，例如全局缓存，在收集阶段对宝贵IO有影响。
所以如果你看数据产品，用BDB对比LecelDb，用Cassandra对比MongoDb。你要把他们的文件结构和他们的相关性能练习在一起（比如LSM适合写多读少，因此ldb和cassan适合写多读少）。测试出来的数据支持这种看法，你使用的系统（以及场合）当然要考虑到系统选择的算法而造成的性能折扣。
