TableofContents

实现区间树的起因

区间树实现简介

插入/删除

查询重叠操作

使用SafeRust实现区间树

问题

RcRefCellT
i.线程安全问题

其他智能指针
?

数组模拟指针

总结

01、实现区间树的起因

在Xline最近的一次重构中，我们发现有两个在关键路径上的数据结构SpeculativePool和UncommittedPool导致了性能瓶颈。这两个数据结构用于在CURP中进行冲突检测。具体来说，由于CURP协议的要求，对于每个处理的command，需要在已经接收的commands中找到所有与当前command相冲突的commands。

例如对于KV操作put/get_range/delete_range，我们需要考虑这些操作之间可能的冲突情况。由于每个KV操作都会有一个key的范围，所以问题就转化为要查询某一个key范围和某个Pool中所有key范围的集合是否有相交。采用朴素遍历整个集合的方法会导致每次查询的时间复杂度为O(n)，从而降低效率并导致性能瓶颈。

为了解决这一问题，我们需要引入区间树这一数据结构。区间树能够高效支持重叠区间的插入，删除和查询操作，这三种操作都可以在O(log(n))的时间内完成。因此，我们可以利用区间树维护key范围的集合，从而解决性能瓶颈的问题。

02、区间树实现简介

Xline中的区间树是基于IntroductiontoAlgorithms(3rded.)实现的，它是由二叉平衡树扩展而来。

区间树以一颗二叉平衡树为基础(例如使用红黑树实现)，将区间本身作为平衡树的key。对于区间[low,high]，我们首先按照low值进行排序，如果low值相同，再按照high值进行排序，这样对区间集合能够定义一个全序的关系(如果不处理重复区间则不需要对high排序)。同时，对于平衡树的每一个节点，我们在这个节点上记录以这个节点为根的子树中high的最大值，记为max。

插入/删除

与红黑树的插入/删除相同，最坏时间复杂度为O(log(n))

查询重叠操作

给出一个区间i，我们需要查询当前树中是否有区间和i重合。在IntroductiontoAlgorithms中给出的伪代码如下

有了max的定义，解决这个问题的思路就非常简单了:对于以x为根的子树T_x，如果i不和x_i相交，那么i一定是在x_i的左侧或者右侧。

1.如果i在x_i的左侧这时可以直接排除右子树，因为这时比x_还要小

2.如果i在x_i的右侧在这种情况下，我们无法直接排除左子树，因为左子树中的节点区间仍然可能和i相交。这时候max值就派上用场了:

如果x的左子树中high的最大值仍然小于的话，那么可以直接排除x的左子树。

如果x的左子树中high的最大值大于或等于的话，那么左子树中一定存在和i相交的区间，因为x左子树中所有的low都小于x_，而i在x_i的右侧，所以x左子树中所有的low也小于，因此一定有相交。

通过以上两点可以验证上述伪代码的正确性，并且从代码可以看出查询的最坏时间复杂度为O(log(n))。

03、使用SafeRust实现区间树

困难点

为了构建区间树，我们首先需要实现一个红黑树。在红黑树中，每个树节点需要指向父节点，这就要求一个节点实例存在多个所有权。

RcRefCellT

最初我尝试使用了Rust最常见的多所有权的实现RcRefCellT，树节点结构类似于以下的代码:

structNodeT,V{left:OptionNodeRefT,V,right:OptionNodeRefT,V,parent:OptionNodeRefT,V,}structNodeRefT,V(RcRefCellNodeT,V);

从数据结构定义上看起来还算清晰，但是实际使用起来相当繁琐，因为RefCell要求用户明确地调用borrow，或者borrow_mut，我不得不构建很多helperfunctions来简化实现，下面是一些例子：

implT,VNodeRefT,V{fnleftF,R(self,op:F)-RwhereF:FnOnce(NodeRefT,V)-R,{op(().left())}fnparentF,R(self,op:F)-RwhereF:FnOnce(NodeRefT,V)-R,{op(().parent())}fnset_right(self,node:NodeRefT,V){let_ignore=_mut().(node);}fnset_max(self,max:T){let_ignore=_mut().(max);}}

RefCell使用上不符合人体工程学是一点，更糟糕的是我们在代码中需要使用大量的Rc::clone，因为在自上而下遍历树节点时，我们需要持有一个节点的ownedtype，而不是一个引用。例如在之前提到的INTERVAL-SEARCH操作中，每次x=或者x=，首先需要borrowx本身，再赋值给x。因此需要先取得左(或右)节点的ownedtype，再更新x到新值。这样导致大量的节点计数开销。

