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

LevelDB 是 C++ 开发的优秀的 LSM Tree 的存储组件，整体代码量不大，但是设计精巧，值得学习。在阅读源码过程中，整理了系列文章，逐步拆解 LevelDB 的实现细节。不过在阅读代码前，最好先准备好整个开发环境。

本文会从最基本的拉取代码开始，记录自己准备整个环境的过程，包括配置 VSCode IDE 和 clangd 插件使用，以及如何配置编译选项等。然后会通过简单的读写代码 demo，来简单使用下 LevelDB，对这个库有个感性的认识。另外，还会介绍如何运行测试用例，LevelDB 的测试用例写的很好，在代码阅读过程中，可以借助用例更好的理解代码。