伪共享

前言

在并发编程时，我们基本都只会关注共享变量的访问控制上以保证线程安全，很少会关注系统硬件及JVM底层相关的影响因素。我们今天的主题–伪共享，就是一个涉及系统底层而影响性能的无形杀手。伪共享简单来说就是，当多个线程修改互相独立的变量时，如果这些变量在同一个缓存行中，那么就会无意中影响彼此的性能。

从伪共享的简单定义可以看出，和伪共享紧密相关的是 CPU 缓存，因此在介绍伪共享之前我们需要先对 CPU 缓存相关的必要知识进行介绍。

CPU缓存

由于 CPU 和内存的访问性能相差很大，因此在 CPU 和内存之间嵌入了高速缓存 CPU Cache 以调和两者之间速度的差距。高速缓存一般分为三级缓存，级别越低的离 CPU 核心越近，访问速度越快，但存储容量相对就会越小。其中，在多核心的 CPU 架构中，每个核心都有各自的 L1 Cache、L2 Cache ，而 L3 Cache 是该 CPU 的所有核心共享使用的。CPU 架构如下：

高速缓存 CPU Cache 是由很多个缓存行 Cache Line 组成的，CPU Line 也是 CPU 从内存读取数据的基本单位。大致如下：

缓存问题

缓存读写

CPU 读取数据的时候，都是先从 CPU Cache 中读取，没有命中才会再从内存中读取数据。对于写操作，数据写入 CPU Cache 后，内存和 CPU Cache 相对应的数据会不同，这时就需要将 CPU Cache 中的数据同步到内存中。

CPU Cache 同步到内存的策略具体如下：

• 写数据时，如果数据已经在 CPU Cache 中，那么直接将数据更新到 CPU Cache 中并标记对应缓存行 Cache Line 为 Dirty，表示 CPU Cache 的数据和内存是不一致的；
• 写数据时，缓存没有命中，数据对应的 Cache Line 中存放的是其它内存地址数据，此时要检查是否标记为 Dirty，如果标记为 Dirty 则需要把缓存中的数据写回内存，然后再把当前要写入的数据写入这个 Cache Line 中并标记对应缓存行 Cache Line 为 Dirty；如果检查的结果是没有标记为 Dirty，那么直接将当前要写入的数据写入到这个 Cache Line 中并标记对应缓存行 Cache Line 为 Dirty。

缓存一致性问题

前面简单介绍了 CPU 单核下的读写过程，但是现代 CPU 都是多核的，而且 L1 Cache 和 L2 Cache 是多个核心各自独立的，这就会带来缓存一致性问题，缓存一致性问题得不到解决，就可能造成计算结果的错误。

下面我们以一个含有两个核心的 CPU 为例，说明缓存一致性问题是怎么发生的。假设 CPU 的 A 号核心和 B 号核心同时运行两个线程，都操作共享变量 i=0 。

时刻 t1: A 号核心执行了 i++ 语句，先把值为 1 的执行结果写入到 A 号核心的 L1 Cache 和 L2 Cache，然后将 L1 Cache 和 L2 Cache 中对应的 Line 标记为 Dirty。注意，此时数据 i 的值没有被同步到内存中；
时刻 t2: B 号核心从内存读取 i 的值，读取到的是 0，这是一个错误的值，因为在 t1 时刻 A 号核心更新 i 的值还没有写入到内存中，内存中的值依然是 0；

这就出现了缓存一致性问题，A 号和 B 号核心的缓存是不一致的，这就会导致计算结果错误。

那么如何解决这一问题呢？可以从以下两个方面入手：

• 某个 CPU 核心更新了 Cache 数据时，必须要把这一动作告知 CPU 其他核心。即要具备传播性；
• CPU 核心对数据的操作顺序，其它 CPU 核心感知必须满足在时间上的先后顺序；

总线嗅探

总线嗅探机制保证了，当某个 CPU 核心更新了 Cache 中的数据，就会通过总线把这个事件广播通知到其他核心。此外，每个 CPU 核心都会监听总线上的广播事件。

