【LSM-Tree】WAL + MemTable：崩溃了也不丢数据

上一篇建立了 LSM-Tree 的全景地图：数据从 WAL 流入内存中的 MemTable，攒够一批后顺序刷盘成为 SSTable。整条写路径上没有随机 I/O。

但这里有一个绕不过去的矛盾：内存很快，但断电就没了。

如果 MemTable 里积攒了 4MB 数据、还没来得及 flush 到磁盘，进程崩溃了怎么办？用户已经收到了”写入成功”的返回——数据丢了就违背了持久性承诺。

解决方案在上一篇已经提到：WAL（Write-Ahead Log）。每次写入，先顺序追加到磁盘上的日志文件，再写入 MemTable。崩溃后重启，从 WAL 逐条重放即可恢复。

本文是系列第 2 篇。目标：从零实现 WAL 和 MemTable，给出可编译的 C 代码，并严格论证崩溃恢复的正确性。

本文是「从零写一个 LSM-Tree 存储引擎」系列的第 2 篇（共 5 篇）。→ 系列目录

篇目核心内容

第 1 篇 · 全景 B-Tree vs LSM-Tree、三种放大的数学推导

第 2 篇 · WAL + MemTable 跳表实现、WAL 32KB 分片、崩溃恢复证明

第 3 篇 · SSTable + Bloom Filter 前缀压缩、双重哈希 Bloom、Builder/Reader

第 4 篇 · Compaction 多路归并、Version/MANIFEST、策略对比

第 5 篇 · 完整引擎 + Rust 重写 DB API + 并发 + Rust 重写 + benchmark

篇目	核心内容
第 1 篇 · 全景	B-Tree vs LSM-Tree、三种放大的数学推导
第 2 篇 · WAL + MemTable	跳表实现、WAL 32KB 分片、崩溃恢复证明
第 3 篇 · SSTable + Bloom Filter	前缀压缩、双重哈希 Bloom、Builder/Reader
第 4 篇 · Compaction	多路归并、Version/MANIFEST、策略对比
第 5 篇 · 完整引擎 + Rust 重写	DB API + 并发 + Rust 重写 + benchmark

WAL：先记账再干活

为什么单独一节讲 WAL

WAL 的概念很简单——先写日志再写内存。但魔鬼藏在格式设计里：record 怎么编码？大 record 怎么拆分？磁盘写到一半断电了怎么检测？这些问题的答案直接决定了恢复的速度和正确性。

LevelDB 的 WAL 设计——来自 log_format.h——简洁而精巧，值得逐字节拆解。

Record 格式

每条写入对应 WAL 中的一条 record。格式如下：

+----------+---------+------+----------------+
| CRC32(4) | Len(2)  | Type | Data(Len bytes)|
+----------+---------+------+----------------+

字段详解：

CRC32（4 字节）：校验范围覆盖 Type + Data（不含 CRC 和 Length 自身）。恢复时用于检测损坏的 record。
Length（2 字节）：Data 部分的长度。最大 65535 字节，但实际受 Block 大小限制（后面会讲）。
Type（1 字节）：这条 record 的分片类型。
Data（变长）：用户写入的 KV 数据。

Header 固定 7 字节。这个数字很重要——后面的 Block 对齐规则会用到。

Type 有四种取值：

Type	值	含义
FULL	1	完整 record，没有分片
FIRST	2	分片 record 的第一段
MIDDLE	3	分片 record 的中间段（可能有多个）
LAST	4	分片 record 的最后一段

绝大多数 record 是 FULL 类型。只有当单条数据太大、放不进当前 Block 的剩余空间时，才需要分片。

用 C 定义：

enum RecordType {
  kZeroType  = 0,  // 预留，用于填充
  kFullType  = 1,
  kFirstType = 2,
  kMiddleType = 3,
  kLastType  = 4,
};

// Header: CRC32(4) + Length(2) + Type(1) = 7 bytes
static const int kHeaderSize = 7;

