LSM-tree Compaction 策略

Compaction 是 LSM-tree 的心脏，也是它最大的痛点。如果把 LSM-tree 比作一台引擎，那么 compaction 就是曲轴——它将无序的写入转化为有序的持久化结构，但代价是巨大的后台 I/O 开销。本文将从原理到实战，系统地剖析各种 compaction 策略的设计哲学、工程实现与调优经验。

一、为什么需要 Compaction

LSM-tree 的核心设计思想是”写入时不排序，读取时合并”。数据先写入内存中的 MemTable，满了之后 flush 成磁盘上的 SSTable（Sorted String Table）。随着写入量增大，磁盘上会堆积越来越多的 SSTable 文件，如果不做任何整理，系统将面临三重灾难：

1.1 空间膨胀

每次更新（Update）或删除（Delete）操作不会原地修改旧数据，而是追加一条新记录或一条墓碑标记（Tombstone）。旧版本的数据仍然占据磁盘空间，且永远不会被自动回收。对于写入密集型场景，磁盘使用量可能是实际有效数据量的数倍。

时间线:
  t1: PUT(k1, v1)   -- 写入 SSTable-1
  t2: PUT(k1, v2)   -- 写入 SSTable-2 (SSTable-1 中的 v1 成为垃圾)
  t3: DEL(k1)       -- 写入 SSTable-3 (tombstone, v2 也成为垃圾)

如果不做 compaction:
  磁盘上同时存在 v1, v2, tombstone 三条记录
  实际有效数据量: 0
  实际磁盘占用: 3 条记录的空间

1.2 读放大（Read Amplification）

点查（Point Lookup）时，系统需要从最新的 SSTable 开始逐个查找，直到找到目标 key 或确认不存在。如果有 N 个 SSTable，最坏情况下需要查找 N 次。范围查询（Range Scan）更加痛苦——需要对所有包含目标范围的 SSTable 做归并排序。

读放大公式（无 Bloom Filter 时）:

  点查: O(N)       -- N 为 SSTable 数量
  范围: O(N * B)   -- B 为每个 SSTable 中落入范围的 block 数

Bloom Filter 可以显著降低点查的读放大，但对范围查询帮助有限。而且 Bloom Filter 本身也消耗内存——每个 key 大约需要 10 bits 才能将误判率压到 1% 以下。

1.3 墓碑泄漏（Tombstone Leak）

墓碑标记不能被立即删除，因为它需要”遮蔽”更老的 SSTable 中同一个 key 的旧值。只有当墓碑与它所遮蔽的所有旧记录在同一次 compaction 中被合并处理后，才能安全移除。如果 compaction 策略不当，墓碑可能长期驻留在系统中，导致：

• 范围查询变慢（需要跳过大量墓碑）
• 磁盘空间无法回收
• 在 Cassandra 等分布式系统中，墓碑积累甚至会导致读超时

经典案例: Cassandra 的 gc_grace_seconds

  默认值: 864000 (10天)
  含义: tombstone 至少保留 10 天才允许被 compaction 清除
  原因: 需要给离线节点足够时间同步删除操作
  副作用: 大量删除后, 10 天内读性能持续恶化

1.4 三种放大的权衡

LSM-tree 的设计本质上是在三种放大之间做权衡：

不存在同时最优化三者的策略——这是 LSM-tree compaction 问题的根本矛盾，也是本文讨论的核心主题。

二、Size-Tiered Compaction（STCS）

Size-Tiered Compaction 是最古老也是最直观的策略，被 Apache Cassandra 和早期 HBase 所采用。

2.1 基本思想

将磁盘上的 SSTable 按大小分组（tier），同一组中的 SSTable 大小相近。当某一组中的 SSTable 数量达到阈值 T（通常 T=4），就把它们合并成一个更大的 SSTable，放入下一组。

STCS 工作流程:

  Tier 0:  [4MB] [4MB] [4MB] [4MB]   -- 4 个相似大小
                    |
                    v  合并
  Tier 1:  [16MB] [16MB] [16MB] [16MB]
                    |
                    v  合并
  Tier 2:  [64MB] [64MB]
                    |
                    v  合并
  Tier 3:  [256MB]

  size_ratio = T = 4
  每次合并: T 个 SSTable -> 1 个 SSTable

2.2 写放大分析

STCS 的写放大是所有经典策略中最低的。每条数据在每个 tier 最多被合并一次，总共经过 L 个 tier：

写放大 = T * L

其中:
  T = size ratio (每个 tier 最多 T 个 SSTable)
  L = tier 数量 = log_T(N/B)
  N = 总数据量
  B = MemTable 大小

例: T=4, 数据量 1TB, MemTable 64MB
  L = log_4(1TB / 64MB) = log_4(16384) = 7
  写放大 = 4 * 7 = 28

对比 Leveled:
  写放大 = T * L = 10 * 7 = 70

但是更精确地说，STCS 的写放大只有 O(L)，因为每个 tier 内的合并只是把 T 个文件合成 1 个，每条数据只被重写一次。而 Leveled 在每一层都可能和该层已有数据做合并，所以是 O(T * L)。

2.3 读放大分析

STCS 的致命弱点在于读放大。每个 tier 内的 SSTable 之间 key 范围可能重叠，最坏情况读放大为 T*L。Bloom Filter 可以帮助点查排除不匹配的文件，但范围查询无法受益。

