LSM-Tree 存储引擎深度解析：MemTable、WAL、Compaction 与读写放大

B+ 树写入路径：
  写入 → 定位叶子页 → 就地修改（随机写）→ 页分裂/合并

痛点：
  · 随机写性能差（磁盘寻道 / SSD 写放大）
  · 页分裂导致写放大与碎片
  · 高并发写下索引更新竞争激烈

LSM-Tree 的思路：
  不立刻落盘 → 先写内存（顺序）→ 批量刷盘（顺序）→ 后台合并
  → 随机写变顺序写，吞吐量提升 1-2 个数量级

内存层：         MemTable（可写）→ 满后转 Immutable
                 ↓ flush
磁盘层（L0）：    SSTable 文件（无序，多个）
                 ↓ compaction
磁盘层（L1+）：   SSTable 文件（有序，按 key 范围划分）
                 ↓ compaction（逐层下沉）
               Lmax（最底层）

每个 SSTable：Sparse Index + Bloom Filter + 数据块
WAL（Write-Ahead Log）：落盘前先写日志，崩溃恢复用

Put(key, value):
  1. 追加到 WAL（顺序写，持久化保障）
  2. 写入 MemTable（有序结构，内存）
  3. MemTable 达到阈值 → 冻结为 Immutable
  4. 后台线程将 Immutable flush 为 SSTable（L0）
  5. 后续 compaction 将 L0 合并到 L1、L2...

删除（Tombstone）：
  Delete(key) → 写入一个删除标记（tombstone）
  → 真正物理删除要等 compaction 时把被标记的旧版本清掉

# lsm_put.py — 写入路径伪代码
def lsm_put(wal, memtable, key, value):
    wal.append(key, value)            # 1. 先写 WAL（顺序追加）
    memtable.put(key, value)          # 2. 写内存表
    if memtable.size > threshold:     # 3. 满则冻结
        immutable = memtable.freeze()
        schedule_flush(immutable)     # 4. 异步刷盘

def lsm_get(memtable, immutables, sstables, bloom_filters, key):
    if key in memtable: return memtable.get(key)          # 1. 内存最新
    for imm in reversed(immutables):                      # 2. 冻结表（新→旧）
        if key in imm: return imm.get(key)
    for sst in level_order(sstables):                     # 3. 磁盘层（L0→Lmax）
        if bloom_filters[sst].might_contain(key):         #    布隆过滤
            if val := sst.get(key): return val
    return None                                           # 4. 未找到

// RocksDB MemTable 相关选项
Options options;
options.write_buffer_size = 64 * 1024 * 1024;  // 单 MemTable 64MB
options.max_write_buffer_number = 4;            // 最多 4 个（含冻结）
options.min_write_buffer_number_to_merge = 2;   // flush 前至少 2 个

WAL 的作用：
  · 数据先落 WAL 再进内存 → 进程崩溃不丢已确认的写
  · 恢复时重放 WAL 重建 MemTable

WAL 的代价：
  · 每次写多一次磁盘 fsync（可调：每次/批/关闭）
  · 可用 group commit 合并 fsync 提升吞吐

RocksDB 选项：
  WriteOptions.sync = true/false   # 是否强制刷盘
  WAL 与 MemTable flush 后 WAL 可清理

WriteOptions write_options;
write_options.sync = true;        // 强持久化（金融场景）
// 或
write_options.sync = false;       // 高吞吐，靠 OS 缓存 + 周期刷

SSTable 文件结构：
  ┌──────────────────────────┐
  │  Data Block 0 (有序 keys) │
  │  Data Block 1             │
  │  ...                      │
  │  Sparse Index（块级索引） │
  │  Bloom Filter（块级/整体）│
  │  Metadata                 │
  │  Footer（索引位置）        │
  └──────────────────────────┘

查询一个 key：
  1. Bloom Filter 快速判断"是否存在"（不存在的直接返回）
  2. Sparse Index 二分定位可能包含 key 的 Data Block
  3. 读取该 Data Block，块内二分/线性扫描定位

L0：文件无序（来自不同 flush），查询需扫描多个文件
L1+：文件内部有序 + 文件间按 key 范围互不重叠（可用稀疏索引定位单个文件）

→ L0 越少越好，compaction 优先把 L0 压到 L1
→ 查询优先从内存 → L0 → 低层逐层搜索

数据永远在膨胀：
  · 旧版本 key 需要清理（多版本 + tombstone）
  · 小 SSTable 太多，查询要扫的文件越来越多
  · 无界增长导致读放大失控

Compaction 做三件事：
  1. 合并小文件成大文件（减少文件数）
  2. 清理旧版本与 tombstone（回收空间）
  3. 保持层级有序（优化读路径）

