LevelDB之整体架构

发表于 更新于

前言

前面介绍了 LevelDB 中的 Slice，编码和 SkipList 较为基础的组件和实现。本文将介绍下 LevelDB 的整体架构。

leveldb_architure

上图是一个比较简陋的架构图。只涉及到数据的读写，没有涉及到如版本控制，文件合并等。下文会按照每个模块稍微讲解下。

首先看下一个 demo 写入数据产生的文件:

1
2
3
4
5
6
7
8
9
10
000005.ldb
000006.ldb
000007.log
000008.log
000009.ldb
CURRENT
LOCK
LOG
LOG.old
MANIFEST-000004

其中 LOG 就是输出的系统日志文件

  • ldb 文件即 sstable 文件
  • log Log 日志，下文的 WAL 日志
  • CURRENT 存储的是当前的 MANIFEST 文件名称
  • LOCK 加锁，一个 leveldb 的数据库只能由一个进程打开
  • MANIFEST 主要保存的是版本数据
    • 这个文件算的上是一种特殊的 Log 日志文件，里面存储的是 Version 的数据，也就是每次 Version 发生变化都会写入到这个文件中，也是一个 WAL 日志。Version 暂时将他认为就是某一时刻，每一个 Level 中包含的文件等信息

Log

前面提到过 LevelDB 是一个 LSM-Tree，这种数据结构分为两种数据，一个是已经持久化到磁盘上的 SSTable，还有一个就是当前内存中的 SSTable，SSTable 就是 Sorted String Table，按照字符排序的数据。每次插入都是先插入内存，然后在时间或者空间的维度上设置阈值，超过阈值将内存中的刷入到磁盘。查询则是每次先查内存，然后去磁盘上查询。

因为服务端返回一般是写入到内存中就可以直接返回了，所以可能存在当前异常挂掉的时候内存数据丢失。也就是说需要一个系统崩溃后的恢复机制。只要涉及到类似的，先写内存然后异步刷磁盘的场景基本上都是需要这个机制的，这个机制就是 WAL(write-ahead log)，实现方式就是将可能对当前系统内部的数据变更的操作（增删改）操作先顺序写入到磁盘上，在出现系统异常推出后，可以通过读取这个日志将将数据恢复到开始阶段。

不过存在下面的情况，WAL 成功，没有执行操作的时候宕机，只能恢复到上一次完成操作的 WAL 日志位置，这也就意味这实际使用过程中，必须要有一个 ID 来标识当前的操作序列，便于恢复的时候不会返回原本已经报错写入失败的数据被恢复的情况。

LevelDB 中的数据没有删除的概念，删除的时候只是在当前的 Key 中设置一个墓碑标识，表示当前的数据已经被删除了，然后在后续文件合并的时候才会真正删除数据。所以基本上只涉及到曾和改，但是在 KV 数据库中，改也是一种增加，也就是直接覆盖原始数据。

Mem_Table 和 Immutable_Table

从命名可以看出。immutable_table 是一个不可变的 table。LevelDB 的操作是先将数据写入到 MemTable 中，MemTable 的实现就是一个 SkipList。等到 MemTable 中的数据到达容量阈值，一般是 4MB，就将他转换成不可变的 immutable_table 即只读不写的 SkipList。后面直接将 immutable_table 数据刷入到磁盘上，就是 level0 的数据了。

SSTable

SSTable 就是一个按找字符排好序的文件，但是仅仅存储值也是不够的。比如最开始写入了 Key_0，然后系统一直运行，而且后续在也没有插入新的 Key 为 Key_0 的值了，那么内存中肯定是没有数据的，必然会触发到文件中去找的需求。这里就遇到元数据的组织问题，即如何知道当前文件是处于那一层的，当前文件中包含了哪些 Key 值，在前面的 MANIFEST 文件内容中提到过，每一时刻当前的数据库都有一个对应的 Version，记录了当前数据库中每一层有哪些文件。

SSTable 文件写入后是不可变的，所以在合并的时候也是新建一个文件，然后将需要合并的数据合并成一个新的文件，必要的时候可能会将他的层级往下。

因为涉及到合并，Version 管理，不一一详细介绍，会在后面的 Version 和 合并等操作中解析。

总结下就是 SSTable 的文件组织是放在 Version 中，也就是某一时刻，当前的数据库有哪些文件，删除哪些文件等等信息会放在 Version，每次操作都会写入 MANIFEST 文件中。

但是每层的数据大小是不一定的，比如 Level0 层的数据是直接写入的 Mem_table,也即是 4MB，但是 Level1 层的大小是 10MB，而且并不是说一个完整的 10MB 的文件，而是分成 2MB 的文件。除了 Level0 以外的数据都是组织成 2MB 的文件，而且每一层都是上一层的 10 倍大小。

由于文件都需要合并，比如说当前 Level0 层和 Level1 层都是满的而且里面的 Key 各不相同，在合并的过程中可能就是需要读取 10+16MB，然后在写入 10+16 MB 的数据。

Others

其实在读取的过程中还会涉及到一个 LRUCache，但是个人觉得和总的架构来说只是一个缓存的左右，用于加快查询，所以没有在图上展示出来。

总结

本文非常粗糙的介绍了下 LevelDB 的整体结构。