LSM原理解读

06年，Google发表了BigTable论文，从此推开了大数据时代的大门。

为什么又提及BigTable，是因为这篇论文中使用了LSM这种数据结构。

LSM: Log Structured-Merge Tree(日志结构合并树)，是一种先于BigTable出现的文件组织方式，最早可以追溯到1996年 Patrick O'Neil等人的论文。在BigTable出现之后开始被重视被广泛应用，比较有名的产品就是Hbase、Cassandra、Leveldb等。

• 用一句话先简单概括其原理

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

• 先用个简单的结构看一下

最简单的LSM tree是两层树状结构C0,C1。 C0比较小，驻留在内存，当C0超过一定的大小， 一些连续的片段会从C0移动到磁盘中的C1中，这是一次merge的过程。在实际的应用中， 一般会分为更多的层级(level)， 而层级C0都会驻留在内存中。

背景

LSM被设计来提供比传统的B+树或者ISAM(Indexed Sequential Access Method)更好的写操作吞吐量，通过消去随机的本地更新操作来达到这个目标。之所以说这是一个好方法，是因为对于存储来讲问题的本质还是磁盘随机操作慢，顺序读写快。顺序读写磁盘快于随机读写主存，而且快至少三个数量级。

如果对写操作的吞吐量敏感,一个好的办法是简单的将数据添加到文件。这个策略经常被使用在日志或者堆文件，因为他们是完全顺序的，所以可以提供非常好的写操作性能。

同时他们也有一些缺点，从日志文件中读一些数据将会比写操作需要更多的时间，需要倒序扫描，直接找到所需的内容。

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

与此同时我们也有多种方法来支持复杂的读场景，比如二分查找、哈希、B+数等。这些方式虽提升了读的性能，却丢失了日志文件很好的写性能。

不管怎样，随机的操作要尽量减少。所以LSM就出现了，保持了日志文件写性能，以及微小的读操作性能损失。本质上就是让所有的操作顺序化。

算法

LSM将之前使用一个大的查找结构，变换为将写操作顺序的保存到一些相似的有序文件(Sorted Strings Table,简称sstable)中。所以每个文件包 含短时间内的一些改动。因为文件是有序的，所以之后查找也会很快。文件是不可修改的，他们永远不会被更新，新的更新操作只会写到新的文件中。通过周期性的合并这些文件来减少文件个数。 此时可以回到上面看图 。

更具体的看，当一些更新操作到达时，他们会被写到内存缓存（也就是memtable）中，memtable使用树结构来保持key的有序，在大部分的实现中，memtable会通过写WAL的方式备份到磁盘，用来恢复数据，防止数据丢失。当memtable数据达到一定规模时会被刷新到磁盘上的一个新文件，重要的是系统只做了顺序磁盘读写，因为没有文件被编辑，新的内容或者修改只用简单的生成新的文件。

因为比较旧的文件不会被更新，重复的纪录只会通过创建新的纪录来覆盖，这也就产生了一些冗余的数据。所以系统会周期的执行合并操作（compaction)。 合并操作选择一些文件，并把他们合并到一起，移除重复的更新或者删除纪录，同时也会删除上述的冗余。更重要的是，通过减少文件个数的增长，保证读操作的性 能。因为sstable文件都是有序结构的，所以合并操作也是非常高效的。

当一个读操作请求时，系统首先检查内存数据(memtable)，如果没有找到这个key，就会逆序的一个一个检查sstable文件，直到key 被找到。因为每个sstable都是有序的，所以查找比较高效(O(logN))，但是读操作会变的越来越慢随着sstable的个数增加，因为每一个 sstable都要被检查。

所以，读操作比其它本地更新的结构慢，幸运的是，有一些技巧可以提高性能。最基本的的方法就是页缓存（也就是leveldb的 TableCache，将sstable按照LRU缓存在内存中）在内存中，减少二分查找的消耗。

即使有每个文件的索引，随着文件个数增多，读操作仍然很慢。通过周期的合并文件，来保持文件的个数，因些读操作的性能在可接收的范围内。即便有了合 并操作，读操作仍然会访问大量的文件，大部分的实现通过布隆过滤器来避免大量的读文件操作, cassandra就采用了Bloom filter的方式。

思考

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

而如scylladb，通过异步IO，非阻塞线程，线程和线程之间通过消息通讯，没有内存的共享，没有互斥锁，也没有原子操作来大幅的提高了cpu的效率。

2016年，Lanyue Lu等人发布了WiscKey论文，这篇论文提出了一种新的设计 WiscKey: Separating Keys from Values

in SSD-conscious Storage，专门为SSD所优化，将key和value分别存储以减少I/O放大。key存在LSM tree中， value存在WAL中，叫做value log。

通常情况下，key比较小，所以LSM tree比较小，当获取value值的时候，再从SSD存储中读取。