伪共享

Java

近期对并发编程进行了研究，看到已经从jsr166y添加到java 7里的LinkedTransferQueue及Disruptor框架均有对伪共享(False Sharing)问题进行了单独的处理，于是，对此类问题进行了梳理：

目前典型的CPU架构有三级缓存，从读取速度由快而慢分别为L1 -> L2 ->L3。对于多核架构，L1，L2为单核独享，而L3为多核共享。CPU指令执行即从L1 cache开始读取，如果cache miss，便从下一级cache读取，直到内存。

为了高效利用cache，CPU不是简单地将单条数据(指令)写入cache，而是将一批数据指令(连续地)写入cache行中。即cache行是对cache进行读写操作的最小单位。对于目前典型的core，ivy，sandy等cpu，cache行大小为64bytes。

同时，对于多核系统，每个核有私有的L1，L2，多线程并发时，如果某个核需要修改的变量同时在另外一个核的cache中，为了保证数据的一致性，需要使当前核cache中变量失效(invalidate)，然后同步一致数据。这种操作是有硬件层级的缓存一致性协议来保证的，通常是M-E-S-I协议。其中M,E,S和I代表使用cache行所处的四个状态，协议通过四种状态的(复杂)迁移(类似状态机模型)来保证一致性。当发生上述不一致时，当前核会发出RFO(Request For Owner)请求来保证一致性，但是这个保证过程需要低层级cache或者内存的同步，会对性能造成很大的影响。
对于Java对象，相邻的成员变量被加载到同一个cache行中，当不同线程对成员变量分别操作时，就会导致RF0请求的发生，这种现象即伪共享。

Disruptor设计示意图

上图为disruptor作者设计的示意图，x，y变量分别被load到c1，c2的cache行中，c1更新x，c2更新y，而x，y位于同一条cache行中，此时两个线程轮番发送RFO消息，占有cache行拥有权，获得拥有权线程对变量的更新会导致其他核中的cache行中的变量失效，进而通过L3进行变量同步，而此时如果L3 miss，还需要通过内存同步，对性能造成很大的影响。因此，虽然x，y被独立线程操作，彼此无任何关系，因为伪共享，性能有很大的问题。
比较悲催的是，上面的x，y变量的伪共享在生产者-消费者模式中比较常见。生产者-消费者模式中，生产者和消费者作为不同的线程不停地操作队列的首尾两端(通过head,tail指针)，而这两个指针对象定义在一起，加载head时，会将tail同时加载到同一个cache line中。

例如：Java j.u.c LinkedBlockingQueue的

1
2
3
4
5
 /** Head of linked list */
private transient Node<E> head;
 
/** Tail of linked list */
private transient Node<E> last;

head，last共占8bytes。两者被加载到同一个cache line。大量的生产者、消费者对queue进行读写时，会发生较大的性能问题

为了防止伪共享的发生，通常进行缓存行补齐(cache line padding)，即对对象进行填充，使其占用一个cache行。这样可以保证对象不处于同一缓存行。

对于Hotspot Java对象，Java程序的对象头固定占8字节(32位系统)，此时只需要填48bytes即可保证对象处于,不同的缓存行, 从而避免伪共享。(对于64位系统，对象头占用空间更大，多出也无所。)

例如：

在 LinkedTransferQueue中(早期的jsr166y版本，收录在早期的netty项目中)，队列的head，tail如下定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/** head of the queue */
    private final PaddedAtomicReference<QNode> head;
    /** tail of the queue */
    private final PaddedAtomicReference<QNode> tail;
 
 
    /**
     * Padded version of AtomicReference used for head, tail and
     * cleanMe, to alleviate contention across threads CASing one vs
     * the other.
     */
    private static final class PaddedAtomicReference<T> extends AtomicReference<T> {
        private static final long serialVersionUID = 4684288940772921317L;
 
        // enough padding for 64bytes with 4byte refs
        Object p0, p1, p2, p3, p4, p5, p6, p7, p8, p9, pa, pb, pc, pd, pe;
        PaddedAtomicReference(T r) { super(r); }
    }

PaddedAtomicReference通过15个4byte对象，对AtomicReference进行了填充，从避免了伪共享，LinkedTransferQueue后期版本对其设计进行了更新，但核心类似，只是方法更加优雅（还没有完全看懂）。

在Disruptor框架中，其核心数据结构RingBuffer的序号由Sequence对象来维护，Sequence对象，定义了

1
private final long[] paddedValue = new long[15];

通过15个long来填充。序号设置/获取时分别调用

1
2
3
4
5
6
7
public long get(){
    return unsafe.getLongVolatile(paddedValue, valueOffset);
}
 
public void set(final long value){
    unsafe.putOrderedLong(paddedValue, valueOffset, value);
}

这样通过sun unsafe的CAS操作，对序号进行填充，从而避免了伪共享。