:mannotop Golang – manno的博客

标签: Golang

关于获取”真“随机数的方法

近期在做的需求涉及到了一个获取真随机数的领域,查找资料Linux内核居然提供了相关的方法,这下可以通过Golang提供的os/exec包去调用内核获取真随机数了。

从Linux内核中获取真随机数

内核随机数产生器

Linux内核实现了一个随机数产生器,从理论上说这个随机数产生器产生的是真随机数。与标准C库中的rand(),srand()产生的伪随机数不同,尽管伪随机数带有一定的随机特征,但这些数字序列并非统计意义上的随机数。也就是说它们是可重现的–只要每次使用相同的seed值,就能得到相同的伪随机数列。通常通过使用time()的返回值来改变seed,以此得到不同的伪随机数序列,但time()返回值的结果并不是不确定的(可预测),也就是这里仍然缺少一个不确定的噪声源。对于需要真随机数的程序,都不能允许使用伪随机数。

为了获得真正意义上的随机数,需要一个外部的噪声源。Linux内核找到了一个完美的噪声源产生者–就是使用计算机的人。我们在使用计算机时敲击键盘的时间间隔,移动鼠标的距离与间隔,特定中断的时间间隔等等,这些对于计算机来讲都是属于非确定的和不可预测的。虽然计算机本身的行为完全由编程所控制,但人对外设硬件的操作具有很大的不确定性,而这些不确定性可以通过驱动程序中注册的中断处理例程(ISR)获取。内核根据这些非确定性的设备事件维护着一个熵池,池中的数据是完全随机的。当有新的设备事件到来,内核会估计新加入的数据的随机性,当我们从熵池中取出数据时,内核会减少熵的估计值。

dev/random与dev/urandom之争?

关于 /dev/urandom 的流言终结

命令使用方法

Using /dev/random, /dev/urandom to generate random data

在Golang中使用

type RandomGenerator struct{}

func (r *RandomGenerator) GetNum() (random int64, err error) {
	//gen num 4 1bytes len uint
	cmd := exec.Command("od", "-vAn", "-N4", "-tu1", "/dev/random")

	outputStr := strings.Builder{}
	stdout, err := cmd.StdoutPipe()
	if err != nil {
		fmt.Println(err)
	}
	if err = cmd.Start(); err != nil {
		fmt.Println(err)
		return
	}
	go func() {
		scr := bufio.NewScanner(stdout)
		for {
			if scr.Scan() {
				fmt.Println(scr.Text())
				outputStr.WriteString(scr.Text())
			}
			if scr.Err() != nil {
				return
			}
		}
	}()
	if err = cmd.Wait(); err != nil {
		fmt.Println(err)
		return
	}

	randomStr := strings.ReplaceAll(outputStr.String(), " ", "")
	//fmt.Printf("randomStr:%v\n", randomStr)

	if len(randomStr) == 0 {
		return r.GetNum()
	}

	random, err = strconv.ParseInt(randomStr, 10, 64)
	if err != nil {
		fmt.Printf("strconv.ParseInt err:%v", err.Error())
		return
	}
	return
}

Go 调度器-网络轮询器

设计原理

网络轮询器不仅用于监控网络 I/O,还能用于监控文件的 I/O,它利用了操作系统提供的 I/O 多路复用模型来提升 I/O 设备的利用率以及程序的性能。本节会分别介绍常见的几种 I/O 模型以及 Go 语言运行时的网络轮询器如何使用多模块设计在不同的操作系统上支持多路复用。

I/O 模型

在神作《UNIX 网络编程》里,总结归纳了 5 种 I/O 模型,包括同步和异步 I/O:

  • 阻塞 I/O (Blocking I/O)
  • 非阻塞 I/O (Nonblocking I/O)
  • I/O 多路复用 (I/O multiplexing)
  • 信号驱动 I/O (Signal driven I/O)
  • 异步 I/O (Asynchronous I/O)

操作系统上的 I/O 是用户空间和内核空间的数据交互,因此 I/O 操作通常包含以下两个步骤:

  1. 等待网络数据到达网卡(读就绪)/等待网卡可写(写就绪) –> 读取/写入到内核缓冲区
  2. 从内核缓冲区复制数据 –> 用户空间(读)/从用户空间复制数据 -> 内核缓冲区(写)

即:读就绪->写就绪->加载数据到内核缓冲区->读->写

而判定一个 I/O 模型是同步还是异步,主要看第二步:数据在用户和内核空间之间复制的时候是不是会阻塞当前进程,如果会,则是同步 I/O,否则,就是异步 I/O。基于这个原则,这 5 种 I/O 模型中只有一种异步 I/O 模型:Asynchronous I/O,其余都是同步 I/O 模型。

这 5 种 I/O 模型的对比如下:

阻塞 I/O

阻塞 I/O 是最常见的 I/O 模型,在默认情况下,当我们通过 read 或者 write 等系统调用读写文件或者网络时,应用程序会被阻塞:

ssize_t read(int fd, void *buf, size_t count);
ssize_t write(int fd, const void *buf, size_t nbytes);

如下图所示,当我们执行 read 系统调用时,应用程序会从用户态陷入内核态,内核会检查文件描述符是否可读;当文件描述符中存在数据时,操作系统内核会将准备好的数据拷贝给应用程序并交回控制权。

blocking-io-mode

图 6-39 阻塞 I/O 模型

操作系统中多数的 I/O 操作都是如上所示的阻塞请求,一旦执行 I/O 操作,应用程序会陷入阻塞等待 I/O 操作的结束。

非阻塞 I/O

非阻塞 I/O,顾名思义就是:所有 I/O 操作都是立刻返回而不会阻塞当前用户进程。I/O 多路复用通常情况下需要和非阻塞 I/O 搭配使用,否则可能会产生意想不到的问题。比如,epoll 的 ET(边缘触发) 模式下,如果不使用非阻塞 I/O,有极大的概率会导致阻塞 event-loop 线程,从而降低吞吐量,甚至导致 bug。

Linux 下,我们可以通过 fcntl 系统调用来设置 O_NONBLOCK 标志位,从而把 socket 设置成 Non-blocking。当对一个 Non-blocking socket 执行读操作时,流程是这个样子:

当用户进程发出 read 操作时,如果 kernel 中的数据还没有准备好,那么它并不会 block 用户进程,而是立刻返回一个 EAGAIN error。从用户进程角度讲 ,它发起一个 read 操作后,并不需要等待,而是马上就得到了一个结果。用户进程判断结果是一个 error 时,它就知道数据还没有准备好,于是它可以再次发送 read 操作。一旦 kernel 中的数据准备好了,并且又再次收到了用户进程的 system call,那么它马上就将数据拷贝到了用户内存,然后返回。

所以,Non-blocking I/O 的特点是用户进程需要不断的主动询问 kernel 数据好了没有。 I/O 多路复用需要和 Non-blocking I/O 配合才能发挥出最大的威力

IO多路复用

所谓IO多路复用就是使用select/poll/epoll这一系列的多路选择器,实现一个线程监控多个文件句柄,一旦某个文件句柄就绪(ready),就能够通知到对应应用程序的读写操作;没有文件句柄就绪时,就会阻塞应用程序,从而释放CPU资源。I/O 复用其实复用的不是 I/O 连接,而是复用线程,让一个 thread of control 能够处理多个连接(I/O 事件)

select&poll

select实现多路复用的方式是,将需要监听的描述符都放到一个文件描述符集合,然后调用select函数将文件描述符集合拷贝到内核里,让内核来检查是否有事件产生,检查的方式很粗暴,就是通过遍历文件描述符集合的方式,当检查到有事件产生后,将此描述符标记为可读或可写,接着再把整个文件描述符集合拷贝回用户态里,然后用户态还需要再通过遍历的方法找到可读或可写的描述符,然后再对其处理。

所以,对于select方式,在时间上,需要进行两遍遍历,一次在内核态,一次在用户态,所以其时间复杂度是O(N);在空间上,会发生两次文件描述符集合的拷贝,一次由用户空间拷贝到内核空间,一次由内核空间拷贝到用户空间,但是由于select使用的是固定长度的bitsmap,默认最多1024个文件描述符。

综上,select 有如下的缺点:

  • 最大并发数限制:使用 32 个整数的 32 位bitsmap,即 32*32=1024 来标识 fd,虽然可修改,但是有以下第 2, 3 点的瓶颈
  • 每次调用 select,都需要把 fd 集合从用户态拷贝到内核态,这个开销在 fd 很多时会很大
  • 性能衰减严重:每次 kernel 都需要线性扫描整个 fd_set,所以随着监控的描述符 fd 数量增长,其 I/O 性能会线性下降

除了标准的 select 之外,操作系统中还提供了一个比较相似的 poll 函数,它使用链表存储文件描述符,摆脱了 1024 的数量上限。

pollselect没有本质区别,只是不再使用bitsmap来存储关注的描述符,而是采用链表的方式存储,突破了文件描述符的个数限制,但是同样需要线性扫描整个链表。随着文件描述符的个数增加,其O(N)的时间复杂度也会使得效率越来越低下。

io-multiplexing

图 6-41 I/O 多路复用函数监听文件描述符

epoll

int s = socket(AF_INET, SOCK_STREAM, 0);
bind(s, ...);
listen(s, ...)

int epfd = epoll_create(...);
epoll_ctl(epfd, ...); // 将所有需要监听的socket添加到epfd中

while(1) {
    int n = epoll_wait(...);
    for(events){
        // 处理逻辑
    }
}

以上是一个很经典的epoll使用逻辑:先用epoll_create创建一个epfd对象,然后通过epoll_ctl将需要监控的文件描述符放到epfd中,最后调用epoll_wait等待数据。

相比于selectpollepoll很好地解决了前二者在时间和空间上效率问题:

  1. epoll在内核中使用红黑树跟踪文件描述符集合,大大缩减了时间,相比于select/poll遍历集合的 O(N) 的时间复杂度,红黑树的时间复杂度是 O(logN)
  2. epoll使用事件驱动的机制(前缀e应该就是event的首字母),当某个文件描述符有消息时,当用户调用epoll_wait函数时,只会返回有事件发生的文件描述符的个数,因此 epoll 的 I/O 性能不会像 select&poll 那样随着监听的 fd 数量增加而出现线性衰减,是一个非常高效的 I/O 事件驱动技术

由于使用 epoll 的 I/O 多路复用需要用户进程自己负责 I/O 读写,从用户进程的角度看,读写过程是阻塞的,所以 select&poll&epoll 本质上都是同步 I/O 模型

多路复用 in GO

GO提供了网络轮询器在不同平台的多种实现

Go 语言在网络轮询器中使用 I/O 多路复用模型处理 I/O 操作,但是他没有选择最常见的系统调用 select2。虽然 select 也可以提供 I/O 多路复用的能力,但是使用它有比较多的限制:

  • 监听能力有限 — 最多只能监听 1024 个文件描述符;
  • 内存拷贝开销大 — 需要维护一个较大的数据结构存储文件描述符,该结构需要拷贝到内核中;
  • 时间复杂度 O(n) — 返回准备就绪的事件个数后,需要遍历所有的文件描述符;

