写点什么

我从 LongAdder 中窥探到了高并发的秘籍,上面只写了两个字...

用户头像
why技术
关注
发布于: 2020 年 07 月 16 日
我从LongAdder中窥探到了高并发的秘籍,上面只写了两个字...

荒腔走板

大家好,我是why。

时间过的真是快,一周又要结束了。那么,你比上周更博学了吗?先来一个简短的荒腔走板,给冰冷的技术文注入一丝色彩。

上面这图是我之前拼的一副拼图,一共划分了800块,背面无提示,难度极高,我花了两周的时间才拼完。

拼的是坛城,传说中佛祖居住生活的地方。

第一次知道这个名词是 2015 年,窝在寝室看纪录片《第三极》。

其中有一个片段讲的就是僧人为了某个节日用沙绘画坛城,他们的那种专注,虔诚,真挚深深的打动了我,当宏伟的坛城画完之后,他静静的等待节日的到来。

本以为节日当天众人会对坛城顶礼膜拜,而实际情况是大家手握一炷香,看着众僧人快速的摧毁坛城。

还没来得及仔细欣赏那复杂的美丽的图案,却又用扫把扫的干干净净。

扫把扫下去的那一瞬间,我的心受到了一种强烈的撞击:可以辛苦地拿起,也可以轻松地放下。

看到摧毁坛城的片段的时候,有一个弹幕是这样说的:

一切有为法,如梦幻泡影,如露亦如电,应作如是观。

这句话出自《金刚般若波罗蜜经》第三十二品,应化非真分。

因为之前翻阅过几次《金刚经》,看到这句话的时候我一下就想起了它。

因为读的时候我就觉得这句话很有哲理,但是也似懂非懂。所以印象比较深刻。

当他再次在坛城这个画面上以弹幕的形式展现在我的眼前的时候,我一下就懂了其中的哲理,不敢说大彻大悟,至少领悟一二。

观看摧毁坛城,这个色彩斑斓的世界变幻消失的过程,正常人的感受都是震撼,转而觉得可惜,心里久久不能平静。

但是僧人却风轻云淡的说:一切有为法,如梦幻泡影,如露亦如电,应作如是观。

好了,说回文章。

先说AtomicLong

关于 AtomicLong 我就不进行详细的介绍了。

先写这一小节的目的是预热一下,抛出一个问题,而这个问题是关于 CAS 操作和 volatile 关键字的。

我不知道源码为什么这样写,希望知道答案的朋友指点一二。

抱拳了,老铁。

为了顺利的抛出这个问题,我就得先用《Java并发编程的艺术》一书做引子,引出这个问题。

首先在书的第 2.3 章节《原子操作的实现原理》中介绍处理器是如何实现原子操作时提到了两点:

  • 使用总线锁保证原子性。

  • 使用缓存锁保证原子性。

所谓总线锁就是使用处理器提供一个提供的一个 LOCK # 信号,当一个处理器在总线上输出此信号时,其他处理器的请求将被阻塞住,那么该处理器可以独占共享内存。

总线锁保证原子性的操作有点简单粗暴直接了,导致总线锁定的开销比较大。

所以,目前处理器在某些场合下使用缓存锁来进行优化。

缓存锁的概念可以看一下书里面怎么写的:

其中提到的图 2-3 是这样的:

其实关键 Lock 前缀指令。

被 Lock 前缀指令操作的内存区域就会加锁,导致其他处理器不能同时访问。

而根据 IA-32 架构软件开发者手册可以知道,Lock 前缀的指令在多核处理器下会引发两件事情:

  • 将当前处理器缓存行的数据写回系统内存。

  • 这个写回内存的操作会使在其他 CPU 里缓存了该内存地址的数据无效。

对于 volatile 关键字,毫无疑问,我们是知道它是使用了 Lock 前缀指令的。

那么问题来了,JVM 的 CAS 操作使用了 Lock 前缀指令吗?

是的,使用了。

JVM 中的 CAS 操作使用的是处理器通过的 CMPXCHG 指令实现的。这也是一个 Lock 前缀指令。

好,接下来我们看一个方法:

java.util.concurrent.locks.AbstractQueuedLongSynchronizer#compareAndSetState

这个方法位于 AQS 包里面,就是一个 CAS 的操作。现在只需要关心我框起来的部分。

英文部分翻译过来是:这个操作具有 volatile 读和写的内存语言。

