mace 记录 -- Split SMO

BwTree的分裂分为两个阶段：child split 和 parent update

Child Split

假设要分裂的page为P，那么先找到P中的 sep-key （通常就是中间位置的key），然后新分配一个page位Q，Q中包含P里面大于 sep-key的所有记录，然后将Q链接到P的右兄弟R(Q->link = P->link)，随后将Q添加到page table中（注意：由于Q只对当前线程可见，因此这个操作不需要CAS）

以上的操作对其他线程是不可见的，为了使其可见，需要安装一个split-delta，这个delta包含了1. sep-key，用来使原P中大于sep-key的查找失效，转而向Q中查找；2. 一个指向Q的逻辑指针，即：Q的 page id。这里的安装指的是：将 split-delta插入到 delta chain 中，在P的前面

split-delta的结构可能是


struct SplitDelta<'a> {
    sep_key: &'a [u8],
    /// 指向Q的逻辑指针
    logical_ptr: u64,
    /// 指向P（或新插入delta）的物理指针，即 page address
    chain_next: u64,
}

以上就是分裂的前半部分。这部分完成后，当查找遇到split-delta时，与sep-key比较，如果大于sep-key，那么跟随逻辑指针到Q中查找，否则跟随物理指针，占delta chain上查找，最终到P查找

Parent Update

为了能在查找时直接找到Q，需要在P和Q的父节点中添加到Q的索引，这里叫做index-delta，它包含：1. key-PQ，作用是将查找落到P上；2. 到Q的逻辑指针，即：Q的page id；3. 父节点中到Q的索引key，这里姑且叫做key-QR （R是Q的右兄弟节点），作用是将查找落到Q上。这个index-delta将会插入到父节点所在的delta chain 中

parent_update.png

index-delta的结构可能是


struct IndexDelta<'a> {
    /// 到P的索引key
    key_pq: &'a [u8],
    /// 到Q的索引key
    key_qr: &'a [u8],
    /// 到Q的逻辑指针
    logical_ptr: u64,
    /// 到父节点的物理指针
    chain_next: u64,
}

以上就是分裂的后半部分。这部分完成后，当在父节点中查找遇到index-delta时，将key和 key_pq以及key_qr比较，如果落在区间(key_pq, key_qr]就跟随logical_ptr到Q上查找，否则跟随chain_next到原来的delta chain中查找，多半还是原来P的父节点上进行二分（除非P的父节点仍然是index-delta)

Consolidate

前面分裂的两个步骤中都产生了新的delta，为了优化查找性能，需要将过长的delta chain进行合并

以上是原文的描述，但在实践中是需要一些修改的和考量的，例如：1. consolidate；2. lookup

Consolidate

需要完整的 consolidate delta chain，否则会出现问题，例如delta chain 为 12 -> 13 -> 14，这时出发了 consolidate ，将 12 和 13 合并为一个，但合并后由于超过了 page 大小上限，又开始 split 将 12 和 13 分为两个部分，显然 split-key 为 13，提到 parent 中。但问题后续查找 14 时，会先到 13 ，在 13 的 child 中找 14，而实际上 14 在 12 的后面，结果就是找不到 14 如图

pid
2               13
                /
1            12 -> 14

然而完整的 consolidate 在频繁顺序插入的场景下性能不高并且浪费资源，因为 delta chain 的长度记录在并发环境中并不是准确的刚好达到设置的上限，并且加上 consolidate 只有最后的那个线程才能成功，因此 delta chain 的长度实际上要长于设定的长度，由于一直有新的插入导致 consolidate 不断的失败，delta chain 可能会变得很长，

不过可以像split那样修改为其他线程辅助完成 consolidate

Lookup

和常规B+树不同的是，BwTree的节点是虚拟节点，由 delta + base 组成，并且 delta 是无序的，只有 base 中的key才是有序的，因此在查找时必须遍历 delta chain，由于 split 操作会将 split-delta 和 index-delta 这种特殊的 delta 加入到 delta chain 中，因此在遍历是需要特殊的处理

但是，可以观察到的是，遍历 delta chain 遇到 split-delta 时我们可以直接跳过它，只需要跟随它的chain_next找到它在 delta chain 中的后续节点，因为我们进行的是 full consolidate，Q就是最右边的节点，它只保持了 P 中大于 sep-key 的数据，而 P 中保存了完整的数据，与其经过Q的逻辑指针找到Q再从Q中查找，不如直接在 P 中查找。同时，对内部节点配置更小的 delta chain 长度上下，让它们尽快的进行 consolidate，这样大概能弥补间接查找带来的损耗

Q: 那么 parent update 何时进行呢？

A: 当所有的线程在进行查找时发现了 split-delta就会进行 parent update，和 consolidate 一样， parent update 也只会有一个线程成功

Q: 那么后续的线程如何知道已经完成了 parent update 呢，毕竟 split-delta 一直都在，直到 consolidate 完成？

A: 我们使用一个 epoch 计数，在生成 split-delta 时增加 1，这样从 parent 找到 split-delta 时就会发现 epoch 不同，从而知道发生了分裂。而在进行 parent update 生成 index-delta 的 epoch 设置为 split-delta 的 epoch，这样在 parent update 完成后，只有通过 index-delta 才能索引到 split-delta ，而这两者的 epoch 相同，因此不会重复进行 parent update。注意⚠️：进行 parent update 的判断是：1. 找到的 Index 节点是 split-delta；2. 它的 epoch 和当前节点不同

除此之外，实际上还有另外的问题：consolidate 完成后的 page 大小超过了设定的值，于是开始 split，但 split 完成后 page 大小仍然超过了设定值，这时就需要再次进行 split。但 split 只能对 base 进行，而此时的 delta chain 是 -> split-delta -> base，因此需要做一些处理：1. 限制 consolidate 的 page 大小；2. 再次 consolidate 后再次进行 split；3. 跳过检查 split-delta