无锁并发容器的设计与实现原理

无锁并发容器的设计与实现原理

——以 mpmc_map 为例的工程化剖析

摘要

本文以 mpmc_map 库（头文件式 C++11 并发容器：unordered_map、unordered_set、map、set）为对象，系统阐述无锁并发容器从内存模型到工程实现的完整原理。内容包括：并发容器面临的核心问题（锁的代价与内存回收）；C++11 原子操作与内存序的基础；分离序链表与并发红黑树两种引擎的算法结构、操作协议与线性化论证；世代回收与危险指针两种回收方案的安全论证与成本模型；节点池、扩容、预取等工程细节及其测量依据；性能数据的诚实解读；以及验证方法论。全文基于代码实现与可复现的测量结果，不对性能作超出证据的断言，也不回避设计上的权衡。

1 引言：并发容器要解决什么问题

1.1 多线程共享可变状态的基本约束

多个线程共享一个可变容器时，正确性的基本要求是：任何线程观察到的状态都必须是"某个合法中间状态"，且不存在数据竞争。C++11 标准对数据竞争的定义是：两个线程对同一内存位置的访问至少有一个是写操作，且它们之间没有先行发生（happens-before）关系——这属于未定义行为。

实现线程安全容器有两条技术路线：

锁的代价不是"几次原子指令"那么简单。在真实硬件上，一个被多个核心竞争的自旋锁会引发缓存行在所有核心之间反复传递（缓存一致性协议流量），其单次获取成本随竞争线程数超线性增长；互斥锁还引入阻塞、唤醒、优先级反转与死锁可能。这些是并发容器必须面对的物理现实，而不是理论装饰。

1.2 无锁方案额外付出的代价

无锁不是免费的。它把锁的代价转嫁到三处：

• 每次操作的原子性：读路径也要使用原子读与内存序，防止读到撕裂的中间状态；
• 并发修改的协调：写路径使用比较交换（CAS）循环，失败重试；
• 内存回收：这是最隐蔽也最昂贵的一部分。节点被逻辑删除后不能立即释放——另一个线程可能正持有指向它的指针并即将解引用。如何证明"不再有人使用它"再释放，就是内存回收（reclamation）问题。没有回收方案的无锁容器要么泄漏，要么悬垂。

本文第 2 节先建立内存模型与原子操作的基础，第 3 节专门讲回收问题，第 4、5 节分别剖析两种容器引擎，第 6 节讲工程细节，第 7 节分析内存占用，第 8 节解读测量数据，第 9 节讲验证方法，第 10 节总结。

2 基础：内存模型、原子操作与内存序

2.1 硬件现实：缓存与一致性

现代多核处理器中，每个核心有私有缓存（一级、二级），所有核心共享末级缓存与内存。核心对内存的读写首先作用于缓存。当两个核心读写同一地址时，缓存一致性协议（x86 为 MESI 一族）保证它们看到一致的值——但"一致"以缓存行（通常 64 字节）为粒度，且需要时间。

两个后果对并发编程至关重要：

• 伪共享：两个无关变量落在同一缓存行，一个核心修改其一，会使另一核心持有的该行失效，即使另一个变量根本没被碰。多线程结构必须按缓存行对齐热字段。
• 内存序：处理器与编译器都可能重排指令，只要单线程可观察行为不变。跨线程的顺序保证必须显式声明。

2.2 C++11 原子操作与内存序

C++11 提供 std::atomic<T> 与四种主要内存序：

• 松弛序（memory_order_relaxed）：只保证原子性，不提供任何跨线程顺序；
• 获取序（memory_order_acquire）：其后的读与写不能被重排到该操作之前（用于"读锁"侧）；
• 释放序（memory_order_release）：其前的读与写不能被重排到该操作之后（用于"写锁"侧）；
• 顺序一致序（memory_order_seq_cst）：默认，全序。

获取/释放配对是同步的基石：线程甲对原子变量 X 做释放写，线程乙对 X 做获取读并读到该值，则甲在释放之前的所有写（包括非原子写）对乙在获取之后的所有读可见。这就是先行发生关系的传递链。

本库的每个原子操作都遵循"能松弛就松弛，该获取/释放就不省"的原则，例如：

• 链表遍历中读取后继指针用获取序：需要看到前驱的发布；
• 节点池分片锁的加解锁用获取/释放配对；
• 预取地址的松弛读只用于拿地址，不依赖其值。

2.3 对比交换与 ABA 问题

无锁数据结构的基本操作是比较交换（CAS）：若内存位置的值等于期望值则写入新值，返回成功；否则失败。无锁数据结构的基本敌人是 ABA 问题：线程甲读到指针 P，被抢占；线程乙删除 P 指向的节点、释放、再分配出地址相同的节点（内容已变）；甲恢复后执行 CAS(P, Q) 成功，但 P 的内容已不是甲所见的版本——甲基于陈旧观察做了错误的比较交换。

本库的 ABA 防护有两层：

• 回收层：被删除节点不会立即归还分配器，而是进入回收器，等待"证明无人引用"——因此"释放后立即重用同一地址"的概率被大幅压低（世代方案中，节点要等两个世代；危险指针方案中，要等所有槽不再引用）；
• 校验层：遍历路径采用"发布-重读-校验"协议：先把读到的指针发布到保护槽，再重读源地址，若两次读到的值不同则重来。

3 内存回收：无锁结构的隐藏地基

3.1 问题形式化

设线程 T 执行删除操作：它标记并摘除了节点 N。此刻另一个线程 S 可能已经读过 N 的地址（在它的局部变量或寄存器里），正打算解引用。如果 T 立即释放 N，S 解引用悬垂指针——未定义行为。因此必须存在一个机制回答：何时可以安全释放 N？

答案的通用形式是：当且仅当没有任何并发运行的操作还能到达 N。两种经典方案分别用不同证据回答这个问题。

3.2 危险指针

危险指针（hazard pointers，Michael 提出）的思路是"主动声明"：任何线程在解引用一个从共享结构读到的指针之前，必须先把该指针写入自己的一个专用槽位（hazard slot），并重新读取源地址确认没有变化（防 ABA），然后才能解引用；解引用结束后清除槽位。

回收方在释放对象前，扫描所有活跃线程的槽位：如果某个槽位仍然持有该对象，说明某个线程可能还在用它，不能释放；只有当没有任何槽位引用它时，才可释放。

这个方案的成本模型是：每次解引用付出"发布 + 重读 + 清除"的序列（两次原子读加一次槽写）；每批回收付出与"线程数 × 槽数"成正比的扫描。优点是没有全局热点；缺点是每次解引用都贵。

3.3 世代回收

世代回收（epoch-based reclamation）的思路是"集体记账"。一个全局计数器按世代递增；每次操作开始时，线程登记自己处于当前世代，结束时注销。回收规则是：对象在其退休世代被释放，当且仅当全局世代已越过该世代两代。

为什么是两代而不是一代？考虑世代 g 的最后一个线程正在离开（活跃计数从 1 变 0），同时新线程已经进入 g+1。如果只等一代，g 代的退休对象可能在"g 代仍有一个线程尚未完全离开"时被释放。两代规则保证：对象在世代 e 退休，只有全局世代达到 e+2 时才释放——此时任何曾在 e 代执行操作的线程都已完成那些操作。

本库的世代实现细节：

• 每操作守卫（RAII）进入/离开世代；
• 每线程三个标签向量（按世代取模 3），退休对象按世代入队；
• 每线程的退休总数计数器超过阈值（256）触发回收；
• 回收时只释放两个世代前的那一标签——这是唯一被证明安全的标签。

成本模型：每操作一次全局原子读 + 一次活跃计数增量 + 退出时一次递减；无每次解引用成本。代价是全局计数器在多线程同时进出时成为热点。

3.4 两种方案的测量对比

在参考机器上（见第 8 节的方法学说明），世代方案在读多负载下每个线程数都更快（约 1.4-1.6 倍），混合负载从 4 线程起更快；危险指针仅在 1-2 线程的混合换手下领先（约 7-16%，单次最高 38%）。原因是结构性的：危险指针按解引用付费，世代方案按操作付费；读多负载的解引用次数远多于操作次数。

