mini-lsm通关笔记Week2Day2

标签：mini Week2Day2 level SST lsm 合并 snapshot compaction L0

项目地址：https://github.com/skyzh/mini-lsm

个人实现地址：https://gitee.com/cnyuyang/mini-lsm

Summary

在本章中，您将：

要将测试用例复制到启动器代码中并运行它们，

实现一个simple leveled合并策略，并在合并模拟器上进行仿真。
将compaction作为后台任务启动，并在系统中实现一个compaction触发器。

cargo x copy-test --week 2 --day 2
cargo x scheck

Task 1-Simple Leveled Compaction

在本章中，我们将实现我们的第一个合并策略-simple leveled合并。在此任务中，您需要修改：
src/compact/simple_leveled.rs
simple leveled合并类似于原始LSM论文的合并策略。它维护LSM树的多个级别。当一个级别（>=L1）过大时，它会将这个级别的所有SST与下一个级别合并。Compaction策略由SimpleLeveledCompactionOptions中定义的3个参数控制：

size_ratio_percent：下一级文件数/上一级文件数。实际上，我们应该计算文件的实际大小。但是，我们将公式简化为使用文件数，以便更容易地进行模拟。当比率太低（上层的文件太多）时，我们应该触发一个Compaction。

level0_file_num_compaction_trigger：当L0中SST的个数大于等于该个数时，触发L0和L1的合并。

max_levels:LSM树的层数（不包括L0）。

假设size_ratio_percent=200（下级应该有2倍于上级的文件数量）,max_levels=3,level0_file_num_compaction_trigger=2，我们来看下面的例子。

假设存储引擎转储了两个L0 SST。这达到了level0_file_num_compaction_trigger，你的控制器应该触发L0->L1的合并。
--- After Flush ---
L0 (2): [1, 2]
L1 (0): []
L2 (0): []
L3 (0): []
--- After Compaction ---
L0 (0): []
L1 (2): [3, 4]
L2 (0): []
L3 (0): []
现在，L2是空的，而L1有两个文件。L1和L2的大小比例百分比为(L2/L1) * 100 = (0/2) * 100 = 0 < size_ratio_percent (200)。因此，我们将触发L1+L2合并，将数据合并到L2。L2也是如此，这两个SST将在2次合并后放置在最底层。
--- After Compaction ---
L0 (0): []
L1 (0): []
L2 (2): [5, 6]
L3 (0): []
--- After Compaction ---
L0 (0): []
L1 (0): []
L2 (0): []
L3 (2): [7, 8]
继续转储SST，我们会发现：
L0 (0): []
L1 (0): []
L2 (2): [13, 14]
L3 (2): [7, 8]
此时，L3/L2= (1 / 1) * 100 = 100 < size_ratio_percent (200)。因此，我们需要在L2和L3之间触发一个compaction。
--- After Compaction ---
L0 (0): []
L1 (0): []
L2 (0): []
L3 (4): [15, 16, 17, 18]
当我们转储更多的SST时，我们可能最终处于如下状态：
--- After Flush ---
L0 (2): [19, 20]
L1 (0): []
L2 (0): []
L3 (4): [15, 16, 17, 18]
--- After Compaction ---
L0 (0): []
L1 (0): []
L2 (2): [23, 24]
L3 (4): [15, 16, 17, 18]
因为L3/L2 = (4 / 2) * 100 = 200 >= size_ratio_percent (200)，所以我们不需要合并L2和L3，最终会得到上面的状态。simple leveled合并策略总是合并一个完整的层，并在层之间保持扇出大小，这样低层总是比高层大一些倍数。

我们已经将LSM状态中的levels属性初始化为具有max_level个空的Vec。你应该首先实现generate_compaction_task，它根据上面的3个条件生成一个compaction任务。之后再实现apply_compaction_result。我们建议您首先实现level0_file_num_compaction_trigger合并条件，运行compaction-simulator，然后实现size_ratio_percent合并条件，然后运行compaction-simulator。运行compaction-simulator：
cargo run --bin compaction-simulator-ref simple # Reference solution
cargo run --bin compaction-simulator simple # Your solution
模拟器会转储L0 SST，运行您的compaction控制器以生成compaction任务，然后应用compaction结果。每次刷新一个新的SST时，它都会重复调用控制器，直到没有需要调度的compaction为止，因此你应该确保你的compaction任务生成器会收敛。

在您的compaction实现中，您应该尽可能减少活动迭代器的数量（即使用concat迭代器）。此外，请记住，合并顺序很重要，当一个键的多个版本出现时，您需要确保创建的迭代器以正确的顺序生成键值对。

