概述 Overview

首先，在数据存储的畛域，有两大阵营，以 B +tree 为根底的关系型数据库，MySQL，SQLServer。以及以 LSM-tree 为根底的 NoSQL key-value 存储, LevelDB。LSM 是 (Log Structured Merge 的简称) 在分布式存储系统中通常会被设计成 append-only 的零碎，LSM 零碎次要是程序写优化，例如 commit log 等等，并作为分布式系统底层的基石。因而，要理解 LSM 的实现是非常重要的。

背景常识

十年前，谷歌发表了“BigTable”的论文，论文中很多很酷的方面之一就是它所应用的文件组织形式，这个办法更个别的名字叫 Log Structured-Merge Tree。LSM 是以后被用在许多产品的文件构造策略：HBase, Cassandra, LevelDB, SQLite, 甚至在 mangodb3.0 中也带了一个可选的 LSM 引擎（Wired Tiger 实现的）。LSM 乏味的中央是他摈弃了大多数数据库所应用的传统文件组织办法，实际上，当你第一次看它是违反直觉的。

简略的说，LSM 被设计来提供比传统的 B + 树或者 ISAM 更好的写操作吞吐量，通过消去随机的本地更新操作来达到这个指标。

那么为什么这是一个好的办法呢？这个问题的实质还是磁盘随机操作慢，程序读写快的老问题。这二种操作存在微小的差距，无论是磁盘还是 SSD。

上图很好的阐明了这一点，他们展示了一些反直觉的事实，程序读写磁盘（不论是 SATA 还是 SSD）快于随机读写主存，而且快至多三个数量级。这阐明咱们要防止随机读写，最好设计成程序读写。所以，让咱们想想，如果咱们对写操作的吞吐量敏感，咱们最好怎么做？一个好的方法是简略的将数据增加到文件。这个策略常常被应用在日志或者堆文件，因为他们是齐全程序的，所以能够提供十分好的写操作性能，大概等于磁盘的实践速度，也就是 200~300 MB/s。

因为简略和高效，基于日志的策略在大数据之间越来越风行，同时他们也有一些毛病，从日志文件中读一些数据将会比写操作须要更多的工夫，须要倒序扫描，间接找到所需的内容。

这阐明日志仅仅实用于一些简略的场景：1. 数据是被整体拜访，像大部分数据库的 WAL(write-ahead log) 2. 晓得明确的 offset，比方在 Kafka 中。

所以，咱们须要更多的日志来为更简单的读场景（比方按 key 或者 range）提供高效的性能，这儿有 4 个办法能够实现这个，它们别离是：

1. 二分查找: 将文件数据有序保留，应用二分查找来实现特定 key 的查找。
2. 哈希：用哈希将数据宰割为不同的 bucket
3. B+ 树：应用 B + 树 或者 ISAM 等办法，能够缩小内部文件的读取
4. 内部文件：将数据保留为日志，并创立一个 hash 或者查找树映射相应的文件。

所有的办法都能够无效的进步了读操作的性能（起码提供了 O(log(n)) )，然而，却失落了日志文件超好的写性能。下面这些办法, 都强加了总体的构造信息在数据上，数据被依照特定的形式搁置，所以能够很快的找到特定的数据，然而却对写操作不友善，让写操作性能降落。

更蹩脚的是，当咱们须要更新 hash 或者 B + 树的构造时，须要同时更新文件系统中特定的局部，这就是下面说的比较慢的随机读写操作。这种随机的操作要尽量减少。

所以这就是 LSM 被创造的原理，LSM 应用一种不同于上述四种的办法，放弃了日志文件写性能，以及渺小的读操作性能损失。实质上就是让所有的操作程序化，而不是像散弹枪一样随机读写。

很多树结构能够不必 update-in-place，最风行就是：

append-only Btree http://www.bzero.se/ldapd/btree.html

也称为 Copy-On-Write Tree。他们通过程序的在文件开端反复写对构造来实现写操作，之前的树结构的相干局部，包含最顶层结点都会变成孤结点。只管通过这种办法防止了本地更新，然而因为每个写操作都要重写树结构，放大了写操作，升高了写性能。