默认方案因此选为世代。但危险指针仍被保留并支持显式选择——它的读路径没有全局热点，对"长期发布指针、读者极多"的应用仍是合理选项。这是基于测量与场景的选择，不是"某个方案永远更好"的判断。

3.5 线程退出与迟到回收链

一个线程可能带着尚未可回收的退休对象退出（世代方案中：它退休的对象还没满两个世代；危险指针方案中：对象仍被其他线程的槽引用）。线程局部状态销毁后，这些对象必须有人接管。两个方案都使用共享的"迟到回收链"：

• 退出的线程把未回收对象逐元素推入链头（用比较交换）；
• 任何后续的回收操作、以及每个容器析构函数，都会排空这条链。

链的推入必须是逐元素的：整链推入存在一个经典竞争——两个推入者可能各自比较交换成功但交叉了尾部链接，形成环。逐元素推入在构造上无环。

3.6 排空门控：一个被测量揭示的工程陷阱

这里有一个值得写进博客的教训。早期版本中，每次回收都无条件调用链排空，而排空的第一步是对链头做一次全局交换——一个共享缓存行上的锁定读改写。在 8 线程、40% 插入/40% 删除的负载下，出现了吞吐崩塌（约 2.5 万次操作每秒，正常应为数百万）。

测量（在代码路径上插入周期计数器）揭示的因果链是：

修复是两道廉价的门控：链非空（用无争用的松弛加载检查）且全局世代自本线程上次排空以来已前进，才执行排空。延迟排空是安全的：孤儿留在链上直到其标签可回收，析构路径释放全部。

这个案例的普遍教训是：一个"看起来每次调用都是常数开销"的全局原子操作，在触发频率被放大后可以成为吞吐的瓶颈；触发频率的放大（阈值被永久超限）与操作的全局性（共享缓存行的锁定读改写）缺一不可。定位它靠的是在每条候选路径上做周期计数，而不是猜。

4 无序容器：分离序链表的原理

4.1 为什么不用"数组加链表"的经典哈希表

经典哈希表（如 std::unordered_map）由桶数组加冲突链表组成。它在单线程下简单高效，但并发化有两个障碍：其一，查找需要两级间接（先读桶单元，再沿链表走），桶数组扩容时所有桶单元同时变化，无法用一次原子操作发布；其二，扩容需要移动元素（重哈希），移动过程对读者不可原子地隐藏。

分离序链表（split-ordered list，Shalev 与 Shavit，2003）的核心思想是：把哈希表的"桶"编码进一个有全局次序的单一链表，扩容不再移动任何元素。这就是"分离序"的含义——桶的次序与元素的哈希次序分离处理，通过位反转建立对应。

4.2 结构

整个表是一张按分裂序键排序的单向链表，外加一张小的桶指针间接表：

• 元素节点携带分裂序键 so_key = 位反转(混合哈希(键) | 最高位置 1)。最高位置 1 使键的分裂序键恒为奇数，从而排在分裂序键为偶数的桶节点之后；位反转把哈希的高位翻到低位，使"桶边界"在扩容时保持稳定（见 4.5）；
• 桶节点（哨兵）携带桶编号，其后继指针上有一个标签位（第 1 位）标记"这是桶节点"。桶 b 的桶节点标志桶 b 范围内元素的起始位置；
• 后继指针是带标签的原子指针：第 0 位 = 已标记（逻辑删除），第 1 位 = 桶标志。哈希冲突的元素（哈希映射到同一桶）在相邻桶节点之间形成等键运行；哈希混合函数保证这些运行在实践中小而短。

值得强调的推论：从桶 b 的桶节点出发的遍历，只会经过桶 b 的运行，遇到下一个桶节点即停——因为每个桶节点恰好是其桶区间（以位反转桶号为起点、宽度为 2 的(64 减桶位宽)次方）的起点，而该区间内不含任何其他桶节点（不同桶区间互不重叠）。这就是"查找常数期望开销"的结构基础。

4.3 操作协议

查找。从桶单元读桶节点，沿链表按分裂序键前进，直到遇到键不小于目标键的节点或链表尾。全程不阻塞。每个被遍历的指针在解引用前先发布到回收保护，再重读源校验（防 ABA）——该发布与校验是协议层面的统一描述：危险指针方案下为实际的槽位写入与重读，世代方案下保护为空操作、重校验在编译期被跳过（每操作守卫已证明安全性）。快速路径先检查目标运行的首节点，再决定是否进入扫描循环——常见情况（运行长度为 1，无冲突）下循环被完全跳过。

插入。按键定位前驱；发布期望指针；把新节点接在前驱之后。关键规则：比较交换拒绝已标记的前驱。如果前驱已被逻辑删除（标记位已置），在其后插入的新节点会在删除方摘链时被一并孤立——这是无锁链表插入的经典陷阱，必须显式拒绝。

删除。两步走：先标记（把目标节点的后继指针第 0 位置 1），再摘链。摘链是循环：按指针（而非键——指针唯一，键可能重复）定位前驱，把前驱的后继从"已标记目标"比较交换为"目标的后继"，失败重试，直到目标被摘除。摘除完成后才把目标交给回收器。

下标访问。键不存在时插入新节点，并直接从刚链入的节点返回映射值引用——插入成功路径不需要第二次查找。重复键路径才需要再次定位已有元素。

4.4 线性化论证

每个操作的效果都是对某个节点后继指针的一次比较交换（或有界的比较交换序列），所有读路径只观察比较交换发布的状态。标准论证成立：每个操作在其成功的比较交换处生效。删除在标记处生效——标记之后所有查找都不再返回该元素；摘链稍后执行，只服务于回收安全，不改变线性化点。

4.5 扩容：为什么可以无锁

当插入观察到负载因子超限时（或显式预留容量时），桶间接表翻倍。扩容只做一件事：让新桶单元指向现有链表中的对应桶节点。元素从不移动，因此：

• 扩容的发布是一次比较交换（把新的桶表指针写入表引用）；
• 旧表交给回收器，等证明无人使用后释放；
• 新表的上半桶单元先置空，首次被触及时惰性物化（创建桶节点并链入链表）——这避免了扩容时的整表拷贝；
• 一个"扩容进行中"标志确保同一时刻只有一个线程在拷贝桶数组；其他线程继续在旧表上操作，互不阻塞；
• 查找遇空桶单元时，先物化再重试，通过标签位正确处理尚未插入的桶。

缓存增长阈值（松弛原子）让常见插入路径免于加载表指针；仅当计数超过缓存值时才走慢路径加载并验证。缓存值始终是真实阈值的下界，过期值只会多走慢路径，绝不会跳过必要的扩容——这是"性能优化不得破坏正确性"的典型设计。

4.6 工程细节：标签、单次加载与预取

标签位。后继指针的低两位承载标记信息（第 0 位标记删除、第 1 位标记桶节点）。所有从共享结构读出的指针必须先清除标签再解引用；原始带标签值保留用于比较交换的期望值与标记检查。标签复用指针的空闲低位，不增加节点内存。

单次加载纪律。遍历家族（定位、插入定位、首节点、下一节点两阶段、以及插入/查找/删除慢路径的运行扫描）的每个迭代只加载一次后继指针：清除后的指针用作预取地址与标记检查，原始带标签值用作比较交换期望值。早期版本曾为预取地址多加载一次松弛值——在 x86 上松弛与获取原子加载编译为同一条指令，多出的加载是纯开销。

软件预取。两条遍历热点（链表定位与树搜索）在加载后继/子节点后、使用之前发出预取指令（x86 专用，其他架构为空操作）。链表遍历是依赖加载链——每个后继指针位于不同缓存行——提前发起拉取把缓存未命中隐藏在比较交换或保护工作之后。预取地址必须是清除标签后的指针，否则可能预取到带标记的无效地址。

4.7 哈希混合

原始哈希（如 std::hash）在低位质量上不可靠——经典哈希表直接取模会因哈希低位分布差而退化。本库先把用户哈希混合成均匀的 64 位值，再取低位作桶选择、取位反转作分裂序键。混合是纯函数，无状态，不引入共享可变性。

