Mini-LSM Week2 Day 1,2,3,4

(Updated: )
KV
, 
实现多种压缩策略，并讨论读放大，写放大，空间放大

读放大：一次Get需要的磁盘IO请求
写放大：实际写入磁盘的字节数与逻辑写入字节数的比值。

  • 如果不进行压缩，那么将内存表的数据刷盘成为SST，那么此时写入放大就是1:1; 压缩是写放大的来源。
  • 由于字节数不好估算，一般使用SST个数来估算写放大: 假设每次刷新SST后都要压缩，依次写入100个文件，那么合并的文件数量就是2+3+4+100 约等于5000；写放大估算为50倍
    空间放大: 磁盘实际占用空间与逻辑数据大小之比。来源于同一个Key的多个版本,包含墓碑。
  • 使用total_size/last_level_size估算, 假定用户填充初始数据后，工作负载的插入和删除率应该相同, 用户数据大小不变，最后一级包含某个时间点的数据快照，上层是增量更新
    Sorted Run: 一次刷新或者一次压缩的产物，指一组键值互不重叠的SST

总览

核心的数据结构一共就三个:

  • CompactionTask: 定义了压缩算法需要的资源
  • CompactionOptions: 定义压缩算法的配置信息
  • CompactionController: 根据配置生成 压缩任务，并且应用压缩任务的更改。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    pub enum CompactionTask {
        Leveled(LeveledCompactionTask),
        Tiered(TieredCompactionTask),
        Simple(SimpleLeveledCompactionTask),
        ForceFullCompaction {
            l0_sstables: Vec<usize>,
            l1_sstables: Vec<usize>,
        },
    }
    // 
    pub enum CompactionOptions {
        /// Leveled compaction with partial compaction + dynamic level support (= RocksDB's Leveled
        /// Compaction)
        Leveled(LeveledCompactionOptions),
        /// Tiered compaction (= RocksDB's universal compaction)
        Tiered(TieredCompactionOptions),
        /// Simple leveled compaction
        Simple(SimpleLeveledCompactionOptions),
        /// In no compaction mode (week 1), always flush to L0
        NoCompaction,
    }

    pub(crate) enum CompactionController {
        Leveled(LeveledCompactionController),
        Tiered(TieredCompactionController),
        Simple(SimpleLeveledCompactionController),
        NoCompaction,
    }

压缩

全量压缩实现

实现从L0->L1的全量压缩，快速上手Mini-LSM的压缩流程

思路: 使用合并迭代器合并所有的L0 SST并生成新的SST,修改元数据,删除旧文件
关键函数:

  • force_full_compaction: 体现了完整地压缩流程.
    • 获取当前快照,根据L0和L1信息生成压缩任务,释放快照
    • 执行实际的压缩,并返回压缩生成的新SSTs
    • 获取state_lock, 拷贝快照, 生成新的元数据并替换,随后释放锁
    • 删除被合并的文件

      后台压缩不影响前台读写流程,锁的颗粒度要尽可能小。将IO等放在关键临界区之外，思路之前几章体现过了

关注压缩函数的实现: 获取快照和要压缩的SST，创建SST迭代器并且按照L0->L1的顺序来使用合并迭代器合并,如果要压缩到最后一层，再使用FusedIterator删除墓碑值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
fn compact(&self, task: &CompactionTask) -> Result<Vec<Arc<SsTable>>> {
		// 根据任务信息判断压缩是否涉及最后一层数据,如果是，那么压缩时需要删除墓碑值
		// 也就是使用FusedIterator来规范行为
        let compact_to_bottom_level = task.compact_to_bottom_level();
        let snapshot = self.state.read().clone();

        match task {
            CompactionTask::ForceFullCompaction {
                l0_sstables,
                l1_sstables,
            } => {
	            // 获取 l0_sst, l1_sst
                let mut iters_to_merge = Vec::with_capacity(l0_ssts.len() + l1_ssts.len());
                for l0_sst in l0_ssts {
                    iters_to_merge
                        .push(Box::new(SsTableIterator::create_and_seek_to_first(l0_sst)?));
                }
                for l1_sst in l1_ssts {
                    iters_to_merge
                        .push(Box::new(SsTableIterator::create_and_seek_to_first(l1_sst)?));
                }

                if compact_to_bottom_level {
                    let mut iter = FusedIterator::new(MergeIterator::create(iters_to_merge));
                    self.do_compact(&mut iter)
                } else {
                    let mut iter = MergeIterator::create(iters_to_merge);
                    self.do_compact(&mut iter)
                }
            }
            __ => unimplemented!()
        }
    }

