Striped64与LongAdder

从JDK 8开始，针对Long型的原子操作，Java又提供了LongAdder、LongAccumulator；针对Double类型，Java提供了DoubleAdder、DoubleAccumulator。Striped64相关的类的继承层次如图2-2所示。

读者会有一个疑问，既然已有了AtomicLong，为什么还要提供LongAdder？并且还提供了LongAccumulator？

2.6.1 LongAdder原理

AtomicLong内部是一个volatile long型变量，由多个线程对这个变量进行CAS操作。多个线程同时对一个变量进行CAS操作，在高并发的场景下仍不够快，如果再要提高性能，该怎么做呢？

把一个变量拆成多份，变为多个变量，有些类似于 ConcurrentHashMap 的分段锁的例子。如图2-3所示，把一个Long型拆成一个base变量外加多个Cell，每个Cell包装了一个Long型变量。当多个线程并发累加的时候，如果并发度低，就直接加到base变量上；如果并发度高，冲突大，平摊到这些Cell上。在最后取值的时候，再把base和这些Cell求sum运算。

以LongAdder的sum（）函数为例，如下所示。

由于无论是long，还是double，都是64位的。但因为没有double型的CAS操作，所以是通过把double型转化成long型来实现的。所以，上面的base和cell[]变量，是位于基类Striped64当中的。英文Striped意为“条带”，也就是分片。

2.6.2 最终一致性

在sum求和函数中，并没有对cells[]数组加锁。也就是说，一边有线程对其执行求和操作，一边还有线程修改数组里的值，也就是最终一致性，而不是强一致性。这也类似于ConcurrentHashMap 中的 clear（）函数，一边执行清空操作，一边还有线程放入数据，clear（）函数调用完毕后再读取，hash map里面可能还有元素。因此，在LongAdder开篇的注释中，把它和AtomicLong 的使用场景做了比较。它适合高并发的统计场景，而不适合要对某个 Long 型变量进行严格同步的场景。

2.6.3 伪共享与缓存行填充

在Cell类的定义中，用了一个独特的注解@sun.misc.Contended，这是JDK 8之后才有的，背后涉及一个很重要的优化原理：伪共享与缓存行填充。

在讲 CPU 架构的时候提到过，每个 CPU 都有自己的缓存。缓存与主内存进行数据交换的基本单位叫Cache Line（缓存行）。在64位x86架构中，缓存行是64字节，也就是8个Long型的大小。这也意味着当缓存失效，要刷新到主内存的时候，最少要刷新64字节。

如图2-4所示，主内存中有变量X、Y、Z（假设每个变量都是一个Long型），被CPU1和CPU2分别读入自己的缓存，放在了同一行Cache Line里面。当CPU1修改了X变量，它要失效整行Cache Line，也就是往总线上发消息，通知CPU 2对应的Cache Line失效。由于Cache Line是数据交换的基本单位，无法只失效X，要失效就会失效整行的Cache Line，这会导致Y、Z变量的缓存也失效。

虽然只修改了X变量，本应该只失效X变量的缓存，但Y、Z变量也随之失效。Y、Z变量的数据没有修改，本应该很好地被 CPU1 和 CPU2共享，却没做到，这就是所谓的“伪共享问题”。

问题的原因是，Y、Z和X变量处在了同一行Cache Line里面。要解决这个问题，需要用到所谓的“缓存行填充”，分别在X、Y、Z后面加上7个无用的Long型，填充整个缓存行，让X、Y、Z处在三行不同的缓存行中，如图2-5所示。

下面的代码来自JDK 7的Exchanger类，为了安全，它填充了15（8+7）个long型。

在著名的开源无锁并发框架Disruptor中，也有类似的代码：

而在JDK 8中，就不需要写这种晦涩的代码了，只需声明一个@sun.misc.Contended即可。下面的代码摘自JDK 8里面Exchanger中Node的定义，相较于JDK 7有了明显变化。

回到上面的例子，之所以这个地方要用缓存行填充，是为了不让Cell[]数组中相邻的元素落到同一个缓存行里。

2.6.4 LongAdder核心实现

下面来看LongAdder最核心的累加函数add（long x），自增、自减操作都是通过调用该函数实现的。

当一个线程调用add（x）的时候，首先会尝试使用casBase把x加到base变量上。如果不成功，则再用 a.cas（..）函数尝试把 x 加到Cell 数组的某个元素上。如果还不成功，最后再调用longAccumulate（..）函数。

注意：Cell[]数组的大小始终是2的整数次方，在运行中会不断扩容，每次扩容都是增长2倍。上面代码中的as[getProbe（）&m]其实就是对数组的大小取模。因为m=as.length–1，getProbe（）为该线程生成一个随机数，用该随机数对数组的长度取模。因为数组长度是2的整数次方，所以可以用&操作来优化取模运算。对于一个线程来说，它并不在意到底是把x累加到base上面，还是累加到Cell[]数组上面，只要累加成功就可以。因此，这里使用随机数来实现Cell的长度取模。

如果两次尝试都不成功，则调用 longAccumulate（..）函数，该函数在 Striped64 里面LongAccumulator也会用到，如下所示。

上面的函数fn就是2.6.5节LongAccumulator要用到的，但对于LongAdder而言，fn=null，就是简单的累加操作v+x。

上面的for循环被分成三个大的分支。在第二个分支里面，进行了Cells[]数组的初始化工作，初始大小为2，然后把x累加在0下标或者1下标对应的Cell上面。

在第一个大的分支里面，完成Cells[]数组的不断扩容，每次扩容都是增长2倍。

数组为空，并且有一个线程正在进行初始化工作，于是进入第三个大的分支中，尝试对base变量进行累积，如果再次失败，则会再次进入第一个大的分支。

2.6.5 LongAccumulator

LongAccumulator的原理和LongAdder类似，只是功能更强大，下面为两者构造函数的对比：

LongAdder只能进行累加操作，并且初始值默认为0；LongAccumulator可以自己定义一个二元操作符，并且可以传入一个初始值。

操作符的左值，就是base变量或者Cells[]中元素的当前值；右值，就是add（）函数传入的参数x。

下面是LongAccumulator的accumulate（x）函数，与LongAdder的add（x）函数类似，最后都是调用的Striped64的LongAccumulate（..）函数。唯一的差别就是LongAdder的add（x）函数调用的是casBase（b，b+x），这里调用的是casBase（b，r），其中，r=function.applyAsLong（b=base，x）。

2.6.6 DoubleAdder与DoubleAccumulator

DoubleAdder 其实也是用 long 型实现的，因为没有 double 类型的 CAS 函数。下面是DoubleAdder的add（x）函数，和LongAdder的add（x）函数基本一样，只是多了long和double类型的相互转换。

其中的关键Double.doubleToRawLongBits（Double.longBitsToDouble（b）+x），在读出来的时候，它把 long 类型转换成 double 类型，然后进行累加，累加的结果再转换成 long 类型，通过CAS写回去。

DoubleAccumulate也是Striped64的成员函数，和longAccumulate类似，也是多了long类型和double类型的互相转换。

DoubleAccumulator和DoubleAdder的关系，与LongAccumulator和LongAdder的关系类似，只是多了一个二元操作符，此处不再赘述。

到此为止，Concurrent包的所有原子类都介绍完了，接下来分析锁的实现。