Just For Fun的 RSS 预览

LevelDB 源码阅读：一步步拆解 SSTable 文件的创建过程

2025-06-28 05:00:00

LevelDB 中，内存表中的键值对在到达一定大小后，会落到磁盘文件 SSTable 中。并且磁盘文件也是分层的，每层包含多个 SSTable 文件，在运行时，LevelDB 会在适当时机，合并、重整 SSTable 文件，将数据不断往下层沉淀。

这里 SSTable 有一套组织数据的格式，目的就是保证数据有序，并且能快速查找。那么 SSTable 内部是怎么存储这些键值对的，又是怎么提高数据的读、写性能的。以及整个 SSTable 文件的实现中有哪些优化点？

本文接下来我们会仔细分析 SSTable 文件的创建过程，一步步拆解来看看这里到底怎么实现的。在开始之前，我先给一个大的图，大家可以先留个印象。

SSTable 文件格式设计原因

在开始之前，我们要先搞明白一个关键问题，文件格式该如何设计，才能兼顾高效写入和快速读取？ 下面我们从几个基本问题出发，来推测作者是如何设计这里的数据格式。

问题一：键值对该如何存放？

首先，最核心的数据，也就是用户的键值对，得有个地方放。最简单的方法，把所有键值对按顺序放进 SSTable 这整个大文件。这样有什么问题呢？首先读的时候，如果要找一个 key，需要遍历整个大文件。然后写入过程中，每次添加一个键值对就要写磁盘的话，写 IO 压力会很大，吞吐上不去。

既然太大了不行，那就分块吧。计算机科学中的”分而治之”思想，在 LevelDB 中得到了很好的体现。我们把大文件切分成不同的数据块，按照数据块的粒度来存储键值对。每个块默认大约 4KB。当一个块写满了，就把它作为一个整体写入文件，然后再开始写下一个。这样整体写入的时候，就会减少很多磁盘 IO 了。

这里我再多说一点，分块存储不仅减少了写入磁盘的 IO 次数，通过配合

不过查找问题还没解决，还是要遍历所有的块来查找键值。

要是我们能快速定位到键值在哪个 DataBlock 里，那就只用遍历单个块就好了，效率会提升很多。

问题二：如何快速定位到某个 Data Block？

为了解决这个问题，我们需要一个”目录”。计算机中也叫索引，于是 Index Block (索引块) 诞生了。这个块里存放了一系列的索引记录，每个记录都记录一个 Data Block 的信息，根据这个记录，我们能快速知道某个键所在的 DataBlock。

这样查找键值的时候，只需要在 Index Block 中二分查找，就能快速定位到键值可能在的 DataBlock。索引块只包含一些索引数据，所以整体大小会小很多，通常可以加载到内存中去，所以查找会快很多。

有了索引块之后，我们把扫描整个文件变成了”查索引 -> 精准读取一小块”的操作，效率会大大提升。这里索引具体怎么设计我们先不管，后面再详细分析。

问题三：如何避免无效的磁盘读取？

通过索引块，我们其实能找到 key 可能在哪个块，但它不能百分百确定。为什么呢？因为索引块里记录的只是 key 的区间，并不能保证 key 一定在这个区间里，后面结合代码理解会更清晰。这就导致一个问题，当我们兴冲冲地把 Data Block 从磁盘读到内存后，却发现要找的 key 根本不存在，这不就白白浪费了一次宝贵的磁盘 I/O 吗？尤其是如果业务中，有大量读不存在 key 的场景，那么这种浪费很可观。

这种判断不存在的需求，计算机科学中早就有解法了，常见的就是布隆过滤器。布隆过滤器是位数组和哈希函数的组合，可以快速判断一个元素是否在集合中。本系列之前的文章LevelDB 源码阅读：布隆过滤器原理、实现、测试与可视化中，有详细介绍布隆过滤器的原理和实现。

LevelDB 中，用同样的解决思路，它支持设置一个可选的过滤块(Filter Block)，在读取 Data Block 之前，先通过 Filter Block 确认键是否存在。如果不存在的话，直接返回，如果可能在，再读取 Data Block 进行确认。通过这种方式，我们极大地减少了对不存在的 key 的无效查询。

看起来一切很美好了，不过等下，还有个问题，我们怎么知道 Index Block 和 Filter Block 在 SSTable 文件的哪个位置呢？

问题四：如何定位索引和过滤块？

现在我们有很多数据块、一个 Index Block、一个 Filter Block。问题又来了：当我们打开一个 SSTable 文件时，我们怎么知道 Index Block 和 Filter Block 在文件的哪个位置呢？

最朴素的思路就是可以把这些元信息放到文件的固定偏移位置。不过如果放到文件头的话，这些记录发生变化的话，整个文件的数据都要移动，这显然不行。

那放文件末尾呢？看起来可行，LevelDB 也是这么设计的。在文件尾部，放一个固定 48 字节的 Footer 区域，里面记录了 Index Block 在文件的偏移位置，以及另一个之前没提到过的 Meta-Index Block 的位置。

这里按理说 Footer 记录 Index Block 和 Filter Block 的位置就行了，为啥引入一个 Meta-Index Block 呢？作者在代码注释里有提到过，主要为了扩展性。Footer 的大小固定，不能增加更多信息了，那万一未来有更多种类的元数据块，比如统计块等，要在哪里存偏移。

所以作者增加了一个元数据的索引——Meta-Index Block。这个块的作用就是一张元数据目录，它的键是元数据的名字（如 “filter.leveldb.BuiltinBloomFilter2”），值是对应元数据块（如 Filter Block）的偏移位置。当前只有过滤块信息，后续可以任意增加元数据块。

这样整个查找过程就串起来了，先拿出尾部 48 字节的固定内容。从里面解析出 Index Block 和 Meta-Index Block 的偏移位置，然后从 Meta-Index Block 中拿到 Filter Block 的偏移位置，最后根据偏移位置读取 Filter Block 的内容。有了 Index Block 和 Filter Block，我们就能快速、高效地”按图索骥”去查找键值了。

答案: SSTable 结构图

前面已经把 SSTable 中数据块组织方式分析完了，这里我画一个简单的 ASCII 图来描述 SSTable 中的各个块，方便大家理解：

+-------------------+
|   Data Block 0    |
+-------------------+
|   Data Block 1    |
+-------------------+
|       ...         |
+-------------------+
|   Data Block N    |
+-------------------+
|   Filter Block    |  (可选) <-- 由 Meta-Index Block 索引
+-------------------+
| Meta Index Block  | <-- 由 Footer 索引
+-------------------+
|   Index Block     | <-- 由 Footer 索引
+-------------------+
|      Footer       | (文件末尾，固定大小)
+-------------------+

不过要怎么提供接口，怎么把键值对保存为上面格式，还是有不少工程细节的。这里顺便说下，LevelDB 代码中的分层抽象是做的真好，一层套一层，把复杂逻辑封装起来，方便理解和维护。比如每个块自己是怎么构建数据的，都封装了单独的实现，后面我会在其他文章里详细说明。

本篇文章，咱们重点关注 SSTable 文件构建的工程细节部分。这部分实现在table/table_builder.cc 中，主要就是 TableBuilder 类。

该类只有一个私有成员变量，是一个 Rep* 指针，里面保存各种状态信息，比如当前的 DataBlock、IndexBlock 等。这里 Rep* 用到了 Pimpl 的设计模式，可以看本系列的 LevelDB 源码阅读：理解其中的 C++ 高级技巧了解关于 Pimpl 的更多细节。

该类最重要的接口有 Add，这个函数会层层调用其他一些封装好的函数，来完成键值对的添加。接下来从这个接口入手，分析 TableBuilder 类的实现。

Add 添加键值对

TableBuilder::Add 方法是向 SSTable 文件中添加键值对的核心函数。添加键值对，需要更改上面提到的 DataBlock、IndexBlock、FilterBlock 等各个块。这里为了提高效率，有不少工程优化细节，为了更好理解，我把它主要分 4 部分，这里一个个来说吧。

void TableBuilder::Add(const Slice& key, const Slice& value) {
  // 1. 前置校验
  // 2. 处理索引块
  // 3. 处理过滤块
  // 4. 处理数据块
  // 5. 适当时机落盘
}

前置校验

在 Add 方法中，首先会先读出来 rep_ 的数据，做一些前置校验，比如验证文件没有被关闭，保证键值对是有序的。

Rep* r = rep_;
assert(!r->closed);
if (!ok()) return;
if (r->num_entries > 0) {
  assert(r->options.comparator->Compare(key, Slice(r->last_key)) > 0);
}

LevelDB 在代码中 加了不少校验逻辑，确保如果有问题，早崩溃早发现，这个理念对于底层库来说，还是很有必要的。Add 方法这里 assert 校验后面插入的键值对永远都是更大的，当然这点需要调用方来保证。为了实现校验逻辑，在每个 TableBuilder 的 Rep 中，都保存了 last_key，用来记录最后一个插入的 key。这个 key 在索引键优化的时候会用到，后面会详细说明。

处理索引记录

接着会在适当时机添加新的索引。我们知道索引记录用来快速查找一个 key 所在的 DataBlock 偏移位置，每一个完整的 DataBlock 对应一个索引记录。我们先看看这里添加索引记录的时机，当处理完一个 DataBlock 时，会将 pending_index_entry 设置为 true，等到下次新的 DataBlock 增加第一个 key 时，再更新上个完整的 DataBlock 对应的索引记录。

这部分的核心代码如下：

if (r->pending_index_entry) {
  assert(r->data_block.empty());
  r->options.comparator->FindShortestSeparator(&r->last_key, key);
  std::string handle_encoding;
  r->pending_handle.EncodeTo(&handle_encoding);
  r->index_block.Add(r->last_key, Slice(handle_encoding));
  r->pending_index_entry = false;
}

这里之所以要等到新 DataBlock 增加第一个 key 的时候才更新索引块，就是 为了尽最大程度减少索引键的长度，从而减少索引块的大小，这也是 LevelDB 工程上的一个优化细节。

这里扩展讲下背景可能更好理解，SSTable 中每个索引记录都由一个分割键 separator_key 和一个指向数据块的 BlockHandle（偏移量+大小）组成。这个 separator_key 的作用就是划分不同 Datablock 的键空间，对于第 N 个数据块（Block N），它的索引键 separator_key_N 必须满足以下条件：

separator_key_N >= Block N 中的任何键
separator_key_N < Block N+1 中的任何键

这样在查找一个目标键的时候，如果在索引块中找到第一个 separator_key_N > target_key 的条目，那么 target_key 如果存在，就必定在前一个数据块（Block N-1）中。

直观上讲，索引最简单的实现是直接用 Block N 的最后一个键（last_key_N）作为 separator_key_N。但问题是，last_key_N 本身可能非常长。这就导致索引项会很长，进而整个索引块变得很大。索引块通常需要加载到内存中，索引块越小，内存占用越少，缓存效率越高，查找速度也越快。

其实我们细想下，我们并不需要一个真实存在的键作为分割索引 key，只需要一个能把前后两个块分开的”隔离键”即可。这个键只需要满足：last_key_N <= separator_key < first_key_N+1。LevelDB 就是这样做的，这里通过调用 options.comparator->FindShortestSeparator，找到前一个块最后的键，和下一个块第一个键之间最短分割字符串。这里 FindShortestSeparator 的默认实现在 util/comparator.cc中，本文不再列出来了。

为了更清楚地理解这个优化过程，下面用一个具体的例子来演示：

最后再聊下这里每条索引记录的 value，它是该块在文件内的偏移和 size，这是通过 pending_handle 来记录的。当通过 WriteRawBlock 将 DataBlock 写文件的时候，会更新 pending_handle 的偏移和大小。然后写索引的时候，用 EncodeTo 将偏移和 size 编码到字符串中，和前面的索引 key 一起插入到 IndexBlock 中。

处理过滤记录

接着处理 FilterBlock 过滤索引块，前面的索引块只是能找到键应该在的块的位置，还需要去读出块的内容才知道键到底存不存在。为了快速判断键值在不在，LevelDB 支持了过滤索引块，可以快速判断某个 key 是否存在于当前 SSTable 中。如果设置用到过滤索引块，则在添加 key 的时候，同步添加索引，其核心代码如下：

1
2
3

if (r->filter_block != nullptr) {
  r->filter_block->AddKey(key);
}

这里添加 key 之后，只是在内存中存储索引，要等到最后 TableBuild 写完所有的 Block 之后，才会将 FilterBlock 写入文件。FilterBlock 本身是可选的，通过 options.filter_policy 来设置。在初始化 TableBuilder::Rep 的时候，会根据 options.filter_policy 来初始化 FilterBlockBuilder 指针，如下：

Rep(const Options& opt, WritableFile* f)
    : options(opt),
      // ...
      filter_block(opt.filter_policy == nullptr
                       ? nullptr
                       : new FilterBlockBuilder(opt.filter_policy)),
      pending_index_entry(false) {
  // ...
}

这里值得注意的是 filter_block 之所以是指针，主要是因为除了用默认的布隆过滤器，还可以用多态机制使用自己的过滤器。这里用 new 在堆上创建的对象，为了防止内存泄露，在 TableBuilder 析构的时候，先释放掉 filter_block，再接着释放 rep_。

TableBuilder::~TableBuilder() {
  assert(rep_->closed);  // Catch errors where caller forgot to call Finish()
  delete rep_->filter_block;
  delete rep_;
}

之所以需要释放 rep_，是因为它是在 TableBuilder 构造的时候，在堆上创建的，如下：

TableBuilder::TableBuilder(const Options& options, WritableFile* file)
    : rep_(new Rep(options, file)) {
  if (rep_->filter_block != nullptr) {
    rep_->filter_block->StartBlock(0);
  }
}

关于 LevelDB 默认的布隆过滤器实现，可以参考LevelDB 源码阅读：布隆过滤器的实现。索引块的构建，后面我单独写一篇来详解，这里我们也不深究细节部分。

处理数据块

接着需要将键值对添加到 DataBlock 中。DataBlock 是 SSTable 文件中存储实际键值对的地方，代码如下：

r->last_key.assign(key.data(), key.size());
r->num_entries++;
r->data_block.Add(key, value);

const size_t estimated_block_size = r->data_block.CurrentSizeEstimate();
if (estimated_block_size >= r->options.block_size) {
  Flush();
}

这里调用 BlockBuilder 中的 Add 方法，将键值对添加到 DataBlock 中，关于 BlockBuilder 的实现，后面单独文章来描述。哈哈，这里 LevelDB 分层抽象是做的真好，搞的我们的文章也只能分层了。每次添加键值对后，都会检查当前 DataBlock 的大小是否超过了 block_size，如果超过了，则调用 Flush 方法将 DataBlock 写入磁盘文件。这里 block_size 是在 options 中设置的，默认是 4KB。这个是键值压缩前的大小，如果开启了压缩，实际写入文件的大小会小于 block_size。

// Approximate size of user data packed per block.  Note that the
// block size specified here corresponds to uncompressed data.  The
// actual size of the unit read from disk may be smaller if
// compression is enabled.  This parameter can be changed dynamically.
size_t block_size = 4 * 1024;

这里 Flush 怎么写磁盘呢，我们接着往下看。

Flush 写数据块

在前面的 Add 方法中，如果一个块的大小凑够 4KB，就会调用 Flush 方法写磁盘文件。Flush 的实现如下：

void TableBuilder::Flush() {
  Rep* r = rep_;
  assert(!r->closed);
  if (!ok()) return;
  if (r->data_block.empty()) return;
  assert(!r->pending_index_entry);
  WriteBlock(&r->data_block, &r->pending_handle);
  if (ok()) {
    r->pending_index_entry = true;
    r->status = r->file->Flush();
  }
  if (r->filter_block != nullptr) {
    r->filter_block->StartBlock(r->offset);
  }
}

