单机存储系统之LSM树存储引擎

一、LSM（Log Structured Merge Tree） 的思想

  将数据的修改增量保存在内存中，达到指定大小后将这些修批量写入磁盘中。读取时需要合并磁盘中历史数据和内存中最近修改的操作。LSM树的优点在于有效规避了磁盘随机写入的问题，但是读取的时候有可能要访问较多的磁盘文件。


二、LSM存储引擎的应用——LevelDB
  2011年Google发布了LevelDB。LevelDB是Key-Value嵌入式数据库管理系统编程库，目前的版本能够支持Billion级别的数据量。LevelDB是一个C++库，可按照字符串键值顺序映射。
  Level DB是典型的Log-Structured-Merge Tree的实现，它通过延迟写入以及Write Log Ahead技术来加速数据的写入并保障数据的安全。LevelDB的每个数据文件(sstable)中的记录都是按照Key的顺序进行排序的，但是随机写入时，key的到来是无序的，因此难以将记录插入到其排序位置。于是需要它采取一种延迟写入的方式，批量攒集一定量的数据，将它们在内存中排好序，一次性写入到磁盘中。但是这期间一旦系统断电或其他异常，则可能导致数据丢失，因此需要将数据先写入到log的文件中，这样便将随机写转化为追加写入，对于磁盘性能会有很大提升，如果进程发生中断，重启后可以根据log恢复之前写入的数据。


三、LevelDB的策略
1、写数据与修改数据
  当一条新数据写入的时候，LevelDB后首先写入MemTable中。当MemTable达到一定大小的时候LevelDB会将MemTable冻结成不可变的MemTable，并生成一个新的MemTable。后台的线程会将不可变的MemTable，写入到一个SSTable中。LevleDB的SSTable是分层级的。
2、读数据
  当需要读取一条数据的时候，Level后先检索内存中的MemTable然后在按层级读取每一个SSTable。为了加速读取SSTble。加速读取数据的方式是生成一个索引文件。
3、合并操作
  当某个层级下的SSTable文件超过一定数量的时候，levelDB后从这一层选择文件与高一层进行合并。按照主键顺序依次迭代出所有记录，如果有价值则写入新的SSTable文件中，没有价值则丢弃