注：本文首发于笔者的个人微信公众号”iamtonybai”，是公号付费文章(价格1元)。首发于2020.10.9日，经过一个月收费期，我觉得将其免费分享出来。如果你觉得文章质量不错，欢迎到首发地址付费支持：https://mp.weixin.qq.com/s/rsDC-6paC5zN4sepWd5LqQ

近期在项目考虑在内存中保存从数据库加载的配置数据的方案，初步考虑采用map来保存。Go语言中有两个map，一个是Go语言原生的map类型，而另外一种则是在Go 1.9版本新增到标准库中的sync.Map。

一. 原生map的“先天不足”

对于已经初始化了的原生map，我们可以尽情地对其进行并发读：

// github.com/bigwhite/experiments/inside-syncmap/concurrent_builtin_map_read.go

package main

import (
    "fmt"
    "math/rand"
    "sync"
)

func main() {
    var wg sync.WaitGroup
    var m = make(map[int]int, 100)

    for i := 0; i < 100; i++ {
        m[i] = i
    }

    wg.Add(10)
    for i := 0; i < 10; i++ {
        // 并发读
        go func(i int) {
            for j := 0; j < 100; j++ {
                n := rand.Intn(100)
                fmt.Printf("goroutine[%d] read m[%d]: %d\n", i, n, m[n])
            }
            wg.Done()
        }(i)
    }
    wg.Wait()
}

但原生map一个最大的问题就是不支持多goroutine并发写。Go runtime内置对原生map并发写的检测，一旦检测到就会以panic的形式阻止程序继续运行，比如下面这个例子：

// github.com/bigwhite/experiments/inside-syncmap/concurrent_builtin_map_write.go

package main

import (
        "math/rand"
        "sync"
)

func main() {
        var wg sync.WaitGroup
        var m = make(map[int]int, 100)

        for i := 0; i < 100; i++ {
                m[i] = i
        }

        wg.Add(10)
        for i := 0; i < 10; i++ {
                // 并发写
                go func(i int) {
                        for n := 0; n < 100; n++ {
                                n := rand.Intn(100)
                                m[n] = n
                        }
                        wg.Done()
                }(i)
        }
        wg.Wait()
}

运行上面这个并发写的例子，我们很大可能会得到下面panic：

$go run concurrent_builtin_map_write.go
fatal error: concurrent map writes

... ...

原生map的“先天不足”让其无法直接胜任某些场合的要求，于是gopher们便寻求其他路径。一种路径无非是基于原生map包装出一个支持并发读写的自定义map类型，比如，最简单的方式就是用一把互斥锁(sync.Mutex)同步各个goroutine对map内数据的访问；如果读多写少，还可以利用读写锁(sync.RWMutex)来保护map内数据，减少锁竞争，提高并发读的性能。很多第三方map的实现原理也大体如此。

另外一种路径就是使用sync.Map。

二. sync.Map的原理简述

按照官方文档，sync.Map是goroutine-safe的，即多个goroutine同时对其读写都是ok的。和第一种路径的最大区别在于，sync.Map对特定场景做了性能优化，一种是读多写少的场景，另外一种多个goroutine读/写/修改的key集合没有交集。

下面是两种技术路径的性能基准测试结果对比(macOS(4核8线程) go 1.14)：

// 对应的源码在https://github.com/bigwhite/experiments/tree/master/go19-examples/benchmark-for-map下面

$go test -bench .
goos: darwin
goarch: amd64
pkg: github.com/bigwhite/experiments/go19-examples/benchmark-for-map
BenchmarkBuiltinMapStoreParalell-8           7945152           179 ns/op
BenchmarkSyncMapStoreParalell-8              3523468           387 ns/op
BenchmarkBuiltinRwMapStoreParalell-8         7622342           190 ns/op
BenchmarkBuiltinMapLookupParalell-8          7319148           163 ns/op
BenchmarkBuiltinRwMapLookupParalell-8       21800383            55.2 ns/op
BenchmarkSyncMapLookupParalell-8            70512406            18.5 ns/op
BenchmarkBuiltinMapDeleteParalell-8          8773206           174 ns/op
BenchmarkBuiltinRwMapDeleteParalell-8        5424912           214 ns/op
BenchmarkSyncMapDeleteParalell-8            49899008            23.7 ns/op
PASS
ok      github.com/bigwhite/experiments/go19-examples/benchmark-for-map    15.727s

我们看到：sync.Map在读和删除两项性能基准测试上的数据都大幅领先使用sync.Mutex或RWMutex包装的原生map，仅在写入一项上存在一倍的差距。sync.Map是如何实现如此高的读取性能的呢？简单说：空间换时间+读写分离+原子操作(快路径)。

sync.Map底层使用了两个原生map，一个叫read，仅用于读；一个叫dirty，用于在特定情况下存储最新写入的key-value数据:

read(这个map)好比整个sync.Map的一个“高速缓存”，当goroutine从sync.Map中读取数据时，sync.Map会首先查看read这个缓存层是否有用户需要的数据(key是否命中)，如果有(命中)，则通过原子操作将数据读取并返回，这是sync.Map推荐的快路径(fast path)，也是为何上面基准测试结果中读操作性能极高的原因。

三. 通过实例深入理解sync.Map的原理

sync.Map源码(Go 1.14版本)不到400行，应该算是比较简单的了。但对于那些有着“阅读源码恐惧症”的gopher来说，我们可以通过另外一种研究方法：实例法，并结合些许源码来从“黑盒”角度理解sync.Map的工作原理。这种方法十分适合那些相对独立、可以从标准库中“单独”取出来的包，而sync.Map就是这样的包。

