LevelDB 源码阅读：MemTable

Arena 那篇讲了 MemTable 的节点从哪来（内存层面）；SkipList 那篇讲了它们被编织成的索引结构。这一篇站在这套结构的最上层：MemTable（db/memtable.h、db/memtable.cc）——LSM 树的内存写缓冲，真正负责编码 K/V 对、排序它们、并把删除藏进墓碑的那个结构。

如果还没读过这两篇前置，它们是顺理成章的引子： → LevelDB 源码阅读：Arena 区域分配器 → LevelDB 源码阅读：SkipList 跳表索引

1. MemTable 是什么

MemTable 是 LSM 树的内存组件。写操作（Put/Delete）先落在这里；写满（write_buffer_size）后被冻结、刷成 SSTable。它内部其实就是三样东西：

• 一个 Arena：拥有全部节点内存（bump 分配、整体释放）；
• 一个 SkipList<const char*, KeyComparator>：按 internal key 索引 entry；
• 一个 KeyComparator：知道两个编码后的 entry 怎么比大小。

跳表节点的”键”说穿了就是一个指向 entry 缓冲区起始地址的 const char*。所以 MemTable 做的一切——编码、排序、查找——都可归结为 这段缓冲区怎么布局 以及 两个缓冲区怎么比。

2. 内存 entry 格式

从 db/memtable.cc:78-99，Add 把一条 K/V 打包进同一段连续的 arena 缓冲区：

// 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()]
...
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);
table_.Insert(buf);

一个 entry = key 和 value 打包在同一段连续内存里（全部由 Arena 托管）：

┌──────────┬──────────────────────────┬────────┬───────────┬──────────┐
│ key_size │ userkey + tag (8B)        │ tag    │ value_size│ value    │
│ varint32 │ char[internal_key_size-8] │ uint64 │ varint32  │ char[]   │
└──────────┴──────────────────────────┴────────┴───────────┴──────────┘
              └──── 合起来 = internal_key（排序键） ────┘

• internal_key = userkey + 8 字节 tag，其中 tag = (sequence << 8) | type。
• 注意 userkey 和 tag 是用分开的 memcpy / EncodeFixed64 写入的，但语义上连续，合起来就是排序用的 internal_key。
• table_.Insert(buf) 把这段内存的起始指针作为跳表节点的”键”插入；节点本身只是一个指向该 entry 的 const char*。
• 排序只看 internal_key，完全不碰 value（见第 4 节）。

3. 变长编码 varint —— 与 Protobuf 字节级兼容

EncodeVarint32（util/coding.cc:21-47）：

char* EncodeVarint32(char* dst, uint32_t v) {
  uint8_t* ptr = reinterpret_cast<uint8_t*>(dst);
  static const int B = 128;
  if (v < (1 << 7))      { *(ptr++) = v; }
  else if (v < (1 << 14)){ *(ptr++) = v | B; *(ptr++) = v >> 7; }
  ...
}

• 规则：每字节低 7 位存数据，最高位（0x80）作续位标志；多字节时按小端（低位字节在前）排列。
• 解码（GetVarint32PtrFallback，util/coding.cc:86-102）：循环读字节，若 byte & 128 说明还有后续，result |= (byte & 127) << shift，shift 每次 +7。
• VarintLength（:77-84）：预算某数值要几字节（while (v >= 128) { v >>= 7; len++; }）。

与 Protobuf 的关系

LevelDB 的 varint 字节级兼容 Protobuf 的 varint 编码。区别仅在 Protobuf 额外提供 zigzag（把有符号数映射到无符号），而 LevelDB 这里只编码无符号的长度 / 序号，不涉及有符号 zigzag。

4. KeyComparator —— 只比 internal_key，不碰 value

int MemTable::KeyComparator::operator()(const char* aptr,
                                        const char* bptr) const {
  Slice a = GetLengthPrefixedSlice(aptr);   // 跳过 key_size 取 internal_key
  Slice b = GetLengthPrefixedSlice(bptr);
  return comparator.Compare(a, b);
}

• 比较器收到的是 entry 起始指针 aptr。
• GetLengthPrefixedSlice（:14-19）先 GetVarint32Ptr 读出 key_size，再返回 [key_size 之后, 长度 = key_size] 的切片——即只切出 internal_key（userkey + tag），value 被直接跳过。
• 因此排序比较 只看 internal_key，value 的字节序与大小对排序毫无影响。

