Zacard's Notes

分布式追踪系统x-apm拾遗之伪共享与缓存行填充

背景

之前开发分布式追踪系统x-apm的时候,确认了2个目标:

  1. x-apm的异常绝不能影响业务系统
  2. x-apm应该尽可能的少暂用系统资源的前提下,尽可能的快(实时)

针对第2点,用来暂存追踪数据的数据结构碰到了伪共享的问题,导致收集发送的效率不够高,所以使用的缓存行填充。

这里记录下伪共享和缓存行填充的相关内容。

基础简介

cpu cache

一个典型的cpu cache架构:

访问速度:寄存器<L1 cache<L2 cache<L3 cache<主存

所以,充分利用它的结构和机制,可以有效的提高程序的性能

这里需要注意:一个cpu中的多核共享L3 cache,而L1、L2 cache是每个核心各自拥有的;一个缓存行一般缓存64byte大小的数据

cpu缓存一致性协议 - MESI

在MESI协议中,每个Cache line有4个状态,可用2个bit表示,它们分别是:

状态 描述
M(Modified) 这行数据有效,数据被修改了,和主存冲的数据不一致,数据只存在本Cache中
E(Exclusive) 这行数据有效,数据和内存中的数据一致,数据只存在于本Cache中
S(Shard) 这行数据有效,数据和内存中的数据一致,数据存在于很多Cache中
I(Invalid) 这行数据无效

MESI协议中的状态

  • M: 被修改(Modified)

    该缓存行只被缓存在该CPU的缓存中,并且是被修改过的(dirty),即与主存中的数据不一致,该缓存行中的内存需要在未来的某个时间点(允许其它CPU读取请主存中相应内存之前)写回(write back)主存。

    当被写回主存之后,该缓存行的状态会变成独享(exclusive)状态。

  • E: 独享的(Exclusive)

    该缓存行只被缓存在该CPU的缓存中,它是未被修改过的(clean),与主存中数据一致。该状态可以在任何时刻当有其它CPU读取该内存时变成共享状态(shared)。

    同样地,当CPU修改该缓存行中内容时,该状态可以变成Modified状态。

  • S: 共享的(Shared)

    该状态意味着该缓存行可能被多个CPU缓存,并且各个缓存中的数据与主存数据一致(clean),当有一个CPU修改该缓存行中,

    其它CPU中该缓存行可以被作废(变成无效状态(Invalid))。

  • I: 无效的 (Invalid)

    该缓存行数据无效。

M(Modified)和E(Exclusive)状态的Cache line,数据是独有的,不同点在于M状态的数据是dirty的(和内存的不一致),E状态的数据是clean的(和内存的一致)。

S(Shared)状态的Cache line,数据和其他Core的Cache共享。只有clean的数据才能被多个Cache共享。

一个缓存除在Invalid状态外都可以满足cpu的读请求,一个invalid的缓存行必须从主存中读取(变成S或者E状态)来满足该CPU的读请求

cache line

数据在缓存中不是以独立的项来存储的,如不是一个单独的变量,也不是一个单独的指针。缓存是由缓存行组成的,通常是64字节,并且它有效地引用主内存中的一块地址。一个Java的long类型是8字节,因此在一个缓存行中可以存8个long类型的变量。

当缓存行加载数据的时候,会同时加载其后连续的一部分数据。所以你可以非常快速的遍历在连续的内存块中分配的任意数据结构。因此如果你数据结构中的项在内存中不是彼此相邻的(比如链表),你将得不到免费缓存加载所带来的优势。并且在这些数据结构中的每一个项都可能会出现缓存未命中

伪共享

伪共享就是2个不同的数据恰好被加载到同一个缓存行中,不同cpu的核分别去修改该缓存行中的不同数据,却导致了相互竞争同一个缓存行。例如以下例子:

数据X、Y、Z被加载到同一Cache Line中,线程A在Core1修改X,线程B在Core2上修改Y。根据MESI大法,假设是Core1是第一个发起操作的CPU核,Core1上的L1 Cache Line由S(共享)状态变成M(修改,脏数据)状态,然后告知其他的CPU核,图例则是Core2,引用同一地址的Cache Line已经无效了;当Core2发起写操作时,首先导致Core1将X写回主存,Cache Line状态由M变为I(无效),而后才是Core2从主存重新读取该地址内容,Cache Line状态由I变成E(独占),最后进行修改Y操作, Cache Line从E变成M。可见多个线程操作在同一Cache Line上的不同数据,相互竞争同一Cache Line,导致线程彼此牵制影响,变成了串行程序,降低了并发性。

缓存行填充

