> For the complete documentation index, see [llms.txt](https://shimin-huang.gitbook.io/doc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shimin-huang.gitbook.io/doc/base/ji-suan-ji-li-lun/lsm-cun-chu-mo-xing.md).

# LSM存储模型

## 概述

### 什么是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存储模型[LSM paper](https://link.zhihu.com/?target=https%3A//www.cs.umb.edu/~poneil/lsmtree.pdf)就是解决上述问题的。

### LSM如何解决问题

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

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

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

### LSM好处

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

## 存储结构

### 实现方式

1. 当有`写操作(或update操作)`时，写入位于内存的buffer，内存中通过某种`数据结构(如skiplist、vertor等)保持key有序`
2. 一般的实现也会将数据追加写到磁盘Log(wal)文件，以备必要时恢复
3. 内存中的`数据定时或按固定大小`地刷到磁盘，更新操作只不断地写到内存，并不更新磁盘上已有文件 compact操作
4. 随着越来越多写操作，磁盘上积累的文件也越来越多，这些文件不可写且有序
5. 定时对文件进行合并操作(compaction)，消除冗余数据，减少文件数量

![技术分享](http://image.mamicode.com/info/201503/20181004105358040541.png)

* LSM存储结构的写操作，只需更新内存，内存中的数据以块数据形式刷到磁盘，是顺序的IO操作，另外磁盘文件定期的合并操作，也将带来磁盘IO操作。
* LSM存储结构的读操作，先从内存数据开始访问，如果在内存中访问不到，再顺序从一个个磁盘文件中查找，由于文件本身有序，并且定期的合并减少了磁盘文件个数，因而查找过程相对较快速。
* 合并操作是LSM实现中重要的一环，LevelDB、Cassandra中，使用基于层级的合并方式(Levelled compaction)，生成第N层的时候，对N-1层的数据进行排序，使得每层内的数据文件之间都是有序的，但最高层除外，因为该层不断有数据文件产生，因而只是数据文件内部按key有序。
* 除最高层外，其他层文件间数据有序，这也加速了读过程，因为一个key对应的value只存在一个文件中。假设总共有N层，每层最多K个数据文件，最差的情况下，读操作先遍历K个文件，再遍历每层，共需要K+(N-1)次读盘操作。

## LSM Paper解读

### 为什么要有LSM-TREE

* 对于大量写操作B-Tree的写入会带来大量的IO开销，存在维护索引、排序写成本，LSM-Tree的核心思想是将写入推迟(Defer)并转换为批量(Batch)写，先将大量写入缓存在内存中，当积攒到一定程度后，批量写入文件中充分利用每一次IO。

### LSM-Tree大量写优于B-Tree的原因

1. **multi-page block**：不同于B-Tree，LSM-Tree的延时写(数据可以积攒)可以有效的利用multi-page block，在Rolling Merge的过程中，一次从C1中读出多个连续pages，与C0进行Merge，然后一次向C1写回这些连续pages，这样有效利用单次I/O完成多个pages的读写（B-Tree在此场景下无法利用multi-page的优势）
2. **batch**：同样因为延迟写，LSM-Tree可以在Rolling Merge中，通过一次I/O批量向C1写入C0多条数据，那么这多条数据就均摊了这一次I/O，减少磁盘的I/O开销