LongAdder · 分段锁 · false sharing

分片与争用

前四页解决的是「多线程改同一个结构会不会出错」。本页解决的是另一件事：不出错的结构，为什么线程加到十六个之后反而更慢。

答案不在算法里，在谁和谁抢同一个字。

1 · 争用的形状

模型很简单：每一轮，每个还有活的线程各自挑一个 cell 发起一次 CAS；落在同一个 cell 上的线程里只有一个成功，其余全部失败并在下一轮重来。

这个模型不预测真实吞吐（那要算 cache line 往返的时钟周期），但它给出争用的结构性部分。8 个线程各自自增 200 次，全部压在单个 cell 上：失败重试 5600 次，跑完要 1600 轮。5600 这个数有闭式——第一轮到第 200 轮有 8 个线程在抢，此后依次减少，总失败数是 $200 \times \binom{8}{2} = 5600$ 。

2 · 分片计数器

把一个 cell 换成 $S$ 个，每个线程只碰其中一个，读取时把 $S$ 个加起来。Java 的 LongAdder 就是这个东西，它给每个线程一个 probe 值决定用哪个 cell，撞车了就重算 probe。

图 2-1 · 分片计数器的争用曲线：CAS 失败重试次数随分片数的变化，以及各分片承接的成功次数。可切换三种挑片方式，调整线程数与分片数，也可切到 8 个 seed 取平均。

挑片方式决定曲线的形状，三种差别很大：

线程绑定分片： $S$ 一达到线程数争用就归零。8 线程下的实测是 5600、2400、1400、800、600、400、200、0， $S = 8$ 之后再加分片毫无收益。LongAdder 把 cell 数量封顶在 CPU 数，理由在此。
key 决定分片（分片哈希表就是这种）： $S = 8$ 时仍有 779 次重试， $S = 16$ 时 396 次，加倍只砍掉一半，永远不归零。原因是 balls into bins——随机投掷的碰撞概率随 $S$ 下降但不消失，哈希表系列量过同一件事的另一面。
撞了就换一片：介于两者之间，每个 $S$ 上都略优于第二种。代价是分片选择不再稳定。

注 · 「分片越多重试越少」本以为是一条无条件的单调关系，实测在 key 决定分片的模式下不成立：单个 seed 的曲线尾部会回升， $S = 15$ 的 367 次涨到 $S = 16$ 的 396 次。逐个查过 8 个 seed，其中 5 个至少出现一次这样的回升，位置各不相同。分片一多，每片承接的操作就少，一次抽样的碰撞数波动盖过了分片带来的那点差别。8 个 seed 平均之后单调恢复，可见回升是抽样噪声而非机制。正文引用的曲线因此取平均值，单 seed 的曲线只在图 2-1 里保留，供对照。

3 · 锁粒度的三档

同一套思路搬到哈希表上，变量是「两个操作什么时候算撞在一起」，即争用域怎么划。

一把大锁：整表一个争用域<br> 分段锁：bucket 归约到 $S$ 个 segment<br> per-bucket CAS：每个 bucket 自成一个争用域

Java 7 的 ConcurrentHashMap 用的是第二档，默认 16 段，concurrencyLevel 参数调的就是段数。Java 8 换成第三档：bucket 头结点为空时直接 CAS 挂上，非空时 synchronized 锁住头结点，于是争用域细到单个 bucket，concurrencyLevel 从此只剩兼容语义。

图 3-1 · 三档锁粒度在同一批 key 上的被挡次数与轮数对照。可调线程数、段数与桶数，观察桶数远超线程数之后收益如何趋平。

16 线程各 100 次操作、64 个 bucket、16 段的实测：一把大锁被挡 12000 次、跑 1600 轮，轮数正好等于总操作数，也就是完全串行；分段锁 908 次、216 轮；per-bucket 187 次、124 轮。三档的算法一模一样。

桶数远大于线程数之后曲线趋平——争用不再是瓶颈，剩下的开销在访存与哈希本身上。

分片切开了逻辑上的争用，硬件上还有一层没切开。缓存一致性协议以 cache line 为单位工作，通常 64 字节。两个线程各写各的分片，若这两个分片落在同一条 line 上，每一次写都会让对方的那份副本作废。

图 4-1 · 分片在 cache line 上的排布与跨片作废次数。可调每个 cell 占多少字节，观察 padding 到 64 字节时作废归零。

16 个 8 字节的 cell 挤在 2 条 line 上，8 个线程各写各的，实测跨片作废 11172 次；cell 撑到 16 字节降到 4788 次，32 字节 1596 次，64 字节归零。有效数据仍是 8 字节，其余全是 padding，空间利用率 12.5%。

LongAdder 的 cell 类上挂着 @Contended 注解，JVM 据此在字段两侧插入 padding，做的就是这件事。高频交易里的无锁环形队列 §2 从另一个角度量过同一现象：那里是一个 producer 写两个 counter，本页是多个线程写多个 cell，成因相同。

警示 · padding 不是越多越好。每个 cell 独占一条 line 意味着 $S$ 个分片占 $64S$ 字节， $S$ 取到 CPU 数时已是几千字节，而这些字节全部驻留在各核的 L1 里。分片计数器的读取端还要遍历全部分片求和，分片越多这一步越贵。LongAdder 的 sum() 因此不是原子快照——它逐个读 cell 相加，期间别的线程还在改，返回的是一个「近似值」。要精确总数就得停写，这正是它换来写侧可扩展性的代价。

5 · 分片改变了什么与没改变什么

分片降低的是争用，不是操作本身的代价。单线程下分片计数器比普通计数器慢——多一次 probe 计算、多一次间接寻址。它的价值在斜率：线程数翻倍时，单 cell 版本的失败率随之上升，分片版本基本持平。

也有一类东西分片解决不了。需要跨分片的原子操作（比如「总数超过阈值就拒绝」）没法只锁一片；需要精确快照的读取只能停写。分片本质上是把一个强一致的对象拆成若干个弱耦合的部分，能拆的前提是操作可交换。计数的加法可交换，所以能拆；Michael-Scott 队列的 FIFO 次序不可交换，所以拆不了——多个分片队列合起来不再是一个队列。

6 · 参考文献

Anderson, T. E. (1990). The performance of spin lock alternatives for shared-memory multiprocessors. IEEE Transactions on Parallel and Distributed Systems, 1(1), 6–16. 争用随线程数增长的经典测量。
Mellor-Crummey, J. M., & Scott, M. L. (1991). Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems, 9(1), 21–65. MCS 锁：让每个等待者在自己的 cache line 上自旋。
Dice, D., Hendler, D., & Mirsky, I. (2013). Lightweight contention management for efficient compare-and-swap operations. Euro-Par 2013, 595–606.
OpenJDK. java.util.concurrent.atomic.Striped64 源码注释。cell 数组扩张策略、probe 重算与 @Contended padding 的取舍都记在开头那段长注释里。
Lea, D. java.util.concurrent.ConcurrentHashMap 源码注释（Java 8）。开头解释了从 segment 换到 per-bucket 的动机与遗留参数的处理。