《LSM算法原理》

记内存中的树为T0, 硬盘上的树按时间顺序，记做T1, ..., Tk

读:

T0
Tk -> Tk-1 -> ... -> T0

T0
T0超过一定大小后，插入硬盘变为Tk+1

复杂度

读：最坏需要读k+1棵树，所以需要定期合并，从而使得只有常数棵树。
写：T0需要O(log)次操作，T0写入硬盘是Append-only的。

比较B+-Tree和LSM-Tree，可以发现对于Scan，前者需要O(logN)次查找，而后者只需要O(k)次（Ti的大小和N无关）。

原理上，无论是B+-Tree还是LSM-Tree都是针对现代存储器的特点而设计的，前者注意利用了Bulk读写，而后者则是力求减少Seek操作，可以说各有侧重。

发布于 2018-10-24

作者：匿名用户
链接：https://www.zhihu.com/question/19887265/answer/517406632
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

LSM的思想，在于对数据的修改增量保持在内存中，达到指定的限制后将这些修改操作批量写入到磁盘中，相比较于写入操作的高性能，读取需要合并内存中最近修改的操作和磁盘中历史的数据，即需要先看是否在内存中，若没有命中，还要访问磁盘文件。

原理：把一颗大树拆分成N棵小树，数据先写入内存中，随着小树越来越大，内存的小树会flush到磁盘中。磁盘中的树定期做合并操作，合并成一棵大树，以优化读性能。

对应于使用LSM的Leveldb来说，对于一个写操作，先写入到memtable中，当memtable达到一定的限制后，这部分转成immutable memtable（不可写），当immutable memtable达到一定限制，将flush到磁盘中，即sstable.，sstable再进行compaction操作。

编辑于 2018-04-12

作者：mina
链接：https://www.zhihu.com/question/19887265/answer/365078623
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：wuxinliulei
链接：https://www.zhihu.com/question/19887265/answer/78839142
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

http://www.open-open.com/lib/view/open1424916275249.html  粘贴党

Log Structured Merge Trees(LSM) 原理

十年前，谷歌发表了 “BigTable” 的论文，论文中很多很酷的方面之一就是它所使用的文件组织方式，这个方法更一般的名字叫 Log Structured-Merge Tree。

LSM是当前被用在许多产品的文件结构策略：HBase, Cassandra, LevelDB, SQLite,甚至在mangodb3.0中也带了一个可选的LSM引擎（Wired Tiger 实现的）。

LSM 有趣的地方是他抛弃了大多数数据库所使用的传统文件组织方法，实际上，当你第一次看它是违反直觉的。

背景知识

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

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

《LSM算法原理》-LMLPHP

上图很好的说明了这一点，他们展现了一些反直觉的事实，顺序读写磁盘（不管是SATA还是SSD）快于随机读写主存，而且快至少三个数量级。这说明我们要避免随机读写，最好设计成顺序读写。

所以，让我们想想，如果我们对写操作的吞吐量敏感，我们最好怎么做？一个好的办法是简单的将数据添加到文件。这个策略经常被使用在日志或者堆文件，因为他们是完全顺序的，所以可以提供非常好的写操作性能，大约等于磁盘的理论速度，也就是200~300 MB/s。

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

这说明日志仅仅适用于一些简单的场景：1. 数据是被整体访问，像大部分数据库的WAL(write-ahead log) 2. 知道明确的offset，比如在Kafka中。

所以，我们需要更多的日志来为更复杂的读场景（比如按key或者range）提供高效的性能，这儿有4个方法可以完成这个，它们分别是：

二分查找: 将文件数据有序保存，使用二分查找来完成特定key的查找。
哈希：用哈希将数据分割为不同的bucket
B+树：使用B+树或者 ISAM 等方法，可以减少外部文件的读取
外部文件：将数据保存为日志，并创建一个hash或者查找树映射相应的文件。

