mace 记录 -- Tree 的设计和实现

目前 mace 中的 tree 和前面文章中的记录已经完全不同了（大约是今年 6 月完全重写了），以前的实现几乎是严格按照 Bw-Tree 的论文来的：插入就是先找到 page id 对应的 delta page 的 addr，然后将 addr 替换成新 delta page 的 addr，再将旧的 addr 作为新 delta page 的 next 指针，然后再通过 CAS 替换 page id 对应的 addr；查询就是遍历 delta page 链。好处是插入真的很快，缺点就是查询性能惨不忍睹，因此后面将它完全重写了

新的实现保留了 Bw-Tree 论文中最关键的部分：page table 间接层，以及动态 page 大小。简单来讲，现在的插入变成了插入到一个 COW 的 B+ 树，时间复杂度从 O(1) 变成了 O(logn) 当然这颗树的大小是固定的，默认配置的是 256，这个值是平衡插入/查询性能的结果，如果偏向更好的查询性能可以将这个值减小，如果偏向更好的插入性能则可以将这个值增大。这个想法来自 Sled，mace 对它进行了修改。下面就详细介绍下 mace 中 tree 的插入和查询以及 SMO 的实现

点查询

首先介绍下树中的两种节点：Intl node （internal 或 branch) 和 leaf node，这两种节点的表示是不同的，intl node 的 key 是 &[u8] 它的值是 Index 存放的是指向 page table 的 key 即 page id （后面称 pid），而 leaf node 的 key 除了存放 &[u8] 还存放了 txid 和 command id 它的值则存放的是 worker_id 和 &[u8]，其中 txid、cmd id 以及 worker id 都是为事务服务的。除此之外，intl node 和 leaf node 都存放了 low key 和 high key 用来辅助查询和 SMO

在 tree 中，所有的操作都是从查询开始的，目前不支持子树（其实已经删除了），在初始化时创建了空的 root 节点，root 的 pid 是固定的，因此查询首先使用root pid 经过 page table 找到 root 节点，然后和 key 比较，找到 key 所在的分支，再在分支中查找，直到找到 leaf node，然后在 leaf node 中查找，判断可见性，最后返回结果。整个流程和 B+ 树一样，这里不详细展开，接下来要说的是并发场景下查找中要出来的异常情况

节点不见了

首先就是通过 pid 加载 node，但在加载过程中其他线程可能完成了 merge 操作，已经将 node 给 unmap 了，这时需要回到父节点重新开始查找，而父节点也可能被 unmap 了，这时候就需要到更上一层的节点重新查找，为了简化实现，mace 中直接回到 root 节点重新查找（后续的重新查找也是如此）

节点正在 merge

这里有两种情况，要么是刚通过 pid 找到 node 时就发现它的子节点正在 merge，那么这时需要的时辅助完成 merge；要么是发现 node 自己正在被 merge，这时需要等待 merge 尝试回到父节点，辅助完成 merge 而不是等待

关于 merge 的细节会在后面介绍

加载错了节点

没错，这也是可能的。从父节点找到的子节点的范围必然是包含查询的 key 的，但其他线程可能正在 merge，本线程刚拿到 intl node 中的索引，其他线程就 unmap了节点，这会导致索引节点的元素整体左移，这时本线程在通过索引拿到的节点已经变成了原节点右边的节点，因 key 应该是小于 low key 的。这时同样是重试

需要进行分裂

这也是必要的判断，在 mace 中所有 SMO 之前都会先对节点进行 consolidation 确保没有 delta 存在，因此 split 只会在查找时触发

节点正在进行分裂

接上面一条，节点分裂分为两步：1. 将节点分为两部分，2. 将新节点插入到父节点。本线程发现节点正在分裂（即，其他线程完成了第一步），那么需要辅助完成第二步，然后重试（也许会发现父节点也需要分裂）

需要进行合并

当发现当前节点大小少于阈值时，那么需要触发合并，然后重试

需要 consolidate

如果找到了 leaf node，那么需要判断它的 delta 长度是否到了阈值，如果是，则需要将 delta page 合并成 base page 然后重试

以上就是需要处理的异常情况，本来重试应该是逐级向上的，但实现起来过于复杂，目前重头开始重试还不是 top 的瓶颈（瓶颈在于 IO）因此暂不优化

插入

讲完了查找，插入就比较简单了，因为分裂的情况已经在查询的过程中处理了，因此插入不需要额外的操作。拿到找到的 leaf node，从 key 和 value 构建一个新的 delta，将 delta 插入到 cow b+ 树中，然后替换掉 page table 中的地址即可

consolidate

