leveldb 的基本原理

背景

leveldb 是一个持久化的键值存储数据库引擎。google 将 leveldb 和 paxos 结合，搞出了一个分布式存储系统 bigTable。

技术组成

SSTable

SSTable 即排序字符串表，是一个包含按键排序的键值对序列的文件。一旦 SSTable 被写入到磁盘文件后，就不可以修改了。如果需要修改，只能用新的 SSTable 文件覆盖旧的 SSTable 文件。

MemTable

MemTable 就是一个在内存中的 SSTable。在 leveldb 中，MemTable 使用跳表来实现。对于跳表，我们以任意顺序插入键值对，遍历时按顺序读取键值对就可以读到一个有序键值对序列。理想情况下，跳表的修改、查找的时间复杂度是 log(n)。

写入

leveldb 将新增、更新、删除操作都看成是添加操作，分为几个步骤：

先将添加的数据写到一个日志文件中，用于系统崩溃重启后重新构建 MemTable，可以防止系统宕机时丢失最近（已在MemTable，但还未写入磁盘）的数据。
将数据添加到 MemTable。如果 MemTable 的大小超过某个阈值，就将当前 MemTable 转为 Immutable MemTable，之后创建一个新的 MemTable 用以应对后续的写入请求。当 dump 指令下达之后，会将 Immutable MemTable 写入成 SSTable 文件进行存储。

leveldb 将新增、更新、删除操作都看成是添加操作。对于更新、删除操作，如果原数据在 MemTable 中，那么直接修改 MemTable 就行；如果不在，就需要找到原数据所在的 SSTable，然后进行修改，最后覆盖原来的 SSTable。这个过程会耗费大量的磁盘IO资源。所以，在 leveldb 中，更新操作直接在 MemTable 新增一条记录，后台合并 SSTable 时会自动覆盖旧值；删除操作直接在 MemTable 新增一条记录，用以标记删除，后台合并 SSTable 时如果后续没有新增该键值对，就会丢弃该键值对。

读取

leveldb 读取数据分为几个步骤：

先在 MemTable 中查找数据
如果没有，再在 Immutable MemTable 查找，因为 Immutable MemTable 还未写入磁盘。
按层级查找 SSTable，先查找 Level0 的 SSTable，再查找 Level2 的 SSTable，直到最后一层的最后一个文件。

层级压缩

Level 0

每处理一个用户请求，日志文件就会多出一条日志记录。所以，日志文件会越来越大，直到超过一个固定大小（默认1MB）,

将 memtable 的内容写到一个不可修改的 sstable 文件中（存储在磁盘上）
添加这个新的 sstable* 到 Level-0

当 Level-0 的文件数量达到某个阈值时（当前是4），Level-0 的所有文件将与 Level-1 中（和 Level-0 ）重叠的文件合并，生成一系列新的 Level-1 文件（Level-1 中每个文件的大小为2MB）。

Level-0 的特殊之处在于：处于 Level-0 的 sstable 的 key space 可能是互相重叠的。

Level >= 1

Level >= 1 ：处于同一层级的 sstable 的 key space 不会重叠。

当 Level-T 的大小超过它的限制时，我们就会在一个后台线程中压缩它。这个压缩线程会从选择 Level-T 的某个文件和 Level-(T+1) 中重叠的所有文件，然后合并它们，生成一系列新的 Level-(T+1) 文件。每个文件大小默认是2MB。

核心原理

核心原理：通过将随机写入转化为顺序写入，提高写入操作的吞吐量。