2.4 空间放大

STCS 在合并期间需要同时存在输入文件和输出文件，最坏空间放大接近 2x。

2.5 适用场景

STCS 适合写入远多于读取的场景：

• 日志收集系统（写入后很少读取）
• 时间序列数据的批量导入
• 对写入延迟极度敏感的系统

// Cassandra 中配置 STCS
CREATE TABLE logs (
    id UUID PRIMARY KEY,
    ts timestamp,
    message text
) WITH compaction = {
    'class': 'SizeTieredCompactionStrategy',
    'min_threshold': 4,
    'max_threshold': 32,
    'min_sstable_size': 52428800  // 50MB
};

三、Leveled Compaction（LCS）

Leveled Compaction 是 RocksDB 的默认策略，也是工业界使用最广泛的方案。它由 LevelDB 首创，后来被 RocksDB、Cassandra、ScyllaDB 等广泛采用。

3.1 核心不变量

LCS 的设计围绕一个核心不变量：除 L0 外，每一层的 SSTable 之间 key 范围不重叠。

Level 结构:

  L0: [SST-a] [SST-b] [SST-c]     -- 允许重叠 (直接 flush)
  L1: [a-d][e-h][i-l][m-p]        -- 不重叠, 有序
  L2: [a-b][c-d][e-f]...[y-z]     -- 不重叠, 有序, 容量 = L1 * T
  L3: [a-a][a-b]...[z-z]          -- 不重叠, 有序, 容量 = L2 * T

  容量关系: size(Li+1) = T * size(Li)
  默认 T = 10

  L1: 256MB
  L2: 2.56GB
  L3: 25.6GB
  L4: 256GB
  L5: 2.56TB

3.2 合并过程

当某一层超过容量限制时，RocksDB 会选择一个 SSTable 文件，将它与下一层中 key 范围重叠的所有 SSTable 进行合并排序，生成新的 SSTable 文件写入下一层：

L1 -> L2 合并示例:

  选中 L1 的 [e-h]
  找到 L2 中 key 范围与 [e-h] 重叠的文件: [e-f], [g-h]

  合并: [e-h] + [e-f] + [g-h]
  输出: [e-f'], [g-h']  (新文件写入 L2)
  删除: L1 的 [e-h], L2 的旧 [e-f] 和 [g-h]

  L1 文件数减少 1, L2 文件数不变或微增

3.3 写放大分析

LCS 的写放大是其最大缺陷。在最坏情况下：

L(i) -> L(i+1) 合并:
  选中 L(i) 的 1 个 SSTable (大小 S)
  可能与 L(i+1) 中最多 T 个 SSTable 重叠
  读取: S + T*S = (T+1)*S
  写入: (T+1)*S

  每层写放大: T + 1 ≈ T

  总写放大 = T * L
  其中 L = 层数 ≈ log_T(N / size(L1))

例: T=10, 数据量 1TB, L1=256MB
  L = log_10(1TB / 256MB) ≈ 4
  总写放大 = 10 * 4 = 40

在实际工作负载中，如果写入的 key 分布均匀，平均写放大会低于最坏情况。RocksDB 的经验值通常在 10-30 之间。

3.4 读放大分析

LCS 的读放大极低——这是它最大的优势：

点查:
  L0: 最多检查 L0 中所有文件 (通常 < 4 个)
  L1-Ln: 每层最多检查 1 个文件 (因为不重叠)
  总计: L0_count + L - 1

  配合 Bloom Filter:
  实际读取 ≈ 1 次磁盘 I/O（大多数情况）

范围查询:
  每层最多一个文件的起始边界需要 seek
  后续顺序读取, 效率很高

3.5 RocksDB 中的 LCS 配置

// RocksDB LCS 核心配置
Options options;
options.compaction_style = kCompactionStyleLevel;

// 层级配置
options.num_levels = 7;                    // 最大层数
options.level0_file_num_compaction_trigger = 4;  // L0 文件数触发 compaction
options.max_bytes_for_level_base = 256 * 1048576; // L1 容量 = 256MB
options.max_bytes_for_level_multiplier = 10;       // T = 10
options.target_file_size_base = 64 * 1048576;      // 单个 SST 文件 = 64MB
options.target_file_size_multiplier = 1;

// Write buffer (MemTable) 配置
options.write_buffer_size = 64 * 1048576;          // 64MB
options.max_write_buffer_number = 3;
options.min_write_buffer_number_to_merge = 1;

// Compaction 并发
options.max_background_compactions = 4;
options.max_background_flushes = 2;

3.6 Level 0 的特殊性

L0 是唯一允许 key 范围重叠的层，直接接收 MemTable flush 产物。这意味着 L0 到 L1 的合并可能需要一次性合并所有 L0 文件（因为它们互相重叠），加上 L1 中对应范围的文件——单次 compaction 的 I/O 量可能非常大，这是 write stall 的常见原因之一。

四、FIFO Compaction

FIFO（First-In-First-Out）Compaction 是最简单的策略，专为时间序列数据设计。

4.1 工作原理

FIFO Compaction 不做任何合并操作。它只是按时间顺序删除最老的 SSTable，相当于自动 TTL（Time-To-Live）：

