Just For Fun的 RSS 预览

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 的实现细节。

LevelDB 源码阅读：如何优雅地合并写入和删除操作

2025-01-14 06:00:00

LevelDB 支持写入单个键值对和批量写入多个键值对，这两种操作的处理流程本质上是相同的，都会被封装进一个 WriteBatch 对象中，这样就可以提高写操作的效率。

在 LevelDB 中，WriteBatch 是通过一个简单的数据结构实现的，其中包含了一系列的写入操作。这些操作被序列化（转换为字节流）并存储在内部的一个字符串中。每个操作都包括操作类型（如插入或删除），键和值（对于插入操作）。

当 WriteBatch 被提交给数据库时，其内容被解析并应用到 WAL 日志和 memtable 中。不管 WriteBatch 中包含多少操作，它们都将作为一个整体进行处理和日志记录。

WriteBatch 的实现主要涉及到 4 个文件，接下来一起看看。

include/leveldb/write_batch.h：对外暴露的接口文件，定义了 WriteBatch 类的接口。
db/write_batch_internal.h：内部实现文件，定义了 WriteBatchInternal 类，提供了一些操作 WriteBatch 的方法。
db/write_batch.cc：WriteBatch 类的实现文件，实现了 WriteBatch 类。
db/write_batch_test.cc：WriteBatch 类的测试文件，用于测试 WriteBatch 的功能。

WriteBatch 接口设计

我们先来看 write_batch.h 文件，这里定义了 WriteBatch 类对外暴露的一些接口。 LevelDB 代码中的注释十分清晰，不过这里先省略注释：

class LEVELDB_EXPORT WriteBatch {
 public:
  class LEVELDB_EXPORT Handler {
   public:
    virtual ~Handler();
    virtual void Put(const Slice& key, const Slice& value) = 0;
    virtual void Delete(const Slice& key) = 0;
  };

  WriteBatch();

  // Intentionally copyable.
  WriteBatch(const WriteBatch&) = default;
  WriteBatch& operator=(const WriteBatch&) = default;

  ~WriteBatch();
  void Put(const Slice& key, const Slice& value);
  void Delete(const Slice& key);
  void Clear();
  size_t ApproximateSize() const;
  void Append(const WriteBatch& source);
  Status Iterate(Handler* handler) const;

 private:
  friend class WriteBatchInternal;

  std::string rep_;  // See comment in write_batch.cc for the format of rep_
};

其中 WriteBatch::Handler 是一个抽象基类，定义了处理键值对操作的接口，只包括 Put 和 Delete 方法。这样的设计允许 WriteBatch 类实现与具体存储操作解耦，使得 WriteBatch 不必直接知道如何将操作应用到底层存储（如 MemTable）。

通过继承 Handler 类，可以创建多种处理器，它们可以以不同的方式实现这些方法。比如：

MemTableInserter：定义在 db/write_batch.cc 中，将键值操作存储到 MemTable 中。
WriteBatchItemPrinter：定义在 db/dumpfile.cc 中，将键值操作打印到文件中，可以用来测试。

另外还有一个 friend class WriteBatchInternal 作为 WriteBatch 的友元类，能够访问其私有和受保护成员。WriteBatchInternal 主要用来封装一些内部操作，这些方法不需要对外暴露，只在内部用到。通过将内部操作方法隐藏在 WriteBatchInternal 中，保持了对象的接口清晰，可以自由地修改内部实现而不影响到使用这些对象的代码。

WriteBatch 使用方法

在应用层，我们可以通过 WriteBatch 来批量写入多个键值对，然后通过 DB::Write 方法将 WriteBatch 写入到数据库中。

这里 WriteBatch 支持 Put 和 Delete 操作，可以合并多个 WriteBatch。如下使用示例：

WriteBatch batch;
batch.Put("key1", "value1");
batch.Put("key2", "value2");
batch.Delete("key3");

// 合并另一个批次
WriteBatch another_batch;
another_batch.Put("key4", "value4");
batch.Append(another_batch);

// 写入数据库
db->Write(writeOptions, &batch);

WriteBatch 实现细节

那么 WriteBatch 是怎么实现的呢？关键在 db/write_batch.cc，该类中有一个 private 成员 std::string rep_ 来存储序列化后的键值操作。我们先来看看这里的存储数据协议：

+---------------+---------------+----------------------------------------+
|   Sequence    |     Count     |                Data                    |
|  (8 bytes)    |   (4 bytes)   |                                        |
+---------------+---------------+----------------------------------------+
                                   |                 |                   |
                                   v                 v                   v
                               +-------+         +-------+          +-------+
                               |Record1|         |Record2|   ...    |RecordN|
                               +-------+         +-------+          +-------+
                                  |                 |
                                  v                 v
                        +-----------------+ +-----------------+
                        | kTypeValue      | | kTypeDeletion   |
                        | Varstring Key   | | Varstring Key   |
                        | Varstring Value | |                 |
                        +-----------------+ +-----------------+
                        
Varstring (可变长度字符串):
+-------------+-----------------------+
| Length (varint32) | Data (uint8[])  |
+-------------+-----------------------+