另外，请注意，实现中有些参数是基于0的，有些是基于1的。在向量中使用级别作为索引时要小心。

注意：这部分我们不提供细粒度的单元测试。您可以运行compaction模拟器，并与参考解决方案的输出进行比较，以查看您的实现是否正确。

这个任务只需要修改simple_leveled.rs文件，实现其中的两个函数

generate_compaction_task：用于生成SimpleLeveled策略的合并任务。输入参数snapshot: &LsmStorageStateLSM当前的状态，输出参数Option<SimpleLeveledCompactionTask>一个SimpleLeveled策略的合并任务。
apply_compaction_result：合并任务执行后，用于生成新的LSM状态。输入参数snapshot: &LsmStorageStateLSM当前的状态、SimpleLeveledCompactionTask执行的SimpleLeveled策略的合并任务。output执行任务后新生成的SST。输出参数LsmStorageState新的LSM状态，Vec<usize>需要被删除的SST。

generate_compaction_task

按照任务书中描述的，level0_file_num_compaction_trigger、size_ratio_percent两个参数可以用于控制是否生成任务。

将L0到Lx中各层的SST数量存储到level_sizes中
计算Lx+1数量与Lx数量之比存储到size_ratio
当前计算出的size_ratio与size_ratio_percent比较，若大于则生成一个新的合并任务

pub fn generate_compaction_task(
    &self,
    snapshot: &LsmStorageState,
) -> Option<SimpleLeveledCompactionTask> {
    let mut level_sizes = Vec::new();
    // 将L0中的SST数量存储到level_sizes中
    level_sizes.push(snapshot.l0_sstables.len());
    // 将L1到Lx中的SST数量存储到level_sizes中
    for (_, files) in &snapshot.levels {
        level_sizes.push(files.len());
    }


    for i in 0..self.options.max_levels {
        if i == 0
            && snapshot.l0_sstables.len() < self.options.level0_file_num_compaction_trigger
        {
            continue;
        }

        let lower_level = i + 1;
        // 计算Lx+1数量与Lx数量之比存储到size_ratio
        let size_ratio = level_sizes[lower_level] as f64 / level_sizes[i] as f64;
        // 当前计算出的size_ratio与size_ratio_percent比较，若大于则生成一个新的合并任务
        if size_ratio < self.options.size_ratio_percent as f64 / 100.0 {
            println!(
                "compaction triggered at level {} and {} with size ratio {}",
                i, lower_level, size_ratio
            );
            return Some(SimpleLeveledCompactionTask {
                upper_level: if i == 0 { None } else { Some(i) },
                upper_level_sst_ids: if i == 0 {
                    snapshot.l0_sstables.clone()
                } else {
                    snapshot.levels[i - 1].1.clone()
                },
                lower_level,
                lower_level_sst_ids: snapshot.levels[lower_level - 1].1.clone(),
                is_lower_level_bottom_level: lower_level == self.options.max_levels,
            });
        }
    }
    None
}

apply_compaction_result

合并L0和L1中的SST，将合并生成的新SST放在下层，L0中的SST不能直接删除，因为存在刚转储出来的SST。

合并L1以上的SST，将合并生成的新SST放在下层，历史的SST都需要被删除。

pub fn apply_compaction_result(
    &self,
    snapshot: &LsmStorageState,
    task: &SimpleLeveledCompactionTask,
    output: &[usize],
) -> (LsmStorageState, Vec<usize>) {
    let mut snapshot = snapshot.clone();
    let mut files_to_remove = Vec::new();
    if let Some(upper_level) = task.upper_level {
        assert_eq!(
            task.upper_level_sst_ids,
            snapshot.levels[upper_level - 1].1,
            "sst mismatched"
        );
        files_to_remove.extend(&snapshot.levels[upper_level - 1].1);
        snapshot.levels[upper_level - 1].1.clear();
    } else {
        files_to_remove.extend(&task.upper_level_sst_ids);
        let mut l0_ssts_compacted = task
            .upper_level_sst_ids
            .iter()
            .copied()
            .collect::<HashSet<_>>();
        let new_l0_sstables = snapshot
            .l0_sstables
            .iter()
            .copied()
            .filter(|x| !l0_ssts_compacted.remove(x))
            .collect::<Vec<_>>();
        assert!(l0_ssts_compacted.is_empty());
        snapshot.l0_sstables = new_l0_sstables;
    }
    assert_eq!(
        task.lower_level_sst_ids,
        snapshot.levels[task.lower_level - 1].1,
        "sst mismatched"
    );
    files_to_remove.extend(&snapshot.levels[task.lower_level - 1].1);
    snapshot.levels[task.lower_level - 1].1 = output.to_vec();
    (snapshot, files_to_remove)
}

