无锁数据结构入门：Java 实例详解

最后修改:2024年1月8日

by Michael Krimgen

1. 引言

本文带你深入理解无锁（lock-free）数据结构的核心原理及其在高并发场景下的优势。相比传统的基于锁的并发容器，无锁结构能有效避免线程阻塞、死锁和优先级反转等问题，是构建高性能并发系统的关键技术之一。

我们将依次讲解以下内容：

  • ✅ 无锁相关的术语：obstruction-free、lock-free、wait-free
  • ✅ 实现无锁算法的核心原子操作，如 CAS
  • ✅ 手写一个简单的 Java 无锁队列
  • ✅ 如何向 wait-free 迈进

目标是让你不仅能看懂 JDK 中 ConcurrentLinkedQueue 的设计思想，还能在必要时自己实现或优化类似结构。

2. 锁 vs 饥饿

我们先厘清两个关键概念：阻塞（blocked） 和 饥饿（starvation）。

阻塞线程（Blocked Thread）

看下图：

threads lock

Thread 2 拿到了数据结构的锁。当 Thread 1 也想获取锁时，它必须等待 Thread 2 释放。⚠️ 如果 Thread 2 被挂起（suspend），Thread 1 将永远等下去 —— 这就是阻塞。

饥饿线程（Starving Thread）

再看无锁情况：

threads lockfree

Thread 2 访问数据结构但不加锁。Thread 1 同时尝试访问，检测到冲突后立即返回失败（红色），然后重试，直到成功（绿色）。

✅ 优势：无需锁，避免了死锁和无限等待。
❌ 缺点：如果其他线程频繁操作，Thread 1 可能需要重试很多次才能成功 —— 这就是饥饿。

无锁算法的核心思想是：用“重试”代替“等待”，通过原子操作（如 CAS）实现线程间的协调。

3. 无锁数据结构的三种级别

根据线程进展保证的强弱，可分为三类：

3.1. Obstruction-Free（无障碍）

  • ✅ 定义：只要其他所有线程都暂停，当前线程一定能向前推进。
  • ⚠️ 最弱保证。现实中很少直接使用，多作为构建更高级别算法的基础。
  • 对比锁：如果持有锁的线程挂起，等待者会永久阻塞；而 obstruction-free 不会。

3.2. Lock-Free（无锁）

  • ✅ 定义：在任意时刻，至少有一个线程能够成功完成操作并推进。
  • ❌ 允许个别线程长时间饥饿，但系统整体必须持续向前（global progress）。
  • 这是大多数高性能无锁容器（如 ConcurrentLinkedQueue）的目标级别。

3.3. Wait-Free（免等待）

  • ✅ 定义：在 lock-free 基础上，每个线程都能在有限步数内完成操作，彻底避免饥饿。
  • ✅ 最强保证，但实现复杂，开销大，实际应用较少。

3.4. 小结对比

threads summary

  • 左：obstruction-free —— 其他线程暂停后，目标线程可推进。
  • 中：lock-free —— 即使所有线程都在跑，至少一个能成功。
  • 右：wait-free —— 每个线程最终都能成功，不会无限重试。

4. 无锁算法的基石：原子操作

实现无锁结构依赖底层硬件支持的原子指令。Java 通过 sun.misc.Unsafe 和 java.util.concurrent.atomic 包封装了这些能力。

4.1. Compare-and-Swap (CAS)

CAS 是无锁编程的核心原子操作，语义如下：

如果当前值等于预期值，则更新为新值，返回 true；否则不更新，返回 false。

其原子性保证了“读-比-写”三步操作不可分割。

threads cas

图解：

  • 两线程同时读取值为 3。
  • Thread 2 CAS 成功，值变为 8。
  • Thread 1 的 CAS 失败（预期是 3，实际是 8），需重试。

CAS 代码模拟

volatile int value;

boolean cas(int expectedValue, int newValue) {
    if(value == expectedValue) {
        value = newValue;
        return true;
    }
    return false;
}

CAS 典型使用模式

void testCas() {
    int v = value;
    int x = v + 1;

    while(!cas(v, x)) {
        v = value;
        x = v + 1;
    }
}

✅ 成功则退出循环；失败则重读最新值，重新计算，再试。
⚠️ 风险：在高竞争下可能陷入长时间重试（饥饿），但系统整体仍在推进（lock-free）。

注意事项

  • ✅ Java 推荐使用 AtomicInteger 等类，而非直接操作 Unsafe。
  • ⚠️ CAS 无法解决 A-B-A 问题，见下节。

4.2. Load-Link / Store-Conditional (LL/SC) 与 A-B-A 问题

A-B-A 问题

threads aba

场景：

  1. Thread 1 读取值 A (3)。
  2. Thread 2 将 A 改为 B (8)，又改回 A (3)。
  3. Thread 1 执行 CAS，预期是 A，当前也是 A，于是成功。

问题：Thread 1 无法察觉中间状态的变化。这在指针操作中可能引发严重错误（如访问已释放内存）。

解决方案：LL/SC 或 带版本号的 CAS

Java 提供了 AtomicStampedReference<V>，它不仅存储对象引用，还附带一个整型“戳记”（stamp），每次修改都递增 stamp，从而区分真正的“相同值”。

AtomicStampedReference<String> ref = new AtomicStampedReference<>("A", 0);
// 即使值变回"A"，stamp已不同，CAS会失败

4.3. Fetch-and-Add

