Level 0内存化以及多Table实现关联

[KKould]

1. Leveled Compaction层次结构
2. Leveled Compaction Level 0 的性能瓶颈
3. SSTable结构解析
4. 拓展性SSTable示例：KipDB的SkipTable

Leveled Compaction层次结构

LevelDB中Leveled Compaction的LSM实现是由不同层级且虽等级逐步递增而以10的N次方逐级递增的SSTables组成。(类似金字塔)
同时除了Level 0外，其余Level内的SSTables的数据排布彼此连续且有序，但不同Level之间的数据则是交错且重复的，及上一层Level的数据为下一层Level更稀疏的数据范围

Leveled Compaction排列有序的结构非常适合于读多写少的场景。
数据读取时，通过类似二分的方式(以SSTable的min/max key)，可以直接确定数据可能存在的SSTable。
因此即使是大量数据的情况下(数据根据图上排布，使其充分形成金字塔型的排列)，也仅仅需要读取 10(Level 0) + 6 x 1(Level N)个SSTable即可查询到对应的数据。
Size-tired Compaction则会查询所有SSTable数据范围重复。。。读放大和空间放大直接爆炸

Leveled Compaction Level 0 的性能瓶颈

上述的Level 0的SSTable排布中，一直有Level 0除外的备注。
而Level 0作为MemTable到SSTables的缓冲层，导致Level 0中的SSTable是数据范围交错且非有序的，因此读取时需要读取所有的Level 0SSTable才能获取到对应Key的数据。
Level 0在Leveled Compaction中起着非常关键的作用；
Leveled Compaction分为两级Compaction

• Minor Compaction
• Major Compaction

Minor Compaction

Minor Compaction是轻量级的Compaction，主要将MemTable中的数据转移至Level 0中作为SSTable。

1. MemTable将数据切换至Immutable MemTable(只读)中

pub(crate) fn swap(&self) -> Result<Option<(i64, Vec<KeyValue>)>> {
    loop {
        if 0 == self.tx_count.load(Acquire) {
            let mut inner = self.inner.lock();
            // 二重检测防止lock时(前)突然出现事务
            // 当lock后，即使出现事务，会因为lock已被Compactor获取而无法读写，
            // 因此不会对读写进行干扰
            // 并且事务即使在lock后出现，所持有的seq为该压缩之前，
            // 也不会丢失该seq的_mem，因为转移到了_immut，可以从_immut得到对应seq的数据
            if 0 != self.tx_count.load(Acquire) {
                continue;
            }
            return if !inner._mem.is_empty() {
                inner.trigger.reset();

                let mut vec_data = inner
                    ._mem
                    .iter()
                    .map(|(k, v)| (k.key.clone(), v.clone()))
                    // rev以使用最后(最新)的key
                    .rev()
                    .unique_by(|(k, _)| k.clone())
                    .collect_vec();

                vec_data.reverse();

                inner._immut = Some(mem::replace(&mut inner._mem, SkipMap::new()));

                let new_gen = Gen::create();
                let new_writer = (inner.log_loader.writer(new_gen)?, new_gen);
                let (mut old_writer, old_gen) = mem::replace(&mut inner.log_writer, new_writer);
                old_writer.flush()?;

                Ok(Some((old_gen, vec_data)))
            } else {
                Ok(None)
            };
        }
        std::hint::spin_loop();
    }
}

2. Compactor线程读取Immutable MemTable数据，执行Minor Compaction进行持久化(SSTable)，放入至Level 0尾部

pub(crate) async fn check_then_compaction(
        &mut self,
        option_tx: Option<oneshot::Sender<()>>,
    ) -> Result<()> {
        if let Some((gen, values)) = self.mem_table().swap()? {
            if !values.is_empty() {
                let start = Instant::now();
                // 目前minor触发major时是同步进行的，所以此处对live_tag是在此方法体保持存活
                self.minor_compaction(gen, values).await?;
                info!("[Compactor][Compaction Drop][Time: {:?}]", start.elapsed());
            }
        }

        // 压缩请求响应
        if let Some(tx) = option_tx {
            tx.send(()).map_err(|_| KernelError::ChannelClose)?
        }

        Ok(())
    }

3. Minor Compaction执行完毕后，判断是否超出Level 0的SSTable数量阈值以触发Major Compactoin

