JDK8系列之LongAdder解析

偏执的太偏执、 2022-11-16 13:50 25阅读 0赞

### JDK8系列之LongAdder解析 ###

*   *  前言
     *  准备
     *  源码解析
     *   *  longValue()
         *  increment()
     *  总结

## 前言 ##

JDK1.8时，`java.util.concurrent.atomic`包中提供了一个新的原子类：**`LongAdder`**。  
根据`Oracle`官方文档的介绍，`LongAdder`在高并发的场景下会比它的前辈————`AtomicLong`具有更好的性能，代价是`消耗更多的内存空间`。下面就来分析下它

## 准备 ##

**`Java Striped64`**  
`Striped64`是在java8中添加用来支持累加器的并发组件，它可以在并发环境下使用来做某种计数，`Striped64`的设计思路是在竞争激烈的时候尽量分散竞争，在实现上，Striped64维护了一个`base Count和一个Cell数组`，计数线程会`首先试图更新base变量`，如果成功则退出计数，否则会认为当前竞争是很激烈的，那么就会通过Cell数组来分散计数，Striped64根据线程来计算哈希，然后将不同的线程分散到不同的Cell数组的index上，然后这个线程的计数内容就会保存在该Cell的位置上面，基于这种设计，最后的总计数需要结合base以及散落在Cell数组中的计数内容。

## 源码解析 ##

首先看一下类的定义

public class LongAdder extends Striped64 implements Serializable

然后来看一下类的属性和方法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70]

这里让我困惑的一个问题是`LongAdder`中没有类似于`AtomicLong`中g`etAndIncrement()`或者`incrementAndGet()`这样的原子操作，所以只能通过`increment()`方法和`longValue()`方法的组合来实现更新和获取的动作，然而这样不能保证这个组合操作的原子性，猜想也许LongAdder就是不具备这样的机制吧。那么就主要看一下increment()和longValue()方法。

### longValue() ###

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

首先看一下获取值的`longValue()`方法，这里调用了`sum()`

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;
        }

通过上面的代码不难发现：`获取值的操作就是对base的值和cesll数组中值求和。`

这里出现了一个类`Cell`，这个类是`Striped64`类的静态内部类，因此当`Striped64`对象初始化时并不会连带将`Cell`类初始化，其源码如下

@sun.misc.Contended static final class Cell { 
            volatile long value;
            Cell(long x) {  value = x; }
            final boolean cas(long cmp, long val) { 
                return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val);
            }
    
            // Unsafe mechanics
            private static final sun.misc.Unsafe UNSAFE;
            private static final long valueOffset;
            static { 
                try { 
                    UNSAFE = sun.misc.Unsafe.getUnsafe();
                    Class<?> ak = Cell.class;
                    valueOffset = UNSAFE.objectFieldOffset
                        (ak.getDeclaredField("value"));
                } catch (Exception e) { 
                    throw new Error(e);
                }
            }
        }

这里有一个`@sun.misc.Contended`标识非常奇怪，查了资料发现是用于解决[伪共享（false sharing）][false sharing]问题的，这里就不深入讲解了。这个类只有一个`cas(long cmp, long val)`方法，做的事情也就是简单的CAS操作，接着来看一下`cells和base`的定义，这两个属性都是`Striped64`中的

transient volatile Cell[] cells;
    
        transient volatile long base;

可以看到全部都是`volatile`类型的，因此`都具有可见性`，并且可以推测会遇到并发的操作。  
回到`sum()`方法就很好理解了，这个方法返回的是base和cells数组中所有元素的和，这里的base像是一个初始值的作用，我们继续往下分析。

### increment() ###

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

接着分析`increment()`方法，可以看到该方法就是对`add(long x)`的封装，那么具体来分析一下这个方法

public void add(long x) { 
            Cell[] as; long b, v; int m; Cell a;
            if ((as = cells) != null || !casBase(b = base, b + x)) { 
                boolean uncontended = true;
                if (as == null || (m = as.length - 1) < 0 ||
                    (a = as[getProbe() & m]) == null ||
                    !(uncontended = a.cas(v = a.value, v + x)))
                    longAccumulate(x, null, uncontended);
            }
        }

这里重点是`casBase(b = base, b + x)`，来看一下它做了什么

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

由于此处的x为1，那么该方法就是对`Striped64`的`BASE`的值进行累加并返回是否成功，顺带一提这里的`BASE`是`base值所对应的内存偏移量`，所以`casBase(b = base, b + x)`就是`对base进行CAS操作`，执行成功的话操作就结束了。执行失败就是`并发量大`的时候，结合之前分析的`longValue()`方法，这里就可以得出一个结论——`当并发不大的时候只对base进行更新，获取值得时候当然也只从base获取即可，这个时候其实和AtomicLong的原理几乎一模一样`，看来区别就在于后面的分支，继续往下看。  
首先置标志位`uncontended为true`，从字面意思也可以看出来`uncontended`意思是没有竞争的。当casBase不成功则将进入add(long x)的if分支中，分支由四部分组成中间用||连接，必须全部满足才会结束方法执行，否则进入`longAccumulate(x, null, uncontended)`方法，这四部分分别为

