从零构建 LSM Tree 存储引擎：写入性能碾压 B+ Tree 的核心秘密

RocksDB 在 Facebook 内部每天处理超过 10 万亿次键值操作，Cassandra 支撑着 Apple 全球 10 万台服务器的数据存储，LevelDB 是 Ethereum 节点的底层引擎——这些高性能存储系统的底层都基于同一个数据结构：LSM Tree（Log-Structured Merge Tree，日志结构合并树）。如果你只了解 B+ Tree，你会困惑为什么这些系统不选择「查询更快」的 B+ Tree，而选择了 LSM Tree。答案在于一个关键权衡：LSM Tree 将随机写入转换为顺序写入，在写密集型场景下吞吐量可以达到 B+ Tree 的 10-100 倍。理解 LSM Tree 的内部机制，是理解现代存储系统的第一步。

本文将用 TypeScript 从零实现一个完整的 LSM Tree 存储引擎，包含 MemTable、SSTable、WAL（预写日志）、Compaction 策略和 Bloom Filter 优化。每个组件都有完整可运行的代码和性能对比数据。

📌 记住： LSM Tree 不是一种「更好」的数据结构，而是一种「不同取舍」的数据结构。它用读性能换取写性能，用空间换取时间。理解这个取舍，才能做出正确的技术选型。

🔧 一、LSM Tree 核心架构：为什么写入这么快

1.1 B+ Tree 的写入瓶颈

要理解 LSM Tree 的优势，先要理解 B+ Tree 的痛点。B+ Tree 是 MySQL InnoDB、PostgreSQL 等关系型数据库的默认索引结构，它的读性能优秀（O(log n)），但写入操作有一个致命问题：随机 I/O。

当你插入一条记录时，B+ Tree 需要：

1. 找到正确的叶子节点（可能在磁盘的任意位置）
2. 读取该节点到内存
3. 插入数据，可能导致节点分裂
4. 将修改后的节点写回磁盘

每一步都可能触发一次随机磁盘寻道（Random Disk Seek），而机械硬盘的随机寻道时间约为 5-10ms，SSD 约为 0.1ms。相比之下，顺序写入（Sequential Write）的速度可以达到 500MB/s 以上。一个简单的计算：

随机写入：10ms/次 × 1000 次 = 10 秒（1000 条记录）
顺序写入：1000 条 × 100 字节 = 100KB，约 0.2ms
差距：50,000 倍！

1.2 LSM Tree 的核心思想：先内存，后磁盘

LSM Tree 的核心思想极其简单：所有写入先进入内存缓冲区（MemTable），缓冲区满了再一次性刷到磁盘（SSTable）。这样就把大量的随机写入转换成了少量的顺序写入。

写入流程：
Client → Write-Ahead Log (WAL) → MemTable (内存)
                                    ↓ (满了)
                              SSTable (磁盘，不可变，顺序写入)
                                    ↓ (定期)
                              Compaction (合并 + 清理)

这个设计的精妙之处在于：

• ✅ WAL 保证数据持久化（即使进程崩溃也不丢数据）
• ✅ MemTable 提供 O(log n) 的写入（内存操作，极快）
• ✅ SSTable 是不可变文件，写入后不再修改（天然适合顺序 I/O）
• ✅ Compaction 定期合并多个 SSTable，清理已删除/过期数据

1.3 读写性能对比总览

⚡ 关键结论： LSM Tree 适合写密集型场景（日志、时序数据、消息队列），B+ Tree 适合读密集型场景（OLTP、在线交易）。没有银弹，只有合适的取舍。

🚀 二、从零实现 LSM Tree 核心组件

2.1 MemTable：基于跳表的内存数据结构

MemTable 是 LSM Tree 的写入缓冲区，需要满足两个要求：有序（方便后续生成有序的 SSTable）和高效的插入/查询。业界主流选择是跳表（Skip List）——Redis 的有序集合也使用跳表。

// memtable.ts — LSM Tree 的内存写入缓冲区（基于跳表）
interface SkipListNode {
  key: string
  value: string | null  // null 表示删除标记（tombstone）
  forward: SkipListNode[]
  span: number[]
}

class SkipList {
  private header: SkipListNode
  private level: number = 0
  private length: number = 0
  private readonly MAX_LEVEL = 32
  private readonly P = 0.25

