Golang 常见问题

Go 结构体是否可以比较,为什么?

Go 的结构体是否可以比较,需要视具体情况而定,在某些情况下是可以比较的,而某些情况下比较会不符合预期,甚至直接报错。

先来看看几个例子:

例子一

type Value struct {
    Name   string
    Gender string
}

func main() {
    v1 := Value{Name: "煎鱼", Gender: "男"}
    v2 := Value{Name: "煎鱼", Gender: "男"}
    if v1 == v2 {
        fmt.Println("脑子进煎鱼了")
        return
    }

    fmt.Println("脑子没进煎鱼")
}

声明了两个变量,分别是 v1 和 v2。其都是 Value 结构体的实例化,是同一个结构体的两个实例。

输出结果:

脑子进煎鱼了

在这里,结构体是可比较的。

例子二

接下来继续改造上面的例子,在原本的结构体中增加了指针类型的引用。

第二个例子如下:

type Value struct {
    Name   string
    Gender *string
}

func main() {
    v1 := Value{Name: "煎鱼", Gender: new(string)}
    v2 := Value{Name: "煎鱼", Gender: new(string)}
    if v1 == v2 {
        fmt.Println("脑子进煎鱼了")
        return
    }

    fmt.Println("脑子没进煎鱼")
}

这段程序输出的结果是:脑子没进煎鱼。

例子三

再尝试 string 数组类型:

type Value struct {
    Name   string
    GoodAt []string
}

func main() {
    v1 := Value{Name: "煎鱼", GoodAt: []string{"炸", "煎", "蒸"}}
    v2 := Value{Name: "煎鱼", GoodAt: []string{"炸", "煎", "蒸"}}
    if v1 == v2 {
        fmt.Println("脑子进煎鱼了")
        return
    }

    fmt.Println("脑子没进煎鱼")
}

这里程序会直接报错:

# command-line-arguments
./main.go:15:8: invalid operation: v1 == v2 (struct containing []string cannot be compared)

例子四

那不同结构体,相同的值内容呢,能否进行比较?

type Value1 struct {
    Name string
}

type Value2 struct {
    Name string
}
func main() {
    v1 := Value1{Name: "煎鱼"}
    v2 := Value2{Name: "煎鱼"}
    if v1 == v2 {
        fmt.Println("脑子进煎鱼了")
        return
    }

    fmt.Println("脑子没进煎鱼")
}

显然,这种情况是会直接报错:

# command-line-arguments
./main.go:18:8: invalid operation: v1 == v2 (mismatched types Value1 and Value2)

那是不是就完全没法比较了呢?并不,可以借助强制转换来实现:

if v1 == Value1(v2) {
  fmt.Println("脑子进煎鱼了")
  return
 }

这样程序就会正常运行,且输出 “脑子进煎鱼了”。当然,若是不可比较类型,依然是不行的。

分析

为什么 Go 结构体有的比较就是正常,有的就不行,甚至还直接报错了。难道是有什么 “潜规则” 吗?

在 Go 语言中,Go 结构体有时候并不能直接比较,当其基本类型包含:slice、map、function 时,是不能比较的。若强行比较,就会导致出现例子中的直接报错的情况。

而指针引用,其虽然都是 new(string),从表象来看是一个东西,但其具体返回的地址是不一样的。

因此若要比较,则需改为:

func main() {
    gender := new(string)
    v1 := Value{Name: "煎鱼", Gender: gender}
    v2 := Value{Name: "煎鱼", Gender: gender}
    ...
}

这样就可以保证两者的比较。如果被迫无奈,被要求一定要用结构体比较怎么办?

这时候可以使用反射方法 reflect.DeepEqual,如下:

func main() {
    v1 := Value{Name: "煎鱼", GoodAt: []string{"炸", "煎", "蒸"}}
    v2 := Value{Name: "煎鱼", GoodAt: []string{"炸", "煎", "蒸"}}
    if reflect.DeepEqual(v1, v2) {
        fmt.Println("脑子进煎鱼了")
        return
    }

    fmt.Println("脑子没进煎鱼")
}

例子五

再看一种特殊的例子:

type People struct {}

func main() {
 a := &People{}
 b := &People{}
 fmt.Println(a == b)
}

这里的输出结果是: false。

再稍加改造一下:

type People struct {}

func main() {
 a := &People{}
 b := &People{}
 fmt.Printf("%p\n", a)
 fmt.Printf("%p\n", b)
 fmt.Println(a == b)
}

输出结果是:true。

综合以上,总结的一个例子:

func main() {
 a := new(struct{})
 b := new(struct{})
 println(a, b, a == b)

 c := new(struct{})
 d := new(struct{})
 fmt.Println(c, d)
 println(c, d, c == d)
}

输出的结果如下:

// a, b; a == b
0xc00005cf57 0xc00005cf57 false

// c, d
&{} &{}
// c, d, c == d
0x118c370 0x118c370 true

第一段代码的结果是 false,第二段的结果是 true,且可以看到内存地址指向的完全一样,也就是排除了输出后变量内存指向改变导致的原因。

进一步来看,似乎是 fmt.Print 方法导致的,但一个标准库里的输出方法,会导致这种奇怪的问题?

这里其实跟内存的逃逸有关,对例子进行逃逸分析:

// 源代码结构
$ cat -n main.go
     5 func main() {
     6  a := new(struct{})
     7  b := new(struct{})
     8  println(a, b, a == b)
     9 
    10  c := new(struct{})
    11  d := new(struct{})
    12  fmt.Println(c, d)
    13  println(c, d, c == d)
    14 }

