从零实现一个无锁并发哈希表

上一篇无锁文章讲了一个结论：大多数自称”无锁”的代码不满足无锁的定义。这篇做另一件事——正确地实现一个。

无锁哈希表的论文很多。Michael (2002) 的 lock-free linked list、Harris (2001) 的 list-based set、Herlihy/Shavit 的 split-ordered list。但论文看完你还是不知道怎么写，因为论文不讲内存回收，不讲 ABA 问题的具体解法，不讲 x86 和 ARM 上的行为差异。

这篇从头来。一行 compare_exchange 开始，一步一步走到可以跑在 x86 和 ARM 上的并发哈希表。

一、CAS：无锁世界的唯一原语

所有无锁数据结构的核心操作是 Compare-And-Swap (CAS)。语义：

CAS(addr, expected, desired):
    atomic {
        if *addr == expected:
            *addr = desired
            return true
        else:
            return false
    }

在 Rust 里是 AtomicPtr::compare_exchange。在 C 里是 __atomic_compare_exchange_n。在 x86 上编译成 LOCK CMPXCHG 指令。在 ARM 上是 LDXR + STXR 循环（LL/SC）。

关键区别：x86 的 LOCK CMPXCHG 是一条指令，要么成功要么失败。ARM 的 LL/SC 可能出现 spurious failure——即使值没变，Store-Exclusive 也可能失败（因为 cache line 被其他核抢了）。这就是为什么 Rust 有 compare_exchange 和 compare_exchange_weak 两个版本：后者允许 spurious failure，在 ARM 上可以编译成更高效的代码。

内存序：你必须选对

CAS 只保证原子性，不保证顺序。你还需要指定内存序 (memory ordering)：

use std::sync::atomic::{AtomicPtr, Ordering};

// 最保守: 完整的顺序一致性
ptr.compare_exchange(old, new, Ordering::SeqCst, Ordering::SeqCst);

// 常用: 成功时 AcqRel，失败时 Acquire
ptr.compare_exchange(old, new, Ordering::AcqRel, Ordering::Acquire);

// 最宽松: Relaxed。不保证任何顺序。
// 只在你完全理解后果时使用。
ptr.compare_exchange(old, new, Ordering::Relaxed, Ordering::Relaxed);

在 x86 上，Relaxed 和 AcqRel 编译出来的代码完全一样——因为 x86 的 TSO (Total Store Ordering) 模型本身就保证了 acquire 和 release 语义。区别只在 ARM 上才体现：AcqRel 会插入屏障指令，Relaxed 不会。

这就是内存屏障那篇讲的核心问题在数据结构层面的具体化：你在 x86 上测试通过的无锁代码，可能在 ARM 上随机崩溃。

二、链表法：最简单的无锁哈希表

哈希表 = 数组 + 冲突解决。无锁版本的最简单实现：数组的每个 bucket 是一个无锁链表。

use std::sync::atomic::{AtomicPtr, Ordering};
use std::ptr;

struct Node<K, V> {
    key: K,
    value: V,
    next: AtomicPtr<Node<K, V>>,
}

struct LockFreeHashMap<K, V> {
    buckets: Vec<AtomicPtr<Node<K, V>>>,
    bucket_count: usize,
}

Insert

CAS 循环插入链表头部：

fn insert(&self, key: K, value: V) -> bool
where K: Hash + Eq
{
    let idx = self.bucket_index(&key);
    let new_node = Box::into_raw(Box::new(Node {
        key,
        value,
        next: AtomicPtr::new(ptr::null_mut()),
    }));

    loop {
        let head = self.buckets[idx].load(Ordering::Acquire);

        // 检查是否已存在
        let mut curr = head;
        while !curr.is_null() {
            let node = unsafe { &*curr };
            if node.key == unsafe { &*new_node }.key {
                // key 已存在，释放新节点
                unsafe { drop(Box::from_raw(new_node)); }
                return false;
            }
            curr = node.next.load(Ordering::Acquire);
        }

        // 头插
        unsafe { (*new_node).next.store(head, Ordering::Relaxed); }

        match self.buckets[idx].compare_exchange(
            head, new_node,
            Ordering::AcqRel, Ordering::Acquire
        ) {
            Ok(_) => return true,   // 成功
            Err(_) => continue,     // 别人先插了，重试
        }
    }
}

注意 CAS 循环的模式：load -> 准备新值 -> CAS -> 失败就重试。这是所有无锁操作的基本形式。