5 有序容器：并发红黑树的原理

5.1 为什么红黑树难以完全无锁

完全无锁的红黑树只存在于研究文献，没有可用的参考实现。原因不是"没人试过"，而是结构性的：红黑树的插入/删除修复需要同时修改多个节点的多个指针（旋转涉及父、子、叔、兄弟、侄子），这些多点更新无法用单个比较交换表达——除非引入侵入式元数据（如每个节点的版本计数加帮助者协议），复杂度会陡增且难以验证。

因此本库选择了务实的折中：搜索完全无锁，更新用可证明无死锁的加锁路径。这个选择的合理性与代价，将在 5.6 节诚实说明。

5.2 锁位括号：无锁搜索的正确性协议

搜索（查找、包含、计数、下界、上界、迭代）用普通原子读沿树下降，从不阻塞。它依赖的协议是锁位括号：

两次锁位读取都看到"未加锁"，则两次读取之间的子指针是稳定的：任何修改方在修改该节点字段期间都持有锁，而两次获取序读取排除了修改在窗口内发生又结束的可能性。

两个细节值得说明：

• 子指针用松弛序。首次获取序锁位读已经与"加锁后解锁的修改方"建立了先行发生（解锁是释放写），子指针在锁下写入、经释放写发布，因此可见。第二次获取序读验证稳定性。中间的松弛读不需要额外栅栏。
• 两次锁位读之间的键比较是安全的。因为键不可变（构造时设定，永不修改），第二次检查只需验证子指针稳定，无需重读键。键不可变是无锁搜索的通用前提——它使"比较"与"指针稳定性"解耦。

5.3 更新路径：手拉手加锁

插入与删除沿根到叶的方向加锁：严格父先于子（手拉手，hand-over-hand），然后用经典红黑修复（CLRS）旋转，最后释放。修复步骤会额外锁定涉及的叔、兄弟、侄子节点。

死锁自由论证：所有锁的获取都沿有向树边、根到叶——主路径（根到目标）、删除扩展（目标到后继再到最左）、修复辅助边（祖父到父、父到兄弟、兄弟到侄子、祖父到叔）。每条边都是当前树的父到子边，因此锁序图是树的子图，无环。持有 B 的锁而要 A 的锁的线程，必有 A 是 B 的后代；两个线程不可能在锁上成环等待。死锁在构造上不可能。

5.4 无父指针与后继重链

无父指针。树节点不存父指针，更新路径用一个固定容量的路径栈记录沿途加锁的节点。这消除了整类"父链竞争"——父指针若存在，其更新与读取就构成新的同步点。

两个孩子的删除。经典红黑树删除有两个孩子时，用中序后继顶替。由于映射值节点中键是 const（不可交换值），本库采用后继节点重链：把后继节点整体移到目标位置。双黑（删除黑色后继产生）位于后继的原位置：后继是目标的右孩子时，双黑在后继自身的旧右槽，修复从后继自身开始；否则从后继的父开始。所有旋转与重链都在已加锁节点上进行。

根的特殊情况。根指针只可能在旧根锁被持有时改变（根处修复旋转，或删除根）。因此等待根锁的线程在获得锁后必须重新校验根指针，变了就重试——否则会沿一个不再是整棵树的子树下降。这个"获取锁后重验"的模式是手拉手协议的一部分，不是事后补丁。

5.5 缓存行与预取

节点结构把热搜索字段（左、右、锁位、颜色）放在首缓存行起始，冷字段（载荷、分配器归属）在后。搜索访问 N 个节点只加载每节点的热字段，紧凑排列避免读争用下拉入（可能很大的）载荷。

树搜索在子指针松弛加载后、第二次锁位获取检查前预取子节点缓存行。红黑树下降是随机访问模式——每个子指针通常指向冷缓存行——预取把 50-100 周期的缓存延迟隐藏在括号验证工作之后。预取指令用架构宏守护，非 x86 编译为空操作。

5.6 诚实的权衡

红黑树的更新路径在下降时锁定每个节点，并在整个更新期间持有根锁，因此更新完全串行化，每操作成本高于单互斥锁的 std::map——在所有测得线程数下，更新重负载的树都慢于标准库加锁。这不是缺陷，是文档化的设计选择：树的价值在于搜索无锁（从不阻塞、从不令写者等待），以及读路径无单一争用缓存行。选择 mpmc::map 的场景是读占主导、延迟绝不能被写者阻塞、或线程数很高；小型更新重负载应选择 std::map 加锁。

同样的诚实也适用于无序容器：单线程下它们比标准容器慢约 40%（无锁机制的固定开销：原子、标签、回收守卫），其价值从多线程才显现。没有免费的午餐，文档的职责就是把午餐的价格写清楚。

6 工程细节：节点池与分配器纪律

6.1 节点池

退休节点不直接归还分配器，而是进入按容器实例化共享的节点池：高换手负载复用热块，避免每次操作都触碰分配器（分配器调用通常伴随堆锁，多线程下成本可观）。

池记录每个块分配时的分配器（节点内嵌分配器归属指针）：池化块只被使用同一分配器实例的容器复用，否则通过其自身分配器释放。这保证了分配器平衡——每个块最终都归还给分配它的分配器实例，不同（或带状态）分配器的实例绝不会交叉释放。

池超过水位线时排空（有界内存驻留），每个容器析构时排空全部——析构后分配器的分配/释放计数精确相等（测试套件以计数分配器断言）。

6.2 分片池：缓存行隔离的工程实践

早期的池是单一共享锁。在 16 线程混合负载下，它成为新的瓶颈：实测每次池操作约 1.2 万周期（约 3 微秒），占全部线程时间约 55%。原因与前文的排空门控案例同构——一个被多线程竞争的共享缓存行上的锁定操作，其成本随竞争者数量超线性增长。

修复是分片：128 个缓存行隔离的分片，每线程首次使用时分配自己的分片（一次均摊的全局计数递增）；此后该线程的所有池操作只锁自己的分片，其缓存行只在自己的核心间流转，与其他线程的池流量互不干扰。每个分片在其水位份额处排空（总驻留有界）；容器析构函数排空所有分片。

一个关键的设计约束值得记录：分片索引是线程局部的，池本身必须保持为每实例化的静态成员。如果池也做成线程局部，会引入两类问题：其一，线程局部对象的析构顺序未定义——线程终结流程（把退休对象交还池）与池自身析构的先后不可控；其二，池可能比容器活得久（回收动作可能在容器析构后运行），线程局部池无法保证这一点。静态池加线程局部索引，兼得两者的优点。

6.3 分配器平衡与异常安全

节点分配走用户分配器；分配失败以分配器的异常传播。抛出路径上容器不变量必须保持：失败的插入不改变容器；回收簿记（跟踪退休对象的向量）在构造上保持对齐——先推指针、再推动作，动作推入失败则回退指针推入，两向量永不失同步。

键与映射类型被要求不抛拷贝构造、不抛析构（编译期断言强制），因此值操作本身不会抛出；唯一可能抛出的是分配器调用与下标越界访问。这让异常路径的论证范围变得很小、可穷举。

7 内存占用分析

无锁方案的内存成本需要被如实量化。本节的数字以 64 位平台、载荷为 int 对（8 字节键 + 8 字节值）为例；其他载荷按比例推算。结论先行：本库每元素的内存约为 std::unordered_map 的两倍，主要来自每桶一个哨兵节点与删除延迟释放；桶表本身与标准实现相同。

7.1 每元素的内存构成