开始部分也就是一些前置校验，注意 Flush 只是用来刷 DataBlock 部分，如果 data_block 为空，就直接返回。接着调用 WriteBlock 方法(后面详解)将 DataBlock 写入文件，然后更新 pending_index_entry 为 true，表示下次添加 key 时，需要更新索引块。

最后调用 file->Flush() 将目前内存中的数据调用系统 write 写磁盘，注意这里不保证数据已被同步到物理磁盘。数据可能还在系统缓存中，如果操作系统宕机，那有可能丢失没写入成功的数据。这里写文件刷磁盘，可以参考本系列LevelDB 源码阅读：Posix 文件操作接口实现细节中关于文件操作的更多细节。如果有 filter_block，还需要调用 StartBlock 方法，这个方法也比较有意思，等后面我们专门来写 filter block 的时候再详细说明。

WriteBlock 写文件

上面提到 Flush 中会调用 WriteBlock 方法将 DataBlock 写入文件，该方法在下面要提到的 Finish 中也会被调用，用来在最后写索引块，过滤块等内容。WriteBlock 的实现比较简单，主要用来处理压缩逻辑，然后调用真正的写文件函数 WriteRawBlock 来把块内容写入文件。

压缩并不是必须的，如果调用 leveldb 时设置了需要压缩，并且链接了压缩库，就会选择对应的压缩算法对 Block 进行压缩。LevelDB 这里也做了一点压缩性能和效果的平衡，如果压缩比 (compression_ratio) 小于等于 0.85，就会将压缩后的数据写入文件，否则直接写入原始数据。真正写文件部分，调用 WriteRawBlock 方法，主要代码如下：

void TableBuilder::WriteRawBlock(const Slice& block_contents,
                                 CompressionType type, BlockHandle* handle) {
  Rep* r = rep_;
  handle->set_offset(r->offset);
  handle->set_size(block_contents.size());
  r->status = r->file->Append(block_contents);
  if (r->status.ok()) {
    char trailer[kBlockTrailerSize];
    trailer[0] = type;
    uint32_t crc = crc32c::Value(block_contents.data(), block_contents.size());
    crc = crc32c::Extend(crc, trailer, 1);  // Extend crc to cover block type
    EncodeFixed32(trailer + 1, crc32c::Mask(crc));
    r->status = r->file->Append(Slice(trailer, kBlockTrailerSize));
    if (r->status.ok()) {
      r->offset += block_contents.size() + kBlockTrailerSize;
    }
  }
}

这里在每个块的尾部放了 5 个字节的 trailer 部分，来对数据准确性进行校验。第一个字节是压缩类型，目前支持的压缩算法有 snappy 和 zstd。后面 4 字节是 crc32 校验和，这里用 crc32c::Value 计算数据块的校验和，然后把压缩类型一起计算进去校验和。这里 crc32 部分，可以参考本系列 LevelDB 源码阅读：内存分配器、随机数生成、CRC32、整数编解码了解更多细节。

Finish 主动触发落盘

上面的所有操作，主要用来将键值对不断添加到数据块中，这个过程如果达到 DataBlock 的大小限制，会触发 DataBlock 的落盘。但整个 SSTable 文件还有索引块，过滤块等，需要主动触发落盘。那在什么时机触发，又是怎么落盘呢？

LevelDB 中产生 SSTable 文件的时机有很多，这里以保存 immetable 时候触发的落盘时机为例。将 immemtable 保存为 SSTable 文件时，过程如下：首先迭代 immemtable 中的键值对，然后调用上面的 Add 方法来添加。Add 中会更新相关 block 的内容，每当 DataBlock 超过 block_size 时，会调用 Flush 方法将 DataBlock 写入文件。

等所有键值对写完，会主动调用 Finish 方法，来进行一些收尾工作，比如将最后一个 Datablock 的数据写入文件，写入 IndexBlock，FilterBlock 等。

Finish 的实现如下，开始之前先用 Flush 把剩余的 DataBlock 部分刷到磁盘文件中，接着会处理其他块，并且在文件尾部添加一个固定大小的 footer 部分，用来记录索引信息。

Status TableBuilder::Finish() {
  Rep* r = rep_;
  Flush();
  assert(!r->closed);
  r->closed = true;

  // Write filter block
  // Write metaindex block
  // Write index block
  // Write footer

  return r->status;
}

这里构建各个块也比较有意思，都是用一个 builder 来处理内容，同时用一个 handler 来记录块的偏移和大小。我们分别来看下。

BlockBuilder 构建块

先思考一个问题，这里有这么多类型的块，每个块都要一个自己的 Builder 来拼装数据吗？

这里要从每个块的数据结构来看，Data/Index/MetaIndex Block 这三种块都具有以下共同特征：

键值对结构：都存储键值对形式的数据，虽然这里每个块里面的键值含义不一样，但都是键值对形式;
有序性要求：键必须按顺序排列，因为后面查找的时候，需要支持二分查找或顺序扫描;

所以这 3 类块的构建逻辑是类似的，LevelDB 中共用同一个 BlockBuilder 来处理。这里实现在 table/block_builder.h 中，也有不少优化细节。比如前缀压缩优化，对于相似的键只存储差异部分，节省空间。重启点机制，每隔几个条目设置一个重启点，支持二分查找。后面我会专门用一篇文章来详细说明。封装后用起来比较简单，以 MetaIndex Block 为例，用 Add 添加键值，然后 WriteBlock 落磁盘就好。代码如下:

void TableBuilder::Finish() {
    BlockBuilder meta_index_block(&r->options);
    if (r->filter_block != nullptr) {
      // Add mapping from "filter.Name" to location of filter data
      std::string key = "filter.";
      key.append(r->options.filter_policy->Name());
      std::string handle_encoding;
      filter_block_handle.EncodeTo(&handle_encoding);
      meta_index_block.Add(key, handle_encoding);
    }

    // TODO(postrelease): Add stats and other meta blocks
    WriteBlock(&meta_index_block, &metaindex_block_handle);
    // ...
}

而 filter block 的数据结构和其他的都不一样，它存储的是布隆过滤器的二进制数据，按文件偏移分组，每 2KB 文件范围对应一个过滤器。所以 filter block 的构建逻辑和其他的都不一样，需要单独处理。这里的实现在 table/filter_block.cc 中，后面我单独再展开分析。这里使用倒是很简单，如下：

// Write filter block
if (ok() && r->filter_block != nullptr) {
  WriteRawBlock(r->filter_block->Finish(), kNoCompression,
                &filter_block_handle);
}

这里 Finish 方法会返回 filter block 的二进制数据，然后调用 WriteRawBlock 方法将数据写入文件。

BlockHandle 记录偏移和大小

上面用两个 builder 来构建块，但是用同一个 handler 类来记录块的偏移和大小。代码如下：

1 2	BlockHandle filter_block_handle, metaindex_block_handle, index_block_handle;

这里 BlockHandle 的实现在 table/format.h 中，主要告诉系统在文件的第 X 字节位置，有一个大小为 Y 字节的块，仅此而已。不过配合不同块的 handle 信息，就能方便存储不同块的偏移和大小。

至此，我们用两个 builder 来构建各种索引块，同时用一个 handler 来辅助记录块的偏移和大小。就完成了整个块的构建。

创建 SSTable 文件完整步骤

最后我们可以来看看上层调用方，是如何用 TableBuilder 来构造 SSTable 文件的。

在 db/builder.cc 中封装了一个函数 BuildTable 来创建 SSTable 文件，它就是调用 TableBuilder 类的接口来实现的。省略其他无关代码，核心代码如下：

Status BuildTable(const std::string& dbname, Env* env, const Options& options,
                  TableCache* table_cache, Iterator* iter, FileMetaData* meta) {
    // ...
    TableBuilder* builder = new TableBuilder(options, file);
    // ...
    Slice key;
    for (; iter->Valid(); iter->Next()) {
      key = iter->key();
      builder->Add(key, iter->value());
    }
    // ...
    // Finish and check for builder errors
    s = builder->Finish();
    // ...
    delete builder;
    //..
}

这里用迭代器 iter 来遍历 immemtable 中的键值对，然后调用 TableBuilder 的 Add 方法将键值对添加到 SSTable 文件中。Memtable 的大小限制默认是 4MB(write_buffer_size = 4*1024*1024)，在用 TableBuilder 添加键值对时，会根据 block_size(4*1024) 来划分数据块。每当凑够一个 DataBlock，就会拼装相应 block 的数据，然后用 flush 追增内容到磁盘 SSTable 文件中。最后调用 TableBuilder 的 Finish 方法写入其他 Block，完成整个SSTable 文件的写入。

除了这里 BuildTable 将 immemtable 中的数据写入 level0 的 SSTable 文件外，还有一个场景是在 Compact 过程中，将多个 SSTable 文件合并成一个 SSTable 文件。这个过程在 db/db_impl.cc 中的 DoCompactionWork 函数中实现，整体流程稍微复杂，调用比较深入，等后面我们讲 Compact 的时候再详细分析。

不过这里只讲一个点，在 Compact 过程中，会在某些失败场景调用 TableBuilder 的 Abandon 方法，用来放弃当前的 TableBuilder 写入文件过程。

1	compact->builder->Abandon();

Abandon 主要就是把 TableBuilder 的 Rep 中的 closed 设置为 true，调用方之后就会丢掉这个 TableBuilder 实例，不会用它执行任何写入操作了(写入中一堆断言来检查这个状态)。

总结

回到开头我们提出的问题，文件格式该如何设计，才能兼顾高效写入和快速读取？通过深入分析 LevelDB 的 SSTable 文件创建过程，我们可以看到作者是如何一步步解决这个问题的。首先SSTable 数据格式设计有几个重要的设计思想：

分块存储：将大文件切分成 4KB 的 DataBlock，既便于管理，又能减少无效的磁盘 I/O，还方便缓存热点数据。
索引加速：通过 IndexBlock 将”全文扫描”变成”查目录 + 精准读取”，减少磁盘 I/O 次数。
过滤优化：用 FilterBlock 在源头减少不必要的磁盘读取，提高读取性能。
元信息集中管理：Footer + Meta-IndexBlock 的设计保证了扩展性，方便后续添加更多元数据块。

在 TableBuilder 的实现中，我们也看到了不少值得学习的工程细节，比如：

索引键优化：延迟到下一个块开始时才更新索引，通过 FindShortestSeparator 算法生成最短分割键，大幅减少索引块大小。这个优化看似微小，但在大规模数据下效果显著。
错误处理：代码中大量的 assert 断言体现了”早崩溃早发现”的理念，对于底层存储系统来说至关重要。
分层抽象：TableBuilder → BlockBuilder → FilterBlockBuilder 的分层设计，让复杂的文件格式构建变得井井有条。每一层都有明确的职责边界。
性能平衡：压缩策略中的 0.85 压缩比阈值，体现了对性能与效果的权衡考量。

其实 SSTable 的设计回答了存储系统中的几个根本问题。用顺序写入，来保证写入吞吐，用索引结构来保证读取性能。用分块和按需加载以及缓存，在有限内存下处理海量数据。同时用压缩和过滤器来平衡存储空间与查询效率，用元信息分层来保证系统的可扩展性。这些都是计算机软件系统中沉淀多年的经典设计，值得我们学习。

理解了 SSTable 的创建过程后，你可能会产生一些新的疑问：DataBlock 内部是如何组织数据的？读取 SSTable 时的流程是怎样的？多个 SSTable 文件如何协同工作？

这些问题的答案，构成了 LevelDB 这个精巧存储引擎的完整图景。我会在后面的文章中继续深入分析，敬请期待。

LevelDB 源码阅读：LRU Cache 高性能缓存实现细节

2025-06-14 05:00:00

计算机系统中，缓存无处不在。从 CPU 缓存到内存缓存，从磁盘缓存到网络缓存，缓存无处不在。缓存的核心思想就是空间换时间，通过将热点数据缓存到高性能的存储中，从而提高性能。因为缓存设备比较贵，所以存储大小有限，就需要淘汰掉一些缓存数据。这里淘汰的策略就非常重要了，因为如果淘汰的策略不合理，把接下来要访问的数据淘汰掉了，那么缓存命中率就会非常低。

缓存淘汰策略有很多种，比如 LRU、LFU、FIFO 等。其中 LRU(Least Recently Used) 就是一种很经典的缓存淘汰策略，它的核心思想是：当缓存满了的时候，淘汰掉最近最少使用的数据。这里基于的一个经验假设就是”如果数据最近被访问过，那么将来被访问的几率也更高“。只要这个假设成立，那么 LRU 就可以显著提高缓存命中率。

在 LevelDB 中，实现了内存中的 LRU Cache，用于缓存热点数据，提高读写性能。默认情况下，LevelDB 会对 sstable 的索引和 data block 进行缓存，其中 sstable 默认是支持缓存 990 (1000-10) 个，data block 则默认分配了 8MB 的缓存。

LevelDB 实现的 LRU 缓存是一个分片的 LRU，在细节上做了很多优化，非常值得学习。本文将从经典的 LRU 实现思路出发，然后一步步解析 LevelDB 中 LRU Cache 的实现细节。

经典的 LRU 实现思路

一个实现良好的 LRU 需要支持 O(1) 时间复杂度的插入、查找、删除操作。经典的实现思路是使用一个双向链表和一个哈希表，其中：

双向链表用于存储缓存中的数据项，并保持缓存项的使用顺序。最近被访问的数据项被移动到链表的头部，而最久未被访问的数据项则逐渐移向链表的尾部。当缓存达到容量限制而需要淘汰数据时，链表尾部的数据项（即最少被访问的数据项）会被移除。
哈希表用于存储键与双向链表中相应节点的对应关系，这样任何数据项都可以在常数时间内被快速访问和定位。哈希表的键是数据项的键，值则是指向双向链表中对应节点的指针。

双向链表保证在常数时间内添加和删除节点，哈希表则提供常数时间的数据访问能力。对于 Get 操作，通过哈希表快速定位到链表中的节点，如果存在则将其移动到链表头部，更新为最近使用。对于插入 Insert 操作，如果数据已存在，更新数据并移动到链表头部；如果数据不存在，则在链表头部插入新节点，并在哈希表中添加映射，如果超出容量则移除链表尾部节点，并从哈希表中删除相应的映射。

上面的实现思路相信每个学过算法的人都知道，Leetcode 上也有 LRU 实现的题目，比如 146. LRU 缓存，需要实现的接口：

class LRUCache {
public:
    LRUCache(int capacity) {
    }
    int get(int key) {
    }
    void put(int key, int value) {    
    }
};

不过想实现一个工业界可用的高性能 LRU 缓存，还是有点难度的。接下来，我们来看看 LevelDB 是如何实现的。

缓存设计：依赖倒置

在开始看 LevelDB 的 LRU Cache 实现之前，先看下 LevelDB 中如何使用这里的缓存。比如在 db/table_cache.cc 中，为了缓存 SST table 的元数据信息，TableCache 类定义了一个 Cache 类型的成员变量，然后通过该成员来对缓存进行各种操作。

Cache* cache_(NewLRUCache(entries));

*handle = cache_->Lookup(key);
*handle = cache_->Insert(key, tf, 1, &DeleteEntry);
cache_->Release(handle);
cache_->Erase(Slice(buf, sizeof(buf)));
// ...

这里 Cache 是一个抽象类，定义了缓存操作的各种接口，具体定义在 include/leveldb/cache.h 中。它定义了缓存应该具有的基本操作，如 Insert、Lookup、Release、Erase 等。它还定义了 Cache::Handle 这个类型，作为缓存条目。用户代码只与这个抽象接口交互，不需要知道具体实现。

