冥冥之中，接触到了不同于关系数据库的NoSQL Key-Value存储引擎RocksDB，懵懵懂懂、充满好奇，google一点，满眼皆是LSM-Tree，头晕眼花、若即若离，便有了这篇文章，一起与大家分享这趟探险之旅。

LSM-Tree(Log-Structured-Merge-Tree)

LSM从命名上看，容易望文生义成一个具体的数据结构，一个tree。但LSM并不是一个具体的数据结构，也不是一个tree。LSM是一个数据结构的概念，是一个数据结构的设计思想。实际上，要是给LSM的命名断句，Log和Structured这两个词是合并在一起的，LSM-Tree应该断句成Log-Structured、Merge、Tree三个词汇，这三个词汇分别对应以下三点LSM的关键性质：

• 将数据形成Log-Structured：在将数据写入LSM内存结构之前，先记录log。这样LSM就可以将有易失性的内存看做永久性存储器。并且信任内存上的数据，等到内存容量达到threshold再集体写入磁盘。将数据形成Log-Structured，也是将整体存储结构转换成了“内存(in-memory)”存储结构。
• 将所有磁盘上数据不组织成一个整体索引结构，而组织成有序的文件集：因为磁盘随机读写比顺序读写慢3个数量级，LSM尽量将磁盘读写转换成顺序读写。将磁盘上的数据组织成B树这样的一个整体索引结构，虽然查找很高效，但是面对随机读写，由于大量寻道导致其性能不佳。而LSM用了一种很有趣的方法，将所有数据不组织成一个整体索引结构，而组织成有序的文件集。每次LSM面对磁盘写，将数据写入一个或几个新生成的文件，顺序写入且不能修改其他文件，这样就将随机读写转换成了顺序读写。LSM将一次性集体写入的文件作为一个level，磁盘上划分多level，level与level之间互相隔离。这就形成了，以写入数据时间线形成的逻辑上、而非物理上的层级结构，这也就是为什么LSM被命名为”tree“，但不是“tree”。
• 将数据按key排序，在合并不同file、level上的数据时类似merge-join：如果一直保持生成新的文件，不仅写入会造成冗余空间，而且也会大量降低读的性能。所以要高效的、周期性合并不同file、level。而如果数据是乱序的，根本做不到高效合并。所以LSM要将数据按key排序，在合并不同file、level上的数据时类似merge-join。

很明显，LSM牺牲了一部分读的性能和增加了合并的开销，换取了高效的写性能。那LSM为什么要这么做？实际上，这就关系到对于磁盘写已经没有什么优化手段了，而对于磁盘读，不论硬件还是软件上都有优化的空间。通过多种优化后，读性能虽然仍是下降，但可以控制在可接受范围内。实际上，用于磁盘上的数据结构不同于用于内存上的数据结构，用于内存上的数据结构性能的瓶颈就在搜索复杂度，而用于磁盘上的数据结构性能的瓶颈在磁盘IO，甚至是磁盘IO的模式。

LSM近年来已被广泛使用起来，还有将B家族树和LSM结合起来使用的，像HBase、SQLite4、MongoDB、Cassandra、LevelDB，还有接下来的主角RocksDB，这些当家数据存储花旦，都或多或少支持、使用起LSM了。

RocksDB

RocksDB是Facebook在LevelDB基础上用C++写的Key-Value存储引擎。其Key和Value都是二进制流。并对闪存(flash)有更友好的优化。先来聊一聊RocksDB的整体结构，然后再聊一聊RocksDB中的一些有意思的抽象，最后聊一聊RocksDB内存上、磁盘上的具体结构。在RocksDB中，将内存结构中的数据写入磁盘结构叫做flush，而不同file、level之间merge叫做compaction。

Architecture

RocksDB如上文所说是基于LSM做存储。RocksDB在内存中的结构叫做memtable，用于形成Log-Structured的file叫做logfile，磁盘上的file结构叫做sstfile，用于记录对file更改的log叫做manifest。

Column-Family

为存储的数据逻辑分族，将不同family互相隔离，分开配置、存储。column family共享logfile，而不共享memtable和sstfile，这使得column family有以下两点特点：

• 多个column family仍然能保持事务的原子性。
• 单独增加、修改、删除一个column family内的数据性能提升。

Filter

RocksDB有一些奇思妙想的filter，这些filter根据特定条件生成，通过数据的key就可以判断数据是否确定或可能被特定条件排除掉。有些filter可以用来对读优化，有些也可以用来管理数据的生命周期等。

Bloom-Filter

bloom filter就是一个能提高读性能的filter。通过算法可以生成一个key set对应的bloom filter。这个bloom filter可以判断出任意key可能存在或者肯定不存在key set中。每个sstfile在生成的时候，都会创建一个或多个对应的bloom filter，当在读数据的时候，可以快速判断出数据是否可能在sstfile中。在做range scan和prefix查找的时候，bloom filter也能帮上忙。

Time-To-Live(TTL)

RocksDB还支持为存入的数据设置上最长生命周期。RocksDB会为有TTL的数据创建一个filter。这种filter叫做compaction filter，当进行compaction的时候，生命周期结束的数据将会被排除。很明显，这个TTL不是绝对时间，RocksDB会在绝对时间过后的一段时间内删除数据。

Memtable

RocksDB在内存上的结构由memtable组成，具体默认使用SkipList，当然，外部也可以指定其他数据结构。不过，SkipList做为用多个线性结构模仿出层级结构的“树状“数据结构，能提供常数级顺序访问和对数级随机访问，并且在并发环境相对于其他树状数据结构，减轻了锁开销，运用在这里再合适不过了。

Flush

为了减小锁开销，将写入memtable和flush分离，RocksDB会使用多个memtable，并且把flush这件事抽象为task-pipeline，也就是job、job queue、worker抽象。将要flush的memtable先转换成immutable memtable，代表其不可写了，并将immutable memtable加入flush pipeline，等待后台线程去flush。而同时新的memtable生成取代immutable memtable等待数据写入。在将immutable memtable flush的过程中，值得一提的是会做inline-compaction，这是将immutbale memtable提前进行数据合并的优化，如果在这个memtable创建到flush的周期中，数据被加入然后删除，在这一步就可以compact掉，这对短生命周期的数据有很大的写优化。