第 18 篇：并发数据结构——加锁容易，加对锁难

一、先加上锁，正确性就有了

给任何一个数据结构加锁，有一个万能做法：

每个公开函数一进来就上锁，一出去就解锁。

链表的 insert、lookup、delete 各自锁住同一把锁，正确性立刻成立——同一时刻只有一个线程在动这个结构。

这叫粗粒度锁（coarse-grained locking）。它有个非常大的优点：基本不会写错。

然后你把它放到 8 核机器上，发现完全跑不起来。

打个比方

接着第 16 篇那个钱箱。

一把大锁，相当于整个银行只有一个柜台。 存款、取款、查余额、办卡，全部排一条队。

只有一个客户时，这个柜台效率极高。但你雇十个柜员也没用——柜台只有一个，另外九个只能站着看。

⭐ 更糟的是：十个人挤在一个柜台前，光是"谁下一个"的争执就要花时间。这不是比喻——下一节的实测里，加线程真的会让总吞吐下降。

二、跑一遍看看：加线程反而更慢

一个用 pthread_mutex 保护的计数器，每个线程加一百万次：

if (MODE == 0) {                       /* 一把大锁 */
    pthread_mutex_lock(&glock); global++; pthread_mutex_unlock(&glock);
}

  一把大锁    1 线程   总数  1000000   用时 0.004 秒   吞吐 27592.3 万次/秒
  一把大锁    2 线程   总数  2000000   用时 0.061 秒   吞吐  3292.6 万次/秒
  一把大锁    4 线程   总数  4000000   用时 0.183 秒   吞吐  2191.4 万次/秒
  一把大锁    8 线程   总数  8000000   用时 0.225 秒   吞吐  3551.4 万次/秒

一个线程 2.76 亿次/秒。加到两个线程，掉到 3292 万次/秒——慢了八倍。

⭐ 不是"加速比不理想"，是绝对性能下降。 你多雇了一个人，总产出反而少了。

原因有两层：

1. 序列化。 临界区里只能有一个线程，所以吞吐的上限就是单线程的速度——加人不可能变快。
2. 竞争的开销。 抢锁本身要付钱：原子指令、缓存行在核之间来回搬、拿不到锁的线程要陷入内核挂起再被唤醒。人越多，这笔钱越贵。

第 2 条就是"绝对下降"的来源。单线程时没有竞争，一分钱不用付。

三、第一级解法：把锁拆细

既然一把锁是瓶颈，那就多来几把。

并发链表：与其锁整个链表，不如每个节点一把锁。遍历时按"抓住下一个再放开当前"的方式挪动（hand-over-hand locking）。

⚠️ 但这个例子恰好说明拆锁不总是划算：每挪一步就要一次加锁解锁，而链表遍历本来只是一次指针跳转。锁的开销比被保护的操作还大。 实测中它常常还不如一把大锁。

并发哈希表：这个就漂亮多了。

哈希表天然分成很多桶，每个桶一把锁。两个线程只要哈希到不同的桶，就完全不互相干扰。

⭐ 哈希表是并发场景里的明星，不是因为它查得快，是因为它天然可分。 而链表天然不可分——它是一条链，你必须顺着走。

⭐ 这给出一条很实用的判据：拆锁划算不划算，取决于这个数据结构本身能不能被切成互不相干的块。

四、另一种拆法：拆操作，不拆数据

上一节那条判据里藏着一个前提：数据能被切开。 那数据切不开的时候怎么办？

一份全局配置、一张路由表、一个缓存的元数据——它就是一整块，没有"桶"可分。但它有另一个性质：

绝大多数访问只是读它，很少有人改它。

而两个人同时读，本来就不会互相干扰。 冲突只发生在"有人在写"的时候。互斥量看不见这个区别——它把每一次访问都当成潜在的冲突，于是十个只想读的线程被排成一队，而它们本来可以一起进去。

读写锁（reader-writer lock）就是把这个区别告诉锁：

读锁：可以同时被很多人持有。 写锁：独占，和所有人互斥（包括其他写者）。