而这个操作是什么操作?

就是 344 行 unsafe 的 compareAndSwapLong 操作,这个方法是一个 native 方法。

public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

为什么这个操作具有 volatile 读和写的内存语言呢?

书里面是这样写的:

这个本地方法的最终实现在 openjdk 的如下位置:
openjdk-7-fcs-src-b147- 27_jun_2011\openjdk\hotspot\src\os_cpu\windows_x86\vm\atomic_windows_x86.inline.hpp(对应于Windows操作系统,X86处理器)




intel 的手册对 Lock 前缀的说明如下。

  • 确保对内存的读-改-写操作原子执行。在 Pentium 及 Pentium 之前的处理器中,带有 Lock 前缀的指令在执行期间会锁住总线,使得其他处理器暂时无法通过总线访问内存。很显然,这会带来昂贵的开销。从Pentium 4、Intel Xeon及P6处理器开始,Intel使用缓存锁定(Cache Locking) 来保证指令执行的原子性。缓存锁定将大大降低lock前缀指令的执行开销。

  • 禁止该指令,与之前和之后的读和写指令重排序。

  • 把写缓冲区中的所有数据刷新到内存中。

上面的第2点和第3点所具有的内存屏障效果,足以同时实现 volatile 读和volatile 写的内存语义。

好,如果你说你对书上的内容存疑。那么我带大家再看看官方文档:

https://docs.oracle.com/javase/8/docs/api/

我框起来的部分:

compareAndSet 和所有其他的诸如 getAndIncrement 这种读然后更新的操作拥有和 volatile 读、写一样的内存语义。

原因就是用的到了 Lock 指令。

好,到这里我们可以得出结论了:

compareAndSet 同时具有volatile读和volatile写的内存语义。

那么问题就来了!

这个操作,在 AtomicLong 里面也有调用:

而 AtomicLong 里面的 value 又是被 volatile 修饰了的:

请问:为什么 compareAndSwapLong 操作已经同时具有 volatile 读和 volatile 写的内存语义了,其操作的 value 还需要被 volatile 修饰呢?

这个问题也是一个朋友抛出来探讨的,探讨的结果是,我们都不知道为什么:

我猜测会不会是由于操作系统不同而不同。在 x86 上面运行是这样,其他的操作系统就不一定了,但是没有证据。

希望知道为什么这样做的朋友能指点一下。

(后来我发现有一个单独的set方法,而这个set方法是没有cas加持的。所以volatile的作用是这样体现出现来的吧)

好,那么前面说到 CAS ,那么一个经典的面试题就来了:

请问,CAS 实现原子操作有哪些问题呢?

  • ABA问题。

  • 循环时间开销大。

  • 只能保证一个共享变量的原子操作。

如果上面这三点你不知道,或者你说不明白,那我建议你看完本文后一定去了解一下,属于面试常问系列。

我主要说说这个循环时间开销大的问题。自旋 CAS 如果长时间不成功,就会对 CPU 带来比较大的执行开销。

而回答这个问题的朋友,大多数举例的时候都会说: “AtomicLong 就是基于自旋 CAS 做的,会带来一定的性能问题。巴拉巴拉......”

而我作为面试官的时候只是微笑着看着你,让你错以为自己答的很完美。

我知道你为什么这样答,因为你看了几篇博客,刷了刷常见面试题,那里面都是这样写的 :AtomicLong 就是基于自旋 CAS 做的。

但是,朋友,你可以这样说,但是回答不完美。这题得分别从 JDK 7 和 JDK 8 去答:

JDK 7 的 AtomicLong 是基于自旋 CAS 做的,比如下面这个方法:

while(true) 就是自旋,自旋里面纯粹依赖于 compareAndSet 方法:

这个方法里面调用的 native 的 comareAndSwapLong 方法,对应的 Lock 前缀指令就是我们前面说到的 cmpxchg。

而在 JDK 8 里面 AtomicLong 里面的一些方法也是自旋,但是就不仅仅依赖于 cmpxchg 指令做了,比如还是上面这个方法:

可以看到这里面还是有一个 do-while 的循环,还是调用的 compareAndSwapLong 方法:

这个方法对应的 Lock 前缀指令是我们前面提到过的 xadd 指令。

从 Java 代码的角度来看,都是自旋,都是 compareAndSwapLong 方法。没有什么差异。

