分布式 KV 存储的 LSM-Tree 合并策略分层压缩与读放大的工程平衡一、读请求的磁盘 IO 次数从 1 次变成了 7 次在一个基于 LSM-Tree 的分布式 KV 存储中。写入性能一直稳定在 50K QPS。但读请求的 p99 延迟从最初的 3ms 恶化到了 22ms。查询一个 Key 的值时。Perf 追踪显示需要遍历 7 层 SSTable 文件。每次查询触发一次磁盘 IO从文件末尾的 Bloom Filter Index Block 读取开始。LSM-Tree 写多读少的优势逐渐被读放大侵蚀。根源在于后台的 Compaction 跟不上写入的速度。Level 0 文件堆叠过多。数据分布在各层之间。一个 Key 的最新值可能在更深层。查询需要回溯多层。核心矛盾是 Compaction 的资源分配。太激进消耗 IO 带宽影响前台读写。太保守则读放大恶化。需要在写入放大Write Amplification、读放大Read Amplification和空间放大Space Amplification三者之间找到最优平衡点。二、LSM-Tree 的分层压缩策略与三放大权衡LSM-Tree 的 Compaction 决定了三放大之间的权衡。分层压缩Leveled Compaction和大小分级压缩Size-Tiered Compaction是这个权衡的两个极端。graph TD A[写入请求] -- B[MemTable] B -- C[Immutable MemTable] C -- D[Level 0 SSTable(s)] D -- E[Compaction: L0 → L1] subgraph 分层压缩策略 E -- F[Level 1 (10MB × 10个)] F -- G[Compaction: L1 → L2] G -- H[Level 2 (100MB × 10个)] H -- I[Compaction: L2 → L3] I -- J[Level 3 (1GB × 10个)] end subgraph 三放大指标 K[写放大 WA 总写IO / 用户写IO] L[读放大 RA 每查询平均读IO次数] M[空间放大 SA 总空间 / 用户数据空间] end D -- K E -- K J -- L J -- M分层压缩策略中每层的大小是上一层的固定倍数通常为 10。Level i 的单个 SSTable 与 Level i1 中重叠的 SSTable 合并。这种策略的空间放大最小。但写放大最高。因为同一条数据向下每经过一层都要被重新写入一次。读放大可以通过多种技术缓解。Bloom Filter 在每个 SSTable 前快速排除不存在的 Key。Index Block 二分定位 Key 在文件中的大致位置。Fence Pointer 进一步缩小扫描范围。三者配合将读 IO 从扫描整个 SSTable降低到12 次 IO。但 Bloom Filter 并非万能。它的误报率False Positive Rate通常设为 1%。在 Level 较多时累积误报可能变得显著。例如 7 层每层 1% 误报率。累积误报率约为 6.8%。误报会导致一次无意义的磁盘读取。三、Compaction 调度器的实现use std::cmp::Reverse; use std::collections::{BinaryHeap, HashMap}; use std::sync::Arc; use std::time::Instant; use tokio::sync::RwLock; /// SSTable 文件元数据 #[derive(Clone, Debug)] struct SstMetadata { file_id: u64, level: usize, /// 文件大小字节 size: u64, /// Key 范围 [min, max] min_key: Vecu8, max_key: Vecu8, /// Bloom Filter 的误报率 bloom_fpr: f64, /// 创建时间用于判断是否需要进行 Compaction created_at: Instant, } /// Compaction 调度器 /// /// 设计目标 /// 1. 优先合并重叠最多的 Level 以减少读放大 /// 2. 限制单次 Compaction 的数据量避免阻塞前台流量 /// 3. 基于优先级评分确保最需要的 Compaction 最先执行 struct CompactionScheduler { /// 各层 SSTable 文件清单 levels: ArcRwLockVecVecSstMetadata, /// 待执行的 Compaction 任务优先级队列 pending_queue: ArcRwLockBinaryHeapReverseCompactionTask, /// 最大并发 Compaction 数 max_concurrent: usize, /// 单次 Compaction 最大数据量字节 /// 防止大 Compaction 占用全部 IO 带宽影响前台读写 max_compaction_bytes: u64, } /// Compaction 任务 #[derive(Clone, Debug, Eq, PartialEq)] struct CompactionTask { /// 源层 source_level: usize, /// 参与合并的源文件 source_files: VecSstMetadata, /// 目标层的重叠文件 overlapping_files: VecSstMetadata, /// 优先级分数越高越优先 score: u64, } // 按分数排序Reverse 使得分数高的在前 impl Ord for CompactionTask { fn cmp(self, other: Self) - std::cmp::Ordering { self.score.cmp(other.score) } } impl PartialOrd for CompactionTask { fn partial_cmp(self, other: Self) - Optionstd::cmp::Ordering { Some(self.cmp(other)) } } impl CompactionScheduler { fn new(max_concurrent: usize, max_compaction_bytes: u64) - Self { Self { levels: Arc::new(RwLock::new(Vec::new())), pending_queue: Arc::new(RwLock::new(BinaryHeap::new())), max_concurrent, max_compaction_bytes, } } /// 计算 Compaction 优先级 /// /// 分数计算公式 /// score read_amplification_factor * 1000 /// level_overlap_ratio * 500 /// - compaction_bytes / 1MB (惩罚过大的 Compaction) /// /// 为什么这样设计 /// - 读放大是最迫切需要解决的问题权重最高 /// - Level 重叠越多单次查询需要访问的文件越多 /// - 过大的 Compaction 会阻塞前台 IO应延后处理 fn calculate_score(self, level: usize, files: [SstMetadata]) - u64 { let read_amp files.len() as u64; let overlap self.estimate_overlap(files); let total_size: u64 files.iter().map(|f| f.size).sum(); // 每 1MB 减去 1 分防止大 Compaction 排在前方 let size_penalty total_size / (1024 * 1024); read_amp * 1000 overlap * 500 - size_penalty } /// 估算文件间的 Key 重叠度 /// 重叠度越高读放大越严重 fn estimate_overlap(self, files: [SstMetadata]) - u64 { if files.len() 2 { return 0; } let mut overlap_count 0u64; for i in 0..files.len() { for j in (i 1)..files.len() { // 判断两个文件的 Key 范围是否有重叠 if files[i].min_key files[j].max_key files[j].min_key files[i].max_key { overlap_count 1; } } } overlap_count } /// 扫描所有层生成 Compaction 任务 /// /// 触发条件满足任一即触发 /// 1. Level 0 文件数超过 4 个L0 文件间 Key 可能重叠 /// 2. 某层的总大小超过下一层的预设比例 /// 3. 某个文件的 Bloom Filter 误报率过高5% async fn schedule_compactions(self) { let levels self.levels.read().await; for level in 0..levels.len() { let trigger self.should_compact(level, levels); if let Some(task) trigger { let score self.calculate_score(level, task.source_files); let mut queue self.pending_queue.write().await; queue.push(Reverse(CompactionTask { source_level: level, source_files: task.source_files, overlapping_files: task.overlapping_files, score, })); } } } /// 判断某层是否需要 Compaction fn should_compact( self, level: usize, levels: [VecSstMetadata], ) - OptionCompactionTrigger { let current levels[level]; // Level 0 特别处理文件数超过 4 个时触发 // 原因L0 文件间 Key 可能重叠查询需要访问所有 L0 文件 if level 0 current.len() 4 { return Some(CompactionTrigger { source_files: current.clone(), overlapping_files: self.find_overlapping(level 1, current, levels), }); } // 其他层当总大小超过 10MB × 10^level 时触发 let target_size 10 * 1024 * 1024 * 10u64.pow(level as u32); let current_size: u64 current.iter().map(|f| f.size).sum(); if current_size target_size { // 选择参与 Compaction 的文件 // 策略选取重叠最多的文件组合 // 这里使用贪心——选文件大小占比最大的部分 let mut selected Vec::new(); let mut selected_size 0u64; for file in current.iter().sorted_by_key(|f| Reverse(f.size)) { if selected_size file.size self.max_compaction_bytes { break; } selected.push(file.clone()); selected_size file.size; } if !selected.is_empty() { return Some(CompactionTrigger { source_files: selected, overlapping_files: self.find_overlapping( level 1, selected, levels, ), }); } } None } fn find_overlapping( self, target_level: usize, source: [SstMetadata], levels: [VecSstMetadata], ) - VecSstMetadata { if target_level levels.len() { return Vec::new(); } let target levels[target_level]; let mut overlapping Vec::new(); for t in target { for s in source { if s.min_key t.max_key t.min_key s.max_key { overlapping.push(t.clone()); break; } } } overlapping } } struct CompactionTrigger { source_files: VecSstMetadata, overlapping_files: VecSstMetadata, }优先级评分的计算公式是调度器设计中最核心的部分。读放大文件数的权重最高×1000。因为这直接对应每次查询需要做的磁盘 IO 次数。Key 重叠度次之。数据量惩罚项用于避免过于庞大的 Compaction 阻塞前台流量。Level 0 的特殊处理是 LSM-Tree 实现中的关键点。Level 0 的 SSTable 通常直接由 MemTable Flush 生成。文件之间 Key 范围可能重叠。Level 1 及以上则保证同一层文件 Key 不重叠。这个差异意味着 Level 0 的读放大最严重。必须优先 Compaction。四、Compaction 策略的工程选择指引不同的业务场景需要不同的 Compaction 策略侧重。对于写密集型场景如时序数据、日志存储。写放大是首要关注指标。大小分级压缩Size-Tiered的写放大远低于分层压缩。适合写 QPS 极高、存储空间充足的场景。代价是读放大和空间放大更高。对于读密集型场景如用户配置、缓存数据。读放大是首要关注指标。分层压缩Leveled是最优选择。它保证每层只有一个文件包含给定 Key 的数据。查询的单层 IO 次数为 1。代价是写放大高。每条数据从 MemTable 下沉到最深层需要被重写 log(N) 次。对于混合负载场景。动态调整策略是更务实的选择。在业务高峰期降低 Compaction 的 IO 带宽分配。优先服务前台读写。在低峰期加速 Compaction 清理积压。带宽控制可以通过 cgroup blkio 或自定义 IO Rate Limiter 实现。五、总结LSM-Tree 的三放大写、读、空间是不可同时最小化的矛盾体。Compaction 策略的选择是在三者之间做工程权衡。分层压缩Leveled最小化读放大和空间放大。代价是写放大高。适合读密集型场景。优先级调度让最紧迫的 Compaction 先执行。评分公式中读放大的权重应最高。因为读延迟直接影响用户体验。Level 0 需要特殊处理。L0 文件间 Key 可重叠。文件数超过 4 时查询需访问全部 L0 文件。是读放大的主要来源。在高并发生产环境中必须对 Compaction 的 IO 带宽设置上限。避免争抢前台读写的 IO 资源。