由于要支持多种不同的迭代器实现压缩函数,因此封装一层。得益于良好的模块化设计,压缩函数只需要一些胶水代码。

  • 拆分超过target_sst_size的Builder
  • 结束最后一个未超过target_sst_size的Builder
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    fn do_compact<I>(&self, iter: &mut I) -> Result<Vec<Arc<SsTable>>>
        where
            I: for<'a> StorageIterator<KeyType<'a> = KeySlice<'a>>,
        {
            let mut new_ssts = Vec::new();
            let mut builder = SsTableBuilder::new(self.options.block_size);

            while iter.is_valid() {
                builder.add(iter.key(), iter.value());
                iter.next()?;
                if builder.estimated_size() >= self.options.target_sst_size {
                    let finished_builder =
                        std::mem::replace(&mut builder, SsTableBuilder::new(self.options.block_size));
                    let sst_id = self.next_sst_id();
                    let sst = finished_builder.build(
                        sst_id,
                        Some(self.block_cache.clone()),
                        self.path_of_sst(sst_id),
                    )?;
                    new_ssts.push(Arc::new(sst));
                }
            }

            if builder.estimated_size() > 0 {
                let sst_id = self.next_sst_id();
                let sst = builder.build(
                    sst_id,
                    Some(self.block_cache.clone()),
                    self.path_of_sst(sst_id),
                )?;
                new_ssts.push(Arc::new(sst));
            }

            Ok(new_ssts)
        }
    根据新生成的SST来修改元数据:
  • 由于只有一个线程参与压缩,因此只需要 移除L0中参与压缩的SST, 清空L1中原有的SST,并设置为压缩产物

连接迭代器

实现压缩后,L1的SST就是有序互不重叠的了,过去的逐个创建SstTabelIterator迭代器然后合并的读取方式引入了额外开销，事实上，我们可以连接这些迭代器，每次只读取当前使用SST的数据

1
2
3
4
5
pub struct SstConcatIterator {
    current: Option<SsTableIterator>,
    next_sst_idx: usize,
    sstables: Vec<Arc<SsTable>>,
}

这个迭代器的实现难点在于create_and_seek_to_key需要定位到第一个>=key的位置:

  • 如果ssts为空,返回一个无效的迭代器
  • 找到最后一个sst.first_key().as_key_slice() <= key的位置并创建迭代器，如果成功，直接返回，否则判断是否还有下一个位置可以用于创建迭代器，如果有，create_and_seek_first
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    pub fn create_and_seek_to_key(sstables: Vec<Arc<SsTable>>, key: KeySlice) -> Result<Self> {
            if sstables.is_empty() {
                return Ok(Self {
                    current: None,
                    next_sst_idx: 0,
                    sstables,
                });
            }

            let idx = sstables
                .partition_point(|sst| sst.first_key().as_key_slice() <= key)
                .saturating_sub(1);

            let (current, next_sst_idx) =
                match SsTableIterator::create_and_seek_to_key(sstables[idx].clone(), key) {
                    Ok(iter) => (Some(iter), idx + 1),
                    Err(_) => {
                        let next_idx = idx + 1;
                        if next_idx < sstables.len() {
                            (
                                Some(SsTableIterator::create_and_seek_to_first(
                                    sstables[next_idx].clone(),
                                )?),
                                next_idx + 1,
                            )
                        } else {
                            (None, sstables.len())
                        }
                    }
                };

            Ok(Self {
                current,
                next_sst_idx,
                sstables,
            })
        }
    }

集成到读取路径

将L1 Iterator从Merged<SstIter>替换为SstConcateIter

