← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 1770.b.1.a.1

删除标记延后清理

理解等级:高级

LSM删除先写墓碑,使读路径知道旧值已无效;刷内存表时不能直接去掉墓碑,因为旧值可能仍在其他层。合并清理必须确认不会让更老值复活,并保留仍被快照需要的版本。原书以minor和major解释过程,不同系统的术语与回收条件需分别核对。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 大数据常用的算法与数据结构 · 查看原书依据

      从图3-8可以看出,当MemTable中记录数量到了一定程度会转换为Immutable MemTable,此时不能往其中写入记录,只能从中读取KV内容。Immutable MemTable其实是一个SkipList多层级队列,其中的记录是根据key有序排列的。所以这个minor Compaction实现起来也很简单,就是按照Immutable MemTable中记录由小到大遍历,并依次写入一个Level 0的新建SSTable文件中,写完后建立文件的index数据,这样就完成了一次minor Compaction。从图中也可以看出,对于被删除的记录,在minor Compaction过程中并不真正删除这个记录,原因也很简单,这里只知道要删掉key记录,但是这个KV数据在哪里?这需要复杂的查找,所以在minor Compaction的时候并不做删除,只是将这个key作为一个记录写入文件中,至于真正的删除操作,在以后更高层级的Compaction中会去做。

    参考来源

    - 位置:《大数据日知录:架构与算法》第3章《大数据常用的算法与数据结构》(来源项目:book-sources;源文件:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00008.html) - 结论依据:原文以“只是将这个key作为一个记录写入文件中”所在段落解释具体机制;本卡保留其条件,另将实现限制、勘误和教学推导在正文中明确区分。 - 原始内容:从图3-8可以看出,当MemTable中记录数量到了一定程度会转换为Immutable MemTable,此时不能往其中写入记录,只能从中读取KV内容。Immutable MemTable其实是一个SkipList多层级队列,其中的记录是根据key有序排列的。所以这个minor Compaction实现起来也很简单,就是按照Immutable MemTable中记录由小到大遍历,并依次写入一个Level 0的新建SSTable文件中,写完后建立文件的index数据,这样就完成了一次minor Compaction。从图中也可以看出,对于被删除的记录,在minor Compaction过程中并不真正删除这个记录,原因也很简单,这里只知道要删掉key记录,但是这个KV数据在哪里?这需要复杂的查找,所以在minor Compaction的时候并不做删除,只是将这个key作为一个记录写入文件中,至于真正的删除操作,在以后更高层级的Compaction中会去做。 - 边界对照:[LevelDB实现说明](https://raw.githubusercontent.com/google/leveldb/main/doc/impl.md)、[Bitcoin原论文](https://bitcoin.org/bitcoin.pdf)、[SILT原论文](https://www.cs.cmu.edu/~dga/papers/silt-sosp2011.pdf);用于校正原书简化,未将书外观点伪作原文。