然后有个 LRUCache 类，是具体的缓存实现类，它实现了一个完整的 LRU 缓存。这个类不直接对外暴露，也不直接继承 Cache。然后还有个 ShardedLRUCache 类，它继承 Cache 类实现了缓存各种接口。它内部包含 16 个 LRUCache “分片”（shards），每个分片负责缓存一部分数据。

这样的设计允许调用方在不修改使用缓存部分的代码的情况下，轻松替换不同的缓存实现。哈哈，这不就是八股文经常说的，面向对象编程 SOLID 中的依赖倒置嘛，应用层依赖于抽象接口(Cache)而不是具体实现(LRUCache)。这样可以降低代码耦合度，提高系统的可扩展性和可维护性。

使用 Cache 的时候，通过这里的工厂函数来创建具体的缓存实现 ShardedLRUCache：

Cache* NewLRUCache(size_t capacity) { return new ShardedLRUCache(capacity); }

// 可以随时增加新的缓存实现
// Cache* NewClockCache(size_t capacity);

LRUCache 是缓存的核心部分，不过现在我们先不管怎么实现 LRUCache，先来看看缓存项 Hanle 的设计。

LRUHandle 类的实现

在 LevelDB 中，缓存的数据项是一个 LRUHandle 类，定义在 util/cache.cc 中。这里的注释也说明了，LRUHandle 是一个支持堆分配内存的变长结构体，它会被保存在一个双向链表中，按访问时间排序。我们来看看这个结构体的成员有哪些吧：

struct LRUHandle {
  void* value;
  void (*deleter)(const Slice&, void* value);
  LRUHandle* next_hash;
  LRUHandle* next;
  LRUHandle* prev;
  size_t charge;  // TODO(opt): Only allow uint32_t?
  size_t key_length;
  bool in_cache;     // Whether entry is in the cache.
  uint32_t refs;     // References, including cache reference, if present.
  uint32_t hash;     // Hash of key(); used for fast sharding and comparisons
  char key_data[1];  // Beginning of key
}

这里还稍微有点复杂，每个字段都还挺重要的，我们一个个来看吧。

value：存储缓存的实际 value 值，这里是一个 void* 的指针，说明缓存这层不关心具体值的结构，只用知道对象的地址就好；
deleter：一个函数指针，指向用于删除缓存值的回调函数，当缓存项被移除时，用它来释放缓存值的内存空间；
next_hash：LRU 缓存实现需要用到哈希表。这里 LevelDB 自己实现了一个高性能的哈希表，在 LevelDB 源码阅读：如何设计一个高性能哈希表中，我们介绍了 LevelDB 中哈希表的实现细节，里面有介绍过 LRUHandle 的 next_hash 字段就是用来解决哈希表的冲突的。
prev/next：双向链表的前一个/下一个指针，用来维持双向链表，方便快速从双向链表中插入或者删除节点；
charge：表示该缓存项占用的成本（通常是内存大小），用于计算总缓存使用量，判断是否需要淘汰；
key_length：键的长度，用于构造 Slice 对象表示键；
in_cache：标记该项是否在缓存中，如果为 true，表示缓存拥有对该项的引用；
refs：引用计数，包括缓存本身的引用（如果在缓存中）和使用方的引用，当计数为0时，可以释放该项；
hash：键的哈希值，用于快速查找和分片；这里同一个 key 也把 hash 值保存下来，避免重复计算；
key_data：柔性数组成员，存储键的实际数据，使用 malloc 分配足够空间来存储整个键。柔性数组我们在 LevelDB 源码阅读：理解其中的 C++ 高级技巧中也有介绍过，这里就不展开了。

这里 LRUHandle 的设计允许缓存高效地管理数据项，跟踪缓存项的引用，并实现 LRU 淘汰策略。特别是 in_cache 和 refs 字段的结合使用，使得我们可以区分”被缓存但未被客户端引用“和”被客户端引用“的项，从而用两个链表来支持高效淘汰缓存。

下面我们详细看看 LRUCache 类的实现细节，就更容易理解上面各个字段的用途了。

LRUCache 类的实现细节

前面看完了缓存的数据项的设计，接着可以来看看这里 LevelDB LRUCache 的具体实现细节了。核心的缓存逻辑实现在 util/cache.cc 的 LRUCache 类中。该类包含了缓存的核心逻辑，如插入、查找、删除、淘汰等操作。

这里注释(LevelDB 的注释感觉都值得好好品读)中提到，用了两个双向链表来维护缓存项，这又是为什么呢？

// The cache keeps two linked lists of items in the cache.  All items in the
// cache are in one list or the other, and never both.  Items still referenced
// by clients but erased from the cache are in neither list.  The lists are:
// - in-use:  contains the items currently referenced by clients, in no
//   particular order.  (This list is used for invariant checking.  If we
//   removed the check, elements that would otherwise be on this list could be
//   left as disconnected singleton lists.)
// - LRU:  contains the items not currently referenced by clients, in LRU order
// Elements are moved between these lists by the Ref() and Unref() methods,
// when they detect an element in the cache acquiring or losing its only
// external reference.

为什么用两个双向链表？

我们前面也提到，一般的 LRU Cache 实现中用一个双向链表。每次使用一个缓存项时，会将其移动到链表的头部，这样链表的尾部就是最近最少使用的缓存项。淘汰的时候，直接移除链表尾部的节点即可。比如开始提到的 Leetcode 中的题目就可以这样实现来解决，实现中每个缓存项就是一个 int，取的时候直接复制出来就好。如果要缓存的项是简单的值类型，读的时候直接复制值，不需要引用，那单链表的实现足够了。

但在 LevelDB 中，缓存的数据项是 LRUHandle 对象，它是一个动态分配内存的变长结构体。在使用的时候，为了高并发和性能考虑，不能通过简单的值复制，而要通过引用计数来管理缓存项。如果还是简单的使用单链表的话，我们考虑下这样的场景。

我们依次访问 A, C, D 项，最后访问了 B, B 项被客户端引用(refs=1)，位于链表头部，如下图中的开始状态。一段时间内，A、C、D都被访问了，但 B 没有被访问。根据 LRU 规则，A、C、D被移到链表头部。B 虽然仍被引用，但因为长时间未被访问，相对位置逐渐后移。A 和 D 被访问后，很快使用完，这时候没有引用了。当需要淘汰时，从尾部开始，会发现B项(refs=1)不能淘汰，需要跳过继续往前遍历检查其他项。

也就是说在这种引用场景下，淘汰节点的时候，如果链表尾部的节点正在被外部引用（refs > 1），则不能淘汰它。这时候需要遍历链表寻找可淘汰的节点，效率较低。在最坏情况下，如果所有节点都被引用，可能需要遍历整个链表却无法淘汰任何节点。

为了解决这个问题，在 LRUCache 实现中，用了两个双向链表。一个是in_use_，用来存储被引用的缓存项。另一个是lru_，用来存储未被引用的缓存项。每个缓存项只能在其中的一个链表中，不能同时在两个链表中。但是可以根据当前是否被引用，在两个链表中互相移动。这样在需要淘汰节点的时候，就可以直接从 lru_ 链表中淘汰，而不用遍历 in_use_ 链表。

双链表介绍就先到这里，后面可以结合 LRUCache 的核心实现继续理解双链表具体怎么实现。

缓存插入，删除，查找节点

先来看插入节点，实现在 util/cache.cc 中。简单说，这里先创建 LRUHandle 对象，然后把它放到 in_use_ 双向链表中，同时更新哈希表。如果插入节点后，缓存容量达到上限，则需要淘汰节点。但是实现中，还是有不少细节部分，LevelDB 的代码也确实精简。

可以看下这里的入参，key 和 value 是客户端传入的，hash 是 key 的哈希值，charge 是缓存项占用的成本，deleter 是删除缓存项的回调函数。这里因为 LRUHandle 最后成员是柔性数组，所以我们先手动计算 LRUHandle 对象的大小，然后分配内存，之后开始初始化各种成员。这里 refs 初始化为 1，因为返回了一个 Handle 指针对象。

Cache::Handle* LRUCache::Insert(const Slice& key, uint32_t hash, void* value,
                                size_t charge,
                                void (*deleter)(const Slice& key,
                                                void* value)) {
  MutexLock l(&mutex_);

  LRUHandle* e =
      reinterpret_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()));
  e->value = value;
  e->deleter = deleter;
  e->charge = charge;
  e->key_length = key.size();
  e->hash = hash;
  e->in_cache = false;
  e->refs = 1;  // for the returned handle.
  std::memcpy(e->key_data, key.data(), key.size());

接着这里也比较有意思，LevelDB 中的 LRUCache 实现，支持缓存容量设为 0，这时候就不缓存任何数据。要缓存的时候，更新 in_cache 为 true，增加 refs 计数，因为把 Handle 对象放到了 in_use_ 链表中。接着当然还要把 Handle 插入到哈希表中，注意这里有个 FinishErase 调用，值得好好聊聊。

if (capacity_ > 0) {
  e->refs++;  // for the cache's reference.
  e->in_cache = true;
  LRU_Append(&in_use_, e);
  usage_ += charge;
  FinishErase(table_.Insert(e));
} else {  // don't cache. (capacity_==0 is supported and turns off caching.)
  // next is read by key() in an assert, so it must be initialized
  e->next = nullptr;
}

我们前面将哈希表实现的时候，这里插入哈希表，如果已经有同样的 key，则返回旧的 Handle 对象。这里 FinishErase 函数就是用来清理这个旧的 Handle 对象。

// If e != nullptr, finish removing *e from the cache; it has already been
// removed from the hash table.  Return whether e != nullptr.
bool LRUCache::FinishErase(LRUHandle* e) {
  if (e != nullptr) {
    assert(e->in_cache);
    LRU_Remove(e);
    e->in_cache = false;
    usage_ -= e->charge;
    Unref(e);
  }
  return e != nullptr;
}

清理操作有几个吧，首先从 in_use_ 或者 lru_ 链表中移除，这里其实不确定旧的 Handle 对象具体在哪个链表中，不过没关系，LRU_Remove 不用知道在哪个链表也能处理。LRU_Remove 函数实现很简单，也就两行代码，大家不理解的话可以画个图来理解下：

void LRUCache::LRU_Remove(LRUHandle* e) {
  e->next->prev = e->prev;
  e->prev->next = e->next;
}

接着更新 in_cache 为 false，表示已经不在缓存中了。后面还要更新缓存容量，减少 usage_。最后调用 Unref 减少这个 Handle 对象的引用计数，这时候这个 Handle 对象可能在其他地方还有引用。等到所有引用都释放了，这时候才会真正清理这个 Handle 对象。Unref 函数其实也有点意思，我把代码也贴出来：

void LRUCache::Unref(LRUHandle* e) {
  assert(e->refs > 0);
  e->refs--;
  if (e->refs == 0) {  // Deallocate.
    assert(!e->in_cache);
    (*e->deleter)(e->key(), e->value);
    free(e);
  } else if (e->in_cache && e->refs == 1) {
    // No longer in use; move to lru_ list.
    LRU_Remove(e);
    LRU_Append(&lru_, e);
  }
}

首先减少计数，如果计数为 0，则表示完全没有外部引用，这时候可以大胆释放内存。释放也分两部分，先用回调函数 deleter 来清理 value 部分的内存空间。接着用 free 来释放 LRUHandle 指针的内存空间。如果计数为 1 并且还在缓存中，表示只有来自缓存自身的引用，这时候需要把 Handle 对象从 in_use_ 链表中移除，并放到 lru_ 链表中。如果后面要淘汰节点，这个节点在 lru_ 链表中，就可以直接淘汰了。

接下来就是插入节点操作的最后一步了，判断缓存是否还有剩余空间，没有的话，要开始淘汰节点了。这里只要空间还是不够，然后就会从 lru_ 链表中取出队首节点，然后从哈希表中移除，接着调用 FinishErase 清理节点。这里判断双向链表是否为空也比较有意思，用到了哑元节点，后面再介绍。

while (usage_ > capacity_ && lru_.next != &lru_) {
  LRUHandle* old = lru_.next;
  assert(old->refs == 1);
  bool erased = FinishErase(table_.Remove(old->key(), old->hash));
  if (!erased) {  // to avoid unused variable when compiled NDEBUG
    assert(erased);
  }
}

整个插入节点函数，包括这里的淘汰逻辑，甚至是整个 LevelDB 代码中，都有大量的 assert 断言，用来做一些检查，保证有问题进程立马挂掉，避免错误传播。

看完插入节点，其实删除节点就不用看了，代码实现很简单，从哈希表中移除节点，然后调用 FinishErase 清理节点。

void LRUCache::Erase(const Slice& key, uint32_t hash) {
  MutexLock l(&mutex_);
  FinishErase(table_.Remove(key, hash));
}

查找节点也相对简单些，直接从哈希表中查找，如果找到，则增加引用计数，并返回 Handle 对象。这里其实和插入一样，只要返回了 Handle 对象，就会增加引用计数。所以如果外面如果没有用到的话，要记得调用 Release 方法手动释放引用，不然内存就容易泄露了。

Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
  MutexLock l(&mutex_);
  LRUHandle* e = table_.Lookup(key, hash);
  if (e != nullptr) {
    Ref(e);
  }
  return reinterpret_cast<Cache::Handle*>(e);
}
void LRUCache::Release(Cache::Handle* handle) {
  MutexLock l(&mutex_);
  Unref(reinterpret_cast<LRUHandle*>(handle));
}

此外，这里的 Cache 还实现了 Prune 接口，用来主动清理缓存。方法和插入里面的清理逻辑类似，不过这里会把 lru_ 链表中所有节点都清理掉。这个清理在 LevelDB 中也没地方用到过。

双向链表的操作

我们再补充讨论下这里双向链表相关的操作吧。前面我们其实已经知道了分了两个链表，一个 lru_ 链表，一个 in_use_ 链表。这里结合注释看更清晰：

// Dummy head of LRU list.
// lru.prev is newest entry, lru.next is oldest entry.
// Entries have refs==1 and in_cache==true.
LRUHandle lru_ GUARDED_BY(mutex_);

// Dummy head of in-use list.
// Entries are in use by clients, and have refs >= 2 and in_cache==true.
LRUHandle in_use_ GUARDED_BY(mutex_);

lru_ 成员是链表的哑元节点，next 成员指向 lru_ 链表中最老的缓存项，prev 成员指向 lru_ 链表中最新的缓存项。在 LRUCache 的构造函数中，lru_ 的 next 和 prev 都指向它自己，表示链表为空。还记得前面插入节点的时候，怎么判定还有可以淘汰的节点的吧，就是用 lru_.next != &lru_。

LRUCache::LRUCache() : capacity_(0), usage_(0) {
  // Make empty circular linked lists.
  lru_.next = &lru_;
  lru_.prev = &lru_;
  in_use_.next = &in_use_;
  in_use_.prev = &in_use_;
}

哑元（dummy node）在很多数据结构的实现中被用作简化边界条件处理的技巧。在 LRU 缓存的上下文中，哑元主要是用来作为链表的头部，这样链表的头部始终存在，即使链表为空时也是如此。这种方法可以简化插入和删除操作，因为在插入和删除操作时不需要对空链表做特殊处理。

例如，当向链表中添加一个新的元素时，可以直接在哑元和当前的第一个元素之间插入它，而不需要检查链表是否为空。同样，当从链表中删除元素时，你不需要担心删除最后一个元素后如何更新链表头部的问题，因为哑元始终在那里。

