LSM Tree与SSTable：构建高效KV存储的基石

数据存储方面除了被大家熟知的MySQL、PostgreSQL数据库之外，目前基于LSMTree数据模型的数据库也已经得到广泛的应用，尤其在比较看重写入吞吐量和写入性能的场景基于LSMTree的数据库具有良好的性能表现。我们简单看下SSTable和LSMTree的实现原理。

从一个简单的数据库实现开始

假设我们要构建一个KV数据库，可以用一个shell脚本完成一个名字为myDB的简单实现：

#! /bin/bash

db_set() {
    echo "$1,$2" >> db.data
}

db_get() {
    grep "^$1," db.data | sed -e "s/^$1,//" | tail -n 1
}

那么可以通过如下的方式来进行存储和获取数据：

$ db_set 123 '{"name":"tesla","attr":["made in china"]}'
$ db_set 456 '{"name":"audi","attr":["made in german"]}'
$ db_get 123
{"name":"tesla","attr":["made in china"]}

它的底层存储也很简单，在一个文本文件中每行包含一个kv对，key和value用逗号分隔。如果有新的值写入不会覆盖旧值，在获取数据时找到文件中该key最后一次的记录来获取最新的值。

通过这种在文件尾部追加的方式使得db_set性能很好，此处暂不考虑并发控制、错误处理、文件大小等问题。db_get每次都要扫描整个文件，随着文件中保存的数据增多性能会逐渐降低。

引入索引和文件压缩

在数据库中为了提高查询性能通常为某些字段添加索引，同样的思路我们可以为myDB添加一个哈希索引，哈希索引的key对应文件中的key，哈希索引的value为该key在文件中的offset。为简单起见这里使用HashMap来实现，每次启动myDB时都从数据库文件构建索引并保存在内存中。查找时通过索引找到该key对应的offset便可快速读取value，每次有新的数据写入数据库时都会更新HashMap中该key对应的最新offset。

随着数据的增多我们需要考虑数据文件膨胀的问题，控制文件大小的一个办法是对文件进行压缩，但是如果只有一个数据文件同时还要提供读写则没办对其压缩所以我们可以设定为当数据文件超过一定大小后就关闭该文件，新的数据写到另一个新的文件中。对于这些停止写入的文件后台有一个线程来对其进行合并和压缩：将两个文件的内容合并写入到另一个新文件中，写入过程中对相同的key只保留最近的value。合并过程中仍然可以用旧的文件进行读取，合并完成后读取请求切换到新的合并文件上，旧的文件即可删除。

每个文件在内存中都有对应的HashMap，查找数据时首先查找最新写入文件的HashMap如果没找到再找次新的HashMap，以此类推，数据文件的合并可以使得文件数量控制在一定的范围内，因此通常也不需要查找太多的HashMap。

其他方面的一些考虑：

删除数据

如果要删除某个kv，则需要数据文件中追加一条特殊的删除记录，改记录通常被称为墓碑，在合并数据文件时一旦发现墓碑标志则会丢弃这个已经删除的key

崩溃恢复

如果数据库发生崩溃再次重启的时候需要扫描全部的数据文件以构建索引，如果数据文件很大则耗时较长，可以将HashMap的快照存在磁盘中每次从快照文件中恢复索引

另外如果在数据写入时发生了崩溃则会导致数据丢失，通常的做法是在数据写入前先写入WAL文件中，崩溃时可从该文件进行数据恢复，也是目前数据库中常见的一种办法

并发控制

数据是先后顺序追加到文件中的所以通常可以只维护一个写线程，数据写入后便不可改变因此可以并发的有多个读取线程

通过文件顺序追加的方式存储数据有以下几个好处：

相比于新值覆盖旧值的方式，顺序追加将随机写入转变为顺序写入可以获取到更好的性能
对于文件顺序追加且不可变的方式，在发生崩溃时更容易进行数据恢复，不用过于担心某个数据存在部分新值部分旧值的问题
定期的合并压缩可以避免数据空洞和文件碎片化的问题

