RocksDB LSM树原理 #

核心思想：
将随机写入转换为顺序写入，极大提高写入性能

传统B+Tree：
随机写入 → 磁盘随机IO → 性能差

LSM-Tree：
随机写入 → 内存缓冲 → 顺序刷盘 → 性能优

                    写入请求
                       │
                       ▼
┌──────────────────────────────────────────┐
│              MemTable (内存)              │
│         有序跳表，接收写入                │
└────────────────────┬─────────────────────┘
                     │ 写满后转为Immutable
                     ▼
┌──────────────────────────────────────────┐
│          Immutable MemTable (内存)        │
│         不可变，等待Flush                 │
└────────────────────┬─────────────────────┘
                     │ 后台Flush
                     ▼
┌──────────────────────────────────────────┐
│                 Level 0                   │
│  ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐    │
│  │ SST  │ │ SST  │ │ SST  │ │ SST  │    │
│  └──────┘ └──────┘ └──────┘ └──────┘    │
│         (文件可能有键重叠)                │
└────────────────────┬─────────────────────┘
                     │ Compaction
                     ▼
┌──────────────────────────────────────────┐
│                 Level 1                   │
│  ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐    │
│  │ SST  │ │ SST  │ │ SST  │ │ SST  │    │
│  └──────┘ └──────┘ └──────┘ └──────┘    │
│         (文件无重叠，有序)                │
└────────────────────┬─────────────────────┘
                     │ Compaction
                     ▼
┌──────────────────────────────────────────┐
│                 Level 2                   │
│  ┌──────┐ ┌──────┐ ┌──────┐ ...         │
│  │ SST  │ │ SST  │ │ SST  │             │
│  └──────┘ └──────┘ └──────┘             │
└──────────────────────────────────────────┘
                     ...

写入请求 (key, value)
        │
        ▼
┌─────────────────┐
│   追加WAL日志    │ ← 顺序写入，保证持久性
└────────┬────────┘
         │
         ▼
┌─────────────────┐
│ 写入MemTable    │ ← 跳表插入，O(log n)
└────────┬────────┘
         │
         ▼
    返回成功

写入优化策略：

1. 批量写入
   - WriteBatch合并多个操作
   - 减少WAL写入次数

2. 异步写入
   - sync=false，不等待刷盘
   - 提高写入吞吐

3. MemTable优化
   - 跳表实现，高效有序
   - 支持并发写入

读取请求 (key)
        │
        ▼
┌─────────────────────┐
│ 检查MemTable        │
│ (Active + Immutable)│
└──────────┬──────────┘
           │ 未找到
           ▼
┌─────────────────────┐
│ 检查Block Cache     │
└──────────┬──────────┘
           │ 未命中
           ▼
┌─────────────────────┐
│ 查找Level 0         │
│ (所有文件，可能重叠) │
└──────────┬──────────┘
           │ 未找到
           ▼
┌─────────────────────┐
│ 查找Level 1~N       │
│ (二分查找文件)      │
└──────────┬──────────┘
           │
           ▼
      返回结果

// 布隆过滤器加速查找
rocksdb::BlockBasedTableOptions table_options;
table_options.filter_policy.reset(
    rocksdb::NewBloomFilterPolicy(10)  // 10 bits per key
);
options.table_factory.reset(
    rocksdb::NewBlockBasedTableFactory(table_options)
);

布隆过滤器效果：
- 快速排除不存在的键
- 减少不必要的磁盘读取
- 代价：少量内存开销

Level 0:
- 文件数量不限
- 文件可能有键重叠
- 直接从MemTable Flush生成

Level 1~N:
- 文件无重叠，有序
- 大小呈指数增长
- Level N+1 = 10 × Level N

示例：
Level 0: 不限
Level 1: 256 MB
Level 2: 2.5 GB
Level 3: 25 GB
Level 4: 250 GB
Level 5: 2.5 TB
Level 6: 25 TB

rocksdb::Options options;

// 每层目标大小
options.max_bytes_for_level_base = 256 * 1024 * 1024;  // 256MB

// 层级倍数
options.max_bytes_for_level_multiplier = 10;

// L0文件数量触发Compaction
options.level0_file_num_compaction_trigger = 4;

// L0文件数量触发写入减速
options.level0_slowdown_writes_trigger = 20;

// L0文件数量触发写入停止
options.level0_stop_writes_trigger = 36;

写放大 = 实际写入磁盘的数据量 / 用户写入的数据量

LSM-Tree写放大来源：
1. Flush: MemTable → SST
2. Compaction: Level N → Level N+1

示例：
写入1MB数据：
- Flush: 写入1MB SST
- L0→L1 Compaction: 写入10MB
- L1→L2 Compaction: 写入100MB
- ...
总写入量远超1MB

Leveled Compaction写放大：
WAF ≈ (Level数) × (每层放大倍数)

典型配置：
- 7层
- 每层放大10倍
WAF ≈ 7 × 10 = 70

优化方法：
1. 减少层级数量
2. 使用Tiered Compaction
3. 增大每层大小

读放大 = 实际读取的数据量 / 用户需要的数据量

LSM-Tree读放大来源：
1. 多层查找
2. SST文件内查找
3. Block读取

示例：
查找一个键：
- 检查MemTable
- 检查L0所有文件（可能重叠）
- 检查L1~L6各一个文件
- 每个文件可能读取多个Block

// 1. 布隆过滤器
table_options.filter_policy.reset(
    rocksdb::NewBloomFilterPolicy(10)
);

// 2. Block Cache
options.block_cache = rocksdb::NewLRUCache(
    1024 * 1024 * 1024  // 1GB
);

// 3. 压缩缓存
options.block_cache_compressed = rocksdb::NewLRUCache(
    256 * 1024 * 1024  // 256MB
);

空间放大 = 实际磁盘占用 / 有效数据大小

LSM-Tree空间放大来源：
1. 多版本数据
2. Compaction中间状态
3. 未压缩数据

示例：
有效数据10GB：
- L0: 1GB（可能有重复）
- L1: 2GB
- L2: 10GB
- Compaction临时文件: 2GB
实际占用15GB，空间放大1.5x

// 1. 启用压缩
options.compression = rocksdb::CompressionType::kZSTD;

// 2. 分层压缩
options.compression_per_level = {
    rocksdb::CompressionType::kNoCompression,
    rocksdb::CompressionType::kLZ4Compression,
    rocksdb::CompressionType::kLZ4Compression,
    rocksdb::CompressionType::kZSTD,
    rocksdb::CompressionType::kZSTD,
    rocksdb::CompressionType::kZSTD,
    rocksdb::CompressionType::kZSTD
};

// 3. 及时Compaction
options.max_compaction_bytes = 256 * 1024 * 1024;

选择LSM-Tree：
- 写入密集型应用
- 需要高写入吞吐
- 数据量大
- 可接受读放大

选择B+Tree：
- 读取密集型应用
- 需要低延迟读取
- 频繁更新
- 需要高效范围查询