关于node.js:Nodejs工程师养成计划完整无密某课

0次阅读

共计 9014 个字符，预计需要花费 23 分钟才能阅读完成。

通过实例深入理解 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 的行为特色。

初始状态
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{}))

复制代码

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

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

正文完