思考

  • 鉴于压缩占用大量写入带宽和读取带宽，并可能干扰前台操作，当有大量写入流时推迟压缩是一个好主意。在这种情况下甚至停止/暂停现有的压缩任务是有益的。你对此有何看法？
    • 更重要的是做流量控制，而不是简单的开关，需要平衡 前台延迟、空间占用、稳定性
    • 在高峰期暂停压缩确实可以 减少前台延迟，但是也会造成L0文件的迅速堆积，空间占用膨胀
    • 可以根据写入流量来决定压缩频率：
      • 前台写入轻：不限制压缩线程
      • 前台负载加重： 对于压缩线程限流 或 减少压缩频率
      • 短时突发大量写入：暂停压缩线程
      • L0文件堆积过多，严重影响读取： 暂停前台写入，紧急压缩L0,L1来环节压力
  • 为压缩使用/填充块缓存是一个好主意吗？还是在压缩时完全绕过块缓存更好？
    • 压缩时的数据大部分都是冷数据且只读取一次，使用块缓存污染缓存，影响热点数据，一般情况不建议使用；如果是由于读取压力(seek_compaction)引起的合并即压缩文件和负载有部分重叠，此时使用块缓存会更好
  • 在系统中拥有 struct ConcatIterator<I: StorageIterator> 有意义吗？
    • 没有意义，增加了系统设计的复杂度，迭代器完全可以等到使用时创建，提前创建与设计目标背离
  • 一些研究人员/工程师提议将压缩卸载到远程服务器或无服务器 lambda 函数。远程压缩的好处是什么，以及远程压缩可能带来的潜在挑战和性能影响是什么？（思考压缩完成时以及下一个读取请求时块缓存会发生什么…）
    • 减少了主机CPU使用，并且可以弹性扩容，即使压缩崩溃也不会影响主机
    • 引入了额外的通信开销和管理开销，对于小范围压缩得不偿失；没办法预热块缓存

简单层级压缩

在全量合并的基础上引入了多个层级,并且根据层级之间文件比例触发压缩

关键数据结构:

  • 压缩选项
    • max_levels: 判断压缩任务是否要压缩到底层
    • level0_file_num_compaction_trigger: 用于触发L0->L1的压缩过程
    • size_ratio_percent: 如果 lower_level_size/upper_level_size < size_ratio/100,那么触发层级间的全量压缩
  • 压缩任务:
    • if upper_level is None, then it is L0 compaction
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      pub struct SimpleLeveledCompactionOptions {
          pub size_ratio_percent: usize,
          pub level0_file_num_compaction_trigger: usize,
          pub max_levels: usize,
      }

      pub struct SimpleLeveledCompactionTask {
          pub upper_level: Option<usize>,
          pub upper_level_sst_ids: Vec<usize>,
          pub lower_level: usize,
          pub lower_level_sst_ids: Vec<usize>,
          pub is_lower_level_bottom_level: bool,
      }
      实现思路很明显:
  • generate_compact_task:
    • 判断l0 num是否达到阈值，达到则优先触发L0压缩
    • 按照level 1 -> Level N-1的顺序计算大小比例,决定是否触发size_compaction
  • compact:
    • 底层迭代器只会是L1~LN,因此使用SstConcateIterator来减少迭代器开销
    • 如果是L0压缩，使用MergeIter<SstTable>来获取L0数据，因为SST可能互相重叠。最后创建TwoMergeIter合并两个层级
    • 如果不是，那么上层也使用SstConcateIter,然后创建MergeIter合并两个层级
    • 根据是否压缩到最后一级，决定是否采用FusedIter
  • apply_compaction_result:
    • 清除掉压缩的sst,添加新的sst到对应层级

集成到读路径就是添加对于L1之下层级的访问

思考

  • 分级压缩的估计写放大是多少？
    • WA = 1 + L * (1+R): L表示每一层的大小, R表示size_ration
    • L0 -> L1 写入放大 = 1 + R (假设L1大小是L0的R倍)
    • Lk -> Lk+1 写入放大 = $R^{k-1} + R^{k}= R^{k-1}*(1+R)$
  • 分级压缩的估计读放大是多少？
    • RA = O(L) ; 每层最多一个
  • 只有当用户请求删除一个键并且它已在最底层被压缩时，该键才会从 LSM 树中清除，这是正确的吗？
    • 对
  • 定期对 LSM 树进行完全压缩是一个好策略吗？为什么或为什么不？
    • 不是一个好策略，因为对于两个层级而言，都是全量压缩；
  • 主动选择一些旧文件/级别进行压缩，即使它们不违反级别放大器，会是一个好选择吗？（查看 Lethe 论文！）
    • 如果能够切合用户负载，确定这些是冷数据，是一个好选择
  • 如果存储设备可以实现可持续的 1GB/s 写入吞吐量，并且 LSM 树的写放大为 10 倍，用户可以从 LSM 键值接口获得多少吞吐量？
    • 100MiB/s
  • 如果 L2 中有 SST 文件，你可以直接合并 L1 和 L3 吗？它仍然产生正确的结果吗？
    • 可以，但必须L2中的SST与L1、L3不重叠，此时结果是正确的
  • 到目前为止，我们假设我们的 SST 文件使用单调递增的 id 作为文件名。使用 <level>_<begin_key>_<end_key>.sst 作为 SST 文件名可以吗？这可能会有什么潜在问题？（你可以在第 3 周问自己同样的问题…）
    • 不可以,L0的SST是可以重叠的
    • 如果 L0_a_c_.sst 旧于 L0_b_d.sst , 但是查询 b 时会优先使用L0_a_c.sst