The Base LSM Algorithm

从概念上说，最根本的 LSM 是很简略的。将之前应用一个大的查找构造（造成随机读写，影响写性能），变换为将写操作程序的保留到一些类似的有序文件（也就是 sstable)中。所以每个文件包 含短时间内的一些改变。因为文件是有序的，所以之后查找也会很快。文件是不可批改的，他们永远不会被更新，新的更新操作只会写到新的文件中。读操作查看很 有的文件。通过周期性的合并这些文件来缩小文件个数。

让咱们更具体的看看，当一些更新操作达到时，他们会被写到内存缓存（也就是 memtable）中，memtable 应用树结构来放弃 key 的有序，在大部 分的实现中，memtable 会通过写 WAL 的形式备份到磁盘，用来复原数据，避免数据失落。当 memtable 数据达到肯定规模时会被刷新到磁盘上的一 个新文件，重要的是零碎只做了程序磁盘读写，因为没有文件被编辑，新的内容或者批改只用简略的生成新的文件。

所以越多的数据存储到零碎中，就会有越多的不可批改的，程序的 sstable 文件被创立，它们代表了小的，按工夫程序的批改。

因为比拟旧的文件不会被更新，反复的纪录只会通过创立新的纪录来笼罩，这也就产生了一些冗余的数据。

所以零碎会周期的执行合并操作（compaction)。合并操作抉择一些文件，并把他们合并到一起，移除反复的更新或者删除纪录，同时也会删除上述的冗余。更重要的是，通过缩小文件个数的增长，保障读操作的性 能。因为 sstable 文件都是有序构造的，所以合并操作也是十分高效的。

当一个读操作申请时，零碎首先查看内存数据(memtable)，如果没有找到这个 key，就会逆序的一个一个查看 sstable 文件，直到 key 被找到。因为每个 sstable 都是有序的，所以查找比拟高效(O(logN))，然而读操作会变的越来越慢随着 sstable 的个数减少，因为每一个 sstable 都要被查看。（O(K log N), K 为 sstable 个数，N 为 sstable 均匀大小）。

所以，读操作比其它本地更新的构造慢，侥幸的是，有一些技巧能够进步性能。最根本的的办法就是页缓存（也就是 leveldb 的 TableCache，将 sstable 依照 LRU 缓存在内存中）在内存中，缩小二分查找的耗费。LevelDB 和 BigTable 是将 block-index 保留在文件尾部，这样查找就只有一次 IO 操作，如果 block-index 在内存中。一些其它的零碎则实现了更简单的索引办法。

即便有每个文件的索引，随着文件个数增多，读操作依然很慢。通过周期的合并文件，来放弃文件的个数，因些读操作的性能在可接管的范畴内。即使有了合 并操作，读操作依然会拜访大量的文件，大部分的实现通过布隆过滤器来防止大量的读文件操作，布隆过滤器是一种高效的办法来判断一个 sstable 中是否包 含一个特定的 key。（如果 bloom 说一个 key 不存在，就肯定不存在，而当 bloom 说一个文件存在是，可能是不存在的，只是通过概率来保障）

所有的写操作都被分批解决，只写到程序块上。另外，合并操作的周期操作会对 IO 有影响，读操作有可能会拜访大量的文件（散乱的读）。这简化了算法工 作的办法，咱们替换了读和写的随机 IO。这种折衷很有意义，咱们能够通过软件实现的技巧像布隆过滤器或者硬件（大文件 cache）来优化读性能。

Basic Compaction

为了放弃 LSM 的读操作绝对较快，保护并缩小 sstable 文件的个数是很重要的，所以让咱们更深刻的看一下合并操作。这个过程有一点儿像个别垃圾回收算法。

当肯定数量的 sstable 文件被创立，例如有 5 个 sstable，每一个有 10 行，他们被合并为一个 50 行的文件（或者更少的行数）。这个过程一 直继续着，当更多的有 10 行的 sstable 文件被创立，当产生 5 个文件时，它们就被合并到 50 行的文件。最终会有 5 个 50 行的文件，这时会将这 5 个 50 行的文件合并成一个 250 行的文件。这个过程不停的创立更大的文件。像下图：

