LSM学习分享——初识LSM

LSM简介：

      LSM(Log-Structured-Merge-Tree)数据结构是很多存储引擎的底层数据结构，如LevelDB，RocksDB，HBase等。

     LSM树由Patrick O'Neil等人在论文《The Log-Structured Merge Tree》中提出，它实际上不是一棵树，而是2个或者多个树或类似树的结构（注意这点）的集合。我更喜欢把LSM-tree理解成一个存储结构。

      LSM对写性能要求比较高，写性能有显著提升，但牺牲了一点读性能，读性能不稳定，磁盘碎片少，空间利用率高。因此，LSM适用于写多读少的特定场景。

LSM的结构：

最简单的2个结构的示意图

      最简单的LSM树如图所示，在LSM树中，最低级也是最小的C0 tree位于内存中，更高级的C1、C2、C3......都位于磁盘里。数据写入时会先将数据写入内存，当数据量达到一定的阈值，C0树中的数据就会全部或部分刷入磁盘树C1中。

LSM怎么解决大量写：

      利用顺序IO解决

单个文件数据存储

      从图片来分析，数据写入内存的速率要比外存的速率高很多，所以写入C0树（内存）的效率是很高的，数据从内存刷入磁盘之前会进行预排序，将原来的随机写操作转化为顺序写操作。但是在磁盘那个层面来看，暴露出一个问题，在更新k1之后，之前的数据就成了无效数据，但依然保存在磁盘中。 

   （1）、优点：提高了写性能

   （2）、弊端：可能出现无效数据，造成空间浪费

   （3）、改进：后台定时合并压缩数据，消除无效数据