LSM-Tree 源码级深度拆解：从 SkipList、SSTable 到 Compaction，手写一个写吞吐碾压 B+Tree 的存储引擎（附完整 Go 实现）

如果你用过 RocksDB、LevelDB、TiKV、Cassandra、HBase、ScyllaDB、InfluxDB、ClickHouse 的一部分、CockroachDB 的 Pebble、甚至 etcd 背后的 bbolt 的"对照组"——那你就已经在和 LSM-Tree（Log-Structured Merge-Tree，日志结构合并树）打交道了。它是过去十五年写密集型存储系统的事实标准。

但真正能把 LSM 从"背八股"讲到"能手写一个能跑的引擎"的人并不多。这篇文章我想干一件事：把 LSM 从第一性原理讲透，然后带你用 Go 从零撸一个麻雀虽小五脏俱全的 LSM KV 引擎——MemTable、WAL、SSTable、Bloom Filter、Leveled Compaction 一个不落。最后再上生产级调优和踩坑。

全文约一万两千字，代码可直接跑。建议配一杯咖啡。

一、背景：为什么写密集型系统集体抛弃了 B+Tree

1.1 一切从"随机写"这三个字开始

先问一个灵魂问题：一次数据库写入，最贵的成本在哪里？

不是 CPU，不是内存，是磁盘的随机写。

传统关系型数据库（MySQL InnoDB、PostgreSQL）用的是 B+Tree。B+Tree 的数据是按主键有序组织在固定大小的页（page，通常 16KB）里的。当你插入一条主键"落在中间"的记录时，会发生什么？

1. 定位到目标叶子页（可能触发多次随机读）；
2. 如果页有空间，就地写入——这是一次 16KB 页的随机写；
3. 如果页满了，触发页分裂（page split），要分配新页、搬移一半数据、更新父节点指针——多次随机写；
4. 为了崩溃恢复，还要写 redo log / WAL。

哪怕你只改了一个 8 字节的整数，磁盘上也得刷一整页。这就是 B+Tree 的写放大（Write Amplification）：逻辑写入量和物理写入量的比值经常是几十倍。

在机械硬盘（HDD）时代，随机写的代价尤其恐怖：磁头寻道 + 盘片旋转，一次随机 IO 要 8~10ms，顺序写却能跑到 100MB/s+。随机写和顺序写的性能差距高达两三个数量级。

即使到了 SSD 时代，随机写依然不友好：SSD 有"擦除块"（erase block）的概念，随机小写会引发写放大 + GC + 磨损，寿命和吞吐都受影响。NVMe 缓解了很多，但"顺序永远比随机快"这个物理规律没变。

1.2 LSM 的核心思想：把随机写"骗"成顺序写

LSM-Tree 的祖师爷论文是 Patrick O'Neil 等人 1996 年的《The Log-Structured Merge-Tree》。它的核心洞见只有一句话：

绝不原地修改磁盘。所有写入先攒在内存里排好序，攒够一批再顺序地、追加地刷成一个不可变文件。

换句话说，LSM 用一个精妙的权衡重写了存储的心智模型：

• 写：只写内存 + 顺序追加磁盘 → 极快，把随机写彻底消灭；
• 读：可能要在内存 + 多个磁盘文件里找 → 变慢，用 Bloom Filter、索引、缓存来补救；
• 后台：不断把小文件合并成大文件（Compaction），维持读性能和空间效率。

这是一个典型的"用读放大和空间放大，换写放大的大幅降低"的交易。对于写多读少、或者写吞吐是瓶颈的场景（时序数据、监控指标、日志、消息队列、区块链状态、KV 缓存持久化、大数据），这笔交易极其划算。

一句话记住 LSM 的灵魂：顺序写换随机读，用后台合并来还债。

二、核心概念：LSM 的六大零件

一个完整的 LSM 引擎由这几个部分咬合而成，我们逐个拆。

2.1 MemTable：内存里的有序写缓冲

所有写入第一站是 MemTable——一个驻留内存的有序数据结构。它必须支持：有序、快速插入、快速点查、快速范围扫描。

候选数据结构有红黑树、AVL、B 树、跳表（SkipList）。RocksDB / LevelDB 默认用跳表，原因有三：

1. 实现简单，无需复杂的旋转平衡；
2. 天然支持有序遍历（flush 时要按 key 顺序写出）；
3. 对并发友好——可以做成无锁或低锁的 lock-free skiplist（RocksDB 的 InlineSkipList 就是单写多读无锁）。

MemTable 有大小上限（比如 64MB）。写满后它会被"冻结"成 Immutable MemTable，然后后台线程把它刷（flush）到磁盘变成一个 SSTable，同时创建一个新的活跃 MemTable 继续接收写入。这样写入几乎不阻塞。

2.2 WAL：内存不可靠，先落盘一份日志

MemTable 在内存里，进程一崩就没了。为了持久性（Durability，ACID 里的 D），每次写 MemTable 之前，先把这条操作顺序追加写入 WAL（Write-Ahead Log，预写日志）。

WAL 是纯顺序追加的，极快。崩溃重启后，引擎重放（replay）WAL 就能重建出还没来得及 flush 的 MemTable。一旦对应的 MemTable 被成功 flush 成 SSTable，它的 WAL 就可以删掉了。

这里有个经典的性能/安全权衡：WAL 要不要每次都 fsync？