32KB Block 对齐

WAL 文件在逻辑上被划分为一系列固定大小的 Block，每个 Block 32768 字节（32KB）。Record 不能跨越 Block 的逻辑边界——如果放不下，就拆分成多个 fragment。

为什么要 32KB 对齐？两个原因：

恢复效率：崩溃后按 Block 粒度读取。如果在某个 Block 中发现 CRC 校验失败，跳过整个 Block 即可定位损坏边界，后续 Block 中的完好 record 不受影响。
I/O 对齐：32KB 是磁盘 I/O 的合理粒度，不至于太小（频繁系统调用）也不至于太大（浪费空间）。

一个关键规则：如果当前 Block 的剩余空间不足 7 字节（即不够放一个 Header），则填零并跳到下一个 Block。 读取端看到全零的 Header 时，知道这是 padding，直接跳过。

static const int kBlockSize = 32768;  // 32KB

// Block 尾部剩余空间不足 kHeaderSize 时，填零
if (block_remaining < kHeaderSize) {
  if (block_remaining > 0) {
  // 写入全零 padding
  memset(buf, 0, block_remaining);
  write(fd, buf, block_remaining);
  }
  block_remaining = kBlockSize;
}

分片策略

当一条 record 的 Data 超过当前 Block 的可用空间（block_remaining - kHeaderSize）时，需要拆分：

在当前 Block 写入 FIRST fragment，填满剩余空间。
如果数据还没写完，在后续 Block 写入 MIDDLE fragment（可能多个）。
最后一段写入 LAST fragment。

核心代码：

typedef struct {
  int fd;  // WAL 文件描述符
  int block_offset;  // 当前 Block 内已写入的字节数
  uint32_t crc;  // CRC32 临时变量
} WALWriter;

int wal_writer_append(WALWriter *w, const char *data, size_t len) {
  const char *ptr = data;
  size_t left = len;
  bool begin = true;

  while (left > 0 || begin) {
  int block_remaining = kBlockSize - w->block_offset;

  // Block 尾部空间不够放 Header，填零跳过
  if (block_remaining < kHeaderSize) {
  if (block_remaining > 0) {
  static const char zeros[kHeaderSize] = {0};
  write(w->fd, zeros, block_remaining);
  }
  w->block_offset = 0;
  block_remaining = kBlockSize;
  }

  size_t avail = block_remaining - kHeaderSize;
  size_t fragment_len = (left < avail) ? left : avail;

  enum RecordType type;
  bool end = (fragment_len == left);
  if (begin && end)  type = kFullType;
  else if (begin)  type = kFirstType;
  else if (end)  type = kLastType;
  else  type = kMiddleType;

  // 写入一个 fragment: [CRC32 | Length | Type | Data]
  emit_record(w, type, ptr, fragment_len);

  ptr  += fragment_len;
  left -= fragment_len;
  begin = false;
  }
  return 0;
}

emit_record 负责计算 CRC32、组装 Header、调用 write()：

static void emit_record(WALWriter *w, enum RecordType type,
  const char *data, size_t len) {
  char header[kHeaderSize];
  // CRC32 覆盖 Type + Data
  uint32_t crc = crc32(0, &type, 1);
  crc = crc32(crc, (const uint8_t *)data, len);

  // 小端写入
  header[0] = (crc >>  0) & 0xff;
  header[1] = (crc >>  8) & 0xff;
  header[2] = (crc >> 16) & 0xff;
  header[3] = (crc >> 24) & 0xff;
  header[4] = (len >> 0) & 0xff;
  header[5] = (len >> 8) & 0xff;
  header[6] = (uint8_t)type;

  write(w->fd, header, kHeaderSize);
  write(w->fd, data, len);

  w->block_offset += kHeaderSize + len;
}

fsync 策略

WAL 写入 write() 后，数据可能还在操作系统的 page cache 里。如果这时系统崩溃（不是进程崩溃），数据仍然会丢失。要保证落盘，需要 fsync()。

