mace 记录 -- 再谈GC

经过一段时间的迭代，mace 中的垃圾回收已经有些不同了，因此在此梳理下（基于版本 0.0.15)

原始的实现

mace 中的数据文件是扁平的，就是一个个的 data file，data file 又有固定大小，这看起来就是 SSD 中的 block，因此 mace 垃圾回收的策略使用的就是 SSD 的垃圾回收策略，不过目前只考虑了IO成本（后续还可以加入写放大，空间放大等因子）

一点改进

为了实现垃圾回收，需要对每一个 data file 做一个描述，因为是 append only 的，因此这个描述只能存放在内存中，包括这个 data file 中总的 page 有多少，活跃的 page 有多少，大小是多少等，当规模变大时问题就出现了。假设一个 data file 中总的 page 数量为 10K 个，每一个 page 使用一个bit来标记是否活跃，那么大约需要 1.25K 的内存，一百万个 data file 就需要 1.2GB内存，而 data file 的总大小则是 61TB （默认情况下 data file 的大小是 64MB）

这样来看，内存问题不大，但单纯遍历一百万的遍历在我的机器上一需要 10ms 左右，问题不大，不需要改进，但可以减少遍历次数，因此在这个版本中将 空闲率的计算从 O(n)优化到了 O(1)，另外将排序替换为 heap，空间占用从 O(n) 减小到 O(1）

当然如果 data file 的规模达到了千万以上，那么可以根据 MDC 公式的特点，按照 active ratio 和 up2，缓存 K 个优先清理的 data file，这样虽然不能总是挑选到全局最优的 data file 但时间上的 trade-off 还是可以接受的。不过，话又说回来，如果 data file 达到了 610TB 还是建议对数据进行拆分

另外，根据 Bw 树的特点，delta page 总是会很快的被丢弃，而 base page 则不会，因此，ArkDB 中将 delta page 和 base page 区分为两种 stream 写入到生命周期不同的文件中，这样在 GC 时可以明显的减小IO成本。 不过在 mace 中并没有这么做，mace 中在 delta page 不再使用时，会将它从映射中删除，压根就不会写入到 data file，除非是用户打开数据库，写入几个kv后就关闭数据库，然后重复这个操作，这中场景并不多见

同样，在原版的 llama 论文中提到，垃圾回收是需要感知上层的数据的，简单来说，llama 中的垃圾回收除了过滤掉不再使用的 delta page，还需要感知 node 中 delta chain 的长度，如果过长，需要对 node 做 consolidation 目的是将node分散在各个 data file 中的数据集中到一起，这样可以提升读性能

在 mace 中，曾经尝试过这样的是实现，但最终没有这么做。原因是：

• mace 是面向磁盘的存储，那么它的数据绝大多数都不会是热点，在 GC 中执行这样的操作收益不大
• mace 提供了 evictor 后台线程，在 node 被淘汰时会按照设定，将 delta chain 长度超过配置的 node 进行 consolidate
• mace 目前还没有 IO 优先级和流控

后者保证了性能的下限，但有一点不同，对冷数据做 consolidation 有一个好处：如果 node 中的版本较多，随着运行这些版本几乎都过期了，但它仍然占用着磁盘空间 （没错，在 mace 中数据的历史版本是直接放在 node 中的，这是因为 node 本身由多个 delta 和 一个 base 构成，这是天然的多版本）。那么这样的过期的版本的数据有多少呢？这个很难估算，因此未来 mace 可能会提供一个类似 VACUUM 的接口给用户，或者将版本存储独立出来（但这肯定会增加更新开销和内存占用）

内部的交互

前面提到，对data file的描述都存放在一个全局的 hashmap 中，那么这就会出现并发问题：当 GC 线程在对 data file 中不活跃的 page 进行过滤时，flush 线程可能正在修改记录活跃信息的数据结构，这就有两种可能：flush 先记录了，然后在过滤，那么 GC 拿到的活跃的 page 就是真活跃的，但如果反过来，GC 拿到的 page 可能在过滤后变成了垃圾，如果不管直接重写到 data file 中，那么这些垃圾将永远不会被清除（因为没有任何地方会再次将其标记为垃圾了）

另外，GC 会将不活跃的 data file 删除，在此之前会将删除操作记录到 manifest 中，而 flush 线程同样会记录文件描述的变化，这就会出现 GC 先记录了删除， flush 再记录描述的变化，那么在恢复重放 manifest 时就会出现描述先创建，然后删除，然后又重新创建的情况，但重新创建时活跃的page数已经变了，而 data file 中总的数量不不会变，因此会出现后续将 data file 中的page 标记为垃圾时在描述中找不到的情况

这两个问题涉及到了：flush、recover 和 gc 三个部分