链表的进阶：无锁链表（Lock-Free Linked List）简介

多线程编程里，链表是个让人又爱又恨的数据结构。爱它，是因为插入删除灵活；恨它，是因为一旦多个线程同时操作，各种诡异问题就冒出来了。传统的做法是加锁——mutex、spinlock 轮着上。但锁这东西，用多了性能下降，用少了数据错乱。

那有没有不用锁也能保证线程安全的办法？有，这就是无锁链表。说白了，就是利用 CPU 提供的原子操作，让多个线程同时读写链表时，不会出现数据竞争。

为什么需要无锁链表？

我在一个高并发消息队列项目里遇到过这个问题。当时用互斥锁保护链表，压测到 8 个线程时，性能曲线就开始往下掉。锁竞争太激烈了，大部分时间线程都在等锁，而不是真正干活。

无锁方案的好处很明显：

• 没有锁的开销——不需要获取/释放锁，省掉了系统调用和上下文切换
• 天然避免死锁——没有锁，自然不会有死锁问题
• 更好的扩展性——线程数增加时，性能不会因为锁竞争而急剧下降

当然，代价是编程复杂度上升。你想想看，要保证多个线程同时读写一个链表还不乱，这逻辑得有多绕。

无锁编程的核心：CAS 操作

无锁编程的基石是 CAS（Compare-And-Swap）。这是一个 CPU 级别的原子指令，它的语义很简单：

// 伪代码：如果 *ptr == old_val，就把 *ptr 改成 new_val，返回 true
bool CAS(void** ptr, void* old_val, void* new_val) {
    if (*ptr == old_val) {
        *ptr = new_val;
        return true;
    }
    return false;
}

在 C11 标准里，我们可以用 stdatomic.h 里的 atomic_compare_exchange_strong。我个人习惯用这个，因为它语义清晰，不容易踩坑。

无锁链表的插入操作

先看最简单的场景：在链表头部插入一个节点。传统做法是：

new_node->next = head;
head = new_node;

但在多线程下，这两行代码之间可能被其他线程打断。无锁版本是这样写的：

void lock_free_push(Node* new_node, Node** head) {
    do {
        new_node->next = *head;  // 1. 先让新节点指向当前头
    } while (!CAS(head, new_node->next, new_node));  // 2. 原子地更新头指针
}

这里有个细节：如果 CAS 失败，说明 *head 已经被别的线程改了。这时候 new_node->next 还是指向旧值，但 *head 已经变了。所以循环里重新读取 *head 赋值给 new_node->next，再试一次。

无锁链表的删除操作

删除比插入麻烦得多。为什么？因为当你删除一个节点时，别的线程可能正在访问它。这就是经典的 ABA 问题。

举个例子：线程 A 要删除节点 X，它先读到了 X 的 next 指针。但还没来得及操作，线程 B 把 X 删了，又新建了一个节点 Y，恰好 Y 的地址和 X 一样。线程 A 继续操作时，以为 X 还在，实际上它操作的是 Y——数据就乱了。

解决 ABA 问题的常用方法是使用带标记的指针（Tagged Pointer）：

// 用 64 位整数的低 48 位存地址，高 16 位存版本号
typedef struct {
    uintptr_t ptr : 48;
    uint16_t tag : 16;
} tagged_ptr_t;

每次修改指针时，版本号加 1。这样即使地址复用，版本号对不上，CAS 也会失败。

无锁链表的遍历

遍历相对简单，因为只读不写。但有个坑：你读到某个节点的 next 指针时，这个节点可能已经被别的线程删了。

解决办法是使用危险指针（Hazard Pointer）机制。每个线程维护一个列表，记录它当前正在访问的节点。删除节点前，先检查有没有线程正在访问它，如果有，就延迟删除。

// 伪代码：遍历时标记当前节点
hazard_ptr_set(current);  // 告诉其他线程：我在用这个节点
if (current->value == target) {
    // 找到了，处理逻辑
}
hazard_ptr_clear();  // 用完了，释放标记

我曾经在一个项目中因为没处理好危险指针，导致内存泄漏。排查了两天才发现，是删除线程没等所有读者线程释放引用就回收了节点。嗯，这里要注意：无锁编程里，内存回收比数据同步更难。

无锁链表的性能特征

操作	加锁版本	无锁版本	说明
插入（头部）	O(1)，但锁竞争时退化	O(1)，CAS 重试次数少	无锁版本在低竞争下更快
删除（已知节点）	O(1)，需持有锁	O(1)，需处理 ABA	无锁版本实现更复杂
遍历	O(n)，读锁可共享	O(n)，需危险指针保护	读多写少场景下无锁优势明显
内存开销	低，只需锁变量	较高，需要标记位/危险指针	无锁版本空间换时间

什么时候该用无锁链表？

说实话，不是所有场景都适合无锁。我个人的经验是：

• 读多写少——比如配置表、路由表，大部分时间在查，偶尔更新
• 写操作简单——只在头部或尾部插入，不涉及复杂的中间节点操作
• 线程数多——超过 4 个线程竞争时，无锁的优势开始显现
• 实时性要求高——不能容忍锁导致的优先级反转或不确定延迟

反过来，如果链表操作复杂（比如双向链表、需要同时修改多个指针），或者线程数很少，那老老实实用锁反而更省心。

无锁链表的核心逻辑图

下面这张图展示了无锁链表插入操作的核心流程：

避坑指南

最后，分享几个我踩过的坑：

• 不要用 volatile 替代原子操作——volatile 只保证编译器不优化，不保证 CPU 指令的原子性
• 注意内存序——C11 的 atomic 操作默认是 memory_order_seq_cst，性能有损耗。读多写少的场景可以降级为 memory_order_acquire/release
• 测试要跑在多核机器上——单核下无锁代码看起来没问题，一上多核就暴露问题
• 先保证正确性，再优化性能——无锁代码调试困难，先写对再改快

我曾经在一个项目里，把无锁链表的内存回收写错了，导致线上服务运行 72 小时后内存暴涨。排查时发现是危险指针的释放顺序反了——先清除了标记，才释放节点，中间刚好被另一个线程插进来访问。这种时序问题，靠 log 几乎查不出来，最后是用 ThreadSanitizer 跑出来的。

无锁链表是个好东西，但用之前得想清楚：你真的需要它吗？如果加锁就能满足性能要求，别折腾。如果确实需要，那就做好心理准备——调试无锁代码的时间，通常是写代码时间的 5 倍以上。

---