Lookup

查找不需要 CAS，但需要正确的内存序：

fn get(&self, key: &K) -> Option<&V>
where K: Hash + Eq
{
    let idx = self.bucket_index(key);
    let mut curr = self.buckets[idx].load(Ordering::Acquire);

    while !curr.is_null() {
        let node = unsafe { &*curr };
        if node.key == *key {
            return Some(&node.value);
        }
        curr = node.next.load(Ordering::Acquire);
    }
    None
}

看起来很简单？问题在 unsafe { &*curr }。你在解引用一个裸指针。如果另一个线程在你解引用的瞬间把这个节点 free 了，你就是 use-after-free。

这就是无锁数据结构最核心的难题：内存回收。

三、ABA 问题

在讲内存回收之前，先讲一个更基础的陷阱。

场景：线程 A 读取 head 指针为 P。线程 B 删除了 P 指向的节点，又插入了一个新节点，恰好分配到了同一个地址 P。线程 A 的 CAS 比较 head == P，成功了——但 P 指向的已经是一个完全不同的节点。

这就是 ABA 问题。值从 A 变成 B 又变回 A，CAS 无法检测中间的变化。

解法一：带版本号的指针

把指针和一个版本号打包成一个原子操作的单元：

struct TaggedPtr<T> {
    // 低 48 位: 指针 (x86_64 虚拟地址只用 48 位)
    // 高 16 位: 版本号
    raw: AtomicU64,
    _marker: PhantomData<*mut T>,
}

impl<T> TaggedPtr<T> {
    fn pack(ptr: *mut T, tag: u16) -> u64 {
        (ptr as u64) | ((tag as u64) << 48)
    }

    fn unpack(val: u64) -> (*mut T, u16) {
        let ptr = (val & 0x0000_FFFF_FFFF_FFFF) as *mut T;
        let tag = (val >> 48) as u16;
        (ptr, tag)
    }
}

每次修改指针时同时递增版本号。CAS 同时比较指针和版本号，即使指针值相同，版本号不同也会失败。

16 位版本号意味着要 65536 次 ABA 才会误判。在实践中这足够了。

解法二：不复用地址

另一个思路：如果删除的节点永远不被 free（或延迟足够久才 free），地址不会被复用，ABA 就不会发生。这就引出了内存回收方案。

四、内存回收：Hazard Pointer vs Epoch

无锁数据结构的核心困境：你不能在有人可能还持有引用时释放内存。但你又不能用锁来协调谁持有引用——那就不是无锁了。

Hazard Pointer

Michael (2004) 的方案。每个线程维护一小组”hazard pointer”——指向它当前正在访问的节点。删除操作不立即释放，而是放进一个待回收列表。定期扫描所有线程的 hazard pointer，只回收没有被任何 hazard pointer 保护的节点。

// 简化的 Hazard Pointer 接口
thread_local! {
    static HAZARD: Cell<*const ()> = Cell::new(ptr::null());
}

fn protect<T>(ptr: *const T) {
    HAZARD.with(|h| h.set(ptr as *const ()));
}

fn retire<T>(ptr: *mut T) {
    // 不立即释放，放入待回收列表
    RETIRED_LIST.lock().push(ptr as *mut ());
    // 当列表够长时，扫描所有 hazard pointer，释放安全的节点
    if RETIRED_LIST.lock().len() > THRESHOLD {
        scan_and_reclaim();
    }
}

fn scan_and_reclaim() {
    let hazards: HashSet<*const ()> = collect_all_hazard_pointers();
    RETIRED_LIST.lock().retain(|ptr| {
        if hazards.contains(&(*ptr as *const ())) {
            true  // 有人在用，保留
        } else {
            unsafe { drop(Box::from_raw(*ptr)); }
            false // 安全，释放
        }
    });
}

Hazard Pointer 的优势：每个节点的回收延迟有上界（最多等到下一次 scan）。劣势：每次访问共享数据都要写 hazard pointer（一次原子写），scan 的开销和线程数成正比。

Epoch-based Reclamation

crossbeam-epoch 使用的方案。全局维护一个 epoch 计数器（0, 1, 2 循环）。每个线程在进入临界区时记录当前 epoch。当一个 epoch 的所有线程都已离开，那个 epoch 里退休的节点就可以安全回收了。

// crossbeam-epoch 的使用方式
use crossbeam_epoch::{self as epoch, Atomic, Owned, Shared};

