Mace 是一款由 Rust 编写的高性能嵌入式 Key-Value 存储引擎。它的设计初衷是寻找一种平衡：既能拥有 LSM 树的写入吞吐量，又能具备 B+ 树的查询预测性（参考 kv_bench）
本文作为 mace 的后续，去掉淘汰的设计和实现，补充新的功能和优化
Manifest
早期的 Mace 使用类似 WAL 的append-only log + snapshot 的方式存储，但随着功能的迭代，这种方式有两个大问题： - 无法查找 - 空间占用大
还有一些小问题，如：使用复杂，需要小心谨慎的安排数据的写入顺序 其中无法查找带来的问题是：必须在内存中保存完整的元数据映射，这也就导致为了避免日志不停的变大需要定期将内存dump到snapshot，简单计算一下发现当数据规模在 61TB 时需要dump 11GB左右的元数据，这会严重影响前后台线程的工作
为了解决这个问题，Mace 引入了 btree-store 一个基于 COW 的持久化存储（吊打 lmdb），将不同的元数据分散到不同的 bucket 中，按需加载，按需更新。同时 Mace 本身的 bucket 支持需要使用 bree-store
Namespace (bucket)
原本 Mace 只有一个索引树，要增加 namespace 功能要么使用子树，要么使用 key prefix 分片，但这两者皆有弱点，在 namespace 删除时需要遍历整颗（子）树。在引入 btree-store 后，Mace 对原本的 manifest 进行了分片，所有的 namespace 有独立的 Page Table、Buffer Manager、Cache 但共享数据文件和日志文件（目的是减小fd膨胀）在 btree-store 中存放 name -> bucket_id 的映射
Vacuuming
对于硬盘上的旧数据，Mace 增加了后台的 scavenger 程序定期的扫描数据，如果 Node 存在过期的版本或者 delta 链过长，那么会被 compact 到新的 Node，旧的数据交由 GC 程序回收
但对于不加载的 bucket 来说，过期的数据用于无法被清理。为此，Mace 提供对外接口，允许用户手动调用清理程序
除此之外，由于 btree-store 本身是 COW 的，因此它也会产生垃圾，Mace 同样提供对外接口，允许用户对 btree-store 进行在线瘦身
Buffer
这个模块的改动不大，但修复了一个设计上的遗漏：在 Mace 中对于大 value 会在 Node 中存放 remote pointer，对于旧版本同样是存放的 remote pointer。但在 Arena 分配内存时没有考虑到这一点，可能出现 Node 和 remote data 分配在不同的 Arena，如果 Node 所在的 Arena 在 flush 后系统崩溃了，那么在恢复后 Node中的 remote pointer 就变成了 dangling pointer。对于这种情况 Mace 修改了 Arena 的分配方式，保证不存在跨 Arena 分配的情况
还有一点可以提及一下，Mace 尝试过将 Arena 真正作为 “Arena”，即：预先分配固定大小的内存块，专门给小块的内存分配使用。但结果是性能倒退，原因很简单，内存分配在 Mace 中是绝对的 hot path，当固定大小的内存块分配完成后需要申请下一块固定大小的内存块时，不管使用积极的 CAS 替换和消极的 Mutex 都会带来巨大的开销，导致插入性能下降。当然或许可以 fine-tune 一下固定大小内存块的大小，使用一块即可。但这也不能绕过 Mace 的基于 reference counting 的生命周期管理，也就是说对固定大小的内存块分配的管理本身也是一种开销，同时也会增加复杂性
Scalable TxnKV/TxnView
在原设计中有一个 worker 的概念，worker 绑定了 WAL、TxnKV 和 TxnView 绑定了 worker，结果就是事物的并发受限于worker的数量，为了突破这个限制，Mace 引入了两个中间层：WriterGroup、CCPool
CCPool
对于只读事务（TxnView）来说，根本不会写 WAL，但还是需要和 WAL 绑定，这本身是不合理的，实际上对于只读事务来说只需要关心哪些数据是可见的即可
而这个可见性检查是在 ConcurrencyControl 完成的，因此 Mace 引入了 CCPool （CC Node Pool）一个对象池，用于管理 CCNode (包装了 ConcurrencyControl) ，在 TxnView 初始化时分配一个 CCNode 在 TxnView drop 时归还，这样对于 TxnView 来说 CC 就和 worker/WAL 分离了
这个修改还需要考虑到对 CommitTree 压缩的影响，因为全局的可见性 water mark 必须要向前推进，同时避免对前台线程的影响，引入单独的后台收集线程来追踪所有 TxnView 中最旧的 start_ts （txid）用于 CommitTree 的压缩和全局 water mark 的计算
WriterGroup
对于 TxnKV 来说是必须要写日志的，因此不得不和 WAL 绑定，但对于可写事务来说也并不是一直都在写日志，因此 Mace 引入了中间层 WriterGroup
简单来说，多个 TxnKV 会在初始化时分配到若干个 WriterGroup 而 WriterGroup 使用锁对 WAL 进行保护，并且共享 ConcurrencyControl 。这么做的一个明显的问题是：所在并发增加 WriterGroup 的锁竞争会变得激烈，但好在 Mace 本身支持多个 WAL，相当于是对锁做了分片，另外 Mace 对日志写了路径做了优化，昂贵的 fsync 操作不会在持有锁时进行。还有一个问题是：ConcurrencyControl 不得不进行改造，之前是按照 worker id 用于可见性判断和计算 LCB，现在必须替换成 group id， 并且现在允许并发的修改 ConcurrencyControl，因此额外引入顺序锁对共享的缓存进行保护
引入 WriterGroup 的代价是：性能倒退，不过 Mace 已经尽力做好了 scalable 和 performance 的 trade-off 目前性能反倒有所提升
Index
对 Mace 的随机插入进行 profile 发现：随机插入的性能和内存分配有巨大关系，特别是 SMO 和 consolidate 相关的内存分配。Mace 的索引是基于 Bw Tree 实现的，在 Bw Tree 中 consolidate 和 SMO 都需要各个参与的线程进行内存分配，然后将 delta 合并到 base page，然后使用 CAS 替换 Page Table 中的 addr，并发越高那么 CAS 的竞争及越激烈，并且只有一个线程能够成功的完成 CAS，而其他所有线程分配的内存都CAS都变成了沉没成本
对于这个问题，Mace 在 Node 中引入了 Mutex 用于防止并发的 SMO 和 consolidate，实测效果显著。但还存在另一个问题：对于 Leaf Node 的插入来说仍然是使用 COW + CAS 的模式，每次需要分配一个 Page 指针，并且 ImTree 的修改节点也都需要重新分配。因此 Mace 将这种方式修改成了原地插入，代价是对 Leaf Node 加锁。这么做的结果是：随机插入性能再次提升，而顺序插入则受到影响。不过这也有一个好处：原来 CAS 失败后不得不重新从 root 开始插入，因为你不知道这个 Leaf Node 是否 consolidate 了或许发生了SMO，现在不需要这一步了，因为 SMO/consolidate 都受锁保护，当插入线程拿到锁后只需要检查 Page Table 中的 addr 是否变化，只有变化时才需要从 root 开始插入。（至于为什么要从 root 插入，是因为原版算法中提到的从当前 parent 逐级往上找的实现过于复杂）
对于顺序插入来说，并发的插入极大概率同时在一个 Leaf Node 上进行，那么它们会竞争同一把锁。对于这个问题其实没有很有效的解法，contention split、delta 分片、线程选主批量插入、减小锁持有时间等都不能治本。但目前来看，现有的测试中 Mace 的顺序插入性能也是吊打 RocksDB 的，优化暂时可以缓一缓
另外，Mace 还增加了一项优化，避免在 SMO 时的额外 consolidate，以 merge 举例，之前实现的流程中有这样两步：标记 node 正在 merge，标记 parent 正在merge的child的page id。因为原版 Bw Tree 是 appnd-only 的，因此需要新分配一个 base page 将这些标记合并进去再发布到 Page Table 这样其他线程才能看到。但这其实是不必要的，在 Mace 中在 Node 中引入了一个共享的状态，直接对这个状态进行设置即可，不需要进行 consolidate。目前的 merge 实现已经替换为这种方式，而 split 则保留，原因是原版更优雅
最后，Leaf Node 修改为 update-in-place 后对查询产生了影响，因此在查询时需要对 ImTree 进行 clone，借助 COW 的优势并不会造成性能倒退。简单来说 Mace 中的 Bw Tree 仅保留了 append-only 的特性，变成了混合 fine-grained lock + cow 的实现
Outlook
经过几个月的发展，Mace 不仅是性能和可扩展性的提升，也通过了故障注入测试、压力测试和混沌测试。Mace 的工作重心已经转移到了稳定性保证，下一步是将存储格式稳定下来，做好监测和数据迁移、修复工具发现并解决bug，准备大的版本跳跃