Tier / 分层压缩

一组Key互不重叠的SST称为一个Sorted Run (一次合并/一次压缩的产物)
Tiered Compaction的组织方式:

  • 将SST划分为由低到高的Tier,每一个Tier内部含有一个或多个Sorted Run,Tier内部是局部有序的
    由于不强制维护每一个Tier内部的有序性,采用Tier压缩的LSM-Tree写放大会减小,读放大会增大

刷新策略如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
初始状态: levels = []  (空)  
第一次 flush:  
→ levels = [(tier_id=1, [sst_1])]   // 新 tier 插入前面  
第二次 flush:  
→ levels = [(tier_id=2, [sst_2]), (tier_id=1, [sst_1])]  // 新 tier 插入前面  
第三次 flush:  
→ levels = [(3, [sst_3]), (2, [sst_2]), (1, [sst_1])]  
// levels[0] = 最新 tier，levels[last] = 最老 tier（底层）  
当 levels.len() >= num_tiers (例如 8):  
→ 触发 compaction，合并多个 tiers  
→ 新 tier 放到 levels 末尾（底层位置）  
关键点:
1. 每次 flush：新 sorted run 插入 levels.insert(0, ...)（最新位置）
2. levels 索引：levels[0] = 最新，levels[last] = 最老（底层）
3. 压缩触发条件：levels.len() >= num_tiers
4. 压缩后新 tier 位置：放到被移除 tiers 的位置之后（往底层方向）

这与 Simple Leveled Compaction 不同——tiered 没有 L0，所有 sorted run 都在 level

如果只采用num_tiers触发压缩,那么底层文件的压缩率不够高，空间放大明显,上层文件线性增长，读放大过大
因此引入额外的优化方案:

  • 空间放大触发：(非底层总大小/底层大小) >= max_size_amplification_percent * 1%
  • 大小比率触发：(当前tier/之前所有tier) > (100+size_ration) * 1% 并且待合并的tier数量 >= min_merge_width
  • 减少sorted run: 前两者都不触发,合并前max_merge_tiers个tier

代码实现时只需要注意apply_snapshot函数执行时刷新线程会刷入新的tier,合并的输出应该放在新tier之后

思考

  • 层级压缩的估计写放大是多少？（好吧，这很难估计…但如果没有最后的_减少排序运行_触发器呢？）
    • 用大小比率触发的size_ratio来估算, r= 1 + size_ratio/100,tiers大小为r^N,N为刷写次数,那么一个tier大小从1变化到r^N,需要被刷新的次数就是写放大的次数: log_r(N)
  • 层级压缩的估计读放大是多少？
    • tier数量
  • 与简单分级/分层压缩相比，通用压缩的优缺点是什么？
    • 写入放大比率 小
    • 空间放大和读取放大比率
  • 运行通用压缩需要多少存储空间（与用户数据大小相比）？
    • r = 1 + size_ratio/100; 峰值就是 1 + r; 正常运行约r
  • 如果两个层在 LSM 状态中不相邻，我们可以合并它们吗？
    • 除非两个层和中间层没有任何重叠的Key否则会导致访问到过期数据
  • 如果压缩速度跟不上分层压缩的 SST 刷新会发生什么？
    • 读取速度显著降低
    • 触发全量压缩导致写入暂停
  • 如果系统并行调度多个压缩任务，可能需要考虑什么？
    • 多个压缩任务的tier不能重叠
  • SSD 也写入自己的日志（基本上它是一个日志结构存储）。如果 SSD 的写放大为 2 倍，整个系统的端到端写放大是多少？相关：ZNS: Avoiding the Block Interface Tax for Flash-based SSDs。
    • 2 * WA
  • 考虑用户选择为分层压缩保留大量排序运行（即 300）的情况。为了使读取路径更快，保留一些数据结构来帮助减少在每个层中为某些键范围查找要读取的 SST 的时间复杂度（即到 O(log n)）是一个好主意吗？注意，通常，你需要在每个排序运行中进行二分查找以找到需要读取的键范围。（查看 Neon 的层映射实现！）
    • 当然是个好主意,能够有效减少文件读取和缓存颠簸