  constructor() {
    this.header = {
      key: '',
      value: null,
      forward: new Array(this.MAX_LEVEL).fill(null),
      span: new Array(this.MAX_LEVEL).fill(0),
    }
  }

  private randomLevel(): number {
    let level = 1
    while (Math.random() < this.P && level < this.MAX_LEVEL) {
      level++
    }
    return level
  }

  insert(key: string, value: string | null): void {
    const update: SkipListNode[] = new Array(this.MAX_LEVEL)
    const rank: number[] = new Array(this.MAX_LEVEL)
    let current = this.header

    // 从最高层向下搜索插入位置
    for (let i = this.level - 1; i >= 0; i--) {
      rank[i] = i === this.level - 1 ? 0 : rank[i + 1]
      while (
        current.forward[i] &&
        current.forward[i]!.key < key
      ) {
        rank[i] += current.span[i]
        current = current.forward[i]!
      }
      update[i] = current
    }

    const newLevel = this.randomLevel()
    if (newLevel > this.level) {
      for (let i = this.level; i < newLevel; i++) {
        update[i] = this.header
        update[i].span[i] = this.length
      }
      this.level = newLevel
    }

    const newNode: SkipListNode = {
      key,
      value,
      forward: new Array(newLevel),
      span: new Array(newLevel),
    }

    for (let i = 0; i < newLevel; i++) {
      newNode.forward[i] = update[i].forward[i]
      update[i].forward[i] = newNode
    }

    this.length++
  }

  get(key: string): string | null | undefined {
    let current = this.header
    for (let i = this.level - 1; i >= 0; i--) {
      while (current.forward[i] && current.forward[i]!.key < key) {
        current = current.forward[i]!
      }
    }
    current = current.forward[0]!
    if (current && current.key === key) {
      return current.value
    }
    return undefined // 不存在
  }

  // 获取所有有序键值对（用于 flush 到 SSTable）
  *entries(): IterableIterator<[string, string | null]> {
    let current = this.header.forward[0]
    while (current) {
      yield [current.key, current.value]
      current = current.forward[0]
    }
  }

  get size(): number {
    return this.length
  }
}

class MemTable {
  private skiplist = new SkipList()
  private bytesUsed: number = 0
  private readonly maxSize: number

  constructor(maxSize: number = 4 * 1024 * 1024) { // 默认 4MB
    this.maxSize = maxSize
  }

  put(key: string, value: string): void {
    this.skiplist.insert(key, value)
    this.bytesUsed += key.length + value.length + 16 // 16 bytes overhead
  }

  delete(key: string): void {
    this.skiplist.insert(key, null) // tombstone 标记
    this.bytesUsed += key.length + 16
  }

  get(key: string): string | null | undefined {
    return this.skiplist.get(key)
  }

  isFull(): boolean {
    return this.bytesUsed >= this.maxSize
  }

  *entries(): IterableIterator<[string, string | null]> {
    yield* this.skiplist.entries()
  }
}

💡 提示： 跳表的平均时间复杂度为 O(log n)，空间复杂度为 O(n)。相比红黑树，跳表实现更简单、范围查询更高效（只需遍历最底层链表），且天然支持并发（局部锁）。

2.2 SSTable：不可变的磁盘存储格式

SSTable（Sorted String Table）是 LSM Tree 的磁盘存储格式。每个 SSTable 文件包含三部分：数据块（Data Block）、索引块（Index Block） 和 尾部元数据（Footer）。

// sstable.ts — SSTable 的写入与读取
import * as fs from 'fs'

interface SSTableMeta {
  minKey: string
  maxKey: string
  entryCount: number
  fileSize: number
  level: number
}

interface IndexEntry {
  key: string
  offset: number
  length: number
}

class SSTableWriter {
  private entries: [string, string | null][] = []
  private filePath: string

  constructor(filePath: string) {
    this.filePath = filePath
  }

  add(key: string, value: string | null): void {
    this.entries.push([key, value])
  }

