手写 LSM 存储引擎（二）：Memtable 与跳表

(手写 LSM 存储引擎, Part 2)

前言

上一篇讲了 LSM 的整体思路——所有写入都追加到新位置，数据分层管理，后台 compaction 整理碎片。这一篇把视角收回到最顶上那一层：Memtable。

所有写入都先落到 Memtable，所以它的性能直接决定引擎的写入吞吐。Memtable 该怎么设计？用什么数据结构？怎么处理删除？冻结的时候怎么保证没有线程还在往旧表写？

本篇对应 golsm 里 Day 1 的 commit。

内存层要做什么

先想想 Memtable 要支持哪些操作：

• Put(key, value)：写入或覆盖
• Get(key)：按 key 查询
• Delete(key)：删除
• 遍历：flush 的时候要按 key 顺序把所有数据写到 SSTable
• 范围扫描：range scan 要从某个 key 开始顺序读

Put 和 Get 是 O(1) 还是 O(log n) 倒不是关键，真正的硬约束是有序。因为 SSTable 要求数据按 key 有序排列，如果 Memtable 里的数据是乱的，flush 之前就要先排序——几百万条记录排一次很贵，还阻塞后续写入。

所以 Memtable 的数据结构要满足三个条件：

1. 有序
2. 插入、查找、遍历都不太慢
3. 并发读写友好——LSM 的写路径是高并发的，多个 goroutine 同时写 Memtable 是常态

候选数据结构的对比

满足"有序"的数据结构其实不多：

结构	插入/查找	并发友好度	实现复杂度
红黑树	O(log n)	低。旋转操作涉及多个节点，加锁粒度粗	中
B-Tree	O(log n)	低。节点分裂/合并需要锁住路径上的多个节点	高
跳表	O(log n) 期望	高。插入只改局部指针，容易做 lock-free	低
排序数组 + 二分	O(n) 插入	差	极低

跳表在写入场景下有一个明显的优势——局部性。插入一个节点只需要修改几个前驱指针，不涉及整棵树的结构变动。对比红黑树，插入可能触发连锁的颜色翻转和旋转，锁的粒度很难做细。

所以 LevelDB、RocksDB、Pebble、HBase 的 MemStore——无一例外——Memtable 都是跳表。

跳表是什么

跳表的核心思想是给有序链表加多层"索引"，每一层都是下一层的稀疏子集。查找的时候从最高层开始横着走，走不动了再下沉一层。

Level 2:  1 ─────────────────────→ 15
          │                         │
Level 1:  1 ────────→ 7 ────────→ 15
          │           │            │
Level 0:  1 → 3 → 5 → 7 → 9 → 12 → 15 → 20

找 12：Level 2 走不动（下一个 15 太大），下沉到 Level 1，走到 7，再下沉到 Level 0，从 7 往右两步找到 12。

关键点：节点的层高是随机决定的。插入一个新节点时抛硬币——正面继续往上长一层，反面停下。这个概率过程保证了期望意义上的平衡，不需要像红黑树那样主动维护。

层高一般用 p=0.5 的几何分布，一个节点有 1/2 的概率达到 Level 1，1/4 达到 Level 2，依此类推。期望层数是 log₂ n，查找期望步数 O(log n)。

跳表的好处在插入：

插入 key="dog":

Level 2:  "apple" ──────────────────→ "grape"
             │                           │
Level 1:  "apple" ────→ "cat" ────→ "grape"
             │            │             │
Level 0:  "apple" → "cat" → "dog" → "grape" → "zoo"
                          ↑
                       只改这几个指针

插入"dog"只修改了 Level 0 里它前后两个节点的指针。如果随机到 Level 1，再多改一个。总之修改范围是局部的——这就是为什么跳表适合并发。

MemTable 的接口

我们的 MemTable 非常薄——本质上是一个带锁的跳表外加一些元信息：

type MemTable struct {
    mu   sync.RWMutex
    id   uint64
    list *skiplist.SkipList
    size uint64 // 近似字节数
}

func (m *MemTable) Put(key, value []byte) {
    m.mu.Lock()
    defer m.mu.Unlock()
    elem := m.list.Get(key)
    if elem != nil {
        oldVal := elem.Value.([]byte)
        m.size -= uint64(len(key) + len(oldVal))
    }
    m.size += uint64(len(key) + len(value))
    m.list.Set(key, value)
}

size 字段不是精确内存占用，而是所有 key+value 字节的累加。它用来判断 Memtable 什么时候"满了"——超过阈值就冻结。

id 用来给每个 Memtable 起唯一编号。为什么要编号？因为一个引擎实例运行期间会产生很多 Memtable（冻结一个就造一个新的），编号用来和后续的 SSTable ID 对应，方便追踪数据血缘。

为什么没有 Delete 接口

注意到 MemTable 只有 Put 没有 Delete。上一篇提过——LSM 的删除是写一条空值（tombstone，墓碑）：

func (l *LsmStorage) Delete(key []byte) {
    l.Put(key, []byte{})
}

这条空值记录会按时间顺序盖住所有旧版本。读取的时候发现空值就当作"不存在"返回。为什么 LSM 不能"真的删除"：

1. 旧版本可能在已经 flush 到磁盘的 SSTable 里，SSTable 不可变，改不了
2. 就算能改，也要回头做随机 I/O，违背了 LSM 的设计哲学