该字符串前 12 个字节是头部元数据部分，包括 8 个字节的序列号和 4 个字节的 count 数。接下来是一个或多个操作记录，每个记录包含一个操作类型和键值对。操作类型是一个字节，可以是 Put 或者 Delete 操作。键和值都是可变长度的字符串，格式为 varstring。

LevelDB 的序列号机制

rep_ 头部 8 个字节代表64位的数字 sequence（序列号），WriteBatchInternal 友元类提供了两个方法来获取和设置 sequence number，内部是用 EncodeFixed64 和 DecodeFixed64 方法来编解码 64 位的序列号。

SequenceNumber WriteBatchInternal::Sequence(const WriteBatch* b) {
  return SequenceNumber(DecodeFixed64(b->rep_.data()));
}

void WriteBatchInternal::SetSequence(WriteBatch* b, SequenceNumber seq) {
  EncodeFixed64(&b->rep_[0], seq);
}

序列号是 LevelDB 中的全局递增标识符，用于实现版本控制和操作排序。每个 WriteBatch 在执行时会获得一段连续的序列号，批次内的每个操作（Put/Delete）都会分配到其中的一个序列号。序列号在 LevelDB 中有三个核心作用：

版本控制：LevelDB 中的每个 key 可以有多个版本，每个版本都对应一个序列号。在读取时，通过比较序列号来确定应该返回哪个版本的值。较大的序列号表示更新的版本。
多版本并发控制（MVCC）：写操作获取新的序列号，创建 key 的新版本。读操作可以指定序列号，访问该序列号时间点的数据快照。这种机制使得读写操作可以并发执行，无需互相阻塞。
故障恢复：WAL（预写日志）中记录了操作的序列号。系统重启时，通过序列号可以准确重建崩溃时的数据状态，避免重复应用已持久化的操作。

这种设计让 LevelDB 既保证了数据一致性，又实现了高效的并发控制。

设置序列号的逻辑在 DBImpl::Write 方法中，首先获取当前最大序列号，然后为 WriteBatch 分配一个新的序列号。

Status DBImpl::Write(const WriteOptions& options, WriteBatch* updates) {
  // ...
  uint64_t last_sequence = versions_->LastSequence();
  // ...
  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);
    // ...
  }
}

如果 WriteBatch 包含多个操作，那么这些操作会连续地分配序列号。在写入 WAL 日志时，会将 WriteBatch 的序列号写入到日志中，这样在恢复时可以根据序列号来恢复操作的顺序。写入 memtable 之后，会更新当前最大序列号，以便下次分配。

count 记录操作数

头部还有 4 个字节的 count，用于记录 WriteBatch 中包含的操作数。这里每次 put 或者 delete 操作都会增加 count 的值。如下示例：

WriteBatch batch;
batch.Put("key1", "value1");  // count = 1
batch.Put("key2", "value2");  // count = 2
batch.Delete("key3");         // count = 3
int num_ops = WriteBatchInternal::Count(&batch);  // = 3

在合并两个 WriteBatch 的时候，也会累计两部分的 count 的值，如下 WriteBatchInternal::Append 方法：

void WriteBatchInternal::Append(WriteBatch* dst, const WriteBatch* src) {
  SetCount(dst, Count(dst) + Count(src));
  assert(src->rep_.size() >= kHeader);
  dst->rep_.append(src->rep_.data() + kHeader, src->rep_.size() - kHeader);
}

使用 count 的地方主要有两个，一个是在迭代这里每个记录的时候，会用 count 来做完整性检查，确保没有遗漏操作。

Status WriteBatch::Iterate(Handler* handler) const {
  Slice input(rep_);

  ...
  if (found != WriteBatchInternal::Count(this)) {
    return Status::Corruption("WriteBatch has wrong count");
  } else {
    return Status::OK();
  }
}

另一个是在 db 写入的时候，根据 count 可以预先知道需要分配多少序列号，保证序列号连续性。如下 DBImpl::Write：

1 2	WriteBatchInternal::SetSequence(write_batch, last_sequence + 1); last_sequence += WriteBatchInternal::Count(write_batch);

支持的各种操作

在头部的 sequence 和 count 之后，rep_ 紧跟着的是一系列的记录，每个记录包含一个操作类型和键值。这里记录可以通过 Put 和 Delete 方法来添加，其中 Put 方法的实现如下：

void WriteBatch::Put(const Slice& key, const Slice& value) {
  WriteBatchInternal::SetCount(this, WriteBatchInternal::Count(this) + 1);
  rep_.push_back(static_cast<char>(kTypeValue));
  PutLengthPrefixedSlice(&rep_, key);
  PutLengthPrefixedSlice(&rep_, value);
}

这里更新了 count，然后添加了 kTypeValue 操作类型，接着是添加 key 和 value。Delete 操作类似，count 计数也是要加 1，然后操作类型是 kTypeDeletion，最后只用添加 key 即可。