#mermaid-svg-tKXevLrCrnAziFoJ{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-tKXevLrCrnAziFoJ .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-tKXevLrCrnAziFoJ .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-tKXevLrCrnAziFoJ .error-icon{fill:#552222;}#mermaid-svg-tKXevLrCrnAziFoJ .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-tKXevLrCrnAziFoJ .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-tKXevLrCrnAziFoJ .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-tKXevLrCrnAziFoJ .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-tKXevLrCrnAziFoJ .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-tKXevLrCrnAziFoJ .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-tKXevLrCrnAziFoJ .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-tKXevLrCrnAziFoJ .marker{fill:#333333;stroke:#333333;}#mermaid-svg-tKXevLrCrnAziFoJ .marker.cross{stroke:#333333;}#mermaid-svg-tKXevLrCrnAziFoJ svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-tKXevLrCrnAziFoJ p{margin:0;}#mermaid-svg-tKXevLrCrnAziFoJ .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-tKXevLrCrnAziFoJ .cluster-label text{fill:#333;}#mermaid-svg-tKXevLrCrnAziFoJ .cluster-label span{color:#333;}#mermaid-svg-tKXevLrCrnAziFoJ .cluster-label span p{background-color:transparent;}#mermaid-svg-tKXevLrCrnAziFoJ .label text,#mermaid-svg-tKXevLrCrnAziFoJ span{fill:#333;color:#333;}#mermaid-svg-tKXevLrCrnAziFoJ .node rect,#mermaid-svg-tKXevLrCrnAziFoJ .node circle,#mermaid-svg-tKXevLrCrnAziFoJ .node ellipse,#mermaid-svg-tKXevLrCrnAziFoJ .node polygon,#mermaid-svg-tKXevLrCrnAziFoJ .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-tKXevLrCrnAziFoJ .rough-node .label text,#mermaid-svg-tKXevLrCrnAziFoJ .node .label text,#mermaid-svg-tKXevLrCrnAziFoJ .image-shape .label,#mermaid-svg-tKXevLrCrnAziFoJ .icon-shape .label{text-anchor:middle;}#mermaid-svg-tKXevLrCrnAziFoJ .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-tKXevLrCrnAziFoJ .rough-node .label,#mermaid-svg-tKXevLrCrnAziFoJ .node .label,#mermaid-svg-tKXevLrCrnAziFoJ .image-shape .label,#mermaid-svg-tKXevLrCrnAziFoJ .icon-shape .label{text-align:center;}#mermaid-svg-tKXevLrCrnAziFoJ .node.clickable{cursor:pointer;}#mermaid-svg-tKXevLrCrnAziFoJ .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-tKXevLrCrnAziFoJ .arrowheadPath{fill:#333333;}#mermaid-svg-tKXevLrCrnAziFoJ .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-tKXevLrCrnAziFoJ .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-tKXevLrCrnAziFoJ .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-tKXevLrCrnAziFoJ .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-tKXevLrCrnAziFoJ .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-tKXevLrCrnAziFoJ .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-tKXevLrCrnAziFoJ .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-tKXevLrCrnAziFoJ .cluster text{fill:#333;}#mermaid-svg-tKXevLrCrnAziFoJ .cluster span{color:#333;}#mermaid-svg-tKXevLrCrnAziFoJ div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-tKXevLrCrnAziFoJ .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-tKXevLrCrnAziFoJ rect.text{fill:none;stroke-width:0;}#mermaid-svg-tKXevLrCrnAziFoJ .icon-shape,#mermaid-svg-tKXevLrCrnAziFoJ .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-tKXevLrCrnAziFoJ .icon-shape p,#mermaid-svg-tKXevLrCrnAziFoJ .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-tKXevLrCrnAziFoJ .icon-shape .label rect,#mermaid-svg-tKXevLrCrnAziFoJ .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-tKXevLrCrnAziFoJ .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-tKXevLrCrnAziFoJ .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-tKXevLrCrnAziFoJ :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

std::unordered_map：一个桶（每元素分摊）

桶单元8 B

元素节点next 8 + 哈希缓存 8载荷 16 = 32 B

本库：一个桶段（负载因子 1.0，每元素分摊）

桶单元8 B（与 std 相同）

哨兵节点 dummynext 8 + so_key 8载荷 16 + 归属 8 = 40 B

元素节点next 8 + so_key 8载荷 16 + 归属 8 = 40 B

按负载因子 1.0（桶数约等于元素数）估算：本库每元素约 88 字节（桶单元 8 + 哨兵 40 + 元素 40），std 约 40 字节（桶单元 8 + 元素 32）——比值约 2.2 倍。

7.2 哨兵节点为什么必须存在

哨兵不是可选优化，而是"扩容不移动元素"机制的结构前提：每个桶段的起点必须是一个常驻链表、且永不移动的锚点，查找才能从桶单元出发沿链表精确停在本段内。删掉哨兵，桶单元就只能指向元素——扩容后桶边界变化，指向就失效，元素就得移动。这笔内存是"扩容零移动 + 单次比较交换发布"的机制成本，不是浪费。

#mermaid-svg-aYlcbpnmIXnIxYrr{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-aYlcbpnmIXnIxYrr .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-aYlcbpnmIXnIxYrr .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-aYlcbpnmIXnIxYrr .error-icon{fill:#552222;}#mermaid-svg-aYlcbpnmIXnIxYrr .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-aYlcbpnmIXnIxYrr .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-aYlcbpnmIXnIxYrr .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-aYlcbpnmIXnIxYrr .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-aYlcbpnmIXnIxYrr .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-aYlcbpnmIXnIxYrr .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-aYlcbpnmIXnIxYrr .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-aYlcbpnmIXnIxYrr .marker{fill:#333333;stroke:#333333;}#mermaid-svg-aYlcbpnmIXnIxYrr .marker.cross{stroke:#333333;}#mermaid-svg-aYlcbpnmIXnIxYrr svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-aYlcbpnmIXnIxYrr p{margin:0;}#mermaid-svg-aYlcbpnmIXnIxYrr .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-aYlcbpnmIXnIxYrr .cluster-label text{fill:#333;}#mermaid-svg-aYlcbpnmIXnIxYrr .cluster-label span{color:#333;}#mermaid-svg-aYlcbpnmIXnIxYrr .cluster-label span p{background-color:transparent;}#mermaid-svg-aYlcbpnmIXnIxYrr .label text,#mermaid-svg-aYlcbpnmIXnIxYrr span{fill:#333;color:#333;}#mermaid-svg-aYlcbpnmIXnIxYrr .node rect,#mermaid-svg-aYlcbpnmIXnIxYrr .node circle,#mermaid-svg-aYlcbpnmIXnIxYrr .node ellipse,#mermaid-svg-aYlcbpnmIXnIxYrr .node polygon,#mermaid-svg-aYlcbpnmIXnIxYrr .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-aYlcbpnmIXnIxYrr .rough-node .label text,#mermaid-svg-aYlcbpnmIXnIxYrr .node .label text,#mermaid-svg-aYlcbpnmIXnIxYrr .image-shape .label,#mermaid-svg-aYlcbpnmIXnIxYrr .icon-shape .label{text-anchor:middle;}#mermaid-svg-aYlcbpnmIXnIxYrr .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-aYlcbpnmIXnIxYrr .rough-node .label,#mermaid-svg-aYlcbpnmIXnIxYrr .node .label,#mermaid-svg-aYlcbpnmIXnIxYrr .image-shape .label,#mermaid-svg-aYlcbpnmIXnIxYrr .icon-shape .label{text-align:center;}#mermaid-svg-aYlcbpnmIXnIxYrr .node.clickable{cursor:pointer;}#mermaid-svg-aYlcbpnmIXnIxYrr .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-aYlcbpnmIXnIxYrr .arrowheadPath{fill:#333333;}#mermaid-svg-aYlcbpnmIXnIxYrr .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-aYlcbpnmIXnIxYrr .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-aYlcbpnmIXnIxYrr .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-aYlcbpnmIXnIxYrr .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-aYlcbpnmIXnIxYrr .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-aYlcbpnmIXnIxYrr .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-aYlcbpnmIXnIxYrr .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-aYlcbpnmIXnIxYrr .cluster text{fill:#333;}#mermaid-svg-aYlcbpnmIXnIxYrr .cluster span{color:#333;}#mermaid-svg-aYlcbpnmIXnIxYrr div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-aYlcbpnmIXnIxYrr .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-aYlcbpnmIXnIxYrr rect.text{fill:none;stroke-width:0;}#mermaid-svg-aYlcbpnmIXnIxYrr .icon-shape,#mermaid-svg-aYlcbpnmIXnIxYrr .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-aYlcbpnmIXnIxYrr .icon-shape p,#mermaid-svg-aYlcbpnmIXnIxYrr .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-aYlcbpnmIXnIxYrr .icon-shape .label rect,#mermaid-svg-aYlcbpnmIXnIxYrr .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-aYlcbpnmIXnIxYrr .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-aYlcbpnmIXnIxYrr .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-aYlcbpnmIXnIxYrr :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