由于 mace 中数据的存储是追加式的，因此对于插入的 delta 虽然内存中组织为 B+ 树，但在持久化存储上仍然是 delta 组成的链，因此为了后续的查找（尤其是冷数据）需要将过长的 delta 链合并成到一个完整的 base page，mace 中这个链的长度默认是树节点大小的一半

consolidate 主要有两个作用：1. 就是提交查询效率；2. 删除过期的数据，包括不可见的删除的数据以及重复的数据。具体来讲是通过 cow B+ 树和本身的 base page 构建一个 merge iterator，第一次迭代计算所需的内存大小，第二次迭代构建新的 base page，在迭代过程中利用传入的 watermark 过滤掉过期的数据。完成后，通过 CAS 替换掉 pid 指向的地址即可

和原版实现不同的是，原版 consolidation 发生在插入新 delta 后，并且 CAS 失败需要一直重试，这在核越多时性能越差，不仅仅是 CAS 争抢本身，整个过程中还需要一遍又一遍的分配内存和遍历数据，到头来却是在做无用功（因为 CAS 失败后并不知道 pid 对应的新地址是 consolidate 后的 base page 的还是新的插入delta的，只能拿到 pid 对应的最新的地址重头开始）

新实现中，将 consolidate 移到了插入之前，所有线程都会先发现需要 consolidate，为了避免做无用功，首先发现的线程会在 pid 对应的 node 中做一个标记，后续的线程看到这个标记就会重新尝试，而这个标记的线程会自己完成 consolidate

当然，也可以通过在执行 consolidate 前记录 delta 的长度和增加一个版本号（防止ABA，即其他线程完成consolidate后新的插入使得delta又变成了原来的长度），在失败后检查以决定是否要重试

不管怎么讲，总是存在一个段的时间，无非是忙轮训或是等待而已

分裂

分裂的触发条件是：当 consolidate 后的 node 的元素个数达到了配置的上限。因此把分裂触发的检查放在查找路径中必要的，因为可以保证 node 的元素个数达到上限时不存在 delta，这可以简化分裂的实现（简单的将节点分为两部分），有些实现是根据 node 大小来触发分裂的，并且由于 key 和 value 都是变长的，因此会根据某个策略来进行划分，避免造成多次分裂。而 mace 中没有按照大小来划分，mace 中节点大小的上限是可控的，对于过大的 value 不会存储在 node 内部

分裂具体实现是：

找到需要分裂的节点，使用 range iterator 将其分为两半遍历，分别生成两个新的自身节点 lnode 和右节点 rnode，并需要将 lnode 的 right_sibling （即：节点的 pid）赋值给 rnode，随后在 page table 中新分配一个 pid 给 rnode，接着将新的 pid 赋值给 lnode 的 right_sibling，最后使用 lnode 替换原来分裂的节点
将 rnode 的 pid 插入到 parent 中，然后对 parent 进行 consolidate，接着替换掉原来的 parent。如果分裂的节点没有 parent 那么说明它是 root 节点，这时需要使用 lnode 和 rnode 的 pid 生成一个新的节点，然后替换 root 节点

同样，这里也使用了标记来确保只有一个线程在工作，当然两个阶段是可以并行的，如果其他线程发现节点正在分裂，那么它会辅助完成第2个阶段

合并

合并的触发条件是：当节点真实元素个数小于配置节点元素一半时。除此之外，不允许同一个 parent 的多个 children 并发的 merge，这也是为了简化实现，当然，也不允许 parent 和 child 同时发生 merge

merge 的实现要复杂一些： 1. 将要执行 merge 的节点的 pid 赋值给 parent 节点 2. 标记要执行 merge 的节点为正在 merge 3. 找到要标记后的节点的左边节点，然后合并到左边节点 4. 从 parent 节点中删除已经merge节点的 pid 5. 从 page table 中删除已经 merge 节点的 pid，并释放节点内存

这里面省略了节点的 consolidate 和 CAS 替换。要注意的是，在 mace 中不允许 merge 并发执行

COW B+ Tree

这个东西来自于 imbl ，它主要是利用了 Arc::get_mut 的特性，在发生修改时会复制一份，在 mace 中对它进行了修改，支持实现了 Copy trait 的作为 key，具体来讲，在 mace 中用它来存放 delta page 的一个视图，delta page 的内存又 mace 在外部管理，这这样的好处是避免 Copy on Write 时逐个对 B+ 树的节点元素调用 clone 可以直接使用 memcpy 完成拷贝

总的来说，mace 中的 tree 保留了绝大部分 Bw Tree 的特点，根据自身的情况进行了必要的调整和修改。虽然还有很多优化的空间，但目前从 benchmark 的结果来看 tree 的优化可以暂时放一放