第六章 并发数据结构 (Concurrent Data Structures)
一、导读
1.1 本章学习目标
掌握并发数据结构的设计原则和分类方法
深入理解并发队列、并发栈、并发哈希表等常见并发数据结构的实现
学会分析并发数据结构的正确性（线性一致性）和性能（吞吐量、可伸缩性）
理解基于锁的并发数据结构与无锁并发数据结构的权衡
掌握分段锁（Segmented Locking）和细粒度锁（Fine-Grained Locking）的设计方法
了解并发数据结构在实际系统中的应用和优化技术
学会根据应用场景选择合适的并发数据结构
1.2 为什么本章如此重要
并发数据结构是并发编程中最常用的构建块。在多线程程序中，线程之间经常需要共享和交换数据，而并发数据结构提供了一种高效、安全的方式来实现这种数据共享。从 Java 的 ConcurrentHashMap 到 C++ 的并发容器，从数据库的 B+ 树索引到消息队列的缓冲区，并发数据结构无处不在。
设计高效的并发数据结构是一个充满挑战的任务。它需要同时考虑正确性（多线程访问不会产生错误结果）、性能（在高争用下仍能保持高吞吐量）和可伸缩性（随着线程数增加，性能不会急剧下降）。这三个目标往往相互冲突：更强的正确性保证（如线性一致性）通常意味着更高的开销；更粗的锁粒度简化了设计但降低了并发度。
本章系统地介绍了并发数据结构的设计方法。从最简单的基于锁的容器开始，逐步引入更高级的技术：细粒度锁、分段锁、无锁数据结构。每种技术都有其适用的场景和局限性，理解这些技术的设计思路和权衡是设计高效并发系统的关键。
在实际工程中，大多数程序员不需要从头实现并发数据结构——标准库已经提供了高度优化的实现。但理解这些实现的原理对于正确使用它们至关重要：知道什么操作是线程安全的、什么操作不是；知道在什么场景下应该选择什么类型的容器；知道如何避免常见的并发陷阱。
1.3 核心问题引导
并发数据结构有哪些主要的设计方法？它们各自的优缺点是什么？
如何实现一个高吞吐量的并发哈希表？ConcurrentHashMap 的设计思路是什么？
细粒度锁和分段锁有什么区别？如何选择？
无锁的并发数据结构一定比基于锁的更好吗？
如何测试和验证并发数据结构的正确性？
在实际应用中，如何根据访问模式选择最合适的并发数据结构？
二、核心概念详解
2.1 基于锁的并发容器
最简单的并发数据结构设计方法：在顺序数据结构的基础上添加一把全局锁。每次操作前获取锁，操作完成后释放锁。
这种方法的优势是简单、正确性容易保证。所有操作都是互斥的，不会出现数据竞争。劣势是并发度低：任何时刻只有一个线程能操作数据结构，即使操作的是不同的元素。
全局锁的并发容器适用于争用较低的场景（线程很少同时访问容器），或者容器的操作频率很低。在高争用场景下，全局锁会成为严重的性能瓶颈。
2.2 分段锁与 ConcurrentHashMap
分段锁（Segmented Locking / Lock Striping）是提高并发容器吞吐量的关键技术。其核心思想是：将数据结构分成多个段（Segment），每个段有自己的锁。操作只需要获取对应段的锁，不同段的操作可以并发执行。
Java 的 ConcurrentHashMap（JDK 7 版本）是分段锁的经典实现。它将哈希表分成 16 个段（默认），每个段包含一个小的哈希表。put、get、remove 等操作只需要锁定对应的段，不同段的操作完全并发。
ConcurrentHashMap 的设计巧妙地平衡了并发度和内存开销：16 个段提供了 16 倍的并发度提升，而额外的锁空间开销很小。在高争用场景下，ConcurrentHashMap 的吞吐量比全局锁的 HashMap 高数十倍。
JDK 8 的 ConcurrentHashMap 进一步优化：放弃了分段锁，改为每个桶（bucket）一把锁（使用 synchronized 或 CAS）。这提供了更细的粒度和更高的并发度。
2.3 细粒度锁的链表和树
细粒度锁（Fine-Grained Locking）将锁的粒度降低到数据结构的单个元素（如链表的每个节点、树的每个节点）。不同元素的操作可以完全并发。
并发有序链表使用"手递手"（Hand-over-Hand / Lock Coupling）加锁策略：遍历链表时，先获取当前节点的锁，然后获取下一个节点的锁，再释放当前节点的锁。这种方法保证了遍历的一致性，但每次操作需要获取和释放多把锁，开销较大。
优化方案：使用"乐观遍历"——先不加锁遍历找到目标位置，然后加锁验证。如果验证失败（节点已被修改），重试。这种方法在争用较低时性能很好。
并发搜索树（如并发红黑树、并发 AVL 树）的实现更加复杂，因为树的旋转操作涉及多个节点的修改，需要同时锁定这些节点以避免死锁。通常使用自顶向下的加锁策略：从根开始，沿路径加锁，确保不会形成循环等待。
2.4 并发队列
并发队列是并发数据结构中研究最深入的主题之一。根据同步方式，可以分为：
阻塞队列（Blocking Queue）：当队列为空时，出队操作阻塞等待；当队列满时，入队操作阻塞等待。适用于生产者-消费者模式。Java 的 ArrayBlockingQueue 使用一把锁和两个条件变量（notEmpty、notFull）实现。
非阻塞队列（Non-Blocking Queue）：当队列为空时，出队操作立即返回 null 或抛出异常。适用于不需要等待的场景。
无锁队列（Lock-Free Queue）：使用 CAS 实现，不需要锁。Michael-Scott 队列是最经典的无锁 FIFO 队列实现。
并发双端队列（Concurrent Deque）：支持从两端入队和出队。Java 的 ConcurrentLinkedDeque 使用细粒度锁实现。无锁双端队列的实现更加复杂，因为需要同时维护两端的指针。
2.5 并发数据结构的设计模式
在实际设计中，有几种常见的设计模式用于构建并发数据结构。
复制模式（Copy-On-Write）：每次修改操作都创建数据结构的副本，在副本上修改，然后原子地替换引用。读操作不需要锁，因为读的是不可变的快照。适用于读多写少的场景。Java 的 CopyOnWriteArrayList 和 CopyOnWriteArraySet 使用这种模式。
惰性删除（Lazy Deletion / Mark-and-Sweep）：删除操作不立即移除节点，而是将其标记为"已删除"。后续的操作在遇到已删除节点时才真正清理。这种方法简化了并发控制，但可能导致数据结构中积累大量"垃圾"节点。
分块模式（Chunked Structure）：将数据结构分成多个固定大小的块，每个块独立管理。新元素分配到当前块的下一个空位，块满时分配新块。这种模式减少了锁争用，因为不同块的操作完全独立。
三、深入分析与讨论
3.1 并发数据结构的性能评估
评估并发数据结构的性能需要考虑多个维度。吞吐量（Throughput）：单位时间内完成的操作数。这是最常用的指标，但可能掩盖了个别操作的高延迟。
延迟分布（Latency Distribution）：不仅要看平均延迟，还要看 P50、P99、P999 延迟。在高争用下，某些操作可能因为重试而延迟很高，即使平均延迟看起来正常。
可伸缩性（Scalability）：随着线程数增加，吞吐量如何变化。理想情况下，吞吐量应该随线程数线性增长。实际中，由于锁争用和缓存一致性开销，吞吐量增长通常低于线性。
公平性（Fairness）：是否所有线程都有均等的机会完成操作。某些数据结构可能"偏向"某些线程（如总是先服务入队操作的线程），导致其他线程饥饿。
3.2 缓存效应与并发数据结构
并发数据结构的性能不仅取决于算法复杂度，还受到缓存效应的显著影响。伪共享（False Sharing）是最常见的问题：两个线程频繁修改同一缓存行中的不同变量，导致缓存行在处理器之间反复传递。
避免伪共享的技术包括：在变量之间插入填充（Padding），使它们位于不同的缓存行；使用线程本地存储（Thread-Local Storage）来减少共享。
缓存行的预取（Prefetching）也可以被利用：如果数据结构按顺序遍历（如数组、链表），硬件预取器可以提前加载数据到缓存，减少缓存未命中。
NUMA 效应：在 NUMA 架构下，访问远程内存（其他处理器的本地内存）比访问本地内存慢。将数据结构分配到访问它的处理器的本地内存中，可以显著提升性能。
3.3 并发数据结构的选择指南
在实际应用中，选择并发数据结构需要考虑以下因素：
访问模式：读多写少 → CopyOnWrite 容器或读写锁；写多读少 → 全局锁或分段锁；读写均衡 → ConcurrentHashMap 或无锁结构。
争用程度：低争用 → 全局锁足够；中等争用 → 分段锁或细粒度锁；高争用 → 无锁结构或专门设计的高并发容器。
操作类型：只需要等值查找 → 哈希表；需要有序操作 → 搜索树；FIFO 顺序 → 队列；LIFO 顺序 → 栈。
规模：小规模 → 简单实现即可；大规模 → 需要考虑内存效率和可伸缩性。
四、实践案例
4.1 Java ConcurrentHashMap 的演进
JDK 7 的 ConcurrentHashMap：使用 16 个 Segment，每个 Segment 继承 ReentrantLock，内部是一个 HashEntry 数组。size() 操作需要获取所有 Segment 的锁，开销较大。
JDK 8 的 ConcurrentHashMap：放弃 Segment，使用 Node 数组 + 链表/红黑树。每个桶使用 synchronized 锁定头节点。size() 使用 baseCount + CounterCell 数组来分散计数争用（类似 LongAdder 的思想）。扩容时使用多线程协助迁移（helpTransfer）。
4.2 生产者-消费者模式中的并发队列
在生产者-消费者模式中，并发队列作为线程间的通信通道。生产者线程将任务放入队列，消费者线程从队列中取出任务执行。
使用 ArrayBlockingQueue（基于数组的有界阻塞队列）：内部使用一把锁和两个条件变量。put 操作在队列满时等待，take 操作在队列空时等待。适用于需要限流的场景。
使用 LinkedBlockingQueue（基于链表的可选有界阻塞队列）：使用两把锁（putLock 和 takeLock），入队和出队可以并发执行。吞吐量高于 ArrayBlockingQueue。
使用 ConcurrentLinkedQueue（无锁非阻塞队列）：基于 Michael-Scott 算法。不入队不阻塞，出队为空时返回 null。适用于不需要等待的场景。
五、常见误区与注意事项
5.1 认为"线程安全"等于"正确"
一个线程安全的并发数据结构保证了单个操作的原子性，但不保证多个操作的组合是原子的。例如，if (!map.containsKey(key)) map.put(key, value) 在 ConcurrentHashMap 上不是原子的——在 containsKey 和 put 之间，另一个线程可能已经插入了相同的 key。需要使用 putIfAbsent 等原子复合操作。
5.2 忽视并发数据结构的内存开销
分段锁、细粒度锁和无锁结构都需要额外的内存来存储锁、标记位或版本信息。在大规模部署时，这些额外开销可能不可忽视。
5.3 在不需要并发性的地方使用并发容器
如果数据结构只在单线程中使用，使用并发容器只会增加不必要的开销。应该根据实际的使用场景选择合适的数据结构。
5.4 忽视迭代器的弱一致性
大多数并发数据结构的迭代器是弱一致性的（Weakly Consistent）：不保证反映迭代开始后的所有修改，也不会抛出 ConcurrentModificationException。在使用迭代器时需要理解这种语义。
六、本章小结
本章系统介绍了并发数据结构的设计方法和技术。基于锁的容器简单但并发度低；分段锁通过分散锁来提高并发度；细粒度锁将锁粒度降低到单个元素；无锁结构通过 CAS 完全避免锁。并发队列、哈希表、链表和树各有不同的设计策略。性能评估需要考虑吞吐量、延迟、可伸缩性和公平性。缓存效应（伪共享、NUMA）对性能有显著影响。选择并发数据结构需要根据访问模式、争用程度和操作类型来权衡。
七、思考题与练习
实现一个基于全局锁的并发哈希表，然后改进为分段锁版本。比较两者的吞吐量。
分析 Java ConcurrentHashMap（JDK 8）的设计：为什么放弃了分段锁？CounterCell 数组的作用是什么？
实现一个并发有序链表，使用手递手加锁策略。分析其性能瓶颈。
实现 CopyOnWriteArrayList，分析其在读多写少场景下的性能优势。
设计一个并发优先队列（Concurrent Priority Queue），分析其正确性和性能。
比较 ArrayBlockingQueue、LinkedBlockingQueue 和 ConcurrentLinkedQueue 在不同场景下的适用性。
实现一个并发的跳表（Skip List），分析其设计挑战和性能特征。
讨论：在设计一个新的并发数据结构时，应该选择基于锁还是无锁方案？给出你的决策框架。