为了提高 I/O 多路复用的性能,不同的操作系统也都实现了自己的 I/O 多路复用函数,例如:epollkqueue 和 evport 等。Go 语言为了提高在不同操作系统上的 I/O 操作性能,使用平台特定的函数实现了多个版本的网络轮询模块

这些模块在不同平台上实现了相同的功能,构成了一个常见的树形结构。编译器在编译 Go 语言程序时,会根据目标平台选择树中特定的分支进行编译:

netpoll-modules

图 6-43 多模块网络轮询器

如果目标平台是 Linux,那么就会根据文件中的 // +build linux 编译指令选择 src/runtime/netpoll_epoll.go 并使用 epoll 函数处理用户的 I/O 操作。

在Linux环境上,Go中的网络轮询器的底层是基于epoll实现的,所以其根本不支持磁盘IO的多路复用,任何磁盘IO的操作都会陷入内核调用

Go netpoller

Go netpoller 通过在底层对 epoll/kqueue/iocp 的封装,从而实现了使用同步编程模式达到异步执行的效果。

总结来说,所有的网络操作都以网络描述符 netFD 为中心实现。netFD 与底层 PollDesc 结构绑定,当在一个 netFD 上读写遇到 EAGAIN 错误时,就将当前 goroutine 存储到这个 netFD 对应的 PollDesc 中,同时调用 gopark 把当前 goroutine 给 park 住,直到这个 netFD 上再次发生读写事件,才将此 goroutine 给 ready 激活重新运行。

显然,在底层通知 被挂起的goroutine 再次发生读写等事件的方式就是 epoll/kqueue/iocp 等事件驱动机制。

client 连接 server 的时候,listener 通过 accept 调用接收新 connection,每一个新 connection 都启动一个 goroutine 处理,accept 调用会把该 connection 的 fd 连带所在的 goroutine 上下文信息封装注册到 epoll 的监听列表里去,当 goroutine 调用 conn.Read 或者 conn.Write 等需要阻塞等待的函数时,会被 gopark 给封存起来并使之休眠,让 P 去执行本地调度队列里的下一个可执行的 goroutine,往后 Go scheduler 会在循环调度的 runtime.schedule() 函数以及 sysmon 监控线程中调用 runtime.netpoll 唤醒的可运行的 goroutine 列表并通过调用 injectglist 把剩下的 g 放入全局调度队列或者当前 P 本地调度队列去重新执行。

当 I/O 事件发生之后,runtime.netpoll 会唤醒那些在 I/O wait 的 goroutine 。

runtime.netpoll 的核心逻辑是:

根据调用方的入参 delay,设置对应的调用 epollwait 的 timeout 值;
调用 epollwait 等待发生了可读/可写事件的 fd;
循环 epollwait 返回的事件列表,处理对应的事件类型, 组装可运行的 goroutine 链表并返回。

Go netpoller的价值

Go netpoller I/O 多路复用搭配 Non-blocking I/O 而打造出来的这个原生网络模型,它最大的价值是把网络 I/O 的控制权牢牢掌握在 Go 自己的 runtime 里。非阻塞 I/O 避免了让操作网络 I/O 的 goroutine 陷入到系统调用从而进入内核态,因为一旦进入内核态,整个程序的控制权就会发生转移(到内核),不再属于用户进程了,那么也就无法借助于 Go 强大的 runtime scheduler 来调度业务程序的并发了。

而有了 netpoll 之后,借助于非阻塞 I/O ,G 就再也不会因为系统调用的读写而 (长时间) 陷入内核态,当 G 被阻塞在某个 network I/O 操作上时,实际上它不是因为陷入内核态被阻塞住了,而是被 Go runtime 主动调用 gopark 给 park 住了,此时 G 会被放置到某个 wait queue 中,而 M 会尝试运行下一个 _Grunnable 的 G,如果此时没有 _Grunnable 的 G 供 M 运行,那么 M 将解绑 P,并进入 sleep 状态。当 I/O available,在 epoll 的 eventpoll.rdr 中等待的 G 会被放到 eventpoll.rdllist 链表里并通过 netpoll 中的 epoll_wait 系统调用返回放置到全局调度队列或者 P 的本地调度队列,标记为 _Grunnable ,等待 P 绑定 M 恢复执行。

Go 调度器-系统监控sysmon

在支持多任务的操作系统中,守护进程是在后台运行的计算机程序,它不会由用户直接操作,它一般会在操作系统启动时自动运行。Kubernetes 的 DaemonSet 和 Go 语言的系统监控都使用类似设计提供一些通用的功能:

golang-system-monitor

main goroutine创建的过程中,runtime会新建一个不在调度中的线程,执行sysmon任务,这个任务也称为系统监控任务,接下来我们就看看这个任务究竟做了什么。

sysmon

func sysmon() {
	sched.nmsys++
	checkdead()

	lasttrace := int64(0)
	idle := 0
	delay := uint32(0)
	for {
		if idle == 0 {
			delay = 20
		} else if idle > 50 {
			delay *= 2
		}
		if delay > 10*1000 {
			delay = 10 * 1000
		}
		usleep(delay)
		...
	}
}

当runtime刚刚调用上述函数时,会先通过 runtime.checkdead 检查是否存在死锁,然后进入核心的监控循环;系统监控在每次循环开始时都会通过 usleep 挂起当前线程,该函数的参数是微秒,运行时会遵循以下的规则决定休眠时间:

  • 初始的休眠时间是 20μs;
  • 最长的休眠时间是 10ms;
  • 当系统监控在 50 个循环中都没有唤醒 Goroutine 时,休眠时间在每个循环都会倍增;

当程序趋于稳定之后,系统监控的触发时间就会稳定在 10ms。它除了会检查死锁之外,还会在循环中完成以下的工作:

  • 检查死锁 — 根据协程状态判断是否退出程序;
  • 运行计时器 — 获取下一个需要被触发的计时器;
  • 轮询网络 — 获取需要处理的到期文件描述符;
  • 抢占处理器 — 抢占运行时间较长的或者处于系统调用的 Goroutine;
  • 垃圾回收 — 在满足条件时触发垃圾收集回收内存;

我们在这一节中会依次介绍系统监控是如何完成上述几种不同工作的。

检查死锁(保证死锁时程序及时退出)

系统监控通过 runtime.checkdead 检查运行时是否发生了死锁,我们可以将检查死锁的过程分成以下三个步骤:

  1. 检查正在运行的线程数量(=0进入下一步);
  2. 检查是否存在正在运行的 Goroutine(不存在进入下一步);
  3. 检查处理器上是否存在计时器(不存在进入下一步);
  4. 报错并退出程序。

该函数首先会检查 Go 语言运行时中正在运行的线程数量,我们通过调度器中的多个字段计算该值的结果:

func checkdead() {
	var run0 int32
	run := mcount() - sched.nmidle - sched.nmidlelocked - sched.nmsys
	if run > run0 {
		return
	}
	if run < 0 {
		print("runtime: checkdead: nmidle=", sched.nmidle, " nmidlelocked=", sched.nmidlelocked, " mcount=", mcount(), " nmsys=", sched.nmsys, "\n")
		throw("checkdead: inconsistent counts")
	}
	...
}
  1. runtime.mcount 根据下一个待创建的线程 id 和释放的线程数得到系统中存在的线程数;
  2. nmidle 是处于空闲状态的线程数量;
  3. nmidlelocked 是处于锁定状态的线程数量;
  4. nmsys 是处于系统调用的线程数量;

利用上述几个线程相关数据,我们可以得到正在运行的线程数,如果线程数量大于 0,说明当前程序不存在死锁;如果线程数小于 0,说明当前程序的状态不一致;如果线程数等于 0,我们需要进一步检查程序的运行状态:

func checkdead() {
	...
	grunning := 0
	for i := 0; i < len(allgs); i++ {
		gp := allgs[i]
		if isSystemGoroutine(gp, false) {
			continue
		}
		s := readgstatus(gp)
		switch s &^ _Gscan {
		case _Gwaiting, _Gpreempted:
			grunning++
		case _Grunnable, _Grunning, _Gsyscall:
			print("runtime: checkdead: find g ", gp.goid, " in status ", s, "\n")
			throw("checkdead: runnable g")
		}
	}
	unlock(&allglock)
	if grunning == 0 {
		throw("no goroutines (main called runtime.Goexit) - deadlock!")
	}
	...
}
  1. 当存在 Goroutine 处于 _Grunnable_Grunning 和 _Gsyscall 状态时,意味着程序发生了死锁;
  2. 当所有的 Goroutine 都处于 _Gidle_Gdead 和 _Gcopystack 状态时,意味着主程序调用了 runtime.goexit

当运行时存在等待的 Goroutine 并且不存在正在运行的 Goroutine 时,我们会检查处理器中存在的计时器:

func checkdead() {
	...
	for _, _p_ := range allp {
		if len(_p_.timers) > 0 {
			return
		}
	}

	throw("all goroutines are asleep - deadlock!")
}

如果处理器中存在等待的计时器,则所有的 Goroutine 陷入休眠状态是合理的,如果不存在等待的计时器,运行时会直接报错并退出程序。

运行计时器(计算下一次唤醒系统监控的时间)

在系统监控的循环中,我们通过 runtime.nanotime 和 runtime.timeSleepUntil 获取当前时间和计时器下一次需要唤醒的时间;当前调度器需要执行垃圾回收或者所有处理器都处于闲置状态时,如果没有需要触发的计时器,那么系统监控可以暂时陷入休眠。

休眠的时间会依据强制 GC 的周期 forcegcperiod 和计时器下次触发的时间确定,runtime.notesleep 会使用信号量同步系统监控即将进入休眠的状态。当系统监控被唤醒之后,我们会重新计算当前时间和下一个计时器需要触发的时间、调用 runtime.noteclear 通知系统监控被唤醒并重置休眠的间隔。

如果在这之后,我们发现下一个计时器需要触发的时间小于当前时间,这也说明所有的线程可能正在忙于运行 Goroutine,系统监控会启动新的线程来触发计时器,避免计时器的到期时间有较大的偏差。

轮询网络(及时将处于就绪状态的 Goroutine 加入全局运行队列)

系统监控会在findrunnable中进行网络轮询器中epollwait的轮询,但是如果上一次轮询网络已经过去了 10ms,那么系统监控还会在循环中轮询网络,检查是否有待执行的文件描述符:

func sysmon() {
	...
	for {
		...
		lastpoll := int64(atomic.Load64(&sched.lastpoll))
		if netpollinited() && lastpoll != 0 && lastpoll+10*1000*1000 < now {
			atomic.Cas64(&sched.lastpoll, uint64(lastpoll), uint64(now))
			list := netpoll(0)
			if !list.empty() {
				incidlelocked(-1)
				injectglist(&list)
				incidlelocked(1)
			}
		}
		...
	}
}

