LevelDB 学习备忘

LevelDB 设计出发点

LevelDB 是一个轻量级，写优先，批量读，硬盘存储的K-V嵌入式数据库，这是其许多设计和优化的出发点。为了保证读性能中查找操作的可用性，一段数据必须要被有序地放入到数据库中，并且最优的算法复杂度是固定的——O(nlogn)，这意味着数据被放入预定位置延迟是具有最小值的，即写操作必定会具有固定的延迟。LevelDB 的设计就是如果合理地利用结构来优化这个延迟，来获得最小的写入延迟，核心技巧就是将数据写入数据库的操作分解，并且尽可能地将操作放入后台线程中运行，以此来获得最小的用户输入延迟，从而获得优异的批量写入性能，并且同时保证一定的读性能。

LevelDB 的典型应用之一是作为临时存储——在本地临时存储用户的工作数据，当工作确认提交后再整体发送给其他数据库。

LevelDB 的写入延迟优化

不同于其他的单机数据库形式，LevelDB 的设计更多地用于嵌入式数据库，因此必须要保证数据库的系统资源占用较小。LevelDB 的写入延迟优化的核心思想是进行数据写入操作的分解，牺牲一定的总操作时间，来换取每一步操作的低延迟，从而实现较低的用户操作延迟以及较低的系统资源占用。

总体来看，LevelDB 中数据的写入流程可以被分解为：

WAL 日志：目的为获得低用户写入延迟
批写入缓冲：目的为获得较少的线程同步次数
内存缓冲表：目的为优化用户修改近期数据的需要
SSTFile 以及合并：目的为减少系统占用，优化读性能

WAL 日志

虽然将数据有序地写入数据库中的延迟最小是 O(nlogn)，但是只是将数据持久化到硬盘中的延迟只有 O(1)。利用 WAL 操作，用户调用 Put()操作时，操作被追加到 WAL 文件中即可对用户操作返回成功。实际设计中，LevelDB 将操作记录到内存缓冲区后，再写入到 WAL 文件中，后台线程会根据内存缓冲区完成后续的数据写入操作。由于 WAL 文件流时追加形式，并且是持续打开的，不需要寻址，因此该速度非常快。

批写入缓冲

在 LevelDB 中，具有一个缓冲区用于存储用户的写入操作。只有当该缓冲区满时，或者经过一段时间后，后端线程才会将该缓冲区中的数据真正写入到内存中的跳跃表中。这一设计主要的优点如下：

优化跳跃表写入时间：跳跃表写入操作需要进行查找，查找操作是插入延时的主要原因。利用批写入缓冲，可以将用户的 N 个操作根据键值进行排序，在进行跳跃表写入时，最坏情况下只需要从头遍历一次跳跃表，大大节约了查找的时间。
符合用户操作习惯：用户在执行插入操作时，可能会在短期内多次更新同一个值，这样可以将多次插入操作合并为一次。
优化线程同步：跳跃表是需要由多个后台线程共享的（插入线程，持久化线程，读取线程），执行写入操作时是需要进行加锁的。执行批写入时，写入时间更短，获取锁的时间更短，同时唤醒其他线程的时机也更少，对线程同步是有益的。

批量写入也有一定的弊端，主要是数据库宕机时会增加恢复时间，但总体来说对数据库性能的影响很小。

MMAP (跳跃表)

mmap 主要是实现了缓冲区的功能，将多次写入硬盘的操作合并为一次写入。由于操作系统的调度机制，频繁进行 IO 的线程优先级是比较低的，线程频繁进行 IO 操作会浪费很多时间在调度上。同时，使用内存缓冲区时，可以将整个表进行数据压缩操作，节约硬盘的存储空间。

跳跃表是一个综合来看比较优异的数据结构。对比跳跃表、哈希表、红黑树三种典型的数据结构，哈希表并不是一种顺序容器，在迭代操作的时候可能会遇到问题（迭代器失效），红黑树的插入操作因为涉及到旋转，时间常数会比较高，插入性能略差。而跳跃表可以提供顺序迭代访问，并且插入数据时比较简单，很容易实现无锁结构，易于并发访问，因此 LevelDB、Redis 等一些内存数据库经常会使用跳跃表进行缓存操作。

MMAP 的惰性删除机制：在引入惰性删除机制前，对跳跃表的操作需要分为四类：读、写、删除、修改。其中，写、删除操作因为涉及链表的重构，是需要写并发控制才能够运行的；而另外两种操作，并不涉及到链表内部节点的修改，只需要将值设置为原子量就可以进行并发访问了。在引入惰性删除机制后，通过修改节点的标志量来标记删除，当 MMAP 持久化时再删除节点，这样就将删除操作变更为了修改操作，能够大大提升对内存表的并发访问量。

SSTFile

为了保证读性能的可用性，必须将键值对放入预期的位置。如果数据库简单地将所有数据在硬盘中有序排列，那么每次将 MMAP 中的数据插入到硬盘的操作时间复杂度就是 O(nlogn)，但是这样会导致一次插入操作的系统占用过高。LevelDB 设计了一套分层存储机制来代替传统的存储机制。

SSTFile 是数据在硬盘中的组织形式，不同的 SSTFile 分为不同的层级（ 0 - n ），文件内部的键值对是有序排列的，Level 0 之外的文件在层级之间也是有序排列的。每次 MMAP 中的数据需要持久化时，会生成一个 Level 0 的 SSTFile，如果一个 Level 对应的文件数量过多会触发合并操作。这样设计，高层级的数据是有序的旧数据，低层级因为单个文件数据量很小，因此无序存储也不会过多地影响系统的读性能。每次进行读取操作时，从低层次往高层次进行查找，直到找到数据。