// RocksDB 选择 Leveled（默认）
options.compaction_style = CompactionStyle::kCompactionStyleLevel;

// Size-Tiered（写密集时序场景可选）
options.compaction_style = CompactionStyle::kCompactionStyleUniversal;

写放大（Write Amplification）：
  实际写入磁盘的数据量 / 用户写入数据量
  Leveled 通常 10-30x；Size-Tiered 5-15x
  → 高写放大磨损 SSD、限制写吞吐

读放大（Read Amplification）：
  一次查询实际读取的数据量 / 目标数据量
  → 越高点查越慢

权衡：压缩越激进（Leveled），读放大越低但写放大越高
  需按 workload 调 L0 大小、层数、触发阈值

// RocksDB 每个 SSTable 启用 Bloom Filter
options.filter_policy = rocksdb::NewBloomFilterPolicy(10);  // 10bit/key
// 不同级别的 filter 可差异化：
// L0/L1 关闭（小层查询成本低），高层开启（省内存）

// 也支持整表前缀 Bloom（针对前缀查询）

命中分析：
  存在 key：Bloom 几乎必过 → 进入索引定位
  不存在 key：Bloom 大概率拒绝（1% 误判才多读一层）

收益：
  · 点查不存在 key 的成本 ≈ O(1)
  · 点查存在 key 的成本大幅下降（跳过无关文件）
  · 代价：每个 SSTable 增加 10-20% 内存/存储

// RocksDB 生产调优常用参数
options.write_buffer_size = 128 << 20;      // MemTable 128MB
options.max_write_buffer_number = 4;        // 内存缓冲深度
options.min_write_buffer_number_to_merge = 2;
options.max_background_compactions = 4;     // 并行 compaction
options.max_background_flushes = 2;
options.level0_file_num_compaction_trigger = 8;   // L0 触发 compaction
options.level0_slowdown_writes_trigger = 20;      // 写降速阈值
options.level0_stop_writes_trigger = 36;          // 写暂停阈值（防雪崩）
options.soft_pending_compaction_bytes_limit = 64GB;
options.hard_pending_compaction_bytes_limit = 128GB;

// 压缩算法
options.compression = rocksdb::kSnappyCompression;      // 快速
options.bottommost_compression = rocksdb::kZSTD;        // 底层高压缩

写吞吐不足：
  · 增大 write_buffer_size（攒更多再刷）
  · 增大 max_write_buffer_number（容忍内存延迟）
  · 增 max_background_compactions（并行压缩）
  · 检查写放大（Universal 是否更合适）

点查变慢（读放大）：
  · 开 Bloom Filter
  · 加快 compaction（缩小 L0，减少小文件扫描）
  · 减少层级（压缩更激进）

空间使用高：
  · 用 zstd/lz4 压缩底层
  · 检查 tombstone 清理节奏（是否 compaction 太慢）

写停顿（stall）：
  · pending compaction 达到 hard 阈值会暂停写
  · 提前扩容 / 增加压缩线程 / 用更轻的压缩算法

RocksDB 关键指标（Prometheus）：
  rocksdb_compaction_num                  # 压缩次数
  rocksdb_compaction_bytes_written        # 写放大字节
  rocksdb_slow_write_count                # 写停顿
  rocksdb_memtable_total_size             # 内存占用
  rocksdb_compaction_pending              # 待压缩量
  rocksdb_block_cache_hit_ratio           # 缓存命中率

演进方向：
  · MySQL 8.x：可选 RocksDB 引擎（MyRocks），写密集业务受益
  · RocksDB 引入"持久化 MemTable / 分块索引"改善读
  · 很多系统 LSM + 内存加速层（缓存热点）缓解读放大
  → 选型不是"二选一"，而是按 workload 混用

落地 Checklist：
  □ 明确 workload：写多读少 / 读多写少
  □ 选择 compaction 策略（Leveled 通用 / Universal 写密集）
  □ MemTable 与 WAL 参数匹配写入速率
  □ Bloom Filter 按层差异化开启
  □ 压缩算法：热层 Snappy/LZ4，冷层 ZSTD
  □ 设置写停顿阈值（防止 compaction 追不上写入）
  □ 监控 read/write amplification 与 stall
  □ 定期做 compaction 健康检查与空间回收

写密集 + 点查少（日志/时序/Feed）：LSM（RocksDB/Universal）
写密集 + 点查多：LSM + 大缓存层 + Bloom
读密集 + 低延迟：B+ 树（InnoDB/PostgreSQL）
需要事务/外键：B+ 树为主，写热点表可用 MyRocks
大数据分布式：TiKV/Cassandra（LSM 底座）