  // 从 MemTable 的有序数据生成 SSTable 文件
  flush(): SSTableMeta {
    // 确保数据已排序
    this.entries.sort((a, b) => a[0].localeCompare(b[0]))

    const fd = fs.openSync(this.filePath, 'w')
    let offset = 0
    const index: IndexEntry[] = []

    // 写入数据块
    for (const [key, value] of this.entries) {
      const keyBuf = Buffer.from(key, 'utf-8')
      const valueBuf = value !== null
        ? Buffer.from(value, 'utf-8')
        : Buffer.alloc(0)

      // 格式：[keyLen:4][key][valueLen:4][value][tombstone:1]
      const recordBuf = Buffer.alloc(4 + keyBuf.length + 4 + valueBuf.length + 1)
      recordBuf.writeUInt32BE(keyBuf.length, 0)
      keyBuf.copy(recordBuf, 4)
      recordBuf.writeUInt32BE(valueBuf.length, 4 + keyBuf.length)
      valueBuf.copy(recordBuf, 8 + keyBuf.length)
      recordBuf.writeUInt8(value === null ? 1 : 0, 8 + keyBuf.length + valueBuf.length)

      index.push({ key, offset, length: recordBuf.length })
      fs.writeSync(fd, recordBuf)
      offset += recordBuf.length
    }

    // 写入索引块
    const indexOffset = offset
    const indexJson = Buffer.from(JSON.stringify(index), 'utf-8')
    fs.writeSync(fd, indexJson)
    offset += indexJson.length

    // 写入 Footer：[indexOffset:8][entryCount:4][level:1]
    const footer = Buffer.alloc(13)
    footer.writeBigUInt64BE(BigInt(indexOffset), 0)
    footer.writeUInt32BE(this.entries.length, 8)
    footer.writeUInt8(0, 12) // level 0
    fs.writeSync(fd, footer)

    fs.closeSync(fd)

    return {
      minKey: this.entries[0][0],
      maxKey: this.entries[this.entries.length - 1][0],
      entryCount: this.entries.length,
      fileSize: offset + 13,
      level: 0,
    }
  }
}

class SSTableReader {
  private index: IndexEntry[] = []
  private fd: number
  private meta: SSTableMeta

  constructor(filePath: string) {
    this.fd = fs.openSync(filePath, 'r')
    const stat = fs.statSync(filePath)

    // 读取 Footer
    const footerBuf = Buffer.alloc(13)
    fs.readSync(this.fd, footerBuf, 0, 13, stat.size - 13)

    const indexOffset = Number(footerBuf.readBigUInt64BE(0))
    const entryCount = footerBuf.readUInt32BE(8)
    const level = footerBuf.readUInt8(12)

    // 读取索引块
    const indexBuf = Buffer.alloc(stat.size - 13 - indexOffset)
    fs.readSync(this.fd, indexBuf, 0, indexBuf.length, indexOffset)
    this.index = JSON.parse(indexBuf.toString('utf-8'))

    this.meta = {
      minKey: this.index[0]?.key ?? '',
      maxKey: this.index[this.index.length - 1]?.key ?? '',
      entryCount,
      fileSize: stat.size,
      level,
    }
  }

  // 点查询：先查索引，再读数据
  get(key: string): string | null | undefined {
    // 二分查找索引
    let lo = 0, hi = this.index.length - 1
    while (lo <= hi) {
      const mid = (lo + hi) >>> 1
      const cmp = this.index[mid].key.localeCompare(key)
      if (cmp === 0) {
        return this.readEntry(mid)
      }
      if (cmp < 0) lo = mid + 1
      else hi = mid - 1
    }
    return undefined
  }

  private readEntry(indexPos: number): string | null | undefined {
    const entry = this.index[indexPos]
    const buf = Buffer.alloc(entry.length)
    fs.readSync(this.fd, buf, 0, entry.length, entry.offset)

    const keyLen = buf.readUInt32BE(0)
    const valueLen = buf.readUInt32BE(4 + keyLen)
    const tombstone = buf.readUInt8(8 + keyLen + valueLen)

    if (tombstone === 1) return null // 已删除
    return buf.slice(8 + keyLen, 8 + keyLen + valueLen).toString('utf-8')
  }

  getMetadata(): SSTableMeta {
    return this.meta
  }

  close(): void {
    fs.closeSync(this.fd)
  }
}

2.3 WAL（Write-Ahead Log）：崩溃恢复的生命线

WAL 是 LSM Tree 的持久化保障。每次写入操作首先追加到 WAL 文件，然后才写入 MemTable。如果进程崩溃，重启时可以通过重放 WAL 恢复 MemTable 中的数据。

// wal.ts — Write-Ahead Log 实现
import * as fs from 'fs'

class WriteAheadLog {
  private fd: number
  private filePath: string

  constructor(filePath: string) {
    this.filePath = filePath
    this.fd = fs.openSync(filePath, 'a') // append mode
  }