上述函数会非阻塞地调用 runtime.netpoll 检查待执行的文件描述符并通过 runtime.injectglist 将所有处于就绪状态的 Goroutine 加入全局运行队列(因为sysmon没有绑定的P)中:

func injectglist(glist *gList) {
	if glist.empty() {
		return
	}
	lock(&sched.lock)
	var n int
	for n = 0; !glist.empty(); n++ {
		gp := glist.pop()
		casgstatus(gp, _Gwaiting, _Grunnable)
		globrunqput(gp)
	}
	unlock(&sched.lock)
	for ; n != 0 && sched.npidle != 0; n-- {
		startm(nil, false)
	}
	*glist = gList{}
}

该函数会将所有 Goroutine 的状态从 _Gwaiting 切换至 _Grunnable 并加入全局运行队列等待运行,如果当前程序中存在空闲的处理器,会通过 runtime.startm 启动线程来执行这些任务。

抢占处理器(保证协程调度公平、防止饥饿)

系统监控会在循环中调用 runtime.retake 抢占处于运行或者系统调用中的处理器,该函数会遍历运行时的全局处理器,每个处理器都存储了一个 runtime.sysmontick

type sysmontick struct {
	schedtick   uint32
	schedwhen   int64
	syscalltick uint32
	syscallwhen int64
}

该结构体中的四个字段分别存储了处理器的调度次数、处理器上次调度时间、系统调用的次数以及系统调用的时间。runtime.retake 的循环包含了两种不同的抢占逻辑:

func retake(now int64) uint32 {
	n := 0
	for i := 0; i < len(allp); i++ {
		_p_ := allp[i]
		pd := &_p_.sysmontick
		s := _p_.status
		if s == _Prunning || s == _Psyscall {
			t := int64(_p_.schedtick)
			if pd.schedwhen+forcePreemptNS <= now {
				preemptone(_p_)
			}
		}

		if s == _Psyscall {
			if runqempty(_p_) && atomic.Load(&sched.nmspinning)+atomic.Load(&sched.npidle) > 0 && pd.syscallwhen+10*1000*1000 > now {
				continue
			}
			if atomic.Cas(&_p_.status, s, _Pidle) {
				n++
				_p_.syscalltick++
				handoffp(_p_)
			}
		}
	}
	return uint32(n)
}
  1. 当处理器处于 _Prunning 或者 _Psyscall 状态时,如果上一次触发调度的时间已经过去了 10ms,我们会通过 runtime.preemptone 抢占当前处理器;
  2. 当处理器处于 _Psyscall 状态时,在满足以下两种情况下会调用 runtime.handoffp 让出处理器的使用权:
    1. 当处理器的运行队列不为空或者不存在空闲处理器时2
    2. 当系统调用时间超过了 10ms 时3

系统监控通过在循环中抢占处理器来避免同一个 Goroutine 占用线程太长时间造成饥饿问题。

垃圾回收

在最后,系统监控还会决定是否需要触发强制垃圾回收,runtime.sysmon 会构建 runtime.gcTrigger 并调用 runtime.gcTrigger.test 方法判断是否需要触发垃圾回收:

func sysmon() {
	...
	for {
		...
		if t := (gcTrigger{kind: gcTriggerTime, now: now}); t.test() && atomic.Load(&forcegc.idle) != 0 {
			lock(&forcegc.lock)
			forcegc.idle = 0
			var list gList
			list.push(forcegc.g)
			injectglist(&list)
			unlock(&forcegc.lock)
		}
		...
	}
}

如果需要触发垃圾回收,我们会将用于垃圾回收的 Goroutine 加入全局队列,让调度器选择合适的处理器去执行。

小结

运行时通过系统监控来触发线程的抢占、网络的轮询和垃圾回收,保证Go语言运行时的可用性。系统监控能够很好地解决尾延迟的问题,减少调度器调度 Goroutine 的饥饿问题并保证计时器在尽可能准确的时间触发。

几个比官方库效率更高的开源库

本文列出这几个库并不是让你去立刻替换官方库。例如net/http包,实际上它已经可以满足大多数使用场景。

在使用官方库时遇到了问题,我们很容易通过搜索引擎找到解决方案,或者直接向 Go 官方提 issue 。当切换为开源库时,如果遇到了问题,并不一定能及时得到处理。

官方库的 API 几乎可以保证能与 Go 版本的迭代一直兼容,而三方库可能存在潜在的版本兼容问题,这也是切换时需要考虑的问题。

本文列出来的几个开源库,它们的重点都是优化对应官方库的性能问题。我们可以从这些开源库中,学到很多实用的 Go 代码优化技巧。

当然,如果你的项目中因为这些官方库而导致了性能问题,不妨一试。

net/http -> fasthttp

地址:github.com/valyala/fas…

fasthttp号称比net/http快十倍,其优化的核心思路很简单:资源复用。

  • 复用 goroutine,减轻 runtime 调度压力;
  • 对象复用,大量使用 sync.Pool 减轻 GC 压力。

除了复用,还有其他的一些优化手段,例如尽量避免 string 与 []byte 的转换开销等。

这些优化技巧和最佳实践,在其 Github 主页上已经贴心给出:_github.com/valyala/fas…

因为fasthttp的实现与标准库差距较大,所以它与net/http的 API 接口是不同的,这导致从net/http重构为fasthttp需要一些学习成本。

使用fasthttp的知名项目:Fiber、Gearbox、atreugo 等。

encoding/json -> jsoniter

地址:github.com/json-iterat…

jsoniter(json-iterator)是一款快且灵活的 JSON 解析器,同时提供 Java 和 Go 两个版本。官方称 Golang 版本可以比标准库(encoding/json)快 6 倍之多。

image.png 最重要的是,它与标准库encoding/json完全兼容。

  • Marshal()
# encoding/json 
import "encoding/json"json.Marshal(&data)

# jsoniter
import jsoniter "github.com/json-iterator/go"
var json = jsoniter.ConfigCompatibleWithStandardLibrary
json.Marshal(&data)
  • Unmarshal()
# encoding/json
import "encoding/json"
json.Unmarshal(input, &amp;data)

# jsoniter
import jsoniter "github.com/json-iterator/go"
var json = jsoniter.ConfigCompatibleWithStandardLibrary
json.Unmarshal(input, &amp;data)

对其优化原理感兴趣的读者可以看这里:jsoniter.com/benchmark.h…

golang/protobuf -> gogo/protobuf

地址:github.com/gogo/protob…

ProtoBuf 的全称是 Protocol Buffers,它是由 Google 开发和定义的与 XML、JSON 类似的一种协议格式,用于高效存储与读取结构化数据。它基于二进制,因此使用 ProtoBuf 能将数据压缩得更小。

gogo/protobuf是基于官方库golang/protobuf的增强版实现:

  • golang/protobuf更快地序列化与反序列化;
  • 更规范的 Go 结构;
  • 兼容golang/protobuf
  • 可选地生成额外的帮助代码,减少代码输入;
  • 可以生成测试代码和 benchmark 代码;
  • 其他序列化格式;

有很多知名项目都在使用该库,例如 etcd、k8s、docker swarmkit、tidb、nakama 等。

html/template -> valyala/quicktemplate

地址:github.com/valyala/qui…

quicktemplate启发自 Python 的 Mako 项目,是一个快速、强大且易于使用的 Go 模板渲染引擎,它的主要特性如下:

  • quicktemplate会先将编写的模板代码转换为 Go 语言代码,再进行编译渲染。因此,它比标准库html/template快 20 倍以上。
  • quicktemplate的语法与 Go 语法非常类似,几乎没有学习成本。
  • 几乎所有的 bug 都能在模板编译时被捕获,因此在实际项目中,很少会有受模板相关的bug影响。
  • 模板中可以嵌入任意 Go 代码。

虽然quicktemplate的主要目的是生成 HTML,但它也可用于生成其他数据。

例如,使用quicktemplate可以轻松实现 JSON 和 XML 序列化,并且通过quicktemplate的序列化通常也会比通过标准库encoding/jsonencoding/xml更快。

Go 内存管理-内存逃逸分析

学习过C语言的都知道,在C栈区域会存放函数的参数、局部变量等,而这些局部变量的地址是不能返回的,除非是局部静态变量地址,字符串常量地址或者动态分配的地址,因为程序调用完函数后,局部变量会随着此函数的栈帧一起被释放。而对于程序员主动申请的内存则存储在堆上,需要使用malloc等函数进行申请,同时也需要使用free等函数释放,由程序员进行管理,而申请内存后如果没有释放,就有可能造成内存泄漏。

但是在Go中,程序员根本无需感知数据是在栈(Go栈)上,还是在堆上,因为编译器会帮你承担这一切,将内存分配到栈或者堆上。在编译器优化中,逃逸分析是用来决定指针动态作用域的方法。Go语言的编译器使用逃逸分析决定哪些变量应该分配在栈上,哪些变量应该分配在堆上,包括使用newmake和字面量等方式隐式分配的内存,Go语言逃逸分析遵循以下两个不变性:

  1. 指向栈对象的指针不能存在于堆中;
  2. 指向栈对象的指针不能在栈对象回收后存活;

逃逸分析是在编译阶段进行的,可以通过go build -gcflags="-m -m -l"命令查到逃逸分析的结果,最多可以提供4个-m, m 越多则表示分析的程度越详细,一般情况下我们可以采用两个-m分析。使用-l禁用掉内联优化,只关注逃逸优化即可。

1. 几种逃逸分析

1.1 函数返回局部变量的指针

package main

func Add(x, y int) *int {
   res := 0
   res = x + y
   return &res
}

func main() {
   Add(1, 2)
}

逃逸分析结果如下:

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:4:2: res escapes to heap:
./main.go:4:2:   flow: ~r2 = &res:
./main.go:4:2:     from &res (address-of) at ./main.go:6:9
./main.go:4:2:     from return &res (return) at ./main.go:6:2
./main.go:4:2: moved to heap: res
note: module requires Go 1.18

分析结果很明显,函数返回的局部变量是一个指针变量,当函数Add执行结束后,对应的栈帧就会被销毁,引用返回到函数之外,如果在外部解引用这个地址,就会导致程序访问非法内存,所以编译器会经过逃逸分析后在堆上分配内存。

1.2 interface(any)类型逃逸

package main

import (
   "fmt"
)

func main() {
   str := "hello world"
   fmt.Printf("%v\n", str)
}

逃逸分析如下:

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:9:13: str escapes to heap:
./main.go:9:13:   flow: {storage for ... argument} = &{storage for str}:
./main.go:9:13:     from str (spill) at ./main.go:9:13
./main.go:9:13:     from ... argument (slice-literal-element) at ./main.go:9:12
./main.go:9:13:   flow: {heap} = {storage for ... argument}:
./main.go:9:13:     from ... argument (spill) at ./main.go:9:12
./main.go:9:13:     from fmt.Printf("%v\n", ... argument...) (call parameter) at ./main.go:9:12
./main.go:9:12: ... argument does not escape
./main.go:9:13: str escapes to heap

