19.Atomic系列之LongAdder的底层原理(分段锁提升并发性能)

简介: 19.Atomic系列之LongAdder的底层原理(分段锁提升并发性能)

老王:小陈啊,上一章我们讲解了cas的缺陷无法同时更新多个变量、以及ABA的问题。以及如果使用AtomicReference解决同时更新多个变量,如果使用AtomicStampedReference解决ABA的问题,这些都还记得不?

小陈:嗯嗯,记得的。

老王:那好,这一章节我们就来讲解CAS带来的另外一个问题在并发激烈的时候,产生大量的自旋,空耗CPU的问题,以及怎么使用分段锁机制解决这个问题的,我们已LongAdder这个原子类来举例讲解。

小陈:嗯嗯,洗耳恭听......

AtomicInteger的缺陷,并发竞争激烈时导致大量线程自旋

老王:小陈啊,在说LongAdder之前,我先问题一个问题,为什么要设计出LongAdder?

小陈:这个啊,我看有些人说在并发非常高的时候,使用AtomicInteger、AtomicLong底层的CAS操作竞争非常激烈,会导致大量线程CAS失败而不断自旋,耗费CPU的性能。

老王:哦,那你来说说并发非常高的时候,AtomicInteger、AtomicLong为什么会导致的大量自旋?

小陈:AtomicInteger、AtomicLong的底层原理和实现方式基本一致,只不过一个是int类型一个是long类型,我就拿我们之前讨论过的AtomicInteger来分析一下

我记得AtomicInteger的incrementAndGet方法的底层源码是这样的:


public final int incrementAndGet() {
    return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}

底层调用了unsafe类的getAndAddInt方法,源码如下:


public final int getAndAddInt(Object o, long valueOffset, int x) {
    int expected;
    // CAS的失败的线程,会不断在do... while循环里重试,知道成功为止
    do {
        expected = this.getIntVolatile(o, valueOffset);
        // while条件判断这里的compareAndSwapInt每次只有一个线程成功
    } while(!this.compareAndSwapInt(o, valueOffset, expected, expected + x));
    return expected;
}

(1)我们看一下上述 do...while 循环假设有10000个线程并发的操作,由于CAS操作能保证原子性(之前的文章讲过哦,CAS的底层原理)一个时刻只会有一个线程执行compareAndSwapInt方法成功

(2)失败的另外9999个线程进入下一次循环然后成功一个剩下9998个进入下一层循环....,这种方式啊,竞争太过激烈导致大量线程在循环里面自旋重试,此时是不会释放CPU资源的,大大降低CPU的利用率,降低了并发的性能。

小陈:我再画一副图补充一下:

image.png

小陈:上面就是我理解竞争非常激烈的时候大量线程在do...while循环里面自旋重试,导致非常消耗CPU资源,降低了并发的性能。

老王:很好很好,理解得非常不错,看来小陈你对之前讲解的AtomicInteger理解很深入了,哈哈,不愧是我亲自带出来的......

小陈:哪能啊,嘿嘿,都是老王你教的好啊......

老王:小陈啊,既然你知道了AtomicInteger在并发竞争非常激烈会导致大量线程自旋,那你说说LongAdder在设计层次是怎么解决这个问题的?

小陈:额,我印象中LongAdder采用分段锁的思想,去减少并发竞争的;我打个比方还是上面10000个线程并发操作,但是LongAdder内部可能有10个锁不同的线程可能去竞争不同的锁,平均下来可能是1000个线程竞争1个锁这样并发性能这样比起AtomicInteger可能就提升了10倍

老王:你说的大概准确,但是你能说说什么是分段锁吗?LongAdder底层又是怎么实现分段锁的?

小陈:额,这个,我就不太懂了,还是老王你来说吧......

老王:好,那我先给你讲讲什么是分段锁吧,讲完分段锁之后再给讲LongAdder是怎么实现分段锁的

老王:下面我以银行办事大厅多窗口机制来给你将什么是分段锁

银行办事大厅多窗口讲解分段锁

如下图所示:

(1)银行大厅有一个常规窗口一堆备用窗口每个窗口有个计数器value记录了当前窗口的访客人数

(2)当人数很少的时候,不存在竞争,通常办事大厅只启用常规窗口就足以应对了

(3)当银行某个经理想知道总的访客人数的时候,需要将所有窗口的value访问人数累加就可以了

image.png

老王:上面的图看懂了没?

小陈:看懂了,也就是说一个银行办事大厅,处理访客的请求。当访客人数很少,比如一两个的时候只开放常规窗口就可以了。

同时每个窗口内部有一个访客计数器,窗口每次接待完一个访客,value就加1,当银行经理想看一下整个办事大厅的来访总人数的时候,就把所有的窗口的访客计数器value累加就可以了。

老王:没错,就是这样。下面再给你说说,当访客非常多的时候,怎么使用备用窗口减少竞争的?

多窗口处理减少竞争

(1)在访客非常多的情况下,只开启常规窗口是不行的,由于一个窗口同一时间只能处理一个访客的请求,并发竞争非常激烈(这个就是上述说的AtomicInteger的缺陷,所有人竞争通过一个窗口

(2)所以这个时候启用备用窗口假如说有4个备用窗口,分别为A、B、C、D窗口每个用户自己有一个id,比如用户2(id=4)来了之后看到常规窗口有人了就会根据 id % 备用窗口大小 =》 4 % 4 = 0,就会派到第一个备用窗口,也就是窗口A

(3)同时并发非常激烈的时候,同一个备用窗口也是存在竞争的,比如用户3(id=5)、用户6(id=9)根据 id % 备用窗口大小 = 2,所以都竞争备用窗口B;用户4(id=6)和用户7(id=10)同样会竞争备用窗口C

(4)使用了备用窗口列表,相当于将不同的用户派遣到不同的窗口减少了竞争,这样并发性能自然就提升上去了。

image.png

老王:上面的这种机制啊,其实就是类似将锁拆成锁多个段;其中每个窗口就是一段锁,只有被派到同一个窗口的用户才会存在竞争,使用分段锁大大减少了竞争,提升了并发性能

这个时候如果银行经理想要知道办事大厅的总访问人数,只需要将多个窗口(多个段)内的value人数累加起来就可以了

老王:小陈啊,上面通过办事大厅多窗口(多段)机制讲解分段锁,你听懂了没

小陈:牛逼啊老王,你这么讲解我完全听得懂。

老王:好了,下面再给你讲讲LongAdder的底层原理怎么使用分段锁优化并发性能的?

LongAdder属性

老王:首先啊,我给你说LongAdder之前得给你介绍一下Striped64这个类,Striped64这个类是分段锁的基础,实现分段锁的功能,而LongAdder继承Striped64,只是在Striped64基础之上做了简单的封装而已。

首先介绍一下LongAdder继承Striped64之后内部有哪些属性

Cell单元(窗口)

Cell其实就是我们上面说窗口,每个窗口内部有一个value计数器


Cell {
    // 计数器,当前访问人数多少
    volatile long value;
    // 构造函数
    Cell(long x) { value = x; }
    // CAS竞争同一个窗口,可能多个用户CAS竞争这个窗口 
    final boolean cas(long cmp, long val) {
        return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val);
    }
}

基础窗口

基础窗口直接一个base变量表示


transient volatile long base;

争抢基础窗口的方法,casBase底层源码,直接cas修改base变量在内存的值


final boolean casBase(long cmp, long val) {
    return UNSAFE.compareAndSwapLong(this, BASE, cmp, val);
}

用户id生成方法

这里就是通过线程id,经过系列运算得到用户id


static final int getProbe() {
    return UNSAFE.getInt(Thread.currentThread(), PROBE);
}

LongAdder内部源码分析

老王:上面知道了LongAdder内部有用哪些属性,接下来我们看一下LongAdder内部的源码。

老王:我们首先看下LongAdder提供的加减方法:


public void increment() {
    add(1L);
}
public void decrement() {
    add(-1L);
}

我们看到,increment和decrement方法底层调用的都是add方法,只不过传入的是正数和负数的区别而已。