/// 持久化immutable_table为SSTable
    ///
    /// 请注意：vec_values必须是依照key值有序的
    pub(crate) async fn minor_compaction(&self, gen: i64, values: Vec<KeyValue>) -> Result<()> {
        if !values.is_empty() {
            let (scope, meta) = self.ver_status().loader().create(
                gen,
                values,
                LEVEL_0,
                self.config().level_table_type[LEVEL_0],
            )?;

            // `Compactor::data_loading_with_level`中会检测是否达到压缩阈值，因此此处直接调用Major压缩
            self.major_compaction(
                LEVEL_0,
                vec![VersionEdit::NewFile((vec![scope], 0), 0, meta)],
            )
            .await?;
        }
        Ok(())
    }

Minor Compaction将MemTable(内存缓冲数据)批量的写入硬盘，这也就是LSM写入性能较高的关键
Q: 为什么Level 0不与其他Level对齐，形成排布有序SSTable
A: 如果Level 0需要保持数据有序，那么实际已经类似Major Compaction造成比较严重的写放大，即每次Minor Compaction时都需要像Major Compactoin中一致需要读取Next Level交错范围的SSTable
而又因为MemTable中的数据是随机性较强的，非常容易导致数据范围过大而可能造成Next Level有非常多数量的SSTable与这个MemTable的数据范围重合，而造成每次Minor Compaction甚至可能造成比常规Major Compaction更大的写放大
(本身Minor Compaction造成Major Compaction时，有几率造成多Level的连锁Compaction而导致比较严重的写放大，这是Leveled Compaction造成的写放大问题之一)
因此这会导致更加严重的读放大问题

Major Compaction

Major Compaction是较为重量级的Compaction，负责将Level N中越出阈值的SSTable与Level N+1中相同数据范围内的SSTable进行合并，减少数据空间占用。
Major Compaction是LevelDB中最为复杂的操作之一，是LSM中第一道较为复杂的操作。
KipDB中Major Compaction的大体步骤为
目前Major压缩的大体步骤是

1. 获取当前Version，读取当前Level的指定数量SSTable，命名为vec_ss_table_l
2. vec_ss_table_l的每个SSTable中的scope属性进行融合，并以此获取下一Level与该scope相交的SSTable，命名为vec_ss_table_l_1
3. 获取的vec_ss_table_l_1向上一Level进行类似第2步骤的措施，获取两级之间压缩范围内最恰当的数据
4. vec_ss_table_l与vec_ss_table_l_1之间的数据并行取出排序归并去重等处理后，分片成多个Vec
5. 并行将每个分片各自生成SSTable
6. 生成的SSTables插入到vec_ss_table_l的第一个SSTable位置，并将vec_ss_table_l和vec_ss_table_l_1的SSTable删除
7. 将变更的SSTable插入至vec_ver_edit以持久化
8. 将vec_ver_edit中的数据进行log_and_apply生成新的Version作为最新状态

/// 通过Level进行归并数据加载
    async fn data_loading_with_level(
        &self,
        level: usize,
    ) -> Result<Option<(usize, DelNodeTuple, MergeShardingVec)>> {
        let version = self.ver_status().current().await;
        let config = self.config();
        let major_select_file_size = config.major_select_file_size;
        let next_level = level + 1;

        // 如果该Level的SSTables数量尚未越出阈值则提取返回空
        if level > 5 || !version.is_threshold_exceeded_major(config, level) {
            return Ok(None);
        }

        // 此处vec_ss_table_l指此level的Vec<SSTable>, vec_ss_table_ll则是下一级的Vec<SSTable>
        // 类似罗马数字
        if let Some((mut ss_tables_l, scopes_l)) =
            version.first_tables(level, major_select_file_size)
        {
            let start = Instant::now();
            let scope_l = Scope::fusion(&scopes_l)?;
            // 获取下一级中有重复键值范围的SSTable
            let (ss_tables_ll, scopes_ll) = version.tables_by_scopes(next_level, &scope_l);
            let index =
                version.find_index_by_level(ss_tables_ll.first().map(|sst| sst.gen()), next_level);

            // 若为Level 0则与获取同级下是否存在有键值范围冲突数据并插入至del_gen_l中
            if level == LEVEL_0 {
                ss_tables_l
                    .append(&mut version.tables_by_meet_scope(level, |scope| scope.meet(&scope_l)))
            }

            // 收集需要清除的SSTable
            let del_gen_l = collect_gen(&ss_tables_l)?;
            let del_gen_ll = collect_gen(&ss_tables_ll)?;

            // 此处没有chain vec_ss_table_l是因为在vec_ss_table_ll是由vec_ss_table_l检测冲突而获取到的
            // 因此使用vec_ss_table_ll向上检测冲突时获取的集合应当含有vec_ss_table_l的元素
            let ss_tables_l_final = match Scope::fusion(&scopes_ll) {
                Ok(scope_ll) => version.tables_by_meet_scope(level, |scope| scope.meet(&scope_ll)),
                Err(_) => ss_tables_l,
            }
            .into_iter()
            .unique_by(|sst| sst.gen())
            .collect_vec();

            // 数据合并并切片
            let vec_merge_sharding = Self::data_merge_and_sharding(
                ss_tables_l_final,
                ss_tables_ll,
                config.sst_file_size,
            )
            .await?;

            info!(
                "[LsmStore][Major Compaction][data_loading_with_level][Time: {:?}]",
                start.elapsed()
            );

            Ok(Some((index, (del_gen_l, del_gen_ll), vec_merge_sharding)))
        } else {
            Ok(None)
        }
    }