通过这个分析你可能会认为str escapes to heap表示这个str逃逸到了堆,但是却没有上一节中返回值中明确写上moved to heap: res,那实际上str是否真的逃逸到了堆上呢?

escapes to heap vs moved to heap

我们可以写如下代码试试:

package main

import "fmt"

func main() {
   str := "hello world"
   str1 := "nihao!"
   fmt.Printf("%s\n", str)
   println(&str)
   println(&str1)
}

其逃逸分析和上面的没有区别:

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:8:13: str escapes to heap:
./main.go:8:13:   flow: {storage for ... argument} = &{storage for str}:
./main.go:8:13:     from str (spill) at ./main.go:8:13
./main.go:8:13:     from ... argument (slice-literal-element) at ./main.go:8:12
./main.go:8:13:   flow: {heap} = {storage for ... argument}:
./main.go:8:13:     from ... argument (spill) at ./main.go:8:12
./main.go:8:13:     from fmt.Printf("%s\n", ... argument...) (call parameter) at ./main.go:8:12
./main.go:8:12: ... argument does not escape
./main.go:8:13: str escapes to heap
note: module requires Go 1.18

但是,str1str二者的地址却是明显相邻的,那是怎么回事呢?

$ go run main.go
hello world
0xc00009af50
0xc00009af40

如果我们将上述代码的第8行fmt.Printf("%s\n", str)改为fmt.Printf("%p\n", &str),则逃逸分析如下,发现多了一行moved to heap: str

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:6:2: str escapes to heap:
./main.go:6:2:   flow: {storage for ... argument} = &str:
./main.go:6:2:     from &str (address-of) at ./main.go:8:21
./main.go:6:2:     from &str (interface-converted) at ./main.go:8:21
./main.go:6:2:     from ... argument (slice-literal-element) at ./main.go:8:12
./main.go:6:2:   flow: {heap} = {storage for ... argument}:
./main.go:6:2:     from ... argument (spill) at ./main.go:8:12
./main.go:6:2:     from fmt.Printf("%p\n", ... argument...) (call parameter) at ./main.go:8:12
./main.go:6:2: moved to heap: str
./main.go:8:12: ... argument does not escape
note: module requires Go 1.18

再看运行结果,发现看起来str的地址看起来像逃逸到了堆,毕竟和str1的地址明显不同:

$ go run main.go
0xc00010a210
0xc00010a210
0xc000106f50

参考如下解释

When the escape analysis says “b escapes to heap”, it means that the values in b are written to the heap. So anything referenced by b must be in the heap also. b itself need not be.

翻译过来大意是:当逃逸分析输出“b escapes to heap”时,意思是指存储在b中的值逃逸到堆上了,即任何被b引用的对象必须分配在堆上,而b自身则不需要;如果b自身也逃逸到堆上,那么逃逸分析会输出“&b escapes to heap”。

由于字符串本身是存储在只读存储区,我们使用切片更能表现以上的特性。

切片指针和底层数组无逃逸
package main

import (
   "reflect"
   "unsafe"
)

func main() {
   var i int
   i = 10
   println("&i", &i)
   b := []int{1, 2, 3, 4, 5}
   println("&b", &b) // b这个对象的地址
   println("b", unsafe.Pointer((*reflect.SliceHeader)(unsafe.Pointer(&b)).Data)) // b的底层数组地址
}


逃逸分析是:

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:12:12: []int{...} does not escape
note: module requires Go 1.18

打印结果:

$ go run main.go
&i 0xc00009af20
&b 0xc00009af58
b 0xc00009af28

可以看到,以上分析无逃逸,且&i b &b地址连续,可以明显看到都在栈中。

切片底层数组逃逸

我们新增一个fmt包的打印:

package main

import (
   "fmt"
   "reflect"
   "unsafe"
)

func main() {
   var i int
   i = 10
   println("&i", &i)
   b := []int{1, 2, 3, 4, 5}
   println("&b", &b) // b这个对象的地址
   println("b", unsafe.Pointer((*reflect.SliceHeader)(unsafe.Pointer(&b)).Data)) // b的底层数组地址
   fmt.Println(b) // 多加了这行
}

逃逸分析如下:

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:16:13: b escapes to heap:
./main.go:16:13:   flow: {storage for ... argument} = &{storage for b}:
./main.go:16:13:     from b (spill) at ./main.go:16:13
./main.go:16:13:     from ... argument (slice-literal-element) at ./main.go:16:13
./main.go:16:13:   flow: {heap} = {storage for ... argument}:
./main.go:16:13:     from ... argument (spill) at ./main.go:16:13
./main.go:16:13:     from fmt.Println(... argument...) (call parameter) at ./main.go:16:13
./main.go:13:12: []int{...} escapes to heap:
./main.go:13:12:   flow: b = &{storage for []int{...}}:
./main.go:13:12:     from []int{...} (spill) at ./main.go:13:12
./main.go:13:12:     from b := []int{...} (assign) at ./main.go:13:4
./main.go:13:12:   flow: {storage for b} = b:
./main.go:13:12:     from b (interface-converted) at ./main.go:16:13
./main.go:13:12: []int{...} escapes to heap
./main.go:16:13: ... argument does not escape
./main.go:16:13: b escapes to heap
note: module requires Go 1.18

可以发现,出现了b escapes to heap,然后查看打印:

$ go run main.go
&i 0xc000106f38
&b 0xc000106f58
b 0xc000120030
[1 2 3 4 5]

可以发现,b的底层数组发生了逃逸,但是b本身还是在栈中。

切片指针和底层数组都发生逃逸
package main

import (
   "fmt"
   "reflect"
   "unsafe"
)

func main() {
   var i int
   i = 10
   println("&i", &i)
   b := []int{1, 2, 3, 4, 5}
   println("&b", &b) // b这个对象的地址
   println("b", unsafe.Pointer((*reflect.SliceHeader)(unsafe.Pointer(&b)).Data)) // b的底层数组地址
   fmt.Println(&b) // 修改这行
}

如上,将fmt.Println(b)改为fmt.Println(&b),逃逸分析如下:

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:13:2: b escapes to heap:
./main.go:13:2:   flow: {storage for ... argument} = &b:
./main.go:13:2:     from &b (address-of) at ./main.go:16:14
./main.go:13:2:     from &b (interface-converted) at ./main.go:16:14
./main.go:13:2:     from ... argument (slice-literal-element) at ./main.go:16:13
./main.go:13:2:   flow: {heap} = {storage for ... argument}:
./main.go:13:2:     from ... argument (spill) at ./main.go:16:13
./main.go:13:2:     from fmt.Println(... argument...) (call parameter) at ./main.go:16:13
./main.go:13:12: []int{...} escapes to heap:
./main.go:13:12:   flow: b = &{storage for []int{...}}:
./main.go:13:12:     from []int{...} (spill) at ./main.go:13:12
./main.go:13:12:     from b := []int{...} (assign) at ./main.go:13:4
./main.go:13:2: moved to heap: b
./main.go:13:12: []int{...} escapes to heap
./main.go:16:13: ... argument does not escape
note: module requires Go 1.18

发现多了moved to heap: b这行,然后看地址打印:

$ go run main.go
&i 0xc00006af48
&b 0xc00000c030
b 0xc00001a150
&[1 2 3 4 5]

发现不仅底层数组发生了逃逸,连b这个对象本身也发生了逃逸。

所以可以总结下来就是:

  • escapes to heap:表示这个对象里面的指针对象逃逸到堆中;
  • moved to heap:表示对象本身逃逸到堆中,根据指向栈对象的指针不能存在于堆中这一准则,该对象里面的指针对象特必然逃逸到堆中。

1.3 申请栈空间过大

package main

import (
   "reflect"
   "unsafe"
)

func main() {
   var i int
   i = 10
   println("&i", &i)

   b := make([]int, 0)
   println("&b", &b) // b这个对象的地址
   println("b", unsafe.Pointer((*reflect.SliceHeader)(unsafe.Pointer(&b)).Data))

   b1 := make([]byte, 65536)
   println("&b1", &b1) // b1这个对象的地址
   println("b1", unsafe.Pointer((*reflect.SliceHeader)(unsafe.Pointer(&b1)).Data))

   var a [1024*1024*10]byte
   _ = a
}

可以发现逃逸分析显示没有发生逃逸:

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:13:11: make([]int, 0) does not escape
./main.go:17:12: make([]byte, 65536) does not escape
note: module requires Go 1.18

如果将切片和数组的长度都增加1,则会发生逃逸。
逃逸分析:
$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:21:6: a escapes to heap:
./main.go:21:6:   flow: {heap} = &a:
./main.go:21:6:     from a (too large for stack) at ./main.go:21:6
./main.go:17:12: make([]byte, 65537) escapes to heap:
./main.go:17:12:   flow: {heap} = &{storage for make([]byte, 65537)}:
./main.go:17:12:     from make([]byte, 65537) (too large for stack) at ./main.go:17:12
./main.go:21:6: moved to heap: a
./main.go:13:11: make([]int, 0) does not escape
./main.go:17:12: make([]byte, 65537) escapes to heap
note: module requires Go 1.18

可以发现切片类型的逃逸阈值是65536 = 64KB,数组类型的逃逸阈值是1024*1024*10 = 10MB,超过这个数值就会发生逃逸。

1.4 闭包逃逸

package main

func intSeq() func() int {
   i := 0
   return func() int {
      i++
      return i
   }
}

func main() {
    a := intSeq()
    println(a())
    println(a())
    println(a())
    println(a())
    println(a())
    println(a())
}

逃逸分析如下,可以发现闭包中的局部变量i发生了逃逸。

$ go build -gcflags="-m -m -l" ./main.go
# command-line-arguments
./main.go:4:2: intSeq capturing by ref: i (addr=false assign=true width=8)
./main.go:5:9: func literal escapes to heap:
./main.go:5:9:   flow: ~r0 = &{storage for func literal}:
./main.go:5:9:     from func literal (spill) at ./main.go:5:9
./main.go:5:9:     from return func literal (return) at ./main.go:5:2
./main.go:4:2: i escapes to heap:
./main.go:4:2:   flow: {storage for func literal} = &i:
./main.go:4:2:     from i (captured by a closure) at ./main.go:6:3
./main.go:4:2:     from i (reference) at ./main.go:6:3
./main.go:4:2: moved to heap: i
./main.go:5:9: func literal escapes to heap
note: module requires Go 1.18

因为函数也是一个指针类型,所以匿名函数当作返回值时也发生了逃逸,在匿名函数中使用外部变量i,这个变量i会一直存在直到a被销毁,所以i变量逃逸到了堆上。

2. 总结