但是从这篇 oracle 官网的文章,我们可以窥见 JDK 8 在 x86 平台上对 compareAndSwapLong 方法做了一些操作,使用了 xadd 汇编指令代替 CAS 操作。

xadd 指令是 fetch and add。

cmpxchg 指令是 compare and swap。

xadd 指令的性能是优于 cmpxchg 指令的。

具体可以看看这篇 oracle 官网的文章:

https://blogs.oracle.com/dave/atomic-fetch-and-add-vs-compare-and-swap

文章下面的评论,可以多注意一下,我截取其中两个,大家品一品:

然后是这个:

总之就是:这篇文章说的有道理,我们(Dave and Doug)也在思考这个问题。所以我们会在 JIT 上面搞事情,在 x86 平台上把 CAS 操作替换为 LOCK:XADD 指令。

所以,JDK 8 之后的 AtomicLong 里面的方法都是经过改良后, xadd+cmpxchg 双重加持的方法。

另外需要注意的是,我怕有的朋友懵逼,专门多提一嘴:CAS 是指一次比较并交换的过程,成功了就返回 true,失败了则返回 false,强调的是一次。而自旋 CAS 是在死循环里面进行比较并交换,只要不返回 true 就一直循环。

所以,不要一提到 CAS 就说循环时间开销大。前面记得加上“自旋”和“竞争大”两个条件。

至于 JDK 8 使用 xadd 汇编指令代替 CAS 操作的是否真的是性能更好了,可以看看这篇 oracle 官网的文章:

https://blogs.oracle.com/dave/atomic-fetch-and-add-vs-compare-and-swap

文章下面的评论,可以多注意一下,我截取其中一个,大家品一品:

经过我们前面的分析,AtomicLong 从 JDK 7 到 JDK 8 是有一定程度上的性能优化的,但是改动并不大。

还是存在一个问题:虽然它可以实现原子性的增减操作,但是当竞争非常大的时候,被操作的这个 value 就是一个热点数据,所有线程都要去对其进行争抢,导致并发修改时冲突很大。

所以,归根到底它的主要问题还是出在共享热点数据上。

为了解决这个问题,Doug Lea 在 JDK 8 里面引入了 LongAdder 类。

更加牛逼的LongAdder

大家先看一下官网上的介绍:

上面的截图一共两段话,是对 LongAdder 的简介,我给大家翻译并解读一下。

首先第一段:当有多线程竞争的情况下,有个叫做变量集合(set of variables)的东西会动态的增加,以减少竞争。sum() 方法返回的是某个时刻的这些变量的总和。

所以,我们知道了它的返回值,不论是 sum() 方法还是 longValue() 方法,都是那个时刻的,不是一个准确的值。

意思就是你拿到这个值的那一刻,这个值其实已经变了。

这点是非常重要的,为什么会是这样呢?

我们对比一下 AtomicLong 和 LongAdder 的自增方法就可以知道了:

AtomicLong 的自增是有返回值的,就是一个这次调用之后的准确的值,这是一个原子性的操作。

LongAdder 的自增是没有返回值的,你要获取当前值的时候,只能调用 sum 方法。

你想这个操作:先自增,再获取值,这就不是原子操作了。

所以,当多线程并发调用的时候,sum 方法返回的值必定不是一个准确的值。除非你加锁。

该方法上的说明也是这样的:

至于为什么不能返回一个准确的值,这就是和它的设计相关了,这点放在后面去说。

然后第二段:当在多线程的情况下对一个共享数据进行更新(写)操作,比如实现一些统计信息类的需求,LongAdder 的表现比它的老大哥 AtomicLong 表现的更好。在并发不高的时候,两个类都差不多。但是高并发时 LongAdder 的吞吐量明显高一点,它也占用更多的空间。这是一种空间换时间的思想。

这段话其实是接着第一段话在进行描述的。

因为它在多线程并发情况下,没有一个准确的返回值,所以当你需要根据返回值去搞事情的时候,你就要仔细思考思考,这个返回值你是要精准的,还是大概的统计类的数据就行。

比如说,如果你是用来做序号生成器,所以你需要一个准确的返回值,那么还是用 AtomicLong 更加合适

如果你是用来做计数器,这种写多读少的场景。比如接口访问次数的统计类需求,不需要时时刻刻的返回一个准确的值,那就上 LongAdder 吧

