伪共享

近期对并发编程进行了研究,看到已经从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操作,对序号进行填充,从而避免了伪共享。