计算机组成-无锁编程追求极致性能

前言

​ 现代计算机通常由 CPU ，以及主板、内存、硬盘等主要硬件结构组成，而决定计算机性能的最核心部件是 CPU +内存， CPU 负责处理程序指令，内存负责存储指令执行结果。在这个工作机制当中 CPU 的读写效率其实是远远高于内存的，为提升执行效率减少 CPU 与内存的交互，一般在 CPU 上设计了缓存结构，常见的为三级缓存结构：

• L1 Cache，分为数据缓存和指令缓存，逻辑核独占
• L2 Cache，物理核独占，逻辑核共享
• L3 Cache，所有物理核共享

下图为 CPU-Core(TM)I7-10510U 型号缓存结构

存储器存储空间大小：内存>L3>L2>L1>寄存器。

存储器速度快慢排序：寄存器>L1>L2>L3>内存。

缓存行大小

[root@192 ~]# getconf -a|grep CACHE
LEVEL1_ICACHE_SIZE                 32768 #L1缓存大小
LEVEL1_ICACHE_ASSOC                8 #L1缓存行大小
LEVEL1_ICACHE_LINESIZE             64
LEVEL1_DCACHE_SIZE                 32768
LEVEL1_DCACHE_ASSOC                8
LEVEL1_DCACHE_LINESIZE             64
LEVEL2_CACHE_SIZE                  262144 #L2缓存大小
LEVEL2_CACHE_ASSOC                 4
LEVEL2_CACHE_LINESIZE              64 #L2缓存行大小
LEVEL3_CACHE_SIZE                  8388608 #L3缓存大小
LEVEL3_CACHE_ASSOC                 16
LEVEL3_CACHE_LINESIZE              64 #L3缓存行大小
LEVEL4_CACHE_SIZE                  0
LEVEL4_CACHE_ASSOC                 0
LEVEL4_CACHE_LINESIZE              0
[root@192 ~]# cat /proc/cpuinfo |grep -i cache
cache size    : 8192 KB
cache_alignment    : 64
cache size    : 8192 KB
cache_alignment    : 64

JAVA程序毫无疑问也必须是运行在硬件机器之上，如何利用底层硬件工作原理，提升性能也必然是我们需要考虑的，笔者今天以无锁并发高性能框架 Disruptor 为例分析如何高效的利用CPU缓存。

Who is Disruptor?

​ Disruptor是一个开源框架，研发的初衷是为了解决高并发下 队列 锁的问题，最早由LMAX（一种新型零售金融交易平台）提出并使用，能够在 无锁 的情况下实现队列的并发操作，并号称能够在一个线程里每秒处理6百万笔订单。

缓存行填充

下方示例为 Disruptor 框架的内部代码：

abstract class RingBufferPad
{
    protected long p1, p2, p3, p4, p5, p6, p7;
}

分析：

1. 变量p1~p7本身没有实际意义，只能用于 缓存行填充 ，为了尽可能地用上 CPU Cache ！

2. 访问CPU里的L1 Cache或者L2 Cache、L3 Cache，访问延时是内存的1/15乃至1/100（内存的访问速度，是远远慢于CPU Cache的）

   • 因此，为了追求极限性能，需要尽可能地从 CPU Cache 里面读取数据

3. CPU Cache装载内存里面的数据，不是一个个字段加载的，而是加载一整个缓存行

   • 64位的Intel CPU，缓存行通常是 64 Bytes ，一个long类型的数据需要8 Bytes，因此会一下子加载8个long类型的数据

• 

  • 遍历数组元素速度很快，后面连续7次的数据访问都会命中CPU Cache，不需要重新从内存里面去读取数据

缓存行失效

p1-p7仅用来填充缓存行，我们跟本用不到它，但是我们为什么要填充满一个缓存行呢？

1. CPU在加载数据的时候，会把这个数据从 内存 加载到 CPU Cache 里面

