Mini-LSM Week1 Day2

(Updated: )
KV
, 
本章用于了解迭代器这一重要抽象,迭代器很好地隐藏了底层复杂的数据结构并向上提供统一的数据访问接口

要点解析

StorageIterator

采用LevelDB/RocksDB中经典的设计,而非与Rust std iter一致
通过 valid & next 来配合获取KV

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
pub trait StorageIterator {
    type KeyType<'a>: PartialEq + Eq + PartialOrd + Ord
    where
        Self: 'a;

    /// Get the current value.
    fn value(&self) -> &[u8];

    /// Get the current key.
    fn key(&self) -> Self::KeyType<'_>;

    /// Check if the current iterator is valid.
    fn is_valid(&self) -> bool;

    /// Move to the next position.
    fn next(&mut self) -> anyhow::Result<()>;

    /// Number of underlying active iterators for this iterator.
    fn num_active_iterators(&self) -> usize {
        1
    }
}

MemtableIterator

实现的难点在于理解三方库ouroboros自我引用宏的设计,以及Range数据结构;
该结构体通过自动生成的MemTableIteratorBuilder构造后生成,初始的item为空,需要手动的调用next函数来初始化值。
SkipMapRangeIter<'this>结构体和Rust iter语义上有区别:

  • Rust iter: 以 vec![1,2,3].iter()为例,初始化后便指向1,调用next函数会指向2
  • SkipMapRangeIter<'this>: 首次调用next函数后指向第一个KV,当然也可能为空。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #[self_referencing]
    pub struct MemTableIterator {
        /// Stores a reference to the skipmap.
        map: Arc<SkipMap<Bytes, Bytes>>,
        /// Stores a skipmap iterator that refers to the lifetime of `MemTableIterator` itself.
        #[borrows(map)]
        #[not_covariant]
        iter: SkipMapRangeIter<'this>,
        /// Stores the current key-value pair.
        item: (Bytes, Bytes),
    }

    实现MemTableIterator时只需要进行一个思考: 如何处理被删除的KV对(Value为空)，即墓碑数据?
    考虑到查找时需要合并多个MemTableIterator的值, 如果最新的值被删除,那么其他的内存表中的值应该被丢弃；因此需要保留 墓碑数据

MergeIterator

合并多个迭代器的值，提供统一的访问视图。
堆排序方式: 根据内在迭代器的(idx,key)进行排序; key本身从小到大排序,对于相同的key ，靠前的迭代器返回的值新，应该采用。

1
2
3
4
pub struct MergeIterator<I: StorageIterator> {
    iters: BinaryHeap<HeapWrapper<I>>,
    current: Option<HeapWrapper<I>>,
}

实现的难点在于处理 内部迭代器next函数报错,以及失效迭代器被放置到堆带来的排序错误。

  • 如果current不为空,那么迭代器有效,current中就是最新的值, 解引用后即可访问
  • 调用next需要作如下处理:
    • 堆中的迭代器如果有和current要丢弃的Key相同的Key Value，丢弃(调用next)
    • 如果丢弃报错或者丢弃后迭代器失效,使用PeekMut::pop(&mut iter)处理节点,避免无效地迭代器被放置到堆中，从而导致程序崩溃
    • 迭代current的值并将有效迭代器放置回堆,然后重新获取current
      核心代码如下:
      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
      // 如果next报错,认为整个迭代器失效,处理完堆逻辑问题后,立刻返回错误
          fn next(&mut self) -> Result<()> {
              if let Some(mut current) = self.current.take() {
                  while let Some(mut other) = self.iters.peek_mut() {
                      if other.1.key() != current.1.key() {
                          break;
                      }

                      match other.1.next() {
                          Err(e) => {
                              PeekMut::pop(other);
                              return Err(e);
                          }
                          Ok(_) if !other.1.is_valid() => {
                              PeekMut::pop(other);
                              continue;
                          }
                          _ => continue,
                      }
                  }

                  match current.1.next() {
                      Err(e) => return Err(e),
                      Ok(_) if current.1.is_valid() => {
                          self.iters.push(current);
                          self.current = self.iters.pop();
                          return Ok(());
                      }
                      _ => {
                          self.current = self.iters.pop();
                          return Ok(());
                      }
                  }
              }
              Ok(())
          }