1.  as == null，
2.  (m = as.length - 1) < 0
3.  (a = as\[getProbe() & m\]) == null
4.  !(uncontended = a.cas(v = a.value, v + x))  
    这里的四个条件其实并不是并列的，而是递进式的，1和2判断cells数组是否为空，3取cells数组中的任意一个元素a判断是否为空，4是对a进行cas操作并将执行结果赋值标志位uncontended。从这里可以给出第二个结论，当竞争激烈到一定程度无法对base进行累加操作时，会对cells数组中某个元素进行更新。

最后来看一下当上述条件有一个满足时调用的`longAccumulate(x, null, uncontended)`方法

final void longAccumulate(long x, LongBinaryOperator fn,
                                  boolean wasUncontended) { 
            int h;
            if ((h = getProbe()) == 0) { 
                ThreadLocalRandom.current(); // force initialization
                h = getProbe();  //返回当前线程的threadLocalRandomProbe值
                wasUncontended = true;
            }
            boolean collide = false;                // True if last slot nonempty
            for (;;) { 
                Cell[] as; Cell a; int n; long v;
                if ((as = cells) != null && (n = as.length) > 0) { 
                    if ((a = as[(n - 1) & h]) == null) { 
                        if (cellsBusy == 0) {        // cells数组中对应位置没有数据则插入新对象
                            Cell r = new Cell(x);   
                            if (cellsBusy == 0 && casCellsBusy()) { 
                                boolean created = false;
                                try {                // Recheck under lock
                                    Cell[] rs; int m, j;
                                    if ((rs = cells) != null &&
                                        (m = rs.length) > 0 &&
                                        rs[j = (m - 1) & h] == null) { 
                                        rs[j] = r;
                                        created = true;
                                    }
                                } finally { 
                                    cellsBusy = 0;
                                }
                                if (created)
                                    break;
                                continue;           // Slot is now non-empty
                            }
                        }
                        collide = false;
                    }
                    else if (!wasUncontended)       // CAS already known to fail
                        wasUncontended = true;      // Continue after rehash
                    else if (a.cas(v = a.value, ((fn == null) ? v + x :
                                                 fn.applyAsLong(v, x))))         //对该位置的cell元素进行累加
                        break;
                    else if (n >= NCPU || cells != as)
                        collide = false;            // At max size or stale //判断数组大小是否大于核数
                    else if (!collide)
                        collide = true;
                    else if (cellsBusy == 0 && casCellsBusy()) {          //对cells数组进行扩容，直接扩容为2倍
                        try { 
                            if (cells == as) {       // Expand table unless stale
                                Cell[] rs = new Cell[n << 1];
                                for (int i = 0; i < n; ++i)
                                    rs[i] = as[i];
                                cells = rs;
                            }
                        } finally { 
                            cellsBusy = 0;
                        }
                        collide = false;
                        continue;                   // Retry with expanded table
                    }
                    h = advanceProbe(h);
                }
                else if (cellsBusy == 0 && cells == as && casCellsBusy()) {   //cellsBusy这里是做为一个自旋锁来使用的
                    boolean init = false;
                    try {                            // 初始化cells数组大小为2
                        if (cells == as) { 
                            Cell[] rs = new Cell[2];
                            rs[h & 1] = new Cell(x);
                            cells = rs;
                            init = true;
                        }
                    } finally { 
                        cellsBusy = 0;
                    }
                    if (init)
                        break;
                }
                else if (casBase(v = base, ((fn == null) ? v + x :
                                            fn.applyAsLong(v, x))))      //对base进行CAS操作
                    break;                          // Fall back on using base
            }
        }

这个方法比较长，大致对几个关键点做了注释，该方法`主要是用一个死循环对cells数组中的元素进行操作，当要更新的位置的元素为空时插入新的cell元素，否则在该位置进行CAS的累加操作，如果CAS操作失败并且数组大小没有超过核数就扩容cells数组`。

## 总结 ##

`LongAdder`类与`AtomicLong`类的区别在于`高并发`时前者`将对单一变量的CAS操作分散为对数组cells中多个元素的CAS操作，取值时进行求和`；而在`并发较低时仅对base变量进行CAS操作，与AtomicLong类原理相同`。不得不说这种分布式的设计还是很巧妙的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70]: /images/20221022/9ce7fad029214d19bf704da7146fb412.png
[false sharing]: http://ifeve.com/falsesharing/