2. 此时，CPU Cache里面除了这个数据，还会加载这个数据 前后定义 的其他变量

   • 释义：在高并发场景下，假定并发访问变量p0，在p0后定义的其它变量也一并会被缓存load

3. Disruptor是一个 多线程 的服务器框架，在这个数据前后定义的其他变量，可能会被多个不同的线程去更新数据，读取数据

   • 这些写入和读取请求，可能会来自于 不同的CPU Core
   • 为了保证数据的 同步更新 ，不得不把CPU Cache里面的数据， 重新写回 到内存里面或者 重新 从内存里面 加载
   • CPU Cache的 写回 和 加载 ，都是以整个 Cache Line 作为单位的
4. 如果常量的缓存失效，当再次读取这个值的时候，需要重新从 内存 读取，读取速度会大大 变慢

缓存行填充

abstract class RingBufferPad
{
    protected long p1, p2, p3, p4, p5, p6, p7;
}

abstract class RingBufferFields<E> extends RingBufferPad
{
    ...
    private final long indexMask;
    private final Object[] entries;
    protected final int bufferSize;
    protected final Sequencer sequencer;
    ...
}

public final class RingBuffer<E> extends RingBufferFields<E> implements Cursored, EventSequencer<E>, EventSink<E>
{
    ...
    protected long p1, p2, p3, p4, p5, p6, p7;
    ...
}

1. Disruptor在 RingBufferFields 里面定义的变量前后分别定义了7个long类型的变量

   • 前面7个 继承 自 RingBufferPad ，后面7个直接 定义 在 RingBuffer 类中
   • 这14个变量 没有任何实际用途 ，既不会去 读 ，也不会去 写

2. RingBufferFields 里面定义的变量都是 final 的，第一次写入之后就不会再进行修改

   • 一旦被加载到CPU Cache之后，只要被 频繁地读取访问 ，就 不会被换出CPU Cache
   • 无论在内存的什么位置，这些 变量所在的Cache Line 都不会有任何 写更新 的请求

空间局部性+分支预测

1. Disruptor整个框架是一个高速的生产者-消费者模型下的队列

   • 生产者不停地往队列里面生产新的需要处理的任务
   • 消费者不停地从队列里面处理掉这些任务
2. 要实现一个 队列 ，最合适的数据结构应该是 链表 ，如Java中的 LinkedBlockingQueue

3. Disruptor并没有使用LinkedBlockingQueue，而是使用了RingBuffer的数据结构

   • RingBuffer 的底层实现是一个 固定长度的数组

   • 比起链表形式的实现，数组的数据在内存里面会存在空间局部性

     • 数组的连续多个元素会一并加载到CPU Cache里面，所以访问遍历的速度会更快
     • 链表 里面的各个节点的数据， 多半不会出现在相邻的内存空间

   • 数据的遍历访问还有一个很大的优势，就是CPU层面的分支预测会很准确

     • 可以更有效地利用CPU里面的 多级流水线

CAS无锁

锁对性能的影响

1. Disruptor作为一个高性能的生产者-消费者队列系统，一个核心的设计：通过 RingBuffer 实现一个 无锁队列

2. Java里面的 LinkedBlockingQueue ，比起Disruptor的RingBuffer要慢很多，主要原因

   • 链表 的数据在内存里面的布局对于 高速缓存 并 不友好

   • LinkedBlockingQueue 对于锁的依赖

     • 一般来说消费者比生产者快（不然队列会 堆积 ），因为大部分时候，队列是 空 的，生产者和消费者一样会产生 竞争

3. LinkedBlockingQueue 的锁机制是通过 ReentrantLock ，需要JVM进行裁决

   • 锁的争夺，会把没有拿到锁的线程 挂起等待 ，也需要进行一次 上下文切换

   • 上下文切换的过程，需要把当前执行线程的寄存器等信息，保存到内存中的线程栈里面

     • 意味：已经加载到 高速缓存 里面的指令或者数据，又回到 主内存 里面，进一步拖慢性能