首先，我们将sync.Map从标准库源码目录中拷贝一份，放入本地~/go/src/github.com/bigwhite/experiments/inside-syncmap/syncmap/sync下面，得益于go module的引入，我们在~/go/src/github.com/bigwhite/experiments/inside-syncmap/syncmap目录下面建立go.mod文件：

module github.com/bigwhite/go

go 1.14

这样我们就可以通过github.com/bigwhite/go/sync包路径导入module：github.com/bigwhite/go下面的sync包了。

接下来，我们给位于~/go/src/github.com/bigwhite/experiments/inside-syncmap/syncmap/sync下面的map.go中(sync.Map包的副本)添加一个Map类型的新方法Dump：

// github.com/bigwhite/experiments/tree/master/inside-syncmap/syncmap/sync/map.go

func (m *Map) Dump() {
        fmt.Printf("=====> sync.Map:\n")
        // dump read
        read, ok := m.read.Load().(readOnly)
        fmt.Printf("\t read(amended=%v):\n", read.amended)
        if ok {
                // dump readOnly's map
                for k, v := range read.m {
                        fmt.Printf("\t\t %#v:%#v\n", k, v)
                }
        }

        // dump dirty
        fmt.Printf("\t dirty:\n")
        for k, v := range m.dirty {
                fmt.Printf("\t\t %#v:%#v\n", k, v)
        }

        // dump miss
        fmt.Printf("\t misses:%d\n", m.misses)

        // dump expunged
        fmt.Printf("\t expunged:%#v\n", expunged)
        fmt.Printf("<===== sync.Map\n")
}

这个方法将打印Map的内部状态以及read、dirty两个原生map中的所有key-value对，这样我们在初始状态、store key-value后、load key以及delete key后通过Dump方法输出sync.Map状态便可以看到不同操作后sync.Map内部的状态变化，从而间接了解sync.Map的工作原理。下面我们就分情况剖析sync.Map的行为特征。

1. 初始状态

sync.Map是零值可用的，我们可以像下面这样定义一个sync.Map类型变量，并无需做显式初始化（关于零值可用，在我的Go专栏《改善Go语言编程质量的50个有效实践》中有专门的一节详述，有兴趣的gopher可以订阅学习^_^）。

// github.com/bigwhite/experiments/tree/master/inside-syncmap/syncmap/main.go

var m sync.Map

我们通过Dump输出初始状态下的sync.Map的内部状态：

// github.com/bigwhite/experiments/tree/master/inside-syncmap/syncmap/main.go

func main() {
        var m sync.Map
        fmt.Println("sync.Map init status:")
        m.Dump()

        ... ...

}

运行后，输出如下：

sync.Map init status:
=====> sync.Map:
     read(amended=false):
     dirty:
     misses:0
     expunged:(unsafe.Pointer)(0xc0001101e0)
<===== sync.Map

在初始状态下，dirty和read两个内置map内都无数据。expunged是一个哨兵变量(也是一个包内的非导出变量)，它在sync.Map包初始化时就有了一个固定的值。该变量在后续用于元素删除场景(删除的key并不立即从map中删除，而是将其value置为expunged)以及load场景。如果哪个key值对应的value值与explunged一致，说明该key已经被map删除了（即便该key所占用的内存资源尚未释放）。

// map.go

var expunged = unsafe.Pointer(new(interface{}))

2. 写入数据(store)

下面，我们向Map写入一条数据：

// github.com/bigwhite/experiments/tree/master/inside-syncmap/syncmap/main.go

type val struct {
        s string
}

func main() {
        ... ...
        val1 := &val{"val1"}
        m.Store("key1", val1)
        fmt.Println("\nafter store key1:")
        m.Dump()

        ... ...

}

我们看一下存入新数据后，Map内部的状态：

after store key1:
=====> sync.Map:
     read(amended=true):
     dirty:
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000108080)}
     misses:0
     expunged:(unsafe.Pointer)(0xc000108040)
<===== sync.Map

我们看到写入(key1,value1)后，Map中有两处变化，一处是dirty map，新写入的数据存储在dirty map中；第二处是read中的amended值由false变为了true，表示dirty map中存在某些read map还没有的key。

3. dirty提升(promoted)为read

此时，如果我们调用一次sync.Map的Load方法，无论传给Load的key值是否为”key1″还是其他，sync.Map内部都会发生较大变化，我们来看一下：

// github.com/bigwhite/experiments/tree/master/inside-syncmap/syncmap/main.go

        m.Load("key2") //这里我们尝试load key="key2"
        fmt.Println("\nafter load key2:")
        m.Dump()

下面是Load方法调用后Dump方法输出的内容：

after load key2:
=====> sync.Map:
     read(amended=false):
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000010240)}
     dirty:
     misses:0
     expunged:(unsafe.Pointer)(0xc000010200)
<===== sync.Map

我们看到：原dirty map中的数据被提升(promoted)到read map中了，提升后amended值重新变回false。

结合sync.Map中Load方法的源码，我们得出如下sync.Map的工作原理：当Load方法在read map中没有命中（miss)传入的key时，该方法会再次尝试在dirty中继续匹配key；无论是否匹配到，Load方法都会在锁保护下调用missLocked方法增加misses的计数(+1)；如果增加完计数的misses值大于等于dirty map中的元素个数，则会将dirty中的元素整体提升到read：