空值之外，也可以用单独的"类型标志位"来区分墓碑——RocksDB 就这么做。我们这个实现用空值，图个简单，思想是一样的。

冻结 Memtable

Memtable 满了以后要冻结成"不可变 memtable"，排队等 flush。同时创建一个新的 mutable memtable 接收后续写入。

┌──────────────┐   freeze    ┌──────────────┐          ┌──────────────┐
│  Memtable 5  │ ─────────→  │  Immutable 5 │   新建    │  Memtable 6  │
│  (mutable)   │             │  (只读)       │         │  (mutable)   │
└──────────────┘             └──────────────┘          └──────────────┘
                                    │
                                    │ 后台 flush
                                    ▼
                            ┌──────────────┐
                            │  L0 SSTable  │
                            └──────────────┘

冻结的触发点在每次 Put 之后：

func (l *LsmStorage) Put(key, value []byte) {
    // ... 写入 memtable ...
    if mt.ApproximateSize() >= l.options.MemTableSizeCap {
        l.stateLock.Lock()
        // 二次检查
        if l.inner.memtable.ApproximateSize() >= l.options.MemTableSizeCap {
            l.forceFreezeMemtable()
        }
        l.stateLock.Unlock()
    }
}

这里有个细节——双检查锁（double-checked locking）。为什么要两次检查？因为多个 goroutine 可能同时发现"memtable 满了"，但只需要一个去真正冻结，其他的应该直接放过。

流程是：

1. 无锁检查一次大小。没满就直接返回
2. 满了，获取 stateLock（序列化状态修改）
3. 锁内再检查一次——可能别的 goroutine 已经冻结过了，现在的 memtable 已经是个新的空表
4. 确认还是老的满表，才执行冻结

双检查模式的好处是——快路径完全无锁，慢路径才付出锁的代价。

状态替换：Copy-on-Write

冻结的具体实现思路是 不修改旧状态，构造新状态，原子替换指针：

// 伪代码
func (l *LsmStorage) forceFreezeMemtable() {
    newID := l.nextSSTID
    l.nextSSTID++

    newState := &LsmStorageState{
        memtable:     NewMemTable(newID),                 // 全新的 mutable
        immMemtables: prepend(l.inner.memtable, l.inner.immMemtables),  // 老的压到队首
        l0SSTables:   l.inner.l0SSTables,                 // 其他字段原样继承
        levels:       l.inner.levels,
        sstables:     l.inner.sstables,
    }

    l.stateMu.Lock()
    l.inner = newState        // 原子替换
    l.stateMu.Unlock()
}

这种"状态指针替换"模式的好处是：

• 读者拿到 l.inner 的快照后，即便之后被冻结了也不受影响——它手里的指针还指向旧状态
• 冻结过程不需要长时间持锁，只在最后交换指针那一瞬间持写锁

后面讲读路径的时候会看到这个设计的威力——一致性快照几乎是免费的。

并发：不止一层锁

这个设计里一共有三层并发保护：

1. stateMu (sync.RWMutex)：保护 l.inner 这个指针。读者 RLock，替换状态时 Lock
2. stateLock (sync.Mutex)：序列化所有状态修改操作（冻结、flush、compaction）。避免多个 goroutine 同时冻结
3. MemTable.mu (sync.RWMutex)：保护单个 Memtable 内部的跳表

第三层是实现过程中踩过坑才加的。huandu/skiplist 不是并发安全的——stateMu.RLock() 允许多个读者同时拿到同一个 Memtable 的指针，但这些读者其实都在写（调 Put），跳表内部就 panic 了。

Rust 原版 mini-lsm 用的是 crossbeam-skiplist，那是真·无锁并发跳表。Go 这边没有同样成熟的选项，老老实实加 RWMutex 性能也够用——从压测数据看，MemTable.Put 约 1.2 µs，裸引擎 Put 1.1 µs，几乎没有损失。

迭代器

跳表天然支持顺序遍历。包装一下就是 MemTableIterator：

type MemTableIterator struct {
    mt    *MemTable
    mu    *sync.RWMutex   // 指向 MemTable.mu
    cur   *skiplist.Element
    lower []byte
    upper []byte
}

几个关键点：

• 持有 MemTable 的锁引用：迭代过程中其他 goroutine 可能正在写，每次 Next() 都要加读锁
• lower/upper 支持范围扫描：[lower, upper) 半开区间，和 Go 里的惯例一致
• 生命周期：用完要显式释放，否则长期持锁会阻塞写入

迭代器用的场景主要是：

1. Flush：遍历整个 Memtable，写到 SSTable
2. Range scan：用户发起的范围查询
3. 事务 commit：把事务的私有缓冲区复制到 Memtable

小结

Memtable 看着简单，其实踩过几个坑——

1. 选跳表不是因为它"快"，是因为它插入局部性好，天然并发友好，且有序
2. 删除用空值而不是真删，是 LSM 的核心设计哲学——不碰已写入的数据
3. 冻结用双检查锁避免惊群，用 Copy-on-Write 让读者不受影响
4. Go 没有 crossbeam-skiplist，老老实实加 RWMutex 即可，性能损失可忽略
5. 锁的分层要想清楚——状态锁保护指针，Memtable 锁保护数据结构，少一层都不行

下一篇开始讨论磁盘那边——SSTable 的物理布局。