LevelDB 使用 WAL（Write-Ahead Logging）日志来确保数据的持久性。当写入操作发生时，LevelDB 首先将数据写入到日志文件中，然后再应用到内存中的数据结构（如 MemTable）。系统或数据库崩溃后重新启动时，LevelDB 会检查 WAL 日志文件中的记录。通过读取并重放这些日志记录，LevelDB 可以重建那些在崩溃发生时还未被完全写入磁盘的数据状态。

整个 WAL 日志相关的操作流程如下：

1. LevelDB首先将数据写入WAL日志。确保即使在系统崩溃的情况下，数据也不会丢失。
2. 数据被写入内存中的MemTable，这个是内存操作，很快。
3. LevelDB向客户端确认写入完成。
4. 随着时间推移，当MemTable满了之后，它会被刷新到磁盘上的SSTable文件中。
5. 一旦MemTable被成功刷新到SSTable，相应的WAL日志就可以被清除了。

接下来详细看看这里的实现。

LevelDB 整体代码还是比较好懂，没有用很多 C++奇淫技巧。不过还是有部分实现，相当比较少见，比如柔性数组、链接符号导出、Pimpl 类设计等。本文会梳理这里的 C++ 高级技巧，帮助更好地理解 LevelDB 的实现。

柔性数组

在 util/cache.cc 的 LRUHandle 结构体定义中，有一个柔性数组(flexible array member) char key_data[1]，用来在 C/C++ 中实现可变长数据结构。

1
2
3
4
5
6
7
8
9

struct LRUHandle {
  // ...
  char key_data[1];  // Beginning of key

  Slice key() const {
    assert(next != this);
    return Slice(key_data, key_length);
  }
};

LevelDB 中数据存储在 SSTable 文件中，当用 Get() 来查询 key 的时候，可能需要从 SST 文件中读取多个块。为了减少磁盘读取，LevelDB 提供了 FilterPolicy 过滤策略，如果判断出来一个 Key 不在当前 SSTable 文件中，那么就可以跳过读取该文件，从而提高查询效率。

LevelDB 支持用户自定义过滤策略，不过提供了一个默认的布隆过滤器实现。布隆过滤器是一种空间效率极高的数据结构，用于判断一个元素是否存在于一个集合中，有一定的误判率但没有漏判。简单说就是如果布隆过滤器判断一个元素不存在，那么这个元素一定不存在；如果布隆过滤器判断一个元素存在，那么这个元素可能不存在。