上述的计划有一个问题，就是大量的文件被创立，在最坏的状况下，所有的文件都要搜寻。

Levelled Compaction

更新的实现，像 LevelDB 和 Cassandra 解决这个问题的办法是：实现了一个分层的，而不是依据文件大小来执行合并操作。这个办法能够缩小在最坏状况下须要检索的文件个数，同时也缩小了一次合并操作的影响。

按层合并的策略绝对于上述的按文件大小合并的策略有二个要害的不同：

1. 每一层能够保护指定的文件个数，同时保障不让 key 重叠。也就是说把 key 分区到不同的文件。因而在一层查找一个 key，只用查找一个文件。第一层是非凡状况，不满足上述条件，key 能够散布在多个文件中。
2. 每次，文件只会被合并到上一层的一个文件。当一层的文件数满足特定个数时，一个文件会被选出并合并到上一层。这显著不同与另一种合并形式：一些相近大小的文件被合并为一个大文件。

这些扭转表明按层合并的策略减小了合并操作的影响，同时缩小了空间需要。除此之外，它也有更好的读性能。然而对于大多数场景，总体的 IO 次数变的更多，一些更简略的写场景不实用。

总结

所以，LSM 是日志和传统的单文件索引（B+ tree，Hash Index）的中立，他提供一个机制来治理更小的独立的索引文件(sstable)。

通过治理一组索引文件而不是繁多的索引文件，LSM 将 B + 树等构造低廉的随机 IO 变的更快，而代价就是读操作要解决大量的索引文件 (sstable) 而不是一个，另外还是一些 IO 被合并操作耗费。

如果还有不明确的，这还有一些其它的好的介绍。

http://leveldb.googlecode.com…

and here

对于 LSM 的一些思考

为什么 LSM 会比传统单个树结构有更好的性能？

咱们看到 LSM 有更好的写性能，同时 LSM 还有其它一些益处。sstable 文件是不可批改的，这让对他们的锁操作非常简单。一般来说，惟一的竞争资源就是 memtable，相对来说须要绝对简单的锁机制来治理在不同的级别。

所以最初的问题很可能是以写为导向的压力预期如何。如果你对 LSM 带来的写性能的进步很敏感，这将会很重要。大型互联网企业仿佛很看中这个问题。Yahoo 提出因为事件日志的减少和手机数据的减少，工作场景为从 read-heavy 到 read-write。。许多传统数据库产品仿佛更青眼读优化文件构造。

因为可用的内存的减少，通过操作系统提供的大文件缓存，读操作天然会被优化。写性能（内存不可进步）因而变成了次要的关注点，所以采取其它的办法，硬件晋升为读性能做的更多，绝对于写来说。因而抉择一个写优化的文件构造很有意义。

天经地义的，LSM 的实现，像 LevelDB 和 Cassandra 提供了更好的写性能，绝对于单树结构的策略。

Beyond Levelled LSM

这有更多的工作在 LSM 上，Yahoo 开发了一个零碎叫作 Pnuts，组合了 LSM 与 B 树，提供了更好的性能。我没有看到这个算法的凋谢的实现。IBM 和 Google 也实现了这个算法。也有相干的策略通过类似的属性，然而是通过保护一个拱形的构造。如 Fractal Trees，Stratified Trees.

这当然是一个抉择，数据库利用大量的配置，越来越多的数据库为不同的工作场景提供插件式引擎。Parquet 是一个风行的 HDFS 的代替，在很多绝对的文面做的好很（通过一个列格局进步性能）。MySQL 有一个存储形象，反对大量的存储引擎的插件，例如 Toku (应用 fractal tree based index)。Mongo3.0 则蕴含了反对 B + 和 LSM 的 Wired Tiger 引擎。许多关系数据库能够配置索引构造，应用不同的文件格式。

思考被应用的硬件，低廉的 SSD，像 FusionIO 有更好的随机写性能，这适宜本地更新的策略办法。更便宜的 SSD 和机械盘则更适宜 LSM。