RingBuffer 无锁方案

1. 加锁很慢，所以Disruptor的解决方案是 无锁 （没有 操作系统 层面的锁）
2. Disruptor利用了一个 CPU硬件支持的指令 ，称之为 CAS （Compare And Swap）

3. Disruptor的RingBuffer创建一个 Sequence 对象，用来指向当前的RingBuffer的头和尾

   • 头和尾的标识，不是通过一个指针来实现的，而是通过一个 序号

4. RingBuffer在进行生产者和消费者之间的资源协调，采用的是对比序号的方式

   • 当生产者想要往队列里面加入新数据的时候，会把当前生产者的Sequence的序号，加上需要加入的新数据的数量

   • 然后和实际的消费者所在的位置进行对比，看下队列里是不是有足够的空间加入这些数据

     • 而不是直接 覆盖 掉消费者还没处理完的数据

5. CAS指令，既不是基础库里的一个函数，也不是操作系统里面实现的一个系统调用，而是一个CPU硬件支持的机器指令

   • 在Intel CPU上，为 cmpxchg 指令： compxchg [ax] (隐式参数，EAX累加器), [bx] (源操作数地址), [cx] (目标操作数地址)
   • 第一个操作数不在指令里面出现，是一个隐式的操作数，即 EAX累加寄存器 里面的值
   • 第二个操作数就是源操作数，指令会对比这个操作数和上面EAX累加寄存器里面的值
   • 伪代码： IF [ax]== [bx] THEN [ZF] = 1, [bx] = [cx] ELSE [ZF] = 0, [ax] = [bx]
   • 单个指令是 原子 的，意味着使用CAS操作的时候， 不需要单独进行加锁 ，直接调用即可

Sequence关键代码 如下：

public long addAndGet(final long increment)
{
    long currentValue;
    long newValue;

    // 如果CAS操作没有成功，会不断等待重试
    do
    {
        currentValue = get();
        newValue = currentValue + increment;
    }
    while (!compareAndSet(currentValue, newValue));

    return newValue;
}

public boolean compareAndSet(final long expectedValue, final long newValue)
{
    // 调用CAS指令
    return UNSAFE.compareAndSwapLong(this, VALUE_OFFSET, expectedValue, newValue);
}

Benchmark

互斥锁竞争、CAS乐观锁与无锁测试：

public class LockBenchmark {

    private static final long MAX = 500_000_000L;

    private static void runIncrement() {
        long counter = 0;
        long start = System.currentTimeMillis();
        while (counter < MAX) {
            counter++;
        }
        long end = System.currentTimeMillis();
        System.out.println("Time spent is " + (end - start) + "ms without lock");
    }

    private static void runIncrementWithLock() {
        Lock lock = new ReentrantLock();
        long counter = 0;
        long start = System.currentTimeMillis();
        while (counter < MAX) {
            if (lock.tryLock()) {
                counter++;
                lock.unlock();
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("Time spent is " + (end - start) + "ms with lock");
    }

    private static void runIncrementAtomic() {
        AtomicLong counter = new AtomicLong(0);
        long start = System.currentTimeMillis();
        while (counter.incrementAndGet() < MAX) {
        }
        long end = System.currentTimeMillis();
        System.out.println("Time spent is " + (end - start) + "ms with cas");
    }

    public static void main(String[] args) {
        runIncrement();
        runIncrementWithLock();
        runIncrementAtomic();

        // Time spent is 153ms without lock
        // Time spent is 7801ms with lock
        // Time spent is 3164ms with cas
        // 7801 / 153 ≈ 51
        // 3164 / 153 ≈ 21   
    }
}得出

结论：无锁性能要远高于cas与lock，cas要大于lock

更多好文章，请关注公众号：奇客时间，原创JAVA架构技术栈社区