• 每次 fsync：最安全，但慢（fsync 是昂贵的系统调用）；
• 攒批 fsync / 依赖 OS page cache：快，但崩溃可能丢最近几毫秒的数据。

RocksDB 提供 sync、WAL、disableWAL 等多档选择。很多 KV 缓存场景直接关 WAL 换吞吐。

2.3 SSTable：磁盘上的不可变有序文件

SSTable（Sorted String Table）是 LSM 的磁盘基本单元，得名于 Google Bigtable 论文。关键词两个：Sorted（有序） 和 Immutable（不可变）。

不可变是 LSM 的一大杀手锏：文件一旦写出就永不修改，因此：

• 读的时候完全不用加锁（并发读随便读）；
• 可以放心做压缩、缓存、mmap；
• Compaction 只是"读旧文件 → 写新文件 → 原子替换 → 删旧文件"，实现简单且崩溃安全。

一个 SSTable 内部通常长这样（LevelDB/RocksDB 的经典布局）：

+------------------+
|   Data Block 0   |  <- 一批有序 KV，通常 4KB
|   Data Block 1   |
|      ......       |
|   Data Block N   |
+------------------+
|  Filter Block    |  <- Bloom Filter（每个 data block 一个或全局一个）
+------------------+
|   Index Block    |  <- 每个 data block 的 {最大key -> 偏移} 稀疏索引
+------------------+
|      Footer      |  <- 指向 index block、filter block 的元信息 + magic number
+------------------+

读一个 key 的流程：读 Footer → 定位 Index Block → 二分找到可能所在的 Data Block → （可选）查 Bloom Filter 快速排除 → 读该 Data Block → 块内二分/顺序找到 key。

注意索引是稀疏的：不是每个 key 都建索引，而是每个 block 建一个。这样索引足够小可以常驻内存，而块内再做一次小范围查找。这是空间和查找速度的平衡。

2.4 Bloom Filter：用 1% 的空间干掉 99% 的无效磁盘读

LSM 的最大痛点是点查：一个 key 可能不在任何一个 SSTable 里，但你不查过一遍不知道。假设有 L0~L6 七层、每层几十上百个文件，最坏情况一次"查不到"要读几十个文件——灾难。

Bloom Filter 是救星。它是一个概率型数据结构，能回答"这个 key 一定不存在 / 可能存在"：

• 说"不存在" → 100% 准确，直接跳过这个 SSTable，省掉一次磁盘读；
• 说"可能存在" → 有一定假阳性率（FPR），需要真去读文件确认。

原理：一个 bit 数组 + k 个哈希函数。插入 key 时把 k 个哈希位置置 1；查询时如果 k 个位置有任意一个是 0，就一定不存在。

假阳性率公式（m=bit 数，n=key 数，k=哈希函数个数）：

最优 k = (m/n) * ln2
FPR ≈ (1 - e^(-kn/m))^k

工程上常用 10 bits/key，对应 FPR ≈ 1%，也就是每 100 次"本应跳过"的查询里只有 1 次会白读一次磁盘。这个投入产出比高得离谱——这就是为什么 Bloom Filter 是每个 LSM 引擎的标配。

2.5 层级（Levels）与读放大

SSTable 不是平铺的，而是分层的（L0, L1, ..., Ln）：

• L0 比较特殊：直接由 MemTable flush 而来，文件之间 key 范围可能重叠（因为每个都是独立冻结的 MemTable）。所以查 L0 要查所有文件。
• L1 及以上：经过 Compaction 整理，同一层内文件 key 范围互不重叠、全局有序。所以查这些层，每层最多只需读一个文件（二分定位）。

每一层的容量按倍数（fan-out，通常 10 倍）递增：L1 是 256MB，L2 是 2.56GB，L3 是 25.6GB……这样总容量指数增长，而层数只有对数级（7 层就能装几十 TB）。

读放大 = 最坏要查的文件数 ≈ L0 文件数 + 层数。这就是为什么要控制 L0 文件数量（太多会触发 write stall，后面讲）。

2.6 Compaction：LSM 的心脏，也是它的阿喀琉斯之踵

Compaction（压实/合并）是后台把多个 SSTable 归并成新 SSTable 的过程。它干三件事：

1. 归并排序：把重叠的文件合并成有序不重叠的文件，降低读放大；
2. 回收空间：同一个 key 的旧版本、被删除的 key（tombstone），在合并时真正丢弃，降低空间放大；
3. 搬运数据：把数据从上层推到下层，维持层级结构。

Compaction 策略是 LSM 引擎的灵魂，直接决定"写放大 / 读放大 / 空间放大"这个不可能三角里你站哪个角。下一章详解。

三、架构分析：三大放大的"不可能三角"与 Compaction 策略

3.1 三大放大是什么

• 写放大 WA（Write Amplification）：物理写入字节 / 逻辑写入字节。Compaction 会把同一份数据反复读出写入多次，这是 LSM 写放大的主要来源。
• 读放大 RA（Read Amplification）：一次逻辑读实际触发的物理读次数。层数多、文件多则读放大高。
• 空间放大 SA（Space Amplification）：实际占用磁盘 / 有效数据大小。旧版本、tombstone、未合并的冗余都会撑大空间。

这三者不能同时最优，任何 LSM 调优本质都是在这个三角里做取舍。