一般解决伪共享的方式就是缓存行填充,将频繁写的变量填充到64byte,不和其他变量加载到同一个缓存行即可。

例如以下代码:(参考Disruptor作者的博客改写而来)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class FalseSharingTest {
public static final int THREAD_NUMBER = 4;
public static final long WIRTER_NUMBER = 800_000_000L;
public static final PaddedLong[] ARRAY = new PaddedLong[4];
public static class PaddingLong {
private long p1, p2, p3, p4, p5, p6 = 7L;
/**
* 阻止jvm优化掉无用的字段
*/
public long preventOptimisation() {
return p1 + p2 + p3 + p4 + p5 + p6;
}
}
public static class PaddedLong extends PaddingLong {
public volatile long value = 0L;
}
public static void main(String[] args) throws InterruptedException {
long start = System.currentTimeMillis();
CountDownLatch countDownLatch = new CountDownLatch(THREAD_NUMBER);
for (int i = 0; i < THREAD_NUMBER; i++) {
final int index = i;
new Thread(() -> {
ARRAY[index] = new PaddedLong();
long count = WIRTER_NUMBER;
while (count-- != 0) {
ARRAY[index].value = count;
}
countDownLatch.countDown();
}).start();
}
countDownLatch.await();
System.out.println("耗时:" + (System.currentTimeMillis() - start));
}
}

PaddedLong不继承PaddingLong的时候,即没有使用缓存行填充,程序执行时间甚至2倍于填充后

JDK8后更智能,可以直接使用@sun.misc.Contended来标注需要填充的字段或者类(标注类表示,类中的所有字段都需要填充)。注意,jvm需要添加参数-XX:-RestrictContended才能开启此功能

例如JDK8中的ConcurrentHashMap:

1
2
3
4
5
6
7
8
9
10
11
// ConcurrentHashMap.java line:2506
/**
* A padded cell for distributing counts. Adapted from LongAdder
* and Striped64. See their internal docs for explanation.
*/
@sun.misc.Contended static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}

思考

@sun.misc.Contended虽然很智能,但是需要jvm开启特定参数。对于中间件产品来说可能手动填充更合适。请看以下常见填充方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class PaddingLong {
private long p1, p2, p3, p4, p5, p6 = 7L;
/**
* 阻止jvm优化掉无用的字段
*/
public long preventOptimisation() {
return p1 + p2 + p3 + p4 + p5 + p6;
}
}
public class PaddedLong extends PaddingLong {
public volatile long value = 0L;
}

以上是参考Disruptor作者的填充方式,也是很多开源产品的填充方式。

作者只填充了6个long变量,也就是PaddedLong实例对象的内存占用大小为:16(对象头大小)+6*8(填充变量大小)+1*8(被填充变量大小)=72byte>64byte

可以使用JOL工具(下载传送门)查看对象内存布局来验证我们的预想:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
$ java -jar ~/tools/jol-cli-0.9-full.jar internals -cp algorithm-1.0-SNAPSHOT.jar com.zacard.algorithm.test.falseshare.PaddedLong
$ com.zacard.algorithm.test.falseshare.PaddedLong object internals:
OFFSET SIZE TYPE DESCRIPTION VALUE
0 4 (object header) 01 00 00 00 (00000001 00000000 00000000 00000000) (1)
4 4 (object header) 00 00 00 00 (00000000 00000000 00000000 00000000) (0)
8 4 (object header) 44 08 02 f8 (01000100 00001000 00000010 11111000) (-134084540)
12 4 (alignment/padding gap)
16 8 long PaddingLong.p1 0
24 8 long PaddingLong.p2 0
32 8 long PaddingLong.p3 0
40 8 long PaddingLong.p4 0
48 8 long PaddingLong.p5 0
56 8 long PaddingLong.p6 7
64 8 long PaddedLong.value 0
Instance size: 72 bytes
Space losses: 4 bytes internal + 0 bytes external = 4 bytes total

可以看到填充的对象确实占用了72byte。

看一下作者的解释(传送门):

I do not want the mark word to be in the cache line which can be modified by taking out locks or the garbage collector ageing the object

我不希望在缓存行中的对象头中的“mark word”在设置锁标记或者垃圾回收器在老化对象的时候被修改

这里修改对象头中的锁标记应该能理解,因为当synchronized一个对象的时候,确实会修改对象头中的锁标记,这个也很可能会造成伪共享的问题。

“garbage collector ageing the object”应该指的是对象挨过一次gc存活下来,需要修改对象头中的对象年龄。

对于作者的严谨,我服…

坚持原创技术分享,您的支持将鼓励我继续创作!

热评文章