/lockfree

lockfree queue

Primary LanguageGoApache License 2.0Apache-2.0

Lockfree

如果想使用低于go1.18版本则可以引入tag:1.0.9或branch:below-version1.18

通过条件编译支持386平台,但性能测试发现比较差,因此不建议使用

1. 简介

1.1. 为什么要写Lockfree

在go语言中一般都是使用chan作为消息传递的队列,但在实际高并发的环境下使用发现chan存在严重的性能问题,其直接表现就是将对象放入到chan中时会特别耗时, 即使chan的容量尚未打满,在严重时甚至会产生几百ms还无法放入到chan中的情况。

放大.jpg

1.2. chan基本原理

1.2.1. chan基本结构

chan关键字在编译阶段会被编译为runtime.hchan结构,它的结构如下所示:

chan结构.jpg

其中sudog是一个比较常见的结构,是对goroutine的一个封装,它的主要结构:

sudog.jpg

1.2.2. chan写入流程

write.jpg

1.2.3. chan读取流程

read.jpg

1.3. 锁

1.3.1. runtime.mutex

chan结构中包含了一个lock字段:lock mutex。 这个lock看名字就知道是一个锁,当然它不是我们业务中经常使用的sync.Mutex,而是一个runtime.mutex。 这个锁是一个互斥锁,在linux系统中它的实现是futex,在没有竞争的情况下,会退化成为一个自旋操作,速度非常快,但是当竞争比较大时,它就会在内核中休眠。

futex的基本原理如下图: futex.jpg

当竞争非常大时,对于chan而言其整体大部分时间是出于系统调用上,所以性能下降非常明显。

1.3.2. sync.Mutex

sync.Mutex包中的设计原理如下图:

锁.jpg

2. Lockfree基本原理

2.1. 模块及流程

在最新的设计中已经删除了available模块,转而使用ringBuffer中的对象(e)中的c(游标)标识写入状态。

lockfree.jpg

2.2. 优化点

1) 无锁实现

内部所有操作都是通过原子变量(atomic)来操作,唯一有可能使用锁的地方,是提供给用户在RingBuffer为空时的等待策略,用户可选择使用chan阻塞

2) 单一消费协程

屏蔽掉消费端读操作竞争带来的性能损耗

3) 写不等待原则

符合写入快的初衷,当无法写入时会持续通过自旋和任务调度的方式处理,一方面尽量加快写入效率,另一方面则是防止占用太多CPU资源

4) 泛型加速

引入泛型,泛型与interface有很明显的区别,泛型是在编译阶段确定类型,这样可有效降低在运行时进行类型转换的耗时

5) 一次性内存分配

环状结构Ringbuffer实现对象的传递,通过确定大小的切片实现,只需要分配一次内存,不会涉及扩容等操作,可有效提高处理的性能

6) 运算加速

RingBuffer的容量为2的n次方,通过与运算来代替取余运算,提高性能

7) 并行位图

用原子位运算实现位图并行操作,在尽量不影响性能的条件下,降低内存消耗

并行位图的思路实现历程:

bitmap.jpg

8) 缓存行填充

根据CPU高速缓存的特点,通过填充缓存行方式屏蔽掉伪共享问题。

缓存行填充应该是一个比较常见的问题,它的本质是因为CPU比较快,而内存比较慢,所以增加了高速缓存来处理:

padding1.jpg

在两个Core共享同一个L3的情况下,如果同时进行修改,就会出现竞争关系(会涉及到缓存一致性协议:MESI):

padding2.jpg

在Lockfree中有两个地方用到了填充:

padding3.jpg

最新版本中只保留了cursor中的填充,在e中使用了游标。

9) Pointer替代切片

屏蔽掉切片操作必须要进行越界判断的逻辑,生成更高效机器码。

pointer.jpg

2.3. 核心模块

ringBuffer

具体对象的存放区域,通过数组(定长切片)实现环状数据结构,其中的数据对象是具体的结构体而非指针,这样可以一次性进行内存申请。

stateDescriptor

