lsm-tree
No related notes
Outlinks (0)
No outlinks found
Backlinks (0)
No backlinks found
1 · lsm-tree#
1.1 · S - 场景#
需要大量写入且写吞吐量优先的场景：
- 数据库引擎（RocksDB、LevelDB、SQLite4）
- 时间序列数据库（InfluxDB、Prometheus）
- 日志系统（Kafka、Cassandra）
- 分布式KV存储（HBase、DynamoDB）
1.2 · C - 核心权衡#
| 维度 | 传统 B-tree | LSM-tree |
|---|---|---|
| 写入模式 | 随机写（寻道） | 顺序追加（快） |
| 读取 | 直接查询 | 需要多层查询 |
| 空间利用 | 高 | 较低（重复版本） |
| CPU利用 | 低 | 高（compaction） |
1.3 · Q - 核心问题与解决#
1.3.1 · Q1. 写快读慢的问题#
问题：直接追加 key-value，同一个 key 有多个版本，读取时需要全文件扫描。
解决方案：
- 内存 memtable：小规模数据排序存储，快速查询 O(log n)
- 多层 SSTable：按 key 范围分层，快速定位
- 布隆过滤器：快速判断 key 是否存在，避免不必要的查询
1.3.2 · Q2. 多版本管理问题#
问题：旧值不删除，磁盘持续增长，读取需要找”最新版本”。
解决方案：后台 compaction
- 合并多个 SSTable
- 删除旧版本、过期版本（tombstone）
- 重新排序、去重
1.3.3 · Q3. 宕机数据丢失#
问题：内存 memtable 未刷盘的数据在宕机时丢失。
解决方案：Write-Ahead Log (WAL)
- 写入前先顺序写 WAL
- 宕机恢复时重放 WAL 恢复 memtable
1.4 · A - LSM-tree 架构#
1.4.1 · 核心思想
延迟处理：写的时候尽量顺着写（顺序I/O），读的时候再靠索引和合并补回来。
1.4.2 · 数据流
┌─ 客户端 Write ─┐
│ │
├──> WAL (顺序写) ──────────┐
│ (磁盘预写日志) │
│ ↓
└──> Memtable (内存有序表) │
(SkipList 或 B-tree) │
│ │
├─ 大小 > 阈值 ────┘
│ (如 2MB)
↓
SSTable 0 (新)
SSTable 1
SSTable 2
...
SSTable N (旧)
后台合并（Compaction）：
多层 SSTable ──> 合并排序 ──> 去重 ──> 新 SSTable1.4.3 · 读取流程（Get 操作）#
查询 key
├─> [O(log n)] Memtable（有序跳表）
│ └─> 找到 → 返回
│ └─> 未找到 ↓
├─> [O(k log n)] SSTable 层级查询（k = 层数）
│ ├─ SSTable 0 [最新]
│ │ ├─ 布隆过滤器快速判断
│ │ └─ 二分查找
│ ├─ SSTable 1
│ ├─ SSTable 2
│ └─ ...
└─> 返回最新版本或 null1.5 · 关键组件详解
1.5.1 · 1. Memtable（内存表）#
作用：缓存最近写入的数据，实现高速写入
实现：
- 跳表（skiplist）：原理简单、查询快、易实现
- 红黑树：更好的平衡性
- B+ 树：范围查询友好
特点：
- key 必须有序
- 达到大小阈值（如 2MB）后转换为 SSTable
- 新写入优先查询这里
- 宕机时需要 WAL 恢复
1.5.2 · 2. SSTable（Sorted String Table）#
特点：
- 不可变的有序文件
- 一旦写入就不再修改
- 按 key 范围分级：L0、L1、L2…
内部结构：
┌──────────────────────────┐
│ Data Block 1 │ 实际 key-value 对
│ Data Block 2 │
├──────────────────────────┤
│ Index Block │ key 范围索引
├──────────────────────────┤
│ Bloom Filter │ 概率数据结构，快速判断 key 是否存在
├──────────────────────────┤
│ Footer/Metadata │ 版本号、校验和、指针
└──────────────────────────┘查询过程：
- 布隆过滤器判断 key 可能存在 → 继续
- Index Block 二分查找定位 Data Block 范围
- 在对应 Data Block 中二分查询
1.5.3 · 3. Compaction（合并）#
目的：
- 删除旧版本和过期数据（tombstone）
- 重新组织数据，减少读放大
- 回收磁盘空间
两种策略对比：
Leveled Compaction（LevelDB）
L0: [SST1] [SST2] [SST3] (多个文件，可能有重叠)
↓ (size > threshold)
L1: [SST1] [SST2] [SST3] (固定容量，key 不重叠)
↓
L2: [SST1] [SST2]
↓
L3: [SST1]- 特点：每层内 key 不重叠，读放大小
- 代价：写放大大（频繁重组）
Tiered Compaction（RocksDB）
Level 0: [SST1] [SST2] [SST3] (不排序)
↓ (积累 > threshold)
Level 1: [SST1] [SST2] ... [SSTn] (多个文件可重叠)
↓
Level 2: [SST1] [SST2] ...- 特点：同层内文件可重叠，写放大小
- 代价：读放大大（需要查多个文件）
1.5.4 · 4. Write-Ahead Log (WAL)#
原理：先写日志，再写内存
Client Put(key, value)
↓
WAL.append(key, value) ← 顺序写磁盘（必须成功）
↓
Memtable.put(key, value) ← 写内存
↓
返回成功恢复过程：
宕机重启
↓
读取 WAL 文件
↓
重放日志，恢复 memtable
↓
继续正常操作1.6 · 性能特征
1.6.1 · 时间复杂度
| 操作 | 复杂度 | 说明 |
|---|---|---|
| Put | O(log n) | memtable 的有序插入 |
| Get | O(k·log n) | k = SSTable 层数，每层二分查找 |
| Delete | O(log n) | 写入墓碑标记（tombstone） |
| Range Scan | O(log n + m) | m = 结果行数 |
1.6.2 · 放大因子
读放大（Read Amplification）
- 定义：读一条数据时实际 I/O 操作数
- LSM 的读放大：最坏需要查 k 层 SSTable（k ≈ 10）
- 优化方式：缓存、布隆过滤器、分级索引
写放大（Write Amplification）
- 定义：写 1 字节数据实际写入磁盘的字节数
- LSM 的写放大：数据在 compaction 中被重写多次
- L0 → L1：重写 1 次
- L1 → L2：重写 1 次
- …
- 总写放大 ≈ (key_size + value_size) × (L+1)
- L = 层数
- LSM-tree 接受高写放大是因为顺序写仍比随机写快
空间放大（Space Amplification）
- 定义：实际占用磁盘空间 / 有用数据大小
- 原因：保留多版本、过期数据未及时清理
- LSM 空间放大 ≈ 1.1 ~ 1.5（取决于 compaction 策略）
1.6.3 · 权衡示意
顺序写 vs 随机写：
├─ SSD 随机写: ~100MB/s
└─ SSD 顺序写: ~500MB/s (快 5 倍)
LSM-tree 的权衡：
├─ 写优化：顺序 I/O，高吞吐
├─ 读代价：多层查询，高读放大
└─ 空间代价：多版本保留，高空间放大1.7 · 实现概览（伪代码）
class LSMTree:
def __init__(self):
self.memtable = SkipList() # 内存有序表
self.immutable = None # 待刷盘的 memtable
self.sstables = [] # SSTable 列表（按层级）
self.wal = WriteAheadLog() # 预写日志
def put(self, key, value):
# 1. 写 WAL（保证宕机安全）
self.wal.append(key, value)
# 2. 写 memtable
self.memtable.put(key, value)
# 3. 检查是否需要刷盘
if self.memtable.size() > MEMTABLE_MAX_SIZE:
self._flush_memtable()
def get(self, key):
# 1. 查询 memtable（最新）
val = self.memtable.get(key)
if val is not None:
return val
# 2. 查询待刷盘 memtable
if self.immutable is not None:
val = self.immutable.get(key)
if val is not None:
return val
# 3. 查询 SSTable（从新到旧）
for sstable in self.sstables:
# 先检查布隆过滤器（快速排除）
if not sstable.bloom_filter.might_contain(key):
continue
val = sstable.get(key)
if val is not None:
return val
return None
def delete(self, key):
# LSM 的删除实际是写入墓碑标记
self.put(key, TOMBSTONE)
def _flush_memtable(self):
# memtable 转换为 SSTable
self.immutable = self.memtable
self.memtable = SkipList()
# 后台线程执行
self._background_flush()
def _background_flush(self):
# 将 memtable 刷盘成 SSTable
sstable = SSTable.from_memtable(
self.immutable,
build_bloom_filter=True
)
self.sstables.append(sstable)
self.immutable = None
self._trigger_compaction()
def _trigger_compaction(self):
# 检查是否需要 compaction
if self._should_compact():
self._compact()
def _compact(self):
# 选择要合并的 SSTable
candidates = self._pick_compaction_files()
# 合并、排序、去重
merged = self._merge_sstables(candidates)
# 删除旧文件，添加新文件
for old_sstable in candidates:
self.sstables.remove(old_sstable)
self.sstables.append(merged)1.8 · 对比其他数据结构
| 结构 | 写 | 读 | 空间 | 最佳场景 |
|---|---|---|---|---|
| B-tree | O(log n)随机 | O(log n) | 高利用 | 通用数据库 |
| LSM-tree | O(1)顺序 | O(k log n) | 低利用 | 写密集 |
| Hash表 | O(1) | O(1) | 中等 | 内存缓存 |
| 日志结构 | O(1)追加 | O(n)扫描 | 最低 | 只写日志 |
1.9 · 常见优化
| 优化 | 方法 | 收益 |
|---|---|---|
| 减少读放大 | 布隆过滤器、缓存、分层索引 | 减少不必要的磁盘 I/O |
| 减少写放大 | 选择 Tiered Compaction | 减少重写数据量 |
| 加快 Compaction | 并行压缩、增量压缩 | 减少后台 CPU |
| 减少空间放大 | 及时 compaction、压缩算法 | 降低磁盘占用 |
1.10 · 工业实现
- RocksDB：Facebook 开源，广泛用于生产
- Tiered Compaction 为默认
- 支持列式存储、预留空间等高级特性
- LevelDB：Google 开源，参考实现
- Leveled Compaction
- 代码简洁，易于学习
- WiredTiger：MongoDB 存储引擎
- Cassandra：分布式数据库使用 LSM