Xline中区间树实现小结

Table of Contents

  1. 实现区间树的起因
  2. 区间树实现简介
    1. 插入/删除
    2. 查询重叠操作
  3. 使用Safe Rust实现区间树
    1. 问题
    2. Rc<RefCell<T>>
      i. 线程安全问题
    3. 其他智能指针
      i. Arc<Mutex<T>>?
      ii. QCell
    4. 数组模拟指针
  4. 总结

01、实现区间树的起因

在Xline最近的一次重构中， 我们发现有两个在关键路径上的数据结构Speculative Pool和Uncommitted Pool导致了性能瓶颈。这两个数据结构用于在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中的区间树是基于 Introduction to Algorithms (3rd ed.) 实现的， 它是由二叉平衡树扩展而来。

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

插入/删除

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

查询重叠操作

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

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

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

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

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

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

03、使用Safe Rust实现区间树

困难点

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

Rc<RefCell<T>>

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

struct Node<T, V> {
    left: Option<NodeRef<T, V>>,
    right: Option<NodeRef<T, V>>,
    parent: Option<NodeRef<T, V>>,
    ...
}

struct NodeRef<T, V>(Rc<RefCell<Node<T, V>>>);

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

impl<T, V> NodeRef<T, V> {
    fn left<F, R>(&self, op: F) -> R
    where
        F: FnOnce(&NodeRef<T, V>) -> R,
    {
        op(self.borrow().left())
    }

    fn parent<F, R>(&self, op: F) -> R
    where
        F: FnOnce(&NodeRef<T, V>) -> R,
    {
        op(self.borrow().parent())
    }

    fn set_right(&self, node: NodeRef<T, V>) {
        let _ignore = self.borrow_mut().right.replace(node);
    }

    fn set_max(&self, max: T) {
        let _ignore = self.borrow_mut().max.replace(max);
    }
    ...
}

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

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

test bench_interval_tree_insert_100           ... bench:       9,821 ns/iter (+/- 263)
test bench_interval_tree_insert_1000          ... bench:     215,362 ns/iter (+/- 6,536)
test bench_interval_tree_insert_10000         ... bench:   2,999,694 ns/iter (+/- 134,979)
test bench_interval_tree_insert_remove_100    ... bench:      18,395 ns/iter (+/- 750)
test bench_interval_tree_insert_remove_1000   ... bench:     385,858 ns/iter (+/- 7,659)
test bench_interval_tree_insert_remove_10000  ... bench:   5,465,355 ns/iter (+/- 114,735)

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

BenchmarkIntervalTreeInsert100-20                 123747             12250 ns/op
BenchmarkIntervalTreeInsert1000-20                  7119            189613 ns/op
BenchmarkIntervalTreeInsert10_000-20                 340           3237907 ns/op
BenchmarkIntervalTreeInsertRemove100-20            24584             45579 ns/op
BenchmarkIntervalTreeInsertRemove1000-20             344           3462977 ns/op
BenchmarkIntervalTreeInsertRemove10_000-20             3         358284695 ns/op

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

线程安全问题

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

其他智能指针

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

Arc<Mutex<T>>?

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

QCell

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

QCell设计

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

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

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

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

let mut owner = QCellOwner::new();
let item = Arc::new(QCell::new(&owner, Vec::<u8>::new()));
owner.rw(&item).push(0);

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

impl<T: ?Sized + Send> Send for QCell<T>
impl<T: ?Sized + Send + Sync> Sync for QCell<T>

使用QCell

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

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

pub struct IntervalTree {
    node_owner: QCellOwner,
    ...
}

struct NodeRef<T, V>(Arc<QCell<Node<T, V>>>);

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

test bench_interval_tree_insert_100           ... bench:      41,486 ns/iter (+/- 71)
test bench_interval_tree_insert_1000          ... bench:     586,854 ns/iter (+/- 13,947)
test bench_interval_tree_insert_10000         ... bench:   7,726,849 ns/iter (+/- 102,820)
test bench_interval_tree_insert_remove_100    ... bench:      75,569 ns/iter (+/- 325)
test bench_interval_tree_insert_remove_1000   ... bench:   1,135,232 ns/iter (+/- 7,539)
test bench_interval_tree_insert_remove_10000  ... bench:  15,686,474 ns/iter (+/- 194,385)

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

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

数组模拟指针

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

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

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

pub struct IntervalTree {
    nodes: Vec<Node>,
    ...
}

pub struct Node {
    left: Option<u32>,
    right: Option<u32>,
    parent: Option<u32>,
    ...
}

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

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

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

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