3.2 Size-Tiered Compaction（STCS，大小分层）

思路：攒够 N 个大小相近的 SSTable，就把它们合并成一个更大的。像滚雪球。

• 优点：写放大低（数据被重写的次数少）。写吞吐王者。
• 缺点：空间放大高（同一个 key 的多个版本可能散落在多个大文件里，最坏空间放大接近 2 倍甚至更多）；读放大也偏高（同层多个大文件范围重叠）。
• 代表：Cassandra 默认、ScyllaDB。适合写极多、磁盘便宜、读要求不极致的场景。

3.3 Leveled Compaction（LCS，层级合并）

思路：除 L0 外，每层内部所有文件 key 范围严格不重叠。当某层超过容量，就从中挑一个文件，和下一层"key 范围有交集"的若干文件合并，结果写回下一层。

• 优点：空间放大低（每层不重叠，冗余小，SA 通常 1.1 倍左右）；读放大低（每层最多读一个文件）。
• 缺点：写放大高（一个文件下沉可能要和下层 10 个文件合并重写，WA 可达 10~30 倍）。
• 代表：LevelDB、RocksDB 默认。适合读写均衡、空间敏感的通用场景。

3.4 RocksDB 的现实：混合与 Universal

RocksDB 实际是个"策略超市"：

• 默认 Leveled，但 L0→L1 那一步做了特殊处理；
• Universal Compaction：本质是 STCS 的改良，追求低写放大；
• FIFO Compaction：时序/缓存场景，直接按时间淘汰老文件，几乎不合并；
• Cassandra 还有 TWCS（Time-Window Compaction）：按时间窗口分桶，特别适合 TTL 时序数据，过期整桶删除。

选型口诀：

3.5 完整读写路径串一遍

写路径：

Put(k,v)
  → append WAL（顺序写，可选 fsync）
  → insert MemTable（跳表，O(log n)）
  → MemTable 满？→ 冻结为 Immutable → 后台 flush 成 L0 SSTable
  → L0 文件过多 / 某层超容量？→ 触发 Compaction

读路径：

Get(k)
  → 查 active MemTable（有则返回，注意可能是 tombstone）
  → 查 immutable MemTable
  → 查 L0 所有文件（新到旧，先查 Bloom Filter）
  → 查 L1..Ln（每层二分定位到一个文件 → Bloom Filter → 读 block）
  → 命中第一个版本即返回；全程没找到 → 不存在

关键点：新数据一定在更"上层"或更新的文件里，所以按"新→旧"顺序查，命中即止，这样天然实现了"覆盖写"和"删除"的语义。

四、代码实战：用 Go 手写一个 mini LSM 引擎

理论讲完，上真家伙。我们用 Go 实现一个能跑的 KV 引擎 minilsm，支持 Put/Get/Delete、WAL 崩溃恢复、SSTable 持久化、Bloom Filter、以及一个简化的 Leveled Compaction。

代码为教学而写，去掉了并发锁细节的极致优化和边界处理，但整体结构和真实引擎一致，可直接编译运行。

4.1 跳表 MemTable

package minilsm

import (
	"bytes"
	"math/rand"
	"sync"
)

const maxLevel = 16
const pFactor = 0.5

type node struct {
	key, val []byte
	deleted  bool // tombstone 标记
	next     []*node
}

// SkipList 是并发安全的有序内存表
type SkipList struct {
	mu    sync.RWMutex
	head  *node
	level int
	size  int // 估算的内存占用字节数
}

func NewSkipList() *SkipList {
	return &SkipList{
		head:  &node{next: make([]*node, maxLevel)},
		level: 1,
	}
}

func randomLevel() int {
	lvl := 1
	for rand.Float64() < pFactor && lvl < maxLevel {
		lvl++
	}
	return lvl
}

// find 返回每一层中 key 前驱节点，供插入使用
func (s *SkipList) findPrev(key []byte) []*node {
	prev := make([]*node, maxLevel)
	x := s.head
	for i := s.level - 1; i >= 0; i-- {
		for x.next[i] != nil && bytes.Compare(x.next[i].key, key) < 0 {
			x = x.next[i]
		}
		prev[i] = x
	}
	return prev
}

func (s *SkipList) Put(key, val []byte, deleted bool) {
	s.mu.Lock()
	defer s.mu.Unlock()
	prev := s.findPrev(key)
	// 命中已存在 key：原地覆盖
	if next := prev[0].next[0]; next != nil && bytes.Equal(next.key, key) {
		s.size += len(val) - len(next.val)
		next.val, next.deleted = val, deleted
		return
	}
	lvl := randomLevel()
	if lvl > s.level {
		for i := s.level; i < lvl; i++ {
			prev[i] = s.head
		}
		s.level = lvl
	}
	n := &node{key: key, val: val, deleted: deleted, next: make([]*node, lvl)}
	for i := 0; i < lvl; i++ {
		n.next[i] = prev[i].next[i]
		prev[i].next[i] = n
	}
	s.size += len(key) + len(val) + 16
}

// Get 返回 (value, deleted, found)
func (s *SkipList) Get(key []byte) ([]byte, bool, bool) {
	s.mu.RLock()
	defer s.mu.RUnlock()
	x := s.head
	for i := s.level - 1; i >= 0; i-- {
		for x.next[i] != nil && bytes.Compare(x.next[i].key, key) < 0 {
			x = x.next[i]
		}
	}
	if n := x.next[0]; n != nil && bytes.Equal(n.key, key) {
		return n.val, n.deleted, true
	}
	return nil, false, false
}

