Mini-LSM Week1 Day 5,6,7

(Updated: )
KV
,

Week1 Day5

实现TwoMergeIterator并完善读取路径

TwoMergeIterator

合并两个不同种类的迭代器,优先使用第一个迭代器

最核心的判断其实就是使用哪个迭代器,判断逻辑见create函数

1
2
3
4
5
6
7
8
9
10
pub struct TwoMergeIterator<A: StorageIterator, B: StorageIterator> {
    a: A,
    b: B,
    // Add fields as need
    use_a: bool,
}
pub fn create(a: A, b: B) -> Result<Self> {
        let use_a = a.is_valid() && (!b.is_valid() || a.key() <= b.key());
        Ok(Self { a, b, use_a })
    }

迭代时需要注意, 使用迭代器A时，两个迭代器可能指向相同的Key,因此调用a.next()前需要先迭代B，避免重复值出现

1
2
3
4
5
6
7
8
9
10
11
12
fn next(&mut self) -> Result<()> {
        if self.use_a {
            while self.b.is_valid() && self.b.key() == self.a.key() {
                self.b.next()?;
            }
            self.a.next()?;
        } else {
            self.b.next()?;
        }
        self.use_a = self.a.is_valid() && (!self.b.is_valid() || self.a.key() <= self.b.key());
        Ok(())
    }

读取路径

实现了SST之后,读取路径多了L0 SST,从Memtable -> ImmMemtable -> L0 SST

对于Memtable和ImmMemtable,可能有重叠的部分,使用MergeIterator<MemTableIterator>表示
对于L0 SST, 由于目前尚未合并,多个SST之间也可能有重叠的部分,使用MergeIteartor<SsTableIterator>
LsmIterator使用TwoMergeIterator合并上述两种迭代器,同时引入end_bound字段用于截取迭代范围。

1
2
3
4
5
6
7
8
9
10
11
fn is_valid(&self) -> bool {
        match &self.end_bound {
            Bound::Included(end) => {
                self.inner.is_valid() && self.inner.key() <= KeySlice::from_slice(end.as_bytes())
            }
            Bound::Excluded(end) => {
                self.inner.is_valid() && self.inner.key() < KeySlice::from_slice(end.as_bytes())
            }
            Bound::Unbounded => self.inner.is_valid(),
        }
    }

思考

  • 考虑用户有一个迭代器迭代整个存储引擎的情况，存储引擎大小为 1TB，因此扫描所有数据需要约 1 小时。如果用户这样做会有什么问题？（这是一个好问题，我们将在课程的不同时间点多次询问它…）
    • 读写延迟增大:目前尚未引入合并, 需要扫描巨量的L0 SST, 合并这些迭代器以及从文件中读取数据会占用 大量的CPU和磁盘带宽，导致其他线程的读取延迟波动增大,写入延迟增加
    • 缓存污染:由于大量SST被读取后就不再访问，导致BlockCache颠簸,其他线程无法有效享受到BlockCache带来的性能提升
  • 一些 LSM 树存储引擎提供的另一个流行接口是多获取（或向量化获取）。用户可以传递他们想要检索的键列表。接口返回每个键的值。例如，multi_get(vec!["a", "b", "c", "d"]) -> a=1,b=2,c=3,d=4。显然，一个简单的实现是简单地对每个键执行单个 get。你将如何实现多获取接口，以及你可以进行哪些优化以使其更高效？（提示：get 过程中的某些操作只需要对所有键执行一次，除此之外，你可以考虑改进的磁盘 I/O 接口以更好地支持此多获取接口）
    • 输入预过滤+单次元数据操作(获取快照)
    • 内存表支持批量操作: 显著减少锁争用和并发开销
    • SST分组：将SST根据请求的Key进行分组, 减少对于含有不同键的相同SST迭代开销

Week1 Day6