所有的方法都可以有效的提高了读操作的性能（最少提供了O(log(n)) )，但是，却丢失了日志文件超好的写性能。上面这些方法，都强加了总体的结构信息在数据上，数据被按照特定的方式放置，所以可以很快的找到特定的数据，但是却对写操作不友善，让写操作性能下降。

更糟糕的是，当我们需要更新hash或者B+树的结构时，需要同时更新文件系统中特定的部分，这就是上面说的比较慢的随机读写操作。这种随机的操作要尽量减少。

所以这就是 LSM 被发明的原理， LSM 使用一种不同于上述四种的方法，保持了日志文件写性能，以及微小的读操作性能损失。本质上就是让所有的操作顺序化，而不是像散弹枪一样随机读写。

很多树结构可以不用 update-in-place，最流行就是

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

，也称为 Copy-On-Write Tree。他们通过顺序的在文件末尾重复写对结构来实现写操作，之前的树结构的相关部分，包括最顶层结点都会变成孤结点。尽管通过这种方法避免了本地更新，但是因为每个写操作都要重写树结构，放大了写操作，降低了写性能。

The Base LSM Algorithm

从概念上说，最基本的LSM是很简单的。将之前使用一个大的查找结构（造成随机读写，影响写性能），变换为将写操作顺序的保存到一些相似的有序文件（也就是sstable)中。所以每个文件包含短时间内的一些改动。因为文件是有序的，所以之后查找也会很快。文件是不可修改的，他们永远不会被更新，新的更新操作只会写到新的文件中。读操作检查很有的文件。通过周期性的合并这些文件来减少文件个数。

《LSM算法原理》-LMLPHP

让我们更具体的看看，当一些更新操作到达时，他们会被写到内存缓存（也就是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）来优化读性能。

《LSM算法原理》-LMLPHP

Basic Compaction

为了保持LSM的读操作相对较快，维护并减少sstable文件的个数是很重要的，所以让我们更深入的看一下合并操作。这个过程有一点儿像一般垃圾回收算法。

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

《LSM算法原理》-LMLPHP

上述的方案有一个问题，就是大量的文件被创建，在最坏的情况下，所有的文件都要搜索。

Levelled Compaction

更新的实现，像 LevelDB 和 Cassandra解决这个问题的方法是：实现了一个分层的，而不是根据文件大小来执行合并操作。这个方法可以减少在最坏情况下需要检索的文件个数，同时也减少了一次合并操作的影响。

按层合并的策略相对于上述的按文件大小合并的策略有二个关键的不同：

每一层可以维护指定的文件个数，同时保证不让key重叠。也就是说把key分区到不同的文件。因此在一层查找一个key，只用查找一个文件。第一层是特殊情况，不满足上述条件，key可以分布在多个文件中。
每次，文件只会被合并到上一层的一个文件。当一层的文件数满足特定个数时，一个文件会被选出并合并到上一层。这明显不同与另一种合并方式：一些相近大小的文件被合并为一个大文件。

RocksDB 支持两种不同的压缩方式。

通用压缩（Universal Style Compaction ）存储 L0 中的所有文件，所有文件按时间顺序排列。压缩拾取一些在时间上彼此相邻的文件，并将它们合并回新的文件存回 L0。所有文件可以具有重叠的 key。

级别样式压缩（Level Style Compaction）在数据库中以多个级别存储数据。较新的数据存储在 L0 中，最旧的数据存储在 Lmax 中。L0 中的文件可能具有重叠的键，但其他图层中的文件不能。压缩过程选择 Ln 中的一个文件及其在 Ln + 1 中的所有重叠文件，并用 Ln + 1 中的新文件替换它们。通用样式压缩通常导致较低的写入放大，但比水平样式压缩更高的空间放大。

《LSM算法原理》-LMLPHP

这些改变表明按层合并的策略减小了合并操作的影响，同时减少了空间需求。除此之外，它也有更好的读性能。但是对于大多数场景，总体的IO次数变的更多，一些更简单的写场景不适用。

总结

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