注:最新的版本已将该对象删除,通过ringBuffer中e中的游标来描述状态。这样更充分利用了内存,降低了消耗。

状态描述符,定义了对应位置的数据状态,是可读还是可写。提供了三种方式:

    1. 基于Uint32的切片:每个Uint32值描述一个位置,性能最高,但内存消耗最大;
    1. 基于Bitmap:每个bit描述一个位置,性能最低,但内存消耗最小;
    1. 基于Uint8的切片:每个Uint8值描述一个位置,性能适中,消耗也适中,最推荐的方式。
sequencer

序号产生器,维护读和写两个状态,写状态具体由内部游标(cursor)维护,读取状态由自身维护,一个uint64变量维护。它的核心方法是next(),用于获取下个可以写入的游标。

Producer

生产者,核心方法是Write,通过调用Write方法可以将对象写入到队列中。支持多个g并发操作,保证加入时处理的效率。

consumer

消费者,这个消费者只会有一个g操作,这样处理的好处是可以不涉及并发操作,其内部不会涉及到任何锁,对于实际的并发操作由该g进行分配。

blockStrategy

阻塞策略,该策略用于buf中长时间没有数据时,消费者阻塞设计。它有两个方法:block()和release()。前者用于消费者阻塞,后者用于释放。 系统提供了多种方式,不同的方式CPU资源占用和性能会有差别:

    1. SchedBlockStrategy:调用runtime.Gosched()进行调度block,不需要release,为推荐方式;
    1. SleepBlockStrategy:调用time.Sleep(x)进行block,可自定义休眠时间,不需要release,为推荐方式;
    1. ProcYieldBlockStrategy:调用CPU空跑指令,可自定义空跑的指令数量,不需要release;
    1. OSYieldBlockStrategy:操作系统会将对应M调度出去,等时间片重新分配后可执行,不需要release;
    1. ChanBlockStrategy:chan阻塞策略,需要release,为推荐方式;
    1. CanditionBlockStrategy:candition阻塞策略,需要release,为推荐方式;

其中1/2/5/6为推荐方式,如果性能要求比较高,则优先考虑2和1,否则建议试用5和6。

EventHandler

事件处理器接口,整个项目中唯一需要用户实现的接口,该接口描述消费端收到消息时该如何处理,它使用泛型,通过编译阶段确定事件类型,提高性能。

3. 使用方式

3.1. 导入模块

可使用 go get github.com/bruceshao/lockfree 获取最新版本

3.2. 代码调用

为了提升性能,Lockfree支持go版本1.18及以上,以便于支持泛型,Lockfree使用非常简单:

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
	"time"

	"github.com/bruceshao/lockfree"
)

var (
	goSize    = 10000
	sizePerGo = 10000

	total = goSize * sizePerGo
)

func main() {
	// lockfree计时
	now := time.Now()

	// 创建事件处理器
	handler := &eventHandler[uint64]{
		signal: make(chan struct{}, 0),
		now:    now,
	}

	// 创建消费端串行处理的Lockfree
	lf := lockfree.NewLockfree[uint64](
		1024*1024,
		handler,
		lockfree.NewSleepBlockStrategy(time.Millisecond),
	)

	// 启动Lockfree
	if err := lf.Start(); err != nil {
		panic(err)
	}

	// 获取生产者对象
	producer := lf.Producer()

	// 并发写入
	var wg sync.WaitGroup
	wg.Add(goSize)
	for i := 0; i < goSize; i++ {
		go func(start int) {
			for j := 0; j < sizePerGo; j++ {
				err := producer.Write(uint64(start*sizePerGo + j + 1))
				if err != nil {
					panic(err)
				}
			}
			wg.Done()
		}(i)
	}

	// wait for producer
	wg.Wait()

	fmt.Printf("producer has been writed, write count: %v, time cost: %v \n", total, time.Since(now).String())

	// wait for consumer
	handler.wait()

	// 关闭Lockfree
	lf.Close()
}

type eventHandler[T uint64] struct {
	signal   chan struct{}
	gcounter uint64
	now      time.Time
}