逃逸到堆上的内存可能会加大GC压力,所以在一些简单的场景下,我们可以避免内存逃逸,使得变量更多地分配在栈上,可以提升程序的性能。比如:

  • 不要盲目地使用指针传参,特别是参数对象很小时,虽然可以减小复制大小,但是可能会造成内存逃逸到堆上,反而降低了代码的效率;
  • 多根据代码具体分析,根据逃逸分析结果做一些优化,提高性能。

Go 内存管理-内存分配器

1. Go内存分配设计原理

Go内存分配器的设计思想来源于TCMalloc,全称是Thread-Caching Malloc,核心思想是把内存分为多级管理,利用缓存的思想提升内存使用效率,降低锁的粒度。

图片来自链接,侵删!

如上图所示,是Go的内存管理模型示意图,在堆内存管理上分为三个内存级别:

  • 线程缓存(MCache):作为线程独立的内存池,与线程的第一交互内存,访问无需加锁;
  • 中心缓存(MCentral):作为线程缓存的下一级,是多个线程共享的,所以访问时需要加锁;
  • 页堆(MHeap):中心缓存的下一级,在遇到32KB以上的对象时,会直接选择页堆分配大内存,而当页堆内存不够时,则会通过系统调用向系统申请内存。

1.1 内存管理基本单元mspan

//go:notinheap
type mspan struct {
   next *mspan     // next span in list, or nil if none
   prev *mspan     // previous span in list, or nil if none
   list *mSpanList // For debugging. TODO: Remove.

   startAddr uintptr // address of first byte of span aka s.base()
   npages    uintptr // number of pages in span
   
   
   freeindex uintptr

   allocBits  *gcBits
   gcmarkBits *gcBits
   allocCache uint64
   ...
}

runtime.mspan是Go内存管理的基本单元,其结构体中包含的nextprev指针,分别指向前后的runtime.mspan,所以其串联后的结构是一个双向链表。

startAddr表示此mspan的起始地址,npages表示管理的页数,每页大小8KB,这个页不是操作系统的内存页,一般是操作系统内存页的整数倍。

其它字段:

  • freeindex — 扫描页中空闲对象的初始索引;
  • allocBits 和 gcmarkBits — 分别用于标记内存的占用和回收情况;
  • allocCache — allocBits 的补码,可以用于快速查找内存中未被使用的内存;

注意使用//go:notinheap标记次结构体mspan为非堆上类型,保证此类型对象不会逃逸到堆上。

图示:

跨度类

mspan中有一个字段spanclass,称为跨度类,是对mspan大小级别的划分,每个mspan能够存放指定范围大小的对象,32KB以内的小对象在Go中,会对应不同大小的内存刻度Size Class,Size Class和Object Size是一一对应的,前者指序号 0、1、2、3,后者指具体对象大小 0B、8B、16B、24B

//go:notinheap
type mspan struct {
   ...
   spanclass   spanClass     // size class and noscan (uint8)
   ...
}

Go 语言的内存管理模块中一共包含 67 种跨度类,每一个跨度类都会存储特定大小的对象并且包含特定数量的页数以及对象,所有的数据都会被预先计算好并存储在runtime.class_to_sizeruntime.class_to_allocnpages等变量中:

classbytes/objbytes/spanobjectstail wastemax waste
1881921024087.50%
2168192512043.75%
3248192341029.24%
4328192256046.88%
54881921703231.52%
6648192128023.44%
78081921023219.07%
6732768327681012.50%

上表展示了对象大小从 8B 到 32KB,总共 67 种跨度类的大小、存储的对象数以及浪费的内存空间,以表中的第四个跨度类为例,跨度类为 5 的runtime.mspan中对象的大小上限为 48 字节、管理 1 个页、最多可以存储 170 个对象。因为内存需要按照页进行管理,所以在尾部会浪费 32 字节的内存,当页中存储的对象都是 33 字节时,最多会浪费 31.52% 的资源:

((48−33)∗170+32)/8192=0.31518((48−33)∗170+32)/8192=0.31518((48−33)∗170+32)/8192=0.31518

除了上述 67 个跨度类之外,运行时中还包含 ID 为 0 的特殊跨度类,它能够管理大于 32KB 的特殊对象。

1.2 线程缓存(mcache)

runtime.mcache是Go语言中的线程缓存,它会与线程上的处理器1:1绑定,用于缓存用户程序申请的微小对象。每一个线程缓存都持有numSpanClasses个(68∗268*268∗2)个mspan,存储在mcachealloc字段中。

其图示如下:

图片来源于链接,侵删!

1.3 中心缓存(mcentral)

每个中心缓存都会管理某个跨度类的内存管理单元,它会同时持有两个runtime.spanSet,分别存储包含空闲对象和不包含空闲对象的内存管理单元,访问中心缓存中的内存管理单元需要使用互斥锁。

//go:notinheap
type mcentral struct {
   spanclass spanClass
   partial [2]spanSet // list of spans with a free object
   full    [2]spanSet // list of spans with no free objects
}

如图上所示,是 runtime.mcentral 中的 spanSet 的内存结构,index 字段是一个uint64类型数字的地址,该uint64的数字按32位分为前后两半部分head和tail,向spanSet中插入和获取mspan有其提供的push和pop函数,以push函数为例,会根据index的head,对spanSetBlock数据块包含的mspan的个数512取商,得到spanSetBlock数据块所在的地址,然后head对512取余,得到要插入的mspan在该spanSetBlock数据块的具体地址。之所以是512,因为spanSet指向的spanSetBlock数据块是一个包含512个mspan的集合。

由全部spanClass规格的runtime.mcentral共同组成的缓存结构如下:

1.4 页堆(mheap)

//go:notinheap
type mheap struct {
   ...
   arenas [1 &lt;&lt; arenaL1Bits]*[1 &lt;&lt; arenaL2Bits]*heapArena
   ...
   central [numSpanClasses]struct {
      mcentral mcentral
      pad      [cpu.CacheLinePadSize - unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize]byte
   }
   ...
}

runtime.mheap是内存分配的核心结构体,其最重要的两个字段如上。

在Go中其被作为全局变量mheap_存储:

var mheap_ mheap

页堆中包含一个长度为numSpanClasses个(68∗268*268∗2)个的runtime.mcentral数组,其中 68 个为跨度类需要 scan 的中心缓存,另外的 68 个是 noscan (没有指针,无需扫描)的中心缓存。

arenas是heapArena的二维数组的集合。如下:

2. 内存分配/释放流程

堆上所有的对象内存分配都会通过runtime.newobject进行分配,运行时根据对象大小将它们分为微对象、小对象和大对象:

  • 微对象(0, 16B):先使用微型分配器,再依次尝试线程缓存、中心缓存和堆分配内存;多个小于16B的无指针微对象的内存分配请求,会合并向Tiny微对象空间申请,微对象的 16B 内存空间从 spanClass 为 4 或 5(无GC扫描)的mspan中获取。
  • 小对象[16B, 32KB]:先向mcache申请,mcache内存空间不够时,向mcentral申请,mcentral不够,则向页堆mheap申请,再不够就向操作系统申请。
  • 大对象(32KB, +∞):大对象直接向页堆mheap申请。

对于内存的释放,遵循逐级释放的策略。当ThreadCache的缓存充足或者过多时,则会将内存退还给CentralCache。当CentralCache内存过多或者充足,则将低命中内存块退还PageHeap。

Go 内存管理-栈空间管理

1. 系统栈和Go栈

1.1 系统线程栈

如果我们在Linux中执行 pthread_create 系统调用,进程会启动一个新的线程,这个栈大小一般为系统的默认栈大小。

对于栈上的内存,程序员无法直接操作,由系统统一管理,一般的函数参数、局部变量(C语言)会存储在栈上。

1.2 Go栈

Go语言在用户空间实现了一套runtime的管理系统,其中就包括了对内存的管理,Go的内存也区分堆和栈,但是需要注意的是,Go栈内存其实是从系统堆中分配的内存,因为同样运行在用户态,Go的运行时也没有权限去直接操纵系统栈。

Go语言使用用户态协程goroutine作为执行的上下文,其使用的默认栈大小比线程栈高的多,其栈空间和栈结构也在早期几个版本中发生过一些变化:

  1. v1.0 ~ v1.1 — 最小栈内存空间为 4KB;
  2. v1.2 — 将最小栈内存提升到了 8KB;
  3. v1.3 — 使用连续栈替换之前版本的分段栈;
  4. v1.4 — 将最小栈内存降低到了 2KB;

2. 栈操作

在前面的《Golang调度器》系列我们也讲过,Go语言中的执行栈由runtime.stack,该结构体中只包含两段字段,分别表示栈的顶部和底部,每个栈结构体都在[lo, hi)的范围内:

type stack struct {
	lo uintptr
	hi uintptr
}

栈的结构虽然非常简单,但是想要理解 Goroutine 栈的实现原理,还是需要我们从编译期间和运行时两个阶段入手:

  1. 为了防止栈空间不足,编译器会在编译阶段会通过cmd/internal/obj/x86.stacksplit在调用函数前插入runtime.morestack或者runtime.morestack_noctxt函数;
  2. 运行时创建新的 Goroutine 时会在runtime.malg中调用runtime.stackalloc申请新的栈内存,并在编译器插入的runtime.morestack中检查栈空间是否充足;

当然,可以在函数头加上//go:nosplit跳过栈溢出检查。

2.1 栈初始化

栈空间运行时中包含两个重要的全局变量,分别是stackpoolstackLarge,这两个变量分别表示全局的栈缓存和大栈缓存,前者可以分配小于 32KB 的内存,后者用来分配大于 32KB 的栈空间

var stackpool [_NumStackOrders]struct {
   item stackpoolItem
   _    [cpu.CacheLinePadSize - unsafe.Sizeof(stackpoolItem{})%cpu.CacheLinePadSize]byte
}

//go:notinheap
type stackpoolItem struct {
   mu   mutex
   span mSpanList
}

// Global pool of large stack spans.
var stackLarge struct {
   lock mutex
   free [heapAddrBits - pageShift]mSpanList // free lists by log_2(s.npages)
}

2.2 栈分配

我们在这里会按照栈的大小分两部分介绍运行时对栈空间的分配。在 Linux 上,_FixedStack = 2048_NumStackOrders = 4_StackCacheSize = 32768,也就是如果申请的栈空间小于 32KB,我们会在全局栈缓存池或者线程的栈缓存中初始化内存:

如果申请的内存空间过大,运行时会查看runtime.stackLarge中是否有剩余的空间,如果不存在剩余空间,它会从堆上申请新的内存。

2.3 栈扩容

在之前我们就提过,编译器会在cmd/internal/obj/x86.stacksplit中为函数调用插入runtime.morestack运行时检查,它会在几乎所有的函数调用之前检查当前 Goroutine 的栈内存是否充足,如果当前栈需要扩容,我们会保存一些栈的相关信息并调用runtime.newstack创建新的栈。