三种策略，对应不同的延迟/持久性权衡：

策略	做法	丢失窗口	延迟
不 sync	只调 `write()`	系统崩溃丢最后几次写入	最低
每次 sync	每次 `write()` 后调 `fsync()`	零（已返回 OK 的不丢）	最高
批量 sync	攒若干次 `write()` 后调一次 `fsync()`	最后一批可能丢	中等

LevelDB 默认不 sync——靠 WriteOptions::sync = true 让用户按需开启。这在《LevelDB 日常使用》中讲过：

leveldb 允许同步写入，具体实现是在调用 fsync(), fdatasync(), msync() 之后返回。

对于进程崩溃（SIGSEGV、kill -9），数据只要进了内核的 page cache，内核会负责在之后将脏页写回磁盘——所以即使不调 fsync()，进程崩溃通常不会导致数据丢失。真正危险的是操作系统本身崩溃或掉电：此时 page cache 中尚未回写的脏页会一起丢失。

跳表：200 行实现一个有序内存表

MemTable 的底层数据结构是跳表（Skip List）。上一篇提过三个选择它的理由：并发友好、实现简单、缓存局部性好。现在来把它实现出来。

跳表的直觉

想象你有一个有序链表，查找一个 key 需要从头到尾扫描——O(n)。跳表的思路：给链表加多层”快速通道”。

L0：完整的有序链表，包含所有节点。
L1：大约每 2 个节点抽一个建索引。
L2：大约每 4 个节点抽一个。
L3：……以此类推。

查找时：从最高层开始向右走，遇到比目标大的节点就”下降”一层，继续向右。每一层跳过大约一半的节点，总的比较次数就是 O(log n)。

这比红黑树简洁得多。红黑树的插入和删除需要旋转操作来保持平衡，旋转牵涉多个节点的指针修改，加锁复杂。跳表的插入只需修改局部指针——天然适合细粒度锁甚至无锁实现。

核心数据结构

#define SKIPLIST_MAXLEVEL 12
#define SKIPLIST_P  4  // p = 1/4

typedef struct SkipListNode {
  char  *key;
  size_t key_len;
  char  *value;
  size_t value_len;
  int  level;  // 该节点的层数
  struct SkipListNode *forward[];  // 柔性数组，forward[i] 指向第 i 层的下一个节点
} SkipListNode;

typedef struct {
  SkipListNode *header;  // 哨兵头节点
  int  level;  // 当前最高层数
  int  count;  // 节点总数
  Arena  *arena;  // 内存分配器
} SkipList;

节点的 forward 是柔性数组（flexible array member），长度等于该节点的层数。L0 的 forward[0] 是基础链表指针，forward[1] 是上一层的跳跃指针，以此类推。

随机层数

插入新节点时，用随机函数决定它能”升”到第几层：

static int skiplist_random_level(void) {
  int level = 1;
  // 每次有 1/SKIPLIST_P 的概率升一层
  while (level < SKIPLIST_MAXLEVEL && (random() % SKIPLIST_P) == 0) {
  level++;
  }
  return level;
}

p = 1/4 是 LevelDB 的选择。期望层高：

\[ E[h] = \log_{1/p} n = \log_4 n \]

100 万个 key 约 10 层，1 亿个 key 约 13 层。内存开销：平均每个节点有 \(\frac{1}{1 - 1/p} = \frac{4}{3} \approx 1.33\) 个指针——比红黑树的 2 个指针（左、右子节点）还少。

插入

插入算法的核心：先从顶层向下查找，记录每一层的前驱节点（update 数组），然后随机生成层数，逐层插入指针。

注意：下面的插入和查找函数直接使用 memcmp 做字节序比较，这只适合定长、字典序即正确排序的 key。真正集成到 MemTable 时，需要替换成 internal_key_compare（后面 §3 会给出），才能正确处理变长 user_key + sequence 降序的排列要求。