// $GOROOT/src/sync/map.go

func (m *Map) missLocked() {
        m.misses++  //计数+1
        if m.misses < len(m.dirty) {
                return
        }
        m.read.Store(readOnly{m: m.dirty})  // dirty提升到read
        m.dirty = nil  // dirty置为nil
        m.misses = 0 // misses计数器清零
}

为了验证上述promoted的条件，我们再来做一组实验：

        val2 := &val{"val2"}
        m.Store("key2", val2)
        fmt.Println("\nafter store key2:")
        m.Dump()

        val3 := &val{"val3"}
        m.Store("key3", val3)
        fmt.Println("\nafter store key3:")
        m.Dump()

        m.Load("key1")
        fmt.Println("\nafter load key1:")
        m.Dump()

        m.Load("key2")
        fmt.Println("\nafter load key2:")
        m.Dump()

        m.Load("key2")
        fmt.Println("\nafter load key2 2nd:")
        m.Dump()

        m.Load("key2")
        fmt.Println("\nafter load key2 3rd:")
        m.Dump()

在完成一次promoted动作之后，我们又向sync.Map中写入两个key：key2和key3，并在后续Load一次key1并连续三次Load key2，下面是Dump方法的输出结果：

after store key2:
=====> sync.Map:
     read(amended=true):
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000010240)}
     dirty:
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000010240)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc000010290)}
     misses:0
     expunged:(unsafe.Pointer)(0xc000010200)
<===== sync.Map

after store key3:
=====> sync.Map:
     read(amended=true):
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000010240)}
     dirty:
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000010240)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc000010290)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0000102c0)}
     misses:0
     expunged:(unsafe.Pointer)(0xc000010200)
<===== sync.Map

after load key1:
=====> sync.Map:
     read(amended=true):
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000010240)}
     dirty:
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0000102c0)}
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000010240)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc000010290)}
     misses:0
     expunged:(unsafe.Pointer)(0xc000010200)
<===== sync.Map

after load key2:
=====> sync.Map:
     read(amended=true):
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000010240)}
     dirty:
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000010240)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc000010290)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0000102c0)}
     misses:1
     expunged:(unsafe.Pointer)(0xc000010200)
<===== sync.Map

after load key2 2nd:
=====> sync.Map:
     read(amended=true):
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000010240)}
     dirty:
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000010240)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc000010290)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0000102c0)}
     misses:2
     expunged:(unsafe.Pointer)(0xc000010200)
<===== sync.Map

after load key2 3rd:
=====> sync.Map:
     read(amended=false):
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000010240)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc000010290)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0000102c0)}
     dirty:
     misses:0
     expunged:(unsafe.Pointer)(0xc000010200)
<===== sync.Map

我们看到在写入key2这条数据后，dirty中不仅存储了key2这条数据，原read中的key1数据也被复制了一份存入到dirty中。这个操作是由sync.Map的dirtyLocked方法完成的：

// $GOROOT/src/sync/map.go

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

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

前面我们提到过，promoted(dirty -> read)是一个整体的指针交换操作，promoted时，sync.Map直接将原dirty指针store给read并将自身置为nil，因此sync.Map要保证amended=true时，dirty中拥有整个Map的全量数据，这样在下一次promoted(dirty -> read)时才不会丢失数据。不过dirtyLocked是通过一个迭代实现的元素从read到dirty的复制，如果Map中元素规模很大，这个过程付出的损耗将很大，并且这个过程是在锁保护下的。

在存入key3后，我们调用Load方法先load了key1，由于key1在read中有记录，因此此次load命中了，走的是快路径，对Map状态没有任何影响。

之后，我们又Load了key2，key2不在read中，因此产生了一次miss。misses增加计数后的值为1，而此时dirty中的元素数量为3，不满足promote的条件，于是没有执行promote操作。后续我们又连续进行了两次key2的Load操作，产生了两次miss事件后，misses的计数值等于了dirty中的元素数量，于是promote操作被执行，dirty map整体被置换给read，自己则变成了nil。

4. 更新已存在的key

我们再来看一下更新已存在的key的值的情况。首先是该key仅存在于read中(刚刚promote完毕)，而不在dirty中。我们更新这时仅在read中存在的key2的值：

        val2_1 := &val{"val2_1"}
        m.Store("key2", val2_1)
        fmt.Println("\nafter update key2(in read, not in dirty):")
        m.Dump()

下面是Dump输出的结果：

after update key2(in read, not in dirty):
=====> sync.Map:
     read(amended=false):
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc00008e220)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc00008e2d0)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc00008e2a0)}
     dirty:
     misses:0
     expunged:(unsafe.Pointer)(0xc00008e1e0)
<===== sync.Map

我们看到sync.Map直接更新了位于read中的key2的值(entry.storeLocked方法实现的)，dirty和其他字段没有受到影响。

第二种情况是该key刚store到dirty中，尚未promote，不在read中。我们新增一个key4，并更新其值：

        val4 := &val{"val4"}
        m.Store("key4", val4)
        fmt.Println("\nafter store key4:")
        m.Dump()

        val4_1 := &val{"val4_1"}
        m.Store("key4", val4_1)
        fmt.Println("\nafter update key4(not in read, in dirty):")
        m.Dump()

dump方法的输出结果如下：