在此期间可能触发抢占。

接下来就是分配新的栈内存和栈拷贝,这里就不详细描述了。

2.4 栈缩容

runtime.shrinkstack栈缩容时调用的函数,该函数的实现原理非常简单,其中大部分都是检查是否满足缩容前置条件的代码,核心逻辑只有以下这几行:

func shrinkstack(gp *g) {
	...
	oldsize := gp.stack.hi - gp.stack.lo
	newsize := oldsize / 2
	if newsize &lt; _FixedStack {
		return
	}
	avail := gp.stack.hi - gp.stack.lo
	if used := gp.stack.hi - gp.sched.sp + _StackLimit; used >= avail/4 {
		return
	}

	copystack(gp, newsize)
}

如果要触发栈的缩容,新栈的大小会是原始栈的一半,不过如果新栈的大小低于程序的最低限制2KB,那么缩容的过程就会停止。

运行时只会在栈内存使用不足1/4时进行缩容,缩容也会调用扩容时使用的runtime.copystack开辟新的栈空间

Go 内存管理-垃圾回收器

source article

The Go garbage collector is responsible for collecting the memory that is not in use anymore. The implemented algorithm is a concurrent tri-color mark and sweep collector. In this article, we will see in detail the marking phase, along with the usage of the different colors.

Go1.3 标记清除法

分下面四步进行

  1. 进行 STW(stop the world 即暂停程序业务逻辑),然后从 main 函数开始找到不可达的内存占用和可达的内存占用
  2. 开始标记,程序找出可达内存占用并做标记
  3. 标记结束清除未标记的内存占用
  4. 结束 STW 停止暂停,让程序继续运行,循环该过程直到 main 生命周期结束

一开始的做法是将垃圾清理结束时才停止 STW,后来优化了方案将清理垃圾放到了 STW 之后,与程序运行同时进行,这样做减小了 STW 的时长。但是 STW 会暂停用户逻辑对程序的性能影响是非常大的,这种粒度的 STW 对于性能较高的程序还是无法接受,因此 Go1.5 采用了三色标记法优化了 STW。

Go1.5 三色标记法

三色标记算法将程序中的对象分成白色、黑色和灰色三类。

白色对象表示暂无对象引用的潜在垃圾,其内存可能会被垃圾收集器回收;

灰色对象表示活跃的对象,黑色到白色的中间状态,因为存在指向白色对象的外部指针,垃圾收集器会扫描这些对象的子对象;

黑色对象表示活跃的对象,包括不存在引用外部指针的对象以及从根对象可达的对象。

三色标记法分五步进行

  1. 将所有对象标记为白色
  2. 从根节点集合出发,将第一次遍历到的节点标记为灰色放入集合列表中
  3. 遍历灰色集合,将灰色节点遍历到的白色节点标记为灰色,并把灰色节点标记为黑色
  4. 循环这个过程
  5. 直到灰色节点集合为空,回收所有的白色节点

这种方法看似很好,但是将 GC 和程序是一起执行的,程序执行过程中可能会更改白色对象的引用关系,导致出现下面这种情况,被引用的对象 3 受到错误的垃圾回收,程序从而出现错误。

因此在此基础上拓展出了俩种方法,强三色不变式和弱三色不变式

  • 强三色不变式:不允许黑色对象引用白色对象
  • 弱三色不变式:黑色对象可以引用白色,白色对象存在其他灰色对象对他的引用,或者他的链路上存在灰色对象

为了实现这俩种不变式的设计思想,从而引出了屏障机制,即在程序的执行过程中加一个判断机制,满足判断机制则执行回调函数。

屏障机制分为插入屏障和删除屏障,插入屏障实现的是强三色不变式,删除屏障则实现了弱三色不变式。值得注意的是为了保证栈的运行效率,屏障只对堆上的内存对象启用,栈上的内存会在 GC 结束后启用 STW 重新扫描。

  • 插入屏障:对象被引用时触发的机制,当白色对象被黑色对象引用时,白色对象被标记为灰色
  • 删除屏障:对象被删除时触发的机制。如果灰色对象引用的白色对象被删除时,那么白色对象会被标记为灰色。(缺点:这种做法回收精度较低,一个对象即使被删除仍可以活过这一轮再下一轮被回收)

上面的屏障保护只发生在堆的对象上。因为性能考虑,栈上的引用改变不会引起屏障触发。

所以栈在 GC 迭代结束时(没有灰色节点),会对栈执行 STW,重新进行扫描清除白色节点。(STW 时间为 10-100ms)

Go1.8 三色标记 + 混合写屏障

基于插入写屏障和删除写屏障在结束时需要 STW 来重新扫描栈,所带来的性能瓶颈,Go 在 1.8 引入了混合写屏障的方式实现了弱三色不变式的设计方式,混合写屏障分下面四步

GC 开始时直接将栈上可达对象全部标记为黑色(不需要二次扫描,无需 STW)

GC 期间,任何栈上创建的新对象均为黑色

被删除引用的对象标记为灰色(无需判断是否被引用)

被添加引用的对象标记为灰色(无需判断是否被引用)

下面为混合写屏障过程

其它

GC的触发时机

触发 GC 有俩个条件,一是堆内存的分配达到控制器计算的触发堆大小,初始大小环境变量 GOGC,之后堆内存达到上一次垃圾收集的 2 倍时才会触发 GC。二是如果一定时间内没有触发,就会触发新的循环,该触发条件由 runtime.forcegcperiod 变量控制,默认为 2 分钟。

Go 内存管理

程序在内存上被分为堆区、栈区、全局数据区、代码段、数据区五个部分。对于 C++ 等早期编程语言栈上的内存由编译器管理回收,堆上的内存空间需要编程人员负责申请与释放。在 Go 中栈上内存仍由编译器负责管理回收,而堆上的内存由编译器和垃圾收集器负责管理回收,给编程人员带来了极大的便利性。

Go语言指针性能

原文链接

引言

本文主要想整理Go语言中值传递和指针传递本质上的区别,这里首席分享William Kennedy的一句话作为总结:

Value semantics keep values on the stack, which reduces pressure on the Garbage Collector (GC). However, value semantics require various copies of any given value to be stored, tracked and maintained. Pointer semantics place values on the heap, which can put pressure on the GC. However, pointer semantics are efficient because only one value needs to be stored, tracked and maintained.

大意可以理解为Golang中,值对象是存储在stack栈内存中的,指针对象是存储在heap堆内存中的,故使用值对象可以减少GC的压力。然而,指针传递的效率在于,存储、跟踪和维护过程中只需要传递一个值。

基于以上的认识,我们用以下例子来试试

结构体定义

以下面一个简单的struct作为示例

type S struct {
   a, b, c int64
   d, e, f string
   g, h, i float64
}

我们分别构建初始化值对象和指针对象的方法

func byValue() S {
   return S{
      a: math.MinInt64, b: math.MinInt64, c: math.MinInt64,
      d: "foo", e: "foo", f: "foo",
      g: math.MaxFloat64, h: math.MaxFloat64, i: math.MaxFloat64,
   }
}

func byPoint() *S {
   return &amp;S{
      a: math.MinInt64, b: math.MinInt64, c: math.MinInt64,
      d: "foo", e: "foo", f: "foo",
      g: math.MaxFloat64, h: math.MaxFloat64, i: math.MaxFloat64,
   }
}

对象传递

内存地址

首先我们来探究在不同的function传递时,值对象和指针对象在内存地址方面有什么不同。我们创建两个function如下:

func TestValueAddress(t *testing.T) {
   nest1 := func() S {
      nest2 := func() S {
         s := byValue()
         fmt.Println("------ nest2 ------")
         fmt.Printf("&amp;a:%v,  &amp;b:%v, &amp;c:%v, &amp;d:%v, &amp;f:%v, &amp;g:%v, &amp;h:%v, &amp;i: %v\n",
            &amp;s.a, &amp;s.b, &amp;s.c, &amp;s.d, &amp;s.f, &amp;s.g, &amp;s.h, &amp;s.i)
         return s
      }
      s := nest2()
      fmt.Println("------ nest1 ------")
      fmt.Printf("&amp;a:%v,  &amp;b:%v, &amp;c:%v, &amp;d:%v, &amp;f:%v, &amp;g:%v, &amp;h:%v, &amp;i: %v\n",
         &amp;s.a, &amp;s.b, &amp;s.c, &amp;s.d, &amp;s.f, &amp;s.g, &amp;s.h, &amp;s.i)
      return s
   }
   s := nest1()
   fmt.Println("------ main ------")
   fmt.Printf("&amp;a:%v,  &amp;b:%v, &amp;c:%v, &amp;d:%v, &amp;f:%v, &amp;g:%v, &amp;h:%v, &amp;i: %v\n",
      &amp;s.a, &amp;s.b, &amp;s.c, &amp;s.d, &amp;s.f, &amp;s.g, &amp;s.h, &amp;s.i)
}

func TestPointAddress(t *testing.T) {
   nest1 := func() *S {
      nest2 := func() *S {
         s := byPoint()
         fmt.Println("------ nest2 ------")
         fmt.Printf("&amp;a:%v,  &amp;b:%v, &amp;c:%v, &amp;d:%v, &amp;f:%v, &amp;g:%v, &amp;h:%v, &amp;i: %v\n",
            &amp;s.a, &amp;s.b, &amp;s.c, &amp;s.d, &amp;s.f, &amp;s.g, &amp;s.h, &amp;s.i)
         return s
      }
      s := nest2()
      fmt.Println("------ nest1 ------")
      fmt.Printf("&amp;a:%v,  &amp;b:%v, &amp;c:%v, &amp;d:%v, &amp;f:%v, &amp;g:%v, &amp;h:%v, &amp;i: %v\n",
         &amp;s.a, &amp;s.b, &amp;s.c, &amp;s.d, &amp;s.f, &amp;s.g, &amp;s.h, &amp;s.i)
      return s
   }
   s := nest1()
   fmt.Println("------ main ------")
   fmt.Printf("&amp;a:%v,  &amp;b:%v, &amp;c:%v, &amp;d:%v, &amp;f:%v, &amp;g:%v, &amp;h:%v, &amp;i: %v\n",
      &amp;s.a, &amp;s.b, &amp;s.c, &amp;s.d, &amp;s.f, &amp;s.g, &amp;s.h, &amp;s.i)
}

两个方法对应的输入如下:

// TestValueAddress输出
------ nest2 ------
&a:0xc00007e2a0,  &b:0xc00007e2a8, &c:0xc00007e2b0, &d:0xc00007e2b8, &f:0xc00007e2d8, &g:0xc00007e2e8, &h:0xc00007e2f0, &i: 0xc00007e2f8
------ nest1 ------
&a:0xc00007e240,  &b:0xc00007e248, &c:0xc00007e250, &d:0xc00007e258, &f:0xc00007e278, &g:0xc00007e288, &h:0xc00007e290, &i: 0xc00007e298
------ main ------
&a:0xc00007e1e0,  &b:0xc00007e1e8, &c:0xc00007e1f0, &d:0xc00007e1f8, &f:0xc00007e218, &g:0xc00007e228, &h:0xc00007e230, &i: 0xc00007e238

