前言
一提到线程安全的并发计数器,AtomicLong 必然是第一个被联想到的工具。Atomic* 一系列的原子类以及它们背后的 CAS 无锁算法,常常是高性能,高并发的代名词。本文将会阐释,在并发场景下,使用 AtomicLong 来充当并发计数器将会是一个糟糕的设计,实际上存在不少 AtomicLong 之外的计数器方案。近期我研究了一些 Jdk1.8 以及 JCTools 的优化方案,并将它们的对比与实现细节整理于此。
阅读本文前
本文相关的基准测试代码均可在博主的 github 中找到,测试方式全部采用 JMH,这篇文章可以帮助你入门 JMH。
AtomicLong 的前世今生
在 Java 中,Atomic* 是高效的,这得益于 sun.misc.Unsafe 提供的一系列底层 API,使得 Java 这样的高级语言能够直接和硬件层面的 CPU 指令打交道。并且在 Jdk1.7 中,这样的底层指令可以配合 CAS 操作,达到 Lock-Free。
在 Jdk1.7 中,AtomicLong 的关键代码如下:
public final long getAndIncrement() {
while (true) {
long current = get();
long next = current + 1;
if (compareAndSet(current, next))
return current;
}
}
public final boolean compareAndSet(long expect, long update) {
return unsafe.compareAndSwapLong(this, valueOffset, expect, update);
}
我们特别留意到 Jdk1.7 中 unsafe 使用的方法是 compareAndSwapLong,它与 x86 CPU 上的 LOCK CMPXCHG 指令对应,并且在应用层使用 while(true) 完成自旋,这个细节在 Jdk1.8 中发生了变化。
在 Jdk1.8 中,AtomicLong 的关键代码如下:
public final long getAndIncrement() {
return unsafe.getAndAddLong(this, valueOffset, 1L);
}
Jdk1.7 的 CAS 操作已经不复存在了,转而使用了 getAndAddLong 方法,它与 x86 CPU 上的 LOCK XADD 指令对应,以原子方式返回当前值并递增(fetch and add)。
当问及 Atomic* 高效的原因,回答 CAS 是不够全面且不够严谨的,Jdk1.7 的 unsafe.compareAndSwapLong 以及 Jdk1.8 的 unsafe.getAndAddLong 才是关键,且 Jdk1.8 中不存在 CAS。
Jdk1.8 AtomicLong 相比 Jdk1.7 AtomicLong 的表现是要优秀的,这点我们将在后续的测评中见证。
AtomicLong 真的高效吗?
无论在 Jdk1.7 还是 Jdk1.8 中,Atomic* 的开销都是很大的,主要体现在:
抛开上述导致 AtomicLong 慢的原因,AtomicLong 仍然具备优势:
看一组 AtomicLong 在不同并发量下的性能表现:
横向对比,写的性能相比读的性能要差很多,在 20 个线程下写性能比读性能差距了 4~5 倍。
纵向对比,主要关注并发写,线程竞争激烈的情况下,单次自增耗时从 22 ns 增长为了 488 ns,有明显的性能下降。
实际场景中,我们需要统计系统的 qps、接口调用次数,都需要使用到计数的功能,写才是关键,并不是每时每刻都需要关注自增后的返回值,而 AtomicLong 恰恰在核心的写性能上有所欠缺。由此引出其他计数器方案。
认识 LongAdder
Doug Lea 在 JDK1.8 中找到了一个上述问题的解决方案,他实现了一个 LongAdder 类。
@since 1.8
@author Doug Lea
public class LongAdder extends Striped64 implements Serializable {}
LongAdder 的 API 如下
LongAdder
你应当发现,LongAdder 和 AtomicLong 明显的区别在于,increment 是一个 void 方法。直接来看看 LongAdder 的性能表现如何。(LA = LongAdder, AL = AtomicLong, 单位 ns/op):
我们从中可以发现一些有意思的现象,网上不少很多文章没有从读写上对比二者,直接宣称 LongAdder 性能优于 AtomicLong,其实不太严谨。在单线程下,并发问题没有暴露,两者没有体现出差距;随着并发量加大,LongAdder 的 increment 操作更加优秀,而 AtomicLong 的 get 操作则更加优秀。鉴于在计数器场景下的特点—写多读少,所以写性能更高的 LongAdder 更加适合。
LongAdder 写速度快的背后
网上分析 LongAdder 源码的文章并不少,我不打算详细分析源码,而是挑选了一些必要的细节以及多数文章没有提及但我认为值得分析的内容。
1、Cell 设计减少并发修改时的冲突
LongAdder
在 LongAdder 的父类 Striped64 中存在一个 volatile Cell[] cells; 数组,其长度是 2 的幂次方,每个 Cell 都填充了一个 @Contended 的 Long 字段,为了避免伪共享问题。
@sun.misc.Contended static final class Cell {
volatile long value;
Cell(long x) { value = x; }
// ... ignore
}
LongAdder 通过一系列算法,将计数结果分散在了多个 Cell 中,Cell 会随着并发量升高时发生扩容,最坏情况下 Cell == CPU core 的数量。Cell 也是 LongAdder 高效的关键,它将计数的总值分散在了各个 Cell 中,例如 5 = 3 + 2,下一刻,某个线程完成了 3 + (2 + 1) = 6 的操作,而不是在 5 的基础上完成直接相加操作。通过 LongAdder 的 sum() 方法可以直观的感受到这一点(LongAdder 不存在 get 方法)
public long sum() {
Cell[] as = cells; Cell a;
long sum = base;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
这种惰性求值的思想,在 ConcurrentHashMap 中的 size() 中也存在,毕竟他们的作者都是 Doug Lea。
2、并发场景下高效获取随机数
LongAdder 内部算法需要获取随机数,而 Random 类在并发场景下也是可以优化的。
ThreadLocalRandom random = ThreadLocalRandom.current();
random.nextInt(5);
使用 ThreadLocalRandom 替代 Random,同样出现在了 LongAdder 的代码中。
3、longAccumulate
longAccumulate 方法是 LongAdder 的核心方法,内部存在大量的分支判断。首先和 Jdk1.7 的 AtomicLong 一样,它使用的是 UNSAFE.compareAndSwapLong 来完成自旋,不同之处在于,其在初次 cas 方式失败的情况下(说明多个线程同时想更新这个值),尝试将这个值分隔成多个 Cell,让这些竞争的线程只负责更新自己所属的 Cell,这样将竞争压力分散开。
LongAdder 的前世今生
其实在 Jdk1.7 时代,LongAdder 还未诞生时,就有一些人想着自己去实现一个高性能的计数器了,比如一款 Java 性能监控框架 dropwizard/metrics 就做了这样事,在早期版本中,其优化手段并没有 Jdk1.8 的 LongAdder 丰富,而在 metrics 的最新版本中,其已经使用 Jdk1.8 的 LongAdder 替换掉了自己的轮子。在最后的测评中,我们将 metrics 版本的 LongAdder 也作为一个参考对象。
JCTools 中的 ConcurrentAutoTable
并非只有 LongAdder 考虑到了并发场景下计数器的优化,大名鼎鼎的并发容器框架 JCTool 中也提供了和今天主题相关的实现,虽然其名称和 Counter 看似没有关系,但通过其 Java 文档和 API ,可以发现其设计意图考虑到了计数器的场景。
An auto-resizing table of longs, supporting low-contention CAS operations.Updates are done with CAS's to no particular table element.The intent is to support highly scalable counters , r/w locks, and other structures where the updates are associative, loss-free (no-brainer), and otherwise happen at such a high volume that the cache contention for CAS'ing a single word is unacceptable.
ConcurrentAutoTable
在最后的测评中,我们将 JCTools 的 ConcurrentAutoTable 也作为一个参考对象。
最终测评
Jdk1.7 的 AtomicLong,Jdk1.8 的 AtomicLong,Jdk 1.8 的 LongAdder,Metrics 的 LongAdder,JCTools 的 ConcurrentAutoTable,我对这五种类型的计数器使用 JMH 进行基准测试。
public interface Counter {
void inc();
long get();
}
将 5 个类都适配成 Counter 接口的实现类,采用 @State(Scope.Group),@Group 将各组测试用例进行隔离,尽可能地排除了互相之间的干扰,由于计数器场景的特性,我安排了 20 个线程进行并发写,1 个线程与之前的写线程共存,进行并发读。Mode=avgt 代表测试的是方法的耗时,越低代表性能越高。
Benchmark (counterType) Mode Cnt Score Error Units
CounterBenchmark.rw Atomic7 avgt 3 1049.906 ± 2146.838 ns/op
CounterBenchmark.rw:get Atomic7 avgt 3 143.352 ± 125.388 ns/op
CounterBenchmark.rw:inc Atomic7 avgt 3 1095.234 ± 2247.913 ns/op
CounterBenchmark.rw Atomic8 avgt 3 441.837 ± 364.270 ns/op
CounterBenchmark.rw:get Atomic8 avgt 3 149.817 ± 66.134 ns/op
CounterBenchmark.rw:inc Atomic8 avgt 3 456.438 ± 384.646 ns/op
CounterBenchmark.rw ConcurrentAutoTable avgt 3 144.490 ± 577.390 ns/op
CounterBenchmark.rw:get ConcurrentAutoTable avgt 3 1243.494 ± 14313.764 ns/op
CounterBenchmark.rw:inc ConcurrentAutoTable avgt 3 89.540 ± 166.375 ns/op
CounterBenchmark.rw LongAdderMetrics avgt 3 105.736 ± 114.330 ns/op
CounterBenchmark.rw:get LongAdderMetrics avgt 3 313.087 ± 307.381 ns/op
CounterBenchmark.rw:inc LongAdderMetrics avgt 3 95.369 ± 132.379 ns/op
CounterBenchmark.rw LongAdder8 avgt 3 98.338 ± 80.112 ns/op
CounterBenchmark.rw:get LongAdder8 avgt 3 274.169 ± 113.247 ns/op
CounterBenchmark.rw:inc LongAdder8 avgt 3 89.547 ± 78.720 ns/op
如果我们只关注 inc 即写性能,可以发现 jdk1.8 的 LongAdder 表现的最为优秀,ConcurrentAutoTable 以及两个版本的 LongAdder 在一个数量级之上;1.8 的 AtomicLong 相比 1.7 的 AtomicLong 优秀很多,可以得出这样的结论,1.7 的 CAS+LOCK CMPXCHG 方案的确不如 1.8 的 LOCK XADD 来的优秀,但如果与特地优化过的其他计数器方案来进行比较,便相形见绌了。
如果关注 get 性能,虽然这意义不大,但可以见得,AtomicLong 的 get 性能在高并发下表现依旧优秀,而 LongAdder 组合求值的特性,导致其性能必然存在一定下降,位列第二梯队,而 ConcurrentAutoTable 的并发读性能最差。
关注整体性能,CounterBenchmark.rw 是对一组场景的整合打分,可以发现,在我们模拟的高并发计数器场景下,1.8 的 LongAdder 获得整体最低的延迟 98 ns,相比性能最差的 Jdk1.7 AtomicLong 实现,高了整整 10 倍有余,并且,随着并发度提升,这个数值还会增大。
AtomicLong 可以被废弃吗?
既然 LongAdder 的性能高出 AtomicLong 这么多,我们还有理由使用 AtomicLong 吗?
本文重点讨论的角度还是比较局限的:单机场景下并发计数器的高效实现。AtomicLong 依然在很多场景下有其存在的价值,例如一个内存中的序列号生成器,AtomicLong 可以满足每次递增之后都精准的返回其递增值,而 LongAdder 并不具备这样的特性。LongAdder 为了性能而丧失了一部分功能,这体现了计算机的哲学,无处不在的 trade off。
高性能计数器总结
AtomicLong :并发场景下读性能优秀,写性能急剧下降,不适合作为高性能的计数器方案。内存需求量少。
LongAdder :并发场景下写性能优秀,读性能由于组合求值的原因,不如直接读值的方案,但由于计数器场景写多读少的缘故,整体性能在几个方案中最优,是高性能计数器的首选方案。由于 Cells 数组以及缓存行填充的缘故,占用内存较大。
ConcurrentAutoTable :拥有和 LongAdder 相近的写入性能,读性能则更加不如 LongAdder。它的使用需要引入 JCTools 依赖,相比 Jdk 自带的 LongAdder 并没有优势。但额外说明一点,ConcurrentAutoTable 的使用并非局限于计数器场景,其仍然存在很大的价值。
在前面提到的性能监控框架 Metrics,以及著名的熔断框架 Hystrix 中,都存在 LongAdder 的使用场景,有兴趣的朋友快去实践一下 LongAdder 吧。
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对小牛知识库的支持。
本文向大家介绍深入理解Java多线程与并发编程,包括了深入理解Java多线程与并发编程的使用技巧和注意事项,需要的朋友参考一下 一、多线程三大特性 多线程有三大特性:原子性、可见性、有序性。 原子性 (跟数据库的事务特性中的原子性类似,数据库的原子性体现是dml语句执行后需要进行提交): 理解:即一个操作或多个操作,要么全部执行并且执行的过程中不会被任何因素打断,要么都不执行。 一个很经典的例子就
本文向大家介绍Java并发之线程池Executor框架的深入理解,包括了Java并发之线程池Executor框架的深入理解的使用技巧和注意事项,需要的朋友参考一下 线程池 无限制的创建线程 若采用"为每个任务分配一个线程"的方式会存在一些缺陷,尤其是当需要创建大量线程时: 线程生命周期的开销非常高 资源消耗 稳定性 引入线程池 任务是一组逻辑工作单元,线程则是使任务异步执行的机制。当存在大量并发任
具有以下商业案例: 电子邮件促销活动表示,第一个点击链接的1_000_000用户将获得奖金。用户在访问网页时会立即看到奖金或“对不起”消息。 问题:如何设计此解决方案? 选项1:独石。原子整数。CAS问题可以在这里发生吗?或者1_000_000不是在这种情况下引起问题的金额吗?能做到这一点的数字是多少
本文向大家介绍深入分析java并发编程中volatile的实现原理,包括了深入分析java并发编程中volatile的实现原理的使用技巧和注意事项,需要的朋友参考一下 引言 在多线程并发编程中synchronized和Volatile都扮演着重要的角色,Volatile是轻量级的synchronized,它在多处理器开发中保证了共享变量的“可见性”。可见性的意思是当一个线程修改一个共享变量时,另外
本文向大家介绍深入理解Java IO的flush,包括了深入理解Java IO的flush的使用技巧和注意事项,需要的朋友参考一下 Java的IO是一个大知识点, 如果把它的知识点拆开来说的话估计能说一个星期,关于IO的体系可以看看下面这张图, 接下来我们从一段代码开始聊吧,先看看下面这段代码 代码中构造了一个缓冲流,然后往流里写入一个KB长度的数据,最后调用 flush()方法。 这是很简单的一
本文向大家介绍深入理解C预处理器,包括了深入理解C预处理器的使用技巧和注意事项,需要的朋友参考一下 C 预处理器不是编译器的组成部分,是编译过程中一个单独的步骤。C预处理器只是一个文本替换工具,它会指示编译器在实际编译之前完成所需的预处理。 所有的预处理器命令都是以井号(#)开头。它必须是第一个非空字符,为了增强可读性,预处理器指令应从第一列开始。 下表包含所有重要的预处理器指令: 指令 描述 #