Mini-LSM Week1 Day1

(Updated: )
KV
, 
本章任务重在理解Mini-LSM Memtable数据结构,以及如何实现高效并发控制

要点解析

force_freeze_memtable的实现需要权衡性能和语义，理论上当这个函数调用时, Memtable就被转换为ImmMemtable,被立刻冻结，从而禁止写入；那么正确的实现范式应该是先加锁，再创建新的Memtable,但是由于带有WAL的Memtable创建可能会长达几毫秒，此时的锁定会导致延迟峰值。
根据mini-lsm-book任务要求中描述的范式：

1
2
3
4
5
6
7
8
fn freeze_memtable(&self) {
    let memtable = MemTable::create_with_wal()?; // <- 可能需要几毫秒
    {
        let state = self.state.write();
        state.immutable_memtable.push(/* something */);
        state.memtable = memtable;
    }
}

这会导致语义的违背,但是只要实现memtable的原子更新，就不会有数据丢失。为了性能，权衡之下，略微放宽语义限制。

如果不放宽语义限制， LLM + Concurrency Skill 检测竞态条件就会发出警告

报错如下:

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
let size = {
        let state = self.state.read();          // ① 获取 RwLock 读锁
        state.memtable.put(key, value)?;        // ② 写入 M1
        state.memtable.approximate_size()       // ③ 获取大小
    };                                          // ④ RwLock 读锁释放 ⚠️
    // ⚠️ 时间窗口：其他线程可以 freeze M1！
    if size >= self.options.target_sst_size {
        let state_lock = self.state_lock.lock(); // ⑤ 获取 Mutex
        let current = self.state.read();         // ⑥ 检查当前 memtable M2
        if current.memtable.approximate_size() >= self.options.target_sst_size {
            drop(current);
            // 内部会获取 state.write()来阻塞写入
            self.force_freeze_memtable(&state_lock)?; // ⑦ freeze M2
        }
    }
    Ok(())
}
Race Condition 场景
场景 1：写入进入已冻结的 memtable（数据丢失风险）
T1: 线程 A: ①-④ 向 M1 写入 "key1=value1"，获取 size=2MB
T2: 线程 B: freeze M1 → 创建 M2 → 启动 flush M1 到磁盘
T3: 线程 A: ⑤-⑥ 检查发现 size>=2MB，但当前是 M2
T4: 线程 A: 检查 M2 的大小（可能 < 2MB），不触发 freeze
T5: 线程 B: flush 完成，M1持久化
T6: 线程 A: 如果在 T1-T2 之间继续写入 "key2=value2" 到 M1
         → "key2=value2" 可能没有被 flush！
        
场景 2：immutable memtable 语义违反
T1: 线程 A: 获取 RwLock，拿到 M1 的 Arc 引用
T2: 线程 B: freeze M1，M1 变成 immutable
T3: 线程 A: RwLock 释放后，继续持有 M1 的 Arc，向 M1 写入
         → 向 immutable memtable 写入！违反 LSM 语义

思考

  • 为什么内存表不提供 delete API？
    • LSM-Tree 使用追加写 与 墓碑机制来表示删除，如果内存表提供delete API,考虑如下情况: 此前写入KV并被刷盘,目前使用新的内存表,用户调用delete API, 无法达到删除目的, 如果更改磁盘内容，那么既违背模块划分理念,又违背LSM-Tree设计理念。
  • 内存表存储所有写操作而不是仅存储键的最新版本是否有意义？例如，用户将 a->1、a->2 和 a->3 放入同一个内存表。
    • 无意义, KV是1:1对应关系, 如果要访问不同版本的KV, LSM-Tree 会通过时间戳提供快照机制
  • 是否可以使用其他数据结构作为 LSM 中的内存表？使用跳表的优缺点是什么？
    • 当然可以选用其他数据结构, 只要能够存储唯一的KV就行，比如B+ Tree, 红黑树
    • 使用跳表的优点: 实现简单,并发控制方便友好, 范围查询高效
    • 使用跳表的缺点: 最坏复杂度可达O(n), 缓存局部性差
  • 为什么我们需要 state 和 state_lock 的组合？我们能否只使用 state.read() 和 state.write()？
    • 快慢路径分离,正常写入走快路径，获取读锁并发写入，这是大概率时间；触发freeze是慢路径, 小概率事件,用于序列化并发操作并且最小化写锁的颗粒度,从而获得最高性能。
    • 我认为可以只用读写锁,只是性能会下降,写锁的临界区会大大地变长。
  • 存储和探测内存表的顺序为什么重要？如果一个键出现在多个内存表中，你应该向用户返回哪个版本？
    • 为了有序存储，返回最新版本
  • 我们在这个课程中使用 parking_lot 锁。它的读写锁是公平锁吗？如果有一个写者等待现有读者停止，尝试获取锁的读者可能会发生什么？
    • 不是公平锁；读者可能会抢占锁，导致写者饥饿，但是小概率事件，因为读多写少
  • 冻结内存表后，是否可能某些线程仍然持有旧的 LSM 状态并写入这些不可变内存表？你的解决方案如何防止这种情况发生？
    • 不可能，因为写入前需要获取读锁，但是freeze线程此时持有写锁，阻塞其他线程的写入，等到原子地更新完后，其他线程才能写入新的Memtable。
  • 有几个地方你可能首先获取状态的读锁，然后释放它并获取写锁（这两个操作可能在不同的函数中，但由于一个函数调用另一个而顺序发生）。这与直接将读锁升级为写锁有何不同？是否有必要升级而不是获取和释放，升级的成本是什么？
    • 锁的颗粒度更细，不会阻塞其他读者；升级的成本当然是性能啦