新桶表（8 桶，单次比较交换发布）

链表（扩容前后原样，元素与旧哨兵原地不动）

指向既有哨兵

指向既有哨兵

等回收后释放

dummy 0

dummy 2

元素 x

下一节点

桶单元

桶单元

旧桶表（4 桶）

回收器

扩容发布新表后，旧表与所有元素原地不动；新上半桶的哨兵在首次触及时创建，并按分裂序键插入链表中的对应位置（新哨兵的序键落在旧哨兵之间，元素相对次序不变）——从未被访问的桶不消耗哨兵内存（只占 8 字节桶单元，与 std 相同）。这是缓解项之一。

7.3 删除滞留的生命周期

#mermaid-svg-1jouhbvrlwerMTjC{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-1jouhbvrlwerMTjC .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-1jouhbvrlwerMTjC .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-1jouhbvrlwerMTjC .error-icon{fill:#552222;}#mermaid-svg-1jouhbvrlwerMTjC .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-1jouhbvrlwerMTjC .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-1jouhbvrlwerMTjC .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-1jouhbvrlwerMTjC .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-1jouhbvrlwerMTjC .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-1jouhbvrlwerMTjC .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-1jouhbvrlwerMTjC .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-1jouhbvrlwerMTjC .marker{fill:#333333;stroke:#333333;}#mermaid-svg-1jouhbvrlwerMTjC .marker.cross{stroke:#333333;}#mermaid-svg-1jouhbvrlwerMTjC svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-1jouhbvrlwerMTjC p{margin:0;}#mermaid-svg-1jouhbvrlwerMTjC defs #statediagram-barbEnd{fill:#333333;stroke:#333333;}#mermaid-svg-1jouhbvrlwerMTjC g.stateGroup text{fill:#9370DB;stroke:none;font-size:10px;}#mermaid-svg-1jouhbvrlwerMTjC g.stateGroup text{fill:#333;stroke:none;font-size:10px;}#mermaid-svg-1jouhbvrlwerMTjC g.stateGroup .state-title{font-weight:bolder;fill:#131300;}#mermaid-svg-1jouhbvrlwerMTjC g.stateGroup rect{fill:#ECECFF;stroke:#9370DB;}#mermaid-svg-1jouhbvrlwerMTjC g.stateGroup line{stroke:#333333;stroke-width:1;}#mermaid-svg-1jouhbvrlwerMTjC .transition{stroke:#333333;stroke-width:1;fill:none;}#mermaid-svg-1jouhbvrlwerMTjC .stateGroup .composit{fill:white;border-bottom:1px;}#mermaid-svg-1jouhbvrlwerMTjC .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px;}#mermaid-svg-1jouhbvrlwerMTjC .state-note{stroke:#aaaa33;fill:#fff5ad;}#mermaid-svg-1jouhbvrlwerMTjC .state-note text{fill:black;stroke:none;font-size:10px;}#mermaid-svg-1jouhbvrlwerMTjC .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5;}#mermaid-svg-1jouhbvrlwerMTjC .edgeLabel .label rect{fill:#ECECFF;opacity:0.5;}#mermaid-svg-1jouhbvrlwerMTjC .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-1jouhbvrlwerMTjC .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-1jouhbvrlwerMTjC .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-1jouhbvrlwerMTjC .edgeLabel .label text{fill:#333;}#mermaid-svg-1jouhbvrlwerMTjC .label div .edgeLabel{color:#333;}#mermaid-svg-1jouhbvrlwerMTjC .stateLabel text{fill:#131300;font-size:10px;font-weight:bold;}#mermaid-svg-1jouhbvrlwerMTjC .node circle.state-start{fill:#333333;stroke:#333333;}#mermaid-svg-1jouhbvrlwerMTjC .node .fork-join{fill:#333333;stroke:#333333;}#mermaid-svg-1jouhbvrlwerMTjC .node circle.state-end{fill:#9370DB;stroke:white;stroke-width:1.5;}#mermaid-svg-1jouhbvrlwerMTjC .end-state-inner{fill:white;stroke-width:1.5;}#mermaid-svg-1jouhbvrlwerMTjC .node rect{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-1jouhbvrlwerMTjC .node polygon{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-1jouhbvrlwerMTjC #statediagram-barbEnd{fill:#333333;}#mermaid-svg-1jouhbvrlwerMTjC .statediagram-cluster rect{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-1jouhbvrlwerMTjC .cluster-label,#mermaid-svg-1jouhbvrlwerMTjC .nodeLabel{color:#131300;}#mermaid-svg-1jouhbvrlwerMTjC .statediagram-cluster rect.outer{rx:5px;ry:5px;}#mermaid-svg-1jouhbvrlwerMTjC .statediagram-state .divider{stroke:#9370DB;}#mermaid-svg-1jouhbvrlwerMTjC .statediagram-state .title-state{rx:5px;ry:5px;}#mermaid-svg-1jouhbvrlwerMTjC .statediagram-cluster.statediagram-cluster .inner{fill:white;}#mermaid-svg-1jouhbvrlwerMTjC .statediagram-cluster.statediagram-cluster-alt .inner{fill:#f0f0f0;}#mermaid-svg-1jouhbvrlwerMTjC .statediagram-cluster .inner{rx:0;ry:0;}#mermaid-svg-1jouhbvrlwerMTjC .statediagram-state rect.basic{rx:5px;ry:5px;}#mermaid-svg-1jouhbvrlwerMTjC .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#f0f0f0;}#mermaid-svg-1jouhbvrlwerMTjC .note-edge{stroke-dasharray:5;}#mermaid-svg-1jouhbvrlwerMTjC .statediagram-note rect{fill:#fff5ad;stroke:#aaaa33;stroke-width:1px;rx:0;ry:0;}#mermaid-svg-1jouhbvrlwerMTjC .statediagram-note rect{fill:#fff5ad;stroke:#aaaa33;stroke-width:1px;rx:0;ry:0;}#mermaid-svg-1jouhbvrlwerMTjC .statediagram-note text{fill:black;}#mermaid-svg-1jouhbvrlwerMTjC .statediagram-note .nodeLabel{color:black;}#mermaid-svg-1jouhbvrlwerMTjC .statediagram .edgeLabel{color:red;}#mermaid-svg-1jouhbvrlwerMTjC #dependencyStart,#mermaid-svg-1jouhbvrlwerMTjC #dependencyEnd{fill:#333333;stroke:#333333;stroke-width:1;}#mermaid-svg-1jouhbvrlwerMTjC .statediagramTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-1jouhbvrlwerMTjC :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

删除（标记 + 摘链）

交给回收器

世代未满两代 / 槽仍被引用

世代越过两代 / 槽清空

块进入分片池

水位排空 / 容器析构

已摘除

退役

待释放

已释放

节点池

滞留窗口的上界：世代方案为两个世代（删除高峰期的对象在世代前进缓慢时驻留更久），危险指针方案为"所有槽不再引用"。此外，退役节点先进入节点池（按实例化共享、分片保存，总驻留有界）而非立即归还分配器——池化本身也是一种有界的内存保留，换取换手负载下避免分配器调用。

7.4 缓解手段与诚实的取舍

• 预留容量：启动时按预期规模预留桶数，避免运行期扩容的双表峰值；
• 选择回收方案：危险指针方案在退休列表达到阈值时触发扫描回收，滞留窗口通常更短（代价是每次解引用的发布-校验开销更高）；
• 惰性物化：从未访问的桶不创建哨兵——稀疏使用场景的实际内存低于上述稳态估算；
• 取舍陈述：约 2 倍的内存换取了标准实现不具备的性质——扩容无停顿、单次比较交换原子发布、读者永不等待写者。内存极敏感的应用应在选择前把这一条计入权衡。

