Mini-LSM Week2 Day 5,6,7

(Updated: )
KV
,

Manifest

用于崩溃恢复以及重启

创建LSM-Tree时读取清单文件进行回放从而维护崩溃一致性和数据复用，记录三种事件

  • NewMemtable：与WAL一起使用，用于重放没有刷新到磁盘的memtable & imm_memtable
  • Flush: 已经刷盘的memtable
  • Compaction: 恢复到最新状态
    1
    2
    3
    4
    5
    pub enum ManifestRecord {
        Flush(usize),
        NewMemtable(usize),
        Compaction(CompactionTask, Vec<usize>),
    }
    实现的难点在于:
  1. 如何重放日志
  2. 恰当地使用fsync(file) + fsync(dir)来确保文件数据和目录元数据落盘，建立崩溃一致性的提交顺序
    1. sync_file确保数据落盘，SST真实存在；sync_dir使目录元数据落盘，SST物理上存在且可以被观测；添加记录到Manifest，建立逻辑上的存在关系
    2. 采用上述模式，执行操作时崩溃只会出现两种情况：
      1. 写入Manifest失败，从写入前的状态恢复
      2. 写入Manifest成功，从最新状态开始恢复

具体实现:

  • force_flush_imm函数: 刷新SST，刷新目录元数据，添加记录
  • compact: 在应用压缩更改之后，刷新目录，添加记录
  • close: 由于目前没有记录NewMemtable,没有WAL，无法回放内存表，主动关闭时需要手动刷新非空内存表和冻结内存表，从老到新的顺序
  • open: 如果Manifest不存在，走原有路径创建新数据库即可，否则
    • 读取Flush(memtable_id)加入到L0或刷新到new tier；
    • 读取Compaction(task,ouput)并应用；
    • 读取时记录更新next_sst_id
    • 恢复完毕后，在内存中创建SST元数据并加入到state
    • 如果是level compaction，每次压缩后需要对每一级的SST排序，但是由于恢复时暂时没有元数据，因此等到恢复完毕后手动排序
    • 使用最新的next_sst_id创建内存表和storage

思考

  • 你何时需要调用 fsync？为什么需要同步目录？
    • 数据写入WAL后，添加记录到Manifest需要调用fsync(file)
    • 删除压缩的文件后，创建新的文件后，写入记录到Manifest前需要调用fsync(dir)
  • 你需要在哪些地方写入清单？
    • force_flush + compact
  • 考虑 LSM 引擎的替代实现，它不使用清单文件。相反，它在每个文件的头部记录级别/层信息，每次重启时扫描存储目录，并仅从目录中存在的文件恢复 LSM 状态。在此实现中是否可能正确维护 LSM 状态，以及这可能有什么问题/挑战？
    • 考虑压缩任务写入新文件并落盘，但是没有删除旧文件时崩溃，随后进行恢复会导致数据混乱
  • 目前，我们在创建合并迭代器之前创建所有 SST/连接迭代器，这意味着我们必须在开始扫描过程之前将所有级别中第一个 SST 的第一个块加载到内存中。我们在清单中有起始/结束键，是否可以利用此信息延迟数据块的加载，并使返回第一个键值对的时间更快？
    • 可以利用 起始/结束键 做快速筛选
  • 是否可以不将层/级别信息存储在清单中？即，我们只在清单中存储拥有的 SST 列表而不包含级别信息，并使用键范围和时间戳信息（SST 元数据）重建层/级别。
    • L0范围是重叠的
    • L1 ~ Lmax的文件是增量演化的

WAL

注意三点:

  • 单次写入不会主动调用sync，force_freeze_memtable时进行同步
  • close时不会主动刷新内存表，因为创建新MemTable会写入Manifest
  • open恢复时没有Flush记录的memtable需要手动从WAL中恢复

思考

  • 如何处理 WAL 中的损坏数据？
    • 如果在尾部直接丢弃
    • 在中间，丢弃之后的数据
  • 是否可能设计一个没有 WAL 的 LSM 引擎（即使用 L0 作为 WAL）？这种设计会有什么影响？
    • 理论上来说时可以的，只是以什么粒度刷新L0呢，如果使用很小的L0(64KB)会导致小文件增多，读放大和压缩压力大；如果使用大L0,崩溃时丢失的文件多

WriteBatch & CRC校验

内容简单，直接省略

思考

  • 考虑 LSM 存储引擎只提供 write_batch 作为写入接口（而不是单个 put + delete）的情况。是否可以如下实现：有一个带有 mpsc 通道接收器的单个写入线程来获取更改，所有线程将写入批次发送到写入线程。写入线程是写入数据库的唯一点。这种实现的优缺点是什么？（如果你这样做，恭喜你得到了 BadgerDB！）
    • 优点是异步写入，前台返回速度快，缺点就是无法确定数据是否落盘，写入后查询可能无法读取到，需要引入事务？？来提供某种一致性
  • 将所有块校验和一起放在 SST 文件的末尾而不是与块一起存储可以吗？为什么？
    • 不可以，因为块损坏一般是连续的，一个校验损坏就会导致所有校验失效，而且无法反应块的状况