老王:看一下设计极为简洁和精妙的add方法:


public void add(long x) {
    // as就类似我们上述说的备用窗口列表
    Cell[] as;
    // 这里的b就是常规窗口的值,v是你被分派到的那个窗口的value值
    long b, v;
    // m是备用窗口的长度-1,
    // 上面我们讲过getProbe()方法就是获取用户id的方法
    // getProbe() & 其实就是 用户id % 窗口总数,窗口分派的算法
    int m;
    // a就是你被派遣到的那个窗口
    Cell a;
    // 1.首先如果cells==null,说明备用窗口没有开放,
    // 全都执行casBase争抢常规窗口,cas成功则争抢成功,然后办完事就退出了
    // 如果争抢失败 casBase == false,则会进入if代码内重试
    // 2. 如果cells != null,说明备用窗口开发了,不用去争抢常规窗口了,
    // 直接就进入争抢备用窗口
    if ((as = cells) != null || !casBase(b = base, b + x)) {
        boolean uncontended = true;
        // 3. as == null || as.length - 1 < 0 说明备用窗口列表尚未开放
        if (as == null || (m = as.length - 1) < 0 ||
            // 4. as[getProbe() & m] 是你被派遣到的那个备用窗口
            // (a = as[getProbe() & m]) == null 你被派遣到的那个备用窗口还没有人来
            (a = as[getProbe() & m]) == null ||
            // 5. a.cas() 就是你被分派到窗口a后,去尝试争抢窗口a的权限
            // 如果 uncontented就是你争抢的结果,如果!uncnotented == true,说明你争抢失败了
            !(uncontended = a.cas(v = a.value, v + x)))
            // 相当于上面操作都失败之后的一种兜底方案
            longAccumulate(x, null, uncontended);
    }
}

老王:小陈啊,上面的LongAdder原子类的add方法源码,经过我加上的一些注释,你能拿看懂不?

小陈:看不懂......

老王:那这样,我再画个流程图,结合代码给你讲解一下:

image.png

老王:小陈啊,上面就是LongAdder底层执行加减运算的流程图了。

小陈:哇撒,这个有点小复杂啊,这几行代码里面包含这么多的操作啊......,我要多看几遍才行啊。(一次看不懂的童鞋,记得多看几遍哈)

老王:是啊,写LongAdder这哥们看来境界十分高。

老王:按照我们的修炼方式,你一点点的从《筑基》、《练气》、《结丹》....,你可以慢慢提高水平,看懂他们的代码,了解他们设计的思想,前提是你要好好学啊。

老王:好了,小陈,再给十分钟的时间,好好消化一下上面我们讲解下面的内容......

小陈:好的老王,遵命......(十分钟之后......)

老王:小陈啊,上面讨论的LongAdder执行add操作的流程全部弄懂了没?

小陈:longAccumulate的那个底层兜底的实现机制(下一章节讲解),我都基本搞明白了:

(1)大概就是备用窗口没有开放的时候,所有人都来竞争常规窗口

(2)备用窗口列表开放之后,根据算法看自己被派遣到哪个窗口,比如说窗口a

(3)然后看一下自己被派遣到的窗口a有没有人在工作没有那就只等进入兜底方案等人来了才能处理了

(4)如果窗口a有人,这个时候就去竞争窗口a的权限;如果成功了,说明处理了自己的请求,那我就完事了

(5)如果去窗口a竞争失败了,则说明别人比你先一步获取了窗口a的权限,这个时候你只等进入兜底方案等待了。

老王:没错没错,总结得很好,看来小陈你随着境界的提升啊,理解越来越深入了,目前我看你现在的并发实力,已经快《结丹》了,继续保持下去...

小陈:哈哈,这都是老王你的功劳啊,都是你教的好......

老王:哈哈,好了,互吹结束;我们接着继续。

LongAdder中获取总数源码分析

再来看下LongAdder的longValue和intValue的底层源码:

这个就是相当于获取当前办事大厅来访总人数了,底层都是调用sum方法


