How-we-keep-track-of-live-SST-files¶

在 Rocksdb，LSM 树包含一个在文件系统上的 SST 文件的列表，以及一些 WAL 日志。每次压缩之后，压缩输出文件被加入到列表，而输入文件则被删除。然而，输入文件并不是一定能满足立即删除的条件，因为有些 get 或者迭代器可能会需要保留这些文件，直到他们的操作结束，或者迭代器被释放。在这一页剩余的内容中，我们介绍我们是如何维护这些信息的。

LSM 树的文件列表在一个名为 version 的数据结构内保存。在一次压缩或者落盘的最后，一个新的 version 会被创建，以存储更新后的 LSM 树。在同一时间，只有一个“CURRENT”版本表示最新的数据的 LSM 树的文件。新的 get 请求或者新的迭代器在整个读取过程或者迭代的生命周期内，会使用当前版本。所有被 get 或者迭代器使用的版本需要被保留。一个过期版本，没有被任何 get 或者迭代器使用，就需要被丢弃。所有没有被任何其他版本使用的文件需要被删除。比如：

如果我们从一个带有三个文件的版本开始：

v1 = {f1,f2,f3}(current) 磁盘的文件：f1,f2,f3

然后现在有一个迭代器使用这个创建：

v1 = {f1,f2,f3}(current,iterator1 使用) 磁盘的文件：f1,f2,f3

现在一个落盘发生，增加了 f4，一个新的版本被创建：

v2={f1, f2, f3, f4} (current) v1={f1, f2, f3} (iterator1 使用) 磁盘的文件：f1,f2,f3,f4

现在一个压缩发生了，压缩了 f2,f3 和 f4，生成新的文件 f5，这是一个新的版本 v3 被创建：

v3={f1, f5} (current) v2={f1, f2, f3, f4} v1={f1, f2, f3} (iterator1 使用) 磁盘的文件：f1,f2,f3,f4,f5

现在 v2 既不是最新的数据，也没有被任何人使用，所以他可以被删除，f4 也是。而 v1 仍旧不能被删除，因为他仍旧被 iterator1 需要：

v3={f1, f5} (current) v1={f1, f2, f3} (iterator1 使用) 磁盘的文件: f1, f2, f3, f5

假设现在 iterator 被销毁：

v3={f1, f5} (current) v1={f1, f2, f3} 磁盘的文件: f1, f2, f3, f5

现在 v1 既没人用，也不是最新的数据，所以他可以被删除，同时还有 f2 和 f3：

v3={f1, f5} (current) 磁盘的文件: f1, f5

这个逻辑通过引用计数来实现。SST 文件和 version 都有一个引用计数。当我们创建一个 version 的时候，我们增加所有文件的引用计数。如果一个 version 不在被需要，该 version 的所有文件都会减少他们的引用计数。如果一个文件的引用计数降低到 0，这个文件就可以被删除。

类似的，每个 version 都有一个引用计数。当一个 version 被创建，他就是一个最新的版本，所以他有引用计数 1.如果这个版本不在是最新的，他的引用计数就会减少。任何人需要在这个版本上工作，都会使其引用计数加一，并且在用完之后减一。当一个版本的引用计数为 0，他就应该被移除。一个 version 要么是最新的，要么有人在使用，这样他的引用计数就不是 0，他就需要被保留。

有时，一个读者直接保留一个 version 的引用，比如压缩的时候保留源 version。更多的时候，一个读者通过一个名为 super version 的数据结构间接持有 version，他会持有 memtable 的引用计数以及一个 version —— 一个完整的 DB 视图。一个读者只需要增加，然后减少一个引用计数，而 super version 会持有 version 的引用计数。这同时使得更进一步的优化，在大多数时候避免为引用计数上锁，变得可能。参考这个博客。

Rocksdb 使用 VersionSet 数据结构维护所有的 version 数据结构，同时用于记住谁是“current”版本。由于每个列族有一个独立的 LSM 树，他也有自己的 version 列表，以及一个名为“current”的版本。但是每个 DB 只有一个 VersionSet，为所有列族维护 version。