⭐ 注意这一节和上一节是两个不同的切法：上一节按数据切（每个桶一把锁），这一节按操作类型切（读的一起进，写的自己来）。数据切不开的时候，还可以试试切操作。

打个比方

还是那家银行。

一把大锁是整个银行只有一个柜台，办什么业务都排一条队。

读写锁是：“查余额"的人可以一起进大厅看那块公告牌——十个人同时看一块牌子，谁也不碍着谁。但要改牌子上的数字时，得先把所有人请出去。

跑一遍看看：它值多少

8 个线程反复访问同一份数据，每次在临界区里扫 1024 个槽。只改一件事：其中多大比例是写。

if (是写操作) { pthread_rwlock_wrlock(&rw);  /* 改一个槽 */  pthread_rwlock_unlock(&rw); }
else          { pthread_rwlock_rdlock(&rw);  /* 扫一遍   */  pthread_rwlock_unlock(&rw); }

8 个线程反复访问同一份数据，每次在临界区里扫 1024 个槽，各跑 2 秒

  写的比例     互斥量(次/秒)    读写锁(次/秒)     倍率
  0%                 1931960          4961675    2.57x
  5%                 1891664          2827384    1.49x
  20%                1917667          2828080    1.47x
  50%                1857207          3088926    1.66x

读写锁确实赢了，但赢得不多——而且比你预期的少得多。

⚠️ 先看第一行那个 0%：全是读者，8 个线程理论上可以完全并行，你会期望 8 倍。实测只有 2.57 倍。

为什么？⭐ 因为读写锁本身没有被拆开。 八个读者虽然进了临界区就互不干扰，但它们都得先去改同一个读者计数器——那是一次原子操作，落在同一条缓存行上。第 17 篇那个"缓存行在核之间乒乓"的问题，一个字没少地又出现了一次。

读者之间不再互斥了，但它们仍然在同一个点上排队。

⚠️ 再看后面三行：只要掺进 5% 的写，倍率就从 2.57 掉到 1.49。因为一个写者进来，所有读者都得等，攒下来的并行度一次清空。

⭐ 所以读写锁的适用条件比大多数人以为的窄得多：

读必须占压倒性多数，而且临界区要足够长——长到值回那次原子操作的钱。

临界区很短的时候，读写锁往往还不如互斥量——加读锁本身的开销，比它保护的那点活儿还大。这和上一节链表的结论是同一句话。

⭐ 更麻烦的问题：写者会饿死

性能只是小事。读写锁真正的坑在公平性上。

想一想：读者可以同时进去。那么当一个写者在门口等的时候，新来的读者要不要放行？

• 放行（读者优先）：写者要等到一个读者都不剩的那一刻。而如果读者源源不断地来，这一刻永远不会到来。
• 不放行（写者优先）：新读者也得排在写者后面等。写者不会饿死了，但读的吞吐掉下来。

这不是理论担忧。glibc 默认是读者优先，我们让它自己演示后果：7 个读者不停地抢读锁，1 个写者每毫秒尝试写一次，跑 3 秒。唯一的变量是那个策略标志：

pthread_rwlockattr_setkind_np(&at, PTHREAD_RWLOCK_PREFER_READER_NP);            /* 默认 */
pthread_rwlockattr_setkind_np(&at, PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);

7 个读者不停抢读锁，1 个写者每毫秒想写一次，跑 3 秒

  读者优先（默认）    成功写入   3 次   中位等待  780.267 ms   最坏  2157.194 ms
  写者优先            成功写入 200 次   中位等待    0.006 ms   最坏     0.034 ms

⭐ 3 秒里，那个写者只挤进去了 3 次。中位等待 780 毫秒——而写者优先时是 0.006 毫秒。差了十三万倍。

（我跑了三遍，读者优先那一行分别是 3 次、1 次、3 次。有一次它整整 3 秒一个字都没写进去，最坏等待就是全程。）

⚠️ 请注意这里没有任何 bug。两行代码都是对的，锁也没坏，读者们全都正常工作着。只是那个写者永远排不上号——这就是第 17 篇提过的饥饿，而这次它不是自旋锁的小毛病，是一个默认配置带来的、能让写入彻底停摆的后果。