FIFO 工作流程:

  [SST-1: 7天前] [SST-2: 5天前] [SST-3: 3天前] [SST-4: 1天前] [SST-5: 刚写入]

  当总数据量超过 max_table_files_size:
  或者 SST-1 的最老记录超过 ttl:
    -> 直接删除 SST-1
    -> 不做合并, 不读取内容

  写放大: 1 (没有后台重写)
  空间放大: 取决于 TTL 和写入速率

4.2 配置示例

// RocksDB FIFO Compaction
Options options;
options.compaction_style = kCompactionStyleFIFO;

CompactionOptionsFIFO fifo_options;
fifo_options.max_table_files_size = 1024 * 1048576;  // 总大小上限 1GB
fifo_options.ttl = 86400;  // TTL = 24 小时

options.compaction_options_fifo = fifo_options;

4.3 适用与限制

适用场景： - 监控指标存储（Prometheus 风格） - IoT 传感器数据 - 缓存层（不需要持久化旧数据）

限制： - 不支持更新操作（旧值永远不会被覆盖合并） - 不支持删除操作（墓碑无法被清理） - 读放大可能很高（文件数量不断增长直到被 TTL 淘汰）

五、Universal Compaction

Universal Compaction 是 RocksDB 提供的一种混合策略，试图在 STCS 和 LCS 之间找到平衡点。

5.1 设计动机

STCS 写放大低但读放大高，LCS 读放大低但写放大高。能否设计一种策略，根据当前系统负载动态选择合并方式？Universal Compaction 正是这样的尝试。

5.2 合并触发条件

Universal Compaction 维护一个按时间排序的 SSTable 列表（最新的在前），并使用多种条件触发合并：

SSTable 排列 (按新旧顺序):
  R1(最新), R2, R3, ..., Rn(最旧)

触发条件:

1. Space Amplification 条件:
   所有文件总大小 / 最大文件大小 > max_size_amplification_percent / 100
   -> 触发全量合并 (类似 major compaction)

2. Size Ratio 条件:
   从 R1 开始, 找到最小的 i, 使得:
   size(R1) + ... + size(Ri) < size(Ri+1) * (100 + size_ratio) / 100
   -> 将 R1 到 Ri+1 合并

3. 文件数条件:
   sorted_run 数量 > level0_file_num_compaction_trigger
   -> 合并最老的几个 sorted run

5.3 配置参数

// RocksDB Universal Compaction
Options options;
options.compaction_style = kCompactionStyleUniversal;

CompactionOptionsUniversal univ_options;
univ_options.size_ratio = 1;                // 默认 1%
univ_options.min_merge_width = 2;           // 最少合并 2 个 run
univ_options.max_merge_width = UINT_MAX;    // 不限制最大合并数
univ_options.max_size_amplification_percent = 200;  // 空间放大上限 200%
univ_options.compression_size_percent = -1;

options.compaction_options_universal = univ_options;

5.4 与 STCS 的比较

Universal Compaction 可以看作 STCS 的增强版本：

六、Dostoevsky: Lazy Leveling 与 Fluid LSM-tree

2018 年，哈佛大学的 Niv Dayan 和 Stratos Idreos 发表了 Dostoevsky 论文，对 LSM-tree compaction 策略进行了深入的理论分析，并提出了两个重要概念：Lazy Leveling 和 Fluid LSM-tree。

6.1 统一分析框架

Dostoevsky 的核心贡献是建立了一个统一的数学框架来分析所有 compaction 策略的代价：

记号定义:
  N = 总条目数
  B = 磁盘页大小 (条目数)
  P = 内存中的 Bloom Filter 总 bits
  T = size ratio
  L = 层数 = ceil(log_T(N / B))
  p_i = 第 i 层 Bloom Filter 的 false positive rate

代价公式:

  写放大 W:
    Tiering:   O(T/T * L) = O(L)
    Leveling:  O(T * L)

  点查 (zero-result) V:
    Tiering:   O(L * e^(-P/(N*ln2^2)))  -- 受 Bloom Filter 精度影响
    Leveling:  O(e^(-P/(N*ln2^2)))

  短范围查询 Q (返回 s 条结果):
    Tiering:   O(T * L)        -- 每层 T 个 run 都可能贡献结果
    Leveling:  O(L)            -- 每层 1 个 run

  空间放大 A:
    Tiering:   O(T)
    Leveling:  O(1/T)

6.2 Lazy Leveling

Lazy Leveling 是 Tiering 和 Leveling 的混合：最大层使用 Leveling（不重叠），其他层使用 Tiering（允许重叠）。

Lazy Leveling 结构:

  L1: [SST] [SST] [SST]          -- Tiering (允许重叠)
  L2: [SST] [SST] [SST] [SST]    -- Tiering (允许重叠)
  L3: [a-d][e-h][i-l][m-p][q-z]  -- Leveling (不重叠)

代价:
  写放大: O(T * 1 + 1 * (L-1)) = O(T + L)
  点查:   介于 Tiering 和 Leveling 之间
  范围:   O(T * (L-1) + 1)

关键洞察：由于最大层存储了绝大部分数据（约 (T-1)/T 的比例），对最大层使用 Leveling 可以大幅降低空间放大，同时对其他层使用 Tiering 可以降低写放大。

