解决伪共享(False-Sharing)问题：最大化利用你的 CPU 缓存

这篇文章是先前我在分布式 ID 生成算法 SnowFlake 及其 Go 实现中提到的伪共享（False-Sharing） 问题的延伸，主要是为了更好地理解并解决伪共享问题，以便通过最大化使用 CPU 缓存来增强性能。

什么是伪共享？

当代 CPU 普遍采用多级缓存的架构，例如：

1
L1 Cache -> L2 Cache -> L3 Cache -> RAM -> Disk

其中，缓存读写速度（以及硬件成本）依次递减，而容量则依次递增。当 CPU 访问某个内存地址时，会先从 L1 Cache 开始查找，如果没有找到，再从 L2 Cache 查找，以此类推。如果在 L1 Cache 中找到了，那么就会直接返回，否则就会将 L2 Cache 中的数据拷贝到 L1 Cache 中，再返回。

想要让程序运行的更快，就需要尽可能地利用低级别的缓存。CPU 缓存是由缓存行组成的，一个缓存行一般是 64 个字节，CPU 读取数据是以缓存行为单位的读取，这意味着即使是读 1 个字节的数据，CPU 也要读取这个数据所在的连续的 64 个字节的数据，如果使用的数据结构中的数据项不是彼此相邻连续的，如链表，那么读数据的时候就得不到这个缓存机制带来的好处；反之，例如 Java 中大部分情况下（JVM 并未强制规定数组连续）的数组存储空间是连续的，它就能够充分利用一个缓存行中的数据，这也是为什么往往数组的数据访问速度要比链表快的原因。

伪共享问题：假设我们有 Java 中 long 类型（8 字节）的变量 a 和 b，当 a 和 b 同时存放于一个 L1 缓存行时，线程 1 从缓存行读取了 a，与此同时线程 2 读取了 b。此时由于线程 1 先读取了 L1 缓存，线程 2 的 L1 缓存读取失效（即缓存未命中），线程 2 必须到 L2 缓存甚至更加上级的存储介质中去读取 b，造成了额外的开销。这就是伪共享问题。

关于伪共享更详细的例子和背后原理可以看 这篇文章。

伪共享的解决方法

以下例子给出了一个受伪共享问题影响的程序，来自一篇知乎文章：

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
public class FalseSharingDemo {

    public static void main(String[] args) throws InterruptedException {
        testPointer(new Pointer());
    }

    private static void testPointer(Pointer pointer) throws InterruptedException {
        long start = System.currentTimeMillis();
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 100000000; i++) {
                pointer.a++;
            }
        }, "A");

        Thread t2 = new Thread(() -> {
            for (int i = 0; i < 100000000; i++) {
                pointer.b++;
            }
        },"B");

        t1.start();
        t2.start();
        t1.join();
        t2.join();

        System.out.println(System.currentTimeMillis() - start);
        System.out.println(pointer.a + "@" + Thread.currentThread().getName());
        System.out.println(pointer.b + "@" + Thread.currentThread().getName());
    }
}

class Pointer {
    //  变量需要 volatile 关键字修饰，避免重排序

    //  如果有一个线程在读取 a 时，会顺带把同一缓存行中的 b 带出
    volatile long a;
    //  该行用于解决伪共享的问题
    //  long p1, p2, p3, p4, p5, p6, p7;
    volatile long b;
}

在我的机器上运行这段代码，耗时在 3000ms - 4000ms 之间。

而如果将 Pointer 类中的注释去掉，即通过向缓存行填充空数据来确保两个变量不同时在缓存行上：

1
2
3
4
5
6
7
8
9
class Pointer {
    //  变量需要 volatile 关键字修饰，避免重排序

    //  如果有一个线程在读取 a 时，会顺带把同一缓存行中的 b 带出
    volatile long a;
    //  该行用于解决伪共享的问题
    volatile long p0, p1, p2, p3, p4, p5, p6;
    volatile long b;
}

耗时基本在 1000ms - 1100ms 之间，性能提升了三倍之多。

滑动窗口优化

通过填充的方法解决伪共享本质上仍然是用空间换时间的解决方案，这在一些高性能需求的热点数据上是非常有意义的，但不可能将变量全部都做防伪共享处理。

