浅析LSM存储模型

LSM（log-structed-merge-tree）大家可能比较陌生，我之前也是听说而已，只知道Hbase、BigTable、Cassandra、MongoDB等NoSql底层存储模型用的是LSM，仅此而已；最近有个项目用到了RocksDB，底层用的存储模型也是LSM，于是就了解了下LSM，做个笔记加深下理解。

1 what

LSM是什么?解决什么问题？

磁盘的顺序读写速度很快，随机读写很慢。现在市面上7200rpm的希捷SATA硬盘顺序读写基本都能达到300MB/s；但是随机读写却很慢，100 IOPS，假设随机读写每次IO大小为1KB，则随机读写数据带宽为100KB/s；顺序读写和随机读写差了三个数量级。

针对磁盘的上述特性，应用都根据自身读写特点做一些优化。比如数据库的binlog日志就是顺序写入，所以效率很高，但是缺点也比较明显，数据很难查询读取（其实binlog是用来回放恢复数据的，不存在查询读取的使用场景）；

Mysql的innodb存储引擎底层用B+树数据结构来组织磁盘上的数据，B+树因其节点的度远大于平衡二叉树（平衡二叉树度为2），所以B+树树高很低（3~4），每一次数据的查询只需3~4次磁盘随机IO即可查找到数据（说法不太准确，其实是找到数据所在的page 16K，加载到内存中，再以二分法查找数据，内存二分查找所耗时间远小于磁盘IO，可忽略不计），效率很高；但是insert和update操作是随机的，update隐藏的含义先找到更新的primary-key，更新，调整B+树；查找primary-key的过程很高效，但是调整B+树的磁盘IO开销却很大，因此关系型数据库mysql的写效率一致饱受诟病。那有没有一种替代B+树的数据组织模型，在不太影响读效率的前提下，提高数据的写效率（随机写->顺序写）?

由O'Neil提出的LSM存储模型https://www.cs.umb.edu/~poneil/lsmtree.pdf就是解决上述问题的。

2 how

LSM如何解决问题的？

看下LSM是如何解决上述问题的：

简单来说，就是放弃部分磁盘读性能来换取写的顺序性。

我们假设要写入一个1000个key是随机数的数据，对磁盘来说，最快的写入方式一定是顺序地将每一次写入都直接写入到磁盘中即可。但这样带来的问题是，没办法查询，因为每次查询一个值都需要遍历整个数据才能找到，这个读性能就太差了；那么如果我想获取磁盘读性能最高，应该怎么做呢？把数据全部排序就行了，B+树就是这样的结构，但B+树的写性能太差了，需要提升写，可以放弃部分磁盘读性能，怎么办呢？

简单，那就划分很多个小的有序结构，比如每m个数据，在内存里排序一次，下面100个数据，再排序一次……这样依次做下去，我就可以获得N/m个有序的小的有序结构，在查询的时候，因为不知道这个数据到底是在哪里，所以就从最新的一个小的有序结构里做二分查找，找得到就返回，找不到就继续找下一个小有序结构，一直到找到为止。

很容易可以看出，这样的模式，读取的时间复杂度是(N/m)*log2N，读取效率是会下降的，这就是LSM的根本思路。当然RocksDB为了优化效率又引入了bloomfilter，compact机制，感兴趣可以阅读RocksDB的wiki：https://github.com/facebook/rocksdb/wiki

3 why

为什么选用LSM?

B+索引树和log型（append）文件操作（数据库WAL日志）是数据读写的两个极端。B+树读效率高而写效率差；log型文件操作写效率高而读效率差；因此要在排序和log型文件操作之间做个这种，于是就引入了log-structed merge tree模型，通过名称可以看出LSM既有日志型的文件操作，提升写效率，又在每个sstable中排序，保证了查询效率。