after store key4:
=====> sync.Map:
     read(amended=true):
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc00008e220)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc00008e2d0)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc00008e2a0)}
     dirty:
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc00008e220)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc00008e2d0)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc00008e2a0)}
         "key4":&smap.entry{p:(unsafe.Pointer)(0xc00008e310)}
     misses:0
     expunged:(unsafe.Pointer)(0xc00008e1e0)
<===== sync.Map

after update key4(not in read, in dirty):
=====> sync.Map:
     read(amended=true):
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc00008e220)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc00008e2d0)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc00008e2a0)}
     dirty:
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc00008e220)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc00008e2d0)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc00008e2a0)}
         "key4":&smap.entry{p:(unsafe.Pointer)(0xc00008e330)}
     misses:0
     expunged:(unsafe.Pointer)(0xc00008e1e0)
<===== sync.Map

我们看到，sync.Map同样是直接将key4对应的value重新设置为新值(val4_1)。

5. 删除key

为了方便查看，我们将上述Map状态回滚到刚刚promote(dirty -> read)完的时刻，即：

after load key2 3rd:
=====> sync.Map:
     read(amended=false):
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc00008e220)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc00008e270)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc00008e2a0)}
     dirty:
     misses:0
     expunged:(unsafe.Pointer)(0xc00008e1e0)
<===== sync.Map

删除key也有几种情况，我们分别来看一下：

• 删除的key仅存在于read中

我们删除上面Map中仅存在于read中的key2：

        m.Delete("key2")
        fmt.Println("\nafter delete key2:")
        m.Dump()

删除后的Dump结果如下：

after delete key2:
=====> sync.Map:
     read(amended=false):
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000010240)}
         "key2":&smap.entry{p:(unsafe.Pointer)(nil)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0000102c0)}
     dirty:
     misses:0
     expunged:(unsafe.Pointer)(0xc000010200)
<===== sync.Map

我们看到sync.Map并没有删除key2，而是将其value置为nil。

• 删除的key仅存在于dirty中

为了构造初仅存在于dirty中的key，我们向sync.Map写入新数据key4，然后再立刻删除它

        val4 := &val{"val4"}
        m.Store("key4", val4)
        fmt.Println("\nafter store key4:")
        m.Dump()

        m.Delete("key4")
        fmt.Println("\nafter delete key4:")
        m.Dump()

上述代码的Dump结果如下：

after store key4:
=====> sync.Map:
     read(amended=true):
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000104220)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc0001041e0)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0001042a0)}
     dirty:
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000104220)}
         "key4":&smap.entry{p:(unsafe.Pointer)(0xc0001042f0)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0001042a0)}
     misses:0
     expunged:(unsafe.Pointer)(0xc0001041e0)
<===== sync.Map

after delete key4:
=====> sync.Map:
     read(amended=true):
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000104220)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc0001041e0)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0001042a0)}
     dirty:
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0001042a0)}
         "key1":&smap.entry{p:(unsafe.Pointer)(0xc000104220)}
     misses:0
     expunged:(unsafe.Pointer)(0xc0001041e0)
<===== sync.Map

我们看到：和仅在read中的情况不同(仅将value设置为nil)，仅存在于dirty中的key被删除后，该key就不再存在了。这里还有一点值得注意的是：当向dirty写入key4时，dirty会复制read中的未被删除的元素，由于key2已经被删除，因此顺带将read中的key2对应的value设置为哨兵(expunged)，并且该key不会被加入到dirty中。直到下一次promote，该key才会被回收（因为read被交换指向新的dirty，原read指向的内存将被GC）。

• 删除的key既存在于read，也存在于dirty中

目前上述sync.Map实例中既存在于read，也存在于dirty中的key有key1和key3（key2已经被删除），我们这里以删除key1为例：

after delete key1:
=====> sync.Map:
     read(amended=true):
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc0001041e0)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0001042a0)}
         "key1":&smap.entry{p:(unsafe.Pointer)(nil)}
     dirty:
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0001042a0)}
         "key1":&smap.entry{p:(unsafe.Pointer)(nil)}
     misses:0
     expunged:(unsafe.Pointer)(0xc0001041e0)
<===== sync.Map

我们看到删除key1后，read和dirty两个map中的key1均没有真正删除，而是将其value设置为nil。

我们再触发一次promote：连续调用两次导致read miss的LOAD：

        m.Load("key5")
        fmt.Println("\nafter load key5:")
        m.Dump()

        m.Load("key5")
        fmt.Println("\nafter load key5 2nd:")
        m.Dump()

调用后的Dump输出如下：

after load key5:
=====> sync.Map:
     read(amended=true):
         "key1":&smap.entry{p:(unsafe.Pointer)(nil)}
         "key2":&smap.entry{p:(unsafe.Pointer)(0xc000010200)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0000102c0)}
     dirty:
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0000102c0)}
         "key1":&smap.entry{p:(unsafe.Pointer)(nil)}
     misses:1
     expunged:(unsafe.Pointer)(0xc000010200)
<===== sync.Map

after load key5 2nd:
=====> sync.Map:
     read(amended=false):
         "key1":&smap.entry{p:(unsafe.Pointer)(nil)}
         "key3":&smap.entry{p:(unsafe.Pointer)(0xc0000102c0)}
     dirty:
     misses:0
     expunged:(unsafe.Pointer)(0xc000010200)
<===== sync.Map

我们看到虽然dirty中的key1已经处于被删除状态，但它仍算作dirty元素的个数，因此第二次miss才会触发promote。promote后，dirty被赋值给read，因此原dirty中的key1元素就顺带进入到read中，只能等下次写入一个不存在的新key时才能被置为哨兵值，并在下一次promote时才能被真正删除释放。