  // 追加一条记录到 WAL
  append(key: string, value: string | null): void {
    const keyBuf = Buffer.from(key, 'utf-8')
    const valueBuf = value !== null ? Buffer.from(value, 'utf-8') : Buffer.alloc(0)

    // 格式：[totalLen:4][keyLen:4][key][valueLen:4][value][tombstone:1][crc32:4]
    const totalLen = 4 + keyBuf.length + 4 + valueBuf.length + 1 + 4
    const record = Buffer.alloc(4 + totalLen)

    let pos = 0
    record.writeUInt32BE(totalLen, pos); pos += 4
    record.writeUInt32BE(keyBuf.length, pos); pos += 4
    keyBuf.copy(record, pos); pos += keyBuf.length
    record.writeUInt32BE(valueBuf.length, pos); pos += 4
    valueBuf.copy(record, pos); pos += valueBuf.length
    record.writeUInt8(value === null ? 1 : 0, pos); pos += 1

    // 简单 CRC32 校验（生产环境应使用完整 CRC32）
    const crc = this.simpleCRC(record.subarray(4, pos))
    record.writeUInt32BE(crc, pos)

    fs.writeSync(this.fd, record)
  }

  // 同步到磁盘（确保数据持久化）
  sync(): void {
    fs.fsyncSync(this.fd)
  }

  // 重放 WAL 恢复 MemTable
  *replay(): IterableIterator<[string, string | null]> {
    const fd = fs.openSync(this.filePath, 'r')
    const stat = fs.statSync(this.filePath)
    const buf = Buffer.alloc(stat.size)
    fs.readSync(fd, buf, 0, buf.length, 0)
    fs.closeSync(fd)

    let pos = 0
    while (pos < buf.length - 4) {
      const totalLen = buf.readUInt32BE(pos)
      if (pos + 4 + totalLen > buf.length) break // 不完整记录，忽略

      const keyLen = buf.readUInt32BE(pos + 4)
      const key = buf.slice(pos + 8, pos + 8 + keyLen).toString('utf-8')
      const valueLen = buf.readUInt32BE(pos + 8 + keyLen)
      const tombstone = buf.readUInt8(pos + 8 + keyLen + 4 + valueLen)
      const value = tombstone === 1
        ? null
        : buf.slice(pos + 12 + keyLen, pos + 12 + keyLen + valueLen).toString('utf-8')

      yield [key, value]
      pos += 4 + totalLen
    }
  }

  // 删除 WAL 文件（SSTable flush 成功后）
  remove(): void {
    fs.closeSync(this.fd)
    fs.unlinkSync(this.filePath)
  }

  private simpleCRC(data: Buffer): number {
    let crc = 0
    for (let i = 0; i < data.length; i++) {
      crc = (crc + data[i]) >>> 0
    }
    return crc
  }
}

⚠️ 警告： 上面的 CRC 实现是简化版本，仅用于演示。生产环境中应使用完整的 CRC32 算法（如 crc-32 npm 包）来检测数据损坏。WAL 的完整性校验是数据安全的最后一道防线。

💡 三、Compaction 策略与 Bloom Filter 优化

3.1 Compaction：LSM Tree 的「垃圾回收」

随着 SSTable 文件不断积累，读取一条数据可能需要检查多个 SSTable。Compaction（合并）的作用是：将多个 SSTable 合并为更少的、更大的 SSTable，同时清理已删除（tombstone）和被覆盖的旧版本数据。

主流的 Compaction 策略有两种：

// compaction.ts — Leveled Compaction 核心逻辑
interface CompactionResult {
  outputFiles: string[]
  freedBytes: number
}

class LeveledCompaction {
  private levels: Map<number, SSTableReader[]> = new Map()
  private readonly maxBytesPerLevel: number[]
  private readonly sizeRatio: number = 10

  constructor(baseSize: number = 10 * 1024 * 1024) {
    // 每层容量：L1=10MB, L2=100MB, L3=1GB, ...
    this.maxBytesPerLevel = Array.from({ length: 7 }, (_, i) => baseSize * Math.pow(this.sizeRatio, i))
  }

  // 选择需要 Compaction 的层
  pickCompactionLevel(): number | null {
    for (let level = 0; level < 6; level++) {
      const files = this.levels.get(level) ?? []
      const totalBytes = files.reduce((sum, f) => sum + f.getMetadata().fileSize, 0)
      if (totalBytes > this.maxBytesPerLevel[level]) {
        return level
      }
    }
    return null
  }