8 性能的测量与诚实解读

7.1 方法学

基准在参考机器（clang 17，发布构建，Windows x64）上运行。两种负载：混合（40% 插入/40% 删除/20% 查找，私有键范围加共享范围查找）与读多（10%/10%/80%）。每单元为确定性可复现运行（固定每线程随机种子）。参考机器的后台负载在 35%-90% 之间波动，因此多线程绝对值以区间报告，定性结论（世代优于危险指针、树更新串行化、无序容器随核心扩展）在每次运行中稳定。

7.2 数据与解读

无序容器对"标准库加互斥锁"：

• 读多负载：2 线程起超越（8 线程约 2.2-12.9 倍区间，见文档数据表）；
• 混合负载：4 线程起超越（8 线程约 1.26 倍）；
• 单线程：约 0.6 倍——无锁机制的固定开销，如实记录。

无序容器聚合混合吞吐在 4 到 16 线程持平（约 4000 万次每秒）：共享链表及其计数器的结构性上限，不是缺陷。只读 16 线程约 7.4 亿次每秒。

有序容器：更新路径串行化，更新重负载在所有线程数下都慢于标准库；读多负载随线程数拉近差距（8 线程约 0.83 倍并继续上升）。

这些数字的诚实表述要点是：速度比是有条件的（负载构成、线程数、机器、负载窗口），单点数字不可外推。文档的价值在于给出条件与区间，而不是一个醒目的倍数。

9 验证方法论

并发代码无法靠"多跑几次"证明正确。本库的验证是多层互补的：

• 随机化对照测试：固定种子，对标准容器做逐操作对照（顺序、大小、语义、迭代、边界），失败即确定性可复现；
• 并发压力测试：每线程私有键范围加共享读，记录每键的最后操作，结束后校验每键的期望状态；随机数生成器按线程固定种子，运行可精确重放——这是"压力测试可复现"的关键设计；
• 红黑平衡回归：确定性操作流后每次操作都校验红黑不变量（无红红、黑高相等）——顺序/大小对照无法发现的再平衡漂移只有结构校验能捕获；
• 计数分配器：分配与释放精确计数并断言相等——任何泄漏或过度释放都会使断言失败（它曾捕获树析构泄漏）；
• 消毒器：未定义行为消毒器（clang）与地址消毒器（MSVC）跑完整套件；
• 编译期检查：负编译测试（可抛拷贝构造的键必须被拒绝）、类型特征断言（不可复制、不可移动）；
• 警告门禁：MSVC 严格警告等级零警告编译全部测试源；头文件纯 ASCII。

验证的局限同样要如实说明：消毒器只在执行到的路径上生效；压力测试的线程交错不可穷举；黑盒对照无法证明线性化点正确。这些局限由设计层论证（第 4.4、5.3 节）补足。

10 结语

无锁并发容器是"算法结构、内存模型、硬件现实、工程纪律"四者的交汇。本文试图呈现的，是这条路径上的关键原理与教训：

• 结构决定可行性：分离序链表把扩容变成"指针重定向"，红黑树的多点更新决定它只能折中；
• 回收是地基：没有可靠的回收，一切无锁都是悬垂；两代规则与危险指针扫描是两种不同的证据形式；
• 测量纠正直觉：两处瓶颈（排空门控、池锁）都是"看似常数、实为全局争用"的操作被触发频率放大；定位靠计数，不靠猜；
• 诚实是工程的一部分：单线程的代价、更新的串行化、扩展的天花板，都应写进文档，而不是藏起来。

最后回到开头的命题：无锁不是免费的午餐，它把锁的代价换成了原子操作、回收机制与复杂度。它值得付出，当且仅当应用真正需要它提供的性质——不阻塞的读、无死锁的写、随核心扩展的吞吐。判断的根据，是测量，不是信仰。

11 代码走读：核心协议的逐行剖析

本节以伪代码呈现两个引擎的核心循环，逐行解释每个步骤存在的原因。伪代码保留原实现的变量名与分支，省略模板与宏。

11.1 无序：定位与插入

定位（locate）是查找、插入、删除共享的骨架：

locate(混合哈希, 目标分裂键):
循环:
表 = 读表指针(获取序)
桶号 = 混合哈希 & (表大小 – 1)
桶节点 = 读表.桶[桶号](获取序)
若桶节点为空:
物化该桶(递归物化父桶, 创建桶节点链入链表, 发布桶单元)
继续循环
前驱 = 桶节点
发布前驱到保护槽
当前 = 保护读(前驱.后继) # 读后继并发布
循环:
若 当前为空 或 当前.分裂键 >= 目标键: 返回(前驱, 当前)
原始后继 = 读 当前.后继(获取序) # 单次加载
若 原始后继 带标记:
帮助摘链: 前驱.后继 比较交换(期望=带标记当前, 新值=清除标记的后继)
当前 = 保护读(前驱.后继)
否则:
前驱 = 当前; 发布前驱
当前 = 保护读(前驱.后继)

逐行理由：表指针与桶单元用获取序，因为要看到发布者写入的桶节点；空桶先物化再重试，保证查找面对的是完整结构；前驱发布到保护槽后再读后继，保证后继读到的节点不会在解引用前被回收；单次加载的后继原始值同时服务三个用途（标记检查、清除后作预取地址、比较交换期望值）；遇到已标记节点顺手帮助摘链（帮助者协议）——摘链是幂等的，谁做都行，不做也不破坏正确性，只拖延回收。

插入（insert_from）从桶节点开始沿链表前进，找到插入点后执行：

插入(起始桶节点, 新节点):
循环:
前驱 = 起始; 发布前驱
当前 = 保护读(前驱.后继)
循环:
若 当前为空 或 当前.分裂键 >= 新节点.分裂键:
新节点.后继 = 当前 # 先接好再发布自己
期望 = 带标记值
若 期望 带标记: 跳出内层循环重试 # 拒绝已标记前驱
若 前驱.后继 比较交换(期望, 新节点) 成功: 返回
跳出内层循环重试 # 前驱已变: 重新定位
…前进…

插入的线性化点是成功的那次比较交换。失败的原因有两种：前驱被标记（必须放弃——否则新节点会随前驱的摘链被孤立），或前驱的后继被并发修改（重来）。新节点先把自己的后继指好再发布自己，保证发布瞬间结构完整——读者不会看到"已入链但后继悬空"的中间状态。

11.2 无序：删除的标记-摘链-回收

删除(键):
循环:
定位(键) -> (前驱, 当前)
若 当前 为空 或 当前.分裂键 != 目标: 返回 失败
若 当前.后继 带标记: 继续循环 # 已被并发删除
若 当前.后继 比较交换(期望, 置标记) 失败: 继续循环
# 标记成功: 线性化点
摘链(前驱, 当前, 混合哈希, 分裂键)
回收(当前)
计数递减
返回 成功

标记与摘链分离是刻意的：标记是线性化点（此后所有查找不再返回该元素），摘链只服务于回收安全。摘链的快速路径是对前驱后继做一次比较交换（期望=已标记目标）；失败则重新定位并按指针扫描运行（指针唯一，键可能重复），直到目标被摘除或证明已被帮助者摘除。目标被摘除后才交给回收器——这是"先摘链、后回收"纪律的落点，违反它（回收仍在链上的节点）就是悬垂指针的直接来源。

11.3 无序：扩容的单次发布

扩容(强制 = 假):
若 扩容标志 比较交换(假 -> 真) 失败: 返回 # 唯一赢家
循环:
表 = 读表指针
若 计数 <= 阈值 且 非强制: 结束
新表 = 分配并初始化(大小 = 表.大小 * 2) # 全部单元置空
拷贝 表.桶[0 .. 表.大小-1] -> 新表 # 只拷下半
若 表指针 比较交换(表 -> 新表) 成功:
旧表交给回收器
继续循环 # 计数可能又超阈值: 再扩
否则: 结束 # 有别人发布了新表
释放扩容标志