总线嗅探机制虽然简单，但是对总线的负载是很大的。CPU 核心要每时每刻监听总线上的一切事件，修改数据的 CPU 核心针对每次修改都要在总线上广播对应的事件。此外，总线嗅探机制只是保证了某个 CPU 核心更新数据能被其它 CPU 核心感知到，无法保证其它 CPU 感知事件的正确顺序。

鉴于总线嗅探机制存在的问题以及对总线压力过大，CPU 缓存一致性协议 MESI 协议出现了，它是基于总线嗅探机制实现的协议。

MESI 协议

MESI 协议是基于总线嗅探机制实现的，它主要围绕四个状态描述 CPU 的缓存行以及它们之间的转换。

Modified: CPU 核心已经修改缓存行，即是 Dirty 状态，它的内容和内存中的内容不一样，但内容此时只有本地 CPU 核心一个拷贝；
Exclusive: CPU 核心缓存行和内存中的一样，并且其它 CPU 核心都没有该内容；
Shared: CPU 核心缓存行和内存中的一样，并且存在其它 CPU 核心缓存行也和内存中的一样；
Invalid: 缓存行失效，不能使用，必须重新从内存拷贝；

下面根据上诉例子，对 MESI 协议中的缓存行状态转换进行说明：

• 缓存行没有加载任何数据，它处于 I 状态；
• A 号 CPU 核心从内存读取变量 i 的值，数据被缓存在 A 号 CPU 核心的缓存行中，其它 CPU 核心没有缓存该数据，因此缓存行状态为 E 状态，此时缓存中的数据和内存中的数据一致；
• B 号 CPU 核心也从内存读取变量 i 的值，此时 A 和 B 核心缓存了相同的数据，缓存行的状态就会变成 S 状态，并且其 Cache 中的数据与内存也是一致的；
• A 号 CPU 核心要修改缓存行中变量 i 的值，发现变量对应的缓存行的状态为 S 状态，那么要向所有其它 CPU 核心通过总线广播一个请求，要求先把其它 CPU 核心中对应的缓存行标记为 I 状态，然后 A 号 CPU 核心才更新缓存行中的数据，同时标记缓存行为 M 状态，此时缓存中的数据和内存不一致了；这个时候，如果 A 号 CPU 核心继续更新缓存行中变量 i 的值，由于此时的缓存行是 M 状态，因此不需要给其他 CPU 核心发送消息，直接更新数据即可；
• A 号 CPU 核心的缓存行中变量 i 要被替换，并且此时缓存行的状态为 M ，那么需要在替换变量 i 之前先把数据同步到内存；

可以看见，如果处于 M 状态的缓存行，再由本地处理器写入/读出，状态是不会改变的，也就不需要发送广播消息给其它 CPU 核心，这无疑减少了总线带宽的压力。

整个 MESI 的状态转换使用了一个有限状态机来描述，不同状态触发的事件操作，不仅仅来自本地 CPU 核心，还可以来自其它 CPU 核心通过总线发出的广播事件。下图展示了状态转换过程：

伪共享

了解了 CPU 缓存相关的点后，伪共享问题就很简单了。

数据在缓存内部都是以缓存行为单位进行存储的。缓存行一般都是 2^n 个字节大小，现在最为常见的缓存行的大小是 64 字节。因此，缓存中的数据并不是一个个单独的变量进行储存，可能是多个变量放到一个缓存行中存储。

我们以数组和链表举例，数组的内存地址是连续的，当读取数组中的元素时 CPU 会连续加载若干元素到缓存中以提高效率。反观链表，由于内存地址不连续，高效不起来。

在文章的开头，我们已经简单定义了伪共享，下面我们结合具体例子对伪共享进行说明。假设某个 CPU 中缓存了 x,y 两个变量，它们同时已经在不同的三级缓存之中。这时有两个线程A和B同时去修改位于 Core1 和 Core2 的变量 x 和 y。当线程A去修改 Core1 中的缓存中的 x 变量时，由于缓存一致性协议会要求 Core2 中对应缓存了 x 变量的缓存行失效，要继续访问 x 变量就需要从主内存中重新加载。反之亦然，Core1 中对应缓存了 y 变量的缓存行失效。示例图如下：

