mace 记录 -- MVCC

基本使用了《Scalable and Robust Snapshot Isolation for High-Performance Storage Engines》的方式

可见性判断

可见性判断采用的的 LeanStore 中的 LCB (Last Commit Before)，简单来讲就是每个 worker 本地有一个数组（这里叫做 log ）记录了本地事务的 commit_ts 和 start_ts 对，在对当前事务的start_ts判断可见性时，拿到当前获取的 KV 的 txid 和 worker_id，在对应 worker 的 log 中找到第一个小于 start_ts 的 commit_ts 对应的 start_ts（这里叫做 history_txid），如果这个 history_txid <= start_ts 那么说明当前找到的 KV 是见的

由于 LCB 需要跨线程操作，因此为了避免这种情况，可以在每个 worker 本地使用一个 cache 数组来存放上一次的 LCB 值，当本地 cache 可见性测试失败时再进行 LCB 测试

提交协议

在 mace 中，只读事务是不需要 commit 的，对于读写事务，如果整个事务中没有发生修改，那么简单的在 WAL 中记录 commit 即可，并且不需要等待 WAL 落盘

对于发生修改的事务的提交需要等待 WAL 完成刷盘，在 mace 中使用 Group Commit 完成 WAL 刷写和可提交通知

Group Committer

和 LeanStore 不同，由于 mace 是 append-only 的，因此不存在 “Remote Dependency”。这样在 mace 中 Group Committer 就是一个后台线程负责从每个 worker 收集 WAL entry，通过 AIO 刷盘，最后通知 worker 日志已刷盘可以提交，具体流程如下

事务开始时，worker 记录当前的 GSN （Global Sequence Number，即： LSN）和 start_ts
每次修改时在 WAL entry 中记录 txid，gsn
group committer 后台线程拿到 WAL entry，计算最小的 txid 和 gsn，并将 WAL entry 刷盘
事务提交时等待 group commiter 通知
group committer 判断最小的 txid 和 gsn 是否 >= woker 记录的 start_ts 和 gsn，如果是则通知 worker 提交

版本存储

由于 mace 是 append-only 的，因此天然支持多版本存储，并且 mace 增加了 sibling page 用于存放相同 key 的不同的版本（New-to-Old）

避免 page 分裂时将相同的 key 的不同版本分裂到不同分的 page 导致错误
节省存储空间
加快历史版本查找，只需要使用 txid 进行二分查找即可，避免进行遍历

垃圾回收

在 mace 中，不存在 LeanStore 那样的 graveyard，因为版本都存放在 delta-chain 或者 sibling-chain 中。因此对于 mace 来说，垃圾回收指的是：在 consolidate 时删除访问不大的版本

收集 watermark

为了实现垃圾回收，首先需要获取一个 watermark 用来决定哪些版本是无法被访问到的，这个 watermark 在 mace 中，由 ConcurrencyControl 维护，每当 Txn commit 时 cc 有一定1/nr_worker 的概率进行 watermark 的收集，具体流程如下：

遍历所有的 worker，找到当前最小的 active txid 记为 oldest_tx
再次遍历所有的 worker，通过 LCB 传入 oldest_tx 找到这个worker最新的可见的 txid 记为 local_wmk_old，这个值需要存到 worker 本地，因为后续这个 worker 可能都是只读的事务，可以避免 LCB 直接取本地的缓存
在所有local_wmk_old中找到最小的那个，就是我们要收集的 watermark，这个值存放在全局的 Context 中

执行回收

执行回收其实就是在 consolidate 过程中，丢掉 1. txid 小于 watermark 2. 并且是重复的（相同 raw 但版本最老的） 3. 或者标记删除的数据

优化 mace 增加了 sibling page，因此在 consolidate 时需要将它展开，在 consolidate 后又生产新的 sibling page

或许可以不用展开，直接为 sibling page 增加“删除”，这样可以复用空间，但增加删除，那么插入就不再有序，需要在 page 内移动数据，增加了时间消耗，这里是一个 trade-off