// 进行逃逸分析
$ go run -gcflags="-m -l" main.go
# command-line-arguments
./main.go:6:10: a does not escape
./main.go:7:10: b does not escape
./main.go:10:10: c escapes to heap
./main.go:11:10: d escapes to heap
./main.go:12:13: ... argument does not escape

通过分析可得知变量 a, b 均是分配在栈中,而变量 c, d 分配在堆中。

其关键原因是因为调用了 fmt.Println 方法,该方法内部是涉及到大量的反射相关方法的调用,会造成逃逸行为,也就是分配到堆上。

关注第一个细节,就是 “为什么逃逸后,两个空 struct 会是相等的?

这里主要与 Go runtime 的一个优化细节有关,如下:

// runtime/malloc.go
var zerobase uintptr

变量 zerobase 是所有 0 字节分配的基础地址。更进一步来讲,就是空(0字节)的在进行了逃逸分析后,往堆分配的都会指向 zerobase 这一个地址。

所以空 struct 在逃逸后本质上指向了 zerobase,其两者比较就是相等的,返回了 true。

为什么没逃逸不相等

关注第二个细节,就是 “为什么没逃逸前,两个空 struct 比较不相等?”。

这里其实是 Golang 团队有意而为之:

This is an intentional language choice to give implementations flexibility in how they handle pointers to zero-sized objects. If every pointer to a zero-sized object were required to be different, then each allocation of a zero-sized object would have to allocate at least one byte. If every pointer to a zero-sized object were required to be the same, it would be different to handle taking the address of a zero-sized field within a larger struct.

Pointers to distinct zero-size variables may or may not be equal.

因此 Go 团队这番操作,与 Go map 的随机性如出一辙,避免大家对这类逻辑的直接依赖,是值得思考的。

而在没逃逸的场景下,两个空 struct 的比较动作,你以为是真的在比较。实际上已经在代码优化阶段被直接优化掉,转为了 false。

因此,虽然在代码上看上去是 == 在做比较,实际上结果是 a == b 时就直接转为了 false,比都不需要比了。

既然我们知道了他是在代码优化阶段被优化的,那么相对的,知道了原理的我们也可以借助在 go 编译运行时的 gcflags 指令,让他不优化。

在运行前面的例子时,执行 -gcflags="-N -l" 指令:

$ go run -gcflags="-N -l" main.go 
0xc000092f06 0xc000092f06 true
&{} &{}
0x118c370 0x118c370 true

这时候,两个比较的结果都是 true 了。

Golang 语言有什么优缺点

Java 有非常多优点,一直到现在都具有统治力。但是站在微服务角度,它有一些固有缺点,比如说资源开销。并行时资源开销越低,意味着部署密度越高,计算成本越低。而 Java 在运行过程中,要花费较多资源进行 JIT 编译。另外,JVM 本身要占用大概五六十兆左右的内存,而在微服务中,内存不能超卖超售,所以相对来说,JVM 本身占用的内存比较多。另外,JVM 还要占用大概一两百兆左右的磁盘,对于分布式架构的微服务来说,会影响分发部署速度。此外,Java 的启动速度也一直比较令人诟病,对于需要快速迭代和回滚的微服务来说,启动速度慢会影响交付效率和快速回滚,也有可能让用户感受到访问延迟。当然,Java 也一直在优化。比如说 CDS,还有这几年开始兴起的静态编译。 – 《字节大规模微服务语言发展之路》主题分享

Golang 的优势

“设计编程语言一直有两个目标,一个是让编程越来越容易,另外一个就是在新的硬件架构出现以后,可以充分利用硬件特质,发挥更高性能。”

Golang 就是让编程越来越容易的一种语言,它在开发效率和性能之间取得了比较好的平衡。

Golang 有很多优点。

首先,它从语言层面上支持高并发。它自带了 Goroutine、也就是协程,可以比较充分地利用多核的性能,让程序员更容易使用并发。

其次,它非常简单易学,并且开发效率非常高。Go 的关键字只有 25 个,对比一下 C11,大概有 40 多个关键字。虽然 Go 的关键字数量更少,但是表达能力很强大,几乎支持大多数其他语言里一些比较好用的特性。

它的编译速度也非常快。

Golang 存在的问题

Golang 作为一个开源语言,而且 Go team 的核心成员也曾公开表示 Go 完全开源,并且也积极拥抱社区,但是,社区内一直有这样一个说法:“Go 是 Google 的 Go,而不是社区的 Go”。比较典型的一个故事就是 Go 的 module 的发展历史,或者说它的上位史。一般来说,Go 的发展一直被 Google 的 Go Team 核心团队牢牢把控,外界的声音、社区的声音,对 Go 语言的发展来说似乎没那么重要,也就是说,外界很难主导设计一个完整的特性。

另外一个问题是,随着微服务越来越庞大,包括单个微服务越来越大,以及部署微服务的容器数量也越来越大,达到一定的程度之后,会遇到越来越多性能方面的问题。

此外还有一个问题,微服务数量上来之后,会遇到一些观测问题。

性能问题

随着单个微服务本身大小的增加,以及部署微服务的机器数量越来越多,会遇到越来越多的性能问题。这些性能问题,可以分为以下三个方面:

  • 一个是 GC,这是属于内存管理的一个问题;
  • 一个是编译生成代码的质量问题。
  • 另外一个是性能观测问题

GC 问题

内存管理包括了内存分配和垃圾回收两个方面,对于 Go 来说,GC 是一个并发 - 标记 - 清除(CMS)算法收集器。但是需要注意一点,Go 在实现 GC 的过程当中,过多地把重心放在了暂停时间——也就是 Stop the World(STW)的时间方面,但是代价是牺牲了 GC 中的其他特性。