MemTable::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());          // 跳表定位第一个 ≥ memkey 的 entry
  if (iter.Valid()) {
    const char* entry = iter.key();
    const char* key_ptr = GetVarint32Ptr(entry, entry + 5, &key_length);
    if (user_comparator()->Compare(
            Slice(key_ptr, key_length - 8), key.user_key()) == 0) {
      const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
      switch (static_cast<ValueType>(tag & 0xff)) {
        case kTypeValue:    /* 取值赋值返回 */;
        case kTypeDeletion: *s = Status::NotFound(...); return true;
      }
    }
  }
  return false;
}

流程：编码 memkey → 跳表 Seek 到目标 → 校验 user_key 相等（tag & 0xff 是 type，低 8 位；tag >> 8 是 sequence）→ 按 type 分支：

• kTypeValue：用 GetLengthPrefixedSlice(key_ptr + key_length) 跳过 internal_key 取 value 返回。
• kTypeDeletion：返回 NotFound —— 即墓碑。

墓碑语义（纠正”会删除”的误解）

• MemTable 层从不物理删除任何 entry；删除只是向跳表插入一条 kTypeDeletion 墓碑记录。
• 真正清除发生在 compaction 合并 SSTable 时，墓碑与旧值相遇才被丢弃。
• 所以”Insert 进来的数据不会被删除，只是标记为无效”——准确说：本地不删，全局依赖后台 compaction 收敛。

5. Add 路径 —— 一次写如何变成一条 entry

Add（memtable.h:53-57，实现在 memtable.cc）是写路径的落点：

void Add(SequenceNumber s, ValueType type, const Slice& key,
         const Slice& value);

• 参数含义：s 序列号（MVCC 版本号）；type 为 kTypeValue 或 kTypeDeletion（删除时 value 通常为空）；key 是用户 key（internal key 在此现编）；value 值。
• 实现要点（结合第 2 节 entry 格式）：先把用户 key 现编成 internal key（userkey + 8B tag，tag = (s << 8) | type），再把 internal_key + value 打包进 Arena 一块 buffer，最后 table_.Insert(buf)。三个设计点：
  1. tag 打包 (s << 8) | type：sequence 占高 56 位、type 占低 8 位；跳表按 internal key 降序排列，同 user key 下序列号大者在前，所以 Get 时 Seek 第一个命中的就是最新版本——多版本读就是这么实现的。
  2. key + value 合进同一 arena buffer：跳表节点只存一个 const char*，打包后一次分配、缓存友好；比较器只取 internal key 前缀比较，需要时按偏移 key_ptr + key_length 取 value（见第 4 节）。
  3. 用 arena_.Allocate（非对齐版）而非 AllocateAligned：buffer 是纯字节数据，无需 8 字节对齐；节点对齐由 SkipList 内部用 AllocateAligned 单独管（呼应 Arena 笔记）。

6. 类设计：不可拷贝与引用计数（memtable.h）

前 3 节讲 memtable.cc 的 entry 编码与查找；本节讲 memtable.h 类层面的所有权设计。

6.1 禁止拷贝（memtable.h:26-27）

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

• 第 26 行是拷贝构造函数（形参 const MemTable&），第 27 行是拷贝赋值运算符（返回 MemTable&）。= delete 表示编译期禁用任何值拷贝。
• 为什么不可拷贝：
  • 成员 arena_ 是裸内存所有者（std::vector<char*> blocks_ 等），自身已 = delete 拷贝；
  • 成员 table_ 是 SkipList，节点全部分配在 arena_ 里且永不单独释放（节点一旦插入直到 MemTable 销毁），SkipList 自身也 = delete 拷贝。
  • 即使能拷贝，浅拷贝致命：SkipList 节点存的是 arena 内存指针，两份 MemTable 共享同一批节点，一方 Unref() 到 0 时 delete this 会把另一份的节点内存一起释放，造成悬垂指针；深拷贝代价极高且无必要。
• 正确语义是”共享所有权 + 引用计数”，而非值拷贝——对应 LSM 内存组件的”冻结/移交”模型：mem_ 写满后整体 swap 成 imm_，而不是复制。

6.2 引用计数 Ref / Unref（memtable.h:29-39）

void Ref() { ++refs_; }
void Unref() {
  --refs_;
  assert(refs_ >= 0);
  if (refs_ <= 0) delete this;
}

• 为什么需要：因为 MemTable 被多处共享同一实例（不能拷贝、又不能是单一所有者）。典型持有者：
  1. DBImpl::mem_ 活跃 memtable（持 1 ref，写路径写入）；
  2. DBImpl::imm_ 冻结待刷盘的 memtable（持 1 ref，后台刷盘后 Unref()）；
  3. 用户迭代器（NewIterator 时 Ref()，保证遍历期间 memtable 不被销毁，即使后台已 flush）；
  4. 后台压缩任务（操作 imm_ 时持 ref）。
  • 谁最后 Unref() 使 refs_ <= 0，谁负责 delete this。
