无等待Trie从C移植到Rust的并发实现技术问询

为满足高性能计算（HPC）需求，需将无等待Trie（可视为树结构）从C语言移植到Rust语言。该Trie的读写比例为99:1，适用于并行并发场景及单线程多协程的仅并发场景，树结构大小通常在100KB至8MB之间。

核心结构定义如下：

pub struct WFTrie {
    nodes: Vec<Node>,
    leaves: Vec<Leaf>,
    updates: Vec<Update>,
    update_pos: AtomicUsize,
    update_cap: usize,
}

//.... 
let mut wftrie = WFTrie::new(); 
let wftrie_ptr = AtomicPtr::new(&mut wftrie);

//....

该Trie采用类似内存池（arena）的实现方式，通过Vec存储数据，具体逻辑：

• 更新操作：对update_pos执行fetch_and_add操作，若结果超过update_cap则返回错误（空间耗尽），否则当前协程/线程可独占访问updates[update_pos % update_cap]并写入更新内容；
• 批量更新：每累计X次更新（如update_pos % 8 == 0时），某协程会克隆树结构，应用所有待处理更新，再通过compare_and_swap更新wftrie_ptr；
• 读取操作：对wtftrie_ptr执行原子加载，访问树结构时需同时考虑待处理更新。

问题1：多个协程持有树的不可变引用时，单个协程如何执行更新？最符合Rust风格的实现方式是什么？ #

这是典型的读写分离+版本化快照场景，最贴合Rust风格的实现思路如下：

• 用Arc<WFTrie>替代原有的AtomicPtr，所有读操作持有Arc的不可变引用，Rust的借用规则天然允许多个协程同时共享这类引用；
• 执行更新的协程先克隆当前Arc指向的WFTrie实例（因内部存储为Vec，克隆会生成独立的新实例，与原实例无共享状态）；
• 在克隆出的实例上批量应用所有待处理更新；
• 最后通过原子化的Arc替换工具（如ArcSwap）更新全局的Trie实例，保证读操作能感知到新版本。

更新队列部分可保留原子索引逻辑，但需用Vec<UnsafeCell<Update>>替代普通Vec<Update>，在原子索引的保护下安全获取独占的可变引用，避免原生借用规则的限制。

问题2：更新时有协程仍持有旧树的引用，会发生什么？是否应将AtomicPtr替换为Arc？ #

• 旧树的引用依然完全有效：原逻辑的更新是通过克隆新树、替换全局指针实现的，旧树的内存不会被立即回收。只要有协程持有旧树的引用，它就会持续存在——这也是无等待算法的核心特性：读操作无需等待更新完成，可直接访问加载到的版本。
• 必须将AtomicPtr替换为Arc（或ArcSwap这类专用工具）：原代码中AtomicPtr::new(&mut wftrie)直接持有可变引用的裸指针，存在悬垂指针、内存不安全的风险。用Arc<WFTrie>后，引用计数会自动管理内存，所有旧引用释放后旧树才会被销毁，完全符合Rust的内存安全规则。

问题3：该设计是否适配Rust的借用检查器？是否必须使用unsafe代码？ #

• 原设计的核心逻辑不完全适配原生借用检查器：原生规则不允许同时存在可变引用与不可变引用，但通过Arc+克隆替换的方式可绕过此限制——写操作在克隆的独立实例上进行，与原实例的不可变引用无冲突。
• 大部分逻辑可用安全代码实现，但更新队列的独占写入部分可能需要少量unsafe：当多个协程通过原子索引获取更新槽时，需确保每个槽同一时间只有一个写者，此时用Vec<UnsafeCell<Update>>配合原子索引，可通过unsafe安全获取可变引用（只要保证索引的原子性与独占性）。若使用ArcSwap这类成熟库，底层unsafe会被封装，上层代码可完全安全。

另外，原代码中的AtomicPtr<WFTrie>属于明显的unsafe违规用法，替换为Arc后可彻底规避这部分风险。

问题4：在仅并发场景（单线程多协程）下，能否不使用unsafe来移除原子操作？ #

完全可以。单线程多协程场景下，所有协程的执行是串行调度的（同一时间仅一个协程运行），不存在真正的并行竞争，原子操作可直接替换为普通变量：

• update_pos从AtomicUsize改为普通usize，单线程下协程切换会保证内存可见性；
• wftrie_ptr改用Arc<WFTrie>，替换时直接赋值即可，无需原子操作；
• 更新队列的访问无需原子保护，同一时间只有一个协程执行，不会出现并发写入同一个槽的情况。

这种情况下，整个实现可完全用安全Rust代码编写，且性能不会受损——单线程下原子操作的内存屏障开销可被彻底避免。

内容的提问来源于stack exchange，提问作者Mascarpone