总之,AtomicLong 是可以保证每次都有准确值,而 LongAdder 是可以保证最终数据是准确的。高并发的场景下 LongAdder 的写性能比 AtomicLong 高。

接下来探讨三个问题:

  • LongAdder 是怎么解决多线程操作热点 value 导致并发修改冲突很大这个问题的?

  • 为什么高并发场景下 LongAdder 的 sum 方法不能返回一个准确的值?

  • 为什么高并发场景下 LongAdder 的写性能比 AtomicLong 高?

先带大家看个图片,看不懂没有关系,先有个大概的印象:

接下来我们就去探索源码,源码之下无秘密。

从源码我们可以看到 add 方法是关键:

里面有 cells 、base 这样的变量,所以在解释 add 方法之前,我们先看一下 这几个成员变量。

这几个变量是 Striped64 里面的。

LongAdder 是 Striped64 的子类:

其中的四个变量如下:

  • NCPU:cpu 的个数,用来决定 cells 数组的大小。

  • cells:一个数组,当不为 null 的时候大小是 2 的次幂。里面放的是 cell 对象。

  • base : 基数值,当没有竞争的时候直接把值累加到 base 里面。还有一个作用就是在 cells 初始化时,由于 cells 只能初始化一次,所以其他竞争初始化操作失败线程会把值累加到 base 里面。

  • cellsBusy:当 cells 在扩容或者初始化的时候的锁标识。

之前,文档里面说的 set of variables 就是这里的 cells。

好了,我们再回到 add 方法里面:

cells 没有被初始化过,说明是第一次调用或者竞争不大,导致 CAS 操作每次都是成功的。

casBase 方法就是进行 CAS 操作。

当由于竞争激烈导致 casBase 方法返回了 false 后,进入 if 分支判断。

这个 if 分子判断有 4 个条件,做了 3 种情况的判断

  • 标号为 ① 的地方是再次判断 cells 数组是否为 null 或者 size 为 0 。as 就是 cells 数组。

  • 标号为 ② 的地方是判断当前线程对 cells 数组大小取模后的值,在 cells 数组里面是否能取到 cell 对象。

  • 标号为 ③ 的地方是对取到的 cell 对象进行 CAS 操作是否能成功。

这三个操作的含义为:当 cells 数组里面有东西,并且通过 getProbe() & m算出来的值,在 cells 数组里面能取到东西(cell)时,就再次对取到的 cell 对象进行 CAS 操作。

如果不满足上面的条件,则进入 longAccumulate 函数。

这个方法主要是对 cells 数组进行操作,你想一个数组它可以有三个状态:未初始化、初始化中、已初始化,所以下面就是对这三种状态的分别处理:

  • 标号为 ① 的地方是 cells 已经初始化过了,那么这个里面可以进行在 cell 里面累加的操作,或者扩容的操作。

  • 标号为 ② 的地方是 cells 没有初始化,也还没有被加锁,那就对 cellsBusy 标识进行 CAS 操作,尝试加锁。加锁成功了就可以在这里面进行一些初始化的事情。

  • 标号为 ③ 的地方是 cells 正在进行初始化,这个时候就在 base 基数上进行 CAS 的累加操作。

上面三步是在一个死循环里面的。

所以如果 cells 还没有进行初始化,由于有锁的标志位,所以就算并发非常大的时候一定只有一个线程去做初始化 cells 的操作,然后对 cells 进行初始化或者扩容的时候,其他线程的值就在 base 上进行累加操作。

上面就是 sum 方法的工作过程。

感受到了吗,其实这就是一个分段操作的思想,不知道你有没有想到 ConcurrentHashMap,也不奇怪,毕竟这两个东西都是 Doug Lea 写的。

然后再补充说明一下,cells 的初始化大小为 2:

cells 的最大值为 CPU 核数:

cell 是被 Contended 注解修饰了,为了解决伪共享的问题:

说起伪共享,我想起了之前的《一个困扰我122天的技术问题,我好像知道答案了》这篇文章中提到的一个猜想:

后来,我也用这个注解去解决伪共享的问题了,可惜最终的实验结果表明不是这个原因。

那篇文章发布后有很多朋友给我反馈他们的看法,而更多的是在这条路上发现了更多更多的玄学问题,但是最终这些问题的背后都指向了同一个东西:JIT。

扯远了,说回本文的这个 LongAdder。

总的来说,就是当没有冲突的时候 LongAdder 表现的和 AtomicLong 一样。当有冲突的时候,才是 LongAdder 表现的时候,然后我们再回去看这个图,就能明白怎么回事了:

好了,现在我们回到前面提出的三个问题:

  • LongAdder 是怎么解决多线程操作热点 value 导致并发修改冲突很大这个问题的?

  • 为什么高并发场景下 LongAdder 的 sum 方法不能返回一个准确的值?

  • 为什么高并发场景下 LongAdder 的写性能比 AtomicLong 高?

它们其实是一个问题。

因为 LongAdder 把热点 value 拆分了,放到了各个 cell 里面去操作。这样就相当于把冲突分散到了 cell 里面。所以解决了并发修改冲突很大这个问题。

当发生冲突时 sum= base+cells。高并发的情况下当你获取 sum 的时候,cells 极有可能正在被其他的线程改变。一个在高并发场景下实时变化的值,你要它怎么给你个准确值?当然,你也可以通过加锁操作拿到当前的一个准确值,但是这种场景你还用啥 LongAdder,是 AtomicLong 不香了吗?

为什么高并发场景下 LongAdder 的写性能比 AtomicLong 高?

你发动你的小脑壳想一想,朋友。

AtomicLong 不管有没有冲突,它写的都是一个共享的 value,有冲突的时候它就在自旋。

LongAdder 没有冲突的时候表现的和 AtomicLong 一样,有冲突的时候就把冲突分散到各个 cell 里面了,冲突分散了,写的当然更快了。

一点思考

本文的题目是《我从LongAdder中窥探到了高并发的秘籍,上面就写了两个字......》。

那么这两个字是什么呢?

就是拆分。我浅显的觉得分布式、高并发都是基于拆分思想的。

本文的 LongAdder 就不说了。

微服务化、分库分表、读写分离......这些东西都是在拆分,把集中的压力分散开来。

我们常常说性能不行了,那就堆机器解决,这就是在做拆分。

当然,拆分了带来好处的同时也是有一定的问题的。

比如老大难的分布式事务、数据聚合查询等需求。

举一个我遇到过的例子吧。

在写这篇文章之前,我看了 LongAdder 源码,了解到它这样的结构后,知道了它和 AtomicLong 之间的差异后,我想起了之前做过的一个需求。

就是账户服务,有个大商户的账户是一个热点账户,交易非常的频繁。

这个账户上的金额就相当于是一个共享的热点数据。

我们当时的做法是把这个账户拆分为多个影子账户,这样就把热点账户拆分成了多个影子账户,压力就分摊了。

其实这个思想和 LongAdder 是一脉相承的。

这个场景下拆分带来的问题是什么呢?

其中一个问题就是这个账户的总余额是多个影子账户之和,而每个影子账户上的余额是时刻在变化的,所以我们不能保证余额是一个实时准确的值。

但是商户不关心这个呀。他只关心上日余额是准确的,每日对账都能对上就行了。

我们在满足需求的同时,性能还上去了。

还有一个简单的思考是如果我们把“实现原子操作进行加减”这句话当做一个需求。

我个人拙见是这样的,AtomicLong 类就是实现了这个需求,交付出去后,它能用,能正常工作,而且还附送了一个功能是每次都给你返回一个准确的值。

而 LongAdder 就是更加优雅的实现了这个需求,它是在原有的基础上进行了迭代开发,功能还是能一样的实现,没有附加功能,但是针对某些场景来说,更好用了。

它们传递给我的思想不是我们常说的:先上,能跑就行,后期再迭代。

而是:它确实能跑,但是还有更加快,更加优雅的实现方式,我们可以实现它。

这是我们需要学习的地方。

最后说两句(求关注)

才疏学浅,难免会有纰漏,如果你发现了错误的地方,还请你留言指出来,我对其加以修改。

感谢您的阅读,我坚持原创,十分欢迎并感谢您的关注。

我是 why,一个被代码耽误的文学创作者,不是大佬,但是喜欢分享,是一个又暖又有料的四川好男人。



发布于: 2020 年 07 月 16 日阅读数: 57
用户头像

why技术

关注

用匠心敲代码 2019.10.16 加入

公众号:why技术&why不止技术的号主。在这里我会分享一些java技术相关的知识,用匠心敲代码,对每一行代码负责。感谢你的关注,愿你我共同进步。

评论

发布
暂无评论
我从LongAdder中窥探到了高并发的秘籍,上面只写了两个字...