6.3 Monkey: 最优 Bloom Filter 分配

Monkey（也来自同一研究团队）回答了一个关键问题：给定固定的内存预算 P bits，如何为每一层的 Bloom Filter 分配 bits 以最小化总体点查代价？

传统做法: 每层分配相同的 bits-per-key
  每层 false positive rate 相同

Monkey 最优分配:
  最大层分配最多 bits (因为最大层的 false positive 代价最高)
  小层分配较少 bits

具体来说:
  p_i = p_L * T^(L-i)

  即: 越小的层, false positive rate 越高 (分配越少 bits)
  因为小层即使 false positive, 也只是多一次小文件的读取
  而大层的 false positive 意味着读取大文件中的一个 block

效果:
  在相同内存预算下, 点查代价降低一个数量级

6.4 Fluid LSM-tree

Fluid LSM-tree 允许每一层独立选择 Tiering 或 Leveling，通过参数 Z（最大层策略）和 K（其他层策略）统一描述所有变体：Z=1,K=1 即 LCS；Z=T-1,K=T-1 即 STCS；Z=1,K=T-1 即 Lazy Leveling。通用代价公式为 W=O(T/KL)、V=O(LKp+p)、Q=O(K(L-1)+Z)，给定工作负载即可数学优化找到最优参数组合。

七、Compaction 调度与资源管理

Compaction 调度是工程实现中最复杂的部分之一。一个好的调度器需要在”尽快整理数据”和”不影响前台请求”之间找到平衡。

7.1 优先级队列

RocksDB 使用优先级队列来管理 compaction 任务：

优先级排序（从高到低）:

1. L0 -> L1 compaction (最高优先级)
   原因: L0 文件过多会直接导致 write stall
   条件: L0 文件数 >= level0_file_num_compaction_trigger

2. BottomMost Level compaction
   原因: 清理墓碑和过期数据, 回收空间
   条件: 最底层存在可清理的数据

3. Score-based compaction
   原因: 某一层的实际大小超过目标大小
   score = actual_size / target_size
   选择 score 最高的层优先合并

4. Manual compaction
   原因: 用户主动触发 (CompactRange API)
   优先级可配置

7.2 文件选择策略

当确定要对某一层做 compaction 时，选择哪个文件也是一门学问：

RocksDB 文件选择策略:

1. kByCompensatedSize (默认)
   优先选择"补偿后大小"最大的文件
   compensated_size = file_size + 被删除/覆盖的条目数 * 平均条目大小
   目的: 优先清理垃圾数据多的文件

2. kOldestLargestSeqFirst
   优先选择 sequence number 最老的文件
   目的: 尽快推进 snapshot 清理, 释放旧版本数据

3. kOldestSmallestSeqFirst
   优先选择 sequence number 范围最小的文件
   目的: 最小化单次 compaction 涉及的 key 范围

4. kMinOverlappingRatio
   优先选择与下一层重叠比例最小的文件
   overlap_ratio = 与 L(i+1) 重叠的文件总大小 / 当前文件大小
   目的: 最小化单次 compaction 的 I/O 量

7.3 Rate Limiting

Compaction 的 I/O 如果不加限制，会严重影响前台读写性能：

// RocksDB Rate Limiter: 限制 compaction + flush 总 I/O 带宽
options.rate_limiter.reset(
    NewGenericRateLimiter(
        100 * 1048576,   // rate_bytes_per_sec = 100MB/s
        100 * 1000,      // refill_period_us = 100ms
        10,              // fairness (flush vs compaction)
        RateLimiter::Mode::kWritesOnly
    )
);

经验法则：compaction I/O 带宽不超过磁盘总带宽的 50%；如果使用 SSD，compaction 写带宽建议不超过 SSD 标称写带宽的 30%（SSD 内部写放大会叠加 compaction 写放大）。

八、Write Stall: 原因、检测与缓解

Write Stall 是 LSM-tree 在生产环境中最令人头疼的问题。当后台 compaction 跟不上前台写入速度时，系统被迫降低或停止接受写入请求。

8.1 触发条件

RocksDB 中 Write Stall 有三个触发条件：

条件 1: L0 文件数过多
  level0_slowdown_writes_trigger (默认 20)
    -> 写入限速 (delayed)
  level0_stop_writes_trigger (默认 36)
    -> 写入完全停止 (stopped)

条件 2: Pending Compaction 字节数过多
  soft_pending_compaction_bytes_limit (默认 64GB)
    -> 写入限速
  hard_pending_compaction_bytes_limit (默认 256GB)
    -> 写入完全停止

条件 3: MemTable 数量过多
  max_write_buffer_number (默认 3)
    -> 当所有 MemTable 都满且无法 flush 时, 写入停止
    -> 通常是因为 L0 compaction 阻塞了 flush

8.2 检测方法

// 监听 EventListener 检测 write stall
class StallListener : public EventListener {
public:
    void OnStallConditionsChanged(const WriteStallInfo& info) override {
        if (info.condition.cur != WriteStallCondition::kNormal) {
            LOG_WARN("Write stall: cf={}, cond={}", info.cf_name, ToString(info.condition.cur));
        }
    }
};
options.listeners.push_back(std::make_shared<StallListener>());