通过管理一组索引文件而不是单一的索引文件，LSM 将B+树等结构昂贵的随机IO变的更快，而代价就是读操作要处理大量的索引文件(sstable)而不是一个，另外还是一些IO被合并操作消耗。

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

http://leveldb.googlecode.com/svn/trunk/doc/impl.html

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。

从朴素解释出发解释leveldb的设计

实际上MemTable和SSTable都没有采用纯粹的树形结构,MemTable使用的是跳表而SSTable使用的是层次的结构。(这也是为什么 leveldb 叫 level db 的原因)

内存结构

LevelDB 的内存中维护了 2 个跳跃列表，一个是只读的 rtable，一个是可修改的 wtable。跳跃列表在我的另一本书《Redis 深度历险》中有详细讲解，这里就不再细致重复说明。简单理解，跳跃列表就是一个 Key 有序的 Set 集合，排序规则由全局的「比较器」决定，默认是字典序。跳跃列表的查找和更新操作时间复杂度都是 Log(n)。

《LSM算法原理》-LMLPHP

跳跃列表是由多个层次的链表构成，其中最底层的链表存储了所有的 Key，它们是有序的。普通链表并不支持快速二分查找，但是跳跃链表的特殊结构可以让最底层的链表以近似二分查找算法的效率定位到指定节点。简单理解就是跳跃列表同时具备了有序数组的快速定位能力和链表的高效增删能力。但是它会付出一定的代价，在实现上有一定的复杂度。

如果跳跃列表只存 Key，那 Value 存哪里呢？答案是 Value 也存在跳跃列表的 Key 中。跳跃列表中存储的 Key 比较特殊，它是一个复合结构字符串，它同时包含了键值对的 Key 和 Value。

从这里开始完善朴素解释

首先对于MemTable来说不是持久化的如果重启导致内存中的数据丢失怎么办？WAL 表示的是预写日志，这个日志和MemTable是同步的，这个日志把每次的命令追加到日志中再更改MemTable，这样如果重启的话能够进行”重放”把从已经持久化的状态开始把数据填回到MemTable当中。

其次是对SSTable的合并，SSTable是分层存储的，第一层也就是Level0(被称作 young level)，是MemTable刷入的一层，允许这一层的SSTable的key有交集。对于每一层都有一个阈值(young level 是 4,其他层是按大小算的，10^L MB)，如果超过阈值自动向下一层合并，从level1开始的每一次key不允许有交集。具体的做法是从 young level 中把有交集的SSTable一起和下一层key有交集的SSTable合并成一个新的SSTable，然后其他层则是从自身层取出一个和下一层有交集的SSTable合并即可。这个属性可以用归纳法证明，从0层向1层合并的时候，1层只有一个的情况下肯定不会相交，然后假设n个的时候也不相交，在n+1的时候有交集，那么n+1合并时有0层的 key 和 n 当中的有交集，但是有交集的部分会被归并掉所以矛盾，所以n+1个的时候也是没有交集的。那1层能保证没有交集的话取出一个向下合并也是类似的不会有交集。所以再重复一遍分层存储的两个属性。

RocksDB 支持两种不同的压缩方式。

《LSM算法原理》-LMLPHP

对于朴素解释的两个扩展使得我们对leveldb的设计更接近了。

young层SSTable之间可能存在交集
Li（i>0）层SSTable之间不存在交集

在这个基础上再增加几个约束条件，一个是，对于合并过程每超过2MB就会产生一个新文件，如果文件和下一层的文件有交集的个数有10个以上的话也会产生一个新文件，这样的目的是保证Ln和Ln+1之间不会重复太多。个人理解是覆盖太多，会成了倒三角的”树”情况，上一层搜索性能不好。

当然大量的随机读落在磁盘上还是会有性能问题，因为 seek 也可能是不连续的，这个可以想办法优化, 比如leveldb 里面使用了一种LRU缓存优化读性能。

参考

官方实现文档
LSM-tree论文