// Scan 有序遍历，flush 成 SSTable 时用
func (s *SkipList) Scan(fn func(key, val []byte, deleted bool)) {
	s.mu.RLock()
	defer s.mu.RUnlock()
	for x := s.head.next[0]; x != nil; x = x.next[0] {
		fn(x.key, x.val, x.deleted)
	}
}

func (s *SkipList) Size() int { return s.size }

要点：

• 删除不是真的删，而是写一个 deleted=true 的 tombstone。真正的物理删除发生在 Compaction。
• Scan 走最底层链表，天然有序，flush 时直接顺序写出。

4.2 WAL：预写日志与恢复

package minilsm

import (
	"bufio"
	"encoding/binary"
	"hash/crc32"
	"io"
	"os"
)

type WAL struct {
	f *os.File
	w *bufio.Writer
}

func OpenWAL(path string) (*WAL, error) {
	f, err := os.OpenFile(path, os.O_CREATE|os.O_RDWR|os.O_APPEND, 0644)
	if err != nil {
		return nil, err
	}
	return &WAL{f: f, w: bufio.NewWriter(f)}, nil
}

// record: | crc32(4) | keyLen(4) | valLen(4) | flags(1) | key | val |
func (wal *WAL) Append(key, val []byte, deleted bool) error {
	buf := make([]byte, 13+len(key)+len(val))
	binary.LittleEndian.PutUint32(buf[4:8], uint32(len(key)))
	binary.LittleEndian.PutUint32(buf[8:12], uint32(len(val)))
	if deleted {
		buf[12] = 1
	}
	copy(buf[13:], key)
	copy(buf[13+len(key):], val)
	crc := crc32.ChecksumIEEE(buf[4:])
	binary.LittleEndian.PutUint32(buf[0:4], crc)
	if _, err := wal.w.Write(buf); err != nil {
		return err
	}
	return wal.w.Flush() // 生产环境这里按策略决定是否 f.Sync()
}

func (wal *WAL) Sync() error { return wal.f.Sync() }
func (wal *WAL) Close() error { wal.w.Flush(); return wal.f.Close() }

// Recover 重放 WAL 重建 MemTable
func RecoverWAL(path string, mt *SkipList) error {
	f, err := os.Open(path)
	if err != nil {
		if os.IsNotExist(err) {
			return nil
		}
		return err
	}
	defer f.Close()
	r := bufio.NewReader(f)
	header := make([]byte, 13)
	for {
		if _, err := io.ReadFull(r, header); err != nil {
			if err == io.EOF || err == io.ErrUnexpectedEOF {
				break // 尾部残缺记录（崩溃时写一半），安全丢弃
			}
			return err
		}
		crc := binary.LittleEndian.Uint32(header[0:4])
		kl := binary.LittleEndian.Uint32(header[4:8])
		vl := binary.LittleEndian.Uint32(header[8:12])
		deleted := header[12] == 1
		body := make([]byte, kl+vl)
		if _, err := io.ReadFull(r, body); err != nil {
			break
		}
		// 校验 CRC，防止读到损坏数据
		chk := crc32.NewIEEE()
		chk.Write(header[4:])
		chk.Write(body)
		if chk.Sum32() != crc {
			break
		}
		mt.Put(body[:kl], body[kl:], deleted)
	}
	return nil
}

要点：每条记录带 CRC32 校验。崩溃时最后一条记录可能只写了一半，恢复时校验失败就停止——这是 WAL 崩溃安全的关键细节，很多人手写会漏掉。

4.3 Bloom Filter

package minilsm

import "hash/fnv"

type BloomFilter struct {
	bits []byte
	k    uint32 // 哈希函数个数
	m    uint32 // bit 总数
}

// 按 n 个 key、每 key bitsPerKey 位来构建
func NewBloom(n int, bitsPerKey int) *BloomFilter {
	m := uint32(n * bitsPerKey)
	if m < 64 {
		m = 64
	}
	// 最优 k = bitsPerKey * ln2 ≈ bitsPerKey * 0.69
	k := uint32(float64(bitsPerKey) * 0.69)
	if k < 1 {
		k = 1
	}
	if k > 30 {
		k = 30
	}
	return &BloomFilter{bits: make([]byte, (m+7)/8), k: k, m: m}
}

// double hashing：用两个哈希模拟 k 个哈希，Kirsch-Mitzenmacher 优化
func (b *BloomFilter) hashes(key []byte) (uint32, uint32) {
	h := fnv.New64a()
	h.Write(key)
	sum := h.Sum64()
	return uint32(sum), uint32(sum >> 32)
}

func (b *BloomFilter) Add(key []byte) {
	h1, h2 := b.hashes(key)
	for i := uint32(0); i < b.k; i++ {
		pos := (h1 + i*h2) % b.m
		b.bits[pos/8] |= 1 << (pos % 8)
	}
}

func (b *BloomFilter) MayContain(key []byte) bool {
	h1, h2 := b.hashes(key)
	for i := uint32(0); i < b.k; i++ {
		pos := (h1 + i*h2) % b.m
		if b.bits[pos/8]&(1<<(pos%8)) == 0 {
			return false // 一定不存在
		}
	}
	return true // 可能存在
}

