Java高性能并发计数器如何实现：Striped64和LongAdder的用法及原理

作者：吴潇

职位：Java软件工程师

原创声明

这是本人的署名原创文章，未经许可不支持转载，请勿抄袭。本公众号的所有文章均为本人原创。为了更容易理解和记忆，今后所有文章将以图解为主、代码为辅，忽略不太重要的细节，但保留关键技术细节。如果您感兴趣，欢迎关注！

基于JDK 7，我们如何实现一个多线程计数器？一般做法是定义一个volatile long或定义一个AtomicLong（底层也是volatile long），然后在每个线程中用CAS操作对它进行add操作。这两种做法都是没问题的，功能是正确的、性能也还好，我们继续按照原来的方式使用即可。不过，如果你的项目升级到了JDK 8，还可以进一步提高多线程计数器的性能，让它比传统的volatile long方式更高效。JDK 8新增的LongAdder类（父类是Striped64，包含一些公用方法）就是用来完成这个目的的，使用方法就像下面这样的。

LongAdder使用起来跟AtomicLong类似且非常简单。那么LongAdder与AtomicLong有什么不同点，它是如何提高性能的？

1. 消除热点：把一个变量拆成多个变量

AtomicLong之所以有性能瓶颈，是因为当有非常多的线程并发地对其执行CAS操作时，会产生大量竞争（竞争的含义：多个线程同时写入某个变量的时候，只有一个能成功）。那些竞争失败的线程需要重新读出volatile long的最新值，然后把自己的增量加上去，再用CAS操作与其他线程竞争。所有线程都需要通过这个AtomicLong，在经过这个AtomicLong的时候是串行执行的。虽然写入一个变量的代价很低，但是终归是瓶颈。

多个线程都去读写同一个volatile long，让这个long成为了性能瓶颈。因此，LongAdder把这个中心化的long拆成多个long从而减少竞争。需要总和的时候，再把这些被拆开的long求和加起来。这样导致增加了内存空间的占用量，相当于是在用空间换取时间，如图所示。

2. 动态扩容：根据负载情况增加拆分变量

但是应该怎么拆分以及拆成多少个呢？显然，不应该拆成固定个数的long，因为这样比较死板，而是应该根据访问LongAdder的线程的竞争情况，拆分成特定个数的long，即动态拆分策略。当线程竞争不激烈的时候，让LongAdder中只存在一个volatile long；当竞争变激烈后，让LongAdder中多增加一些volatile long；但是并非volatile long越多越好，当数量增加到CPU个数之后，再增加拆分变量已没有多大意义（因为此时不存在两个线程同时写一个volatile long的情况）。

以上思路对应到LongAdder的具体实现（在其父类Striped64中）就是原来的volatile long被拆成一个volatile long base 和一个Cell cells[]，如下图所示。

Cell本质上就是一个volatile long，只不过它的定义增加了一个@sun.misc.Contended注解。这个注解的作用是减少，原子变量因为存放在相邻的位置，容易导致CPU的cache line冲突而削弱性能的问题（所以，如果需要使用原子变量数组，记得仿照Striped64的Cell类，否则性能将很差）。其中，cells是一个长度为2的n次幂的数组，每次扩容都变为原来大小的2倍，当大小超过CPU个数时不再增长（长度超过cpu个数后已经没有意义了，因为同一时刻最多只有N=cpu个数的线程同时运行）。

3. 将线程hash到cells数组slot

把一个long拆成一个base和多个cell后，add操作如何计数？首先尝试写入base，如果写入操作一直没有遇到竞争（即用CAS操作修改base全都成功），那么修改的都是base，cells为null；当遇到第一次竞争时（CAS操作修改base失败），cells被初始化为一个长度等于2的cells数组，并且把当前线程映射到cells数组的一个slot，然后再在这个位于这个slot的Cell上执行CAS操作；如果在Cell上的CAS操作也失败了，则把当前线程的probe值向前调整（probe得作用相当于线程的hash值），再次尝试映射并且执行CAS；如果这里的CAS失败了，那么视为hash冲突并且执行扩容，然后再回头重试。这里的具体执行逻辑比较繁琐，如果不是特别感兴趣建议不必深究。

这里根据线程的probe值（作用相当于hashcode）找到Cells[]数组某个slot的思想跟HashMap/ConcurrentHashMap完全一样，即：

1. 保证数组长度length等于2的n次方（例如8，二进制是10000000）
2. 然后有一个掩码mask=length-1（二进制01111111），
3. 用mask与hash码执行index = mask & hash，结果刚好是数组下标。

这样就找到了slot。这里管理cells[]和映射线程的功能正是Striped64所提供的功能，这个类的名字“Striped64”曾经困扰我。现在明白了其含义了：JDK源码术语dynamic striping指把一个变量拆成多个，放在一个可扩展的数组中管理，Striped64指的是数组中的变量是64位。

通过以上优化手段，LongAdder在并发访问量非常高的情况下，性能显著优于AtomicLong。虽然LongAdder的并发写入性能高，但它的读操作并不是原子操作，无法得到某个时刻的精确值。例如，在调用sum()的时候，如果还有线程正在写入，那么sum()返回的就不是当时的精确值，使用的时候需要留意。

总之，LongAdder适用于统计和显示系统中的某些高速变化的状态，是Java高级工程师应该掌握的API。