LSM 存储引擎

Bitcask提供了一种日志型的键值对存储引擎,这些键值对按照写入的顺序排列,并且对于出现在日志中的同一个键,后出现的值优于之前的值。除此之外,日志中键值对的顺序并不重要。

SSTable

在Bitcask存储引擎基础上,我们加上一条新的规则:要求键值对的顺序按键排序。

这种格式称为排序字符表,简称为SSTable。它要求每个键在每个合并的段文件中只能出现一次(Bitcask中的压缩过程已经确保了)。SSTable相比哈希索引的日志段,具有以下优点:

  1. 合并段更简单高效,即使文件大于可用内存。方法类似合并排序算法中适用的方法,并发地读取多个输入段文件,比较每个文件的第一个键,把最小的键拷贝到输出文件,并重复这个过程。这会产生一个新的按键排序的合并段文件。如果仙童的键出现在多个输入段,保留最新段值并丢弃旧段中的值。
  2. 在文件中查找的键时,不再需要在内存中保存所有键的索引。由于键的排序特性,只需要内存中维护一个系数的内存索引,记录某些键的便宜,就可以很快的扫描查找。

构建和维护SSTable

键值对是以顺序的方式写入的,如何让数据按键排序呢?

在磁盘上维护排序结构是可行的,例如数据库中常用的B-Tree。不过将其保存在内存中更容易。内存排序有很多广为人知的树状数据结构,例如红黑树或AVL树。使用这些数据结构,可以按任意顺序插入健并以排序后的顺序读取它们。

存储引擎的基本工作流程如下:

  • 当写入时,将其添加到内存中的平衡树数据结构中(例如红黑树)。这个内存中的树有时被称为内存表。
  • 当内存表大于某个阈值(通常为几兆字节)时,将其作为SSTable文件写入磁盘。由于树已经维护了按键排序的键值对,写磁盘可以比较高效。新的SSTable文件称谓数据库的最新部分。当SSTable写磁盘的同时,写入可以继续添加到一个新的内存表实例。
  • 为了处理读请求,首先尝试在内存表中查找键,然后使最新的磁盘段文件,接下来是次新的磁盘段文件,以此类推,直到找到目标(或为空)。
  • 后台进程周期性地执行段合并与压缩过程,以合并多个段文件,并丢弃哪些已被覆盖或删除的值。
  • 当数据库崩溃时,最近的写入(写入内存表但尚未写入磁盘)将会丢失。为避免该问题,可以在磁盘上保留单独的日志,每次写入都会立即追加到该日志。这个日志文件不需要按键排序,它唯一的目的就是在崩溃后恢复内存表。每当内存表写入SSTable时,相应的日志可以被丢弃。

以上描述的算法本质上正式LevelDBRocksDB所使用的,主要用于嵌入到其他应用程序的键值对存储引擎库。类似的存储引擎还被用于CassandraHBase,这两个引擎都受到Google的Bigtable论文的启发,实际上,也正是这篇论文引入了SSTable和内存表这两个术语。

最初这个索引结构是以日志结构的合并数(Log-Structured Merge Tree,LSM-Tree)命名,它建立在更早起的日志结构文件系统之上。因此,基于合并和压缩排序文件原理的存储引擎通常被称谓LSM存储引擎。

性能优化

当朝招某个不存在的键时,LSM-Tree算法可能很慢,在确定键不存在之前,必须先检查内存表,然后一直回溯访问到最旧的段文件,这可能从磁盘中多次读取。为了优化这种访问,存储引擎通常使用额外的布隆过滤器。

还有不同的策略会影响甚至决定SSTable压缩和合并时的具体顺序和时机。最常见的方式是大小分级和分层压缩。LevelDBRocksDB使用分层压缩,HBase使用大小分级,Cassandra则同时支持者两种压缩。在大小分级的压缩中,较新的和较小的SSTable被连续合并到较旧和较大的SSTable。在分层压缩中,键的范围分裂成多个更小的SSTable,旧数据被移动到单独的层级,这样压缩可以逐步进行并节省磁盘空间。

即使有许多细微的差异,但LSM-Tree的基本思想,即保存在后台合并的一系列SSTable,却足够简单有效。即使数据集远远大于可用内存,它仍然能够正常工作。由于数据按排序存储,因此可以有效地执行区间查询,并且由于磁盘是顺序写入,所以LSM-Tree可以支持非常高的写入吞吐量。