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

背景

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

x-apm的异常绝不能影响业务系统
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作者的博客改写而来)

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：


// 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开启特定参数。对于中间件产品来说可能手动填充更合适。请看以下常见填充方式：

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工具(下载传送门)查看对象内存布局来验证我们的预想：

$ 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存活下来，需要修改对象头中的对象年龄。

对于作者的严谨，我服…