文件内容

通常包含磁盘以下文件

Sstable
Manifest
WAL

SST格式

每次读取都是通过先加载Meta Section作为索引，然后再到盘上读取数据。

-------------------------------------------------------------------------------------------
|         Block Section         |          Meta Section         |          Extra          |
-------------------------------------------------------------------------------------------
| data block | ... | data block |            metadata           | meta block offset (u32) |
-------------------------------------------------------------------------------------------

对于Block Meta的格式大概为

--------------------------------------------------------------------------------------
|                                    Block Meta                                      | 
--------------------------------------------------------------------------------------
| meta len | offset | first key len | first key | last key len | last key | checksum |
--------------------------------------------------------------------------------------

其中每个Entry

-----------------------------------------------------------------------
|                           Entry #1                            | ... |
-----------------------------------------------------------------------
| key_len (2B) | key (keylen) | value_len (2B) | value (varlen) | ... |
-----------------------------------------------------------------------

checksum

对以下几个模块末尾添加了checksum，都使用了crc32hash

Block Checksum:在SST中每个block的数据后，添加这个block的checksum
SST Meta Checksum:在SST中block meta后，添加block meta的checksum;在bloom filter后添加bloom filter的checksum
WAL Checksum:在WAL中每个kv对后添加一个这个kv对的checksum
Manifest Checksum:在Manifest前面加一个总共Manifest记录个数，然后在每个record后面，记录这个record的checksum

Compaction

Mini-Lsm中实现了三种Compaction的流程，

流程

Compaction实现是通过一个后台线程进行定期Compaction，每50ms执行一次

let handle = std::thread::spawn(move || {
  let ticker = crossbeam_channel::tick(Duration::from_millis(50));
  loop {
    crossbeam_channel::select! {
      recv(ticker) -> _ => if let Err(e) = this.trigger_compaction() {
        eprintln!("compaction failed: {}", e);
      },
      recv(rx) -> _ => return
    }
  }
});

trigget compaction

单次Compaction调用trigget_compaction开始执行，里面函数调用大概如下：

let task = self.compaction_controller.generate_compaction_task(&snapshot)：检测当前lsm tree的结构查看是否需要进行Compaction，如果需要调用，则生成一个task，task里包含了所有需要合并的level和sst；compaction_controller封装了3种不同的compaction策略
let sstables = self.compact(&task)?：根据task种sst的信息，将这些sst进行合并。具体合并的流程为，首先把所有sst包装成一个iterator，具体iterator的类型根据不同的策略产生，iterator的目的是将这些sst的数据进行排序。把iterator中排好序的数据不断取出，然后生成一些排好序的sst
更新sst：目前获取了需要被合并的sst，以及新生成的sst，那么把被合并的sst删除，然后把新的sst插入对应的位置。不同策略插入的方法单独实现

策略

Simple Compaction Strategy

最简单的策略，枚举相邻两层i和i+1，查看相邻两层的文件数量比值，如果比值大于了阈值，那么将这两层中全部sst进行compaction，然后插入i+1层

Tiered Compaction Strategy

这种策略会跳过l0层，每次将一个imm刷入ssd中成为sst时，在所有level之前插入一个新的level，只包含当前最新的sst，对应的合并策略一共有三种：

从上到下枚举，计算 $[0, ma x_{l} e v e l - 1]$ 层的sst数和 $l e v e l$ 层的 $ss t$ 数量的比值，如果大于一个阈值则将lsm tree中所有sst合并成一个层，lsm tree的层数也会变成1
从上到下枚举，计算 $[0, i]$ 层的sst数和 $i + 1$ 层的 $ss t$ 数量的比值，如果大于一个阈值则将 $[0, i]$ 所有sst合并
当以上两种策略都失效时，将前max_merge_width层的sst进行合并

注意当总层数小于num_tier时，不进行compaction，防止过于频繁地compaction。

Leveled Compaction Strategy

由于上两种方法总是会将若干层中所有sst都进行合并，这样写放大过于严重，于是leveled compaction strategy如果不是合并l0时一次只选择一个sst进行compaction。

同样以上策略还存在一个问题，即如果lsm tree已经将所有sst都合并到了底部，那么中间的层都是空的，这样如果保留这些层，那么显然一个新刷新的imm需要额外合并很多次才能到最底层，显然是浪费的。因此这里求出一个最靠上非空的位置base_level，当l0层sst进行compaction时，直接和base_level进行合并。

然后考虑非l0层的compaction。采用的策略是对于第i层计算一个预估的大小 $t a r g e t_{i}$ ，当前大小为 $re a l_{i}$ 。如果超过了这个大小则计算该层超出的比例 $r a t i o = \frac{re a l _{i}}{t a r g e t _{i}}$ ，然后选择 $r a t i o$ 最大的层进行合并到下一层。首先会预设一个base_level_size，表示最底层的sst大小，以及一个层之间的放大倍数multiply，即i+1层应该是i层的multiply倍。最后一层预估的大小为预估和现实大小的较大值，然后根据multiply系数计算出每层预估大小。

Manifest

Manifest模块主要是用来恢复内存中对于sstable的索引。由于Manifest需要存在磁盘里，因此采用顺序写的方法写入Manifest，具体为每次出现flush/compact操作时，将apply_compaction_result的参数记录下来，并执行apply_compaction_result函数，相当于模拟一遍整个存储引擎sst的变化过程。对于修改sst/manifest文件的操作，都需要执行sync_dir将内核缓冲区的数据下盘。

可以发现以上情况并没有考虑mem/imm，因此当正常关闭时，需要先将mem强制转化为imm，然后再把所有imm刷成sst。

具体实现为每次compact/flush后，调用append manifest将新的操作写入manifest文件里，恢复的时候则打开manifest文件然后重放所有compact/flush操作，将sstable的索引写入内存。

注意恢复的时候，现在内存中不存在任何mem/imm，因此新建一个mem。

同时对于策略leveled compaction，由于一次会只合并部分的sst，因此每次合并后都需要排序。但是恢复的时候sst索引还没有被加载进内存，因此无法排序。解决方案是加一个recovery参数表示当前是否处于recovery状态，如果是则不排序，等到建立索引后排序。

WAL

WAL的格式如下

| key_len | key | value_len | value |

WAL的意义在于保存所有mem和imm的数据，在崩溃后回复时直接重放WAL中所有数据即可恢复。具体操作为，当写入一个kv时，首先将kv写入WAL里，然后强制刷盘，再写入mem中。对于一个memtable，存在两种修改，一种是创建一个memtable，一种是被flush到了l0。

重放的过程同样依赖于MANIFEST的记录，首先遍历一遍MANIFEST，如果是创建则插入一个memtable，flush则删除memtable，获取了所有当前的memtable的编号及顺序，然后根据编号读取磁盘上该memtable对应的WAL文件，将里面的kv全部写进一个新创建的imm，然后按顺序插入imm，最后再创建一个新的空的mem。

🪴 meox3259

Explorer

Mini-LSM