// TestPointAddress输出
------ nest2 ------
&a:0xc00007e1e0,  &b:0xc00007e1e8, &c:0xc00007e1f0, &d:0xc00007e1f8, &f:0xc00007e218, &g:0xc00007e228, &h:0xc00007e230, &i: 0xc00007e238
------ nest1 ------
&a:0xc00007e1e0,  &b:0xc00007e1e8, &c:0xc00007e1f0, &d:0xc00007e1f8, &f:0xc00007e218, &g:0xc00007e228, &h:0xc00007e230, &i: 0xc00007e238
------ main ------
&a:0xc00007e1e0,  &b:0xc00007e1e8, &c:0xc00007e1f0, &d:0xc00007e1f8, &f:0xc00007e218, &g:0xc00007e228, &h:0xc00007e230, &i: 0xc00007e238

由此我们可知,值对象由于是分配在栈内存上的,所以他的生命周期跟随func:当function执行完毕时,对应function内部的对象也会被销毁被重新copy到新的栈内存;指针对象由于是分配在堆内存中的,即便function执行完毕,栈内存被清理也不会改变其分配的内存地址,而是由GC统一管理。

故值对象在不同的func中传递时,势必会引起栈内存中的copy

性能

然后让我们来看,仅在一个func中,值对象和指针对象的性能如何。

通过创建Benchmark以追踪他在循环中的性能:

func BenchmarkValueCopy(b *testing.B) {
   var s S
   out, _ := os.Create("value.out")
   _ = trace.Start(out)

   for i := 0; i &lt; b.N; i++ {
      s = byValue()
   }

   trace.Stop()
   b.StopTimer()
   _ = fmt.Sprintf("%v", s.a)
}

func BenchmarkPointCopy(b *testing.B) {
   var s *S
   out, _ := os.Create("point.out")
   _ = trace.Start(out)

   for i := 0; i &lt; b.N; i++ {
      s = byPoint()
   }

   trace.Stop()
   b.StopTimer()
   _ = fmt.Sprintf("%v", s.a)
}

然后执行以下语句

go test -bench=BenchmarkValueCopy -benchmem -run=^$ -count=10 > value.txt
go test -bench=BenchmarkPointCopy -benchmem -run=^$ -count=10 > point.txt

benchmark stat如下:

// value.txt
BenchmarkValueCopy-8       225915150           5.287 ns/op          0 B/op         0 allocs/op
BenchmarkValueCopy-8       225969075           5.348 ns/op          0 B/op         0 allocs/op
BenchmarkValueCopy-8       224717500           5.441 ns/op          0 B/op         0 allocs/op
...

// point.txt
BenchmarkPointCopy-8       22525324           47.25 ns/op          96 B/op         1 allocs/op
BenchmarkPointCopy-8       25844391           46.27 ns/op          96 B/op         1 allocs/op
BenchmarkPointCopy-8       25628395           46.02 ns/op          96 B/op         1 allocs/op
...

由此可以看出,值对象的初始化比指针对象初始化要快

然后我们通过trace日志来看看具体的原因,使用以下命令:

go tool trace value.out
go tool trace point.out

value.png value.out

point.png point.out

经过trace日志可以看出,值对象在执行过程中没有GC且没有额外的goroutines;指针对象总共GC 967次。

方法执行

创建基于值对象和指针对象的空function如下:

func (s S) value(s1 S) {}

func (s *S) point(s1 *S) {}

对应的Benchmark如下:

func BenchmarkValueFunction(b *testing.B) {
   var s S
   var s1 S

   s = byValue()
   s1 = byValue()
   for i := 0; i &lt; b.N; i++ {
      for j := 0; j &lt; 1000000; j++  {
         s.value(s1)
      }
   }
}

func BenchmarkPointFunction(b *testing.B) {
   var s *S
   var s1 *S

   s = byPoint()
   s1 = byPoint()
   for i := 0; i &lt; b.N; i++ {
      for j := 0; j &lt; 1000000; j++  {
         s.point(s1)
      }
   }
}

Benchmark stat如下:

// value
BenchmarkValueFunction-8            160      7339292 ns/op

// point
BenchmarkPointFunction-8            480      2520106 ns/op

由此可以看到,在方法执行过程中,指针对象是优于值对象的。

数组

下面我们尝试构建一个值对象数组和指针对象数组,即[]S和[]*S

func BenchmarkValueArray(b *testing.B) {
   var s []S
   out, _ := os.Create("value_array.out")
   _ = trace.Start(out)

   for i := 0; i &lt; b.N; i++ {
      for j := 0; j &lt; 1000000; j++ {
         s = append(s, byValue())
      }
   }

   trace.Stop()
   b.StopTimer()
}

func BenchmarkPointArray(b *testing.B) {
   var s []*S
   out, _ := os.Create("point_array.out")
   _ = trace.Start(out)

   for i := 0; i &lt; b.N; i++ {
      for j := 0; j &lt; 1000000; j++ {
         s = append(s, byPoint())
      }
   }

   trace.Stop()
   b.StopTimer()
}

获取到的benchmark stat如下

// value array   []S
BenchmarkValueArray-8             2    542506184 ns/op   516467388 B/op       83 allocs/op
BenchmarkValueArray-8             2    532587916 ns/op   516469084 B/op       85 allocs/op
BenchmarkValueArray-8             3    501410289 ns/op   538334434 B/op       57 allocs/op

// point array   []*S
BenchmarkPointArray-8             8    232675024 ns/op   145332278 B/op  1000022 allocs/op
BenchmarkPointArray-8            10    181305981 ns/op   145321713 B/op  1000018 allocs/op
BenchmarkPointArray-8             8    329801938 ns/op   145331643 B/op  1000021 allocs/op

然后是用trace日志看看具体的GC和Goroutines的情况:

go tool trace value_array.out
go tool trace point_array.out

value_array.png value_array.out

point_array.png point_array.out

通过以上的日志可知,[]S相较于[]*S仍然有更少的GC和Goroutines,但是在实际的运行速度中,尤其是需要值传递的情况,[]*S还是优于[]S的。此外,在使用[]S修改其中某一项的值的时候会存在问题,如下

// bad case
func TestValueArrayChange(t *testing.T) {
   var s []S
   for i := 0; i &lt; 10; i++ {
      s = append(s, byValue())
   }

   for _, v := range s {
      v.a = 1
   }

   // assert failed
   // Expected :int64(1)
  // Actual   :int64(-9223372036854775808)
   assert.Equal(t, int64(1), s[0].a)
}

// good case
func TestPointArrayChange(t *testing.T) {
   var s []*S
   for i := 0; i &lt; 10; i++ {
      s = append(s, byPoint())
   }

   for _, v := range s {
      v.a = 1
   }

   // assert success
   assert.Equal(t, int64(1), s[0].a)
}

总结

如同一开始所说的,值对象是跟随func存储在栈内存中的,指针对象是存储在堆内存中的。

对于值对象来说,当func结束时,栈内的值对象也会跟着从一个栈复制到另一个栈;同时存储在栈内存中意味着更少的GC和Goroutines。

对于指针对象来说,在堆内存中存储无异会增加GC和Goroutines,但是在func中传递指针对象时,仅需要传递指针即可。

综上,对于仅在方法内使用的对象,或想跨方法传递的一些小的对象,那么可以使用值对象来提升效率和减少GC;但是如果需要传递大对象,或者跨越更多方法来传递对象,那么最好还是使用指针对象来传递。

GO编程模式:MAP-REDUCE

在本篇文章中,我们学习一下函数式编程的中非常重要的Map、Reduce、Filter的三种操作,这三种操作可以让我们非常方便灵活地进行一些数据处理——我们的程序中大多数情况下都是在到倒腾数据,尤其对于一些需要统计的业务场景,Map/Reduce/Filter是非常通用的玩法。下面先来看几个例子:

基本示例

Map示例

下面的程序代码中,我们写了两个Map函数,这两个函数需要两个参数,

  • 一个是字符串数组 []string,说明需要处理的数据一个字符串
  • 另一个是一个函数func(s string) string 或 func(s string) int
func MapStrToStr(arr []string, fn func(s string) string) []string {
    var newArray = []string{}
    for _, it := range arr {
        newArray = append(newArray, fn(it))
    }
    return newArray
}

func MapStrToInt(arr []string, fn func(s string) int) []int {
    var newArray = []int{}
    for _, it := range arr {
        newArray = append(newArray, fn(it))
    }
    return newArray
}

整个Map函数运行逻辑都很相似,函数体都是在遍历第一个参数的数组,然后,调用第二个参数的函数,然后把其值组合成另一个数组返回。

于是我们就可以这样使用这两个函数:

var list = []string{"Hao", "Chen", "MegaEase"}

x := MapStrToStr(list, func(s string) string {
    return strings.ToUpper(s)
})
fmt.Printf("%v\n", x)
//["HAO", "CHEN", "MEGAEASE"]

y := MapStrToInt(list, func(s string) int {
    return len(s)
})
fmt.Printf("%v\n", y)
//[3, 4, 8]

我们可以看到,我们给第一个 MapStrToStr() 传了函数做的是 转大写,于是出来的数组就成了全大写的,给MapStrToInt() 传的是算其长度,所以出来的数组是每个字符串的长度。

我们再来看一下Reduce和Filter的函数是什么样的。

Reduce:

func Reduce(arr []string, fn func(s string) int) int {
    sum := 0
    for _, it := range arr {
        sum += fn(it)
    }
    return sum
}

var list = []string{"Hao", "Chen", "MegaEase"}

x := Reduce(list, func(s string) int {
    return len(s)
})
fmt.Printf("%v\n", x)
// 15

Filter:

func Filter(arr []int, fn func(n int) bool) []int {
    var newArray = []int{}
    for _, it := range arr {
        if fn(it) {
            newArray = append(newArray, it)
        }
    }
    return newArray
}

var intset = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
out := Filter(intset, func(n int) bool {
   return n%2 == 1
})
fmt.Printf("%v\n", out)

out = Filter(intset, func(n int) bool {
    return n > 5
})
fmt.Printf("%v\n", out)

下图是一个比喻,其非常形象地说明了Map-Reduce是的业务语义,其在数据处理中非常有用。

业务示例

通过上面的一些示例,你可能有一些明白,Map/Reduce/Filter只是一种控制逻辑,真正的业务逻辑是在传给他们的数据和那个函数来定义的。是的,这是一个很经典的“业务逻辑”和“控制逻辑”分离解耦的编程模式,Golang中常用的sort包中也采用了这种设计模式实现了sort.Slice()方法。下面我们来看一个有业务意义的代码,来让大家强化理解一下什么叫“控制逻辑”与业务逻辑分离。