具体开销到底有多大?我尝试对于我们上面的实现进行benchmark，使用随机数据插入和删除。我本机环境为Intel13600KF和DDR4内存。

testbench_interval_tree_insert_100bench:9,821ns/iter(+/-263)testbench_interval_tree_insert_1000bench:215,362ns/iter(+/-6,536)testbench_interval_tree_insert_10000bench:2,999,694ns/iter(+/-134,979)testbench_interval_tree_insert_remove_100bench:18,395ns/iter(+/-750)testbench_interval_tree_insert_remove_1000bench:385,858ns/iter(+/-7,659)testbench_interval_tree_insert_remove_10000bench:5,465,355ns/iter(+/-114,735)

使用相同数据和环境，和etcd的golang区间树实现进行对比:

BenchmarkIntervalTreeInsert100-2012374712250ns/opBenchmarkIntervalTreeInsert1ns/opBenchmarkIntervalTreeInsert10_ns/opBenchmarkIntervalTreeInsertRemove100-202458445579ns/opBenchmarkIntervalTreeInsertRemove1ns/opBenchmarkIntervalTreeInsertRemove10_ns/op

可以看到我们的Rust实现并无优势，甚至有时插入操作还会更慢。(注:这里的etcd的节点删除实现似乎有问题，观察节点数量从1000-10000时耗时的增长，复杂度可能不是O(log(n)))

线程安全问题

即使我们勉强接受以上的性能，一个更严重的问题浮出水面:RcRefCellT无法在多线程环境下使用!由于Xline是在Rust的Tokioruntime之上构建，需要在多个线程间共享一个区间树实例。可惜的是，Rc本身是!S，因为Rc内部的引用计数是以非原子的方式递增/减的。那么这就导致整个区间树的数据结构无法发送到其他线程。除非我们采用一个专用线程，并且通过channel与这个线程进行通信，我们无法在多线程环境下使用。

其他智能指针

于是我们需要考虑其他智能指针来解决这个问题。一个自然的想法是使用ArcRefCellT。然而，RefCell本身是!Sync，因为RefCell的borrowchecking只能在单线程下使用，无法同时由多个线程共享，并且ArcT是S当且仅当T是Sync，因为Arc本身允许克隆。

ArcMutexT?

那么在多线程环境多所有权似乎只能够使用ArcmutexT了。但是显然这对于我们的用例来说是一个anti-pattern，因为这样我们就需要对每一个节点都加上一把锁，而树中可能有数十万乃至几百万的节点，这是不可接受的。

QCell

在使用常规方法无果后，我们尝试使用了qcell这个crate，其中QCell作为RefCell的多线程替代品。作者非常巧妙地解决了多所有权下借用检查的问题。

QCell设计

由于qcell的设计在GhostCell的论文中有正式的证明，这里我就介绍介绍一下GhostCell论文中的设计:

在Rust中，对于数据操作的权限和数据本身是绑定在一起的，也就是说，你首先要拥有一个数据，才能修改它的状态。具体一点，想要修改数据T，你要么有一个T本身，要么有一个mutT。

GhostCell的设计概念是将对数据操作的权限和数据本身分开，那么对于一种数据，数据T本身是一个类型，而它的权限同样也是是一个具体的类型，记为P_t。这种设计相比与Rust现有设计就更加灵活，因为可以让一个权限类型的实例拥有对一个数据集合的权限，即一个P_t拥有多个T。在这种设计下，只要权限类型实例本身是线程安全的，它所管理的这一个数据集合也是线程安全的。

在qcell中使用方法如下，首先需要创建一个QCellOwner代表前述的权限，QCellT则表示储存的数据。

letmutowner=QCellOwner::new();letitem=Arc::new(QCell::new(owner,Vec::u8::new()));(item).push(0);

QCellOwner拥有注册到它这里的QCell的读写权限(通过QCellOwner::rw或者QCellOwner::ro)，所以只要QCellOwner是线程安全，QCell中的数据也是线程安全的。在这里QCellOwner本身是S+Sync，QCell也可以是S+Sync只要T满足:

implT:?Sized+SSforQCellTimplT:?Sized+S+SyncSyncforQCellT

使用QCell

得益于它的设计，QCell本身开销非常小(这里的具体的开销不展开讲了)，因为它借助于Rust类型系统使得borrowchecking是在编译期检查的，而RefCell相比之下则是在运行时检查，因此使用QCell不仅能在多线程环境下使用，还能够提升一部分性能。

