mace 记录 -- GC

由于 mace 是 append-only 的，因此在数据迁移过程中必然会留下“垃圾”，在 mace 中，这些“垃圾”都是由 arena 中或于的数据转变来的，由于 mace 当前还不支持树的 merge 操作，因此这些“垃圾”完全来自于 delta chain 的 consolidation。当 arena 不再使用时就需要 flush 到 disk，这时有两个选择：

完整的刷入，在后台做 GC
丢弃掉标记为 “垃圾” 的数据

前者的好处是：刷盘的逻辑简单，但 GC 需要有好的策略并且需要按照负载tune；后者的好处是：“垃圾”在 arena 复用时自动消失了，不会写到disk，即没有写放大，也没有空间放大，但会面临一个问题：arena 在何时复用？

arena 在何时复用？

讲道理，如果 2. 能实现那将是完美的方案。前面提到 “垃圾”完全有 consolidation 产生，把时间拉长，前面的 arena 中的数据总是会通过 consolidation 被迁移到后面的 arena 中，当前面的 arena 不再被引用时，arena 就可以回收再使用了，但如何确定 arena 不再被引用呢？

按照设计，arena 在分配空间时会增加引用计数，在分配出的空间使用完成时减少引用计数，当 arena 空间耗尽时，arena 被标记为 SEALED，并切换到下一个 arena，当 SEALED 的 arena 的引用计数减为 0 时，这个 arena 就可以 flush 了

按照前面的描述，consolidation 中丢弃的 delta page 会被标记为 “垃圾”，那么在 arena flush时跳过这些“垃圾”的结果就是：arena 中有完整的数据，而文件中仅有活跃的数据。如果在 arena flush 时就有线程正在 lookup 或是 consolidate，那么就会出现：当前的 delta page 在 arena 中，在访问 link 时发现 arena 已经 flush 了，于是从文件中加载，但由于“垃圾”没有 flush，因此 lookup 或是 consolidate 就会无法访问下一个 delta page

那么，如果我们允许从 flush 了的 arena 中继续加载 delta page 是否能解上面的问题呢？答案是可以的，但 arena 何时复用呢？很显然这是一个“🐔和🥚”的问题

All problems in computer science can be solved by another level of indirection, except for the problem of too many layers of indirection

虽然，但是，如果我们增加一层抽象呢？

前面问题的本质是：thread 1 consolidate 成功后“移动了部分数据”，但thread 2 还是使用“已经移动的数据“

那么我们只需要增加一个间接层：在查找时，先在间接层找到最新的映射。即：thread 1 成功时，将自己的 link 放到间接层中，随后 thread 2 还持有旧数据，那么 arena 的引用就不为0，这样就不会被 flush，下一次访问 link 时，先到间接层中查找，发现 link 已经替换为了 thread 1 最新的 link，那么将从新的 link 加载 delta page，而这个 delta page 必定是 arena 中的，如果有 arena 切换，那么旧的 arena 就不会被引用，从而可以被复用

但是，这又引入了新的问题：这个间接层显然是一个 map，那么 map 中的元素何时删除呢？

我们可以观察到，并行的访问是受core数量限制的，最差的情况是所有的 core 都在执行 consolidate，大多数时候，会是多个线程同时访问一个 node，也就是说，这里面隐藏了这样的一个事实：如果我们使用 core 数量大小的池子用来缓存数据，那么当池子满了需要淘汰时，必然有一个 core 已经完成了 consolidate，但问题是怎么知道哪个core已经完成了呢？除此之外，这层抽象是一个明显的性能瓶颈

那么有没有可行的办法呢？

⭐ 重试，当 lookup 访问不到时就从头开始，当 consolidate 访问不到时就放弃（这说明已经有其他 consolidate 完成了，从头开始大概率不满足 consolidation 的条件了）。这个解法看起来很美好，但代价是代码会变得面目全非，由于目前 mace 还不成熟，现在修改会为后续的维护带来不小的压力

综上，目前来看，第 1. 点更适合

GC

GC其实也有两个选项：主动和被动

前者指的是后台线程收集metrics按照某个指标将delta page从旧的文件中迁移走，当旧的文件中不再有活跃的 delta page 时，就可以删除了；后者则是后台线程通过某种策略挑选一些文件，将这些文件中的活跃的delta page写到新的文件中，然后更新映射表，当选中文件中活跃的delta page都迁移完后就可以删除了，这个过程称为 rewrite

前者的优点是：实现简单，并且对于那些delta chain很长但频繁查找的节点来说可以提高查找效率，但不能保证一次成功，需要多次尝试，它的难点是如何确定指标；后者的优点是：相对独立，不影响前台的插入，但会额外消耗写 IO 资源，难点是实现较为复杂

主动

前面提到，mace 中“垃圾”的完全来自于 consolidation，而这些垃圾“目前”不得不刷到disk中，为了实现垃圾收集，可以读取刷入的文件找到活跃的delta pages所占的比例，如果这个比例小于某个设定的值，那么就通过找到它们所在的 node，对齐进行 consolidate，这个过程会读取活跃的 delta pages，并重新分配内存将它们合并到一个新的node中，随着 arena 一起刷入新的文件，当文件足够老时也可以触发相同的操作

经验表明，对于顺序插入来说，活跃的 delta pages 在文件中的比例绝大多数都不会超过 20%，对于6字节的key和value 的10 万次插入来说，实际的数据大小不会超过 20M，因此对于其他负载，“垃圾”的比例会更小