test bench_interval_tree_insert_100           ... bench:       3,333 ns/iter (+/- 87)
test bench_interval_tree_insert_1000          ... bench:      85,477 ns/iter (+/- 3,552)
test bench_interval_tree_insert_10000         ... bench:   1,406,707 ns/iter (+/- 20,796)
test bench_interval_tree_insert_remove_100    ... bench:       7,157 ns/iter (+/- 69)
test bench_interval_tree_insert_remove_1000   ... bench:     189,277 ns/iter (+/- 3,014)
test bench_interval_tree_insert_remove_10000  ... bench:   3,060,029 ns/iter (+/- 50,829)

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

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

04、总结

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

往期推荐

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

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/579222.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

速卖通自养号测评：如何规避安全风险？

速卖通自养号测评：如何规避安全风险？

对于初涉电商领域的新卖家而言&#xff0c;进行销量测评显得尤为关键。由于速卖通新店铺往往难以获得平台活动的支持&#xff0c;流量也相对匮乏&#xff0c;因此&#xff0c;开店的首要任务便是进行测评&#xff0c;通过积累一定的评论和销售数据。 测评的益处颇多&#xff0…
阅读更多...
生成完美口型同步的 AI 代言人视频（及其实现原理详解）

生成完美口型同步的 AI 代言人视频（及其实现原理详解）

目录 什么是Heygen? Heygen注册 Video Translation&#xff08;视频翻译 完美口型同步&#xff09; 实现原理详解 视频翻译部分 完美口型同步部分 什么是Heygen? Heygen是一款在线工具&#xff0c;可帮助您生成具有完美口型同步的 AI 代言人视频。 Heygen注册 https:…
阅读更多...
网络安全实训Day23

网络安全实训Day23

网络空间安全实训-渗透测试 文件上传攻击 定义 将Webshell文件上传到网站服务器上&#xff0c;从而获得网站整台服务器控制权限的攻击方式 Webshell 一种以网页形式存在的命令行执行环境&#xff0c;又称网页木马 分类 一句话木马 只有一行代码&#xff0c;功能强大&#xff…
阅读更多...
(bevfusion:多模态融合)报错：AttributeError: module ‘numpy‘ has no attribute ‘long‘

(bevfusion:多模态融合)报错：AttributeError: module ‘numpy‘ has no attribute ‘long‘

解决办法1&#xff1a;降低numpy版本&#xff08;我的报错版本是1.24.4&#xff09; pip install numpy1.20.3解决办法2&#xff1a;或者将np.long改为np.int64 (由于我的报错在环境内部&#xff0c;不好修改&#xff0c;所以直接降低的numpy版本)
阅读更多...
Java中的StringBuilder

Java中的StringBuilder

为什么要用StringBuilder StringBuilder是一个可变的字符串类&#xff08;StringBuilder对象中的内容可变&#xff09; 为什么不用String拼接呢&#xff1f; 因为拼接字符串会造成前两个字符串的空间浪费 package dayhou40.day44; ​ public class test {public static voi…
阅读更多...
Java线程池让使用线程变得更加高效

Java线程池让使用线程变得更加高效

使用一个线程需要经过创建、运行、销毁三大步骤&#xff0c;如果业务系统每个线程都要经历这个过程&#xff0c;那势必带来过多不必要的资源消耗。线程池就是为了解决这个问题而生&#xff0c;需要时就从池中拿取&#xff0c;使用完毕就放回去&#xff0c;池化思想通过复用对象…
阅读更多...
SpringBoot---------Hutool

SpringBoot---------Hutool

第一步&#xff1a;引入依赖 <dependency><groupId>cn.hutool</groupId><artifactId>hutool-parent</artifactId><version>5.7.17</version></dependency> 第二步&#xff1a;各种用法 ①生成随机数 //生成验证码 String s …
阅读更多...
游戏新手村21：再谈游戏广告页面设计

游戏新手村21：再谈游戏广告页面设计

前文我们说到了网页游戏的LandingPage页面设计中需要遵循的一些规范和注意事项&#xff0c;本章我们重点谈下网络游戏的广告页面设计。 之前在金山的时候&#xff0c;大家习惯或者喜欢称LandingPage为分流页&#xff0c;这个页面需要加入哪些游戏信息才能在短时间内俘获玩家的…
阅读更多...
cJSON的使用

cJSON的使用

文章目录 一、CJSON初识二、CJSON解析器基础三、CJSON解析数据JSON解析基础CJSON解析数组数据CJSON解析嵌套数据 五、创建JSON数据 一、CJSON初识 JSON (JavaScript Object Notation)是一种轻量级的数据交换格式&#xff0c;常用于在网络之间传输数据。它是一种文本格式&#…
阅读更多...
Linux计划任务书以及定时任务的编写

Linux计划任务书以及定时任务的编写

一、程序可以通过两种方式执行&#xff1a; 手动执行利用调度任务&#xff0c;依据一定的条件自动执行 自动执行可通过一下两个命令来实现: &#xff08;1&#xff09;At &#xff08;单一工作调度&#xff09; &#xff08;2&#xff09;Cron &#xff08;循环工作调度&a…
阅读更多...
微信小程序的开发