GC 有很多需要关注的方面,比如吞吐量——GC 肯定会减慢程序,那么它对吞吐量有多大的影响;还有,在一段固定的 CPU 时间里可以回收多少垃圾;另外还有 Stop the World 的时间和频率;以及新申请内存的分配速度;还有在分配内存时,空间的浪费情况;以及在多核机器下,GC 能否充分利用多核等很多方面问题。非常遗憾的是,Golang 在设计和实现时,过度强调了暂停时间有限。但这带来了其他影响:比如在执行的过程当中,堆是不能压缩的,也就是说,对象也是不能移动的;还有它也是一个不分代的 GC。所以体现在性能上,就是内存分配和 GC 通常会占用比较多 CPU 资源。

字节曾对其内部服务进行过一些统计,很多微服务在晚高峰期,内存分配和 GC 时间甚至会占用超过 30% 的 CPU 资源。占用这么高资源的原因大概有两点,一个是 Go 里面比较频繁地进行内存分配操作;另一个是 Go 在分配堆内存时,实现相对比较重,消耗了比较多 CPU 资源。比如它中间有 acquired M 和 GC 互相抢占的锁;它的代码路径也比较长;指令数也比较多;内存分配的局部性也不是特别好。

优化策略:尝试降低内存管理,特别是内存分配带来的开销,进而降低 GC 开销。

很多微服务进行内存分配时,分配的对象大部分都是比较小的对象。基于这个观测,字节自己设计了 GAB(Goroutine allocation buffer)机制,用来优化小对象内存分配。Go 的内存分配用的是 tcmalloc 算法,传统的 tcmalloc,会为每个分配请求执行一个比较完整的 malloc GC 方法,而字节的 Gab 为每个 Goroutine 预先分配一个比较大的 buffer,然后使用 bump-pointer 的方式,为适合放进 Gab 里的小对象来进行快速分配。其算法和 tcmalloc 算法完全兼容,而且它的分配操作可以随意被 Stop the world 打断。虽然 Gab 优化可能会造成一些空间浪费,但是在很多微服务上测试后,发现 CPU 性能大概节省了 5% 到 12%。

生成代码问题

Go 的编译器相比传统编译器来说,可以说实现得比较简陋,优化的数量比较少。Go 在编译阶段总共只有 40 多个 Pass,而作为对比,LLVM 在 O2 的时候就有两百多个优化的 Pass。Go 在编译优化时,优化算法的实现也大多选择那些计算精度不高,但是速度比较快的算法。也就是说,Go 非常注重编译时间,导致生成代码的效率不高。

对于微服务的一些场景来说,可以不用那么在意编译速度。很多微服务,编译一次后会部署到几万个,甚至几十万个核上运行,而且通常会运行比较久。在这种情况下,如果增加一点点编译时间却能够节省 CPU 资源,那么这个开销是可以接受的。

优化策略

字节在 Golang 编译器的基础上,以编译速度和 binary size 为代价进行了一些优化。当然,还是控制了编译速度和 binary size 的代价。比如说 binary size 通常的增长大概在 5% 到 15% 之内,而编译速度也没有降低特别多,大概 50% 到 100% 左右。

首先就是内联优化。内联优化是其他优化的基础,它的作用就是在编译时,把函数的定义替换到调用的位置。函数调用本身是有开销的,在 Go1.17 之前,Go 的传参是栈上传参,函数入栈出栈是有开销的,做函数调用实际上是执行一次跳转,可能也会有指令 cache 缺失的开销。

Golang 原生的内联优化受到比较多限制。比如一些语言特性会阻止内联,比如说如果一个函数内部含有 defer,如果把这个函数内联到调用的地方,可能会导致 defer 函数执行的时机和原有语义不一致。所以这种情况下,Go 没有办法做内联。此外,如果一个函数是 interface 类型的函数调用,那么这个函数也不会被内联。

另外,Go 的编译器从 1.9 才开始支持非叶子节点的内联,虽然非叶子节点的内联默认是打开的,但是策略却非常保守。举个例子,如果在非叶子节点的函数中存在两个函数调用,那么这个函数在内联评估时就不会被内联。另外,从实现的角度上,内联的策略也做得非常保守。字节的 go 编译器中修改了内联策略,让更多函数可以被内联,这样带来的最直接收益就是可以减少很多函数调用开销。虽然单次函数调用的开销可能并不是特别大,但是积少成多,总量也不少。

另外更重要的是,内联之后增加了其他优化的机会,比如说逃逸分析、公共子表达式删除等等。因为编译器优化大多数都是函数内的局部优化,内联相当于扩大了这些优化的分析范围,可以让后面的分析和优化效果更加明显。

当然,内联虽然好,也不能无限制内联,因为内联也是有开销的。经过内联优化后,binary size 体积大概增加了 5% 到 10%,编译时间也有所增加。同时,它还有另外一个更重要的运行时开销。也就是说,内联增加后会导致栈的长度有所增加,进而导致运行时扩栈会增加不小的开销。为了降低扩栈的开销,还需要针对性地调整一下 Golang 的初始栈大小。

这里再简单介绍一下栈调整的背景。Golang 通过 goroutine 支持高并发,用户可以创建非常多的 goroutine。为了降低对内存的要求,每个 goroutine 的栈就不能像其他语言的线程的栈那样,设置成两兆到八兆这么大的空间,要不然很容易 OOM。在 Linux 上,Golang 的起始栈大小是 2K。Go 会在函数开头时检查一下当前栈的剩余空间,看看是否满足当前函数正常运行的需求,所以会在开头插入一个栈检查的指令,如果发现不能满足,就会触发扩栈操作:先申请一块内存,把当前栈复制过去,最后再遍历一下栈,逐帧地修改栈上的指针,避免出现指针指向老的栈的情况。这个开销是很大的,内联策略的调整会让更多数据分配到栈上,加剧这种现象出现,所以字节还调整了 GO 的起始栈大小。