int skiplist_insert(SkipList *sl, const char *key, size_t key_len,
  const char *val, size_t val_len) {
  SkipListNode *update[SKIPLIST_MAXLEVEL];
  SkipListNode *x = sl->header;

  // 从最高层向下，找到每一层中 < key 的最后一个节点
  for (int i = sl->level - 1; i >= 0; i--) {
  while (x->forward[i] != NULL &&
  memcmp(x->forward[i]->key, key, key_len) < 0) {
  x = x->forward[i];
  }
  update[i] = x;
  }

  // 随机决定新节点的层数
  int new_level = skiplist_random_level();
  if (new_level > sl->level) {
  for (int i = sl->level; i < new_level; i++) {
  update[i] = sl->header;
  }
  sl->level = new_level;
  }

  // 创建新节点（从 Arena 分配内存）
  SkipListNode *node = arena_alloc_node(sl->arena, new_level,
  key, key_len, val, val_len);

  // 逐层插入：新节点插到 update[i] 和 update[i]->forward[i] 之间
  for (int i = 0; i < new_level; i++) {
  node->forward[i] = update[i]->forward[i];
  update[i]->forward[i] = node;
  }

  sl->count++;
  return 0;
}

时间复杂度 O(log n)：从顶层到底层共 log n 层，每层平均比较常数次。

查找

查找比插入更简单——同样的从顶到底搜索，找到就返回：

const char *skiplist_find(SkipList *sl, const char *key, size_t key_len,
  size_t *val_len) {
  SkipListNode *x = sl->header;

  for (int i = sl->level - 1; i >= 0; i--) {
  while (x->forward[i] != NULL &&
  memcmp(x->forward[i]->key, key, key_len) < 0) {
  x = x->forward[i];
  }
  }

  x = x->forward[0];  // 移到候选节点
  if (x != NULL && x->key_len == key_len &&
  memcmp(x->key, key, key_len) == 0) {
  *val_len = x->value_len;
  return x->value;
  }
  return NULL;  // Not found
}

顺序迭代也很自然：从 header->forward[0] 开始，沿着 L0 链表遍历到末尾。数据天然有序——这是 flush 到 SSTable 时的关键。

// 顺序遍历所有 KV 对——用于 flush 到 SSTable
SkipListNode *node = sl->header->forward[0];
while (node != NULL) {
  write_to_sstable(node->key, node->key_len,
  node->value, node->value_len);
  node = node->forward[0];
}

Arena 分配器

跳表中的每个节点都需要分配内存。如果每个节点单独 malloc()，会产生两个问题：

内存碎片：大量小对象散落在堆的各个位置，遍历时 cache miss 率高。
释放复杂：MemTable 销毁时需要逐个 free() 每个节点。

LevelDB 的方案：Arena 分配器。预分配一大块内存（4KB 一个 block），节点从 block 中顺序切出。好处：

节点在内存中物理连续，遍历时缓存命中率高。
释放整个 MemTable 时，只需遍历 Arena 的 block 链表逐个释放——无需逐节点 free()，代码路径极短。
Arena 的 bytes_used 字段就是 MemTable 的内存用量——达到 4MB 阈值时触发 Immutable 转换。

typedef struct ArenaBlock {
  struct ArenaBlock *next;
  size_t size;
  size_t used;
  char  data[];
} ArenaBlock;

typedef struct {
  ArenaBlock *current;  // 当前 block
  ArenaBlock *block_list; // 所有 block 的链表
  size_t  bytes_used; // 总内存用量
} Arena;

static const size_t kArenaBlockSize = 4096;