微信小程序的开发

1.了解项目的基本组成结构 pages 用来存放所有小程序的页面 utils 用来存放工具性质的模块(例如:格式化时间的自定义模块) app.js 小程序项目的入口文件 app.json 小程序项目的全局配置文件 app.wxss 小程序项目的全局样式文件 project.config.json 项目的配置文件 sitem…
阅读更多...
(GEE)2000-2020年黄河流域时序渐变图及高程模型计算 JavaScript版

(GEE)2000-2020年黄河流域时序渐变图及高程模型计算 JavaScript版

文章目录 一. 选取目标区域二. NDVI实现三. 高程模型DEM实现四. 时序图五. 植被覆盖类型六. 参考文献 首先推荐吴秋生老师团队开源的便捷构建网站&#xff1a;适用于地理空间应用的Streamlight 吴秋生老师团队的工具请自行探索。本文讲解基于GEE云开发平台实现&#xff0c;基于…
阅读更多...
吾日三省吾身---对平常遇到的错误总结

吾日三省吾身---对平常遇到的错误总结

✨个人主页&#xff1a; 不漫游-CSDN博客 前言 本篇文章是对平常练习遇到的问题总结&#xff0c;多吸取经验教训才能避免未来再犯~ Java语法部分 &#xff08;一&#xff09;多态 思考&#xff1a;这道题很明显考察的是多态的知识点&#xff0c;即一个对象可以被赋值给其父类…
阅读更多...
11.盛最多水的容器 C++

11.盛最多水的容器 C++

一开始我最先想到的是暴力解法&#xff0c;就是两个循环嵌套依次遍历&#xff0c;所有情况都过一遍找出最大值&#xff0c;这样示例的结果虽然是正确的&#xff0c;但是超时。所以暴力解法行不通&#xff0c;双指针思考才是正道&#xff0c;双指针一般都是一边一个&#xff0c;…
阅读更多...
拉链法解决哈希冲突

拉链法解决哈希冲突

1.基本思想: 相同散列地址的记录链成一单链表,m个散列地址就设m个单链表,然后用一个数组将m个单链表的表头指针存储起来,形成一个动态的结构. 例如:一组关键字为{19,14,23,1,68,20,84,27,55,11,10,79},散列函数为:Hash(key)key%13, 就会发现有些元素是同义词,比如14%131,1%131…
阅读更多...
江开2024年春《计算机组成原理 060214》第4次计分作业参考答案

江开2024年春《计算机组成原理 060214》第4次计分作业参考答案

答案&#xff1a;更多答案&#xff0c;请关注【电大搜题】微信公众号 答案&#xff1a;更多答案&#xff0c;请关注【电大搜题】微信公众号 答案&#xff1a;更多答案&#xff0c;请关注【电大搜题】微信公众号 单选题 1某计算机字长32位&#xff0c;其存储容量为4GB&am…
阅读更多...
MySQL__锁

MySQL__锁

文章目录 &#x1f60a; 作者&#xff1a;Lion J &#x1f496; 主页&#xff1a; https://blog.csdn.net/weixin_69252724 &#x1f389; 主题&#xff1a; MySQL__锁&#xff09; ⏱️ 创作时间&#xff1a;2024年04月27日 ———————————————— 这里写目录…
阅读更多...
Java高阶私房菜-JVM垃圾回收机制及算法原理探究

Java高阶私房菜-JVM垃圾回收机制及算法原理探究

目录 垃圾回收机制 什么是垃圾回收机制 JVM的自动垃圾回收机制 垃圾回收机制的关键知识点 初步了解判断方法-引用计数法 GCRoot和可达性分析算法 什么是可达性分析算法 什么是GC Root 对象回收的关键知识点 标记对象可回收就一定会被回收吗&#xff1f; 可达性分析算…
阅读更多...
阳光电源社招前程无忧智鼎题库及远程包过助攻需要重点考察什么？

阳光电源社招前程无忧智鼎题库及远程包过助攻需要重点考察什么？

阳光电源社招前程无忧智鼎题库及远程包过助攻需要重点考察什么&#xff1f; 结合长期服务大型国有企业校招工作的经验&#xff0c;我们总结出阳光电源社招笔试的典型模式&#xff1a;行政职业能力测试企业应知应会测试心理测评&#xff0c;综合考察候选人的政治素养、文化素养…
阅读更多...
VC2022 + protobuf

VC2022 + protobuf

google这是有私心啊&#xff0c;protobuf从某个版本开始&#xff0c;依赖了一个google自己推出的大型组件集&#xff0c;Abseil&#xff0c;有点类似于Boost了&#xff0c;业内用的人&#xff0c;从个人狭窄的圈子来说&#xff0c;应该是不多的&#xff0c;据说google的众贤用的…
阅读更多...
最新文章

Copyright @ 2022~2023