// 也可通过 Property 查询: rocksdb.is-write-stopped / rocksdb.actual-delayed-write-rate
// 或在 LOG 中搜索 "Stalling writes" / "Stopping writes"

8.3 缓解策略

策略 1: 增加 Compaction 并发
  max_background_compactions = CPU / 2, max_background_flushes = 2-4

策略 2: Sub-compaction
  max_subcompactions = 4  -- 拆分大 compaction 为并行子任务

策略 3: 动态 level 大小
  level_compaction_dynamic_level_bytes = true

策略 4: 放宽 L0 限制 (慎用, 读性能会下降)
  level0_file_num_compaction_trigger = 8
  level0_slowdown_writes_trigger = 40
  level0_stop_writes_trigger = 56

策略 5: Direct I/O 避免 Page Cache 污染
  use_direct_io_for_flush_and_compaction = true

8.4 Write Stall 的链式反应

典型连锁故障: 突发写入 -> MemTable 频繁 flush -> L0 堆积 -> L0->L1 合并变慢
  -> slowdown 限速 -> flush 被阻塞 -> MemTable 满 -> 写入完全停止

预防: 应用层限流 + 预留 compaction 带宽 + 监控 L0 文件数 + 自动扩展合并线程

九、Go 实现: Leveled Compaction 模拟器

下面是一个完整的 Go 语言 Leveled Compaction 模拟器实现。它模拟了 MemTable flush、level-by-level 合并、以及基本的统计收集。

package main

import (
    "fmt"
    "math/rand"
    "sort"
    "strings"
)

// SSTable 表示一个 Sorted String Table 文件
type SSTable struct {
    ID       int
    Level    int
    MinKey   int
    MaxKey   int
    Size     int // 字节数
    Entries  int
    SeqNum   int64
    Tombstones int
}

// LSMTree 表示整个 LSM-tree 结构
type LSMTree struct {
    levels        [][]SSTable
    maxLevels     int
    sizeRatio     int     // T, 默认 10
    l1TargetSize  int     // L1 目标大小 (bytes)
    sstSize       int     // 单个 SSTable 目标大小
    nextID        int
    nextSeq       int64

    // 统计
    bytesWritten  int64
    bytesRead     int64
    compactions   int
    userWritten   int64
}

// NewLSMTree 创建新的 LSM-tree
func NewLSMTree(maxLevels, sizeRatio, l1Target, sstSize int) *LSMTree {
    tree := &LSMTree{
        levels:       make([][]SSTable, maxLevels),
        maxLevels:    maxLevels,
        sizeRatio:    sizeRatio,
        l1TargetSize: l1Target,
        sstSize:      sstSize,
        nextID:       1,
        nextSeq:      1,
    }
    for i := range tree.levels {
        tree.levels[i] = make([]SSTable, 0)
    }
    return tree
}

// Flush 模拟 MemTable flush 到 L0
func (t *LSMTree) Flush(minKey, maxKey, entries int) {
    sst := SSTable{
        ID:      t.nextID,
        Level:   0,
        MinKey:  minKey,
        MaxKey:  maxKey,
        Size:    entries * 100, // 假设每条 100 bytes
        Entries: entries,
        SeqNum:  t.nextSeq,
    }
    t.nextID++
    t.nextSeq++
    t.levels[0] = append(t.levels[0], sst)
    t.userWritten += int64(sst.Size)
    t.bytesWritten += int64(sst.Size) // flush 写入

    // 检查是否需要触发 compaction
    if len(t.levels[0]) >= 4 {
        t.compactLevel(0)
    }
}

// targetSize 返回第 level 层的目标大小
func (t *LSMTree) targetSize(level int) int {
    if level == 0 {
        return 0 // L0 没有大小限制，靠文件数触发
    }
    size := t.l1TargetSize
    for i := 1; i < level; i++ {
        size *= t.sizeRatio
    }
    return size
}

// levelSize 返回某层的实际大小
func (t *LSMTree) levelSize(level int) int {
    total := 0
    for _, sst := range t.levels[level] {
        total += sst.Size
    }
    return total
}

// compactLevel 对指定层执行 compaction
func (t *LSMTree) compactLevel(level int) {
    if level >= t.maxLevels-1 {
        return
    }

    nextLevel := level + 1
    t.compactions++

    if level == 0 {
        // L0 -> L1: 合并所有 L0 文件
        t.compactL0ToL1()
    } else {
        // L(i) -> L(i+1): 选择一个文件合并
        t.compactLevelToLevel(level, nextLevel)
    }

    // 级联检查: 如果下一层也超限, 继续合并
    if nextLevel < t.maxLevels-1 {
        target := t.targetSize(nextLevel)
        actual := t.levelSize(nextLevel)
        if actual > target {
            t.compactLevel(nextLevel)
        }
    }
}