删除链表中节点 LRU_Remove 我们前面看过，两行代码就行了。往链表添加节点的实现，我整理了一张图，配合代码就好理解了：

这里 e 是新插入的节点，list 是链表的哑元节点。list 的 pre 和 next 我这里用圆形，表示它可以是自己，比如初始空链表的时候。这里插入是在哑元的前面，所以 list->prev 永远是链表最新的节点，list->next 永远是链表最老的节点。这种链表操作，最好画个图，就一目了然了。

reinterpret_cast 转换

最后再补充说下，上面代码中有不少地方用到了 reinterpret_cast 来在 LRUHandle* 和 Cache::Handle* 之间转换类型。reinterpret_cast 将一种类型的指针强制转换为另一种类型的指针，而不进行任何类型检查。它不进行任何底层数据的调整，只是告诉编译器：”请把这个内存地址当作另一种类型来看待”。其实这种操作比较危险，一般不推荐这样用。

但 LevelDB 这样做其实是为了将接口和实现分析。这里将具体的内部数据结构 LRUHandle* 以一个抽象、不透明的句柄 Cache::Handle* 形式暴露给外部用户，同时又能在内部将这个不透明的句柄转换回具体的数据结构进行操作。

在这种特定的、受控的设计模式下，它是完全安全的。因为只有 LRUCache 内部代码可以创建 LRUHandle。任何返回给外部的 Cache::Handle* 总是指向一个合法的 LRUHandle 对象。任何传递给 LRUCache 的 Cache::Handle* 必须是之前由同一个 LRUCache 实例返回的。

只要遵守这些约定，reinterpret_cast 就只是在指针的”视图”之间切换，指针本身始终指向一个有效的、类型正确的对象。如果用户试图伪造一个 Cache::Handle* 或者将一个不相关的指针传进来，程序就会发生未定义行为，但这属于 API 的误用。

ShardedLRUCache 分片实现

前面 LRUCache 的实现中，插入缓存、查找缓存、删除缓存操作都必须通过一个互斥锁来保护。在多线程环境下，如果只有一个大的缓存，这个锁就会成为一个全局瓶颈。当多个线程同时访问缓存时，只有一个线程能获得锁，其他线程都必须等待，这会严重影响并发性能。

为了提高性能，ShardedLRUCache 将缓存分成多个分片（shard_ 数组），每个分片都有自己独立的锁。当一个请求到来时，它会根据 key 的哈希值被路由到特定的分片。这样，不同线程访问不同分片时就可以并行进行，因为它们获取的是不同的锁，从而减少了锁的竞争，提高了整体的吞吐量。画个图可能更清晰些，mermaid 代码在这里。

那么需要分多少片呢？LevelDB 这里硬编码了一个 $ kNumShards = 1 << kNumShardBits $，计算出来是 16，算是一个经验选择吧。如果分片数量太少，比如2、4个，在核心数很多的服务器上，锁竞争依然可能很激烈。分片太多的话，每个分片的容量就会很小。这可能导致一个”热”分片频繁淘汰数据，而另一个”冷”分片有很多空闲空间的情况，从而降低了整个缓存的命中率。

选择 16 的话，对于典型的 8 核或 16 核服务器，已经能提供足够好的并发度，同时又不会带来过大的额外开销。同时选择 2 的幂次方，还能通过位运算 $ hash >> (32 - kNumShardBits)$ 快速计算分片索引。

加入分片后，包装了下原始的 LRUCache 类，构造的时候需要指定分片数，每个分片容量等，实现如下：

public:
 explicit ShardedLRUCache(size_t capacity) : last_id_(0) {
   const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
   for (int s = 0; s < kNumShards; s++) {
     shard_[s].SetCapacity(per_shard);
   }
 }

然后其他相关缓存操作，比如插入、查找、删除等，都是通过 Shard 函数来决定操作哪个分片。这里以插入为例，实现如下：

Handle* Insert(const Slice& key, void* value, size_t charge,
               void (*deleter)(const Slice& key, void* value)) override {
  const uint32_t hash = HashSlice(key);
  return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
}

求 Hash 和计算分片的 Shard 函数没什么难点，这里就忽略了。这里也提下，ShardLRUCache 这里还要继承 Cache 抽象类，实现 Cache 中的各种接口。这样才能被其他调用 Cache 接口的地方使用。

最后这里还有一个小细节，也值得说下，那就是 Cache 接口还有个 NewId 函数。在其他的 LRU 缓存实现中，没见过有支持 Cache 生成一个 Id。LevelDB 为啥这么做呢？

Cache 的 Id 生成

LevelDB 其实提供了注释，但是只看注释似乎也不好明白，我们结合使用场景来分析下。

// Return a new numeric id.  May be used by multiple clients who are
// sharing the same cache to partition the key space.  Typically the
// client will allocate a new id at startup and prepend the id to
// its cache keys.
virtual uint64_t NewId() = 0;

这里补充些背景，我们在打开 LevelDB 数据库时，可以创建一个 Cache 对象，并传入 options.block_cache，用来缓存 SSTTable 文件中的数据块和过滤块。当然如果不传的话，LevelDB 默认也会创建一个 8 MB 的 SharedLRUCache 对象。这里 Cache 对象是全局共享的，数据库中所有的 Table 对象都会使用这同一个 BlockCache 实例来缓存它们的数据块。

在 table/table.cc 的 Table::Open 中，我们看到每次打开 SSTTable 文件的时候，就会用 NewId 生成一个 cache_id。这里底层用互斥锁保证，每次生成的 Id 是全局递增的。后面我们要读取 SSTTable 文件中偏移量为 offset 的数据块 block 时，会用 <cache_id, offset> 作为缓存的 key 来进行读写。这样不同 SSTTable 文件的 cache_id 不同，即使他们的 offset 一样，这里缓存 key 也不同，不会冲突。

说白了，SharedLRUCache 提供全局递增的 Id 主要是用来区分不同 SSTTable 文件，免得每个文件还要自己维护一个唯一 Id 来做缓存的 key。

总结

好了，LevelDB 的 LRU Cache 分析完了，我们可以看到一个工业级高性能缓存的设计思路和实现细节。最后总结下几个关键点：

接口与实现分离：通过抽象的 Cache 接口，将缓存的使用方与具体实现解耦，体现了面向对象设计中的依赖倒置原则。用户代码只需要跟 Cache 接口打交道，不用关心具体实现。
精心设计的缓存项：LRUHandle 结构体包含了引用计数、缓存标志等元数据，通过柔性数组成员存储变长的 key，减少内存分配次数，提高性能。
双链表优化：通过两个双向链表（in_use_ 和 lru_）分别管理”正在使用”和”可以淘汰”的缓存项，避免了在淘汰时遍历整个链表，提高了淘汰效率。
哑元节点技巧：使用哑元节点简化了链表操作，不需要处理空链表的特殊情况，代码更简洁。
分片减少锁竞争：ShardedLRUCache 将缓存分成多个分片，每个分片有独立的锁，大幅提高了多线程环境下的并发性能。
引用计数管理内存：通过精确的引用计数，确保缓存项在仍被外部引用时不会被释放，同时在不再需要时及时回收内存。
断言保证正确性：大量使用断言来检查代码的前置条件和不变量，确保错误能够及早被发现。

这些设计思路和实现技巧都值得我们在自己的项目中借鉴。特别是在需要高并发、高性能的场景中，LevelDB 的这些优化手段可以帮助我们设计出更高效的缓存系统。

LevelDB 源码阅读：MemTable 内存表的实现细节

2025-06-12 03:47:42

在 LevelDB 中，所有的写操作首先都会被记录到一个 Write-Ahead Log（WAL，预写日志）中，以确保持久性。接着数据会被存储在 MemTable 中，MemTable 的主要作用是在内存中有序存储最近写入的数据，到达一定条件后批量落磁盘。

LevelDB 在内存中维护两种 MemTable，一个是可写的，接受新的写入请求。当达到一定的大小阈值后，会被转换为一个不可变的 Immutable MemTable，接着会触发一个后台过程将其写入磁盘形成 SSTable。这个过程中，会创建一个新的 MemTable 来接受新的写入操作。这样可以保证写入操作的连续性，不受到影响。

在读取数据时，LevelDB 首先查询 MemTable。如果在 MemTable 中找不到，然后会依次查询不可变的 Immutable MemTable，最后是磁盘上的 SSTable 文件。在 LevelDB 的实现中，不管是 MemTable 还是 Immutable MemTable，内部其实都是用 class MemTable 来实现的。这篇文章我们来看看 memtable 的实现细节。

Memtable 使用方法

先来看看 LevelDB 中哪里用到了 MemTable 类。在库的核心 DB 实现类 DBImpl 中，可以看到有两个成员指针，

class DBImpl : public DB {
 public:
  DBImpl(const Options& options, const std::string& dbname);
  //...
  MemTable* mem_;
  MemTable* imm_ GUARDED_BY(mutex_);  // Memtable being compacted
  //...
}

mem_ 是可写的 memtable，imm_ 是不可变的 memtable。这两个是数据库实例中唯一的两个 memtable 对象，用来存储最近写入的数据，在读取和写入键值的时候，都会用到这两个 memtable。

我们先来看写入过程，我之前写过LevelDB 源码阅读：写入键值的工程实现和优化细节，里面有写入键值的全部过程。写入过程中，写入 WAL 日志成功后，会调用 db/write_batch.cc 中的 MemTableInserter 类来写入 memtable，具体代码如下：

// db/write_batch.cc
class MemTableInserter : public WriteBatch::Handler {
 public:
  SequenceNumber sequence_;
  MemTable* mem_;

  void Put(const Slice& key, const Slice& value) override {
    mem_->Add(sequence_, kTypeValue, key, value);
    sequence_++;
  }
  //...
};

这里调用了 Add 接口往 memtable 中写入键值对，sequence_ 是写入的序列号，kTypeValue 是写入的类型，key 和 value 是用户传入的键值对。

除了写入过程，在读取键值对的时候，也会需要 Memtable 类。具体在 db/db_impl.cc 中 DBImpl 类的 Get 方法中，会调用 memtable 的 Get 方法来查询键值对。