  // 执行 Compaction：将 level L 的一个 SSTable 与 level L+1 的重叠 SSTable 合并
  async compact(level: number, outputDir: string): Promise<CompactionResult> {
    const sourceLevel = this.levels.get(level) ?? []
    const targetLevel = this.levels.get(level + 1) ?? []

    if (sourceLevel.length === 0) {
      return { outputFiles: [], freedBytes: 0 }
    }

    // 选择最老的 SSTable 进行 compaction
    const picked = sourceLevel[0]
    const pickedMeta = picked.getMetadata()

    // 找到 target level 中与 picked 重叠的 SSTable
    const overlapping = targetLevel.filter(f => {
      const meta = f.getMetadata()
      return meta.minKey <= pickedMeta.maxKey && meta.maxKey >= pickedMeta.minKey
    })

    // 合并排序所有重叠的 entries
    const merged = new Map<string, string | null>()
    let freedBytes = pickedMeta.fileSize

    // 读取 picked SSTable 的所有 entries
    for (const [key, value] of this.iterateSSTable(picked)) {
      merged.set(key, value)
    }

    // 读取 overlapping SSTables（更新覆盖旧值）
    for (const sst of overlapping) {
      freedBytes += sst.getMetadata().fileSize
      for (const [key, value] of this.iterateSSTable(sst)) {
        if (!merged.has(key)) {
          merged.set(key, value)
        }
        // merged 中的值更新（来自更高 level），所以不覆盖
      }
    }

    // 排序并写入新的 SSTable
    const sortedEntries = [...merged.entries()].sort((a, b) => a[0].localeCompare(b[0]))
    const outputFiles: string[] = []
    const maxEntriesPerFile = 10000

    for (let i = 0; i < sortedEntries.length; i += maxEntriesPerFile) {
      const chunk = sortedEntries.slice(i, i + maxEntriesPerFile)
      const filePath = `${outputDir}/L${level + 1}_${Date.now()}_${i}.sst`
      const writer = new SSTableWriter(filePath)

      for (const [key, value] of chunk) {
        if (value !== null) { // 跳过 tombstone（如果是最后一层）
          writer.add(key, value)
        }
      }

      writer.flush()
      outputFiles.push(filePath)
    }

    return { outputFiles, freedBytes }
  }

  // 简化的 SSTable 遍历（实际需要实现迭代器）
  private *iterateSSTable(sst: SSTableReader): IterableIterator<[string, string | null]> {
    // 生产环境中应实现 SSTable 的全量迭代器
    // 这里简化为示意
    yield* []
  }
}

3.2 Bloom Filter：用概率换时间的查询优化

LSM Tree 的读操作最坏情况下需要检查所有 SSTable。Bloom Filter（布隆过滤器） 是一种空间效率极高的概率数据结构，可以在 O(1) 时间内判断一个 key 是否一定不存在于某个 SSTable 中。

原理：使用 k 个独立的哈希函数将 key 映射到位数组（Bit Array）的 k 个位置，全部为 1 则「可能存在」，任意一个为 0 则「一定不存在」。

// bloom-filter.ts — Bloom Filter 实现
class BloomFilter {
  private bits: Uint8Array
  private size: number
  private hashCount: number

  constructor(expectedItems: number, falsePositiveRate: number = 0.01) {
    // 最优位数组大小：m = -n*ln(p) / (ln2)^2
    this.size = Math.ceil(
      (-expectedItems * Math.log(falsePositiveRate)) / (Math.LN2 ** 2)
    )
    // 最优哈希函数数量：k = (m/n) * ln2
    this.hashCount = Math.round((this.size / expectedItems) * Math.LN2)
    this.bits = new Uint8Array(Math.ceil(this.size / 8))
  }

  add(key: string): void {
    for (let i = 0; i < this.hashCount; i++) {
      const hash = this.hash(key, i)
      const byteIndex = Math.floor(hash / 8)
      const bitIndex = hash % 8
      this.bits[byteIndex] |= (1 << bitIndex)
    }
  }

  // 可能存在 → true，一定不存在 → false
  mightContain(key: string): boolean {
    for (let i = 0; i < this.hashCount; i++) {
      const hash = this.hash(key, i)
      const byteIndex = Math.floor(hash / 8)
      const bitIndex = hash % 8
      if (!(this.bits[byteIndex] & (1 << bitIndex))) {
        return false // 一定不存在
      }
    }
    return true // 可能存在
  }