FusedIterator

提供统一的表现方式,如果底层迭代器出错，那么会返回错误; 同时在本层需要处理墓碑值

1
2
3
4
pub struct FusedIterator<I: StorageIterator> {
    iter: I,
    has_errored: bool,
}

FusedIteartor在创建时就要丢弃墓碑值
next函数实现时注意错误处理即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fn next(&mut self) -> Result<()> {
        if self.has_errored {
            return Err(anyhow!("Inner StorageIter Has Error"));
        }
        if !self.iter.is_valid() {
            return Ok(());
        }
        if let Err(e) = self.iter.next() {
            self.has_errored = true;
            return Err(e);
        }
        if self.iter.is_valid() && self.iter.value().is_empty() {
            return self.next();
        }
        Ok(())
    }

LsmIterator

目前只使用了Memtable和ImmMemTable,因此是一个合并迭代器;按照 MemTable -> ImmMemTables(new -> old)的顺序创建就好

记住这个结构体,后续增加磁盘结构后会修改

1
type LsmIteratorInner = MergeIterator<MemTableIterator>;

思考

  • 使用你的合并迭代器的时间/空间复杂度是多少？
    • 空间复杂度: O(n),其中n为迭代器的数量
    • 时间复杂度:
      • 创建: O(n logn),每个元素被接入堆
      • next: 平均 O(log n), 单次最坏 O(k log n)，k为具有相同key的KV数量
  • 为什么我们需要自引用结构用于内存表迭代器？
    • 为了防止使用迭代器时引用的内存表被析构
  • 如果一个键被删除（有一个删除墓碑），你需要将其返回给用户吗？你在哪里处理了这个逻辑？
    • 不需要,在FusedIterator处理
  • 如果一个键有多个版本，用户会看到所有版本吗？你在哪里处理了这个逻辑？
    • 不会,MergeIterator会合并键,目前只返回最新的版本
  • 如果我们想摆脱自引用结构并在内存表迭代器上有一个生命周期（即 MemtableIterator<'a>，其中 'a = 内存表或 LsmStorageInner 生命周期），是否仍然可以实现 scan 功能？
    • 'a = memtable 不行,因为迭代器的存活时间可能比memtable长(多线程下,memtable被快速写满冻结刷盘然后释放)
    • 'a = LsmStorageInner 存活不代表对应的内存表存活,不行
  • 如果（1）我们在跳表内存表上创建一个迭代器（2）有人向内存表中插入新键（3）迭代器会看到新键吗？
    • 可能会看到;因为迭代器持有的是引用而非快照，如果插入值在游标之后，那么可以通过迭代器访问
  • 如果你的键比较器不能给堆实现提供稳定的顺序会发生什么？
    • 无法顺序访问，同一个值的多个版本会被重复访问
  • 为什么我们需要确保合并迭代器按迭代器构造顺序返回数据？
    • 因为需要对外提供某个键值对的最新版本
  • 是否可以为 LSM 迭代器实现 Rust 风格的迭代器（即 next(&self) -> (Key, Value)）？优缺点是什么？
    • 理论上可以，但是太太太复杂了
    • 优点是兼容rust生态
    • 缺点是无法进行错误处理,性能开销大，生命周期复杂
  • 起始代码提供了合并迭代器接口来存储 Box<I> 而不是 I。这背后的原因可能是什么？
    • 自引用结构体无法移动: 通过Box固定地址防止垂悬引用
    • 支持合并异构迭代器
    • 避免类型地狱
    • 减少堆的内存移动开销