void *arena_alloc(Arena *a, size_t bytes) {
  if (a->current == NULL || a->current->used + bytes > a->current->size) {
  // 当前 block 放不下，分配新 block
  size_t block_size = (bytes > kArenaBlockSize) ? bytes : kArenaBlockSize;
  ArenaBlock *b = malloc(sizeof(ArenaBlock) + block_size);
  b->size = block_size;
  b->used = 0;
  b->next = a->block_list;
  a->block_list = b;
  a->current = b;
  }
  void *ptr = a->current->data + a->current->used;
  a->current->used += bytes;
  a->bytes_used += bytes;
  return ptr;
}

void arena_destroy(Arena *a) {
  ArenaBlock *b = a->block_list;
  while (b != NULL) {
  ArenaBlock *next = b->next;
  free(b);
  b = next;
  }
}

MemTable：把跳表包装成 KV 接口

跳表是纯粹的数据结构，MemTable 在它之上加了三件事：InternalKey 编码、版本排序、Immutable 转换。

InternalKey 编码

用户看到的是 Put("user:1001", value)。但 LSM-Tree 内部存储的 key 并不是 "user:1001"——它是一个 InternalKey：

+------------------+------------+--------+
|  user_key (变长)  | seq (7 B)  | type  |
+------------------+------------+--------+
  ← 8 字节，最后 1 字节是 type →

user_key：用户传入的原始 key。
sequence（7 字节）：全局递增的序列号。每次写操作 +1。
type（1 字节）：kTypePut = 1 或 kTypeDeletion = 0。

为什么需要 sequence？因为 LSM-Tree 不原地修改数据。同一个 user_key 可能被写入多次，每次写入都是一条新记录。sequence 保证了同一个 user_key 的不同版本按时间排序——sequence 越大越新。

InternalKey 的比较规则：

先按 user_key 升序。
user_key 相同时，按 sequence 降序（新版本排在前面）。

这样，跳表中查找 user_key 时，第一个匹配的就是最新版本。

// 将 sequence 和 type 打包成 8 字节
static uint64_t pack_seq_type(uint64_t seq, uint8_t type) {
  return (seq << 8) | type;
}

// InternalKey 比较器
int internal_key_compare(const char *a, size_t a_len,
  const char *b, size_t b_len) {
  // 提取 user_key（去掉最后 8 字节）
  size_t ua_len = a_len - 8;
  size_t ub_len = b_len - 8;

  int r = memcmp(a, b, (ua_len < ub_len) ? ua_len : ub_len);
  if (r == 0) {
  if (ua_len < ub_len) r = -1;
  else if (ua_len > ub_len) r = +1;
  }
  if (r != 0) return r;

  // user_key 相同，按 tag 降序（大的排前面）
  // tag = (sequence << 8) | type，sequence 占高 7 字节
  // 因此直接比较 8 字节整数：sequence 大的 tag 值也大，自然排在前面
  uint64_t sa = decode_fixed64(a + ua_len);
  uint64_t sb = decode_fixed64(b + ub_len);
  if (sa > sb) return -1;
  if (sa < sb) return +1;
  return 0;
}

MemTable 接口

有了 InternalKey 编码和跳表，MemTable 的接口就很直接了：

typedef struct {
  SkipList *table;
  Arena  *arena;
  uint64_t  seq;  // 当前序列号
} MemTable;

// 写入：构造 InternalKey，插入跳表
void memtable_put(MemTable *m, uint8_t type,
  const char *key, size_t key_len,
  const char *val, size_t val_len) {
  // 构造 InternalKey = user_key + pack(seq, type)
  size_t ik_len = key_len + 8;
  char *ik = arena_alloc(m->arena, ik_len);
  memcpy(ik, key, key_len);
  encode_fixed64(ik + key_len, pack_seq_type(m->seq++, type));

  skiplist_insert(m->table, ik, ik_len, val, val_len);
}

