WAL + MemTable：崩溃了也不丢数据

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

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

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

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

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

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 实现。

目录