void WriteBatch::Delete(const Slice& key) {
  WriteBatchInternal::SetCount(this, WriteBatchInternal::Count(this) + 1);
  rep_.push_back(static_cast<char>(kTypeDeletion));
  PutLengthPrefixedSlice(&rep_, key);
}

上面是往 rep_ 中添加记录，那么如何从 rep_ 中解析出这些记录呢？这里 WriteBatch 类中提供了一个 Iterate 方法，该方法遍历 rep_ 中的每条记录，然后通过传入的 Handler 接口来灵活处理这些记录。

此外该方法的实现中还有数据格式验证，会检查头部大小、操作类型、操作数量是否匹配。可以返回 Corruption 错误，表示数据格式不正确等。Iterate 核心代码如下：

Status WriteBatch::Iterate(Handler* handler) const {
  Slice input(rep_);
  if (input.size() < kHeader) {
    return Status::Corruption("malformed WriteBatch (too small)");
  }

  input.remove_prefix(kHeader);
  Slice key, value;
  int found = 0;
  while (!input.empty()) {
    found++;
    char tag = input[0];
    input.remove_prefix(1);
    switch (tag) {
      case kTypeValue:
        if (GetLengthPrefixedSlice(&input, &key) &&
            GetLengthPrefixedSlice(&input, &value)) {
          handler->Put(key, value);
        } else {
          return Status::Corruption("bad WriteBatch Put");
        }
        break;
      case kTypeDeletion:
        if (GetLengthPrefixedSlice(&input, &key)) {
          handler->Delete(key);
        } else {
          return Status::Corruption("bad WriteBatch Delete");
        }
        break;
      default:
        return Status::Corruption("unknown WriteBatch tag");
    }
  }
  // ...
}

前面提过 Handler 是 WriteBatch 的抽象基类，可以传入不同的实现。在 LevelDB 写数据的时候，这里传入的是 MemTableInserter 类，该类将操作数据存储到 MemTable 中。具体可以调用这里的实现：

Status WriteBatchInternal::InsertInto(const WriteBatch* b, MemTable* memtable) {
  MemTableInserter inserter;
  inserter.sequence_ = WriteBatchInternal::Sequence(b);
  inserter.mem_ = memtable;
  return b->Iterate(&inserter);
}

整体上看 WriteBatch 负责存储键值操作的数据，进行编码解码等，而 Handler 负责具体处理里面的每条数据。这样 WriteBatch 的操作就可以被灵活地应用到不同场景中，方便扩展。

测试用例分析

最后再来看看 write_batch_test.cc，这里提供了一些测试用例，用于测试 WriteBatch 的功能。

首先定义了一个 PrintContents 函数，用来输出 WriteBatch 中的所有操作记录。这里用 MemTableInserter 将 WriteBatch 中的操作记录存储到 MemTable 中，然后通过 MemTable 的迭代器遍历所有记录，并保存到字符串中。

这里测试用例覆盖了下面这些情况：

Empty：测试空的 WriteBatch 是否正常；
Multiple：测试多个 Put 和 Delete 操作，验证总的 count 数目和每个操作的序列号是否正确；
Corruption：先写进去数据，然后故意截断部分记录，测试能读取尽量多的正常数据；
Append：测试合并两个 WriteBatch，验证合并后序列号的正确性，以及合并空 WriteBatch；
ApproximateSize：测试 ApproximateSize 方法，计算 WriteBatch 的近似大小；

这里通过测试用例，基本就能知道怎么使用 WriteBatch 了。比较有意思的是，前面在看 Append 代码的时候，没太留意到合并后这里序列号是用谁的。这里结合测试用例，才发现取的目标 WriteBatch 的序列号。

TEST(WriteBatchTest, Append) {
  WriteBatch b1, b2;
  WriteBatchInternal::SetSequence(&b1, 200);
  WriteBatchInternal::SetSequence(&b2, 300);
  b1.Append(b2);
  ASSERT_EQ("", PrintContents(&b1));
  b2.Put("a", "va");
  b1.Append(b2);
  ASSERT_EQ("Put(a, va)@200", PrintContents(&b1));
  // ...
}

总结

通过深入分析 LevelDB 的 WriteBatch 实现，我们可以清晰地看到其设计精妙之处。WriteBatch 通过将多个写入和删除操作封装在一起，不仅提高了写操作的效率，还简化了并发控制和故障恢复的实现。有几个亮点值得借鉴：

批量操作：WriteBatch 允许将多个 Put 和 Delete 操作合并为一个批次，减少了频繁的 I/O 操作，提升了写入性能。
序列号机制：通过全局递增的序列号，LevelDB 实现了多版本并发控制（MVCC），确保了读写操作的一致性。
Handler 抽象：通过 Handler 接口，WriteBatch 将操作的具体实现与存储逻辑解耦，使得代码更加灵活和可扩展。
数据格式验证：在解析 WriteBatch 时，LevelDB 会进行严格的数据格式验证，确保数据的完整性和正确性。

当然本篇只是分析 WriteBatch 的实现，并没有串起 LevelDB 的整个写入流程，后续文章我们会继续分析，写入一个 key 的完整流程。

Just For Fun修改