乐趣区

关于前端工程师:前端工程师2022版完结无密

jiezi

download：前端工程师 2022 版 - 完结无密

通过实例深入理解 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/e… 上面

$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 数据:

图：sync.Map 内置两个原生 map
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{}))

复制代码

  1. 写入数据 (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。

  1. 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 状态没有任何影响。

退出移动版