回到银行：看公告牌的人排着队源源不断地进大厅，而想改牌子的人必须等到大厅一个人都没有。 只要还有人在往里走，他就永远等下去。

⭐ 所以用读写锁的时候，“读者优先还是写者优先"是一个你必须显式决定的问题，不是一个实现细节。而绝大多数人从来没想过这件事——他们拿到的是默认值，也就是会饿死写者的那个。

结论

读写锁看起来像是"免费的并行”，实际上它是这么一笔账：

⭐ 一句话：读写锁不是"更好的互斥量”，它是一个赌注——赌你的负载读远多于写，而且临界区足够长。赌对了赢一点，赌错了亏，而且它还塞给你一个必须回答的公平性问题。

⚠️ 这也是为什么这一篇的三级解法里，它排在"拆锁"之后而不是之前：先确认你的数据真的切不开，再来考虑切操作。

五、第二级解法：换掉锁

有些结构可以完全不用锁，只靠第 17 篇那条 CAS 指令。

比如一个无锁栈的 push：

1. 读当前栈顶 old
2. 把新节点的 next 指向 old
3. CAS(栈顶, old, 新节点)
   —— 成功就完事；失败说明有人插队了，回到第 1 步重来

好处是没有线程会被阻塞。一个线程被调度器换下去，不会挡住别人（而拿着锁被换下去就会）。

代价很实在：

• 写起来极难，验证更难。 内存顺序、ABA 问题（值变回原来的样子，CAS 以为没变过），每一个都能坑死人。
• 高竞争时不一定更快——大家都在重试，做的都是无用功。

⚠️ 实践建议很简单：优先用标准库里现成的无锁结构，不要自己写。

六、⭐ 第三级解法：改需求

前两级都在优化"怎么实现"。第三级换个问题：

你真的需要这个计数器随时都精确吗？

大多数时候不需要。统计信息、监控指标、缓存命中率——你要的是趋势，不是每一刻的精确值。

近似计数器（也叫可扩展计数器）就利用了这一点：

• 每个线程一个自己的局部计数（各自一把锁，或者干脆无锁）。
• 加一时只动自己的。
• 攒够一个阈值（比如 1024），才去把它并进全局计数一次。

pthread_mutex_lock(&local[id].l);
local[id].v++;
if (local[id].v >= THRESH) {
    pthread_mutex_lock(&glock); global += local[id].v; pthread_mutex_unlock(&glock);
    local[id].v = 0;
}
pthread_mutex_unlock(&local[id].l);

同样的活儿，同样的机器：

  近似计数器  1 线程   总数  1000000   用时 0.004 秒   吞吐 26990.2 万次/秒
  近似计数器  2 线程   总数  2000000   用时 0.004 秒   吞吐 50099.2 万次/秒
  近似计数器  4 线程   总数  4000000   用时 0.004 秒   吞吐 90557.0 万次/秒
  近似计数器  8 线程   总数  8000000   用时 0.008 秒   吞吐 94397.6 万次/秒

并排看这两组：

• 单线程时两者一样快（近似计数器没有额外收益）。
• 4 线程时差了 41 倍。
• 而且近似计数器几乎是线性扩展的：1 → 2 → 4 线程，吞吐接近翻倍再翻倍。

代价明明白白：全局值最多可能落后 线程数 × 阈值。 8 个线程、阈值 1024，最多落后 8192。

⭐ 你用"精确性"换了"可扩展性"，而且这笔交易的价码是你自己定的——阈值调小，误差小、扩展性差；调大，反过来。

回到银行：这就是让每个柜员自己记流水，攒够一千笔再去总账房登记一次。 总账房前面不再排长队了，代价是总账上的数字总比现实慢一拍。

⚠️ Linux 内核里到处是这个模式：percpu 计数器、per-CPU 的内存分配缓存（第 11 篇的 tcache 是同一思想）、per-CPU 的调度队列（第 7 篇）。“每个核一份，偶尔汇总"是内核可扩展性的第一原则。

七、代价与取舍

这三级解法换来的东西是递进的： 拆锁换来并行度、无锁换来不阻塞、近似换来近乎线性的扩展。

它们各自花了什么：

