当前位置：首页 > news >正文

存储引擎内核剖析：B+Tree 与 LSM-Tree 的性能博弈，以及如何做可信的 Benchmark

news 2026/6/29 21:08:50

存储引擎内核剖析：B+Tree 与 LSM-Tree 的性能博弈，以及如何做可信的 Benchmark

一、存储引擎选型的伪命题：没有万能引擎，只有场景匹配

存储引擎的选型争论从未停止。InnoDB 用 B+Tree，LevelDB/RocksDB 用 LSM-Tree，两者各有拥趸。但大多数讨论停留在"B+Tree 读快写慢、LSM-Tree 写快读慢"这种粗粒度结论上，缺乏对具体场景的量化分析。

真实的性能特征远比这复杂。LSM-Tree 的读性能取决于 Compaction 策略和 Bloom Filter 的效率；B+Tree 的写性能取决于 Redo Log 的刷盘策略和 Buffer Pool 的命中率。同一个引擎，在不同数据规模、不同读写比例、不同数据分布下，性能表现可能天差地别。

更关键的问题是：如何做可信的 Benchmark？很多性能测试的结论不可复现，因为测试方法本身有缺陷：预热不充分、数据分布不真实、并发模型不合理、统计方法不严谨。一个不可复现的 Benchmark，比没有 Benchmark 更危险——它会误导技术决策。

二、B+Tree 与 LSM-Tree 的写入路径对比

两种引擎的核心差异在于写入路径的设计。B+Tree 采用原地更新（In-place Update），LSM-Tree 采用追加写入（Out-of-place Update）。

flowchart TD subgraph B+Tree写入路径 A1[写入请求] --> A2[Redo Log<br/>WAL 顺序写入] A2 --> A3[Buffer Pool<br/>修改页标记为 Dirty] A3 --> A4[后台刷脏<br/>随机 I/O 写入数据页] A4 --> A5[Doublewrite Buffer<br/>防止页撕裂] end subgraph LSM-Tree写入路径 B1[写入请求] --> B2[WAL 顺序写入] B2 --> B3[MemTable<br/>内存中的有序结构] B3 --> B4[Immutable MemTable<br/>冻结等待刷盘] B4 --> B5[SSTable L0<br/>顺序写入磁盘] B5 --> B6[Compaction<br/>后台合并排序] end

B+Tree 的写入瓶颈。每次写入需要先写 Redo Log（顺序 I/O），再修改 Buffer Pool 中的数据页（内存操作），最后由后台线程将脏页刷回磁盘（随机 I/O）。关键瓶颈在于：如果 Buffer Pool 命中率低，写入会触发大量的随机 I/O 读操作（先将目标页从磁盘读入 Buffer Pool），这才是 B+Tree "写慢"的真正原因——不是写本身慢，而是写之前的读慢。

LSM-Tree 的写入优势与读取代价。LSM-Tree 的写入只涉及顺序 I/O（WAL + MemTable 刷盘），不需要随机 I/O 读。但读取时，需要在多个 Level 的 SSTable 中查找，最坏情况下需要检查 L0 的所有文件 + L1 到 Lmax 的各一个文件。Bloom Filter 可以大幅减少无效磁盘读取，但无法完全消除。

Compaction 的写入放大。LSM-Tree 的 Compaction 过程会产生写入放大。一次 L1 到 L2 的 Compaction，可能需要重写数十 GB 的数据。写入放大系数 = 实际磁盘写入量 / 用户写入量，通常在 10-30 倍之间。这意味着：用户写入 1GB 数据，磁盘实际写入 10-30GB。在 SSD 上，这直接影响磁盘寿命。

三、生产级 Benchmark 设计：可复现、可对比、可解释

以下是一个严谨的存储引擎 Benchmark 框架，核心原则是：控制变量、预热充分、统计可信。