Status DBImpl::Get(const ReadOptions& options, const Slice& key,
                   std::string* value) {
  // ...
  MemTable* mem = mem_;
  MemTable* imm = imm_;
  Version* current = versions_->current();
  mem->Ref();
  if (imm != nullptr) imm->Ref();
  // Unlock while reading from files and memtables
  {
    mutex_.Unlock();
    LookupKey lkey(key, snapshot);
    if (mem->Get(lkey, value, &s)) {
      // Done
    } else if (imm != nullptr && imm->Get(lkey, value, &s)) {
      // Done
    }
    mutex_.Lock();
  }

  // ...
  mem->Unref();
  if (imm != nullptr) imm->Unref();
  // ...

这里会先创建本地指针 mem 和 imm 来引用成员变量 mem_ 和 imm_，之后用本地指针来进行读取。这里有个问题是，为什么不直接使用成员变量 mem_ 和 imm_ 来读取呢？这个问题留到后面解读疑问我们再回答。

好了，至此我们已经看到了 Memtable 的主要使用方法了，那它们内部是怎么实现的呢，我们接着看吧。

Memtable 实现

在开始讨论 MemTable 对外方法的实现之前，先要知道 Memtable 中的数据其实是存储在跳表中的。跳表提供了平衡树的大部分优点（如有序性、插入和查找的对数时间复杂性），但是实现起来更为简单。关于跳表的详细实现，可以参考LevelDB 源码阅读：跳表的原理、实现以及可视化。

MemTable 类内部来声明了一个跳表对象 table_ 成员变量，跳表是个模板类，初始化需要提供 key 和 Comparator 比较器。这里 memtable 中跳表的 key 是 const char* 类型，比较器是 KeyComparator 类型。KeyComparator 就是这样一个自定义的比较器，用来给跳表中键值进行排序。

KeyComparator 包含了一个 InternalKeyComparator 类型的成员变量 comparator，用来比较 internal key 的大小。KeyComparator 比较器的 operator() 重载了函数调用操作符，先从 const char* 中解码出 internal key，然后然后调用 InternalKeyComparator 的 Compare 方法来比较 internal key 的大小。具体实现在 db/memtable.cc 中。

int MemTable::KeyComparator::operator()(const char* aptr,
                                        const char* bptr) const {
  // Internal keys are encoded as length-prefixed strings.
  Slice a = GetLengthPrefixedSlice(aptr);
  Slice b = GetLengthPrefixedSlice(bptr);
  return comparator.Compare(a, b);
}

再补充说下这里 levelDB 的 internal key 其实是拼接了用户传入的 key 和内部的 sequence number，然后再加上一个类型标识。这样可以保证相同 key 的不同版本是有序的，从而实现 MVCC 并发读写。存储到 Memtable 的时候又在 internal key 前面编码了长度信息，叫 memtable key，这样后面读取的时候，我们就能从 const char* 的 memtable key 中根据长度信息解出 internal key 来。这部分我在另一篇文章：LevelDB 源码阅读：结合代码理解多版本并发控制(MVCC) 有详细分析，感兴趣的可以看看。

Memtable 用跳表做存储，然后对外主要支持 Add 和 Get 方法，下面来看看这两个函数的实现细节。

Add 添加键值对

Add 方法用于往 MemTable 中添加一个键值对，其中 key 和 value 是用户传入的键值对，SequenceNumber 是写入时的序列号，ValueType 是写入的类型，有两种类型：kTypeValue 和 kTypeDeletion。kTypeValue 表示插入操作，kTypeDeletion 表示删除操作。LevelDB 中的删除操作，内部其实是插入一个标记为删除的键值对。

Add 实现在 db/memtable.cc 中，函数定义如下：

void MemTable::Add(SequenceNumber s, ValueType type, const Slice& key,
                   const Slice& value) {
  // Format of an entry is concatenation of:
  //  key_size     : varint32 of internal_key.size()
  //  key bytes    : char[internal_key.size()]
  //  tag          : uint64((sequence << 8) | type)
  //  value_size   : varint32 of value.size()
  //  value bytes  : char[value.size()]
  //...

这里的注释十分清楚，Memtable 中存储了格式化后的键值对，先是 internal key 的长度，然后是 internal key 字节串(就是下面的 tag 部分，包含 User Key + Sequence Number + Value Type)，接着是 value 的长度，然后是 value 字节串。整体由 5 部分组成，格式如下：

+-----------+-----------+----------------------+----------+--------+
| Key Size  | User Key  |          tag         | Val Size | Value  |
+-----------+-----------+----------------------+----------+--------+
| varint32  | key bytes | 64 位，后 8 位为 type  | varint32 | value  |

这里第一部分的 keysize 是用 Varint 编码的用户 key 长度加上 8 字节 tag，tag 是序列号和 value type 的组合，高 56 位存储序列号，低 8 位存储 value type。其他部分比较简单，这里不再赘述。

插入过程会先计算出需要分配的内存大小，然后分配内存，接着写入各个部分的值，最后插入到跳表中。具体写入过程代码如下：

// db/memtable.cc
  // ...
  size_t key_size = key.size();
  size_t val_size = value.size();
  size_t internal_key_size = key_size + 8;
  const size_t encoded_len = VarintLength(internal_key_size) +
                             internal_key_size + VarintLength(val_size) +
                             val_size;
  char* buf = arena_.Allocate(encoded_len);
  char* p = EncodeVarint32(buf, internal_key_size);
  std::memcpy(p, key.data(), key_size);
  p += key_size;
  EncodeFixed64(p, (s << 8) | type);
  p += 8;
  p = EncodeVarint32(p, val_size);
  std::memcpy(p, value.data(), val_size);
  assert(p + val_size == buf + encoded_len);
  table_.Insert(buf);
}

这里的 EncodeVarint32 和 EncodeFixed64 是一些编码函数，用来将整数编码到字节流中。具体可以参考LevelDB 源码阅读：内存分配器、随机数生成、CRC32、整数编解码。接下来看看查询键的实现。

Get 查询键值

查询方法的定义也比较简单，如下：

// If memtable contains a value for key, store it in *value and return true.
// If memtable contains a deletion for key, store a NotFound() error
// in *status and return true.
// Else, return false.
bool Get(const LookupKey& key, std::string* value, Status* s);

这里接口传入的 key 并不是用户输入 key，而是一个 LookupKey 对象，在 db/dbformat.h 中有定义。这是因为 levelDB 中同一个用户键可能有不同版本，查询的时候必须指定快照(也就是序列号)，才能拿到对应的版本。所以这里抽象出了一个 LookupKey 类，可以根据用户输入的 key 和 sequence number 来初始化，然后就可以拿到需要的键值格式。

具体到查找过程，先用 LookupKey 对象的 memtable_key 方法拿到前面提到的 memtable key，然后调用跳表的 Seek 方法来查找。db/memtable.cc 中 Get 方法的完整实现如下：

bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {
  Slice memkey = key.memtable_key();
  Table::Iterator iter(&table_);
  iter.Seek(memkey.data());
  if (iter.Valid()) {
    // Check that it belongs to same user key.  We do not check the
    // sequence number since the Seek() call above should have skipped
    // all entries with overly large sequence numbers.
    const char* entry = iter.key();
    uint32_t key_length;
    const char* key_ptr = GetVarint32Ptr(entry, entry + 5, &key_length);
    if (comparator_.comparator.user_comparator()->Compare(
            Slice(key_ptr, key_length - 8), key.user_key()) == 0) {
      // Correct user key
      const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
      switch (static_cast<ValueType>(tag & 0xff)) {
        case kTypeValue: {
          Slice v = GetLengthPrefixedSlice(key_ptr + key_length);
          value->assign(v.data(), v.size());
          return true;
        }
        case kTypeDeletion:
          *s = Status::NotFound(Slice());
          return true;
      }
    }
  }
  return false;
}

我们知道，跳表的 Seek 方法将迭代器定位到链表中第一个大于等于目标内部键的位置，所以我们还需要额外验证该键的 key 与用户查询的 key 是否一致。这是因为可能存在多个具有相同前缀的键，Seek 可能会返回与查询键具有相同前缀的不同键。例如，查询 “app” 可能返回 “apple” 的记录。

这里注释还特别说明了下，我们并没有检查 internal key 中的序列号，这是为什么呢？前面也提到在跳表中，键的排序是基于内部键比较器 (InternalKeyComparator) 来进行的，这里的排序要看键值和序列号。首先会使用用户定义的比较函数（默认是字典顺序）比较用户键，键值小的靠前。如果用户键相同，则比较序列号，序列号大的记录在跳表中位置更前。这是因为我们通常希望对于相同的用户键，更新的更改（即具有更大序列号的记录）应该被优先访问。

比如有两个内部键，Key1 = “user_key1”, Seq = 1002 和 Key1 = “user_key1”, Seq = 1001。在跳表中，第一个记录（Seq = 1002）将位于第二个记录（Seq = 1001）之前，因为1002 > 1001。当用 Seek 查找 <Key = user_key1, Seq = 1001> 时，自然会跳过 Seq = 1002 的记录。

所以拿到 internal key 后，不用再检查序列号。只用确认用户 key 相等后，再拿到 64 位的 tag，用 0xff 取出低 8 位的操作类型。对于删除操作会返回”未找到”的状态，说明该键值已经被删除了。对于值操作，则接着从 memtable key 后面解出 value 字节串，然后赋值给 value 指针。

友元类声明

除了前面的 Add 和 Get 方法，MemTable 类还声明了一个友元类 friend class MemTableBackwardIterator;，看名字是逆向的迭代器。不过在整个代码仓库，并没有找到这个类的定义。可能是开发的时候预留的一个功能，最后没有实现，这里忘记删除无效代码了。这里编译器没有报错是因为C++ 编译器在处理友元声明时不要求友元类必须已经定义。编译器仅检查该声明的语法正确性，只有当实际上需要使用那个类（例如创建实例或访问其成员）时，缺少定义才会成为问题。

此外还有一个友元 friend class MemTableIterator;，该类实现了 Iterator 接口，用于遍历 memTable 中的键值对。MemTableIterator 的方法如 key() 和 value() 依赖于对内部迭代器 iter_ 的操作，这个迭代器直接工作在 memTable 的 SkipList 上。这些都是 memTable 的私有成员，所以需要声明为友元类。

在 db_impl.cc 中，当需要将 immemtable 落地到 Level0 的 SST文件时，就会用到 MemTableIterator 来遍历 memTable 中的键值对。使用部分的代码如下，BuildTable 中会遍历 memTable，将键值对写入到 SST 文件中。

// db/db_impl.cc
Status DBImpl::WriteLevel0Table(MemTable* mem, VersionEdit* edit,
                                Version* base) {
  // ...
  Iterator* iter = mem->NewIterator();
  Log(options_.info_log, "Level-0 table #%llu: started",
      (unsigned long long)meta.number);

  Status s;
  {
    mutex_.Unlock();
    s = BuildTable(dbname_, env_, options_, table_cache_, iter, &meta);
    mutex_.Lock();
  }
  ...
}

这里遍历 memtable 时，用到一个友元类，为啥不直接提供一些 public 的接口来遍历呢？使用友元类的一个好处是，类的职责划分比较清晰。MemTableIterator 负责遍历 memTable 的数据，而 memTable 负责管理数据的存储。这种分离有助于清晰地定义类的职责，遵循单一职责原则，每个类只处理一组特定的任务，使得系统的设计更加模块化。

内存管理

最后来看看 MemTable 的内存管理。MemTable 类有一个 Arena 类的成员变量 arena_，用来管理跳表的内存分配。在插入键值对的时候，编码后的信息就存在 arena_ 分配的内存中。关于内存管理 Arena 类，可以参考LevelDB 源码阅读：内存分配器、随机数生成、CRC32、整数编解码。

为了能够在不使用 MemTable 的时候，及时释放内存，这里引入了引用计数机制来管理内存。引用计数允许共享对 MemTable 的访问权，而不需要担心资源释放的问题。对外也提供了 Ref 和 Unref 两个方法来增加和减少引用计数：

// Increase reference count.
void Ref() { ++refs_; }

// Drop reference count.  Delete if no more references exist.
void Unref() {
  --refs_;
  assert(refs_ >= 0);
  if (refs_ <= 0) {
    delete this;
  }
}

当引用计数减至零时，MemTable 自动删除自己，这时候就会调用析构函数 ~MemTable() 来释放内存。对象析构时，对于自定义的成员变量，会调用各自的析构函数来释放资源。在 MemTable 中，用跳表来存储 key，跳表的内存则是通过 Arena arena_; 来管理的。MemTable 析构过程，会调用 area_ 的析构函数来释放之前分配的内存。

Arena::~Arena() {
  for (size_t i = 0; i < blocks_.size(); i++) {
    delete[] blocks_[i];
  }
}

这里值得注意的是，MemTable 将析构函数 ~MemTable(); 设置为 private，强制外部代码通过 Unref() 方法来管理 MemTable 的生命周期。这保证了引用计数逻辑能够正确执行，防止了由于不当的删除操作导致的内存错误。

解答疑问

好了，这时候还有最后一个问题了，就是前面留的一个疑问，在 LevelDB Get 方法中，为啥不直接使用成员变量 mem_ 和 imm_ 来读取，而是创建了两个本地指针来引用呢？

如果直接使用 mem_ 和 imm_ 的话，会有什么问题？先考虑不加锁的情况，比如一个读线程正在读 mem_，这时候另一个写线程刚好写满了 mem_，触发了 mem_ 转到 imm_ 的逻辑，会重新创建一个空的 mem_，这时候读线程读到的内存地址就无效了。当然，你可以加锁，来把读写 mem_ 和 imm_ 都保护起来，但是这样并发性能就很差，同一时间，只允许一个读操作或者写操作。

为了支持并发，LevelDB 这里的做法比较复杂。读取的时候，先加线程锁，复制 mem_ 和 imm_ 用 Ref() 增加引用计数。之后就可以释放线程锁，在复制的 mem 和 imm 上进行查找操作，这里的查找操作不用线程锁，支持多个读线程并发。读取完成后，再调用 Unref() 减少引用计数，如果引用计数变为零，对象被销毁。

考虑多个读线程在读 mem_，同时有 1 个写线程在写入 mem_。每个读线程都会先拿到自己的 mem_ 的引用，然后释放锁开始查找操作。写线程可以往里面继续写入内容，或者写满后创建新的 mem_ 内存。只要有任何一个读线程还在查找，这里最开始的 mem_ 的引用计数就不会为零，内存地址就一直有效。直到所有读线程读完，并且写线程把 mem_ 写满，将它转为 imm_ 并写入 SST 文件后，最开始的 mem_ 的引用计数为零，这时候就触发析构操作，可以回收地址了。

看文字有点绕，我让 AI 整理一个 mermaid 的流程图来帮助理解吧：

mermaid 的源码可以在这里找到。

总结

在整个 LevelDB 架构中，MemTable 扮演着承上启下的角色。它接收来自上层的写入请求，在内存中积累到一定量后，转变为不可变的 Immutable MemTable，最终由后台线程写入磁盘形成 SST 文件。同时，它也是读取路径中优先级最高的组件，确保最新写入的数据能够立即被读取到。

本文我们详细分析了 LevelDB 中 MemTable 的实现原理与工作机制，最后再简单总结下MemTable 的核心设计：

基于跳表的实现：MemTable 内部使用跳表（SkipList）来存储数据，这种数据结构提供了平衡树的大部分优点，同时实现更为简单，能够高效地支持查找和插入操作。
内存管理机制：MemTable 通过 Arena 内存分配器来管理内存，统一分配和释放，避免内存碎片和提高内存利用率。
引用计数机制：通过 Ref() 和 Unref() 方法实现引用计数，支持并发访问，同时保证资源能在不再使用时及时释放。
特定键值编码格式：MemTable 中存储的键值对采用了特定的编码格式，包含键长度、用户键、序列号和类型标识、值长度以及值本身，支持了 LevelDB 的多版本并发控制（MVCC）。
友元类协作：通过友元类 MemTableIterator 来遍历 MemTable 中的数据，实现了关注点分离的设计原则。

MemTable 通过细致的内存管理和引用计数机制，解决了并发访问问题；通过跳表数据结构，实现了高效的查询和插入；通过特定的键值编码格式，支持了多版本并发控制。这些设计共同构成了 LevelDB 高性能、高可靠性的基础。

LevelDB 源码阅读：结合代码理解多版本并发控制(MVCC)

2025-06-11 01:47:42

在数据库系统中，并发访问是一个常见的场景。多个用户同时读写数据库，如何保证每个人的读写结果都是正确的，这就是并发控制要解决的问题。

考虑一个简单的转账场景，开始的时候 A 账户有 1000 元，要转 800 元给 B 账户。转账过程包括两步：从 A 扣钱，给 B 加钱。恰好在这两步中间，有人查询了 A 和 B 的余额。

如果没有任何并发控制，查询者会看到一个异常现象：A 账户已经被扣除了 800 元，只剩 200 元，B 账户还没收到转账，还是原来的金额！这就是典型的数据不一致问题。为了解决这个问题，数据库系统需要某种并发控制机制。

最直观的解决方案是加锁，当有人在进行写操作（如转账）时，其他人的读操作必须等待。回到前面的问题，只有在转账的两步都完成之后，才能查到正确的账户余额。但是锁机制存在明显的问题，每次只要写相关 key，所有读该 key 的操作都要排队等待，导致并发上不去，性能会比较差。

现代数据库系统普遍采用 MVCC 来控制并发，LevelDB 也不例外，接下来我们结合源码来理解 LevelDB 的 MVCC 实现。

通过 MVCC 控制并发

MVCC(Multi-Version Concurrency Control) 是一种并发控制机制，它通过维护数据的多个版本来实现并发访问。简单来说，LevelDB 的 MVCC 实现关键点有下面几个：

每个 key 可以有多个版本，每个版本都有自己的序列号(sequence number)；
写操作创建新版本而不是直接修改现有数据。不同的写入需要加锁互斥，保证每个写入获得递增的版本号。
不同的读操作之间可以并发，不用加锁。多个读操作也可以和写操作并发，不需要加锁。
通过 snapshot 来实现读和写、读和读之间的隔离，读取操作看到的总是某个时间点之前的数据版本。

这就是 MVCC 的核心思想了。我们通过一个具体的时间操作序列，来理解下 MVCC 是怎么工作的。假设有以下操作序列：

时间点 T1: sequence=100, 写入 key=A, value=1
时间点 T2: sequence=101, 写入 key=A, value=2
时间点 T3: Reader1 获取 snapshot=101
时间点 T4: sequence=102, 写入 key=A, value=3
时间点 T5: Reader2 获取 snapshot=102

那么不管 Reader1 和 Reader2 谁先读取，Reader1 读取 key=A 总会得到 value=2（sequence=101），Reader2 读取 key=A 会得到 value=3（sequence=102）。后续如果有新的读取，不带 snapshot 的读取会得到最新的数据。通过下面的时序图更容易理解，mermaid 源码在这里：

MVCC 的整体效果就如上了，还是比较容易理解的。下面看看 LevelDB 中是怎么实现 MVCC 的。

LevelDB 键带版本格式

实现 MVCC 的前提是，每个键都保存多个版本。所以要设计一个数据结构，把键和版本号关联起来。LevelDB 设计的 key 格式如下：

[key][sequence<<8|type]

LevelDB 的做法也比较容易理解，在原来的 key 后面拼上版本信息。这里版本信息是一个 64 位的 uint，其中高 56 位存储的是 sequence，低 8 位存储的是操作类型。这里操作类型目前只有两种，对应的分别是写入和删除操作。

// Value types encoded as the last component of internal keys.
// DO NOT CHANGE THESE ENUM VALUES: they are embedded in the on-disk
// data structures.
enum ValueType { kTypeDeletion = 0x0, kTypeValue = 0x1 };

这里序列号只有 56 位，所以最多可以支持 $ 2^{56} $ 次写入。这样实现会不会有问题？如果我想写入更多的 key 那岂不是不支持了？理论上是的，但是咱们从实际使用场景来分析下。假设每秒写入 100W 次，这个已经是很高的写入 QPS 了，那么可以持续写入的时间是：

$$ 2^{56} / 1000000 / 3600 / 24 / 365 = 2284 $$

嗯。。。能写 2000 多年，所以这个序列号是够用的，不用担心耗尽问题了。这里的数据格式设计虽然很简单，但还是有不少好处的：

同一个 key 支持不同版本，同一个 key 多次写入，最新写入的会有更高的序列号。在写入的同时，支持并发读这个 key 的更老版本。
类型字段(type)区分普通写入还是删除，这样删除并不是真正删除数据，而是写入一个删除标记，只有等待 compaction 时被真正删除。

我们知道 LevelDB 中键是顺序存储的，当要查询单个键时，可以用二分查找快速定位。当需要获取一系列连续键时，可以使用二分查找快速定位范围起点，然后顺序扫描即可。但现在我们给键增加了版本号，那么问题来了，带版本号的键要怎么排序呢？

内部键排序方法

LevelDB 的做法也是比较简单有效，排序规则如下：

首先按键升序排列，这里是按照字符串的字典序排序；
然后按序列号降序排列，序列号越大越靠前；
最后按类型降序排列，写入类型靠前，删除类型靠后；

为了实现这里的排序规则，LevelDB 实现了自己的比较器，在 db/dbformat.cc 中，代码如下：

int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {
  // Order by:
  //    increasing user key (according to user-supplied comparator)
  //    decreasing sequence number
  //    decreasing type (though sequence# should be enough to disambiguate)
  int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
  if (r == 0) {
    const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
    const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
    if (anum > bnum) {
      r = -1;
    } else if (anum < bnum) {
      r = +1;
    }
  }
  return r;
}

可以看到首先从带版本号的 key 中去掉后 8 位，拿到真实的用户键，之后按照用户键的排序规则进行比较。这里再多说一句，LevelDB 提供了一个默认的用户键比较器 leveldb.BytewiseComparator，这里是完全按照键值的字节序进行比较。比较器的实现代码在 util/comparator.cc 中，如下：

class BytewiseComparatorImpl : public Comparator {
 public:
  BytewiseComparatorImpl() = default;

  const char* Name() const override { return "leveldb.BytewiseComparator"; }

  int Compare(const Slice& a, const Slice& b) const override {
    return a.compare(b);
  }
  // ...

这里 Slice 是 LevelDB 中定义的一个字符串类，用于表示一个字符串，它的 compare 就是字节码比较。其实 LevelDB 也支持用户自定义比较器，只需要实现 Comparator 接口即可。这里多说一点，在使用比较器的时候，用 BytewiseComparator 封装了一个单例，代码有点难理解，如下：

const Comparator* BytewiseComparator() {
  static NoDestructor<BytewiseComparatorImpl> singleton;
  return singleton.get();
}

我之前专门写了一篇文章来解释 NoDestructor 模板类，感兴趣的可以看下：LevelDB 源码阅读：禁止对象被析构。

这种排序规则的好处也是显而易见的，首先按照用户键升序排列，这样范围查询非常高效。当用户需要获取一系列连续键时，可以使用二分查找快速定位范围起点，然后顺序扫描即可。另外，同一个用户键的多个版本按序列号降序排列，这意味着最新版本在前，便于快速找到当前值。查询时，只需找到第一个序列号小于等于当前快照的版本，不需要完整扫描所有版本。

好了，关于排序就说到这。下面咱们结合代码来看看写入和读取的时候，是怎么拼接 key 的。

写入带版本键

LevelDB 写入键值对的步骤比较复杂，可以看我之前的文章：LevelDB 源码阅读：写入键值的工程实现和优化细节。简单说就是先写入 memtable，然后是 immutable memtable，最后不断沉淀(compaction)到不同层次的 SST 文件。整个过程的第一步就是写入 memtable，所以在最开始写入 memtable 的时候，就会给 key 带上版本和类型，组装成前面我们说的带版本的内部 key 格式。

这里组装 Key 的代码在 db/memtable.c 的 MemTable::Add 函数中。这里除了组装 key，还拼接了 value 部分。实现如下：

void MemTable::Add(SequenceNumber s, ValueType type, const Slice& key,
                   const Slice& value) {
  // Format of an entry is concatenation of:
  //  key_size     : varint32 of internal_key.size()
  //  key bytes    : char[internal_key.size()]
  //  tag          : uint64((sequence << 8) | type)
  //  value_size   : varint32 of value.size()
  //  value bytes  : char[value.size()]
  size_t key_size = key.size();
  size_t val_size = value.size();
  size_t internal_key_size = key_size + 8;
  const size_t encoded_len = VarintLength(internal_key_size) +
                             internal_key_size + VarintLength(val_size) +
                             val_size;
  char* buf = arena_.Allocate(encoded_len);
  char* p = EncodeVarint32(buf, internal_key_size);
  std::memcpy(p, key.data(), key_size);
  p += key_size;
  EncodeFixed64(p, (s << 8) | type);
  p += 8;
  p = EncodeVarint32(p, val_size);
  std::memcpy(p, value.data(), val_size);
  assert(p + val_size == buf + encoded_len);
  table_.Insert(buf);
}

可以看到这里同一个用户键的多次写入会产生多个版本，每个版本都有唯一的 sequence number。用户键一旦被转换为内部键，后续所有处理过程都基于这个内部键进行。包括 MemTable 转为 Immutable MemTable，SST 文件写入，SST 文件合并等。

这里 Add 函数中，在 internal_key 内部键的前面其实也保存了整个内部键的长度，然后把长度和内部键拼接起来，一起插入到了 MemTable 中。这样的 key 其实是 memtable_key，后续在读取的时候，也是用 memtable_key 来在 memtable 中查找的。

这里为什么要保存长度呢？我们知道 Memtable 中的 SkipList 使用 const char* 指针作为键类型，但这些指针只是指向内存中某个位置的裸指针。当跳表的比较器需要比较两个键时，它需要知道每个键的确切范围，也就是起始位置和结束位置。如果直接使用 internal key，就没有明确的方法知道一个 internal key 在内存中的确切边界。加上长度信息后，就可以快速定位到每个键的边界，从而进行正确的比较。

读取键值过程

接下来看看读取键值的过程。在读取键值的时候，会先把用户键转为内部键，然后进行查找。不过这里首先面临一个问题是，序列号要用哪个呢。回答这个问题前，我们先来看读取键常用的的方法，如下：

1 2	std::string newValue; status = db->Get(leveldb::ReadOptions(), "key500", &newValue);

这里有个 ReadOptions 参数，里面会封装一个 Snapshot 快照对象。这里的快照你可以理解为数据库在某个时间点的状态，里面有这个时间点之前所有的数据，但不会包含这个时间点之后的写入。

其实这里快照的核心实现就是保存某个时间点的最大序列号，读取的时候，会用这个序列号来组装内部键。读的时候，分两种情况，如果没有指定 snapshot，使用当前最新的 sequence number。如果使用了之前保存下来的 snapshot，则会使用 snapshot 的序列号。

之后会根据快照序列号和用户键组装，这里先定义了一个 LookupKey 对象，用来封装查找时候使用内部键的一些常用操作。代码在 db/dbformat.h 中，如下：

// A helper class useful for DBImpl::Get()
class LookupKey {
 public:
  // Initialize *this for looking up user_key at a snapshot with
  // the specified sequence number.
  LookupKey(const Slice& user_key, SequenceNumber sequence);

  LookupKey(const LookupKey&) = delete;
  LookupKey& operator=(const LookupKey&) = delete;

  ~LookupKey();

  // Return a key suitable for lookup in a MemTable.
  Slice memtable_key() const { return Slice(start_, end_ - start_); }
  // Return an internal key (suitable for passing to an internal iterator)
  Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }
  // Return the user key
  Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }

  // ...
}