完成后，运行以下命令可以看到详细合并过程：

cargo run --bin compaction-simulator simple

Task 2-Compaction Thread

在此任务中，您需要修改：
src/compact.rs
现在您已经实现了合并策略，您需要在后台线程中运行它，以便在后台合并文件。在compact.rs中，trigger_compaction将每50ms调用一次，您需要：

生成一个compaction任务，如果没有需要调度的任务，则返回ok。

运行compaction并获得新SST的列表。

与上一章中实现的force_full_compaction类似，更新LSM状态。

trigger_compaction

trigger_compaction和转储一样，由合并线程每50ms调用一次。

调用generate_compaction_task生成任务
执行合并任务
更新LSM状态
移除需要被删除的SST

fn trigger_compaction(&self) -> Result<()> {
    let snapshot = {
        let garud = self.state.read();
        garud.clone()
    };
    // 调用generate_compaction_task生成任务
    let task = self
        .compaction_controller
        .generate_compaction_task(&snapshot);
    let Some(task) = task else {
        return Ok(());
    };

    // 执行合并任务
    let sstables = self.compact(&task)?;
    let output = sstables.iter().map(|x| x.sst_id()).collect::<Vec<_>>();
    {
        let _state_lock = self.state_lock.lock();
        let mut snapshot = self.state.read().as_ref().clone();
        for file_to_add in sstables {
            let result = snapshot.sstables.insert(file_to_add.sst_id(), file_to_add);
            assert!(result.is_none());
        }
        // 更新LSM状态
        let (mut snapshot, files_to_remove) = self
            .compaction_controller
            .apply_compaction_result(&snapshot, &task, &output);
        
        // 移除需要被删除的SST
        for file_to_remove in &files_to_remove {
            let result = snapshot.sstables.remove(file_to_remove);
            assert!(result.is_some(), "cannot remove {}.sst", file_to_remove);
            std::fs::remove_file(self.path_of_sst(*file_to_remove))?;
        }
        let mut state = self.state.write();
        *state = Arc::new(snapshot);
    }

    Ok(())
}

compact方法参考mini-lsm文件夹中的实现，就是构造迭代器生成新的SST，不再赘述。

查询路径

为了通过用例，需要修改lsm_storage.rs中的get、scan方法。由昨日只查询L1，改为需要查询所有级别的SST。

结果分析

运行完模拟器可以看到如下结果：

--- Statistics ---
Write Amplification: 263/50=5.260x
Maximum Space Usage: 62/50=1.240x
Read Amplification: 3x

其中写放大263/50=5.260x，代表在该种合并策略下，转储了50个SST因为触发的合并策略最终写入的SST的个数为263个，所以写放大为5.26。
最大空间利用62/50=1.240x，代表在该种合并策略下，最终存储了50个SST，在运行过程中，最多使用了62个SST的存储空间，所以最终的空间放大为1.240。
读放大3x，就是除L0外的levels会产生一次IO + L0中SST的个数。因为除L0外的levels都是排好序的，所以只产生一次IO。而L0中的SST不是排好序的，所以每个SST都会产生一次IO。

Task 3-Integrate with the Read Path

在此任务中，您需要修改：
src/lsm_storage.rs
现在您有多个级别的SST，您可以修改读取路径以包括来自新级别的SST。您需要更新scan/get函数以包括L1以下的所有级别。此外，您可能需要再次更改LsmStorageIterator内部类型。

要以交互方式测试您的实现，
cargo run --bin mini-lsm-cli-ref -- --compaction simple # reference solution
cargo run --bin mini-lsm-cli -- --compaction simple # your solution
然后，
fill 1000 3000
flush
fill 1000 3000
flush
fill 1000 3000
flush
get 2333
scan 2000 2333
当合并器触发合并时，你可能会打印一些东西，例如合并任务信息。

同样的需要，运行需要带上参数--path：

cargo run --bin mini-lsm-cli-ref -- --compaction simple --path /tmp/lsm
cargo run --bin mini-lsm-cli -- --compaction simple --path /tmp/lsm

完成任务二后，本任务应该能直接跑通。

标签：mini,Week2Day2,level,SST,lsm,合并,snapshot,compaction,L0
From： https://www.cnblogs.com/cnyuyang/p/18431984