// compactL0ToL1 将所有 L0 文件合并到 L1
func (t *LSMTree) compactL0ToL1() {
    if len(t.levels[0]) == 0 {
        return
    }

    // 找到 L0 所有文件的 key 范围
    minKey, maxKey := t.levels[0][0].MinKey, t.levels[0][0].MaxKey
    totalSize, totalEntries := 0, 0
    for _, sst := range t.levels[0] {
        if sst.MinKey < minKey { minKey = sst.MinKey }
        if sst.MaxKey > maxKey { maxKey = sst.MaxKey }
        totalSize += sst.Size
        totalEntries += sst.Entries
        t.bytesRead += int64(sst.Size)
    }

    // 找到 L1 中重叠的文件
    var overlapping []int
    for i, sst := range t.levels[1] {
        if sst.MinKey <= maxKey && sst.MaxKey >= minKey {
            overlapping = append(overlapping, i)
            totalSize += sst.Size
            totalEntries += sst.Entries
            t.bytesRead += int64(sst.Size)
        }
    }

    // 移除 L1 中重叠的文件（从后往前删）
    sort.Sort(sort.Reverse(sort.IntSlice(overlapping)))
    for _, idx := range overlapping {
        t.levels[1] = append(t.levels[1][:idx], t.levels[1][idx+1:]...)
    }
    t.levels[0] = t.levels[0][:0] // 清空 L0

    // 生成新的 L1 文件
    t.splitAndWrite(1, minKey, maxKey, totalSize, totalEntries)
}

// compactLevelToLevel 从 level 选一个文件合并到 nextLevel
func (t *LSMTree) compactLevelToLevel(level, nextLevel int) {
    if len(t.levels[level]) == 0 {
        return
    }

    // 选择与下一层重叠最小的文件（kMinOverlappingRatio 策略）
    bestIdx := 0
    bestOverlap := int64(1 << 62)
    for i, sst := range t.levels[level] {
        overlap := int64(0)
        for _, nsst := range t.levels[nextLevel] {
            if nsst.MinKey <= sst.MaxKey && nsst.MaxKey >= sst.MinKey {
                overlap += int64(nsst.Size)
            }
        }
        if overlap < bestOverlap {
            bestOverlap = overlap
            bestIdx = i
        }
    }

    picked := t.levels[level][bestIdx]
    t.bytesRead += int64(picked.Size)

    // 收集下一层重叠文件并统计
    var overlapping []int
    totalSize, totalEntries := picked.Size, picked.Entries
    mergedMin, mergedMax := picked.MinKey, picked.MaxKey
    for i, sst := range t.levels[nextLevel] {
        if sst.MinKey <= picked.MaxKey && sst.MaxKey >= picked.MinKey {
            overlapping = append(overlapping, i)
            totalSize += sst.Size
            totalEntries += sst.Entries
            t.bytesRead += int64(sst.Size)
            if sst.MinKey < mergedMin { mergedMin = sst.MinKey }
            if sst.MaxKey > mergedMax { mergedMax = sst.MaxKey }
        }
    }

    // 移除参与合并的文件（从后往前删）
    sort.Sort(sort.Reverse(sort.IntSlice(overlapping)))
    for _, idx := range overlapping {
        t.levels[nextLevel] = append(t.levels[nextLevel][:idx], t.levels[nextLevel][idx+1:]...)
    }
    t.levels[level] = append(t.levels[level][:bestIdx], t.levels[level][bestIdx+1:]...)

    // 生成新文件写入下一层
    t.splitAndWrite(nextLevel, mergedMin, mergedMax, totalSize, totalEntries)
}

// splitAndWrite 将合并结果按 sstSize 切分写入目标层
func (t *LSMTree) splitAndWrite(level, minKey, maxKey, totalSize, totalEntries int) {
    numFiles := max(1, totalSize/t.sstSize)
    keysPerFile := max(1, (maxKey-minKey+1)/numFiles)

    for i := 0; i < numFiles; i++ {
        fMin := minKey + i*keysPerFile
        fMax := fMin + keysPerFile - 1
        if i == numFiles-1 {
            fMax = maxKey
        }
        sst := SSTable{
            ID: t.nextID, Level: level, MinKey: fMin, MaxKey: fMax,
            Size: totalSize / numFiles, Entries: totalEntries / numFiles, SeqNum: t.nextSeq,
        }
        t.nextID++
        t.nextSeq++
        t.levels[level] = append(t.levels[level], sst)
        t.bytesWritten += int64(sst.Size)
    }
    sort.Slice(t.levels[level], func(i, j int) bool {
        return t.levels[level][i].MinKey < t.levels[level][j].MinKey
    })
}

// Stats 返回统计信息
func (t *LSMTree) Stats() string {
    var sb strings.Builder
    sb.WriteString("=== LSM-tree Statistics ===\n")
    for i := 0; i < t.maxLevels; i++ {
        size := t.levelSize(i)
        target := t.targetSize(i)
        sb.WriteString(fmt.Sprintf(
            "  L%d: %d files, %d KB (target: %d KB)\n",
            i, len(t.levels[i]), size/1024, target/1024))
    }
    wa := float64(0)
    if t.userWritten > 0 {
        wa = float64(t.bytesWritten) / float64(t.userWritten)
    }
    sb.WriteString(fmt.Sprintf("  Compactions: %d\n", t.compactions))
    sb.WriteString(fmt.Sprintf("  User Written: %.2f MB\n",
        float64(t.userWritten)/1048576))
    sb.WriteString(fmt.Sprintf("  Actual Written: %.2f MB\n",
        float64(t.bytesWritten)/1048576))
    sb.WriteString(fmt.Sprintf("  Write Amplification: %.2fx\n", wa))
    sb.WriteString(fmt.Sprintf("  Bytes Read (compaction): %.2f MB\n",
        float64(t.bytesRead)/1048576))
    return sb.String()
}