在 LookupKey 的构造函数中，会根据传入的 user_key 和 sequence 来组装内部键，具体代码在 db/dbformat.cc 中。后续在 memtable 中搜索的时候，用的 memtable_key，然后在 SST 中查找的时候，用的 internal_key。这里 memtable_key 就是我们前面说的，在 internal_key 的前面加上了长度信息，方便在 SkipList 中快速定位到每个键的边界。

这里在 memtable 和 immutable memtable 中找不到的话，会去 SST 中查找。SST 的查找就相当复杂一些，涉及多版本数据的管理，后续我会专门写文章来介绍这里的读取过程。

总结

本篇对 MVCC 的讲解还比较浅显，介绍了大概的概念，以及重点讲了下读取和写入过程中如何对序列号进行处理的过程。并没有深入数据多版本管理，以及旧版本数据回收清理的过程。后面文章再深入这些话题。

总的来说，LevelDB 通过在键值中引入版本号，实现了多版本并发控制。通过 snapshot 来实现读取隔离，写入永远创建新版本。对于读操作来说，不需要加锁，可以并发读取。对于写操作来说，需要加锁，保证写入的顺序。

这种设计提供了很好的并发性能，保证了读取的一致性，同时减少了锁冲突。不过代价是存储空间的额外开销，以及需要保存多个版本带来的代码复杂度。

使用 Cursor 深度体验 3 个 MCP Server，惊艳但并不实用?

2025-05-23 19:39:14

大语言模型刚出来的时候，只是通过预训练的模型来生成回答内容。这个时候的模型有两个主要的缺点：

有些数据它不知道，比如 2024 年 3 月训练的模型，就不知道 2024 年 5 月的事情；
没法使用外部工具。这里的工具我们可以等效理解为函数调用，比如我有个发表文章的工具函数，我没法用自然语言让大模型来帮我调用这个函数。

为了解决这两个问题，OpenAI 最先在模型中支持了 function calling 功能，他们在这篇博客: Function calling and other API updates 有介绍。

背景：理解 Function Calling

这时候，我们就可以告诉模型，我有这么几个工具，每个工具需要什么参数，然后能做什么事情，输出什么内容。当模型收到具体任务的时候，会帮我们选择合适的工具，并解析出参数。之后我们可以执行相应的工具，拿到结果。并可以接着循环这个过程，让 AI 根据工具结果继续决定往下做什么事情。

我在网上找了个动图，可以来理解下有了 function calling 后，做事情的流程：

当然这里大模型只是根据我们给的工具列表，选择合适的工具，并解析出参数。它不能直接去调用工具，我们需要编程实现工具调用部分，可以参考 OpenAI 的 Function calling 文档。

为什么又引入了 MCP

只有 function calling 已经能做很多事了，派生了不少有意思的项目，比如 AutoGPT，可以说是最早的 Agent 智能体了。

但是有个问题，就是不同厂商 function calling 实现各不相同，开发者需要为每个平台单独适配。另外开发者还需要编写代码来解析 function calling 的输出，并调用相应的工具。这里面有不少工程的工作，比如失败重试、超时处理、结果解析等。

计算机领域，没有什么是不能通过加个中间层来解决的。过了一年多，随着模型能力提升，各种外部工具的丰富，Anthropic 在2024年11月25日推出了 MCP 协议，引入了 MCP Client 和 MCP Server 这个中间层，来解决解决 LLM 应用与外部数据源和工具之间通信的问题。

当然其实这中间也有一些其他方案，来赋予模型调用外部工具的能力，比如 OpenAI 推出的 ChatGPT Store，曾经也火了一阵子的 GTPs，不过目前似乎很少看到人用了。

目前比较流行的就是 MCP 了，这里有个图，可以帮助你理解：

咱们这篇文章主要是介绍实用体验，所以关于背景的交代就到这里。如果对 MCP 的开发感兴趣，可以看官方文档，介绍的还是十分详细的。

Cursor MCP 使用方法

在使用之前，我先简单介绍下 Cursor 使用 MCP 的方法。Cursor 接入 MCP 还是挺方便的，对于大部分不需要密钥的 MCP Server，基本一个配置就能接入。现在 MCP 发展还挺快，所以建议大家直接去看 Cursor 的官方文档，获取最新信息。网上不少教你如何配置的文章，其实都过时了。

这里我给大家介绍下配置的整体思想，方便你理解文档。Cursor 在这里相当于 AI 应用，它内置了 MCP Client，所以你不用管 Client 部分了。你只需要告诉他你有哪些 MCP Server，然后在会话聊天中 Cursor 会自动调用工具并使用它的结果。

先祭出上面这张图，方便你理解。目前大部分 AI 应用都是用 json 文件来配置 MCP Server 的，比如 Claude Desktop。Cursor 也是如此，它支持全局配置(~/cursor/mcp.json)，也可以在项目中(.cursor/mcp.json) 配置。

目前 Cursor 支持本地 MCP CLI Stdio Server 和远程 MCP SSE Server 两种方式，关于 SSE 可以参考我之前的文章结合实例理解流式输出的几种实现方法。本地的 CLI 方式，其实就是在本地机器启动一个 Server 进程，然后 Cursor 通过标准输入输出来和这个本地进程交互。

这里本地的 Server 支持 Python，Node 服务，也支持 Docker 容器。不过前提是本地机器已经安装了对应的语言环境，能跑起来相应的启动命令。这 3 种方式，我都给了一个例子：

1
2
3

npx @browsermcp/mcp@latest
uvx mcp-server-browser-use@latest
docker run -i --rm -e GITHUB_PERSONAL_ACCESS_TOKEN ghcr.io/github/github-mcp-server

有时候 MCP Server 里面还需要一些配置，比如 Github 的 API 密钥，这时候就需要你手动配置了。提醒下你要把密钥配置到环境变量中，千万不要把密钥上传到代码仓库哦。

具体到某个 MCP Server，你可以参考它的文档，看如何配置，应该没什么难度。配置好 json 后，Cursor 会自动识别，你可以打开这个 MCP Server，过一会看到绿色标记和列出来的工具，就说明配置成功了。

接下来终于到重头戏了，咱们来体验下 MCP 的实际效果。

MCP 体验一：网页自动操作

之前就经常想着让 AI 来自动化执行一些网页任务。比如自动去某个站点搜索、浏览指定主题的内容，进行回复，或者导出一些有意义的内容。于是试了下微软的无头 playwright MCP Server，给了它一个比较复杂的任务:

帮我打开淘宝，搜索苹果手机，找到最新款的苹果手机，给出店铺销量最高的几家，并导出每家店铺的销量和价格。

确实如期打开了淘宝，并真的找到了搜索框，输入了苹果手机，如图:

但是后面弹了一个登录框，Claude 3.7 在这里卡了很久，也没解决。跑了一阵子，最后的输出是这样的：

我注意到我们看到了一个登录弹窗，这可能是因为淘宝网站要求用户登录才能查看详细搜索结果。这是淘宝网站的常见安全措施，特别是对于非登录用户通过自动化工具访问时。
让我尝试取消登录弹窗，点击关闭按钮：
我们看到点击关闭按钮后，淘宝网站依然要求登录才能查看搜索结果。淘宝网站对非登录用户有严格的安全限制，特别是使用自动化工具访问时。
由于需要登录才能查看详细的苹果手机信息，我可以尝试使用其他方式获取有关苹果手机的信息。例如，我可以使用网络搜索查找有关最新款苹果手机及其销量和价格信息的公开数据：

最后开始联网搜索，和我本意差的有点远。这里登录态确实不好处理，我找了另一个 MCP Server，它支持在本地浏览器中运行，这样可以登录后再让 AI 来操作。这个工具的原理是，在本地浏览器安装一个插件，然后 MCP Server 来控制本地浏览器。

使用下来，目前登录态是没问题了，但有些网站有部分防爬的功能，页面元素做了些保护，这个 MCP Server 还没法完美的操控，比如没法成功点击按钮，另外滚动起来也是很卡顿。

其实目前 LLM 操控浏览器还是有不少难度的，最近一个比较火的 Browser Use 项目，它除了用 HTML 元素，还尝试用视觉元素来操控浏览器。整体前景会好一些，等我有 Token 了再来深度体验下这个。

MCP 体验二：Github 仓库信息分析

再来试试 Cursor 官方例子中的 Github MCP Server，它支持搜索仓库、代码、issue，创建 PR 等。我想到一个场景就是，遇到一个火的项目，可以先让 AI 总结下目前比较火的 PR 或者 Issue，然后看看有没有可以贡献的地方。当然了，如果 AI 找到有价值的 Issue，然后再分析代码，给出解决方案，并自动提交代码，那这个价值就更大了。

当然，咱先拆分问题，来个低难度的信息收集：

LevelDB 这个项目中，有哪些讨论比较多，还没合并的 pull request 啊

这里用的 Claude3.7，竟然有点死循环了，一直在 Call list_pull_requests 这个工具，参数也基本一样：

{
  "owner": "google",
  "repo": "leveldb",
  "state": "open",
  "sort": "updated",
  "direction": "desc",
  "perPage": 30
}