• 拆锁：多把锁 = 多个加锁顺序 = 死锁风险（第 21 篇）。而且锁本身的开销变多了——链表那个例子就得不偿失。
• 无锁：难写、难验、ABA 陷阱，高竞争时不一定快。
• 近似：读到的值不精确。

它们共同放弃了什么： 简单。

⭐ 所以有一条实践顺序值得记牢：

先用一把大锁把它写对，测出来真的慢，再拆。

因为大多数数据结构根本没到会成为瓶颈的程度。为一个每秒调用一百次的函数做无锁优化，是纯亏——你付出了正确性风险，换来了看不见的收益。

先测量，再优化。 上面那张表就是"测量"长什么样。

八、小结

• 粗粒度锁（每个函数进来上锁、出去解锁）正确性容易保证，但会成为瓶颈。
• ⭐ 实测：一把大锁的计数器，1 线程 2.76 亿次/秒，2 线程掉到 3292 万——加了一个线程慢了八倍。原因是序列化（上限就是单线程）加竞争开销（人越多越贵）。
• 第一级：拆锁。 ⚠️ 但不总划算——链表拆成每节点一把锁，锁的开销比被保护的操作还大。⭐ 判据是这个结构本身能不能切成互不相干的块：哈希表能（每桶一锁），链表不能。
• 数据切不开时，还可以切操作——读写锁让读者并发、写者独占。⚠️ 但它比想象中差得多：实测全是读者时也只有 2.57 倍（八个读者仍在同一条缓存行上排队），掺进 5% 的写就掉到 1.49 倍，临界区短时还不如互斥量。
• ⭐ 读写锁真正的坑是公平性：读者优先就会饿死写者。实测 glibc 默认配置下，7 个读者不停读时，写者 3 秒只挤进去 3 次、中位等待 780 毫秒；换成写者优先是 200 次 / 0.006 毫秒——差十三万倍，而两边代码都没有 bug。⚠️ “读者优先还是写者优先"是你必须显式回答的问题，默认值会饿死写者。
• 第二级：无锁，只靠 CAS 重试。好处是不阻塞，代价是难写难验、有 ABA 陷阱、高竞争时不一定快。用标准库的，别自己写。
• ⭐ 第三级：改需求。 近似计数器每线程自己记、攒够阈值再汇总一次。实测 4 线程时快 41 倍，且近乎线性扩展；代价是全局值最多落后 线程数 × 阈值——价码由你自己定。
• ⚠️ “每个核一份，偶尔汇总"是内核可扩展性的第一原则：percpu 计数器、tcache、per-CPU 调度队列都是它。
• ⭐ 先用一把大锁写对，测出来真的慢，再拆。

思考题

1. 第二节里，8 线程的吞吐（3551 万）反而比 4 线程（2191 万）高。这不符合"人越多越贵"的说法。可能是什么原因？（提示：这台机器的核不一样快，而且测量本身有噪声——你该怎么设计实验来分辨？）
2. 近似计数器的误差上界是 线程数 × 阈值。如果这个计数器是用来做限流的（超过 N 就拒绝请求），这个误差可以接受吗？如果是用来统计 QPS 呢？
3. 哈希表每桶一把锁。那么扩容（rehash）怎么办？扩容时要动所有桶——这一下是不是又回到一把大锁了？
4. 银行那个比方里，“每个柜员自己记流水，攒够一千笔报一次总账”。那么，如果行长随时要看准确的总额，该怎么办？代价是什么？
5. 第四节实测：全是读者时读写锁也只快 2.57 倍，而不是 8 倍。瓶颈是那个读者计数器所在的同一条缓存行。照第六节"每个核一份"的思路，你会怎么改造这个计数器？改造之后，写者要付出什么代价？（这个想法真的有人做了，叫 per-CPU 读写锁，Linux 内核里就有。）
6. 写者优先能防饿死写者，但它反过来会不会饿死读者？如果一个写者接一个写者源源不断地来呢？想一个两边都不饿死的策略。

延伸

• 上一篇：第 17 篇：锁——从一条原子指令建起来
• 下一篇：第 19 篇：条件变量——等待一件事发生