很显然，这种设计会造成写扩大：同样的数据被写入硬盘多次才保证了全局一致性；但是这种写扩大是被分摊到多个不同的时间节点的，虽然总的写入时间加大了，但是却能够确保每个时间点的系统占用很小。因为 SSTFile 的合并是被动的，数据库只会惰性地检查每个层级是否满足合并条件，并且确保一次只存在一个合并操作；此外，如果一次合并操作花费过多的时间，那么数据库还会中断本次操作并选择延迟执行，以防止MMAP 不能及时持久化到硬盘中。

修改和删除数据

由于数据库采用层级的查找机制，当用户需要进行旧数据的修改时（MMAP 中数据并不存在）；LevelDB 其实并不会对文件中的数据进行查找，而是直接将新的数据写入到 MMAP 中，并不需要删除掉旧数据。因此，在 LevelDB 中，修改操作其实已经退化为了写入操作。同样地，删除操作也只会在 MMAP 中查找数据，若未查询到数据，则会在 MMAP 中插入一条删除记录。

这种优化是因为 LevelDB 面向的应用场景中，用户更加倾向于频繁修改最近的数据，而旧数据的修改可能只会零散的发生，因此额外的硬盘占用量是很小的。

LevelDB 的读取优化

LevelDB 是一个批处理的数据库系统，这种应用场景下，读取操作是具有显著特征的。

用户可能会多次修改最近的数据，如不小心输入错误的数据。
对于旧的数据，用户可能会批量读取并进行操作。

由于 LevelDB 本身存在两个缓冲区，因此已经满足了修改最近数据的需求，基本上只有对旧数据的读取需要进行大规模优化。

文件索引与布隆过滤器

文件索引是一个经典的文件读取优化模式。在 LevelDB 中，每个 SSTFile 都会在内存中保留一个索引，索引包含了数据日期，最大键值、最小键值、最近操作时间、最近读取次数等一系列信息。如果 MMAP 中没有查询到用户需要的数据，那么就会触发对 SSTFile 的查找，在每个高层级中键值是有序的，因此可以在层级中对键值对执行二分查找；对于无序的Level 0 数据，因为文件数量很小，执行顺序查找也不会有较高的性能损失。

通过键值范围确定可能的 SSTFile 文件后，LevelDB 还需要通过布隆过滤器来保证该数据存在的可能性；只有成功通过布隆过滤器，数据库才会将文件读取到内存中。同样，文件的内部也是有序的，同样可以执行二分查找，降低查找的时间复杂度。被读取到内存中的文件会缓存一段时间，以此来应对用户多次读取同一段数据的需要。

版本控制 MVCC

LevelDB 中写入操作是直接写入到最上层级的，并不会被读操作读到，因此唯一可能出现的冲突是 SSTFile 合并操作与读操作的冲突，使用简单的 MVCC 并发控制就可以避免冲突。

执行读操作时，LevelDB 会将对应文件的引用量加一；当执行迭代器操作时，会将当前全部文件标注引用。当合并操作被触发，原有的文件需要删除时，根据文件的引用量来判断是否真正执行删除操作；若引用不为 0，则进行惰性删除机制，当引用为 0 时再自动触发删除操作。

迭代器遍历操作

LevelDB 的读场景存在大量的批量读取，使用迭代器进行数据库的遍历有助于用户简化代码。但由于 LevelDB 中修改和删除操作并不会真正地删除掉旧数据，因此在遍历数据库时必须采取一定措施来防止用户读取过期数据。

LevelDB 中只提供全局有序的迭代器操作，并且能够保证数据的有效性。具体做法为：在每个 Level 上都创建一个内部迭代器，当调用迭代器 MoveNext()操作时，使用类似归并的思想进行操作，这样就能够消除过期数据带来的影响。同时，在创建一个迭代器时，会自动创建一个快照，快照只记录需要访问的文件并声明引用，并不会直接复制数据。

防止读扩大

LevelDB 的层级读取机制并不能很好地处理一种情景：用户短时间内需要频繁读取一段老数据。该情况下，每次都需要从头开始查找，会消耗过多的查询时间，同时还会造成读取的文件过大，这是需要进行优化的。具体的优化措施为：开辟一片最近读内存缓冲区，将最近读取过的数据存入缓冲区中。缓冲区采用一定的置换策略，并且保证在缓冲区内被多次读取的数据会被持久化到 Level 0 中。

LevelDB 的系统占用优化

当 LevelDB 作为嵌入式数据库使用时，必须要保证较低的内存和 CPU 占用来维持整体软件的性能。类似于写入操作，LevelDB 完成相应功能的总时间也是具有优化上限的，只有采用分割任务的方法，才能保持长时间的低系统占用。

内存池与 Slice

LevelDB 内部的内存分配是使用内存池进行分配的，内存池具有效率高、能够避免系统级内存碎片的优点。数据库进程如果只是使用系统调用来简单分配内存，不仅会出现内存频繁申请和销毁的情况，长时间运行还会造成系统级内存碎片，导致系统可用内存下降。

使用内存池会引入较为繁琐的内存管理，因此 LevelDB 引入 Slice 数据结构来简化内存分配。 Slice 是字符串指针和字符串长度的集合，LevelDB 中的所有数据段底层都被存储为 Slice 格式，所有内存申请都是建立在内存池的基础上的，并且会尽量保证持有的内存区域尽可能小。

SSTFile 合并

SSTFile 合并操作会评估当前数据库的系统占用情况，并且会保证一次合并操作并不会持续过长时间。如果一次合并操作耗时过长，该合并操作会被中断，并且选择合适的时机再次执行。