这里收益最大的一个优化应该就是内联策略的优化调整上。

另外还进行了一些其他优化,比如说前面提的 Gab 优化,会在编译期把 Gab 的快速分配路径直接生成到编译器的代码中,这样可以加快分配到 Gab 上的对象的内存分配速度。

因为 Go 的内存分配的优化开销还是比较大的,所以一个优化重点就是想办法降低在堆上的分配。而 Golang 分配对象到堆上还是栈上,这个过程由逃逸分析控制,所以也进行了一些逃逸分析的优化。

在编译器上实现的优化,大多都是通用优化。理论上,所有微服务都可能享受到这些优化的收益,目前实际上线的微服务也证明了这点。

关于编译器的优化,目前还有两个策略在走,第一个是继续尝试在 Go 原生编译器里引入更多编译器优化,希望进一步提升 Go 的原生编译器性能;另一个,也考虑借助 LLVM 强大的优化能力,把 Go 的源代码编译成 LLVM IR,然后生成可执行代码来进行性能上的优化。

现在社区上已经有这么一个项目,就是 Gollvm,基本可用,但是不支持很多重要的特性。比如说它不支持汇编语言,如果微服务当中或者引用的第三方库里含有 Plan9 的汇编,Gollvm 现在是不支持的。另外,它的 GC 暂时不支持精确栈扫描,采用的是保守栈扫描策略。另外,Gollvm 现在的性能相比 GO 原生编译器还有不小差距。

性能观测问题

在 Go 上线的过程中,还存在一个比较明显的问题,就是性能观测问题,具体来说就是测不准。

它自带的 pprof 工具,结果不是太准确。这在 Go 社区内部也有一些讨论,大概原理是 Go 的 pprof 工具使用 itimer 来发生信号,触发 pprof 采样,但是在 Linux 上,特别是某些版本的 Linux 上,这些信号量可能不是那么准确。根据自己内部 pprof 的结果来统计,一些容器上大概有 20% 甚至 50% 的结果被丢掉了。它还有一个问题,在一个线程上触发的信号可能会采样到另外一个 M 上,一个 M 上触发的这个采用信号可能会采到另外一个 M 上的数据。

而 perf 呢,很遗憾,很多线上容器内部不支持 perf。出于一些安全策略的考虑,也不允许在线上安装 perf 这样的工具。

Uber 在 Go 上开发了一个 pprof++ 的工具,类似于 pprof,也是调用 pprof 的一些接口,使用硬件的 PMU 来触发采样。但是 Uber 的 pprof++ 的一个问题是性能损耗非常大。经过一些验证,发现在一些小例子上,在打上 Uber 的 pprof++ 的 patch 之后,仅仅是打上这个 patch 而不是打开这个 pprof,就有大概 3% 左右的性能损耗。

比较幸运的是,Go1.18 之后,它提出了 per-M 这个 pprof,对每个 M 来进行采样,结果相对比较准确。

Go 里面使用 Map 时应该注意什么问题

  1. Map 在读取和写入前要先注意初始化,否则会报 panic
  2. Map 并发不安全,并发写,并发读写都会出发 panic

Map 的 panic 能被 recover 掉吗

不能。

Go 中 Map 的 panic 是通过 throw("xxx") 的方式抛出的,其底层是调用 runtime.fatalthrow() 方法抛出异常,代码中有如下注释:

// fatalthrow implements an unrecoverable runtime throw. It freezes the
// system, prints stack traces starting from its caller, and terminates the
// process.

这说明:

  • fatalthrow()是无法被recover()
  • 它会冻结系统,打印堆栈,然后结束进程

recover 只能捕获到普通的 panic。

Map 怎么知道自己处于竞争状态?

Map 的结构体 hmap 中有一个 flags 成员变量,其用于标识 map 自身处于哪种状态:

// 可能有迭代器在使用 buckets
iterator     = 1
// 可能有迭代器在使用 oldbuckets
oldIterator  = 2
// 有协程正在向 map 写入 key
hashWriting  = 4
// 等量扩容
sameSizeGrow = 8

在进行读写操作时,都会先对 flags 的状态进行检测。

并发使用 Map 有哪些方式

加读写锁

常见的 map 的操作有增删改查和遍历,这里面查和遍历是读操作,增删改是写操作,因此对查和遍历需要加读锁,对增删改需要加写锁。

map[int]int 为例,借助 RWMutex,具体的实现方式如下:

type RWMap struct { // 一个读写锁保护的线程安全的map
    sync.RWMutex // 读写锁保护下面的map字段
    m map[int]int
}
// 新建一个RWMap
func NewRWMap(n int) *RWMap {
    return &RWMap{
        m: make(map[int]int, n),
    }
}
func (m *RWMap) Get(k int) (int, bool) { //从map中读取一个值
    m.RLock()
    defer m.RUnlock()
    v, existed := m.m[k] // 在锁的保护下从map中读取
    return v, existed
}

func (m *RWMap) Set(k int, v int) { // 设置一个键值对
    m.Lock()              // 锁保护
    defer m.Unlock()
    m.m[k] = v
}

func (m *RWMap) Delete(k int) { //删除一个键
    m.Lock()                   // 锁保护
    defer m.Unlock()
    delete(m.m, k)
}

func (m *RWMap) Len() int { // map的长度
    m.RLock()   // 锁保护
    defer m.RUnlock()
    return len(m.m)
}