四. 小结

通过实例法，我们大致得到了sync.Map的工作原理和行为特征，从这些结果来看sync.Map并非是一个可应用于所有场合的goroutine-safe的map实现，但在读多写少的情况下，sync.Map才能发挥出最大的效能。

本文涉及代码可以在这里 https://github.com/bigwhite/experiments/tree/master/inside-syncmap 下载。

我的Go技术专栏：“改善Go语⾔编程质量的50个有效实践”上线了，欢迎大家订阅学习！

我的网课“Kubernetes实战：高可用集群搭建、配置、运维与应用”在慕课网上线了，感谢小伙伴们学习支持！

我爱发短信：企业级短信平台定制开发专家 https://tonybai.com/
smspush : 可部署在企业内部的定制化短信平台，三网覆盖，不惧大并发接入，可定制扩展； 短信内容你来定，不再受约束, 接口丰富，支持长短信，签名可选。

2020年4月8日，中国三大电信运营商联合发布《5G消息白皮书》，51短信平台也会全新升级到“51商用消息平台”，全面支持5G RCS消息。

著名云主机服务厂商DigitalOcean发布最新的主机计划，入门级Droplet配置升级为：1 core CPU、1G内存、25G高速SSD，价格5$/月。有使用DigitalOcean需求的朋友，可以打开这个链接地址：https://m.do.co/c/bff6eed92687 开启你的DO主机之路。

Gopher Daily(Gopher每日新闻)归档仓库 – https://github.com/bigwhite/gopherdaily

我的联系方式：

• 微博：https://weibo.com/bigwhite20xx
• 微信公众号：iamtonybai
• 博客：tonybai.com
• github: https://github.com/bigwhite

微信赞赏：

商务合作方式：撰稿、出书、培训、在线课程、合伙创业、咨询、广告合作。

本文翻译自《Illustrated Tales of Go Runtime Scheduler》。

译注：原文章结构有些乱，笔者自行在译文中增加了一些分级标题，让结构显得更清晰一些:)。

多goroutines形式的Go并发是编写现代并发软件的一种非常方便的方法，但是您的Go程序是如何高效地运行这些goroutines的呢？

在这篇文章中，我们将深入Go运行时底层，从设计角度了解Go运行时调度程序是如何实现其魔法的，并运用这些原理去解释在Go性能调试过程中产生的Go调度程序跟踪信息。

所有的工程奇迹都源于需要。因此，要了解为什么需要一个Go运行时调度程序以及它是如何工作的，我们可以让时间回到操作系统兴起的那个时代，回顾操作系统的历史可以使我们深入的了解问题的根源。如果不了解问题的根源，就没有解决它的希望。这就是历史所能做的。

一. 操作系统的历史

1. 单用户（无操作系统）。
2. 批处理，独占系统，直到运行完成。
3. 多道程序(译注:允许多个程序同时进入内存并运行)

多道程序的目的是使CPU和I/O重叠(overlap)。(译注:多道程序出现之前，当操作系统执行I/O操作时，CPU是空闲的；多道程序的引入实现了在一个程序占用CPU的时候，另一个程序在执行I/O操作)

那怎么实现多道程序(的CPU与I/O重叠)呢？两种方式:多道批处理系统和分时系统。

• 多道批处理系统

  • IBM OS/MFT（具有固定数量的任务的多道程序）
  • IBM OS/MVT（具有可变数量的任务的多道程序）在这里，每个作业(job)仅获得其所需的内存量。随着job的进出，内存的划分会发生变化。

• 分时

  • 这是一种多道程序设计，可以在作业之间快速切换。决定何时切换以及切换到哪个作业的过程就称为调度(scheduling)。

当前，大多数操作系统使用分时调度程序。

那么这些调度程序将用来调度什么实体(entity)呢？

• 不同的正在执行的程序（即进程process）
• 或作为进程子集存在使用CPU的基本单元:线程

但是在这些实体的切换是有代价的。

• 调度成本

因此，使用一个包含多个线程的进程的效率更高，因为进程创建既耗时又耗费资源。但是随后出现了多线程问题:C10k成为主要问题。

例如，如果将调度周期定为10ms（毫秒），并且有2个线程，则每个线程将分别获得5ms。如果您有5个线程，则每个线程将获得2ms。但是，如果有1000个线程怎么办？给每个线程一个10μs（微秒）的时间片？错，这样做很愚蠢，因为您将花费大量时间进行上下文切换，但是真正要完成的工作却进展缓慢或停滞不前。

您需要限制时间片的长度。在最后一种情况下，如果最小时间片为2ms并且有1000个线程，则调度周期需要增加到2s（10002ms）。如果有10,000个线程，则调度程序周期为20秒(100002ms)。在这个简单的示例中，如果每个线程都将分配给它的时间片用完，那么所有线程都完成一次运行需要20秒。因此，我们需要一些可以使并发成本降低而又不会造成过多开销的东西。

• 用户层线程
  • 线程完全由运行时系统（用户级库）管理。
  • 理想情况下，快速高效:切换线程的代价不比函数调用多多少。
  • 操作系统内核对用户层线程一无所知，并像对待单线程进程(single-threaded process)一样对其进行管理。

在Go中，我们知道这样的用户层线程被称为“Goroutine”。

• Goroutine