// 读取：查找最新版本，处理 tombstone
int memtable_get(MemTable *m, const char *key, size_t key_len,
  char **val, size_t *val_len) {
  // 用最大 sequence 构造查找 key，确保找到最新版本
  char lookup_key[key_len + 8];
  memcpy(lookup_key, key, key_len);
  encode_fixed64(lookup_key + key_len,
  pack_seq_type(UINT64_MAX, kTypePut));

  // 在跳表中找到 >= lookup_key 的第一个节点
  SkipListNode *node = skiplist_seek_ge(m->table,
  lookup_key, key_len + 8);
  if (node == NULL) return -1;  // Not found

  // 检查 user_key 是否匹配
  if (node->key_len < 8) return -1;
  size_t uk_len = node->key_len - 8;
  if (uk_len != key_len || memcmp(node->key, key, key_len) != 0)
  return -1;

  // 检查是否是 tombstone
  uint64_t tag = decode_fixed64(node->key + uk_len);
  uint8_t type = tag & 0xff;
  if (type == kTypeDeletion) return 1;  // Deleted

  *val = node->value;
  *val_len = node->value_len;
  return 0;  // Found
}

Delete 操作不需要单独的函数——它就是一次 memtable_put(m, kTypeDeletion, key, key_len, NULL, 0)。物理删除直到 Compaction 时才发生。

Immutable 转换与双缓冲

当 MemTable 的 Arena 内存用量达到阈值（LevelDB 默认 4MB），它被标记为 Immutable（只读），同时创建一个新的空 MemTable 接收后续写入。

这是一个双缓冲设计：

Active MemTable：接收所有 Put / Delete 操作。
Immutable MemTable：只读，后台线程将其顺序遍历后 flush 为 L0 SSTable。

两者同时存在。前台写入新 MemTable 不阻塞，后台 flush 旧 MemTable 也不影响写入。但如果 flush 速度跟不上写入速度——新 MemTable 又满了，而旧的还没 flush 完——写入会被阻塞。这是写入延迟抖动的常见原因。

// 简化的写入流程（单线程版本）
void db_put(DB *db, const char *key, size_t klen,
  const char *val, size_t vlen) {
  // 1. WAL 追加
  wal_writer_append(&db->wal, record, record_len);

  // 2. MemTable 写入
  memtable_put(db->mem, kTypePut, key, klen, val, vlen);

  // 3. 检查是否需要 freeze
  if (db->mem->arena->bytes_used >= kWriteBufferSize) {
  db->imm = db->mem;  // 当前 MemTable → Immutable
  db->mem = memtable_new();  // 新建空 MemTable
  schedule_flush(db);  // 触发后台 flush
  }
}

WriteBatch 原子性

实际使用中，单条写入效率不高——每次都要 write() 一次 WAL。LevelDB 用 WriteBatch 解决这个问题：把多条写入操作打包成一个 batch，WAL 只写一条 record（包含 batch 的全部内容），然后逐条应用到 MemTable。

typedef struct {
  char  *data;  // 序列化的批量操作
  size_t  len;
  int  count;  // 操作数
} WriteBatch;

void write_batch_put(WriteBatch *b, const char *key, size_t klen,
  const char *val, size_t vlen) {
  // 追加: [type=Put | key_len | key | val_len | val]
  batch_append(b, kTypePut, key, klen, val, vlen);
  b->count++;
}

好处：

原子性：WAL 中只有一条 record。要么全部恢复，要么全部丢失。不会出现”batch 中一半写入成功一半丢失”的中间状态。
减少 I/O：N 次 write() 合并成 1 次。在《LevelDB 日常使用》中提到的 db->Write(write_options, &batch) 就是这个机制。

崩溃恢复：证明我们不丢数据

WAL + MemTable 的写入路径建立好了。现在来回答最关键的问题：凭什么相信崩溃后数据不会丢？

恢复流程

启动时的恢复流程很直接：

1. 打开 WAL 文件
2. 按 Block 读取（每次 32KB）
3. 在每个 Block 内逐条解析 Record：
  a. 读 Header → 校验 CRC32
  b. CRC 正确 → 将 Data 重放到新 MemTable
  c. CRC 错误 → 跳过当前 Record，报告损坏