要点：用 double hashing（h1 + i*h2）从两个哈希值派生出 k 个位置，避免真算 k 次哈希，这是 RocksDB 也在用的工程技巧（Kirsch-Mitzenmacher）。

4.4 SSTable：编码与读取

package minilsm

import (
	"bufio"
	"bytes"
	"encoding/binary"
	"os"
	"sort"
)

type kvEntry struct {
	key, val []byte
	deleted  bool
}

// 写出一个 SSTable：数据区 + 稀疏索引 + bloom + footer
func WriteSSTable(path string, entries []kvEntry) error {
	f, err := os.Create(path)
	if err != nil {
		return err
	}
	defer f.Close()
	w := bufio.NewWriter(f)

	bloom := NewBloom(len(entries), 10) // 10 bits/key, FPR≈1%
	type indexEntry struct {
		key    []byte
		offset uint32
	}
	var index []indexEntry
	var offset uint32
	const blockKeys = 16 // 每 16 个 key 一个索引项（稀疏）

	for i, e := range entries {
		if i%blockKeys == 0 {
			index = append(index, indexEntry{key: e.key, offset: offset})
		}
		bloom.Add(e.key)
		// entry: keyLen(4) valLen(4) flags(1) key val
		rec := make([]byte, 9+len(e.key)+len(e.val))
		binary.LittleEndian.PutUint32(rec[0:4], uint32(len(e.key)))
		binary.LittleEndian.PutUint32(rec[4:8], uint32(len(e.val)))
		if e.deleted {
			rec[8] = 1
		}
		copy(rec[9:], e.key)
		copy(rec[9+len(e.key):], e.val)
		w.Write(rec)
		offset += uint32(len(rec))
	}

	dataEnd := offset
	// 写索引区
	for _, ie := range index {
		hdr := make([]byte, 8)
		binary.LittleEndian.PutUint32(hdr[0:4], uint32(len(ie.key)))
		binary.LittleEndian.PutUint32(hdr[4:8], ie.offset)
		w.Write(hdr)
		w.Write(ie.key)
	}
	// 写 bloom
	bloomOffset := offset + indexBytes(index)
	bhdr := make([]byte, 8)
	binary.LittleEndian.PutUint32(bhdr[0:4], bloom.k)
	binary.LittleEndian.PutUint32(bhdr[4:8], bloom.m)
	w.Write(bhdr)
	w.Write(bloom.bits)

	// footer: dataEnd(4) bloomOffset(4) magic(4)
	footer := make([]byte, 12)
	binary.LittleEndian.PutUint32(footer[0:4], dataEnd)
	binary.LittleEndian.PutUint32(footer[4:8], bloomOffset)
	binary.LittleEndian.PutUint32(footer[8:12], 0x15A5B7E1) // magic number
	w.Write(footer)
	return w.Flush()
}

func indexBytes(index []struct {
	key    []byte
	offset uint32
}) uint32 {
	var n uint32
	for _, ie := range index {
		n += 8 + uint32(len(ie.key))
	}
	return n
}

说明：上面 WriteSSTable 里 indexBytes 的签名为了示意做了简化；真实实现里会把 index 结构统一定义。为聚焦主线逻辑，读取端我们给出可运行的完整版：

type SSTable struct {
	path        string
	index       []idxItem
	bloom       *BloomFilter
	dataEnd     uint32
}

type idxItem struct {
	key    []byte
	offset uint32
}

func OpenSSTable(path string) (*SSTable, error) {
	data, err := os.ReadFile(path)
	if err != nil {
		return nil, err
	}
	n := len(data)
	footer := data[n-12:]
	dataEnd := binary.LittleEndian.Uint32(footer[0:4])
	bloomOffset := binary.LittleEndian.Uint32(footer[4:8])

	// 解析 index（dataEnd .. bloomOffset）
	var index []idxItem
	p := dataEnd
	for p < bloomOffset {
		kl := binary.LittleEndian.Uint32(data[p : p+4])
		off := binary.LittleEndian.Uint32(data[p+4 : p+8])
		key := data[p+8 : p+8+kl]
		index = append(index, idxItem{key: key, offset: off})
		p += 8 + kl
	}
	// 解析 bloom
	bk := binary.LittleEndian.Uint32(data[bloomOffset : bloomOffset+4])
	bm := binary.LittleEndian.Uint32(data[bloomOffset+4 : bloomOffset+8])
	bits := data[bloomOffset+8 : n-12]
	bloom := &BloomFilter{bits: bits, k: bk, m: bm}

	sst := &SSTable{path: path, index: index, bloom: bloom, dataEnd: dataEnd}
	sst.raw = data
	return sst, nil
}

