伪共享 FalseSharing (CacheLine，MESI) 浅析以及解决方案

た入场券 2021-09-02 08:42 338阅读 0赞

原理参考：[https://blog.csdn.net/z69183787/article/details/108682200][https_blog.csdn.net_z69183787_article_details_108682200]

其他参考：[https://blog.csdn.net/songfei\_dream/article/details/103436061][https_blog.csdn.net_songfei_dream_article_details_103436061]

**64位下 markdown（8字节，32位4字节），class类型指针（压缩后4字节，压缩jvm参数详解**[https://blog.csdn.net/z69183787/article/details/108682097][https_blog.csdn.net_z69183787_article_details_108682097]**）， padding 6个long ，8+4+6\*8=60字节，就可以让不同的 long类型属性分隔在 2个 cache缓存行中，一共64个字节= 1个缓存行**

# 起因 #

在阅读百度的发号器 [uid-generator][] 源码的过程中，发现了一段很奇怪的代码：

/**
     * 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);
        }
    
    }

这里面有6个看上去毫无作用的volatile long变量（标红）。如果这是我自己写的代码，我肯定会认为是我自己手抖写多了。

但是作为百度的发号器，开源了这么久，如果是手抖早被fix了。肯定还是有深意的。于是阅读了一些类注释，看到了这句话：

>     to prevent the FalseSharing problem

果然，这几个变量不是毫无作用的，是为了解决FalseSharing问题。

但是转念一想，我好像不知道什么是FalseSharing？解决了一个问题，又陷入了另一个更大的问题。

于是就上网查了很多资料，阅读了很多博客，算是对FalseSharing有了一个初步的了解。在这里写出来也为了希望能帮到有同样困惑的人。

# 背景知识 #

要说清楚FalseSharing，不是一两句话能做到的事，有一些必须了解的背景知识需要补充一下。

## 计算机存储架构 ##

上图展示的是不同层级的硬件和cpu之间的交互延迟。越靠近CPU，速度越快。

计算机运行时，CPU是执行指令的地方，而指令会需要一些数据的读写。程序的运行时数据都是存放在主存的，而主存又特别慢（相对），所以为了解决CPU和主存之间的速度差异，现代计算机都引入了高速缓存（L1L2L3）。

现代计算机对缓存/内存的设计一般如下：

L1和L2由CPU的每个核心独享，而L3则被整个CPU里所有核心共享（仅指单CPU架构）。

CPU访问数据时，按照先去L1，查不到去L2，再L3->主存的顺序来查找。

# #

## Cache Line ##

在上述CPU和缓存的数据交换过程中，并不是以字节为单位的。而是每次都会以Cache Line为单位来进行存取。

Cache Line其实就是一段固定大小的内存空间，一般为64字节。

## MESI ##

这个东西研究过 volatile的同学可能会比较熟悉，这个就是各个告诉缓存之间的一个一致性协议。

因为L1 L2是每个核心自己使用，而不同核心又可能涉及共享变量问题，所以各个高速缓存间势必会有一致性的问题。MESI就是解决这些问题的一种方式。

MESI大致原理如下图：

我这里就摘抄一下网上搜到的解释：

> 在MESI协议中，每个Cache line有4个状态，可用2个bit表示，它们分别是：  
> M(Modified)：这行数据有效，数据被修改了，和内存中的数据不一致，数据只存在于本Cache中；  
> E(Exclusive)：这行数据有效，数据和内存中的数据一致，数据只存在于本Cache中；  
> S(Shared)：这行数据有效，数据和内存中的数据一致，数据存在于很多Cache中；  
> I(Invalid)：这行数据无效。

通俗一点说，就是如果Core0和Core1都在使用一个共享变量变量A，则0，1都会在自己的Cache里有一份A的副本，分布在不同的CacheLine。

如果大家都没有修改A，则Core0和Core1里变量A所在的Cache Line的状态都是S。

如果Core0修改了A的值，则此时Core0的Cache Line变为M，Core1 的Cache Line变为I。

这样CPU就可以通过CacheLine的状态，来决定是删除缓存，还是直接读取什么的。

# 伪共享 #

背景知识介绍完毕了，这样再说伪共享就不会显得太难以理解了。

先说一个场景：

你的代码里需要使用一个volatile的Bool变量，当做多线程行为的一个开关：

static volatile boolean flag = true;
    
        public static void main(String[] args) {
            for (int i = 0; i < 10; i++) {
                new Thread(() -> {
                    Integer count = 0;
                    while (flag) {
                        ++count;
                        System.out.println(Thread.currentThread().getName() + ":" + count);
                        try {
                            Thread.sleep(100);
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                    }
                }).start();
            }
    
            new Thread(() -> {
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                flag = false;
    
            }).start();
        }

这段代码会声明一个flag为true，然后有10个工作线程会在flag为true时没100ms对count做个自增操作，然后输出。当flag为false时，就会结束线程。

还有一个线程A，会在1000ms后将flag置为false。

这里就是volatile的一个经典用法，可以保证多个线程对flag的可见性，不会因为线程A修改了flag的值，但是工作线程读取到的不是最新值而额外执行一些工作。

这段代码看起来是没有任何问题的，实际上跑起来也没有问题。

但是结合之前的背景知识，考虑一下flag所在的cache line，肯定还会有其他的变量（cache line 64字节，bool无法完整填充一个CacheLine）。

如果flag所在的CacheLine里还有一个频繁修改的共享变量，这时会发生什么？

很简单，就是flag所在的CacheLine被频繁置为不可用，需要清除缓存重新读取。flag在工作状态并没有被修改，但是仍然会被其他频繁修改的共享变量所影响。

这样就会带来一个问题，即使flag并没有被修改，但我们的工作线程很多时间都等于是在主存中读取flag的值，这样在高并发时会带来很大的效率问题。

以上就是所谓的 “FalseSharing” 问题。

# 解决办法 #

FalseSharing对于普通业务应用，基本没什么实际影响。但是对于很多超高并发的中间件（例如发号器），可能就会带来一定的性能瓶颈。所以这类项目都是需要关注这个问题的。

出现原因已经说清楚了，那么该如何解决呢？

其实答案就在文章的开头，那6个看上去没有任何含义的volatile long变量，就是用来解决这个问题的。

> The CPU cache line commonly be 64 bytes, here is a sample of cache line after padding:64 bytes = 8 bytes (object reference) + 6 \* 8 bytes (padded long) + 8 bytes (a long value)

这行注释就说明了这6个变量是如何解决FalseSharing问题的：

CacheLine一般是64字节，64 = 8（对象字节头，32位下8字节）+ 6\*8（long占用8个字节） + 8 （AtomicLong本身带有一个long） 。

写了这6个看着无效的变量后，PaddedAtomicLong就会占用64个字节，正好填满一个CacheLine，这样就会被独自分配到一个CacheLine，这样就不存在FalseSharing问题了。

需要注意的是本来AtomicLong仅占用不到20字节，但是为了解决FalseSharing做了填充之后就占用64字节了，这样就会导致空间会膨胀很多。所以即使用的时候也要做好取舍。

### 伪共享是什么 ###

**CPU Cache**  
众所周知CPU处理速度与硬盘、内存的访问速度相差过大，需要通过CPU缓存进行磨合，否则会导致CPU整体吞吐量受到极大的影响。  
而单一层缓存无论是价格、命中率、查找速度方面都是不能够满足要求的，因此现在很多CPU出现了三级缓存结构，访问速度如下：

![a2bd46a406985f8dcdf157de3f8d9186.png][]

CPU缓存延迟，单位是CPU时钟周期，可以理解为CPU执行一个指令的时间

其中L1是L2的子集，L2是L3的子集，L1到L3缓存容量依次增大，查找耗时依次增大，CPU查找顺序依次是L1、L2、L3、主存。  
L1与CPU core对应，是单核独占的，不会出现其他核修改的问题。一般L2也是单核独占。而L3一般是多核共享，可能操作同一份数据，那么就有可能出问题。

**Cache Line**  
现代CPU读取数据通常以一块连续的块为单位，即缓存行（Cache Line）。所以通常情况下访问连续存储的数据会比随机访问要快，访问数组结构通常比链结构快，因为通常数组在内存中是连续分配的。

> PS. JVM标准并未规定“数组必须分配在连续空间”，一些JVM实现中大数组不是分配在连续空间的。

缓存行的大小通常是64字节，这意味着即使只操作1字节的数据，CPU最少也会读取这个数据所在的连续64字节数据。

**缓存失效**  
根据主流CPU为保证缓存有效性的MESI协议的简单理解，如果一个核正在使用的数据所在的缓存行被其他核修改，那么这个缓存行会失效，需要重新读取缓存。

**False Sharing**  
如果多个核的线程在操作同一个缓存行中的不同变量数据，那么就会出现频繁的缓存失效，即使在代码层面看这两个线程操作的数据之间完全没有关系。  
这种不合理的资源竞争情况学名伪共享（False Sharing），会严重影响机器的并发执行效率。

### 伪共享示例 ###

// 多个线程，每个线程操作一个VolatileLong数组中的元素
    // VolatileLong是否进行填充会影响最终结果
    // 为填充时会产生伪共享问题，运行更慢，填充后不会
    public class FalseShareTest implements Runnable {
        public static int NUM_THREADS = 4;
        public final static long ITERATIONS = 50L * 1000L * 1000L;
        private final int arrayIndex;
        private static VolatileLong[] longs;
        public static long SUM_TIME = 0l;
        public FalseShareTest(final int arrayIndex) {
            this.arrayIndex = arrayIndex;
        }
        public static void main(final String[] args) throws Exception {
            Thread.sleep(10000);
            // 多个线程操作多个VolatileLong
            for(int j=0; j<10; j++){
            // 初始化
                System.out.println(j);
                if (args.length == 1) {
                    NUM_THREADS = Integer.parseInt(args[0]);
                }
                longs = new VolatileLong[NUM_THREADS];
                for (int i = 0; i < longs.length; i++) {
                    longs[i] = new VolatileLong();
                }
                final long start = System.nanoTime();
                // 构造并启动线程
                runTest();
                final long end = System.nanoTime();
                SUM_TIME += end - start;
            }
            System.out.println("平均耗时："+SUM_TIME/10);
        }
        private static void runTest() throws InterruptedException {
            // 创建每个线程， 每个线程操作一个VolatileLong
            Thread[] threads = new Thread[NUM_THREADS];
            for (int i = 0; i < threads.length; i++) {
                threads[i] = new Thread(new FalseShareTest(i));
            }
            for (Thread t : threads) {
                t.start();
            }
            for (Thread t : threads) {
                t.join();
            }
        }
        public void run() {
            long i = ITERATIONS + 1;
            while (0 != --i) {
                longs[arrayIndex].value = i;
            }
        }
        public final static class VolatileLong {
            public volatile long value = 0L;
            public long p1, p2, p3, p4, p5, p6;     // 注释此行，结果区别很大
        }
    }

VolatileLong是否使用6个long变量填充，结果相差很多。  
使用填充，会避免伪共享，速度更快。

### 伪共享如何避免 ###

**Java8以下的版本**  
在Java8以下的版本中，可以使用填充的方式进行避免，比如[百度的snowflake实现][snowflake]中使用的PaddedAtomicLong：

对象头32位下8字节，使用了6个long变量48字节进行填充，以及一个long型的值，一共64字节。  
使用了sumPaddingToPreventOptimization方法规避编译器或GC优化没使用的变量。

**Java8及以上的版本**  
从Java8开始原生支持避免伪共享，可以使用`@Contended`注解：

public class Point { 
        int x;
        @Contended
        int y; 
    }

详见`@Contended`注解使用方法。

> @Contended 注解会增加目标实例大小，要谨慎使用。默认情况下，除了 JDK 内部的类，JVM 会忽略该注解。要应用代码支持的话，要设置 -XX:-RestrictContended=false，它默认为 true（意味仅限 JDK 内部的类使用）。当然，也有个 –XX: EnableContented 的配置参数，来控制开启和关闭该注解的功能，默认是 true，如果改为 false，可以减少 Thread 和 ConcurrentHashMap 类的大小。参加《Java性能权威指南》210 页。

### 参考资料 ###

[伪共享（false sharing），并发编程无声的性能杀手 - 博客园][false sharing_ -]  
[伪共享(False Sharing)和缓存行(Cache Line) 大杂烩 - 简书][False Sharing_Cache Line_ _ -]

[https_blog.csdn.net_z69183787_article_details_108682200]: https://blog.csdn.net/z69183787/article/details/108682200
[https_blog.csdn.net_songfei_dream_article_details_103436061]: https://blog.csdn.net/songfei_dream/article/details/103436061
[https_blog.csdn.net_z69183787_article_details_108682097]: https://blog.csdn.net/z69183787/article/details/108682097
[uid-generator]: https://github.com/baidu/uid-generator
[a2bd46a406985f8dcdf157de3f8d9186.png]: /images/20210527/7dcbc8a763054bb98fbbb3968ced721d.png
[snowflake]: https://links.jianshu.com/go?to=https%3A%2F%2Fgithub.com%2Fbaidu%2Fuid-generator
[false sharing_ -]: https://links.jianshu.com/go?to=https%3A%2F%2Fwww.cnblogs.com%2Fcyfonly%2Fp%2F5800758.html
[False Sharing_Cache Line_ _ -]: https://www.jianshu.com/p/a9b1d32403ea