pub(crate) async fn major_compaction(
        &self,
        mut level: usize,
        mut vec_ver_edit: Vec<VersionEdit>,
    ) -> Result<()> {
        let next_level = level + 1;
        let config = self.config();

        if level > 6 {
            return Err(KernelError::LevelOver);
        }

        while level < 7 {
            if let Some((
                index,
                ((del_gens_l, del_meta_l), (del_gens_ll, del_meta_ll)),
                vec_sharding,
            )) = self.data_loading_with_level(level).await?
            {
                let start = Instant::now();
                // 并行创建SSTable
                let ss_table_futures = vec_sharding.into_iter().map(|(gen, sharding)| async move {
                    self.ver_status().loader().create(
                        gen,
                        sharding,
                        next_level,
                        config.level_table_type[next_level],
                    )
                });
                let vec_ss_table_and_scope: Vec<(Scope, TableMeta)> =
                    future::try_join_all(ss_table_futures).await?;
                let (new_scopes, new_metas): (Vec<Scope>, Vec<TableMeta>) =
                    vec_ss_table_and_scope.into_iter().unzip();
                let fusion_meta = TableMeta::fusion(&new_metas);

                vec_ver_edit.append(&mut vec![
                    VersionEdit::NewFile((new_scopes, next_level), index, fusion_meta),
                    VersionEdit::DeleteFile((del_gens_l, level), del_meta_l),
                    VersionEdit::DeleteFile((del_gens_ll, next_level), del_meta_ll),
                ]);
                info!(
                    "[LsmStore][Major Compaction][recreate_sst][Level: {}][Time: {:?}]",
                    level,
                    start.elapsed()
                );
                level += 1;
            } else {
                break;
            }
        }
        self.ver_status()
            .log_and_apply(vec_ver_edit, config.ver_log_snapshot_threshold)
            .await?;
        Ok(())
    }

经过压缩测试，Level 1的SSTable总是较多，根据原理推断：
Level0的Key基本是无序的，容易生成大量的SSTable至Level1
而Level1-7的Key排布有序，故转移至下一层的SSTable数量较小
因此大量数据压缩的情况下Level 1的SSTable数量会较多
这也变相说明，每次Level 0中每次发生Major Compaction时，大多数Level 0 SSTable都会转移到Level 1中，此处容易造成较为大量的写放大
WAL-assisted Tiering: Painlessly Improving Your Favorite Log-Structured KV Store Instead of Building a New One | The International Symposium on Memory Systems
其中该论文的结论也基本验证了低Level使用内存进行优化时，可以减少至多50%以上的写流量

在使用18GB DRAM的情况下，SSD写流量的减少可以提高59.4%和64.8%

固态硬盘(Solid-state drive) 由于快闪记忆体上每一个电闸都有一定的写入次数限制，寿命结束后会无法写入变成唯读状态；而且随著使用的快闪记忆体从SLC架构到MLC、TLC，若电闸的品质不变，理论上电闸寿命呈现6:3:2的衰退（因为其原理是在同一个电闸上记录1、2或3个位元，记录越多位元，被写入的机会就越高）
这意味着较大的写放大会严重影响SSD的寿命，变相降低服务的稳定性与性能