  // 双重哈希模拟 k 个哈希函数
  private hash(key: string, index: number): number {
    let h1 = this.fnv1a(key)
    let h2 = this.murmur3(key)
    return Math.abs((h1 + index * h2) % this.size)
  }

  private fnv1a(str: string): number {
    let hash = 2166136261
    for (let i = 0; i < str.length; i++) {
      hash ^= str.charCodeAt(i)
      hash = (hash * 16777619) >>> 0
    }
    return hash
  }

  private murmur3(str: string): number {
    let h = 0x811c9dc5
    for (let i = 0; i < str.length; i++) {
      h ^= str.charCodeAt(i)
      h = Math.imul(h, 0x01000193)
    }
    return h >>> 0
  }
}

⚡ 关键结论： 对于 100 万个 key，使用 1% 误判率的 Bloom Filter 只需要约 1.2MB 内存（相比存储原始数据的数十 MB），却能过滤掉 99% 的无效查询。在 LSM Tree 中，每个 SSTable 都附带一个 Bloom Filter，读取时先检查 Bloom Filter，不存在则跳过，性能提升可达 10-50 倍。

3.3 完整 LSM Tree 引擎组装

将所有组件组装成一个完整的 LSM Tree 引擎：

// lsm-tree.ts — 完整的 LSM Tree 存储引擎
class LSMTree {
  private activeMemTable: MemTable
  private immutableMemTables: MemTable[] = []
  private wal: WriteAheadLog
  private levels: Map<number, { reader: SSTableReader; filter: BloomFilter }[]> = new Map()
  private dataDir: string

  constructor(dataDir: string) {
    this.dataDir = dataDir
    this.wal = new WriteAheadLog(`${dataDir}/wal.log`)
    this.activeMemTable = new MemTable(4 * 1024 * 1024) // 4MB

    // 启动时重放 WAL 恢复数据
    this.recoverFromWAL()
  }

  private recoverFromWAL(): void {
    for (const [key, value] of this.wal.replay()) {
      if (value === null) {
        this.activeMemTable.delete(key)
      } else {
        this.activeMemTable.put(key, value)
      }
    }
  }

  put(key: string, value: string): void {
    this.wal.append(key, value)
    this.activeMemTable.put(key, value)

    if (this.activeMemTable.isFull()) {
      this.flushMemTable()
    }
  }

  delete(key: string): void {
    this.wal.append(key, null)
    this.activeMemTable.delete(key)

    if (this.activeMemTable.isFull()) {
      this.flushMemTable()
    }
  }

  get(key: string): string | null | undefined {
    // 1. 先查 active MemTable
    const memResult = this.activeMemTable.get(key)
    if (memResult !== undefined) return memResult

    // 2. 再查 immutable MemTables（从新到旧）
    for (let i = this.immutableMemTables.length - 1; i >= 0; i--) {
      const result = this.immutableMemTables[i].get(key)
      if (result !== undefined) return result
    }

    // 3. 逐层查 SSTable（从 L0 到 Ln）
    for (let level = 0; level < 7; level++) {
      const files = this.levels.get(level) ?? []
      // 从新到旧遍历（L0 可能有重叠）
      for (let i = files.length - 1; i >= 0; i--) {
        const { reader, filter } = files[i]

        // Bloom Filter 快速判断
        if (!filter.mightContain(key)) continue

        const result = reader.get(key)
        if (result !== undefined) return result
      }
    }

    return undefined // 不存在
  }

  private flushMemTable(): void {
    // 将当前 MemTable 标记为 immutable
    this.immutableMemTables.push(this.activeMemTable)

    // 创建新的 active MemTable
    this.activeMemTable = new MemTable(4 * 1024 * 1024)

    // 异步 flush immutable MemTable 到 SSTable
    const immutable = this.immutableMemTables.shift()!
    const filePath = `${this.dataDir}/L0_${Date.now()}.sst`
    const writer = new SSTableWriter(filePath)
    const bloom = new BloomFilter(100000)

    for (const [key, value] of immutable.entries()) {
      writer.add(key, value)
      if (value !== null) bloom.add(key)
    }

    const meta = writer.flush()

    // 注册到 L0
    if (!this.levels.has(0)) this.levels.set(0, [])
    const reader = new SSTableReader(filePath)
    this.levels.get(0)!.push({ reader, filter: bloom })

    // 删除旧 WAL，创建新 WAL
    this.wal.remove()
    this.wal = new WriteAheadLog(`${this.dataDir}/wal.log`)
  }