func (m *RWMap) Each(f func(k, v int) bool) { // 遍历map
    m.RLock()             //遍历期间一直持有读锁
    defer m.RUnlock()

    for k, v := range m.m {
        if !f(k, v) {
            return
        }
    }
}

分片加锁

通过读写锁 RWMutex 实现的线程安全的 map,功能上已经完全满足了需要,但是面对高并发的场景,仅仅功能满足可不行,性能也得跟上。

锁是性能下降的万恶之源之一。所以并发编程的原则就是尽可能减少锁的使用。当锁不得不用的时候,可以减小锁的粒度和持有的时间。

在第一种方法中,加锁的对象是整个 map,协程 A 对 map 中的 key 进行修改操作,会导致其它协程无法对其它 key 进行读写操作。一种解决思路是将这个 map 分成 n 块,每个块之间的读写操作都互不干扰,从而降低冲突的可能性。Go 比较知名的分片 map 的实现是 concurrent-map 和 bigcache。

读写分离

分片加锁的思路是将大块的数据切分成小块的数据,从而减少冲突导致锁阻塞的可能性。如果在一些特殊的场景下,将读写数据分开,是不是能在进一步提升性能呢?

在内置的 sync 包中也有一个线程安全的 map,通过将读写分离的方式实现了某些特定场景下的性能提升。

其实在生产环境中,sync.map 用的很少,官方文档推荐的两种使用场景是:

The Map type is optimized for two common use cases:

(1) when the entry for a given key is only ever written once but read many times, as in caches that only grow,

or(2) when multiple goroutines read, write, and overwrite entries for disjoint sets of keys.

In these two cases, use of a Map may significantly reduce lock contention compared to a Go map paired with a separate Mutex or RWMutex.

两种场景都比较苛刻,要么是一写多读,要么是各个协程操作的 key 集合没有交集(或者交集很少)。所以官方建议先对自己的场景做性能测评,如果确实能显著提高性能,再使用 sync.map。

sync.map 的整体思路就是用两个数据结构(只读的 read 和可写的 dirty)尽量将读写操作分开,来减少锁对性能的影响。

type Map struct {
    mu Mutex

  // 基本上你可以把它看成一个安全的只读的map
  // 它包含的元素可以通过原子操作更新的,但是已删除的entry就需要加锁操作了
    read atomic.Value // readOnly

  // 包含需要加锁才能访问的元素
  // 包括所有在read字段中但未被expunged(删除)的元素以及新加的元素
    dirty map[any]*entry

  // 记录从read中读取miss的次数,一旦miss数和dirty长度一样了,就会把dirty提升为read,并把dirty置空
    misses int
}

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
    m       map[any]*entry
    amended bool // 当dirty中包含read没有的数据时为true,比如新增一条数据
}

// expunged是用来标识此项已经删掉的指针
// 当map中的一个项目被删除了,只是把它的值标记为expunged,以后才有机会真正删除此项
var expunged = unsafe.Pointer(new(any))

// entry代表一个值
type entry struct {
    p unsafe.Pointer // *interface{}
}

load 方法

