SSTable 与 LSM 引擎

​ 假设我们需要设计一个K-V数据库，为了提升 K-V 数据库的写性能，要尽量避免对磁盘上的内容做随机写，所以对已经持久化在磁盘上的 K-V 不做原地更改，当这个 Key 对应的 Value 发生更新或者删除时，我们仍然继续向磁盘新增一条数据，在读取时同一个 Key 以最后的数据记录为准。

​ 这样的确带来数据写性能的提升，但在查询时，我们需要遍历所有的磁盘数据，然后才知道这个 Key 对应的最后一条数据，因此，我们提出也许可以在内存中维护一个索引结构，HashTable 这样的即可，HashTable 存储着 Key 和 Value 在磁盘中最新数据的位置。

​ 但这又带来一个问题，我们需要对所有的 Key 都保存索引，这就使得整个数据库不能保存太多的 Key，而且磁盘中 Key 的旧数据拜拜浪费了存储空间。因此，又提出一个改进，可以在内存中维护一个 MemTable，MemTable 是按照 Key 排好序的数据结构，当数据写入时，首先写入 MemTable，等到 MemTable 的大小超过限值时，将之写入磁盘文件，而且此后这个文件中的数据将不会再被更新，这个有序的、不可变的文件就被称为 SSTable（Sort String Table，因为最开始 Key、Value 均以二进制字符串形式存储），由于 SSTable 的有序性，对于每个 SSTable 维护的可以是一个稀疏索引，例如，k1 不在索引中，但发现索引中有 k0 和 k3，这时读取这两个地址中间的数据就能找到 k1 对应的 Value。同时，由于 MemTable 的存在，对于 一个Key 在短时间内频繁的变更，只用写最后一次的结果即可。为了减少磁盘中的过期数据，在后台会对 SSTable 进行合并，得益于 SSTable 本身的有序性，我们可以将两个大于可用内存的 SSTable 合成一个新的 SSTable，使用归并排序即可，丢弃这两个 SSTable 中已被覆盖或删除的数据。得益于 SSTable 的不变性，读取 SSTable 时不用加锁，提高了并发读的性能。最早这里的索引结构被命名为 LSM-Tree（Log-Structured Merge-Tree），所以 基于合井和压缩排序文件原理的存储引擎通常都被称为LSM存储引擎。

​ 上述方案还有问题，当数据库故障时，那些写入 MemTable 但还没来得及刷写到磁盘中的文件将丢失，为了避免这个问题，设立一个单独的追加写日志文件，在写入 MemTable 之前先写入该日志文件，称为 WAL(Write-Ahead Log)，故障恢复时从WAL 恢复 MemTable，由于 WAL 只是用来恢复 MemTable 的（这不会经常发生），所以写入 WAL 的数据不需要排序，直接写即可，同时 WAL 是一个追加写文件，其写入速度可以比得上对内存的随机写，所以 WAL 不会对数据库的写入性能产生产生大的影响。另外一个可以优化的点是：当读请求的是一个不存在的 Key 时，需要遍历 MemTable 和所有的 SSTable 才能发现这个 Key 不存在，所以通常使用布隆过滤器来提前判断所请求的 Key 是否存在。

参考资料

- [1] 数据密集型应用系统设计(Designing Data-Intensive Applications)