  // 统计信息
  stats(): { memTableSize: number; sstableCount: number; levels: Record<number, number> } {
    const levels: Record<number, number> = {}
    let sstableCount = 0
    for (const [level, files] of this.levels) {
      levels[level] = files.length
      sstableCount += files.length
    }
    return { memTableSize: this.activeMemTable.size, sstableCount, levels }
  }
}

📊 四、性能基准测试与选型建议

4.1 读写性能对比

以下是在 Node.js 22 环境下的基准测试数据（10 万条随机键值对，每条 100 字节）：

⚠️ 警告： 以上数据基于简化实现。生产级系统（如 RocksDB）经过大量优化（Block Cache、Prefix Bloom Filter、Parallel Compaction 等），实际性能差异会有所不同。不要直接用这些数据做技术选型，应该在你的实际场景中做基准测试。

4.2 LSM Tree 适用场景决策树

你的场景适合 LSM Tree 吗？

写入量大（>10K ops/s）？
  ├─ 是 → LSM Tree ✅
  └─ 否 → 读多写少？
           ├─ 是 → B+ Tree ✅
           └─ 否 → 需要范围查询？
                    ├─ 是 → B+ Tree ✅
                    └─ 否 → LSM Tree ✅

4.3 生产环境中的 LSM Tree 系统选型

✅ 五、最佳实践与避坑指南

5.1 写放大（Write Amplification）问题

LSM Tree 的 Compaction 会导致数据被反复重写。在最坏情况下，一条数据从 L0 到 L6 可能被重写 6 次，写放大系数达到 10-30x。

• ✅ 使用 Leveled Compaction 控制空间放大
• ✅ 使用 Tiered Compaction 降低写放大（适合写密集场景）
• ❌ 避免在 Compaction 期间接受写入（可能导致 L0 堆积）
• ⚠️ 监控写放大指标，超过 20x 需要调优

5.2 空间放大（Space Amplification）问题

由于旧版本数据和 tombstone 的存在，LSM Tree 的实际磁盘占用可能是有效数据的 2-3 倍。

• ✅ 定期触发 Full Compaction 清理 tombstone
• ✅ 设置合理的 TTL（Time-To-Live）自动过期
• ✅ 最后一层（Ln）的 Compaction 可以彻底删除 tombstone
• ❌ 不要在写入时设置过长的 key（增加存储和索引开销）

5.3 读性能优化

• ✅ 为每个 SSTable 配置 Bloom Filter（必须！）
• ✅ 使用 Block Cache 缓存热点数据块
• ✅ 使用 Prefix Bloom Filter 优化前缀查询
• ✅ L0 文件数量过多时优先触发 L0→L1 Compaction
• ❌ 避免全表扫描（LSM Tree 的全表扫描性能远不如 B+ Tree）

🔚 总结

LSM Tree 是现代存储系统的基石，理解它的内部机制对于选择和优化数据库至关重要。本文通过从零实现的方式，带你深入理解了 LSM Tree 的五大核心组件：

• ✅ MemTable：基于跳表的内存有序缓冲区，实现高速写入
• ✅ SSTable：不可变的磁盘文件，支持高效二分查找
• ✅ WAL：预写日志，保证崩溃恢复
• ✅ Compaction：合并策略，控制读写放大和空间放大
• ✅ Bloom Filter：概率过滤器，将无效查询降低 99%

选型建议：

• 💰 写密集型场景（日志、时序数据、消息队列）→ LSM Tree（RocksDB/BadgerDB）
• 💰 读密集型场景（OLTP、在线交易）→ B+ Tree（InnoDB/PostgreSQL）
• 💰 嵌入式应用（CLI 工具、本地缓存）→ SQLite（WAL mode）

相关工具推荐：

• 🔧 RocksDB Tuning Guide — 生产级 LSM Tree 调优
• 🔧 LevelDB 源码 — 学习 LSM Tree 的最佳教材
• 🔧 jsjson.com JSON 格式化工具 — 处理你的 JSON 数据
• 🔧 jsjson.com 在线工具箱 — 50+ 开发者在线工具