import time import statistics import numpy as np from dataclasses import dataclass, field from typing import List, Callable @dataclass class BenchmarkConfig: """Benchmark 配置 关键设计：所有参数必须显式声明， 确保测试结果可复现 """ engine: str # 引擎类型 data_size: int # 数据量（行数） key_size: int # Key 大小（字节） value_size: int # Value 大小（字节） read_write_ratio: float # 读写比例（0.0-1.0，1.0=纯读） concurrency: int # 并发数 warmup_seconds: int # 预热时间（秒） measurement_seconds: int # 测量时间（秒） distribution: str # Key 分布：uniform / zipfian / latest seed: int # 随机种子，确保可复现 @dataclass class BenchmarkResult: """Benchmark 结果""" config: BenchmarkConfig latencies_ms: List[float] = field(default_factory=list) @property def p50(self) -> float: return np.percentile(self.latencies_ms, 50) @property def p99(self) -> float: return np.percentile(self.latencies_ms, 99) @property def p999(self) -> float: return np.percentile(self.latencies_ms, 99.9) @property def throughput(self) -> float: """QPS = 总请求数 / 总时间""" return len(self.latencies_ms) / self.config.measurement_seconds @property def mean_with_ci(self) -> tuple: """均值 + 95% 置信区间 使用 t 分布计算置信区间， 样本量不足时区间更宽， 避免过度自信 """ n = len(self.latencies_ms) mean = statistics.mean(self.latencies_ms) if n < 2: return mean, 0.0 std_err = statistics.stdev(self.latencies_ms) / (n ** 0.5) # t 分布 95% 置信度，自由度 n-1 # 简化：当 n > 30 时 t 值近似 1.96 t_value = 1.96 if n > 30 else 2.0 # 保守估计 ci = t_value * std_err return mean, ci class StorageBenchmark: """存储引擎 Benchmark 框架 核心原则： 1. 预热阶段不计入结果 2. 使用百分位延迟而非均值 3. 报告置信区间 4. 控制随机种子确保可复现 """ def __init__(self, config: BenchmarkConfig): self.config = config self.rng = np.random.default_rng(config.seed) def run(self, write_fn: Callable, read_fn: Callable) -> BenchmarkResult: """执行 Benchmark write_fn/read_fn: 实际的读写函数， 由调用方根据引擎类型提供 """ result = BenchmarkResult(config=self.config) # 阶段一：预热 print(f"预热阶段：{self.config.warmup_seconds} 秒") warmup_end = time.time() + self.config.warmup_seconds while time.time() < warmup_end: self._execute_operation(write_fn, read_fn) # 阶段二：正式测量 print(f"测量阶段：{self.config.measurement_seconds} 秒") measure_end = time.time() + self.config.measurement_seconds while time.time() < measure_end: latency = self._execute_operation(write_fn, read_fn) result.latencies_ms.append(latency) # 输出结果 mean, ci = result.mean_with_ci print(f"引擎: {self.config.engine}") print(f"QPS: {result.throughput:.1f}") print(f"P50: {result.p50:.2f}ms") print(f"P99: {result.p99:.2f}ms") print(f"P999: {result.p999:.2f}ms") print(f"均值: {mean:.2f}ms (95% CI: ±{ci:.2f}ms)") return result def _execute_operation(self, write_fn: Callable, read_fn: Callable) -> float: """执行单次读写操作，返回延迟（ms）""" # 根据读写比例决定操作类型 is_read = self.rng.random() < self.config.read_write_ratio # 生成 Key：根据分布类型 key = self._generate_key() start = time.perf_counter() if is_read: read_fn(key) else: value = self.rng.bytes(self.config.value_size) write_fn(key, value) elapsed = (time.perf_counter() - start) * 1000 return elapsed def _generate_key(self) -> bytes: """根据配置的分布类型生成 Key""" if self.config.distribution == 'uniform': key_int = self.rng.integers(0, self.config.data_size) elif self.config.distribution == 'zipfian': # Zipf 分布模拟热点访问 key_int = self.rng.zipf(1.5) % self.config.data_size elif self.config.distribution == 'latest': # Latest 分布：倾向于访问最近写入的 Key key_int = self.config.data_size - self.rng.integers( 0, min(1000, self.config.data_size)) else: key_int = self.rng.integers(0, self.config.data_size) return str(key_int).zfill(self.config.key_size).encode()

四、Benchmark 的常见陷阱与可信度保障

预热不充分。B+Tree 的 Buffer Pool 需要预热才能达到稳定命中率，LSM-Tree 的 Block Cache 同理。如果预热时间不够，前几次查询的延迟会异常高，拉高整体百分位数。建议：预热时间至少为测量时间的 20%，且预热期间的操作模式必须与正式测量一致。

数据分布不真实。很多 Benchmark 使用均匀分布（Uniform）生成 Key，但真实业务的数据访问通常呈 Zipf 分布——少数热点 Key 占据大部分访问。均匀分布下的性能数据无法代表真实场景。建议：至少测试 Uniform 和 Zipfian 两种分布，重点关注 Zipfian 下的 P99 延迟。

忽略 Compaction 影响。LSM-Tree 的 Compaction 会占用磁盘 I/O 带宽和 CPU，导致查询延迟出现毛刺。如果 Benchmark 时间太短，可能恰好避开了 Compaction，得到过于乐观的结果。建议：Benchmark 持续时间至少 30 分钟，确保覆盖完整的 Compaction 周期。

统计方法不严谨。只报告均值和最大值是远远不够的。均值会被长尾延迟稀释，最大值受极端异常值影响。必须报告 P50、P99、P999 百分位延迟，以及均值的 95% 置信区间。两次 Benchmark 的结果如果置信区间重叠，就不能断言"某引擎更快"。