goroutine是由Go运行时管理的轻量级线程（lightweight thread）。要启动一个新的goroutine，只需在函数前面使用go关键字:go add(a, b)。

• Goroutine之旅

func main() {
    var wg sync.WaitGroup
    for i := 0; i <= 10; i++ {
        wg.Add(1)
        go func(i int) {
        defer wg.Done()
        fmt.Printf("loop i is - %d\n", i)
        }(i)
    }
    wg.Wait()
    fmt.Println("Hello, Welcome to Go")
}

https://play.golang.org/p/73lESLiva0A

您能猜出上面代码片段的输出吗？

loop i is - 10
loop i is - 0
loop i is - 1
loop i is - 2
loop i is - 3
loop i is - 4
loop i is - 5
loop i is - 6
loop i is - 7
loop i is - 8
loop i is - 9
Hello, Welcome to Go

如果我们看一下输出的一种组合，你可能马上就会有两个问题:

• 11个goroutine如何并行运行？魔法？
• goroutine以什么顺序运行？

上面的这两个提问给我们带来了问题。

• 问题概述
  • 如何将这些goroutines分配到在CPU处理器上运行的多个操作系统线程上运行？
  • 这些goroutines应该以什么顺序运行才能保证公平？

本文后续的讨论将主要围绕Go运行时调度程序从设计角度如何解决这些问题。但是，与所有问题一样，我们的讨论也需要定义一个明确的边界。否则，问题陈述可能太含糊，无法形成结论。调度程序可能针对多个目标中的一个或多个，对于我们来说，我们将自己限制在以下需求之内:

1. 应该是并行、可扩展且公平的。
2. 每个进程应可扩展到数百万个goroutine（C10M）
3. 内存利用率高。（RAM很便宜，但不是免费的。）
4. 系统调用不应导致性能下降。（最大化吞吐量，最小化等待时间）

让我们开始为调度程序建模，以逐步解决这些问题。

二. Goroutine调度程序模型 (译者自行加的标题)

1. 模型概述(译者自行加的标题)

a) 一个线程执行一个Goroutine

局限性:

• 并行和可扩展
  • 并行（是的）
  • 可扩展（不是真的）
• 每个进程不能扩展到数百万个goroutine（C10M）。

b) M:N线程—混合线程

M个操作系统内核线程执行N个“goroutine”

实际执行代码和并行执行都需要内核线程。但是线程创建起来很昂贵，因此我们将N个goroutines映射到M个内核线程上去执行。Goroutine是Go代码，因此我们可以完全控制它。而且它在用户空间中，创建起来很便宜。

但是由于操作系统对goroutine一无所知。因此每个goroutine都有一个状态，以帮助调度器根据goroutine状态知道要运行哪个goroutine。与内核线程的状态信息相比，goroutine的状态信息很小，因此goroutine的上下文切换变得非常快。

• 正在运行(Running) – 当前在内核线程上运行的goroutine。
• 可运行(Runnable) – 等待内核线程来运行的goroutine。
• 已阻塞(Blocked) – 等待某些条件的Goroutine（例如，阻塞在channel操作，系统调用，互斥锁上的goroutine）

因此，Go运行时调度器通过将N个Goroutine多路复用到M个内核线程的方式来管理处于各种不同状态的goroutines。

2. 简单的M:N调度器

在我们简单的M:N调度器中，我们有一个全局运行队列(global run queue)，某些操作将一个新的goroutine放入运行队列。M个内核线程访问调度程序从“运行队列”中获取并运行goroutine。多个线程正在尝试访问相同的内存区域，因此使用互斥锁来同步对该运行队列的访问。

但是，那些已阻塞的goroutine在哪里？

下面是goroutine可能会阻塞的情况：

1. 在channel上发送和接收
2. 网络I/O操作
3. 阻塞的系统调用
4. 使用定时器
5. 使用互斥锁

那么我们将这些阻塞的goroutine放在哪里呢？— 将这些阻塞的goroutine放置在哪里的设计决策基本上是围绕一个基本原理进行的：

阻塞的goroutine不应阻塞底层内核线程！（避免线程上下文切换的成本）

channel操作期间阻塞的Goroutine

每个channel都有一个recvq(waitq)，用于存储试图从该channel读取数据而阻塞的goroutine。

Sendq(waitq)存储试图将数据发送到channel而被阻止的goroutine 。（channel实现原理:-https://codeburst.io/diving-deep-into-the-golang-channels-549fd4ed21a8）

channel本身会将channel操作后的未阻塞goroutine放入“运行”队列(run queue)。

那系统调用呢？

首先，让我们看一下阻塞系统调用。系统调用会阻塞底层内核线程，因此我们无法在该线程上调度任何其他Goroutine。

隐含阻塞系统调用可降低并行度。

一旦发生阻塞系统调用，我们无法再在M2线程上安排任何其他Goroutine运行，从而导致CPU浪费。由于我们有工作要做，但没法运行它。

恢复并行度的方法是在进入系统调用时，我们可以唤醒另一个线程，该线程将从运行队列中选择可运行的goroutine。

但是现在，系统调用完成后，我们有超额等待调度的goroutine。因此，我们不会立即运行从阻塞系统调用中返回的goroutine。我们会将其放入调度程序的运行队列中。

因此，在程序运行时，线程数远大于cpu核数。尽管没有明确说明，线程数大于cpu核数，并且所有空闲线程也由运行时管理，以避免启动过多的线程。

https://golang.org/pkg/runtime/debug/#SetMaxThreads