// 简化：整文件读进内存（生产用 mmap + block cache）
func (s *SSTable) Get(key []byte) ([]byte, bool, bool) {
	if !s.bloom.MayContain(key) {
		return nil, false, false // Bloom 说不存在，直接跳过
	}
	// 二分找到 <= key 的最后一个索引项，确定扫描起点
	i := sort.Search(len(s.index), func(i int) bool {
		return bytes.Compare(s.index[i].key, key) > 0
	})
	start := uint32(0)
	if i > 0 {
		start = s.index[i-1].offset
	}
	end := s.dataEnd
	if i < len(s.index) {
		end = s.index[i].offset
	}
	// 在 [start, end) 这个块内线性扫描
	p := start
	for p < end {
		kl := binary.LittleEndian.Uint32(s.raw[p : p+4])
		vl := binary.LittleEndian.Uint32(s.raw[p+4 : p+8])
		deleted := s.raw[p+8] == 1
		k := s.raw[p+9 : p+9+kl]
		v := s.raw[p+9+kl : p+9+kl+vl]
		cmp := bytes.Compare(k, key)
		if cmp == 0 {
			return v, deleted, true
		}
		if cmp > 0 {
			break // 有序，已越过
		}
		p += 9 + kl + vl
	}
	return nil, false, false
}

（为便于阅读，SSTable 结构里补一个 raw []byte 字段缓存整文件内容。）

要点串联：Bloom Filter 先挡一道 → 稀疏索引二分定位块 → 块内线性扫描。真实引擎这里会加 block cache、块级压缩（Snappy/Zstd）、mmap，但骨架就是这样。

4.5 组装引擎：DB、Compaction、恢复

package minilsm

import (
	"fmt"
	"os"
	"path/filepath"
	"sort"
	"sync"
)

const memTableThreshold = 4 * 1024 * 1024 // 4MB flush 阈值
const l0CompactionTrigger = 4             // L0 文件数达到 4 触发合并

type DB struct {
	mu        sync.RWMutex
	dir       string
	mem       *SkipList
	imm       *SkipList // 正在 flush 的 immutable memtable
	wal       *WAL
	levels    [][]*SSTable // levels[0] = L0, ...
	seq       int          // SSTable 文件序号
}

func Open(dir string) (*DB, error) {
	os.MkdirAll(dir, 0755)
	db := &DB{dir: dir, mem: NewSkipList(), levels: make([][]*SSTable, 7)}
	// 恢复：重放 WAL
	walPath := filepath.Join(dir, "wal.log")
	if err := RecoverWAL(walPath, db.mem); err != nil {
		return nil, err
	}
	wal, err := OpenWAL(walPath)
	if err != nil {
		return nil, err
	}
	db.wal = wal
	// 生产环境这里还要加载已有 SSTable 的 MANIFEST，本示例略
	return db, nil
}

func (db *DB) Put(key, val []byte) error {
	db.mu.Lock()
	defer db.mu.Unlock()
	if err := db.wal.Append(key, val, false); err != nil {
		return err
	}
	db.mem.Put(key, val, false)
	return db.maybeFlush()
}

func (db *DB) Delete(key []byte) error {
	db.mu.Lock()
	defer db.mu.Unlock()
	if err := db.wal.Append(key, nil, true); err != nil {
		return err
	}
	db.mem.Put(key, nil, true) // 写 tombstone
	return db.maybeFlush()
}

func (db *DB) Get(key []byte) ([]byte, bool) {
	db.mu.RLock()
	defer db.mu.RUnlock()
	// 1. active memtable
	if v, del, ok := db.mem.Get(key); ok {
		return v, ok && !del
	}
	// 2. immutable memtable
	if db.imm != nil {
		if v, del, ok := db.imm.Get(key); ok {
			return v, ok && !del
		}
	}
	// 3. L0（新→旧）
	for i := len(db.levels[0]) - 1; i >= 0; i-- {
		if v, del, ok := db.levels[0][i].Get(key); ok {
			return v, !del
		}
	}
	// 4. L1..Ln（每层有序，理论上二分定位文件，这里简化线性）
	for lvl := 1; lvl < len(db.levels); lvl++ {
		for _, sst := range db.levels[lvl] {
			if v, del, ok := sst.Get(key); ok {
				return v, !del
			}
		}
	}
	return nil, false
}

func (db *DB) maybeFlush() error {
	if db.mem.Size() < memTableThreshold {
		return nil
	}
	// 冻结当前 memtable
	db.imm = db.mem
	db.mem = NewSkipList()
	// 同步 flush（生产是后台线程异步）
	return db.flushImm()
}

func (db *DB) flushImm() error {
	var entries []kvEntry
	db.imm.Scan(func(k, v []byte, del bool) {
		entries = append(entries, kvEntry{key: k, val: v, deleted: del})
	})
	path := filepath.Join(db.dir, fmt.Sprintf("sst-%06d.db", db.seq))
	db.seq++
	if err := WriteSSTable(path, entries); err != nil {
		return err
	}
	sst, err := OpenSSTable(path)
	if err != nil {
		return err
	}
	db.levels[0] = append(db.levels[0], sst)
	db.imm = nil
	// flush 完成，WAL 可以截断（这里简化：新建 WAL）
	// 检查是否要 compaction
	return db.maybeCompact()
}

// 简化版 Leveled Compaction：L0 满了就把 L0 全部 + L1 归并写到 L1
func (db *DB) maybeCompact() error {
	if len(db.levels[0]) < l0CompactionTrigger {
		return nil
	}
	// 收集 L0 全部 + L1 全部（简化，真实只挑 key 范围重叠的）
	var inputs []*SSTable
	inputs = append(inputs, db.levels[0]...)
	inputs = append(inputs, db.levels[1]...)

	merged := kWayMerge(inputs) // 多路归并 + 去重（保留最新）+ 丢弃 tombstone
	path := filepath.Join(db.dir, fmt.Sprintf("sst-%06d.db", db.seq))
	db.seq++
	if err := WriteSSTable(path, merged); err != nil {
		return err
	}
	newSST, _ := OpenSSTable(path)
	// 原子替换：清空 L0，L1 变为新文件
	db.levels[0] = nil
	db.levels[1] = []*SSTable{newSST}
	return nil
}

