我是从一篇介绍LSM原理的文章的扩展阅读部分，找到这篇文章的。前者的作者称，后者对LSM的原理做了非常精彩的介绍。我读了以后，深以为然：文章没有长篇大论，也没有深奥的数学符号，从一个现实问题，引出了LSM出现的动机和基本原理。作者在最后说到：我们一不小心，又发明了一次LSM。所以，我把这篇文章翻译成中文。本文并不是对原文的直译，我有意删除了其中的一些部分。网络上有另一篇中文译文，基本上算是原文的直译，也可以参考。
SSTable
假设我们需要对大量(G或者T数量级)的数据，用不同的程序多次进行处理。就像我们需要对同一批数据跑多个Map-Reduce任务一样。由于数据量太大，从存储设备读写数据占据了绝大部分的处理时间。因此，我们并不考虑随机读写。我们将用流的方式读取数据，处理完之后，再以流的方式把数据写入到外部存储。这样，我们就可以平摊掉I/O的带来的性能损耗。这个很显然。
SSTable(Sorted String Table)，是一个包含了任意有序键(key-value)值对的文件。key和value可以是任意的二进制对象，key重复没关系，key和value也没有必要进行字节填充。顺序扫描一次这个文件，我们就可以在内存中建立起一个索引(index)。如果文件太大，无法在内存中放下全部索引，为了快速的读取数据，我们可以单独建立一个保存了key:offset(key在文件中的偏移量)的索引文件。就像下图一样。
SSTable和BigTable
SSTable写到外部存储后，文件基本上就不能变了。插入和删除都会改变到文件的结构，需要大量的I/O操作。也就是，对于静态索引来说，随机的读是很简单和快的：读入索引，再进行一次文件I/O，你就可以找到你想要的内容；或者，用memmap把整个SSTable文件映射到内存。
随机写要昂贵得多。除非整个SSTable都在内存中，这样的话，我们只需要几次指针操作。以SSTable为基础，如何构造一种机制，使得即使P数量级的数据，也能达到很快的读写速度：这也是google的BigTable要解决的。他们怎么搞的？
SSTable和LSM树
我们想要保留SSTable提供的快速读取的特点，也想要支持快速写入。事实上，我们基本已经有了一个思路：如果SSTable在内存当中(记成MemTable)，写入速度是很快的；即使SSTable在外部存储上，读取速度也是很快的。这样，我们就有了一个解决方案：
- 在内存当中装载SSTable的索引
- 所有的写操作在MemTable中进行
- 读操作优先检查MemTable是否存在，否则，再在SSTable的index中进行查找
- MemTable会被周期性地写回到外部存储
- 有一个定时任务周期性地合并外部存储上的SSTable
如下图所示：
我们都做了什么？所有的写操作都在内存中进行，因此很快。MemTable达到一定大小的时候，就会被刷新到外部存储上，成为一个SSTable。但是，我们在内存当中维护了SSTable的索引，当我们要进行一次读操作的时候，我们会先检查MemTable，如果没有找到，我们再依次检查每个SSTable的索引，再加上一次IO，因此也是很快的。我们一不小心，又发明了一次LSM。
更新和删除
LSM中，不管已经存在的数据有多大，写入总是很快的：我们只需要在末尾追加一条记录。对于随机读，要么直接从内存中读取(如果命中了MemTable)，要么只需要一次I/O操作，因此也是很快的。更新和删除呢，性能如何？
SSTable一旦保存到外部存储，基本就不能变了。因此，更新和删除都不会动到这些数据。相反，对于更新操作来说，我们在MemTable中存入新的value，对于删除操作，我们在MemTable中追加一条删除的记录。因为我们是顺序检查所有SSTable的索引的，因此，对于后续的读操作来说，我们总会找到最新的值，或者删除的记录，不会读到脏数据。
最后，太多的SSTable会占据大量的存储空间，这不是啥好事，因此，会有一个定时任务来合并SSTable，这样更新和删除操作就会覆盖掉老数据，从而节省了存储空间。