查了 10 多遍，也没自动终止。PR 查不成功，我换了下查 Issue，这次还可以，用 list_issues 工具，查了 3 页，参数类似下面:

{
  "owner": "google",
  "repo": "leveldb",
  "state": "open",
  "sort": "comments",
  "direction": "desc",
  "perPage": 10,
  "page": 3
}

最后也给出了一些结论，如图：

检查了几个，没什么大问题，这个我还是挺满意的。遇到一个大的项目，能够快速找到大家讨论多的 Issue，然后分析下，确实能帮上忙。不过我怀疑这里没找完，只有 3 页，其实一共 200 多个 Issue 呢。

然后继续聚焦其中一个 PR #917，让他给我分析下。刚好今天 Claude 推出了 Sonnet 4 模型，用这个新的模型让他分析下。不得不说，针对这种拆解开的小的问题，AI 分析还是很强的。

先是收集了这个 PR 的评论，PR 的代码改动，然后还拉了这个 PR 提到的另外 2 个 Issue，综合了这么多信息后，给出了一个详细的分析。分析也十分给力，先是问题描述，问题背景和表现，接着是提议的解决方案，社区针对这个方案的讨论焦点，比如性能影响，作者回应等。最后还给出这个 PR 的当前状态，从 2021 年 6 月提交至今，还没合并进去。这里的分析太惊艳了，看来后面遇到一些开源项目的问题，还是可以来用下的。

这里是截图：

当然看了下 Github MCP Server 的文档，这里不止是提供了读仓库，读 Issue 的能力，还有修改仓库的能力。包括提交 PR，创建 Issue，创建评论，创建标签，新建分支等。我还没来得及深入使用下这些会改动仓库的功能，等后面有机会再接着体验。

MCP 体验三：图表生成

有时候会经常根据数据生成一些好看的报表，之前还有 AI 写了一个工具，来生成动态柱状图。现在有了 MCP 后，可以试试让 AI 来生成图表。其实有不少很酷的生成图表的库，比如 echarts 这些。看了下现在没有官方的图表库，不过找到了一个 mcp-server-chart，它支持生成 echarts 的图表。

这里有最近 10 年中国各省份人口变化的动态竞速图，导了一份数据出来，然后试试 MCP Server 生成图表效果如何。

直接给它一份文件，然后提示：

@china_population.csv 结合这份中国人口变化数据，生成一个 2022 年和2023 年各省份人口的柱状图

这里用的 Claude 4 Sonnet 模型，成功调用了 mcp-server-chart 的 generate_column_chart 工具，生成了图表。不过这个工具返回的是图片 URL，需要去输出里复制出来打开才能看。其实 Cursor 支持输出图片的 Base64 编码，这样聊天里也能加载出来。工具返回的图片地址在这，效果如下：

然后我发现这个工具支持其他类型的图表，比如折线图，散点图，饼图等。有个图我不知道啥图，但效果还挺好的，我就截了个图给 Claude，提示：

参考这张图，生成一个 2023 年各省人口的图

它先分析这是一个树状图，然后帮我生成了结果，还解释了下。解释超大矩形块是广东省，占据最大面积，提现了人口第一大省的地位。生成图地址在这，我这里也放出来吧：

效果还是可以的。目前这个工具每个图表一个 Tool，支持的图表类型还是有限的。

MCP 使用限制

目前的 MCP 还是存在一些限制的，首先咱们要明确一点，MCP 协议只是加了个 Server 和 Client 的中间层，它还是要依赖 LLM 的 function calling 能力。而 function calling 会受到 LLM 的上下文长度限制，工具的描述信息，参数等都会占用 Token。

当工具数量太多或者描述复杂的时候，可能会导致 Token 不够用。另外，就算 Token 够用，如果提供的工具描述过多，也会导致模型效果下降。OpenAI 的文档也有提到：

Under the hood, functions are injected into the system message in a syntax the model has been trained on. This means functions count against the model’s context limit and are billed as input tokens. If you run into token limits, we suggest limiting the number of functions or the length of the descriptions you provide for function parameters.

MCP 基于 function calling 能力，所以也有同样的限制。MCP server 如果提供了过多的工具，或者工具描述太复杂，都会影响到实际效果。

比如拿 Cursor 来说，它推荐打开的 MCP Servers 最多提供 40 个工具，太多工具的话，模型效果不好。并且有的模型也不支持超过 40 个工具。

MCP 的实用价值？

好了，咱们介绍完 MCP 背景以及使用方法以及限制了，最后来聊下 MCP 的实用价值。目前市面上有太多 MCP Server 了，Cursor 有个 MCP Server 列表页，有需求的话可以在这找找看。

大致看了下，觉得有些 MCP Servers 后面可能会继续尝试用一用。

firecrawl-mcp-server: 这个工具可以搜索网页，并导出网页内容。还支持搜索，深度研究以及批量爬取。感觉后面写一些文章的时候，可以用来收集参考资料。爬网页这个需求还是会有的，也有不少类似的 MCP Server，后面都可以玩玩看了。
MiniMax-MCP: 最近 MiniMax 的语言合成冲到了榜首，体验了下确实很不错。有几十款音色，每个都很有特色，听起来几乎就是真人的了。这款 MCP Server 支持调用 MiniMax 的合成接口，可以用来生成一些语音内容，来尝尝鲜也是可以的。
mcp-clickhouse: 这类 DB 操作类的 MCP Server 如果足够强大的话也不错，可以聊着天就把数据查出来了，对普通人来说足够了。再配合图表类的 MCP Server，真的就能一句话把数据可视化出来。这里不止 Clickhouse 有，Mysql，Sqlite，Redis 这些都有 MCP Server，后面可以试试。

就目前试过的几款，确实有些不错的亮点功能，但还不能让我觉得有特别大的价值。尝鲜之后，也就就束之高阁了。也就 Github MCP Server 让我觉得后面可能会用得到。

不过文章还没写好 Claude Sonnet 4 模型就发布了，号称世界上最强编程模型。推理能力也有很大提升，等后面多用一段时间，才能有一个真实的体感。或许随着模型能力提升，各个 MCP Server 的持续优化，有一天终会变成大家每天都离不开的工具吧。

不知道各位有什么好的 MCP Server 使用场景吗？欢迎留言讨论。

LevelDB 源码阅读：写入键值的工程实现和优化细节

2025-01-25 02:00:00

读、写键值是 KV 数据库中最重要的两个操作，LevelDB 中提供了一个 Put 接口，用于写入键值对。使用方法很简单：

1 2	leveldb::Status status = leveldb::DB::Open(options, "./db", &db); status = db->Put(leveldb::WriteOptions(), key, value);

LevelDB 最大的优点就是写入速度也非常快，可以支持很高的并发随机写。官方给过一个写入压力测试结果：

fillseq      :       1.765 micros/op;   62.7 MB/s
fillsync     :     268.409 micros/op;    0.4 MB/s (10000 ops)
fillrandom   :       2.460 micros/op;   45.0 MB/s
overwrite    :       2.380 micros/op;   46.5 MB/s

可以看到这里不强制要求刷磁盘的话，随机写入的速度达到 45.0 MB/s，每秒支持写入 40 万次。如果强制要求刷磁盘，写入速度会下降不少，也能够到 0.4 MB/s, 每秒支持写入 3700 次左右。

这里 Put 接口具体做了什么？数据的写入又是如何进行的？LevelDB 又有哪些优化？本文一起来看看。开始之前，先看一个大致的流程图：

LevelDB 写入 key 的 2 种方式

LevelDB 支持一次写入一个键值对，也支持一次写入多个键值对。不论是单个写入，还是批量写内部都是通过 WriteBatch 来处理。

Status DB::Put(const WriteOptions& opt, const Slice& key, const Slice& value) {
  WriteBatch batch;
  batch.Put(key, value);
  return Write(opt, &batch);
}

我们可以选择在调用 LevelDB 接口的应用层聚合写入操作，从而实现批量写入，提高写入吞吐。例如，在应用层可以设计一个缓冲机制，收集一定时间内的写入请求，然后将它们打包在一个 WriteBatch 中提交。这种方式可以减少磁盘的写入次数和上下文切换，从而提高性能。

当然也可以每次都写入单个键值，这时候 LevelDB 内部会通过 WriteBatch 来处理。如果在高并发情况下，可能会在内部合并多个写操作，然后将这批键值对写入 WAL 并更新到 memtable。

这里整体写入还是比较复杂的，本篇文章只先关注写入到 WAL 和 memtable 的过程。

LevelDB 写入详细步骤

完整的写入部分代码在 leveldb/db/db_impl.cc 的 DBImpl::Write 方法中，咱们一点点拆开看吧。

Status DBImpl::Write(const WriteOptions& options, WriteBatch* updates) {
  Writer w(&mutex_);
  w.batch = updates;
  w.sync = options.sync;
  w.done = false;

  MutexLock l(&mutex_);
  writers_.push_back(&w);
  while (!w.done && &w != writers_.front()) {
    w.cv.Wait();
  }
  if (w.done) {
    return w.status;
  }
  // ...
}

开始部分把 WriteBatch 和 sync 参数赋值给 Writer 结构体，然后通过一个 writers_ 队列来管理多个 Writer 结构体。这两个结构体和队列在整个写入过程中还是挺重要的，先来看看。

Writer 结构和处理队列

这里 writers_ 是一个 std::deque<Writer*> 类型的队列，用于管理多个 Writer 结构体。

1	std::deque<Writer*> writers_ GUARDED_BY(mutex_);

这里队列用 GUARDED_BY(mutex_) 装饰，表示队列的访问需要通过 mutex_ 互斥锁来保护。这个用到了 Clang 的静态线程安全分析功能，可以参考我之前的文章 LevelDB 源码阅读：利用 Clang 的静态线程安全分析

这里 Writer 结构体定义如下：

struct DBImpl::Writer {
  explicit Writer(port::Mutex* mu)
      : batch(nullptr), sync(false), done(false), cv(mu) {}

  Status status;
  WriteBatch* batch;
  bool sync;
  bool done;
  port::CondVar cv;
};

这里 Writer 结构体封装了不少参数，其中最重要是一个 WriteBatch 指针，记录了每个 WriteBatch 写请求的数据。然后用一个 status 用来记录每个 WriteBatch 写请求的错误状态。

此外，用一个 sync 来标记每个 WriteBatch 写请求是否需要立马刷到磁盘中。默认是 false，不强制刷磁盘，如果系统崩溃，可能会丢掉部分还没来得及写进磁盘的数据。如果打开了 sync 选项，每次写入都会立马刷到磁盘，整体写入耗时会上涨，但是可以保证只要写入成功，数据就不会丢失。关于刷磁盘文件的更多细节，可以参考我之前的文章LevelDB 源码阅读：Posix 文件操作接口实现细节。

还有一个 **done 则用来标记每个 WriteBatch 的写请求是否完成。**这里因为内部可能会合并写入多个 WriteBatch，当本次写入请求被合并到其他批次写入后，本次请求标记完成，就不需要再处理了。从而避免重复执行，提高并发的写入效率。

为了实现等待和通知，这里还有一个条件变量 cv，用于支持多个写请求的批量处理，并实现多个写请求的同步。写入的时候，多个线程可以同时提交写入请求，每个写请求都会先被放入写入队列。实际写入过程，则是串行化写入，同一时刻只有一批写入过程在执行。每次会从队列中取出队首的写请求，如果此时队列中还有其他等待的写任务，则会被合并为一个批次一起处理。在当前批次的写入请求处理过程中，后续来的请求进入队列后都需要等待。当前批次的请求处理完成后，会通知后面进入队列在等待中的写请求。

结合这里的介绍，应该能看懂前面 Write 方法开始部分代码的含义了。对于每个写入请求，都会先创建一个 Writer 结构体，然后将其放入 writers_ 队列中。接下来在 while 循环中，判断当前写入请求是否完成，如果完成就会直接返回当前写入的状态结果。如果当前写入请求没在队首，则需要等待在 cv 条件变量上。

如果当前写入请求在队首，那么就需要执行实际的写入操作了，这里具体写入流程是什么样呢？

预先分配空间

接下来在正式写入前，要先确保有足够的空间来写入数据。这里会调用 MakeRoomForWrite 方法，确保在进行写入操作之前，有足够的资源和空间来处理新的写入请求。它负责管理内存表（memtable）的使用情况、控制 Level 0 文件的数量，并在需要时触发后台压缩。

// REQUIRES: this thread is currently at the front of the writer queue
Status DBImpl::MakeRoomForWrite(bool force) {
  mutex_.AssertHeld();
  assert(!writers_.empty());
  bool allow_delay = !force;
  Status s;
  while (true) {
    if (!bg_error_.ok()) {
      // Yield previous error
      s = bg_error_;
      break;
    }
    // ...
  }
}

这里开始部分是一些验证部分，用 AssertHeld 验证当前线程必须持有 mutex_ 互斥锁，并且 writers_ 队列不能为空。接着会判断 bg_error_ 是否为空，如果不为空，则直接返回 bg_error_ 状态。在下文中会看到，如果写入 WAL 刷磁盘失败，就会设置 bg_error_ ，这样会让后续的写入都直接返回失败。

在 while 循环中，接着是一系列 if 分支检查，处理不同情况。

else if (allow_delay && versions_->NumLevelFiles(0) >=
                                  config::kL0_SlowdownWritesTrigger) {
      // We are getting close to hitting a hard limit on the number of
      // L0 files.  Rather than delaying a single write by several
      // seconds when we hit the hard limit, start delaying each
      // individual write by 1ms to reduce latency variance.  Also,
      // this delay hands over some CPU to the compaction thread in
      // case it is sharing the same core as the writer.
      mutex_.Unlock();
      env_->SleepForMicroseconds(1000);
      allow_delay = false;  // Do not delay a single write more than once
      mutex_.Lock();
    }

首先当 Level 0 文件数量接近 kL0_SlowdownWritesTrigger=8 阈值时，暂时释放锁，延迟 1 毫秒，以减缓写入速度。当然这里只允许延迟一次，避免长时间阻塞单个写入。这里之所以设置一个小的 Level 0 文件数量阈值，是为了防止 Level 0 文件太多后，到达系统瓶颈后，后续写入卡太长时间。在没到瓶颈前，就开始把延迟平摊到每个请求上，从而减缓压力。这里的注释也写的很清楚，上面也都贴出来了。

else if (!force &&
           (mem_->ApproximateMemoryUsage() <= options_.write_buffer_size)) {
  // There is room in current memtable
  break;
}

接着这里判断如果当前 memtable 的使用量没超过最大容量，就直接返回了。这里 write_buffer_size 是 memtable 的最大容量，默认是 4MB。这里可以调整配置，如果大一点的话，会在内存缓存更多数据，提高写入的性能，但是会占用更多内存，并且下次打开 db 的时候，恢复时间也会更长些。

接下来有两种情况，是当前没有地方可以写入，因此需要等待了。

else if (imm_ != nullptr) {
  // We have filled up the current memtable, but the previous
  // one is still being compacted, so we wait.
  Log(options_.info_log, "Current memtable full; waiting...\n");
  background_work_finished_signal_.Wait();
} else if (versions_->NumLevelFiles(0) >= config::kL0_StopWritesTrigger) {
  // There are too many level-0 files.
  Log(options_.info_log, "Too many L0 files; waiting...\n");
  background_work_finished_signal_.Wait();
}

第一种情况是不可变的 memtable 还在写入中，因此需要等待它写入完成。LevelDB 会维护两个 memtable，一个是当前可以写入的 memtable mem_，一个是不可变的 memtable imm_。每次写满一个 mem_ 后，就会把它转为 imm_ 然后刷数据到磁盘。如果 imm_ 还没完成刷磁盘，那么就必须等待刷完后才能把现有的 mem_ 转为新的 imm_。