// 多路归并：inputs 按"新→旧"顺序，同 key 取第一次出现（最新），并丢弃 tombstone
func kWayMerge(inputs []*SSTable) []kvEntry {
	seen := map[string]bool{}
	var all []kvEntry
	// inputs 逆序遍历以保证新数据优先（示例简化，真实用堆做归并）
	for i := len(inputs) - 1; i >= 0; i-- {
		inputs[i].Scan(func(k, v []byte, del bool) {
			ks := string(k)
			if seen[ks] {
				return
			}
			seen[ks] = true
			if del {
				return // tombstone：合并到最底层时可安全丢弃
			}
			all = append(all, kvEntry{key: append([]byte{}, k...), val: append([]byte{}, v...)})
		})
	}
	sort.Slice(all, func(i, j int) bool {
		return bytes.Compare(all[i].key, all[j].key) < 0
	})
	return all
}

需要给 SSTable 补一个 Scan 方法遍历所有 entry（实现和 Get 里的块扫描类似，此处省略）。

麻雀虽小，五脏俱全。你已经有了：WAL 保证持久性、跳表 MemTable、SSTable 持久化、Bloom Filter 加速点查、以及一个 L0→L1 的 Compaction。把 memTableThreshold 调大、加上后台 goroutine 做异步 flush/compaction、加上 MANIFEST 记录文件元信息，它就越来越像一个真的 LevelDB 了。

关于 tombstone 的坑：上面 kWayMerge 在合并时直接丢弃了 tombstone。但注意——只有当合并的目标是最底层（保证没有更低层还存着这个 key 的旧值）时，才能安全丢弃 tombstone。否则删除会"复活"。这是 LSM 实现里最容易出 bug 的地方之一，真实引擎会跟踪 key 的最低层次来判断。

五、性能优化：把引擎榨干的工程手段

理解了原理，下面是把 LSM 引擎在生产里调到极致的清单（以 RocksDB 术语为主，通用）。

5.1 Bloom Filter 调参

• bits_per_key：默认 10（FPR≈1%）。读多、内存充裕可以调到 15~20，把假阳性再压一个数量级。
• 前缀 Bloom（Prefix Bloom）：如果你的查询模式是"按前缀范围扫"（比如 user:123:*），可以对 key 前缀建 Bloom，让范围查询也能跳过文件。
• Ribbon Filter：RocksDB 6.15+ 引入的新型过滤器，同样 FPR 下比 Bloom 省约 30% 空间，代价是构建稍慢。读密集场景值得开。

5.2 Block Cache 与压缩

• Block Cache（默认 LRU，可换 Clock）：缓存热点 data block，是读性能的命脉。建议设为可用内存的 1/3。RocksDB 还能把 index/filter block 也放进 block cache 统一管理（cache_index_and_filter_blocks）。
• 块压缩：L0~L2 常用 LZ4/Snappy（快），最底层 Ln 用 Zstd（压缩比高，因为最底层数据最多、最冷、重写最少）。这叫分层压缩策略，RocksDB 支持每层不同 compression。
• 压缩字典（Zstd dictionary）：小 value 场景开启字典训练，压缩比大幅提升。

5.3 写路径调优

• write_buffer_size（MemTable 大小）：调大减少 flush 次数、减少 L0 文件数，但增加内存和恢复时间。
• max_write_buffer_number：允许多个 immutable memtable 排队 flush，吸收写入尖峰。
• WAL 组提交（group commit）：多个并发写共享一次 fsync，大幅提升高并发写吞吐。
• bytes_per_sync：让 OS 增量刷脏页，避免一次性大 fsync 造成毛刺。

5.4 Compaction 调优

• level0_file_num_compaction_trigger：L0 文件数达到此值触发合并（默认 4）。太小则合并太频繁（写放大高），太大则读放大高、且逼近 write stall。
• max_bytes_for_level_base 和 max_bytes_for_level_multiplier（默认 10）：控制每层大小和 fan-out。
• Rate Limiter：给 Compaction 的 IO 限速，防止后台合并把前台读写的 IO 带宽吃光（生产环境必开，否则会有周期性延迟毛刺）。
• Subcompaction：把一个大 Compaction 任务切成多个并行子任务，吃满多核，缩短单次合并时间。

5.5 大 Value 与 KV 分离（WiscKey / BlobDB）

LSM 的写放大主要来自"反复搬运数据"。如果 value 很大（比如几 KB~几 MB），每次 Compaction 都搬一遍 value 极其浪费。

WiscKey 论文提出的方案：把 value 单独存到一个追加的 value log（vLog），LSM 里只存 key + value 的指针。这样 Compaction 只搬 key（小），写放大骤降。代价是范围扫描时 value 变成随机读（在 SSD 上可接受）。

RocksDB 的 BlobDB、TiKV 的 Titan、Badger（Dgraph）都是这个思路的工程实现。value 大就用它。

六、生产踩坑实录

6.1 Write Stall（写停顿）——最常见的线上事故

现象：写入 TPS 突然断崖式下跌，甚至短暂归零。