初始设置为10,000个线程，如果超过10,000个线程，程序将崩溃。

非阻塞系统调用-将goroutine阻塞在Integrated runtime poller上 ，并释放线程以运行另一个goroutine。

例如，在非阻塞I/O（例如HTTP调用）的情况下。由于资源尚未准备就绪，第一个syscall将不会成功，这将迫使Go使用network poller并将goroutine暂停。

部分net.Read函数的实现：

    n, err := syscall.Read(fd.Sysfd, p)
        if err != nil {
            n = 0
            if err == syscall.EAGAIN && fd.pd.pollable() {
                if err = fd.pd.waitRead(fd.isFile); err == nil {
                    continue
                }
            }
    }

一旦完成第一个系统调用并明确指出资源尚未准备就绪，goroutine将暂停，直到network poller通知它资源已准备就绪。在这种情况下，线程M将不会被阻塞。

Poller将基于操作系统使用select/kqueue/epoll/IOCP等机制来知道哪个文件描述符已准备好，一旦文件描述符准备好进行读取或写入，它将把goroutine放回到运行队列中。

还有一个Sysmon OS线程，如果超过10ms未轮询网络，它就将定期轮询网络，并将已就绪的G添加到队列中。

基本上所有goroutine都被阻塞在下面操作上：

1. channel
2. 互斥锁
3. 网络IO
4. 定时器

有某种队列，可以帮助调度这些goroutine。

现在，运行时拥有具有以下功能的调度程序。

• 它可以处理并行执行（多线程）。
• 处理阻塞系统调用和网络I/O。
• 处理阻塞在用户级别（在channel上）的调用。

但这不是可伸缩的(scalable)。

您可以通过Mutex同步全局运行队列，但最终会遇到一些问题，例如

1. 缓存一致性保证的开销。
2. 在创建，销毁和调度Goroutine G时进行激烈的锁竞争。

使用分布式调度程序解决可伸缩性问题。

分布式调度程序-每个线程一个运行队列

这样，我们可以看到的直接好处是，每个线程的本地运行队列(local run queue)现在都没有使用mutex。仍然有一个带有mutex的全局运行队列，但仅在特殊情况下使用。它不会影响可伸缩性。

但是现在，我们有多个运行队列。

1. 本地运行队列
2. 全局运行队列
3. 网络轮询器(network poller)

我们应该从哪里运行下一个goroutine？

在Go中，轮询顺序定义如下：
1. 本地运行队列
2. 全局运行队列
3. 网络轮询器
4. 工作偷窃(work stealing)

即首先检查本地运行队列，如果为空则检查全局运行队列，然后检查网络轮询器，最后进行“偷窃工作”。到目前为止，我们对1,2,3有了一些概述。让我们看一下“工作偷窃(work stealing)”。

工作偷窃

如果本地工作队列为空，请尝试“从其他队列中偷窃工作”

当一个线程有太多工作要做而另一个线程空闲时，工作偷窃可以解决这个问题。在Go中，如果本地队列为空，工作偷窃将尝试满足以下条件之一。

• 从全局队列中拉取工作。
• 从网络轮询器中拉取工作
• 从其他线程的本地队列中偷窃工作

到目前为止，Go运行时的调度器具有以下功能：

• 它可以处理并行执行（使用多线程）。
• 处理阻塞系统调用和网络I/O。
• 处理用户级别（比如：在channel）的阻塞调用。
• 可伸缩扩展(scalable)

但这仍不是最有效的。

还记得我们在阻塞系统调用中恢复并行度的方式吗？

它暗示在一个系统调用中我们可以有多个内核线程（可以是10或1000），这可能会比cpu核数多很多。这个方案将最终在以下期间产生了恒定的开销:

• 偷窃工作时，它必须同时扫描所有内核线程（空闲的和运行goroutine的）本地运行队列，并且大多数都将是空闲的。
• 垃圾回收，内存分配器都会遇到相同的扫描问题。（https://blog.learngoprogramming.com/a-visual-guide-to-golang-memory-allocator-from-ground-up-e132258453ed）

使用M:P:N线程克服效率问题。

M:P:N（3级调度程序）— 引入逻辑处理器P

P —表示处理器，可以将其视为在线程上运行的本地调度程序

逻辑进程P的数量始终是固定的。（默认为当前进程可以使用的逻辑CPU数量）

然后，我们将本地运行队列（LRQ）放入固定数量的逻辑处理器（P）中(译者注：而不是每个内核线程一个本地运行队列)。

Go运行时将首先根据计算机的逻辑CPU数量（或根据请求）创建固定数量的逻辑处理器P。

每个goroutine（G）将在分配了逻辑CPU（P）的OS线程（M）上运行。

所以现在我们在以下期间没有了恒定的开销:

• 偷窃工作 -只需扫描固定数量的逻辑处理器（P）的本地运行队列。
• 垃圾回收，内存分配器也将获得相同的好处。

使用固定逻辑处理器（P）的系统调用呢？

Go通过将它们包装在运行时中来优化系统调用（无论是否阻塞）。

阻塞SYSCALL方法封装在runtime.entersyscall(SB)和 runtime.exitsyscall(SB)之间。

从字面上看，某些逻辑在进入系统调用之前被执行，而某些逻辑在系统调用返回之后执行。进行阻塞的系统调用时，此包装器将自动将P与线程M(即将执行阻塞系统调用的线程)解绑，并允许另一个线程在其上运行。