public long longValue() {
    return sum();
}
public int intValue() {
    return (int)sum();
}

再来看下sum() 方法的源码是怎么统计所有的来访人数的:


public long sum() {
    // as = cells 表示备用窗口列表
    Cell[] as = cells;
    Cell a;
    // base,也就是常规窗口的访客人数
    long sum = base;
    if (as != null) {
        // 这里就是将 常规窗口访客 + 所有备用窗口访客 就是总访客
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;
        }
    }
    return sum;
}

老王:这个底层就很简单了,就是遍历所有的窗口,将他们的访问人数加起来就是了:

image.png

老王:上面的获取总数的sum方法对你来说应该不难吧,小陈。

小陈:哈哈,这个就很简单了,只是常规的加和操作而已......

老王:好了,今天我们分析LongAdder的底层和源码就到了这里,我们明天分析一下Strimed64的分段加锁实现机制也就是我们今天图里面的longAccumulate兜底机制。

小陈:好的老王,我们下一章见。



相关文章
|
6月前
|
安全
ConcurrentHashMap1.7分段锁原理
ConcurrentHashMap1.7分段锁原理
44 0
|
4月前
|
存储 安全 容器
【多线程面试题二十一】、 分段锁是怎么实现的?
这篇文章解释了分段锁的概念和实现方式,通过将数据分成多个段并在每段数据上使用独立锁,从而降低锁竞争,提高并发访问效率,举例说明了`ConcurrentHashMap`如何使用分段锁技术来实现高并发和线程安全。
【多线程面试题二十一】、 分段锁是怎么实现的?
|
7月前
|
安全 Java 程序员
【Java多线程】面试常考——锁策略、synchronized的锁升级优化过程以及CAS(Compare and swap)
【Java多线程】面试常考——锁策略、synchronized的锁升级优化过程以及CAS(Compare and swap)
69 0
|
7月前
|
存储 安全 Java
多线程编程常见面试题讲解(锁策略,CAS策略,synchronized原理,JUC组件,集合类)(下)
多线程编程常见面试题讲解(锁策略,CAS策略,synchronized原理,JUC组件,集合类)(下)
64 0
|
7月前
|
存储 安全 Java
多线程编程常见面试题讲解(锁策略,CAS策略,synchronized原理,JUC组件,集合类)(上)
多线程编程常见面试题讲解(锁策略,CAS策略,synchronized原理,JUC组件,集合类)
77 0
|
7月前
|
算法 安全 Java
20.Atmoic系列Strimped64分段锁底层实现源码剖析
20.Atmoic系列Strimped64分段锁底层实现源码剖析
31 0
20.Atmoic系列Strimped64分段锁底层实现源码剖析
|
缓存 安全 Java
【Java基础】线程的原子性、可见性、有序性及线程安全知识整理
一个操作或者多个操作,要么全部执行,并且执行的过程不会被打断, 要么就全部不执行(一个操作是不可被分割的)。
|
存储 算法 小程序
通过 JDK 原子并发类 AtomicInteger 彻底掌握 CAS 无锁算法
通过 JDK 原子并发类 AtomicInteger 彻底掌握 CAS 无锁算法
225 0
通过 JDK 原子并发类 AtomicInteger 彻底掌握 CAS 无锁算法
|
存储 安全 算法
Java并发 --- 线程安全、并发特性等
Java并发 --- 线程安全、并发特性等
Java并发 --- 线程安全、并发特性等
|
缓存 Java
Java 并发学习笔记(一)——原子性、可见性、有序性问题
计算机的 CPU、内存、I/O 设备的速度一直存在较大的差异,依次是 CPU > 内存 > I/O 设备,为了权衡这三者的速度差异,主要提出了三种解决办法: • CPU 增加了缓存,均衡和内存的速度差异 • 发明了进程、线程,分时复用 CPU,提高 CPU 的使用效率 • 编译指令优化,更好的利用缓存 三种解决办法虽然有效,但是也带来了另外的三个问题,分别就是并发 bug 产生的源头。
133 0
Java 并发学习笔记(一)——原子性、可见性、有序性问题