原因：LSM 有一套反压（back-pressure）机制。当以下任一情况发生，引擎会主动降速甚至阻塞前台写：

• L0 文件数超过 level0_slowdown_writes_trigger（降速）/ level0_stop_writes_trigger（停写）；
• 待合并字节数（pending compaction bytes）超阈值；
• immutable memtable 堆积、来不及 flush。

本质是写入速度 > Compaction 消化速度，引擎怕磁盘被撑爆或读放大失控，只能踩刹车。

解决：给 Compaction 更多资源（提高并行度、subcompaction）、调大 L0 触发阈值给缓冲、上更快的磁盘（NVMe）、或从源头削峰。监控一定要盯着 rocksdb.stall.micros、L0 文件数、pending compaction bytes 这几个指标。

6.2 空间放大失控

Size-Tiered 策略下，最坏空间放大能到 2 倍以上。曾经有团队用默认配置存了 1TB 有效数据，磁盘却占了 2TB+，直接爆盘。

解决：读写均衡/省空间场景用 Leveled；或设置 max_compaction_bytes、开启定期 full compaction 回收；监控 rocksdb.estimate-live-data-size vs 实际磁盘占用。

6.3 Tombstone 堆积与"删除不掉的删除"

删除只是写 tombstone，真正回收要等 Compaction 把它推到最底层。如果你大量删除但写入不多（比如按 TTL 清理），tombstone 可能长期滞留，导致：

• 范围扫描要跳过海量 tombstone，越扫越慢（Cassandra 著名的 "tombstone hell"）；
• 空间迟迟不释放。

解决：时序场景用 TWCS/FIFO 让整个文件按时间过期（根本不用逐个删）；或调优 compaction 让 tombstone 尽快下沉；Cassandra 里注意 gc_grace_seconds 和分区级 tombstone 阈值告警。

6.4 Compaction 抢占前台 IO 造成延迟毛刺

后台 Compaction 是 IO 大户。不限速的话，它一启动，前台 P99 延迟就飙升。Rate Limiter 是生产必备，把 Compaction 的 IO 控制在磁盘总带宽的一个合理比例（比如 60%），给前台留足余量。

6.5 恢复时间过长

MemTable 越大、WAL 越长，崩溃恢复重放 WAL 的时间越久。对 RTO 敏感的系统，要在"MemTable 大（写好）"和"恢复快"之间权衡，或用更频繁的 flush + checkpoint。

七、生态全景：谁在用 LSM

看这张表你会发现一个规律：几乎所有需要"高写入吞吐 + 可持久化 + 有序"的系统，最后都收敛到 LSM。B+Tree 依然统治着"读多写少 + 强事务"的 OLTP 主战场（MySQL/PostgreSQL），但只要写成为瓶颈，LSM 就是答案。

八、总结与展望

8.1 一句话总结 LSM

LSM 用"顺序写 + 后台合并"把随机写的物理代价转移到了后台，用 Bloom Filter、稀疏索引、分层和缓存把读放大压回可接受范围。它是一场关于"写放大 / 读放大 / 空间放大"不可能三角的持续博弈。

8.2 什么时候该选 LSM，什么时候不该

选 LSM：写吞吐是瓶颈、时序/日志/监控/消息、KV 存储、需要高压缩比、SSD/NVMe 上的写密集负载。

别硬上 LSM：读远多于写且要求极致点查/范围延迟、强事务 + 复杂查询的传统 OLTP、数据量小到内存放得下（那直接用内存结构或 B-Tree 更省心）。

8.3 未来往哪走

• 硬件驱动的重构：NVMe、ZNS SSD（分区命名空间）、持久内存（PMEM）、CXL 内存池正在改写 LSM 的假设。ZNS 天生适合 LSM 的"顺序写 + 整段回收"，能进一步降写放大。
• KV 分离成主流：大 value 场景 WiscKey/BlobDB/Titan 已经是标配。
• Learned Index（学习型索引）：用机器学习模型替代传统索引结构预测 key 位置，学术界（如 Google 的 Learned Index、Bourbon）已在 LSM 上验证，能进一步压缩索引、加速查找。
• B-Tree 与 LSM 的融合：像 Bε-tree（用在 TokuDB/PerconaFT）试图取二者之长；SplinterDB 则用 STBε-tree 在 NVMe 上做到读写双优。边界正在模糊。

8.4 给你的行动建议

1. 把本文的 minilsm 敲一遍、跑起来、加上后台异步 compaction 和 MANIFEST，你对 LSM 的理解会甩开 90% 只会背八股的人。
2. 生产用 RocksDB 时，别用默认配置就上线——至少配好 block cache、compression 分层、rate limiter，盯紧 write stall 指标。
3. 选型先想清楚你在"不可能三角"里最不能容忍哪个放大，再选 compaction 策略。

存储引擎没有银弹，只有权衡。而理解权衡背后的物理约束，就是从"调包侠"进阶到"能设计系统的人"的分水岭。LSM-Tree 正是这样一个把"物理约束 → 数据结构 → 工程权衡"讲得淋漓尽致的绝佳样本。

本文所有代码为教学演示，聚焦核心逻辑，生产使用请以 RocksDB/Pebble 等成熟引擎为准。如果这篇长文帮你把 LSM 从"听过"变成了"能手写"，那它的使命就达成了。