LSM
简介
2006年，google发表论文《Bigtable: A Distributed Storage System for Structured Data》，文中提到了该存储的文件组织方式，日志结构合并树（Log Structured-Merge Tree）,后被简称为LSM。
LSM因为写入的高性能和良好的适配性，目前在文件存储中广泛应用，例如Hbase，Cassandra, LevelDB, SQLite等。
原理
LSM的重要组件有MemTable，SST文件，WAL等。
内存结构
不同于传统的面向页面的关系性数据库，LSM是日志结构型的存储引擎。
作为KV存储，根据Key快速定位Value数据的位置是至关重要的，解决检索问题有两个手段，一个是建立索引，一个是直接排序，LSM采用的是在内存排序的方式将数据变得有序，从而可以快速定位数据。内存中的数据称为Memtable。
在内存排序还有一个作用是可以将内存作为写操作的Buffer，定期刷新到持久化存储，从而减少对持久化存储的随机写压力，随机写因为涉及到磁盘寻址等问题，所以速度比较慢，通过在内存中提前排序把随机写转为顺序写，顺序写的情况下，可以充分利用磁盘的写入能力。
文件结构
内存的数据dump到硬盘上，dump出来的文件在LSM中称为sst文件，因为dump到文件系统的数据是在内存中排好顺序的，所以具有良好的检索能力。
但是这种批量写的问题随着时间的迁移也会出现问题，sst之间是没有顺序的，所以查询数据需要遍历所有的sst文件，随着sst文件的增加，查询性能会下降，LSM采用的解决方案是定期将sst合并的方式减少sst的数量。
WAL
因为LSM的数据是先写入缓存，之后才存储在文件系统的，因为内存容易丢失的特点，所以LSM树在写入内存之后会先写日志，这种方式一般称为WAL，WAL其实也是一种将随机写转为顺序写的思想。