关键点：新表发布前，下半桶单元已指向旧表对应桶节点（这些桶节点在旧表生命周期内不变，拷贝是安全的）；上半桶单元保持空，由首次触发的查找物化。因此发布新表的那一刻，所有桶都能被正确解析——要么指向现成桶节点，要么触发惰性物化。竞争者的路径是零成本的：它们在获取扩容标志之前就已返回，不会创建新表。标志持有者内部的发布失败是一个防御性分支（正常流程下不会出现，因为持有标志期间只有自己修改表指针）——该分支直接释放未发布的新表，避免泄漏。

11.4 有序：搜索的括号协议

搜索(键):
循环:
当前 = 读根指针(获取序)
发布根指针
若 根指针 重读 != 当前: 继续循环 # 根在等待期间变了
循环:
若 当前 为空: 返回(未找到, 最后访问节点)
读 当前.锁位(获取序) # 括号前
若 已加锁: 从头重试
比较结果 = 比较(键, 当前.键) # 两次锁位读之间
子 = 读 当前.左或右(松弛序)
预取(子) # 仅 x86
读 当前.锁位(获取序) # 括号后
若 已加锁: 从头重试
按比较结果决定: 相等 -> 返回 当前; 小于 -> 下降到左; 大于 -> 下降到右

括号协议的精髓是：两次锁位获取读之间，修改方要么完全没碰这个节点（未加锁），要么加锁修改后又解锁（第一次读到已加锁则重试，第二次读到已加锁也重试）。排除这两种情况后，中间的松弛子指针读必然对应一个稳定状态。键比较发生在两次锁位读之间是安全的，因为键不可变——比较不依赖可能变化的字段，第二次检查只需验证子指针稳定。

11.5 有序：更新路径的加锁-重验-修复

锁定路径(键): # 手拉手
循环:
路径栈清空
当前 = 读根指针(获取序)
若 当前 为空: 返回 空树
锁定(当前) # 自旋
若 根指针 重读 != 当前: # 等待锁期间根可能变了
解锁(当前); 继续循环 # 重验根: 协议的一部分
路径栈压入(当前)
循环:
比较决定下降方向
若 相等: 返回 (找到目标, 路径)
子 = 读 当前.相应子指针(松弛序) # 父锁已提供可见性
若 子 为空: 返回 (插入/删除位置, 路径)
锁定(子)
路径栈压入(子)
当前 = 子

"获取锁后重验根"不是可选的防御——根指针只可能在旧根锁被持有时改变，等待锁的线程必须确认自己拿到的是当前根，否则会沿一个不再是整棵树的子树下降。下降路径上读子指针用松弛序：父节点此时已被本线程锁定（加锁为获取释放比较交换、解锁为释放写），锁本身提供了子指针的可见性，无需额外同步。修复阶段按路径栈自叶向根回卷，逐节点解锁（尽早释放，缩短锁持有时间）；涉及叔、兄弟、侄子的旋转在锁定这些节点后进行。修复完成后路径栈全部解锁。

12 内存序逐点论证

无锁代码的审查核心是"每个原子操作为什么用这个内存序"。下表给出关键位置与理由（获取=读同步侧，释放=写同步侧）：

两条统一原则：需要看到别人的发布，就用获取；需要让别人看到自己的写，就用释放；两者兼需，用获取释放；其余一律松弛。 违背这些原则的常见错误是：把"数据竞争"误当作"不关心顺序"而使用松弛读去读一个正在被写的位置——原子性只保证不撕裂，不保证一致性。

13 接口设计与语义约定

14.1 为什么不可复制、不可移动

四个容器都删除拷贝构造与拷贝赋值，也不提供移动。理由：并发容器在使用中无法通过拷贝安全地快照（拷贝过程本身就是并发修改的目标）；移动构造会让"容器引用"在并发读者眼皮底下更换所有者，与无锁的线性化模型冲突。需要快照时，由调用方在独占窗口内自行遍历拷贝；需要换容器时，用间接层（如智能指针）。

14.2 弱一致迭代器

迭代器是弱一致的：迭代访问一个类似快照的视图，但不保证反映所有并发修改——并发插入的元素可能被访问也可能不被访问；并发删除的元素在回收后绝不会被解引用（回收保证）。迭代期间并发修改是安全的，但访问到的元素集合不确定。这是并发容器迭代器的标准语义，与"强一致快照"有本质区别。

14.3 析构契约

清空与析构要求独占访问：不得有其他线程正在操作，且所有用户线程已先行汇合（join）。这是文档化契约而非强制机制——违反即未定义行为。契约的依据是回收器的终结流程：线程退出时其线程局部状态已终结（未回收对象移交共享链），析构时才能证明"没有遗留引用"。契约不靠代码强制，靠文档与纪律。

14.4 下标访问的语义

映射容器的下标访问在键不存在时插入默认值并返回其引用；存在时返回现有引用。这使下标访问成为"可能修改"的操作，与标准库语义一致。越界读取（只读版本的按键访问）在键不存在时抛出标准异常。所有返回引用或指针的操作，其有效性以"元素未被删除"为界——删除后节点可能随时被回收，持用过期引用是调用方错误。

14.5 审计钩子

有序容器暴露若干调试/审计方法（不属于标准接口）：结构校验（遍历全树检查排序与计数一致性）、最大深度、红黑不变量全量校验（无红红、黑高相等）、节点转储。它们是 O(n) 的、必须独占调用、只用于测试——它们的存在是为了让验证方法论（第 8 节）中的"每次操作后校验不变量"成为可能，而非面向生产。

14 常见问题与工程建议

14.1 何时选择无锁容器

选择无锁容器，依据是应用需要的性质，而不是"无锁更高级"的直觉：

• 需要读不阻塞：读者绝不等待写者，反之亦然。互斥锁方案中读者与写者互相等待；
• 需要无死锁：加锁方案在复杂锁序下可能死锁，无锁写路径在构造上无环；
• 需要确定性延迟：无锁操作没有阻塞点，最坏情况是重试；
• 需要随核心扩展：读多负载下无锁容器随核心数扩展，互斥锁在争用下吞吐封顶。

反之，以下场景应选择标准库加锁：单线程或低竞争；更新重负载（尤其有序容器——其更新路径串行化）；对内存占用极敏感（回收器引入额外内存保留）；需要强一致快照迭代。

14.2 性能调优清单

• 预留容量：写前用预留接口把桶表扩到位，避免运行期扩容（扩容本身无锁，但触发扩容的路径有额外开销）；
• 控制负载因子：默认值已兼顾空间与冲突率；对冲突敏感的应用可调低；
• 独占窗口做管理操作：清空、析构、审计校验在独占窗口内执行；
• 安静窗口测量：多线程基准受后台负载影响显著，对比应在负载可控时进行，且以区间而非单点为准；
• 按实例化选回收器：读极多、长期发布指针的应用可显式选择危险指针（读路径无全局热点）；默认世代方案在混合与读多负载下普遍更优。

14.3 集成与迁移注意

• 线程生命周期：使用容器的线程必须在容器析构前汇合；线程退出时其退休对象移交共享链，由后续回收或析构排空；
• 分配器：节点最终归还给分配它的分配器实例；带状态分配器可用，但同一容器实例的所有节点必须来自同一分配器实例（复用判据）；
• 键类型：必须不抛拷贝构造、不抛析构（编译期强制）；哈希与相等函数必须无状态且线程安全（标准库同要求）；
• 引用有效期：迭代器与引用在元素被删除前有效；删除后视为失效，不得再解引用；
• 快照：需要一致性视图时，在独占窗口内自行遍历拷贝；库不提供并发快照。

14.4 调试无锁代码的方法

无锁代码的 bug 通常是"理论正确、实测偶尔错"。有效的调试工具链：

14.5 常见误解澄清