func (m *Map) Load(key any) (value any, ok bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended {
        m.mu.Lock()
        // 从 read 中读不到的时候,通过dirty进行读取
    // 在此之前,为了避免阻塞在拿锁的时候,read 发生了更新,拿到锁之后再读取一次read(双重检查,真细节啊!)
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            e, ok = m.dirty[key]
            // miss 计数,到达阈值直接把 dirty 升级为 read
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load()
}

func (e *entry) load() (value any, ok bool) {
    p := atomic.LoadPointer(&e.p)
    if p == nil || p == expunged {
        return nil, false
    }
    return *(*any)(p), true
}

store 方法

func (m *Map) Store(key, value any) {
    read, _ := m.read.Load().(readOnly)
  // 如果read字段包含这个key,说明是更新操作,直接在对 entry 进行 cas 更新。
  // (e 是 entry 的指针,对其更新会同时更新 read 和 dirty 中的数据)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }

  // read 中不存在或者 cas 更新失败,加锁访问 dirty
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly) // 同样是双重检查
    if e, ok := read.m[key]; ok {
        if e.unexpungeLocked() {
            // 这个 key 原来已经被删除了,需要添加到 dirty 中
            m.dirty[key] = e
        }
        e.storeLocked(&value)// cas 更新 value
    } else if e, ok := m.dirty[key]; ok {
        e.storeLocked(&value) // read 还是没有,但 dirty 有,直接更新
    } else {
    // 说明这是一个新的 key
        if !read.amended {
            // 创建 dirty 对象,并且标记 dirty 包含了 read 没有的元素
      // 同时对 nil 的数据标识为已删除
            m.dirtyLocked()
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
}

func (e *entry) tryStore(i *any) bool {
    for {
        p := atomic.LoadPointer(&e.p)
        if p == expunged {
            return false
        }
        if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
            return true
        }
    }
}

func (e *entry) unexpungeLocked() (wasExpunged bool) {
    return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

func (e *entry) storeLocked(i *any) {
    atomic.StorePointer(&e.p, unsafe.Pointer(i))
}

func (m *Map) dirtyLocked() {
    if m.dirty != nil {
        return
    }

    read, _ := m.read.Load().(readOnly)
    m.dirty = make(map[any]*entry, len(read.m))
    for k, e := range read.m {
        if !e.tryExpungeLocked() {
            m.dirty[k] = e
        }
    }
}

func (e *entry) tryExpungeLocked() (isExpunged bool) {
    p := atomic.LoadPointer(&e.p)
    for p == nil {
        if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
            return true
        }
        p = atomic.LoadPointer(&e.p)
    }
    return p == expunged
}

delete 方法

func (m *Map) Delete(key any) {
    m.LoadAndDelete(key)
}

func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended {
    // 说明这个 key 在 dirty 中
        m.mu.Lock()
        read, _ = m.read.Load().(readOnly) // 双重检查
        e, ok = read.m[key]
        if !ok && read.amended {
            e, ok = m.dirty[key]
            delete(m.dirty, key)
            // 不管key是否存在,都记录一个未命中:这个键将走dirty查询,直到脏映射被提升为读映射。
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if ok {
        return e.delete()
    }
    return nil, false
}

func (e *entry) delete() (value any, ok bool) {
    for {
        p := atomic.LoadPointer(&e.p)
        if p == nil || p == expunged {
            return nil, false
        }
        if atomic.CompareAndSwapPointer(&e.p, p, nil) {
            return *(*any)(p), true
        }
    }
}

补充说明一下,delete() 执行完之后,e.p 变成 nil,下次 Store 的时候,执行到 dirtyLocked() 这一步的时候,会被标记成 enpunged。因此在 read 中 nil 和 enpunged 都表示删除状态。

总结

  1. 读写分离。读(更新)相关的操作尽量通过不加锁的 read 实现,写(新增)相关的操作通过 dirty 加锁实现。
  2. 动态调整。新写入的 key 都只存在 dirty 中,如果 dirty 中的 key 被多次读取,dirty 就会上升成不需要加锁的 read。
  3. 延迟删除。Delete 只是把被删除的 key 标记成 nil,新增 key-value 的时候,标记成 enpunged;dirty 上升成 read 的时候,标记删除的 key 被批量移出 map。这样的好处是 dirty 变成 read 之前,这些 key 都会命中 read,而 read 不需要加锁,无论是读还是更新,性能都很高。

bigcache 对 map 的优化

处理高并发访问

cache 就像一个大的 hashtable,可不可以使用一个map + sync.RWMutex 实现满足高并发的场景呢?

sync.RWMutex 虽然对读写进行了优化,但是只是处理了并发读,而写操作还是串行,一旦写的并发量大的时候,即使写不同的key,对应的goroutine也会 block住,只允许一个写执行,这是一个瓶颈,并且不可控。

解决并发的问题有一个方法叫做 shard (分片),每个分片一把锁。 很多大并发场景下为了减小并发的压力都会采用这种方法,大的场景比如数据库的分片。 Java 8 之前的ConcurrentMap就是采用分片(segment)的方式减少竞争,Go也有一个类似思想设计的map库:concurrent-map。

对于每一个缓存对象,根据它的key计算它的哈希值: hash(key) % NN是分片数量。 理想情况下N个 goroutine 每次请求正好平均落在各自的分片上,这样就不会有竞争了,即使有多个goroutine落在同一个分片上,如果hash比较平均的话,单个shard的压力也会比较小。

竞争小了有什么好处? 延迟可以大大提高,因为等待获取锁的时间变小了。

当然这里有一些要考虑的地方:

N的选择

既然分片可以很好的降低锁的竞争,那么N是不是越大越好呢?当然不是,如果N非常大,比如每个缓存对象一个锁,那么会带来很多额外的不必要的开销。可以选择一个不太大的值,在性能和花销上寻找一个平衡。

另外, N是 2的幂, 比如16、32、64。这样设计的好处就是计算余数可以使用位运算快速计算。

func (c *BigCache) getShard(hashedKey uint64) (shard *cacheShard) {
    return c.shards[hashedKey&c.shardMask]
}

因为对于2的幂N,对于任意的x, 下面的公式成立:

x mod N = (x & (N − 1))

所以只需要使用一次按位AND (&)就可以求得它的余数。

选择hash算法

以前已经有非常多的哈希算法,最近几年也出现了一些新的哈希算法,也被人使用Go语言来实现。

很显然,一个优秀的哈希算法要保证:

  • 哈希值应该比较随机 (质量)
  • 哈希速度比较快 (速度)
  • 尽量不产生额外的内存分配,避免对垃圾回收产生压力 (耗费资源少)

bigcache提供了一个默认的Hash的实现,采用fnv64a算法。这个算法的好处是采用位运算的方式在栈上进行运算,避免在堆上分配。

type fnv64a struct{}

const (
    // offset64 FNVa offset basis. See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function#FNV-1a_hash
    offset64 = 14695981039346656037
    // prime64 FNVa prime value. See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function#FNV-1a_hash
    prime64 = 1099511628211
)

// Sum64 gets the string and returns its uint64 hash value.
func (f fnv64a) Sum64(key string) uint64 {
    var hash uint64 = offset64
    for i := 0; i < len(key); i++ {
        hash ^= uint64(key[i])
        hash *= prime64
    }

    return hash
}

忽略内存开销

对于Go语言中的map,垃圾回收器在 markscan阶段检查map中的每一个元素,如果缓存中包含数百万的缓存对象,垃圾回收器对这些对象的无意义的检查导致不必要的时间开销。

bigcache的作者做了测试。他们测试了简单的HTTP/JSON序列化(不会访问cache)。 在cache为空的时候1万的QPS的耗时大约10毫秒。当cache填满的时候, P99的请求都会超过1秒。监控显示堆中包含4千万的对象, GC过程中的 markscan 也需要4秒。

可以很容易测试这种状况,比如下面的代码:

package main

import "time"

type Item struct {
    A string
    B string
    C string
    D string
    E string
    F string
    G G
}

type G struct {
    H int
    I int
    K int
    L int
    M int
    N int
}

func main() {
    m := make(map[int]*Item, 10*1024*1024)

    for i := 0; i < 1024*1024; i++ {
        m[i] = &Item{}
    }

    for i := 0; ; i++ {
        delete(m, i)
        m[1024*1024+i] = &Item{}
        time.Sleep(10 * time.Millisecond)
    }
}

只有一个map对象,里面包含一百万的元素,每10毫秒删一个放一个。

并发量相当小,并且单个的goroutine也没有竞争,但是由于元素的数量巨大,垃圾回收在mark/scan阶段需要花费上百毫秒进行标记和遍历。

那么如何解决这个问题呢?

垃圾回收器检查的是堆上的资源,如果不把对象放在堆上,不就解决这个问题了吗?开源项目offheap,它提供了定制的Malloc()Free(),但是缓存需要基于这些方法定制。当然一些基于垃圾回收的编程语言为了减少垃圾回收的时间,都会提供相应的库。但是需要注意,堆外内存很容易产生内存泄漏。

第二种优化方法是和Go 1.5中一个修复有关(#9477),这个issue还是描述了包含大量对象的map的垃圾回收时的耗时问题,Go的开发者优化了垃圾回收时对于map的处理,如果map对象中的key和value不包含指针,那么垃圾回收器就会对它们进行优化:

runtime: do not scan maps when k/v do not contain pointers

Currently we scan maps even if k/v does not contain pointers.
This is required because overflow buckets are hanging off the main table.
This change introduces a separate array that contains pointers to all
overflow buckets and keeps them alive. Buckets themselves are marked
as containing no pointers and are not scanned by GC (if k/v does not
contain pointers).

This brings maps in line with slices and chans – GC does not scan
their contents if elements do not contain pointers.

Currently scanning of a map[int]int with 2e8 entries (~8GB heap)
takes ~8 seconds. With this change scanning takes negligible time.

https://go-review.googlesource.com/c/go/+/3288

所以如果我们的对象不包含指针,虽然也是分配在堆上,但是垃圾回收可以无视它们。

如果把map定义成map[int]int,就会发现gc的耗时就会将下来了。

遗憾的是,一般很难要求用户的缓存对象只能包含intbool这样的基本数据类型。

解决办法就是使用哈希值作为map[int]int的key, 把缓存对象序列化后放到一个预先分配的大的字节数组中,然后将它在数组中的offset作为map[int]int的value。

type cacheShard struct {
    hashmap     map[uint64]uint32
    entries     queue.BytesQueue
    lock        sync.RWMutex
    entryBuffer []byte
    onRemove    onRemoveCallback

    isVerbose    bool
    statsEnabled bool
    logger       Logger
    clock        clock
    lifeWindow   uint64

    hashmapStats map[uint64]uint32
    stats        Stats
}

func (s *cacheShard) set(key string, hashedKey uint64, entry []byte) error {
    currentTimestamp := uint64(s.clock.epoch())
    s.lock.Lock()
    // 查找是否已经存在了对应的缓存对象,如果存在,将它的值置为空
    if previousIndex := s.hashmap[hashedKey]; previousIndex != 0 {
        if previousEntry, err := s.entries.Get(int(previousIndex)); err == nil {
            resetKeyFromEntry(previousEntry)
        }
    }
    // 触发是否要移除最老的缓存对象
    if oldestEntry, err := s.entries.Peek(); err == nil {
        s.onEvict(oldestEntry, currentTimestamp, s.removeOldestEntry)
    }
    // 将对象放入到一个字节数组中,如果已有的字节数组(slice)可以放得下此对象,则重用,否则新建一个字节数组
    w := wrapEntry(currentTimestamp, hashedKey, key, entry, &s.entryBuffer)
    for {
        // 尝试放入到字节队列中,成功则加入到map中
        if index, err := s.entries.Push(w); err == nil {
            s.hashmap[hashedKey] = uint32(index)
            s.lock.Unlock()
            return nil
        }
        // 如果空间不足,移除最老的元素
        if s.removeOldestEntry(NoSpace) != nil {
            s.lock.Unlock()
            return fmt.Errorf("entry is bigger than max shard size")
        }
    }
}

func wrapEntry(timestamp uint64, hash uint64, key string, entry []byte, buffer *[]byte) []byte {
    keyLength := len(key)
    blobLength := len(entry) + headersSizeInBytes + keyLength
    if blobLength > len(*buffer) {
        *buffer = make([]byte, blobLength)
    }
    blob := *buffer
    binary.LittleEndian.PutUint64(blob, timestamp)
    binary.LittleEndian.PutUint64(blob[timestampSizeInBytes:], hash)
    binary.LittleEndian.PutUint16(blob[timestampSizeInBytes+hashSizeInBytes:], uint16(keyLength))
    copy(blob[headersSizeInBytes:], key)
    copy(blob[headersSizeInBytes+keyLength:], entry)
    return blob[:blobLength]
}

queue.BytesQueue是一个字节数组,可以做到按需分配。当加入一个[]byte时,它会把数据copy到尾部。

值得注意的是删除缓存元素的时候bigcache只是把它从的索引从map[uint64]uint32中删除了,并把它在queue.BytesQueue队列中的长度置为0。那么删除操作会不会在queue.BytesQueue中造成很多的“虫洞”?从它的实现上来看,,而且这些”虫洞”不会被整理,也不会被移除。因为它的底层是使用一个字节数组实现的,”虫洞”的移除是一个耗时的操作,会导致锁的持有时间过长。bigcache只能等待清理最老的元素的时候把这些”虫洞”删除掉。

这种缓存,一般来说,删除元素靠的是全局过期时间(注意,是先进先出的过期,并不能为每个key单独指定不同的过期时间)或缓存总大小达到一定阈值后删除,也即把数组当队列用。所以,这种实现的前提是,缓存是自淘汰类型,而非可手动删除指定元素类型的。

panic 和 recover 的机制

Go 的 panic 结构如下:

type _panic struct {
    argp      unsafe.Pointer
    arg       interface{}
    link      *_panic
    recovered bool
    aborted   bool
    pc        uintptr
    sp        unsafe.Pointer
    goexit    bool
}
  1. argp 是指向 defer 调用时参数的指针;
  2. arg 是调用 panic 时传入的参数;
  3. link 指向了更早调用的 runtime._panic 结构;
  4. recovered 表示当前 runtime._panic 是否被 recover 恢复;
  5. aborted 表示当前的 panic 是否被强行终止;

defer 方法会将 recovered 方法设置成 true。

程序崩溃和恢复的过程:

  1. 编译器会负责做转换关键字的工作;
    • panicrecover 分别转换成 runtime.gopanicruntime.gorecover
    • defer 转换成 runtime.deferproc 函数;
    • 在调用 defer 的函数末尾调用 runtime.deferreturn 函数;
  2. 在运行过程中遇到 runtime.gopanic 方法时,会从 Goroutine 的链表依次取出 runtime._defer结构体并执行;
  3. 如果调用延迟执行函数时遇到了runtime.gorecover 就会将 _panic.recovered标记成 true 并返回 panic 的参数
    • 在这次调用结束之后runtime.gopanic 会从 runtime._defer 结构体中取出程序计数器 pc 和栈指针 sp 并调用 runtime.recovery 函数进行恢复程序
    • runtime.recovery 会根据传入的 pcsp 跳转回 runtime.deferproc
    • 编译器自动生成的代码会发现 runtime.deferproc的返回值不为 0,这时会跳回 runtime.deferreturn 并恢复到正常的执行流程;
  4. 如果没有遇到 runtime.gorecover就会依次遍历所有的 runtime._defer,并在最后调用 runtime.fatalpanic 中止程序、打印 panic 的参数并返回错误码 2;

为什么 Fasthttp 使用 slice 而非 map 存储请求数据

Fasthttp 是一个高性能的 Golang HTTP 框架,它在设计上做了许多优化以提高性能。其中一个显著的设计选择是使用 slice 而非 map 来存储数据,尤其是在处理 HTTP headers 时。

Fasthttp 在这方面以下三方面的考量:

内存分配和回收性能

Slice 的内存效率

由于 slice 的元素在内存中是连续存储的,它们访问速度快,且能有效利用 CPU 缓存。此外,slice 可以通过重新切片来复用已有的数组,减少内存分配和垃圾回收的压力。

Map 的内存开销

相比之下,map 的内存开销较大。

在 map 中,键和值通常是散布在内存中的,这导致 CPU 缓存利用率不高。而且,map 的增长通常涉及重新哈希和重新分配内存,这些操作在性能敏感的应用中可能成为瓶颈。

Fasthttp 选择使用自定义的 sliceMap 结构来存储键值对,而非标准的 map。

下面是 sliceMap 的一个简化实现和它的 Add 方法:

type kv struct {
    key []byte
    value []byte
}

type sliceMap []kv

func (sm *sliceMap) Add(k, v []byte) {
    kvs := *sm
    if cap(kvs) > len(kvs) {
        kvs = kvs[:len(kvs)+1]
    } else {
        kvs = append(kvs, kv{})
    }
    kv := &kvs[len(kvs)-1]
    kv.key = append(kv.key[:0], k...)
    kv.value = append(kv.value[:0], v...)
    *sm = kvs
}

在这个设计中,sliceMap 通过以下方式优化性能:

  • 减少内存分配: 通过在现有的 slice 上进行操作,sliceMap 尽可能地复用内存。当容量足够时,它通过重新切片 kvs = kvs[:len(kvs)+1] 来扩展 slice,避免了额外的内存分配。
  • 减少垃圾回收压力:由于 slice 的元素是连续存储的,它可以更有效地被垃圾回收器处理,减少了垃圾回收的开销。而且,由于内存是复用的,垃圾回收的次数也大大减少。

存储数据特性

在处理 HTTP 请求时,通常 headers、query 参数或 cookies 的数量并不多。这意味着即使使用线性搜索,查找效率也不会成为性能瓶颈。

相比之下,虽然 hash map 提供了理论上接近 O(1) 的查找效率,但实际使用中也有其开销和复杂性。

  • • 首先,hash map 的哈希计算本身就需要时间。
  • • 其次,哈希碰撞时,hash map 要额外处理来解决碰撞,这可能涉及到链表遍历或重新哈希等操作。

这些因素在元素数量较少时可能会抵消 hash map 在查找效率上的理论优势,而 slice 则才是更优质的选择。

CPU 预加载特性

由于 slice 的内存布局是连续的,它符合 CPU 缓存的工作原理,即一次性加载相邻数据。这种连续性使得 CPU 在访问一个 slice 元素后,能预加载相邻元素到缓存中,提高后续访问的速度。因此,顺序访问 slice 时,缓存命中率高,减少了对主内存的访问次数,从而提高了性能。

参考文档

手撕 Go 面试官:Go 结构体是否可以比较,为什么?

用 Go struct 不能犯的一个低级错误!

字节大规模微服务 Go 语言发展之路

Go 并发写map产生错误能够通过recover()恢复吗?

妙到颠毫: bigcache优化技巧

[译] Go开源项目BigCache如何加速并发访问以及避免高额的GC开销

Go 并发之三种线程安全的 map

为什么 Golang Fasthttp 选择使用 slice 而非 map 存储请求数据