Rust无锁栈实现（从零开始构建高性能并发栈）

为什么选择Rust实现无锁结构？

Rust 的所有权系统和内存安全保证，使其成为实现并发数据结构的理想语言。结合 std::sync::atomic 模块提供的原子类型，我们可以安全地构建 无锁数据结构，避免数据竞争（Data Race）。

核心思路：使用 Compare-And-Swap (CAS)

无锁栈的核心是使用 CAS（Compare-And-Swap）操作来原子地更新栈顶指针。Rust 中通过 AtomicPtr 和 compare_exchange 方法实现。

完整代码实现

下面是一个完整的 Rust 无锁栈实现：

use std::ptr;use std::sync::atomic::{AtomicPtr, Ordering};struct Node<T> {    data: T,    next: *mut Node<T>,}pub struct LockFreeStack<T> {    head: AtomicPtr<Node<T>>,}impl<T> LockFreeStack<T> {    pub fn new() -> Self {        Self {            head: AtomicPtr::new(ptr::null_mut()),        }    }    pub fn push(&self, data: T) {        let new_node = Box::into_raw(Box::new(Node {            data,            next: ptr::null_mut(),        }));        loop {            let head = self.head.load(Ordering::Relaxed);            unsafe {                (*new_node).next = head;            }            match self.head.compare_exchange_weak(                head,                new_node,                Ordering::Release,                Ordering::Relaxed,            ) {                Ok(_) => return,                Err(_) => continue, // 重试直到成功            }        }    }    pub fn pop(&self) -> Option<T> {        loop {            let head = self.head.load(Ordering::Acquire);            if head.is_null() {                return None;            }            let next;            unsafe {                next = (*head).next;            }            match self.head.compare_exchange_weak(                head,                next,                Ordering::Relaxed,                Ordering::Relaxed,            ) {                Ok(_) => {                    let node = unsafe { Box::from_raw(head) };                    return Some(node.data);                }                Err(_) => continue, // 重试直到成功            }        }    }}impl<T> Drop for LockFreeStack<T> {    fn drop(&mut self) {        while self.pop().is_some() {}    }}

代码详解

• Node 结构体：每个节点包含数据和指向下一个节点的裸指针。
• AtomicPtr：用于原子地存储和更新栈顶指针。
• push 方法：创建新节点，并通过 CAS 循环尝试将其设为新的栈顶。
• pop 方法：尝试 CAS 将栈顶移动到下一个节点，成功后释放旧节点并返回数据。
• Drop 实现：确保栈被丢弃时清理所有剩余节点，防止内存泄漏。

内存序（Ordering）的选择

在原子操作中，我们使用了不同的内存序：

• Ordering::Relaxed：仅保证原子性，不提供同步或顺序约束。
• Ordering::Release：确保在该操作之前的所有写操作对其他线程可见。
• Ordering::Acquire：确保该操作之后的读操作能看到其他线程 Release 的写操作。

合理使用内存序可以在保证正确性的同时提升性能。

测试我们的无锁栈

你可以用以下代码简单测试：

use std::thread;fn main() {    let stack = LockFreeStack::new();    let stack_arc = std::sync::Arc::new(stack);    let mut handles = vec![];    // 多线程 push    for i in 0..10 {        let stack_clone = stack_arc.clone();        handles.push(thread::spawn(move || {            stack_clone.push(i);        }));    }    for handle in handles {        handle.join().unwrap();    }    // 多线程 pop    let mut handles = vec![];    for _ in 0..5 {        let stack_clone = stack_arc.clone();        handles.push(thread::spawn(move || {            println!("Popped: {:?}", stack_clone.pop());        }));    }    for handle in handles {        handle.join().unwrap();    }}

注意事项与局限性

虽然这个实现展示了 Rust并发编程 的强大能力，但实际生产环境中还需考虑：

• ABA 问题：虽然本例中影响较小，但在某些场景下需使用带标签的指针（Tagged Pointer）解决。
• 内存回收：更复杂的无锁结构通常需要使用 Hazard Pointer 或 Epoch-Based Reclamation 等技术。
• 性能调优：在高竞争场景下，可能需要优化重试策略或使用更高级的算法。

结语

通过本文，你已经掌握了如何用 Rust 实现一个基本的无锁栈。这不仅加深了你对 原子操作Rust 的理解，也为构建更复杂的并发系统打下了基础。记住，无锁编程虽强大，但也更复杂——务必充分测试！

希望这篇教程对你有帮助！如果你喜欢，请分享给其他 Rust 学习者。