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

终有救赎

发布于 2023-10-16 10:37:39

1330

发布于 2023-10-16 10:37:39

文章被收录于专栏：多线程多线程

老王：小陈啊，上一章我们讲解了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的利用率，降低了并发的性能。

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

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

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

小陈：哪能啊，嘿嘿，都是老王你教的好啊......

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

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

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

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

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

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

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

如下图所示：

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

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

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

老王：上面的图看懂了没？

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

同时每个窗口内部有一个访客计数器，窗口每次接待完一个访客，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）使用了备用窗口列表，相当于将不同的用户派遣到不同的窗口，减少了竞争，这样并发性能自然就提升上去了。

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

这个时候如果银行经理想要知道办事大厅的总访问人数，只需要将多个窗口（多个段）内的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方法源码，经过我加上的一些注释，你能拿看懂不？

小陈：看不懂......

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

老王：小陈啊，上面就是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;
}

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

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

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

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

小陈：好的老王，我们下一章见。

ThreadPoolExecutor execute执行流程？怎么进行任务提交的？addWorker方法干了啥？什么是workder？
ThreadPoolExecutor execute执行流程？何时将任务提交到阻塞队列？阻塞队列满会发生什么？
ThreadPoolExecutor 中的Worker是如何执行提交到线程池的任务的？多余Worker怎么在超出空闲时间后被干掉的？
ThreadPoolExecutor shutdown、shutdownNow内部核心流程
再回头看看为啥不推荐Executors提供几种线程池？
ThreadPoolExecutor线程池篇总结

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2023-10-12，如有侵权请联系 cloudcommunity@tencent.com 删除

atomic

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度