像这样，当多个线程修改互相独立的变量时，如果这些变量在同一个缓存行中，会导致缓存消失进而导致频繁的主内存访问，性能就会下降，这就是伪共享问题。

解决伪共享问题

知道了伪共享问题后，接下来我们就要避免了，那怎么避免呢？

我们知道伪共享根本问题是 CPU 缓存行的存储规则，但是改变缓存行的存储规则是做不到的，因此我们需要想别的办法。

既然不能通过改变 CPU 缓存行来保证只存储一个数据，那能不能通过填充的方式来保证缓存行中只有一个数据呢？答案是行的，常见的处理方式就是这种思路。

字节填充

一般来说，缓存行的大小是 64 字节，我们依据这个大小进行字节填充来保证缓存行只能容纳一个变量。

比如我们有一个目标变量为 long 类型，它是 8 个字节。我们使用一个类封装这个目标变量，具体如下：

class Value{
    public volatile long value;
    public long f1,f2,f3,f4,f5;
}

我们使用 5 个 long 类型的属性进行填充，一共是 48 个字节。而 Java 中对象头在 32 位系统下占用 8 个字节，64 位系统下占用 16 个字节，这样填充 5 个long 类型即可填满 64 字节，也就是一个缓存行。

@Contented 注解

JDK8以及之后的版本中提供了 sun.misc.Contended 注解，通过该注解就可以解决伪共享的问题。

@Contended
class Value{
    public volatile long value;
    // public long f1,f2,f3,f4,f5;
}

使用 @Contented 注解后会增加128字节的 padding，并且需要开启 -XX:-RestrictContended 选项后才能生效。

以上两种方式解决了伪共享问题，但是这种填充的方式也浪费了缓存资源，因此我们需要在时间和空间之间进行取舍。

应用场景

JDK1.8 中新增了 LongAdder 类以解决高并发下 AtomicLong 的缺点，它的实现中就解决了伪共享问题。LongAdder 继承自 Striped64，内部通过维护一个 Cell 数组来进行元素个数的统计，核心思想就是把单个变量的竞争进行分摊。

解决伪共享的真正的核心在 Cell 数组上，通过对 Cell 类使用 @Contented 注解。因为数组的内存地址是连续的，因此数组内的多个元素可能会被放入一个缓存行，这样的话就会带来伪共享问题，影响性能。这里使用 @Contented 注解，保证 Cell 的填充，规避伪共享问题，使数组中的元素不再共享一个缓存行。

@sun.misc.Contended
  static final class Cell {
      /**
       * 元素值，使用 volatile 修饰保证可见性
       */
      volatile long value;

      Cell(long x) {
          value = x;
      }

      /**
       * CAS 更新 元素值
       *
       * @param cmp 原始值
       * @param val 新值
       * @return
       */
      final boolean cas(long cmp, long val) {
          return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val);
      }
    ...
  }

JDK1.8 中 ConcurrentHashMap 使用了类似 LongAdder 的实现来进行集合元素个数的统计，关键类 CounterCell 相当于 LongAdder 中的 Cell 类，因为两者基本一样就不再说明。

@sun.misc.Contended
static final class CounterCell {
    /**
     * 当前段对应的元素数量，可见性保证
     */
    volatile long value;

    CounterCell(long x) {
        value = x;
    }
}

小结

CPU 具有多级缓存，缓存数据是以缓存行为单位进行处理的。

CPU 缓存虽然提高了性能，但是带来了数据一致性问题，通过缓存一致性协议来保证缓存和主内存的数据一致。

CPU 缓存同样也带来了弊端，多线程处理不相干的变量时会相互影响，造成性能低下，也就是伪共享问题。避免伪共享的主要思路就是让不相干的变量不要出现在同一个缓存行中，一般使用填充法来实现。