• 与 shared_ptr 的关系：思想同源（共享所有权 + 计数归零即销毁），但实现上是手写侵入式引用计数，不是 std::shared_ptr。四个关键差异：
  1. 侵入式 vs 外部控制块：shared_ptr 计数在独立 control block，被管类型无感知；此处 refs_ 是对象内部成员（memtable.h:80），对象自带计数。
  2. 初始计数为 0（memtable.h:22-23 注释：“initial reference count is zero and the caller must call Ref() at least once”）：new 出来的对象”还没被任何人拥有”，必须由调用者立刻 Ref() 接管——比 shared_ptr 默认计数 1 更显式、更靠纪律。
  3. 非线程安全：refs_ 是普通 int，不是 std::atomic，所有 Ref/Unref 必须在 DBImpl::mutex_ 下执行（靠外部锁保证安全，省原子开销）。
  4. 纯手动、无智能指针包装：代码里没有 shared_ptr<MemTable>，调用者拿裸指针并手动配对 Ref/Unref；析构函数还被声明为 private（memtable.h:77），只有 Unref() 能删它——在类型系统上强制”只能经引用计数协议销毁”。
• 为什么不直接用 shared_ptr：避免 control block 额外堆分配、避免原子 RMW 开销、契合”移交”语义（mem_ → imm_ 的所有权整体转移）、早期（C++03 时代）历史风格与禁用异常/RTTI 的取向。
• 联系 DDIA：LSM 内存组件被多处共享/移交，引用计数即”多所有者、最后释放者销毁”模型在 C++ 的落地——和 shared_ptr 想解决的是同一个问题，只是 leveldb 选了更轻、更可控的侵入式手写版本。

7. 与 Arena & SkipList 的关系

• MemTable 组合了一个 Arena（arena_）和构建其上的 SkipList（table_）。第 2 节的 entry buffer 由 arena_.Allocate 分配；存其指针的跳表节点由 arena_.AllocateAligned 分配。
• 跳表”节点永不单独释放”的不变式与 Arena”整体释放”的模型，正是 MemTable 能 = delete 拷贝、转而依赖引用计数的原因——三块设计彼此自洽。
• Add 产出字节、KeyComparator 解读字节、SkipList 排序字节、Arena 拥有字节。MemTable 是把一次 Put/Delete 变成”有序、带版本、刷盘前永生”记录的胶水。

8. 联系 DDIA（数据密集型应用系统设计）

• 每条记录带序列号 = MVCC / 时间戳（支撑快照隔离与多版本读）；删除用 tombstone 而非真删，清理交给后台 compaction——呼应第 4 节墓碑语义与第 5 节 Add 设计。
• MemTable 是经典 LSM 内存组件：写先攒在这里再落 SSTable；第 6.1 节的”冻结并移交”模型正是 compaction 背后所有权整体转移的模式。

9. 下一步阅读

MemTable 是这套结构的最上层，下面两块你已经见过：

1. LevelDB 源码阅读：Arena 区域分配器 —— 拥有每一字节的 bump 分配器；
2. LevelDB 源码阅读：SkipList 跳表索引 —— 覆盖这些字节的无锁索引。

越过 MemTable 的后续自然是 LSM 主线：MemTable → WAL (log) → SSTable (table/block) → Compaction (version_set)。

紧接的一步——mem_ 写满后发生了什么、以及 SSTable 在磁盘上的布局——在这里：LevelDB 源码阅读：MemTable 刷盘与 SSTable 格式。

关键结论速记

主题	要点
entry 格式	varint(key_size)|userkey|tag|varint(val_size)|value，KV 同段
internal_key	userkey + 8B tag = (sequence<<8)|type，是排序键
varint	7 位有效 + 高位续位 + 小端；与 Protobuf varint 字节级兼容
KeyComparator	只切 internal_key 比较，不碰 value
Get / 墓碑	先 Seek 校验 userkey，按 type 取 value 或返回 NotFound
Add	seq+type+userkey+value；编 internal key 打包进 arena 插入跳表，删除 = tombstone
禁止拷贝	memtable.h:26-27；成员 arena/skiplist 不可拷贝，浅拷贝致命、深拷贝无必要
引用计数	memtable.h:29-39；Ref/Unref 侵入式手写，初始 0 需手动 Ref，普通 int 靠 mutex 保护，非 shared_ptr