同时由于Level 0读取时几乎需要加载全量的SSTable(Tips: 加载SSTable并非为全量的SSTable数据加载，后继SSTable结构会延申其加载流程)
即使FilterBlock命中率较高，甚至是全命中的情况，仍然要加载SSTable本身的Meta信息(对于RocksDB来说，64MB的SSTable也会造成本身的Meta内容占比也绝对不会少)
同时Level 0的Major Compaction也会使多数Level 0 SSTable合并到下层，这也将进一步加剧了Level 0造成的读放大与写放大问题
这是Leveled Compaction结构中一项非常明显容易造成性能问题的地方，实际上有诸多论文针对Level 0进行优化：
MatrixKV: Reducing Write Stalls in LSM-tree

• 利用 NVM 基于 LSM-trees 提出了一种 KV 存储的设计 MatrixKV（包含了多级存储：DRAM-NVM-SSD），设计原则表现为：
  • 让 L0-L1 层之间的压缩开销更小从而减少写停顿
  • 减小 LSM-tree 的深度来减小写放大
• 核心思想主要表现为以下四点：
  • 利用自己提出的 matrix container 在 NVM 上管理 L0 层
  • 设计了新的 column compaction 引用到了 L0-L1 的压缩中来减少压缩数据的量
  • 增加每一层的宽度来减少 LSM-tree 的深度
  • 引入了 cross-row hint search 来改善读性能
• 和 RocksDB 以及 KVS NoveLSM 对比， 99th 尾延迟降低了 5x 和 1.9x，随机写吞吐量提升了 3.6x 和 2.6x

KipDB决定使用更为简单，但较为有效的方式进行优化：
将Level 0的SSTable使用IoType::Mem作为其Reader和Writer
Level 0 memorization by KKould · Pull Request #25 · KipData/KipDB
站在该PR的视角下，使用内存类型进行SSTable的存储是不充分的。
因为SSTable是Block-Based的，甚至对于内存类型来说，IndexBlock的稀疏索引与FilterBlock的查询过滤带来的效果是低于硬盘持久化的SSTable的。(因为Block的设计涉及到前缀压缩以及本身的数据压缩、编解码、以及为了减少查询IO而构造的IndexBlock二级索引)

SSTable结构解析

SSTable

拓展性SSTable示例：KipDB的SkipTable

站在Level 0的内存化场景去使用SSTable会发现其主要面向场景主要为硬盘，在内存场景下表现并不如，更简单的存储结构的内存占用更低并且不需要前缀拼接以及Block解压：SkipList(复用MemTable数据结构)
实际上，对SSTable进行抽象改造的案例是存在的，比如：
论文思路猜想：UniKV

所以我们急需一种方法，来缓解L0层的读放大，提升L0层的查找性能，但是我们仍然需要注意的是，L0承接着来自内存的数据写入，所以L0层还需要保持很高的写性能才行。一个可以的思路是使用一种读写性能都很高的数据结构代替L0层原来的方法来索引数据，我们很快可以想到的就是HashTable。
HashTable是一种Hash索引数据结构，它采用Hash函数计算Key对应的Hash值，再用这个Hash值模上一个Bucket数组的长度，找到数组中一个对应的Bucket，Bucket里保存的就是Key对应的Value，查询时间复杂度为O(1)，非常快，写入时，也是利用计算Key出来的Hash值模上Bucket数组的长度，找到对应的Bucket写入，时间复杂度也是O(1)。

ToplingZipTable

CO-Index 在 ToplingDB 中最典型的实现是 NestLoudsTrie，PA-Zip 在 ToplingDB 中最典型的实现是 DictZipBlobStore，两者都是内存压缩的，也就是说，它们在内存中的形态是压缩的，所有的搜索、读取操作都是在内存压缩的形态上执行的。并且 CO-Index + PA-Zip 的压缩率很高，远胜于 BlockBasedTable + zstd。
ToplingZipTable 压缩的计算开销较大（大约是 zstd 的两倍），所以，在 ToplingDB 中，主要是将它通过 DispatchTable 配置在 LSM 的较下层，并通过分布式Compact执行压缩。

这些案例说明了不同Level是存在有不同的WorkLoad的，以最极端的两个Level 0与Level 6举例：

• Level 0的数量较少(阈值为10个)，数据交错且非有序(局部有序)，数据持久性弱：发生Major Compaction时导致大量SSTable转移至Level 1
• Level 6 SSTable数量极大，大多为冷数据，数据持久性强：仅仅会被Level 5插入合并SSTable，Level 6的SSTable不会再向下转移

KipDB中目前抽象了Table并基于SkipList实现了SkipList用于Level 0中，充分利用SkipList在内存中高性能的效果
Feat/table multiple implementations by KKould · Pull Request #28 · KipData/KipDB