层级压缩

层级合并策略使用 下限阈值 + 层级比例 来约束层级大小, 有两个基本参数:

  • base_level_size: 在最底层大小超过base_level_size之前，使用中间层级是没有意义的，导致额外的写放大、读放大
  • level_size_multiplier: 层级大小比例
    举例说明:
    1
    2
    3
    4
    5
    6
    7
    当前最多有5个层级,不包括L0; base_level_size = 200MB; level_size_multiplier = 10;
    初始状态为空: []
    L0 SST Num >= Limit -> [0,0,0,0,30MB]
    持续刷新数据直到最后一层大小超过200MB,此时第四层才开始有意义
    Flush -> [0,0,0,5MB,300MB]; 第四层具有软上限 300MB/10 = 30MB
    Flush -> [0,0,0,40MB,300MB]; 当第四层的数据超过软上限但没有大于200MB之前,会将其和下一层合并从而扩容软上限,直到软上限超过200MB后数据才会写入第三层
    Flush & Compaction -> [0,0,0,201MB,2GB] ; 第三层可以写入数据,具有软上限20MB
    压缩策略如下:
  • 底层大小超过base_level_size之前持续压缩到底层
  • 底层大小超过base_level_size之后,计算上面层级的target_size, 压缩数据到第一个target_size > 0的层级(up -> down)
    • 如果某个层级的target_size < base_level_size,那么不应该计算它的上一级容量
  • 如果多个层级均被压缩,那么计算r = current_size / target_size; 压缩r最大的层级
  • 每次压缩只选择目标层级中最老的SST和下一层级重叠的SST

思考

  • 层级压缩的估计写放大是多少？
    • 假设Key均匀分布，下层大小是上层的M倍；每次压缩需要处理 1 + 1/M 文件, WA = (1 + 1/M) * num_levels
  • 层级压缩的估计读放大是多少？
    • L0 Num + Level
  • 为压缩找到一个好的键分割点可能会减少写放大，还是完全无关紧要？（考虑用户写入以某些前缀开头的键的情况，00 和 01。这两个前缀下的键数量不同，它们的写入模式也不同。如果我们总是可以将 00 和 01 分割到不同的 SST 中…）
    • 由于当前采用前缀编码模式，找到好的分割点可以减少单个SST的大小，减少无关KV的合并，从而减少写放大
  • 想象一个用户之前使用分层（通用）压缩，现在想要迁移到层级压缩。这种迁移可能面临什么挑战？如何进行迁移？
    • 挑战：无法保证每一层的Key Range 不重叠;
    • 迁移策略: 暂停写入，所有的当前tier压缩为最底层
  • 如果我们反向操作，如果用户想要从层级压缩迁移到分层压缩呢？
    • L0包含重叠KV，需要先压缩一遍
    • L1-Lmax由于压缩时不是全量压缩，因此无法保证sst id小的数据老,sst id大的数据新; 需要从底层到顶层开始，每一层压缩一遍当作tier
  • 如果系统并行调度多个压缩任务，可能需要考虑什么？
    • 不要选用重叠的SST
  • 层级压缩的峰值存储使用量是多少？与通用压缩相比呢？
  • 较低的 level_size_multiplier 是否总是能获得较低的写放大？
    • 不会，取值过小会导致一次写入触发多个层级的连续压缩的出现变得频繁
  • 如果完全不使用压缩的用户决定迁移到层级压缩，需要做什么？
    • 全量压缩一遍
  • 有些人建议在将 L0 表推送到较低层之前进行 L0 内部压缩（压缩 L0 表并仍将它们放在 L0 中）。这样做可能有什么好处？（可能相关：PebblesDB SOSP’17）
    • 减少 L0 -> L1 压缩涉及的文件，减少写入放大
    • L0有序，减少读放大
  • 考虑上层有两个表 [100, 200], [201, 300]，下层有 [50, 150], [151, 250], [251, 350] 的情况。在这种情况下，你仍然想一次压缩上层的一个文件吗？为什么？
    • 取决于工程上的权衡： 一次压缩上层的一个文件，会导致多次压缩，写放大较大；一次压缩多个，会导致压缩任务时间长，需要的带宽大，峰值空间使用量更大；在 性能和简单 之前权衡