原子性地对变量进行增减操作。

  • ✅ AtomicInteger.getAndIncrement()：先返回旧值，再加 1。
  • ✅ AtomicInteger.incrementAndGet()：先加 1，再返回新值。

这类操作在计数器、ID 生成器中非常高效。

5. 多线程操作链表队列的典型问题

我们以一个双端链表队列为例，理解无锁的必要性。

队列结构如下：

linkedQueue

tail 指向尾节点，新元素插入在 tail 之后。

两个线程（T1、T2）同时添加元素 N 和 M，需执行三步：

  1. 创建新节点。
  2. 设置前驱（N.prev = L）和后继（L.next = N）。
  3. 更新 tail 指向新节点。

问题场景

linkedQueue threads

  • ❌ 若执行序为 ABCD 或 ACBD：T2 的更新覆盖了 T1，导致 N 节点丢失。
  • ❌ 若执行序为 ACDB：tail 指向 N，但 L.next 指向 M，队列结构不一致。

传统解法是加锁。而无锁解法，是用 CAS 原子地更新 tail 指针，确保插入的原子性。

6. Java 实现一个无锁队列

下面手写一个简化的无锁队列，帮助你理解核心思想。

核心成员变量

public class NonBlockingQueue<T> {

    private final AtomicReference<Node<T>> head, tail;
    private final AtomicInteger size;

    public NonBlockingQueue() {
        head = new AtomicReference<>(null);
        tail = new AtomicReference<>(null);
        size = new AtomicInteger();
        size.set(0);
    }
}
  • ✅ head 和 tail 使用 AtomicReference，保证指针更新是原子的。
  • ✅ size 使用 AtomicInteger，保证计数准确。

节点定义

private class Node<T> {
    private volatile T value;
    private volatile Node<T> next;
    private volatile Node<T> previous;

    public Node(T value) {
        this.value = value;
        this.next = null;
    }

    // getters and setters 
}
  • ✅ 所有引用标记为 volatile，确保内存可见性。

6.1. 无锁 add 操作

public void add(T element) {
    if (element == null) {
        throw new NullPointerException();
    }

    Node<T> node = new Node<>(element);
    Node<T> currentTail;
    do {
        currentTail = tail.get();
        node.setPrevious(currentTail);
    } while(!tail.compareAndSet(currentTail, node)); // CAS 更新 tail

    if(node.previous != null) {
        node.previous.next = node; // 链接前驱的 next
    }

    head.compareAndSet(null, node); // 首元素特殊处理
    size.incrementAndGet();
}

✅ 核心逻辑：

  • 循环尝试用 CAS 将 tail 从 currentTail 更新为 node。
  • 只有当 tail 没被其他线程修改时，CAS 才成功，确保了插入的原子性。
  • 成功后，再修补 previous.next 指针（非原子，但安全，因为只有本线程能修改 node.previous）。

⚠️ 踩坑点：先更新 tail 再设置 previous.next，避免其他线程看到一个 tail 指向但未完全链接的节点。

6.2. 无锁 get 操作

public T get() {
    if(head.get() == null) {
        throw new NoSuchElementException();
    }

    Node<T> currentHead;
    Node<T> nextNode;
    do {
        currentHead = head.get();
        nextNode = currentHead.getNext();
    } while(!head.compareAndSet(currentHead, nextNode)); // CAS 更新 head

    size.decrementAndGet();
    return currentHead.getValue();
}

✅ 核心逻辑：

  • 循环尝试用 CAS 将 head 从 currentHead 更新为 nextNode。
  • 成功则移除头节点并返回其值。

现实中的实现

  • ✅ JDK 的 ConcurrentLinkedQueue 就是基于 Michael & Scott 算法的 lock-free 队列。
  • ⚠️ 有趣的是，早期文档称其为 wait-free，实则为 lock-free。Java 8 起已修正为 lock-free。

7. 如何实现 Wait-Free 队列

前述实现是 lock-free 的，add 和 get 中的 while 循环在高并发下可能重试很多次。

Wait-Free 的挑战

  • ✅ 要求每个线程在有限步内必成功。
  • ❌ 不能依赖“重试”，必须有确定性进展。

基本思路：Helper Threads（辅助线程）

一种经典思路是为每个线程分配一个“助手”：

  1. 当线程 A 想入队，但一直失败。
  2. 助手线程 B 成功入队后，必须先帮 A 完成入队，才能处理自己的请求。
  3. B 也有自己的助手 C，C 也会帮 B，依此类推。

wait free

✅ 保证：在最坏情况下，A 的操作会在所有线程各成功一次后完成。

⚠️ 实现复杂：需动态管理线程关系，处理线程退出等边界情况。实际应用中，lock-free 通常已足够。

8. 总结

  • ✅ 无锁结构通过 CAS 等原子操作，用“重试”替代“阻塞”，提升并发性能。
  • ✅ 三级别：obstruction-free < lock-free < wait-free，实践中 lock-free 最常用。
  • ✅ ConcurrentLinkedQueue 是典型的 lock-free 队列，理解其原理对掌握并发编程至关重要。
  • ✅ A-B-A 问题需警惕，可用 AtomicStampedReference 解决。
  • ⚠️ wait-free 虽理想，但实现复杂，多数场景 lock-free 即可。

本文完整代码示例已托管至 GitHub：https://github.com/yourname/concurrent-examples

原始标题:Introduction to Lock-Free Data Structures with Java Examples

« 上一篇： 使用 Thymeleaf 生成 PDF 文件
» 下一篇： Java 14 Record 关键字