let map: Atomic<Node> = Atomic::null();

// 读操作: pin 当前 epoch
let guard = epoch::pin();
let node = map.load(Ordering::Acquire, &guard);
// guard 存活期间，node 指向的内存不会被回收

// 删除操作: 延迟回收
unsafe {
    guard.defer_destroy(old_node);
    // old_node 不会立即被释放
    // 等所有在当前 epoch 之前 pin 的线程都 unpin 后才释放
}

Epoch 的优势：pin/unpin 开销极低（一次 fence + 原子递增）。劣势：如果一个线程长时间不 unpin（比如在临界区里做了耗时操作），所有退休节点都不能回收，造成内存膨胀。

选哪个？

维度	Hazard Pointer	Epoch-based
回收延迟	有上界	取决于最慢的线程
每次访问开销	一次原子写	几乎为零
内存占用	可控	可能膨胀
实现复杂度	高	中
生产级实现	folly::hazptr	crossbeam-epoch

crossbeam-epoch 是 Rust 生态的事实标准。如果你用 Rust 写无锁数据结构，直接用它。

五、性能实测：无锁 vs Mutex

到了最关键的问题：无锁到底快不快？

测试环境：读多写少（95% 读 5% 写），1M 条目的哈希表，key 均匀分布。

并发线程数	HashMap+Mutex (ops/s)	RwLock (ops/s)	无锁 (ops/s)	无锁倍率
1	18M	15M	12M	0.67x
4	8M	32M	42M	1.3x
8	4M	38M	78M	2.1x
16	2M	25M	140M	5.6x
32	1M	15M	210M	14x
64	0.5M	8M	190M	24x

几个观察：

单线程下无锁更慢。CAS 循环、内存回收、额外的间接寻址，都有开销。Mutex 在无竞争时只是一个原子操作。
4 线程以下 RwLock 就够了。读多写少场景下，RwLock 的读并发基本无锁。
16 线程以上无锁拉开差距。Mutex 的 contention 导致吞吐量塌陷，无锁保持线性扩展。
64 线程时无锁也开始下降。原因不是算法——是 cache line bouncing。所有线程 CAS 同一个 bucket head，缓存一致性协议的开销上来了。

结论：如果你的并发度低于 8，用 DashMap（分段锁）。超过 16 且是读多写少，无锁开始有意义。超过 64，需要考虑分片减少 CAS 竞争。

x86 vs ARM

同样的代码在 ARM 上的表现：

平台	16 线程 (ops/s)	32 线程 (ops/s)
x86_64 (Xeon 8375C)	140M	210M
ARM64 (Graviton 3)	95M	165M

ARM 大约慢 25-30%。原因：LL/SC 的 spurious failure + 内存屏障指令的实际开销。在 x86 上免费的 acquire/release 语义，在 ARM 上需要 DMB 指令。

但 ARM 的核更多、功耗更低。在”相同功耗预算”下，ARM 可以开更多核来补偿单核性能差距。在 AWS Graviton 上，总吞吐量/美元 ARM 反而赢。

结语

无锁哈希表不是一个”更好的哈希表”。它是一个工程权衡：用实现复杂度换取高并发下的扩展性。

写无锁代码的真实成本不是 CAS 循环——那只是最简单的部分。真实成本是：ABA 问题的处理、内存回收方案的选择、内存序在不同架构上的行为差异、以及在 Miri 和 ThreadSanitizer 下反复验证的时间。

如果你的场景需要无锁，用 crossbeam 或 dashmap。如果你想理解无锁，实现一遍然后扔掉。如果你想在生产中用自己的无锁实现——确保你能回答第四节里每一个关于内存回收的问题。

延伸阅读：

大多数”无锁”代码其实不是无锁的 – 为什么 90% 的”无锁”代码不满足定义
Linux 内核的内存屏障：一个让我调了三天的 bug – CAS 的内存序选择和这篇直接相关
unsafe Rust：当编译器不再替你扛枪 – 无锁代码是 unsafe 的主战场

参考资料：

Harris, T. (2001). A Pragmatic Implementation of Non-Blocking Linked-Lists. DISC. – 无锁链表的经典论文
Michael, M. M. (2002). High Performance Dynamic Lock-Free Hash Tables and List-Based Sets. SPAA.
Michael, M. M. (2004). Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. IEEE TPDS.
crossbeam – Rust 的无锁基础设施
DashMap – 分段锁哈希表，大多数场景下的正确选择

目录