后台压缩内存表到SST

  • trigger flush: 检测ImmMemtable数量是否超过阈值,超过则调用force_flush
  • force_flush核心逻辑: 选取最老的ImmMemtable,将其内部存储的KV添加到SstBuilder中,然后创建SST文件。并发控制的逻辑和之前一致：使用state_lock来序列化对于state的更改,使用Copy on Write复制当前快照,修改状态,最后替换到全局锁中。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    pub fn force_flush_next_imm_memtable(&self) -> Result<()> {
            let imm_mtable = self.state.read().imm_memtables.last().cloned().unwrap();
            let mut builder = SsTableBuilder::new(self.options.block_size);
            imm_mtable.flush(&mut builder)?;
            
            let sst_id = self.next_sst_id();
            let sstable = builder.build(
                sst_id,
                Some(self.block_cache.clone()),
                self.path_of_sst(sst_id),
            )?;

            let state_lock = self.state_lock.lock();
            {
                let mut wguard = self.state.write();
                let mut new_state = wguard.as_ref().clone();
                new_state.sstables.insert(sst_id, Arc::new(sstable));
                new_state.l0_sstables.insert(0, sst_id);
                new_state.imm_memtables.pop();
                *wguard = Arc::new(new_state);
            }
            Ok(())
        }
  • 创建LsmStorage时需要检测存储的目标目录是否存在,不存在则创建
  • 关闭LsmStorage时需要向flush_thread发送消息通知并等待所有ImmMemtable落盘后再关闭

思考

  • 如果用户请求删除一个键两次会发生什么？
    • 如果两次请求间MemTable没有被冻结,那么只会向当前的MemTable插入一个墓碑;否则会向两个MemTable插入相同的墓碑
  • 当迭代器初始化时，同时加载到内存中的内存（或块数）是多少？
    • MemTableIterator: 一个Arc引用 + 一对Kv
    • SsTableIterator: 一个块
    • SsTableConcateTerator: 一个块
    • LsmIterator: 可能会因为end_bound为Excluded从而导致读取多个块
    • FusedIterator: 可能会因为跳过空值从而读取多个块
  • 一些疯狂的用户想要_分叉_他们的 LSM 树。他们想要启动引擎以摄取一些数据，然后分叉它，以便他们获得两个相同的数据集，然后分别对它们进行操作。一个简单但低效的实现方法是简单地将所有 SST 和内存结构复制到一个新目录并启动引擎。然而，请注意，我们从不修改磁盘上的文件，实际上我们可以重用父引擎的 SST 文件。你认为如何在不复制数据的情况下高效地实现此分叉功能？（查看 Neon Branching）。
    • 将SST文件对所有存储引擎可见，使用引用计数来管理SST; fork时可以强制父引擎做一次快照刷新,然后获取快照用于开始。每个存储引擎有独立的元数据文件，冻结的快照文件，然后做增量更改
  • 想象你正在构建一个多租户 LSM 系统，在单个 128GB 内存的机器上托管 10k 个数据库。内存表大小限制设置为 256MB。对于此设置，你需要多少内存用于内存表？显然，你没有足够的内存用于所有这些内存表。假设每个用户仍然有自己的内存表，你如何设计内存表刷新策略以使其工作？让所有这些用户共享同一个内存表（即通过将租户 ID 编码为键前缀）是否有意义？
    • 粗略估算需要256TB内存
    • 将内存拆分为 单用户配额 + 全局扩容 两种使用方式； 每个用户固定有4-8GB的内存配额，剩余的内存用于全局调度；方便热点用户扩容
    • 压缩算法需要对全局内存感知，当内存压力大时，强制刷新以缓解内存压力
    • 后台刷新/压缩 做公平调度，保障冷用户或小用户的配额，防止被饿死，减少热点用户的噪声
    • 全局内存表管理复杂，污染严重，不方便使用

Week1 Day7

实现布隆过滤器 + 前缀压缩，比较简单，没什么好说的

思考

  • 布隆过滤器如何帮助 SST 过滤过程？它可以告诉你关于键的什么信息？（可能不存在/可能存在/一定存在/一定不存在）
    • 精确地判断是否该使用某个SST, 可以得知一定不存在
  • 考虑我们需要反向迭代器的情况。我们的键压缩是否影响反向迭代器？
    • 目前只压缩了和块中第一个Key相同的前缀，反向迭代时开销可以接收，只需要额外解码一对KV
  • 你可以在扫描上使用布隆过滤器吗？
    • 不可以，扫描需要获取的是给定范围内的Key，布隆过滤器是针对单个Key给出判断
  • 与块中的第一个键相比，对相邻键进行键前缀编码的优缺点可能是什么？
    • 优点：对于分布均匀的底层SST可能拥有更好的空间利用率，优化IO，减少写放大
    • 缺点：随机定位开销大，单条记录损坏可能影响后续恢复