什么是 LST-Tree
LSM-Tree 全称 Log-Structured Merge Tree，该树用于优化写入密集型的操作，解决了传统的 B 树或 B+ 树进行频繁写入时产生的性能问题。其充分利用了磁盘顺序写的速度远高于随机写的速度，并通过内存 + 磁盘的多层合并，提高了大规模数据的写入性能。
主要包含了几个概念：
- 批量写入：充分利用磁盘顺序写的速度
- 分层存储：充分利用内存速度，平衡磁盘和内存的性能差异
- 合并操作：去除冗余和过期的数据
系统流程：
- 写入操作：系统不断接受写入请求，并将数据存储在内存中
- 落盘操作：当内存中的数据超出一定阈值时，就会将内存中的数据写入到磁盘中，并清空内存中的数据，每次落盘都是写入到一个新的文件中
- 文件合并：由于每次落盘操作都会产生一个文件，所以需要对这些文件进行维护，删除过时或冗余的数据，并将这些小文件合并成一个大文件
需要注意，以上的数据结构，不论是在内存中还是在磁盘中都是有序的，可以实现快速的查找和写入。
存储结构
在内存中的数据结构是 memtable，其是有序的数据结构，可以是跳表或者红黑树，以此实现快速的查询和写入。在写入数据时，当 memtable 的数据量超过一个阈值，就要将该 memtable 写入到磁盘中。为了保证在写入过程中，系统仍能响应请求，这里的操作是交换缓冲区。即当 memtable 满时，使用另一个空的 memtable 来接受新数据，而老的 memtable 进行落盘操作，落盘操作完成后，这个老的 memtable 就可以作为空的 memtable 完成下一次的交换操作。（这个交换缓冲区的操作中，满的 memtable 称为 immutable memtable）
memtable 落盘后称为 sstable，代表落盘后的持久化存储，会按照 key 有序存储，每个 sstable 尾部都会构建一个索引，用于快速查找。同时，sstable 存在一个序号表示其上更早落盘还是更晚落盘的，以此表明哪一个 sstable 是最新的。
当 sstable 越来越多时，读写性能会下降，此时就需要对这些 sstable 进行合并，删除已经删除的键，用新的 key-value 覆盖老的 key-value。在合并操作进行时，就会产生层级式的结构（视合并策略而定），最上层数据最新，同时数据量也最小，最下层数据最老，但是数据量最大，以此维持查询性能。
具体来讲，如果只维护一个有序的 sstable 文件，会产生写放大的问题，也就是每次数据更新都要重写整个文件，造成不必要的磁盘写入。而在层级式的结构中，只有上层较小的数据会频繁更新，而较大的下层数据更新不频繁。
查询操作
由于 LSM-Tree 是层级式的，最顶层代表最新的数据，最底层代表最老的数据，查询则是从顶向下的，只有当顶层查找不到数据时，才会往下。
第一个查询的是 memtable，随后到 immuteble memtable，最后按照时间顺序依次查询 sstable。
为了加速查询，通常会引入布隆过滤器，每个 sstable 都可以关联一个布隆过滤器，用于快速判断某个键是否存在于当前 sstable 中。布隆过滤器是一个基于概率的数据结构，本文不赘述。
删除操作
在删除时，并不会真正删除该数据，而是对该数据打上 tombstone 的标记，如果查询到的数据带有该标记，则可以直接返回不存在该数据。否则查找一个已经删除的数据，必须对全盘进行扫描，显然速度是较慢的，这种方法用空间来交换时间。
合并操作
系统会定期在后台对磁盘中的数据进行合并，称为 Compaction，他将多个有序文件合并成一个新的有序文件，并删除重复和过时的记录。具体来说，假如相同的键存在多个版本，则仅保留最新版本键所对应的值。
合并操作并没有固定的策略，要视具体情况而定，但是合并的操作都是一样的，本质上是合并排序的过程，对两个按 key 排序的数据进行合并。可以根据层级或大小来选择要合并的 sstable，并设置合并后 sstable 的层级。
容错机制
假设数据已经写入内存中，返回给客户端成功的响应，此时断电宕机，数据还来不及写入到磁盘中，那么这次请求就失败了，但是仍然返回给客户端成功的响应。如果等写入磁盘再反馈客户端结果则耗时太长，也是不可行的，所以就需要一个机制来保证写入内存的数据也可以被持久化。
这个机制可以通过 WAL (Write-Ahead Log) 来实现，具体原理本文不赘述，大概的思想是在写入操作发生时，系统首先就将这些操作记录到 WAL 文件中，写入到磁盘。当系统宕机下线，这些操作记录还是能够保留，下次启动时，系统会先查看 WAL 文件，检查当前系统状态和 WAL 有哪些是不一致的，然后根据 WAL 恢复系统状态。
当然，为了防止 WAL 过大，也会对文件进行定期截断，删除那些已经持久化的记录。