4. 所有 Record 重放完毕 → MemTable 恢复完成

读取端需要处理分片——把 FIRST + MIDDLE* + LAST 重新拼装成完整的 record：

int wal_reader_read_record(WALReader *r, char **record, size_t *len) {
  bool in_fragment = false;
  size_t total_len = 0;

  while (1) {
  // 读取下一个 fragment 的 Header
  char header[kHeaderSize];
  if (read_block_data(r, header, kHeaderSize) != kHeaderSize)
  return -1;  // EOF

  uint32_t expected_crc = decode_fixed32(header);
  uint16_t length = decode_fixed16(header + 4);
  uint8_t  type  = (uint8_t)header[6];

  // 读取 Data
  char *data = read_block_data(r, NULL, length);

  // CRC 校验
  uint32_t actual_crc = crc32(0, &type, 1);
  actual_crc = crc32(actual_crc, (uint8_t *)data, length);
  if (actual_crc != expected_crc) {
  // 损坏：跳过，继续读下一个 Record
  report_corruption(r, length);
  in_fragment = false;
  continue;
  }

  switch (type) {
  case kFullType:
  *record = data;
  *len = length;
  return 0;

  case kFirstType:
  buffer_reset(r);
  buffer_append(r, data, length);
  in_fragment = true;
  break;

  case kMiddleType:
  if (!in_fragment) { /* skip orphan */ break; }
  buffer_append(r, data, length);
  break;

  case kLastType:
  if (!in_fragment) { /* skip orphan */ break; }
  buffer_append(r, data, length);
  *record = r->buffer;
  *len = r->buffer_len;
  in_fragment = false;
  return 0;
  }
  }
}

损坏场景分析

三种典型的崩溃场景：

场景 A：Block 中间断电。 正在写一条 FULL record，Header 写完了但 Data 只写了一半。恢复时：CRC32 校验失败（因为 Data 不完整）→ 跳过当前 record → 后续完好的 record 不受影响。丢失最后一条写入。

场景 B：分片写到一半。 FIRST fragment 写完了，但 MIDDLE 或 LAST 还没写。恢复时：FIRST 正常解析，然后 reader 等待后续 fragment。读到 EOF 或者读到另一个 FIRST/FULL → 检测到分片不完整 → 丢弃不完整的 record。丢失这条跨 Block 的写入。

场景 C：fsync 后断电。 所有已经 fsync() 过的 record 都已经持久化到磁盘 → 恢复时完整读出 → 零丢失。

正确性不变式

WAL + MemTable 的写入路径满足三个不变式：

不变式 1（持久性）：任何已返回 OK 且 sync=true 的写入，其 WAL record 已 fsync() 到磁盘，崩溃后可恢复。

证明：sync=true 时，wal_writer_append() 在 write() 后调用 fsync()，确保数据从 page cache 落盘。恢复时按 Block 读取并 CRC 校验，已落盘的 record 一定完整。

不变式 2（顺序性）：WAL 中 record 的顺序 = MemTable 插入顺序 = 全局 sequence 递增。

证明：单线程模型下，wal_writer_append() 和 memtable_put() 是顺序执行的。sequence 在 memtable_put() 中原子递增。

不变式 3（恢复完整性）：恢复后的 MemTable 状态是崩溃前 MemTable 状态的一个前缀——不会多出从未写入的数据，也不会丢失已 fsync() 的数据。

证明：恢复时只重放 CRC 校验通过的 record。因为 CRC 覆盖 Type + Data，任何被截断或损坏的 record 都会校验失败而被跳过。不可能凭空重放出一条用户从未写入的记录（CRC 碰撞概率 < \(2^{-32}\)）。

LevelDB 的选择：不保证 sync=false 时操作系统崩溃的数据安全。这是一个务实的工程决策——绝大多数应用可以容忍极端情况下丢失最后几条写入，但不能容忍 fsync() 带来的每次写入 ~10ms 的延迟。

把它们跑起来

