存储引擎层是键值数据的核心单元。数据存储在存储引擎中，并采用索引结构提升存储引擎中数据的存取性能。存储引擎对上层提供Put、Get、Del和Range函数接口，这些接口分别负责往该存储引擎内部插入/修改键值对、查询键值对，删除键值对和范围查询键值对。
一般来说，存储引擎主要分为4个模块：索引模块、存储模块、持久化模块和空间分配/垃圾回收模块。其中，存储模块负责键值对的物理存储，索引模块负责对每个键值对的快速定位，持久化模块负责对存储模块的持久化和可恢复性的保证，空间分配/垃圾回收模块负责空间的申请、分配及当空间使用率过高时的垃圾回收任务。对于部分有特殊需求的键值数据库，可能还会有额外的模块，如加解密模块和压缩模块等。
根据采用的索引和存储结构的不同，典型的存储引擎可以分为三大类。
1）基于哈希表的存储引擎。
2）基于B+树的存储引擎。
3）基于LSM-tree的存储引擎。
基于LSM-tree的存储引擎
LSM-tree的键值（key-value，KV）存储针对随机写进行优化，通过异地更新把随机写转化为顺序写，取得较为高效的数据插入及删除性能，作为存储引擎被广泛应用于许多存储系统上。Google的BigTable和LevelDB、Facebook的Cassandra和RocksDB、Apache的HBase等系统均采用LSM-tree作为存储引擎。阿里巴巴的OceanBase底层设计也参考了LSM-tree。Facebook还将RocksDB作为MySQL的一个存储引擎移植到MySQL，称之为MyRocks。
下面以LevelDB为例简要介绍LSM-tree。如图4-8所示，内存中的写缓冲（MemTable）以追加写的方式存储最新的键值数据，Immutable MemTable是临时的只读的MemTable，当一个MemTable里存储的键值数据达到一定量后，这个MemTable就转化为Immutable MemTable，然后内存里会生成一个新的MemTable来接收最新的键值数据。当然，新的数据在写入内存的MemTable前需要先写入磁盘中的日志文件（Log File），用于防止系统崩溃导致内存里的数据丢失。一个日志文件对应一个MemTable。当Immutable MemTable里的数据达到一定的阈值后，数据会被组织成一个个SSTable（sorted string table）文件刷写（flush）到磁盘中的Level 0。内存到Level 0的刷写操作在一些文献中也被称为微小合并（minor compaction）。
为了区分，LevelDB将Level 1到Level 2、Level 2到Level 3等的合并操作称为主要合并（major compaction）。通常意义上的“合并”默认指主要合并。LevelDB中所有Level的数据量都是有一定限制的，并且逐层之间的额定数据量是按照特定的参数呈指数级增长的。例如，Level 1中所有文件的大小总和为10MB，此时Level 2中的文件大小总和为100MB，它们之间的增长系数是10。一旦某个Level（ L i ）中的数据量到达预设的阈值，合并（compaction）线程就会从 L i 选择一个文件读入内存，然后在 L i +1 中选择出与该文件有key重叠的所有文件，将 L i 和 L i +1 选择的文件进行多路归并，合并成新的 L i +1 层文件。除了Level 0，LevelDB上的其他Level需确保每一层的所有数据都是全局有序的，即同一层内的任意两个SSTable文件之间不会存在数据重叠的部分。由于Level 0中SSTable直接是由内存的Immutable MemTable刷回的，因此，Level 0中的SSTable之间可能会存在数据重叠，但是Level 0中每个SST文件内的键值数据仍然是有序的。合并过程中需要访问LevelDB的元数据文件Manifest（需要先访问Current文件获取Manifest文件的访问信息）以获取所有SSTable和Level的元数据。
图4-8 LSM-tree的基本结构
LSM-tree通过将随机写转化为顺序写，大大提高了系统的写性能，但查询（包括点查询和范围查询）性能会有一定程度的下降，因为一次查询操作可能要遍历磁盘中的许多个不同的SST文件。当进行数据点查找操作时，LevelDB先对MemTable进行查找，然后是Immutable MemTable，最后是Level 0～Level 6，直到找到为止。一次点查询操作可能会读取磁盘的多个文件，Level 0中文件中key的范围是有重叠的，因此在Level 0执行查询操作时，可能需要读取多个文件，而Level 1～Level 6因为文件之间key的范围是不重叠的，每层只会读取一个文件。LevelDB严格控制了Level 0的文件数目，在写数据密集时控制写入的数据量，给系统充分的时间来调用后台的合并线程将Level 0的数据合并到Level 1，这在一定程度上降低了读操作的时延。
相应地，LSM-tree结构也存在一些问题。
1）LevelDB的合并操作会产生写放大。LevelDB除了Level 0外，每一层的数据都是全局有序的，这使查询操作的性能不至于太差。为了维持数据的有序排列，每一次数据的合并操作都必须有下一层数据参与。因为LevelDB相邻层之间的存储空间是10倍增长的（从Level 1～Level 6），所以理论上，同一大小范围的数据量，较高层将会是相邻低层数据量的10倍。当对某一层的一个SSTable文件进行合并操作时，合并线程会从该层选择一个SSTable文件读入内存，然后再读入下一层中与该SSTable文件有key重叠的所有文件，两者合并成新的SSTable文件存入下一层。此时，真实写入的数据量远远大于实际需要写入的数据量，这就是LevelDB合并操作造成的写放大。写放大系数是参加合并的数据量与生成的新的SSTable文件数据量的比值。当LevelDB存放的数据量变大时，任何文件都会通过一系列的合并操作从Level 1迁移到Level 6，所以LevelDB的写放大可能超过50倍。并且，随着数据量的增加，每个键值可能被多次合并，写放大会随着数据存储容量的增加而增加。
2）LevelDB的点查询操作会产生读放大。在执行合并操作前，LevelDB会预先把数据从设备读出来，产生大量的数据读取，这种放大一般被称作读放大。在LevelDB执行点查询操作读取数据时，当KV数据没有命中内存中的缓存（block cache），需要在设备上逐层查找，直到找到对应的数据。因为Level 0层的数据文件允许有key重叠，因此在查找Level 0当中的文件要依次查找符合范围的文件；当在Level 0层没有找到该数据时，LevelDB需要依次查询Level 1～Level 6的文件。读取设备上的多个文件导致了比较严重的读放大。
很多专家尝试减少LSM-tree的写放大，从而进一步提升LSM-tree键值数据库的写性能。优化写性能主要的方法为分区和分片。分区意味着每一层由多个互不重叠的分区构成，这样将每个大的合并操作划分成多个小型的分区合并操作。这样一方面可以减少执行合并操作所需要的磁盘空间，另一方面可以减少合并操作对磁盘资源的过度挤占，从而阻塞其他插入/查询操作。分片意味着每一层存在多个范围重叠的键值区域，每个区域内部是有序的。当采用分片机制时，当某一层发生合并时，并不需要与下层执行归并排序，而是将该层的所有分片执行归并排序，将排序后的分片作为一个新分片写入下层，从而将每次合并写放大从 T 下降到1（其中 T 为不同层间的大小比例）。