func (h *eventHandler[T]) OnEvent(v uint64) {
	cur := atomic.AddUint64(&h.gcounter, 1)
	if cur == uint64(total) {
		fmt.Printf("eventHandler has been consumed already, read count: %v, time cose: %v\n", total, time.Since(h.now))
		close(h.signal)
		return
	}

	if cur%10000000 == 0 {
		fmt.Printf("eventHandler consume %v\n", cur)
	}
}

func (h *eventHandler[T]) wait() {
	<-h.signal
}

4. 性能对比

4.1. 简述

在实际测试中发现,如果lockfree和chan同时跑的话会有一些影响,lockfree的表现基本是正常的,和chan同时跑的时候性能基本是下降的。 但chan比较奇怪,和lockfree一起跑的时候性能比chan自身跑性能还高。目前正在排查此问题,但不影响使用。

main包下提供了测试的程序,可自行进行性能测试(假设编译后的二进制为lockfree):

  • 1)单独测试lockfree:./lockfree lockfree [time],加入time会有时间分布;
  • 2)单独测试chan:./lockfree chan [time],加入time会有时间分布;
  • 3)合并测试lockfree和chan:./lockfree [all] [time],使用time时,前面必须加all参数,只进行测试,不关注时间分布的话,可直接调用./lockfree;

为描述性能,除了时间外,定义了QR(Quick Ratio,快速率)的指标,该指标描述的是写入时间在1微秒以内的操作占所有操作的比值。 自然的,QR越大,性能越高。

4.2. 软硬件测试环境

CPU信息如下(4 * 2.5GHz):

[root@VM]# lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
Thread(s) per core:    1
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 94
Model name:            Intel(R) Xeon(R) Gold 6133 CPU @ 2.50GHz
Stepping:              3
CPU MHz:               2494.120
BogoMIPS:              4988.24
Hypervisor vendor:     KVM
Virtualization type:   full
L1d cache:             32K
L1i cache:             32K
L2 cache:              4096K
L3 cache:              28160K
NUMA node0 CPU(s):     0-3

内存信息(8G):

[root@VM]# free -m 
              total        used        free      shared  buff/cache   available
Mem:           7779         405        6800         116         573        7216
Swap:             0           0           0

操作系统(centos 7.2):

[root@VM]# cat /etc/centos-release 
CentOS Linux release 7.2 (Final)
[root@VM]# uname -a
Linux VM-219-157-centos 3.10.107-1-tlinux2_kvm_guest-0056 #1 SMP Wed Dec 29 14:35:09 CST 2021 x86_64 x86_64 x86_64 GNU/Linux

云厂商:腾讯云。

4.3. 写入性能对比

设定buffer大小为1024 * 1024,无论是lockfree还是chan都是如此设置。其写入的时间对比如下:

其中 100 * 10000表示有100个goroutine,每个goroutine写入10000次,其他的依次类推。

all(lockfree/chan)表示在lockfree和chan同时跑的情况下,其分别的时间占比情况。

类型 100 * 10000 500 * 10000 1000 * 10000 5000 * 10000 10000 * 10000
lockfree 67ms 306ms 676ms 3779ms 7703ms
chan 116ms 1991ms 4709ms 26897ms 58509ms
all(lockfree) 49ms 414ms 976ms 5038ms 10946ms
all(chan) 83ms 859ms 3029ms 19228ms 40473ms

4.4. QR分布

快速率的分布情况如下所示:

类型 100 * 10000 500 * 10000 1000 * 10000 5000 * 10000 10000 * 10000
lockfree 99.23 99.78 99.81 99.49 98.99
chan 91.67 88.99 57.79 3.98 1.6
all(lockfree) 99.69 99.88 99.88 99.52 99.02
all(chan) 96.72 93.5 93.1 51.37 48.2

4.5. 结果

从上面两张表可以很明显看出如下几点:

  • 1)在goroutine数量比较小时,lockfree和chan性能差别不明显;
  • 2)当goroutine打到一定数量(大于1000)后,lockfree无论从时间还是QR都远远超过chan;