接下来就是应用QCell到我们的树实现上了。由于QCell只提供内部可变性，要能够使用多重所有权，我们还需要有Arc，结构大致看起来如下:

pubstructIntervalTree{node_owner:QCellOwner,}structNodeRefT,V(ArcQCellNodeT,V);

看起来不错，那么性能如何呢?

testbench_interval_tree_insert_100bench:41,486ns/iter(+/-71)testbench_interval_tree_insert_1000bench:586,854ns/iter(+/-13,947)testbench_interval_tree_insert_10000bench:7,726,849ns/iter(+/-102,820)testbench_interval_tree_insert_remove_100bench:75,569ns/iter(+/-325)testbench_interval_tree_insert_remove_1000bench:1,135,232ns/iter(+/-7,539)testbench_interval_tree_insert_remove_10000bench:15,686,474ns/iter(+/-194,385)

比较之前的测试结果，性能竟然下降了1-3倍。这说明最大的开销不是Cell，而是引用计数，在我们的区间树用例中，使用Arc比Rc慢了非常多。

一个不使用Arc的方法是使用arena分配，即一次性对所有对象分配内存，并且销毁也是一次性的，但是这在树的数据结构中并不适用，因为我们需要动态地分配和销毁节点的内存。

数组模拟指针

性能测试反映出我们的智能指针尝试是失败的。在Rust所有权模型下，使用智能指针来实现树结构是非常糟糕的。

那么我们可不可以不使用指针来实现呢?一个自然的想法是使用数组来模拟指针。

于是我们的树结构重新设计如下:

pubstructIntervalTree{nodes:VecNode,}pubstructNode{left:Optionu32,right:Optionu32,parent:Optionu32,}

可以看出在Rust中数组模拟指针的优势是不需要某个节点的所有权，只需要记录下某个节点在Vec中的位置即可。每次插入新节点即向nodes后面push一个节点，它的模拟指针就是()-1。

对于插入操作非常简单，但是如果我们需要删除节点呢?如果使用朴素的删除方法:更新树节点的指针后直接将Vec中的对应的节点置为空，那么这样就会在我们的Vec中留下一个“空洞”。这样的话我们需要再额外维护一个链表结构来记录这个“空洞”的位置，以便在下一次插入的时候能重新使用。而且这种方法会导致nodes这个Vec的空间难以回收，即使大部分节点已经被删除。

那么如何解决这个问题呢?接下来我参照了petgraph中的方法，在删除一个节点时，将这个节点与Vec中最后一个节点交换再移除，这样就解决了之前的内存回收的问题。需要注意的是，我们需要同时更新与最后一个节点有关节点的指针，因为它的位置发生了变化。在petgraph的图实现中，这个操作可能是很耗时的，因为一个节点可能会连接多条边，但是在我们的树用例中，我们只需要更新这个节点的父亲/左孩子/右孩子总共3个节点，因此这个操作是O(1)的，这样就非常高效的解决了节点删除的问题。

我们再来对我们的新实现进行benchmark:

testbench_interval_tree_insert_100bench:3,333ns/iter(+/-87)testbench_interval_tree_insert_1000bench:85,477ns/iter(+/-3,552)testbench_interval_tree_insert_10000bench:1,406,707ns/iter(+/-20,796)testbench_interval_tree_insert_remove_100bench:7,157ns/iter(+/-69)testbench_interval_tree_insert_remove_1000bench:189,277ns/iter(+/-3,014)testbench_interval_tree_insert_remove_10000bench:3,060,029ns/iter(+/-50,829)

从结构来看这次的性能提升非常之大，对比之前的RcRefCellNode或者是etcd的golang的实现大约快了1-2倍。

使用数组模拟指针不仅轻松解决了所有权的问题，并且由于数组内存的连续性使其对于缓存更加友好，比纯指针性能甚至会更高。

04、总结

至此，我们成功完美解决了使用safeRust实现区间树的问题。从之前所述的多种尝试来看，在Rust中使用引用计数智能指针来实现树或者图的数据结构是失败的，因为这些智能指针并不适用于大量的内存操作。将来如果需要使用safeRust实现指针类数据结构，我会优先考虑使用数组而不是智能指针。

往期推荐

1.Xline源码解读（一）——初识CURP协议

2.Xline源码解读（三）——CURPServer的实现