这使得Go运行时可以高效地处理阻塞的系统调用，而无需增加运行队列(译注：本地运行队列数量始终是和P数量一致的)。

一旦阻塞系统调用返回，会发生什么？

• 运行时会尝试获取之前绑定的那个P，然后继续执行。
• 运行时尝试在P空闲列表中获取一个P并恢复执行。
• 运行时将goroutine放在全局队列中，并将关联的M放回M空闲列表。

自旋线程和空闲线程

当M2线程在syscall返回后变得空闲时。如何处理这个空闲的M2线程。从理论上讲，如果线程完成了所需的操作，则应将其销毁，然后再安排进程中的其他线程到CPU上执行。这就是我们通常所说的操作系统中线程的“抢占式调度”。

考虑上述syscall中的情况。如果我们销毁了M2线程，而同时M3线程即将进入syscall。此时，在OS创建新的内核线程并将其调度执行之前，我们无法处理可运行的goroutine。频繁的线程前抢占操作不仅会增加OS的负载，而且对于性能要求更高的程序几乎是不可接受的。

因此，为了适当地利用操作系统的资源并防止频繁的线程抢占给操作系统带来的负担，我们不会销毁内核线程M2，而是使其执行自旋操作并以备将来使用。尽管这看起来是在浪费一些资源。但是，与线程之间的频繁抢占以及频繁的创建和销毁操作相比，“空闲线程”要付出的代价更少。

Spinning Thread(自旋线程) — 例如，在具有一个内核线程M（1）和一个逻辑处理器（P）的Go程序中，如果正在执行的M被syscall阻塞，则运行时会请求与P数量相同的“Spinning Threads”以允许等待的可运行goroutine继续执行。因此，在此期间，内核线程的数量M将大于P的数量（自旋线程+阻塞线程）。因此，即使将runtime.GOMAXPROCS的值设置为1，程序也将处于多线程状态。

调度中的公平性如何？—公平地选择下一个要执行的goroutine

与许多其他调度程序一样，Go也具有公平性约束，并且由goroutine的实现所强加，因为Runnable goroutine应该最终得到调度并运行。

这是Go Runtime Scheduler的四个典型的公平性约束：

任何运行时间超过10ms的goroutine都被标记为可抢占（软限制）。但是，抢占仅在函数执行开始处才能完成。Go当前在函数开始处中使用了由编译器插入的协作抢占点。

• 无限循环 – 抢占（约10毫秒的时间片）- 软限制

但请小心无限循环，因为Go的调度程序不是抢先的（直到Go 1.13）。如果循环不包含任何抢占点（例如函数调用或分配内存），则它们将阻止其他goroutine的运行。一个简单的例子是:

package main

func main() {
    go println("goroutine ran")
    for {}
}

如果你运行:

GOMAXPROCS=1 go run main.go

直到Go（1.13）才可能打印该语句。由于缺少抢占点，main Goroutine将独占处理器。

• 本地运行队列 -抢占（〜10ms时间片）- 软限制
• 通过每61次调度就检查一次全局运行队列，可以避免全局运行队列处于“饥饿”状态。
• 网络轮询器饥饿 后台线程会在主工作线程未轮询的情况下偶尔会轮询网络。

Go 1.14有一个新的“非合作抢占”机制。

有了这种机制，Go运行时便有了具有所有必需功能的Scheduler。

• 它可以处理并行执行（多线程）。
• 处理阻塞系统调用和网络I/O。
• 处理用户级别（在channel上）的阻塞调用。
• 可扩展
• 高效
• 公平

这提供了大量的并发性，并且始终尝试实现最大的利用率和最小的延迟。

现在，我们总体上对Go运行时调度程序有了一些了解，我们如何使用它？Go为我们提供了一个跟踪工具，即调度程序跟踪(scheduler trace)，目的是提供有关调度行为的信息并用来调试与goroutine调度器伸缩性相关的问题。

三. 调度器跟踪

使用GODEBUG=schedtrace=DURATION环境变量运行Go程序以启用调度程序跟踪。（DURATION是以毫秒为单位的输出周期。）

有关调度器跟踪的内容，Go Wiki拥有更多信息。

参考:Dmitry Vyukov的可扩展Go Scheduler设计文档和演讲 https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sLKhJYD0Y_kqxDv3I3XMw/edit

Gopher艺术作品致谢:Ashley Mcnamara。

我的网课“Kubernetes实战:高可用集群搭建、配置、运维与应用”在慕课网上线了，感谢小伙伴们学习支持！

我爱发短信:企业级短信平台定制开发专家 https://tonybai.com/
smspush : 可部署在企业内部的定制化短信平台，三网覆盖，不惧大并发接入，可定制扩展； 短信内容你来定，不再受约束, 接口丰富，支持长短信，签名可选。

著名云主机服务厂商DigitalOcean发布最新的主机计划，入门级Droplet配置升级为:1 core CPU、1G内存、25G高速SSD，价格5$/月。有使用DigitalOcean需求的朋友，可以打开这个链接地址:https://m.do.co/c/bff6eed92687 开启你的DO主机之路。

Gopher Daily(Gopher每日新闻)归档仓库 – https://github.com/bigwhite/gopherdaily

我的联系方式:

微博:https://weibo.com/bigwhite20xx
微信公众号:iamtonybai
博客:tonybai.com
github: https://github.com/bigwhite

微信赞赏:

商务合作方式:撰稿、出书、培训、在线课程、合伙创业、咨询、广告合作。