第二种情况是 Level 0 文件数量太多，需要等待压缩完成。LevelDB 配置了 Level 0 文件数量的阈值 kL0_StopWritesTrigger，默认是 12，当 Level 0 文件数量超过这个阈值时，那么当前写入请求就需要等待。因为 Level 0 层的文件之间没有全局排序的保证，多个 Level 0 文件可能包含重叠的键范围。对于读来说，查询操作需要在所有 L0 文件中查找，文件数量过多会增加读取延迟。对于写来说，文件数量多，后台压缩的工作量也会增加，影响整体系统性能。所以这里强制控制 Level 0 的文件数量，达到阈值后就直接不给写入。

接下来的情况就是不可变的 imm_ 为空，同时 mem_ 也没足够空间，这时候要做的事情比较多：

创建新日志文件：生成新的日志文件号，并尝试创建新的 writable file 作为 WAL（Write-Ahead Log）。如果失败，重用文件号并退出循环，返回错误状态。
关闭旧日志文件：关闭当前日志文件。如果关闭失败，记录后台错误，阻止后续写入操作。
更新日志文件指针：设置新的日志文件指针，更新日志编号，创建新的 log::Writer 进行写入。
转换 memtable：将当前 memtable 转换为不可变 memtable（imm_），并创建新的 memtable 进行写入。通过 has_imm_.store(true, std::memory_order_release) 标记有不可变 memtable 存在。
触发后台压缩：调用 MaybeScheduleCompaction()，触发后台压缩任务，处理不可变 memtable。

这里可以看到 memtable 和 WAL 文件一一对应的，每个 memtable 对应一个 WAL 文件，WAL 文件记录写入 memtable 的所有操作，当 memtable 满时，同时切换 WAL 文件。同一时刻，前台 memtable 和新的 WAL 日志文件处理新的请求，同时后台的 imm_ 和旧的 WAL 文件处理压缩任务。等压缩完成，就可以删除旧的 WAL 文件了。

合并写入任务

接着是合并写入的逻辑，核心代码如下：

uint64_t last_sequence = versions_->LastSequence();
Writer* last_writer = &w;
if (status.ok() && updates != nullptr) {  // nullptr batch is for compactions
  WriteBatch* write_batch = BuildBatchGroup(&last_writer);
  WriteBatchInternal::SetSequence(write_batch, last_sequence + 1);
  last_sequence += WriteBatchInternal::Count(write_batch);

  {
   // ... 具体写入到 WAL 和 memtable 
  }
  if (write_batch == tmp_batch_) tmp_batch_->Clear();

  versions_->SetLastSequence(last_sequence);
}

首先是获取当前全局的 sequence 值，这里 sequence 用来记录写入键值对的版本号，全局单调递增。每个写入请求都会被分配一个唯一的 sequence 值，通过版本号机制来实现 MVCC 等特性。在写入当前批次键值对的时候，会先设置 sequence 值，写入成功后，还会更新 last_sequence 值。

为了提高写入并发性能，每次写入的时候，不止需要写队首的任务，还会尝试合并队列中后续的写入任务。这里合并的逻辑放在 BuildBatchGroup 中，主要是遍历整个写入队列，在控制整体批次的大小，以及保证刷磁盘的级别情况下，不断把队列后面的写入任务合并到队首的写入任务中。整体构建好的写入批次，会放到一个临时的对象 tmp_batch_ 中，在完整的写入操作完成后，会清空 tmp_batch_ 对象。

我们提到的每个写入任务其实封装为了一个 WriteBatch 对象，该类的实现支持了不同写入任务合并，以及获取任务的大小等。相关细节实现可以参考我前面的文章 LevelDB 源码阅读：如何优雅地合并写入和删除操作。

上面代码其实忽略了核心的写入到 WAL 和 memtable 的逻辑，下面来看看这部分的实现。

写入到 WAL 和 memtable

LevelDB 中写入键值对，会先写 WAL 日志，然后写入到 memtable 中。WAL 日志是 LevelDB 中实现数据恢复的关键，memtable 则是 LevelDB 中实现内存缓存和快速查询的关键。写入关键代码如下：

// Add to log and apply to memtable.  We can release the lock
// during this phase since &w is currently responsible for logging
// and protects against concurrent loggers and concurrent writes
// into mem_.
{
  mutex_.Unlock();
  status = log_->AddRecord(WriteBatchInternal::Contents(write_batch));
  bool sync_error = false;
  if (status.ok() && options.sync) {
    status = logfile_->Sync();
    if (!status.ok()) {
      sync_error = true;
    }
  }
  if (status.ok()) {
    status = WriteBatchInternal::InsertInto(write_batch, mem_);
  }
  mutex_.Lock();
  if (sync_error) {
    // The state of the log file is indeterminate: the log record we
    // just added may or may not show up when the DB is re-opened.
    // So we force the DB into a mode where all future writes fail.
    RecordBackgroundError(status);
  }
}

这里在写入到 WAL 和 memtable 的时候，会先释放 mutex_ 互斥锁，写入完成后，再重新加锁。注释也专门解释了下，因为当前队首 &w 正在负责写入 WAL 和 memtable，后续的写入调用，可以拿到 mutex_ 互斥锁，因此可以完成入队操作。但是因为不是队首，需要等在条件变量上，只有当前任务处理完成，才有机会执行。所以写入 WAL 和 memtable 的过程，虽然释放了锁，但整体还是串行化写入的。WAL 和 memtable 本身也不需要保证线程安全。

不过因为写 WAL 和 memtable 相对耗时，释放锁之后，其他需要用到 mutex_ 的地方，都可以拿到锁继续执行了，整体提高了系统的并发。

WAL（Write-Ahead Logging）是一种日志记录机制，它允许在数据写入磁盘之前，先记录日志。WAL 日志是追加写入，磁盘的顺序 IO 性能优于随机 IO 性能，因此追加写入一般效率比较高。写入 WAL 成功后，再把数据放到 memtable 中，memtable 是内存结构，写入效率也很高，等在内存积累到一定量级，再写入磁盘。如果系统崩溃重启，内存中 memtable 的数据可能会丢失，但是通过 WAL 日志，可以重放写入操作，从而恢复数据状态，确保数据的完整性。

这里具体写入，只是简单的调用 log::Writer 对象 log_ 的 AddRecord 方法来写入 WriteBatch 数据。log::Writer 会把这里的数据进行组织，然后在适当的时机写入磁盘，详细实现可以参考我前面的文章LevelDB 源码阅读：读写 WAL 日志保证持久性。

当然，如果写入的时候带了 sync=true，那么这里写入 WAL 成功后，会调用 logfile_->Sync() 方法，强制刷磁盘。这里稍微补充说明下，这里往文件里写内容是会通过系统调用 write 来完成，这个系统调用返回成功，并不保证数据一定被写入磁盘。文件系统一般会把数据先放到缓冲区，然后根据情况，选择合适的时机刷到磁盘中。要保证一定刷到磁盘中去，则需要另外的系统调用，不同平台有不同的接口，具体可以参考我之前的文章LevelDB 源码阅读：Posix 文件操作接口实现细节。

如果强制刷磁盘过程发生错误，那么这里会调用 RecordBackgroundError 方法，记录错误状态到 bg_error_ 中，这样后续所有的写入操作都会返回失败。

在写入 WAL 成功后，就可以写入 memtable 了。这里调用 WriteBatchInternal::InsertInto 方法，把 WriteBatch 数据插入到 memtable 中。关于 memtable 的实现，我后面文章会详细介绍。

更新批次写任务的状态

写入批次完成后，就需要更新批次写任务的状态，从 writers_ 队列的前端取出最先入队的 Writer 对象，然后开始遍历，直到批次中的最后一个写入任务。这里更新所有已经完成任务的状态，然后唤醒所有等待的写入任务。核心实现如下：

while (true) {
  Writer* ready = writers_.front();
  writers_.pop_front();
  if (ready != &w) {
    ready->status = status;
    ready->done = true;
    ready->cv.Signal();
  }
  if (ready == last_writer) break;
}

// Notify new head of write queue
if (!writers_.empty()) {
  writers_.front()->cv.Signal();
}

最后如果队列中还有写入任务，则需要唤醒队首的写入任务，继续处理。至此整个写入处理完毕，可以返回给调用方写入的结果了。

其他工程实现细节

整个写入过程到此分析完了，不过还有些工程实现细节，值得一起看看。

混合 sync 和非 sync 写入

如果有一批写入请求，其中既有 sync 又有非 sync 的写入，那么 LevelDB 内部会怎么处理呢？

前面分析可以看到每次取出队首的写入任务后，会尝试合并队列中后续的写入任务。因为每个写入任务可以强制 sync 刷磁盘，也可以不刷，合并的时候，怎么处理这种混合不同 sync 配置的写入任务呢？

这里配置 sync=true 的时候写入会强制刷磁盘，对于合并后的批次写入，取得是队首的 sync。核心代码如下：

Status DBImpl::Write(const WriteOptions& options, WriteBatch* updates) {
  //...
  if (status.ok() && updates != nullptr) {  // nullptr batch is for compactions
    // ...
    {
      mutex_.Unlock();
      status = log_->AddRecord(WriteBatchInternal::Contents(write_batch));
      bool sync_error = false;
      if (status.ok() && options.sync) {
        status = logfile_->Sync();
        if (!status.ok()) {
          sync_error = true;
        }
      }
      // ...
    }
  }
}

所以，如果队首是的任务是不需要刷磁盘，那么合并的时候，就不能合并 sync=true 的写入任务。核心实现代码如下：

for (; iter != writers_.end(); ++iter) {
  Writer* w = *iter;
  if (w->sync && !first->sync) {
    // Do not include a sync write into a batch handled by a non-sync write.
    break;
  }
  // ...
}

不过如果队首是 sync=true 的写入任务，那么合并的时候，就不需要考虑被合并的写入任务的 sync 设置。因为整个合并后的批次，都会被强制刷磁盘。这样就可以保证不会降低写入的持久化保证级别，但是可以适当提升写入的持久化保证级别。当然这里提升写入的持久化级别保证，其实也并不会导致整体耗时上涨，因为这里队首一定要刷磁盘，顺带着多一点不需要刷磁盘的写入任务，也不会导致耗时上涨。

优化大批量小 key 写入延迟

上面实现可以看到，如果大批量并发写入的时候，写入请求会先被放入队列中，然后串行化写入。如果写入的 key 都比较小，那么从队首取出一个写入任务，然后和当前队列中的其他写入合并为一个批次。合并的时候，需要设置一个 max_size 来限制合并的 key 数量，那么这里 max_size 要设置多少合理呢？

这里 LevelDB 给了一个经验值，默认是 1 << 20 个字节。但是考虑一个场景，如果写入的 key 都比较小，合并的时候，可能会合并很多 key，从而导致写入耗时变长。由于是小 key 的写入，写入耗时长的话，体验上来并不好。

所以这里加了个小优化，如果当前队首写入任务的整体 size 小于 128 << 10 个字节，那么这里 max_size 就会小很多。当然，这个值应该也只是经验值，我也没找到官方具体的说明。相关代码在
BuildBatchGroup 中：

// Allow the group to grow up to a maximum size, but if the
// original write is small, limit the growth so we do not slow
// down the small write too much.
size_t max_size = 1 << 20;
if (size <= (128 << 10)) {
  max_size = size + (128 << 10);
}

写入 WAL 成功，但是 memtable 失败

写入过程，会先写入 WAL 日志，写成功后，才写 memtable。但这两个写入并不是原子的，如果写 WAL 失败，不回写 memtable，并且会阻塞后续所有的写入，这样是合理的，也不会有问题。

但是如果写入 WAL 日志成功，但是写入 memtable 失败的话，返回给调用方的状态是写入失败，调用可能认为写失败。但是 WAL 成功写入，并且其他流程都是正常执行，也更新了全局的 sequence。万一这时候故障，从 WAL 恢复数据的时候，会把写 memtable 失败的也恢复，这样就导致调用方认为写失败的数据，其实成功写入了。

这里自己暂时还没彻底搞明白，可能是 LevelDB 的潜在 bug，也可能是自己对整体代码还没理解透。这里尝试用 GPT O1 和 Deepseek 的 R1 深度思考分析了下，都倾向这里是 bug。Deepseek 给的思考过程也比较有意思：

我需要确认在LevelDB的实际运行中，这种情况发生的概率有多大。MemTable的写入失败通常可能由什么原因引起？比如内存不足，或者其他不可恢复的错误？如果是暂时性的错误，LevelDB是否有重试机制？

另外，查看LevelDB的官方文档或相关讨论，是否有提到这种情况的处理方式。比如，是否在写入MemTable失败时，LevelDB会主动删除或无效化对应的WAL记录？

可能还需要考虑数据库恢复流程。当LevelDB重启时，会读取WAL并重新构建MemTable。如果某个WAL记录对应的写入在MemTable失败，但WAL存在，恢复时会再次尝试写入MemTable。如果此时条件允许（比如内存足够），写入可能成功，导致不一致。但如果原来的失败是持久性的（如数据结构错误），恢复时可能再次失败，导致数据库无法打开，从而避免不一致。

此外，用户的问题是否假设了某些特定场景？例如，MemTable写入失败但数据库没有崩溃，之后正常关闭，这时候WAL未被清除，恢复时重新应用。这种情况是否可能？

AI 现在的深度思考能力，逻辑推理的能力还是非常强的，考虑问题比较全面。这里也欢迎读者留言讨论这个问题哈。

总结

文章有点长，这里简单总结下吧。LevelDB 的写入操作设计充分考虑了高并发和性能优化，通过一系列精巧的机制实现了高效的键值对写入。下面是一些值得借鉴的设计：

批量合并写入: LevelDB 通过 Writer 队列将多个写入请求合并处理，避免了频繁的磁盘 IO。每个写入请求会被放入队列，队列头部的写入请求负责合并后续请求，形成一个大的 WriteBatch。这种设计显著提高了吞吐量，尤其适合高并发的小键值对写入场景。
WAL 日志处理崩溃恢复: WAL（Write-Ahead Log）：所有写入操作首先顺序写入 WAL 日志，确保数据持久性。写入 WAL 后才更新内存中的 MemTable，这种 “先日志后内存” 的设计是 LevelDB 崩溃恢复的基石。
内存双缓冲机制: 当 MemTable 写满后，会转换为 Immutable MemTable 并触发后台压缩，同时创建新的 MemTable 和 WAL 文件。这种双缓冲机制避免了写入阻塞，实现了平滑的内存-磁盘数据流转。
写入限流与自适应延迟: 通过 kL0_SlowdownWritesTrigger 和 kL0_StopWritesTrigger 阈值，在 Level 0 文件过多时主动引入写入延迟或暂停写入。这种 “软限流” 策略避免了系统过载后的雪崩效应。
动态批次合并: 根据当前队列头部请求的大小，动态调整合并批次的最大尺寸（如小请求合并 128KB，大请求合并 1MB），在吞吐量和延迟之间取得平衡。
条件变量唤醒机制: 通过 CondVar 实现高效的线程等待-通知，确保合并写入时不会长时间阻塞后续请求。
混合 Sync 处理: 支持同时处理需要强制刷盘（sync=true）和非强制刷盘的请求，优先保证队首请求的持久化级别，避免降低数据安全性。
错误隔离: WAL 写入失败会标记全局错误状态 bg_error_，直接拒绝掉所有后续写请求，防止数据不一致。

最后，欢迎大家留言讨论，一起学习 LevelDB 的实现细节。

Just For Fun修改