func main() {
    // 参数: 7 层, size_ratio=10, L1=2MB, SST=512KB
    tree := NewLSMTree(7, 10, 2*1024*1024, 512*1024)

    fmt.Println("Simulating 10000 random writes...")
    fmt.Println()

    keySpace := 100000

    for i := 0; i < 10000; i++ {
        // 随机生成 key 范围, 模拟 MemTable flush
        base := rand.Intn(keySpace)
        span := 500 + rand.Intn(500) // 500-999 个 key
        entries := 500 + rand.Intn(500)
        tree.Flush(base, base+span, entries)

        // 每 2000 次输出一次中间状态
        if (i+1)%2000 == 0 {
            fmt.Printf("--- After %d flushes ---\n", i+1)
            fmt.Println(tree.Stats())
        }
    }

    fmt.Println("--- Final State ---")
    fmt.Println(tree.Stats())
}

运行效果示例：

$ go run compaction_sim.go
Simulating 10000 random writes...

--- After 2000 flushes ---
=== LSM-tree Statistics ===
  L0: 0 files, 0 KB (target: 0 KB)
  L1: 4 files, 1953 KB (target: 2048 KB)
  L2: 12 files, 5859 KB (target: 20480 KB)
  L3: 0 files, 0 KB (target: 204800 KB)
  ...
  Compactions: 498
  User Written: 97.66 MB
  Actual Written: 312.50 MB
  Write Amplification: 3.20x
  Bytes Read (compaction): 245.12 MB

--- After 10000 flushes ---
=== LSM-tree Statistics ===
  L0: 2 files, 195 KB (target: 0 KB)
  L1: 5 files, 2441 KB (target: 2048 KB)
  L2: 38 files, 18554 KB (target: 20480 KB)
  L3: 5 files, 2441 KB (target: 204800 KB)
  ...
  Compactions: 2510
  User Written: 488.28 MB
  Actual Written: 1892.10 MB
  Write Amplification: 3.87x
  Bytes Read (compaction): 1523.44 MB

十、实战调优: RocksDB、ScyllaDB 与 Cassandra

10.1 RocksDB 调优指南

RocksDB 的 compaction 调优可以归结为几个核心维度：

维度 1: 写入吞吐 vs 读取延迟
  写优先: Universal + write_buffer_size=128MB + max_write_buffer_number=5
  读优先: Level + max_bytes_for_level_base=512MB + optimize_filters_for_hits=true

维度 2: 空间效率 vs I/O 开销
  空间优先: dynamic_level_bytes=true + compression_per_level={None,LZ4,LZ4,ZSTD,...}
  I/O 优先: target_file_size_base=32MB + max_compaction_bytes=256MB

维度 3: 延迟敏感 vs 吞吐优先
  低延迟: l0_trigger=2, slowdown=8, rate_limiter=50MB/s, direct_io=true
  高吞吐: l0_trigger=8, background_compactions=8, subcompactions=4

10.2 ScyllaDB Incremental Compaction Strategy（ICS）

ScyllaDB 在 2020 年推出了 Incremental Compaction Strategy（ICS），这是对传统 compaction 策略的重要创新。

ICS 核心思想:

  传统 LCS:
    合并 N 个文件 -> 写入 N 个新文件 -> 删除 N 个旧文件
    合并期间空间占用翻倍

  ICS:
    合并 N 个文件 -> 写入一个"增量结果" -> 逐步替换旧文件
    合并可以被中断和恢复
    合并期间空间开销远小于传统 LCS

  优点:
    1. 空间放大更低 (合并期间不需要 2x 空间)
    2. 合并可以暂停/恢复 (对运维友好)
    3. 更好的延迟稳定性 (避免大规模一次性合并)
    4. 自动适应工作负载变化

ICS 的配置相对简单：

-- ScyllaDB ICS 配置
CREATE TABLE sensor_data (
    device_id uuid,
    ts timestamp,
    value double,
    PRIMARY KEY (device_id, ts)
) WITH compaction = {
    'class': 'IncrementalCompactionStrategy',
    'sstable_size_in_mb': 1024,
    'bucket_low': 0.5,
    'bucket_high': 1.5
};

10.3 Cassandra STCS 到 LCS 迁移

在 Cassandra 中，从 STCS 迁移到 LCS 需要谨慎执行。在低峰期逐节点切换，用 nodetool setcompactionthroughput 限速，预留 2x 磁盘空间：

ALTER TABLE keyspace.table
WITH compaction = { 'class': 'LeveledCompactionStrategy', 'sstable_size_in_mb': 160 };

迁移前后的典型对比：

  指标              STCS        LCS         变化
  ------------------------------------------------
  P99 读延迟       12ms        3ms         -75%
  P99 写延迟       2ms         5ms         +150%
  磁盘空间占用     2.1x        1.1x        -48%
  写放大           ~5x         ~25x        +400%

十一、基准测试: 不同策略的性能表现

下面是一组在相同硬件环境下，使用 db_bench 对 RocksDB 不同 compaction 策略进行的基准测试结果。

11.1 测试环境