至此我们已经构建了一个底层数据模型为基于文件顺序写入的简单KV数据库，可以满足一些场景下KV数据的存储和读取，但仍存在如下问题：

如果数据量很大内存里放不下所有的HashMap，而如果将一部分HashMap放入磁盘中则会影响性能，因为它会带来许多磁盘的随机访问
哈希索引对于区间查询只能采用对区间内所有key挨个查询的方式，查询效率不高

有序的数据文件

为解决上面说的问题我们考虑将数据文件中KV的存储顺序改为按key排序的方式写入，这种格式被称为排序字符串表，简称SSTable，每个键在每个合并段文件里只能出现一次，SSTable有以下好处：

合并文件将更加高效，可以同时读取多个文件采用归并排序的方式对文件进行合并
内存中的HashMap不在需要保存所有key的索引，例如对于Martin的查找，虽然索引中不存在该key，但是我们知道Mark和Matt的索引值并且Martin位于它俩之间那么我们只需要扫描Mark到Matt间的数据即可找到Martin。通过这种方式可以减少索引大小节省内存空间

我们需要一种方式将按写入顺序保存的数据文件转变成按key排序的文件且要保证不降低写入的性能：

在内存中维护一个有序的树状结构来存放数据，例如AVL树或者红黑树等，该结构通常被称为内存表(memtable)
当memtable超过一定大小时将其写入文件中，由于已经在内存中排好序因此按照顺序将其写入文件既可以保证写入的高效性又可以使得文件里的内容是按照key完成排序的
为防止崩溃时丢失数据，每次数据写入前先追加写入到WAL日志中，如果发送崩溃可重WAL中恢复memtable。该日志不需要按key排序，当memtable写入SSTable后该WAL日志删除

当查找某个key时首先检查内存数据(memtable)，如果没有找到这个key，就会逆序的检查每个sstable文件，直到key 被找到。因为每个sstable都是有序的，单个文件的查找时间复杂度为O(logN)，总的查找时间复杂度为O(K log N), K为查找sstable的个数， N 为sstable平均大小。

一些其他方面的性能优化

当查找的key不存在时myDB需要扫描所有的memtable和数据文件，为此可使用布隆过滤器来近似计算该key是否存在以提升查询性能

数据文件的合并和压缩方式不同也会影响性能，常见的合并压缩方式有：按层级压缩(LevelDB和RocksDB使用)、按大小分级压缩(HBase)使用。按层级压缩和按大小压缩的区别为：

按层级压缩的每一层维护指定个数的文件且在一层中一个key只能存在于一个文件中，因此在一层查找一个key只需查找一个文件。注意：第一层不满足上述条件，一个key可以分布在多个文件中。
文件只会被合并到上一层的一个文件。当一层的文件数超过一定大小时，一个文件会被选出并合并到上一层

这些策略的目的是为了减少合并操作对读写数据请求的影响同时节省磁盘空间，除了这些之外对性能的优化还有很多，例如通过KV分离来减少写放大、提升压缩率、提升索引效率等。

与Btree对比

基于SSTable的数据存储模型与我们熟知的Btree相比有以下不同：

Btree查找速度相比SSTable更快一些
SSTable写入性能更高，吞吐量大
Btree是写时覆盖容易产生空洞和碎片
Compaction 机制会带来一定程度上的写放大
受后台合并线程的影响，在执行合并时SSTable读写操作性能会有所降低，因此SSTable读写响应时间不如Btree稳定

最后

上述的描述便是LevelDB、RocksDB的主要思想，SSTable和memtable由Google首次在Bigtable论文中提出，HBase和Cassandra的设计也是受此影响，而在Lucene中term与doc list的映射关系也是存放在类似SSTable的文件中。这个memtable索引被称为以日志结构的合并树(Log Structed Merge Tree，简称LSM-Tree)，因此基于合并和压缩排序文件原理的存储引擎被称为LSM存储引擎。

参考

Log Structured Merge Trees