假设上文例子中的变量 a 是我们希望解决伪共享的热点数据，我们实际上并不能保证 a 一直独占缓存行，我们只能保证它不与 b 共享缓存行，因为我们只在 a-b 之间做了缓存行填充。当 a 被存储在缓存行尾的时候，缓存行前面的数据是有可能被另外的线程访问的，这又造成了伪共享问题。

作为优化，对于一个热点变量 a，我们假设其为 Java long 类型（8 字节），机器缓存大小为 64 字节，我们可以通过下面的方法保证该热点变量 a 总是独占一个缓存行：

1
2
3
4
5
class Pointer {
    volatile long p0, p1, p2, p3, p4, p5, p6;
    volatile long a;
    volatile long p8, p9, p10, p11, p12, p13, p14;
}

这是一个滑动窗口的思想，我们将 a 放在缓存行的中间，前后各填充 7 个 long 类型的数据，这样就保证了 a 一定独占一个缓存行：

1
2
3
4
5
6
7
8
9
10
11
12
 7 * 8 = 56   (8 bytes)    7 * 8 = 56
+----------+              +----------+
|          |              |          |
+----------+    count     +----------+


+-------------------------+
|                         |
+-------------------------+
cache line(sliding window) 64 bytes
------------------------->
           slide

该解决方案是我受到 Apache SkyWalking PR#2930 的启发得出的。

自定义原子类（推荐）

之前文章提到的百度 UUID 生成器中，给出了一种防止伪共享的自定义原子类的最佳实践：

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
import java.util.concurrent.atomic.AtomicLong;

/**
 * Represents a padded {@link AtomicLong} to prevent the FalseSharing problem<p>
 *
 * The CPU cache line commonly be 64 bytes, here is a sample of cache line after padding:<br>
 * 64 bytes = 8 bytes (object reference) + 6 * 8 bytes (padded long) + 8 bytes (a long value)
 *
 * @author yutianbao
 */
public class PaddedAtomicLong extends AtomicLong {
    private static final long serialVersionUID = -3415778863941386253L;

    /** Padded 6 long (48 bytes) */
    public volatile long p1, p2, p3, p4, p5, p6 = 7L;

    /**
     * Constructors from {@link AtomicLong}
     */
    public PaddedAtomicLong() {
        super();
    }

    public PaddedAtomicLong(long initialValue) {
        super(initialValue);
    }

    /**
     * To prevent GC optimizations for cleaning unused padded references
     */
    public long sumPaddingToPreventOptimization() {
        return p1 + p2 + p3 + p4 + p5 + p6;
    }

}

从头说明一下这个类的设计细节：

  • 通过 JVM 约定的 static final long serialVersionUID 字段，保证该类的序列化兼容性和一致性，确保不会因为 JVM 优化等原因而导致序列化后的类结构被改变。
  • 仅填充了 6 个 long 类型的数据（占 48 byte），剩余的 16 byte 中，8 byte 用于存储 long 类型的数据，另外 8 byte 用于存储对象的引用/元数据等信息，这样就保证了该类的大小为 64 byte，即一个缓存行的大小。
1
2
3
4
5
 (48 bytes)   (8 bytes)     (8 bytes)
+----------+--------------+----------+
|          |              |          |
+----------+--------------+----------+
   Padding    AtomicLong    Reference
  • 通过添加一个没有实际作用的公共成员函数 sumPaddingToPreventOptimization()，来防止 JVM 对该类的优化，保证了 6 个填充变量不会被 GC 回收。

@Contended 注解（推荐）

在 JDK 8 及以上版本中，Java 提供了 @Contended 注解，用于解决伪共享问题。@Contended 注解可以用于类、字段、方法等，用于告诉 JVM 对被注解的字段进行填充，从而避免伪共享问题。

@Contended 注解默认只是在 JDK 内部起作用，如果我们的程序代码中需要使用到 @Contended 注解，那么需要开启 JVM 参数-XX:-RestrictContended才会生效。

1
2
3
4
5
6
@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.FIELD, ElementType.TYPE})
public @interface Contended {
    //contention group tag
    String value() default "";
}

  • @Contended 标注在类上表示该类对象中的实例数据整体需要独占缓存行。不能与其他实例数据共享缓存行。

  • @Contended 标注在类中的字段上表示该字段需要独占缓存行。

  • 除此之外 @Contended 还提供了分组的概念，注解中的 value 属性表示 contention group 。属于统一分组下的变量，它们在内存中是连续存放的，可以允许共享缓存行。不同分组之间不允许共享缓存行。