硬件:
  CPU: AMD EPYC 7763 64-Core (16 核分配)
  RAM: 64 GB DDR4
  SSD: Samsung PM9A3 3.84TB NVMe (顺序写 2GB/s, 随机读 800K IOPS)

软件:
  RocksDB 8.10.0
  db_bench 工具

数据集:
  Key: 16 bytes (随机)
  Value: 1024 bytes
  总条目数: 100M (~100GB 有效数据)

11.2 写入吞吐测试

db_bench --benchmarks=fillrandom --num=100000000 --value_size=1024 --threads=8

  策略               吞吐 (MB/s)    写放大    P99 延迟
  -------------------------------------------------------
  Leveled (T=10)     185            32.5x     4.2ms
  Leveled (T=8)      201            28.1x     3.8ms
  Universal           312            8.7x     6.1ms
  FIFO                423            1.0x     0.3ms

11.3 混合读写测试

db_bench --benchmarks=readwhilewriting --threads=8 --benchmark_write_rate_limit=10485760

  策略               读吞吐(ops/s)  P50读(us)  P99读(us)  P999读(us)
  -------------------------------------------------------------------
  Leveled (T=10)     245,000        42         380        2,100
  Leveled (T=8)      238,000        45         410        2,400
  Universal           198,000        68         920        8,500
  FIFO                165,000        95         1,800      15,000

11.4 范围查询测试

db_bench --benchmarks=seekrandom --num=100000000 --seek_nexts=100 --threads=8

  策略               范围查询吞吐(ops/s)    P99延迟(us)
  -------------------------------------------------------
  Leveled (T=10)     52,000                 850
  Leveled (T=8)      48,000                 920
  Universal           31,000                 2,400
  FIFO                22,000                 4,100

11.5 分析总结

写放大排名 (低 -> 高):
  FIFO (1.0x) < Universal (8.7x) < Leveled/T=8 (28.1x) < Leveled/T=10 (32.5x)

读放大排名 (低 -> 高):
  Leveled/T=10 < Leveled/T=8 < Universal < FIFO

空间放大排名 (低 -> 高):
  Leveled/T=10 (1.11x) < Leveled/T=8 (1.14x) < Universal (1.5-2x) < FIFO (N/A)

结论:
  - 读多写少: Leveled (T=10)
  - 读写均衡: Leveled (T=8) 或 Universal (调参后)
  - 写多读少: Universal
  - 纯时间序列: FIFO

十二、工程踩坑与个人观点

12.1 踩坑总结

12.2 个人观点

经过多年与各种 LSM-tree 存储引擎打交道的经验，我有以下几点体会：

Leveled Compaction 仍然是最安全的默认选择。 虽然写放大高，但它提供了最可预测的读性能和最低的空间放大。在大多数生产环境中，读性能和空间利用率比写入吞吐更重要。如果你不确定该选哪个策略，选 Leveled。

Universal Compaction 的调参难度被严重低估。 它的参数空间很大，而且不同参数组合之间的交互效应复杂。我见过太多团队在切换到 Universal 后遇到意料之外的空间放大或写入卡顿。除非你有足够的精力去理解和调优每一个参数，否则不建议在生产环境使用。

Dostoevsky 的理论框架比它的具体策略更有价值。 Lazy Leveling 和 Fluid LSM-tree 在学术上很优美，但工程实现的复杂度不低。真正有实用价值的是 Monkey 的 Bloom Filter 分配策略——这是一个低成本、高收益的优化，任何 LSM-tree 都应该考虑。

Write stall 是生产环境的头号敌人。 我个人的经验是，在设计任何 compaction 相关配置时，首先考虑的不是最优性能，而是”最坏情况下会不会 stall”。一个 P99 延迟略高但从不 stall 的系统，远好于一个平均性能极佳但偶尔卡死 5 秒的系统。

分层压缩策略是被低估的优化手段。 对不同层使用不同的压缩算法，可以在几乎不影响读写性能的情况下显著降低磁盘使用量：

推荐的分层压缩配置:

  L0-L1: 不压缩 (数据热，频繁读写)
  L2-L3: LZ4 (快速压缩，适中比率)
  L4+:   ZSTD (高压缩比，数据冷)

  代码:
  options.compression_per_level = {
      kNoCompression,     // L0
      kNoCompression,     // L1
      kLZ4Compression,    // L2
      kLZ4Compression,    // L3
      kZSTD,              // L4
      kZSTD,              // L5
      kZSTD               // L6
  };

监控先行，调优在后。 在动手调整任何参数之前，先确保你有完善的监控：

必监控指标: stall.micros / num-files-at-levelN / estimate-pending-compaction-bytes
            bytes-written / bytes-read / block-cache-hit / compaction.times.micros

12.3 进一步阅读

• O’Neil et al., “The Log-Structured Merge-Tree”, 1996
• Dayan & Idreos, “Dostoevsky”, SIGMOD 2018
• Dayan et al., “Monkey: Optimal Navigable Key-Value Store”, SIGMOD 2017
• RocksDB Wiki: Leveled/Universal Compaction
• Scylla Blog, “Incremental Compaction Strategy”

上一篇: WAL 与 ARIES 恢复算法 下一篇: MVCC 实现变体全解

相关阅读: - B+tree 与 LSM-tree - I/O 调度算法