首先,我们定义一个员工对象,以及一些数据:

type Employee struct {
    Name     string
    Age      int
    Vacation int
    Salary   int
}

var list = []Employee{
    {"Hao", 44, 0, 8000},
    {"Bob", 34, 10, 5000},
    {"Alice", 23, 5, 9000},
    {"Jack", 26, 0, 4000},
    {"Tom", 48, 9, 7500},
    {"Marry", 29, 0, 6000},
    {"Mike", 32, 8, 4000},
}

然后,我们有如下的几个函数:

func EmployeeCountIf(list []Employee, fn func(e *Employee) bool) int {
    count := 0
    for i, _ := range list {
        if fn(&list[i]) {
            count += 1
        }
    }
    return count
}

func EmployeeFilterIn(list []Employee, fn func(e *Employee) bool) []Employee {
    var newList []Employee
    for i, _ := range list {
        if fn(&list[i]) {
            newList = append(newList, list[i])
        }
    }
    return newList
}

func EmployeeSumIf(list []Employee, fn func(e *Employee) int) int {
    var sum = 0
    for i, _ := range list {
        sum += fn(&list[i])
    }
    return sum
}

简单说明一下:

  • EmployeeConutIf 和 EmployeeSumIf 分别用于统满足某个条件的个数或总数。它们都是Filter + Reduce的语义。
  • EmployeeFilterIn 就是按某种条件过虑。就是Fitler的语义。

于是我们就可以有如下的代码:

1)统计有多少员工大于40岁

old := EmployeeCountIf(list, func(e *Employee) bool {
    return e.Age > 40
})
fmt.Printf("old people: %d\n", old)
//old people: 2

2)统计有多少员工薪水大于6000

high_pay := EmployeeCountIf(list, func(e *Employee) bool {
    return e.Salary >= 6000
})
fmt.Printf("High Salary people: %d\n", high_pay)
//High Salary people: 4

3)列出有没有休假的员工

no_vacation := EmployeeFilterIn(list, func(e *Employee) bool {
    return e.Vacation == 0
})
fmt.Printf("People no vacation: %v\n", no_vacation)
//People no vacation: [{Hao 44 0 8000} {Jack 26 0 4000} {Marry 29 0 6000}]

4)统计所有员工的薪资总和

total_pay := EmployeeSumIf(list, func(e *Employee) int {
    return e.Salary
})

fmt.Printf("Total Salary: %d\n", total_pay)
//Total Salary: 43500

5)统计30岁以下员工的薪资总和

younger_pay := EmployeeSumIf(list, func(e *Employee) int {
    if e.Age < 30 {
        return e.Salary
    } 
    return 0
})

泛型Map-Reduce

我们可以看到,上面的Map-Reduce都因为要处理数据的类型不同而需要写出不同版本的Map-Reduce,虽然他们的代码看上去是很类似的。所以,这里就要带出来泛型编程了,目前的Go语言的泛型只能用 interface{} + reflect来完成。

下面我们来看一下一个非常简单不作任何类型检查的泛型的Map函数怎么写:

func Map(data interface{}, fn interface{}) []interface{} {
    vfn := reflect.ValueOf(fn)
    vdata := reflect.ValueOf(data)
    result := make([]interface{}, vdata.Len())

    for i := 0; i < vdata.Len(); i++ {
        result[i] = vfn.Call([]reflect.Value{vdata.Index(i)})[0].Interface()
    }
    return result
}

上面的代码中,

  • 通过 reflect.ValueOf() 来获得 interface{} 的值,其中一个是数据 vdata,另一个是函数 vfn
  • 然后通过 vfn.Call() 方法来调用函数,通过 []refelct.Value{vdata.Index(i)}来获得数据。

于是,我们就可以有下面的代码——不同类型的数据可以使用相同逻辑的Map()代码:

square := func(x int) int {
  return x * x
}
nums := []int{1, 2, 3, 4}

squared_arr := Map(nums,square)
fmt.Println(squared_arr)
//[1 4 9 16]



upcase := func(s string) string {
  return strings.ToUpper(s)
}
strs := []string{"Hao", "Chen", "MegaEase"}
upstrs := Map(strs, upcase);
fmt.Println(upstrs)
//[HAO CHEN MEGAEASE]

但是因为反射是运行时的事,所以,如果类型什么出问题的话,就会有运行时的错误。

健壮版的Generic Map

所以,如果要写一个健壮的程序,对于这种用interface{} 的“过度泛型”,就需要我们自己来做类型检查。下面是一个有类型检查的Map代码(分为是否就地计算两个版本):

func Transform(slice, function interface{}) interface{} {
  return transform(slice, function, false)
}

func TransformInPlace(slice, function interface{}) interface{} {
  return transform(slice, function, true)
}

func transform(slice, function interface{}, inPlace bool) interface{} {
 
  //check the <code data-enlighter-language="raw" class="EnlighterJSRAW">slice</code> type is Slice
  sliceInType := reflect.ValueOf(slice)
  if sliceInType.Kind() != reflect.Slice {
    panic("transform: not slice")
  }

  //check the function signature
  fn := reflect.ValueOf(function)
  elemType := sliceInType.Type().Elem()
  if !verifyFuncSignature(fn, elemType, nil) {
    panic("trasform: function must be of type func(" + sliceInType.Type().Elem().String() + ") outputElemType")
  }

  sliceOutType := sliceInType
  if !inPlace {
    sliceOutType = reflect.MakeSlice(reflect.SliceOf(fn.Type().Out(0)), sliceInType.Len(), sliceInType.Len())
  }
  for i := 0; i < sliceInType.Len(); i++ {
    sliceOutType.Index(i).Set(fn.Call([]reflect.Value{sliceInType.Index(i)})[0])
  }
  return sliceOutType.Interface()

}

func verifyFuncSignature(fn reflect.Value, types ...reflect.Type) bool {

  //Check it is a funciton
  if fn.Kind() != reflect.Func {
    return false
  }
  // NumIn() - returns a function type's input parameter count.
  // NumOut() - returns a function type's output parameter count.
  if (fn.Type().NumIn() != len(types)-1) || (fn.Type().NumOut() != 1) {
    return false
  }
  // In() - returns the type of a function type's i'th input parameter.
  for i := 0; i < len(types)-1; i++ {
    if fn.Type().In(i) != types[i] {
      return false
    }
  }
  // Out() - returns the type of a function type's i'th output parameter.
  outType := types[len(types)-1]
  if outType != nil && fn.Type().Out(0) != outType {
    return false
  }
  return true
}

上面的代码一下子就复杂起来了,可见,复杂的代码都是在处理异常的地方。我不打算Walk through 所有的代码,别看代码多,但是还是可以读懂的,下面列几个代码中的要点:

  • 代码中没有使用Map函数,因为和数据结构和关键有含义冲突的问题,所以使用Transform,这个来源于 C++ STL库中的命名。
  • 有两个版本的函数,一个是返回一个全新的数组 – Transform(),一个是“就地完成” – TransformInPlace()
  • 在主函数中,用 Kind() 方法检查了数据类型是不是 Slice,函数类型是不是Func
  • 检查函数的参数和返回类型是通过 verifyFuncSignature() 来完成的,其中:
    • NumIn() – 用来检查函数的“入参”
    •  NumOut() 用来检查函数的“返回值”
  • 如果需要新生成一个Slice,会使用 reflect.MakeSlice() 来完成。

好了,有了上面的这段代码,我们的代码就很可以很开心的使用了:

可以用于字符串数组:

list := []string{"1", "2", "3", "4", "5", "6"}
result := Transform(list, func(a string) string{
    return a +a +a
})
//{"111","222","333","444","555","666"}

可以用于整形数组:

list := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
TransformInPlace(list, func (a int) int {
  return a*3
})
//{3, 6, 9, 12, 15, 18, 21, 24, 27}

可以用于结构体:

var list = []Employee{
    {"Hao", 44, 0, 8000},
    {"Bob", 34, 10, 5000},
    {"Alice", 23, 5, 9000},
    {"Jack", 26, 0, 4000},
    {"Tom", 48, 9, 7500},
}

result := TransformInPlace(list, func(e Employee) Employee {
    e.Salary += 1000
    e.Age += 1
    return e
})

同样,泛型版的 Reduce 代码如下:

func Reduce(slice, pairFunc, zero interface{}) interface{} {
  sliceInType := reflect.ValueOf(slice)
  if sliceInType.Kind() != reflect.Slice {
    panic("reduce: wrong type, not slice")
  }

  len := sliceInType.Len()
  if len == 0 {
    return zero
  } else if len == 1 {
    return sliceInType.Index(0)
  }

  elemType := sliceInType.Type().Elem()
  fn := reflect.ValueOf(pairFunc)
  if !verifyFuncSignature(fn, elemType, elemType, elemType) {
    t := elemType.String()
    panic("reduce: function must be of type func(" + t + ", " + t + ") " + t)
  }

  var ins [2]reflect.Value
  ins[0] = sliceInType.Index(0)
  ins[1] = sliceInType.Index(1)
  out := fn.Call(ins[:])[0]

  for i := 2; i < len; i++ {
    ins[0] = out
    ins[1] = sliceInType.Index(i)
    out = fn.Call(ins[:])[0]
  }
  return out.Interface()
}

泛型版的 Filter 代码如下:

func Filter(slice, function interface{}) interface{} {
  result, _ := filter(slice, function, false)
  return result
}

func FilterInPlace(slicePtr, function interface{}) {
  in := reflect.ValueOf(slicePtr)
  if in.Kind() != reflect.Ptr {
    panic("FilterInPlace: wrong type, " +
      "not a pointer to slice")
  }
  _, n := filter(in.Elem().Interface(), function, true)
  in.Elem().SetLen(n)
}

var boolType = reflect.ValueOf(true).Type()

func filter(slice, function interface{}, inPlace bool) (interface{}, int) {

  sliceInType := reflect.ValueOf(slice)
  if sliceInType.Kind() != reflect.Slice {
    panic("filter: wrong type, not a slice")
  }

  fn := reflect.ValueOf(function)
  elemType := sliceInType.Type().Elem()
  if !verifyFuncSignature(fn, elemType, boolType) {
    panic("filter: function must be of type func(" + elemType.String() + ") bool")
  }

  var which []int
  for i := 0; i < sliceInType.Len(); i++ {
    if fn.Call([]reflect.Value{sliceInType.Index(i)})[0].Bool() {
      which = append(which, i)
    }
  }

  out := sliceInType

  if !inPlace {
    out = reflect.MakeSlice(sliceInType.Type(), len(which), len(which))
  }
  for i := range which {
    out.Index(i).Set(sliceInType.Index(which[i]))
  }

  return out.Interface(), len(which)
}

使用反射来做这些东西,会有一个问题,那就是代码的性能会很差。所以,上面的代码不能用于你需要高性能的地方