被动

和主动一样，被动也需要挑选活跃的delta page最少的文件，触发条件可以是收集的空间放大率也可以是容量的限制，这个过程中也会遇到访问的数据被移动的情况，同时随着GC的运行，文件本身会碎片化，即：文件数量越来越多，但越来越小。因此需要一个映射帮助找到正确的位置，同时这个过程可以将碎片化的文件写到一起

实现

mace 目前使用的是被动的GC，在⭐实现后，“垃圾”主要来自于跨多个arena的consolidation，这种情况下无论是“主动”还是 “被动“都面临不小的压力：因为“垃圾”太少了，回收的成本会变得更高，而“主动”的方式会带来查询效率的提升，这时候“主动”的方式也需要修改，按照“被动”的方式挑选合适的文件。下面简单描述下 mace 中是如何实现的

简单来讲就是引入一个间接层，原本通过 page id 来找到 frame 需要结果 page table 先找到 addr，再从 addr 解出 file_id 和 offset；引入间接层之后，将 file_id 分为 logical id 和 physical id，addr 总是由 logical id 和 offset 组成（注意，这里的 offset 并不是文件的 offset，而是内存中 buffer 的偏移），这就需要在内存中维护一个 logical id 到 physical id 的映射（Mapping）。在 GC 过程中由于文件的合并，会出现多个 logical id 指向同一个 physical id 的情况

哪些需要回收？

前面提到，在 mace 中垃圾的主要来源是 consolidation 操作的结果（目前还没有实现 merge SMO），因此需要回收的数据就是 consolidate 成功时那些被合并的 frame，我们为这些 frame 增加一个 Junk 的标志，在 consolidate 过程中收集参与的 frame，在成功时，分配一个新的 frame，其内容就是参与的 frame 的 addr。也就是说，当前 arena 中的 Junk 可能来自当前的 arena （注意：这里是一个优化点），也可能来自之前的 arena

哪些需要保留？

在 mace 中数据文件的格式如下

end                                                                          begin 
+--------+------+-------------+-------------+-------+---------------------------+
| footer | lids | map entries | relocations | junks |  frames (normal, slotted) |
+--------+------+-------------+-------------+-------+---------------------------+

其中 footer 记录元数据，lids 表示指向当前文件 (physical id）的 logical id 的列表，map entries 则是 page id 到 addr 的映射列表，relocations 这是 addr 到 frame 地址的映射列表，junks 则是合并后的 Junk frame 的内容（即 addr）的列表，最后 frames 则是数据

所谓的 GC 就是去掉 Junk，为了防止碎片话还需要将多个文件合并成一个，那么原文件中的活跃的 frame 肯定是要保留的，而其中的 lids，map entries 等则需要根据 junks 和其他条件进行过滤，例如：一个文件中的活跃 frame 为 0 时，那么 map entries 和 relocations 可能就不需要了，而 junks 可能因为指向的文件中仍然存在活跃的 frame，因此得以保留

具体流程

目前，mace 通过 gc_ratio 和 buffer_size 参数决定是否进行 GC 以及选择多少个文件进行合并，而文件的需要在策略则来自 https://note.o2c.fun/article/102 描述的 MDC（其中 \(up_{2}\) 和 \(now\) 均为 logical id，因为 logical id 是单调递增的）

首先，通过 timeout 进入 GC 出来函数，在函数中收集 Mapping 中记录的空闲率，如果超过了 gc_ratio 那么运行进入后续流程，随后将收集到的列表根据 MDC 排序找到活跃的 frame 的大小能达到 buffer_size前若干个文件，它们就是要进程 GC 的 victims

接下来就是过滤掉 victims 中不再需要的部分。一个文件中的活跃 frame 可能在运行过程中被标记为 Junk，而我们并不会直接修改文件，而是在 Mapping 中通过 bitmap 来管理。因此在对 victims 过滤时，只需要保留 bitmap 中没有 mask 的部分（即：没有被标记为 Junk），这些映射保存在 relocations 部分；同时，如果 relocations 中的 addr 不再有映射，那么也需要将它从 entries 中删除；最后是对 junks 的过滤，如果 junk 的 addr 存在 victims 中，或者它对于文件没有活跃的frame了，那么就需要去掉

最后，利用过滤 victims 过程中收集到的信息，将数据从原文件读取，再写到新的文件中，随后更新 Mapping，接着删除废弃的文件即可

下面是未触发 GC 和触发时的对比 (gc_ratio = 20)

λ cargo test --test bench --release -- --nocapture 
   Compiling mace v0.0.1 (/home/workspace/gits/github/mace)
    Finished `release` profile [optimized] target(s) in 0.57s
     Running tests/bench.rs (target/release/deps/bench-d7dc81929c462d97)

running 1 test
db_root "/tmp/mace_tmp_292795"
put 779 get 93
test bench ... ok

λ du -sh /tmp/mace_tmp_292795
108M    /tmp/mace_tmp_292795

λ cargo test --test bench --release -- --nocapture 
   Compiling mace v0.0.1 (/home/workspace/gits/github/mace)
    Finished `release` profile [optimized] target(s) in 0.55s
     Running tests/bench.rs (target/release/deps/bench-d7dc81929c462d97)

running 1 test
db_root "/tmp/mace_tmp_58261"
put 738 get 99
test bench ... ok

λ du -sh /tmp/mace_tmp_58261
37M     /tmp/mace_tmp_58261