• “无锁一定更快”：不成立。单线程下无锁机制是纯开销；多线程下的优势取决于负载与争用程度。本文给出的对比数据明确显示单线程约 0.6 倍、多线程才反超；
• “原子操作就是线程安全”：不成立。原子性只保证单次读写不撕裂；跨操作的复合不变量（如"先检查后使用"）需要协议与内存序，否则仍是数据竞争；
• “内存序只是性能选项”：不成立。错误的内存序是正确性错误——松弛读可能读到陈旧值，错误使用获取/释放可能破坏先行发生链；
• “回收器解决了一切内存问题”：不成立。回收器只解决"何时释放安全"，"是否泄漏"取决于容器纪律（摘链后回收、析构排空、分配器平衡）与调用方契约（独占析构）；
• “压力测试通过就是正确”：不成立。压力测试只能证伪不能证实；正确的论证来自协议（线性化点、锁序无环、两代规则），测试是论证的佐证。

15 结语：工程原则清单

把本文的教训压缩为一份可携带的清单：

无锁并发容器的价值，不在于"快"这个字，而在于它提供的性质：读者不等待、写者无死锁、吞吐随核心扩展。当应用真正需要这些性质时，无锁是正确的工程选择；当它不需要时，标准库加锁是更简单也更省的正确选择。判断的根据是需求与测量，不是信仰——这既是本文的方法，也是本文想传达的态度。

术语对照表

16 源码结构导览

把原理映射到代码布局，便于读者按图索骥：

• include/mpmc/——四个容器头文件：mpmc_unordered_map.hpp、mpmc_unordered_set.hpp、mpmc_map.hpp、mpmc_set.hpp。每个都是标准兼容接口的薄包装：类型别名、构造/析构、容量/修改/查找/迭代成员，全部转发给引擎；
• include/mpmc/detail/——实现细节：
  • split_ordered_table.hpp：无序引擎。标签位工具、节点与桶表结构、定位/插入/删除/扩容/迭代、增长阈值；
  • rb_tree.hpp：有序引擎。节点结构（缓存行感知布局）、锁位括号搜索、路径栈、手拉手更新、红黑修复、审计钩子；
  • epoch.hpp 与 hazard_pointer.hpp：两种回收方案。每线程状态、退休入队、回收调度、线程退出终结、迟到回收链、析构排空；
  • reclamation.hpp：统一接口与默认方案选择；
  • utils.hpp：自旋锁、节点池（分片实现）、池链策略、位反转与哈希混合工具；
  • cache_line.hpp：缓存行对齐常量。
• tests/——十个测试套件加公共断言头：对照测试、压力测试（支持线程数参数）、平衡回归、分配器平衡、编译期特征断言、负编译样例；
• bench/——四个基准程序与微基准：回收方案对比、无序/有序对标准库加锁对比、单线程微基准，以及结果记录；
• docs/——英文与中文成对的 API 参考、设计文档、性能文档、回收文档；README 与其中文版位于仓库根目录。

这个布局遵循一条原则：引擎不含任何策略选择——回收方案、哈希、比较、分配器全部通过模板参数注入；引擎代码对两种回收方案完全相同，方案差异被统一接口（操作守卫、保护、退役、回收、排空）完全封装。这使得"换回收器"与"换哈希"一样是纯配置，也使得两种方案的测试可以共用同一套引擎测试。

17 一个完整案例：从需求到部署

以"多线程会话表"为例走一遍决策过程。需求：数千并发连接共享一张会话表（键为会话标识，值为会话状态），读为主（每次请求查一次）、偶发增删（连接建立/断开）、延迟敏感、不允许请求被其他连接的增删阻塞。

第一步：明确需要的性质。 读不阻塞（请求延迟不因他连接的增删而抖动）、无死锁（连接管理线程众多）、读多扩展（并发请求数随核心增长）。这些性质指向无锁容器；负载构成（读为主）指向无序引擎与世代回收。

第二步：确定接口约束。 键为固定长度标识，不抛拷贝构造、不抛析构——满足编译期约束；值（会话状态）独立于容器生命周期管理，容器只持有状态指针或值语义的小对象；分配器用默认即可。

第三步：配置与调优。 连接数上限已知，启动时用预留接口把桶表扩到位，运行期不再扩容；负载因子取默认；回收方案用默认世代，读多负载下世代比危险指针快约 1.4-1.6 倍（见第 8 节数据）。

第四步：生命周期契约。 连接管理线程与请求处理线程共享容器；关闭时先停止请求处理，再汇合所有线程，最后析构容器——独占析构契约得到满足；会话删除路径（连接断开）由连接线程完成，删除后不再持用其引用。

第五步：验证与监控。 集成前跑压力测试（可重放、逐键校验、计数分配器断言平衡、消毒器全套）；上线后在安静窗口做基准对比，确认扩展曲线与预期一致；对延迟敏感度做分位数测量而非均值——无锁结构的最坏情况是重试，其分布尾部应由测量确认。

这个案例没有用到任何超出本文第 1-14 节的原理：结构决定可行性、回收是地基、接口语义清晰、验证分层互补。无锁容器的部署不是"换一个容器类"那么简单，而是一组契约（线程生命周期、引用有效期、独占析构）的落实——契约的纪律性，最终决定正确性。

18 尾声

本文从内存模型出发，依次走过了回收机制、两种引擎、工程细节、性能解读、验证方法与接口语义，最后以源码导览与完整案例收束。贯穿始终的方法论只有一条：每一个设计决策都能回答"基于什么证据"——结构选择基于复杂度论证，内存序选择基于同步需求，优化选择基于周期计数，方案选择基于对比测量，权衡记录基于诚实。当证据不足时，如实说明不足，而不是用修辞补足。

无锁并发是并发编程里最接近"物理"的分支：缓存一致性、指令重排、失效延迟，这些都不是可以靠约定回避的抽象。理解它们、测量它们、敬畏它们，是写出可验证的无锁代码的唯一路径。希望本文对读者的这条路径有所助益。

19 语义的精确定义

并发容器的性能对比若无语义前提则无意义，此处把本文使用的术语定义清楚：

• 线性一致性（linearizability）：每个操作都表现为在其执行期间某个时刻原子生效。本库四种容器提供线性一致性：无序容器以成功比较交换为线性化点，有序容器以标记/锁内链接为线性化点。线性一致性是"单次操作正确"的保证，不承诺跨操作的整体顺序；
• 弱一致迭代：迭代过程反映一个类似快照的视图，但不承诺反映所有并发修改。这是并发哈希/树容器避免"快照成本"的标准选择；
• 多生产者多消费者（MPMC）：任意线程可读可写。与单生产者单消费者（SPSC，通常可用无等待的环形缓冲实现）不同，MPMC 无法避免竞争——竞争的对象是共享结构本身，无锁承诺的是"竞争不导致阻塞与死锁"，而非"竞争没有成本"；
• 无锁（lock-free）：系统级保证——任意线程的任意操作都能在有限步内完成，即使其他线程被无限延迟。本库无序容器全部路径无锁；有序容器搜索无锁、更新为可证明无死锁的加锁路径。文档在"无锁"一词上的用法严格对应此定义，不把"无锁"当作"不加锁"的同义词；
• 可重放（replayable）：压力测试的随机数按线程固定种子，失败案例可以原样重现。这是并发测试可调试性的基础——不可重现的失败等于没有失败现场。

语义边界的诚实陈述：本库不提供事务、不提供跨容器原子性、不提供顺序一致性的多操作序列。超出边界的需求应在上层协议解决，而不是指望容器承担。

20 延伸阅读

• M. Michael. Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects（危险指针原始论文）；
• O. Shalev, N. Shavit. Split-Ordered Lists: Lock-Free Extensibility of Hash Tables（分离序链表原始论文）；
• K. Fraser, T. Harris. Concurrent Programming Without Locks（无锁编程的综合方法，含世代回收思想）；
• M. Herlihy, N. Shavit. The Art of Multiprocessor Programming（多处理器编程艺术：线性一致性、无锁数据结构与验证方法）；
• C++11 标准 [intro.races] 与 [atomics]（数据竞争与原子操作的形式定义）；
• 本库的工程文档（设计与性能文档，含完整测量方法与数据表）可作为上述文献的工程对照。

本文引用的所有测量数据、代码结构与设计论证，均可在仓库源码与文档中复核；不依赖任何未公开的假设。