LevelDB 中实现了不少 utils 工具，比如定制的内存分配器 Arena，随机数生成类 Random，实现中都会考虑到具体的使用场景，做了优化以及取舍，值得好好学习。本篇文章主要聊聊下面部分的实现：

• 内存管理 Arena，一个简单高效，适合 LevelDB 的内存分配管理器；
• 随机数 Random，一个不错的线性同余伪随机生成算法，用位运算替代取模优化了执行效率。
• CRC32 循环冗余校验，用于检测数据传输或存储过程中是否发生错误；
• 整数编、解码，用于将数字存储在字节流或者从字节流中解析数字。

此外，还有些 utils 组件比较复杂些，会放在单独的文章里聊，比如：

• LevelDB 源码阅读：禁止对象被析构 讲在 C++中如何禁止某个对象被析构，以为这样做的原因。

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);
  }
};