前段时间研究了下sentinel系统，这个过程中遇到的一些知识点在这里记录下；如下内容和理解大多来源于网络。

主要知识点：

LongAdder类
伪共享（False sharing）和cpu缓存行

LongAdder类

LongAdder类是Doug Lea的杰作，jdk8中已把该类收录在concurrent包下。
在多线程环境下，我们计数qps、某段时间调用错误量这类计算时，想到的是AtomicInteger/AtomicLong，在多线程情况下，这些能减少锁带来的性能损耗；但是在大并发，竞争很激烈的情况下，出现CAS不成功的情况也会带来性能上的开销。
LongAdder类主要为解决这个问题，分散计数值写入时的压力；主要原理就是利用分段写人，减少竞争。
比如qps值为10, 它可以分解为2+3+4+1，这几个值分布在不同的段中单独计数；当qps加1时，可以在任意一个段中加1即可，每个段绑定某个线程，每次更新值由任一段对应的线程来执行。这样就很好的分散了线程之间的竞争。
当要计算总量时，累加每个段中的值即可。

Hystrix项目中的HystrixRollingNumber类中使用了LongAdder类。HystrixRollingNumber类内部实现了无锁环形数组，来做限流计数这样的统计计数；后续再记录下该类。

在小并发下，LongAdder与AtomicLong更新效率差不多，但在高并发的场景下，LongAdder有着更高的吞吐量。 LongAdder实现比较复杂的，明显的空间换时间。

总结下LongAdder减少冲突的方法以及在求和场景下比AtomicLong更高效的原因：

• 开始和AtomicLong一样，都会先采用cas方式更新值
• 在初次cas方式失败的情况下(通常证明多个线程同时想更新这个值)，尝试将这个值分隔成多个cell（sum的时候求和就好），让这些竞争的线程只管更新自己所属的cell，这样就将竞争压力分散了。

伪共享（False sharing）和cpu缓存行

LongAdder类继承Striped64类，看下Striped64类的一个变量cells：

   /**
     * Table of cells. When non-null, size is a power of 2.
     */
    transient volatile Cell[] cells;

Cell数组即为存储分割后的每个long值；看下Cell类的定义，

static final class Cell {
        volatile long p0, p1, p2, p3, p4, p5, p6;
        volatile long value;
        volatile long q0, q1, q2, q3, q4, q5, q6;
        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 = getUnsafe();
                Class<?> ak = Cell.class;
                valueOffset = UNSAFE.objectFieldOffset
                    (ak.getDeclaredField("value"));
            } catch (Exception e) {
                throw new Error(e);
            }
        }

    }

刚看到这个类代码肯定会很奇怪，为什么里面定义了这些没有用到的变量p0, p1, p2, p3, p4, p5, p6。这个就引出了伪共享（False sharing）和cpu缓存行；
网上关于这两个方面的文章也很多，如： 关于CPU Cache -- 程序猿需要知道的那些事 ，7个示例科普CPU CACHE，What is @Contended and False Sharing ?

Cache Line

CPU不是按单个bytes来读取内存数据的，而是以“块数据”的形式，每块的大小通常为64bytes，这些“块”被成为“Cache Line”（这种说法其实很不太正确，关于Cache Line的知识请参考文末的参考链接）

如果有两个线程（Thread1 和 Thread2）同时修改一个volatile数据，把这个数据记为'x':
volatile long x;

如果线程1打算更改x的值，而线程2准备读取：
Thread1：x=3;
Thread2: System.out.println(x);

由于x值被更新了，所以x值需要在线程1和线程2之间传递（从线程1到线程2），x的变更会引起整块64bytes被交换，因为cpu核之间以cache lines的形式交换数据(cache lines的大小一般为64bytes)。有可能线程1和线程2在同一个核心里处理，但是在这个简单的例子中我们假设每个线程在不同的核中被处理。

我们知道long values的内存长度为8bytes，在我们例子中"Cache Line"为64bytes，所以一个cache line可以存储8个long型变量，在cache line中已经存储了一个long型变量x，我们假设cache line中剩余的空间用来存储了7个long型变量，例如从v1到v7
x,v1,v2,v3,v4,v5,v6,v7

False Sharing

一个cache lien可以被多个不同的线程所使用。如果有其他线程修改了v2的值，线程1和线程2将会强制重新加载cache line。你可以会疑惑我们只是修改了v2的值不应该会影响其他变量，为啥线程1和线程2需要重新加载cache line呢。然后，即使对于多个线程来说这些更新操作是逻辑独立的，但是一致性的保持是以cache line为基础的，而不是以单个独立的元素。这种明显没有必要的共享数据的方式被称作“False sharing”.

Padding

为了获取一个cache line，核心需要执行几百个指令。

如果核心需要等待一个cache line重新加载，核心将会停止做其他事情，这种现象被称为"Stall".Stalls可以通过减少“False Sharing”,一个减少"false sharing"的技巧是填充数据结构，使得线程操作的变量落入到不同的cache line中。

下面是一个填充了的数据结构的例子，尝试着把x和v1放入到不同的cache line中

public class FalseSharingWithPadding {

public volatile long x; 
public volatile long p2;   // padding 
public volatile long p3;   // padding 
public volatile long p4;   // padding 
public volatile long p5;   // padding 
public volatile long p6;   // padding 
public volatile long p7;   // padding 
public volatile long p8;   // padding 
public volatile long v1; 

}
在你准备填充你的所有数据结构之前，你必须了解jvm会减少或者重排序没有使用的字段，因此可能会重新引入“false sharing”。因此对象会在堆中的位置是没有办法保证的。

为了减少未使用的填充字段被优化掉的机会，将这些字段设置成为volatile会很有帮助。对于填充的建议是你只需要在高度竞争的并发类上使用填充，并且在你的目标架构上测试使用有很大提升之后采用填充。最好的方式是做10000玄幻迭代，消除JVM的实时优化的影响。

java 8中引入了一个新注解 @Contented,主要是用来减少“False sharing”，在你需要避免“false sharing”的字段上标记注解，这可以暗示虚拟机“这个字段可以分离到不同的cache line中”，所以LongAdder在java8中的实现已经采用了@Contended