把 WAL 和 MemTable 串在一起，一个最简单的写入+恢复流程：

int main(void) {
  // Phase 1: 正常写入
  WALWriter wal;
  wal_writer_open(&wal, "test.wal");

  MemTable *mem = memtable_new();

  const char *keys[]  = {"apple", "banana", "cherry"};
  const char *values[] = {"red",  "yellow", "dark-red"};

  for (int i = 0; i < 3; i++) {
  // 构造 WAL record: [key_len | key | val_len | val]
  char record[256];
  size_t rlen = encode_kv(record, keys[i], values[i]);

  wal_writer_append(&wal, record, rlen);
  memtable_put(mem, kTypePut,
  keys[i], strlen(keys[i]),
  values[i], strlen(values[i]));
  }
  printf("Wrote 3 keys.\n");

  // 模拟崩溃：直接销毁 MemTable（不 flush）
  memtable_destroy(mem);
  wal_writer_close(&wal);
  printf("MemTable destroyed (simulating crash).\n");

  // Phase 2: 从 WAL 恢复
  WALReader reader;
  wal_reader_open(&reader, "test.wal");

  MemTable *recovered = memtable_new();

  char *rec;
  size_t rec_len;
  while (wal_reader_read_record(&reader, &rec, &rec_len) == 0) {
  char *k, *v;
  size_t klen, vlen;
  decode_kv(rec, &k, &klen, &v, &vlen);
  memtable_put(recovered, kTypePut, k, klen, v, vlen);
  }
  wal_reader_close(&reader);

  // 验证恢复结果
  for (int i = 0; i < 3; i++) {
  char *val;
  size_t vlen;
  int ret = memtable_get(recovered, keys[i], strlen(keys[i]),
  &val, &vlen);
  printf("Recovered: %s -> %.*s (ret=%d)\n",
  keys[i], (int)vlen, val, ret);
  }

  memtable_destroy(recovered);
  return 0;
}

预期输出：

Wrote 3 keys.
MemTable destroyed (simulating crash).
Recovered: apple -> red (ret=0)
Recovered: banana -> yellow (ret=0)
Recovered: cherry -> dark-red (ret=0)

三个 key 全部从 WAL 恢复，没有数据丢失。

系列路线图

→ 系列目录页

篇目	标题	核心产出
第 1 篇	LSM-Tree 全景	架构心智模型 + 三种放大的数学推导
第 2 篇	WAL + MemTable（本文）	WAL 分片策略 + 跳表实现 + 崩溃恢复证明
第 3 篇	SSTable + Bloom Filter	Data Block 前缀压缩 + Bloom Filter 双重哈希 + Builder/Reader
第 4 篇	Compaction	多路归并迭代器 + Version/MANIFEST + 策略对比
第 5 篇	完整引擎 + Rust 重写对比	DB API + 并发 + Snapshot + Iterator + Rust 重写 + benchmark

→ 第 3 篇我们实现 SSTable 和 Bloom Filter：Data Block 的前缀压缩、Index Block 的二分查找、以及用 10 bits/key 把误判率压到 1% 的概率数据结构。

参考

Patrick O’Neil, Edward Cheng, Dieter Gawlick, Elizabeth O’Neil. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica, 1996.
LevelDB 源码: log_format.h — WAL record 格式定义。
LevelDB 源码: log_writer.cc — WAL 写入实现。
LevelDB 源码: log_reader.cc — WAL 读取与恢复。
LevelDB 源码: skiplist.h — 无锁跳表（本文简化为有锁版本）。
LevelDB 源码: memtable.cc — MemTable + InternalKey 编码。
William Pugh. Skip Lists: A Probabilistic Alternative to Balanced Trees. Communications of the ACM, 1990.
本站相关文章：LevelDB 日常使用 — fsync 策略与 WriteBatch API。
本站相关文章：leveldb 的缓存结构 — Block Cache 与 Table Cache 的 LRU 实现。