AlphaGao's Blog

恐惧源于火力不足，紧张源于准备不足！

0%

Go 中 map 与 sync.Map 性能比较

Posted on Edited on In Views: Valine:

sync.Map 是在 Go 1.9 版本新增的并发安全的 map 类型。我们知道通过将普通的 map 与 sync.Mutex 或 sync.RWMutex 结合也能实现并发安全的 map 结构，那为什么 Go 还要提供新的 sync.Map类型呢，又与结合 Mutex 的 map 有什么区别呢？一起来看下吧。

sync.Map 源码分析

一个标准的 sync.Map 的内部结构为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
type Map struct {
	mu Mutex

	// read contains the portion of the map's contents that are safe for
	// concurrent access (with or without mu held).
	//
	// The read field itself is always safe to load, but must only be stored with
	// mu held.
	//
	// Entries stored in read may be updated concurrently without mu, but updating
	// a previously-expunged `entry` requires that the `entry` be copied to the dirty
	// map and unexpunged with mu held.
	read atomic.Pointer[readOnly]

	// dirty contains the portion of the map's contents that require mu to be
	// held. To ensure that the dirty map can be promoted to the read map quickly,
	// it also includes all of the non-expunged entries in the read map.
	//
	// Expunged entries are not stored in the dirty map. An expunged `entry` in the
	// clean map must be unexpunged and added to the dirty map before a new value
	// can be stored to it.
	//
	// If the dirty map is nil, the next write to the map will initialize it by
	// making a shallow copy of the clean map, omitting stale entries.
	dirty map[any]*entry

	// misses counts the number of loads since the read map was last updated that
	// needed to lock mu to determine whether the key was present.
	//
	// Once enough misses have occurred to cover the cost of copying the dirty
	// map, the dirty map will be promoted to the read map (in the unamended
	// state) and the next store to the map will make a new dirty copy.
	misses int
}

可以看到 sync.Map 内部也是使用了一个 Mutex 互斥锁，与此同还有其他几个属性。

read

read 是仅用于并发读取的只读快照，无论是否持有锁，该结构的读取都是并发安全的。但更新操作就必须持有 mu 这个锁才能继续。这里也许你会觉得前后注释冲突，明明说更新 read 需要持有 mu ，但是又说可以在不持有锁的情况下并发修改。但其实这里的更新操作是将 dirty 升级为 read，而不是更新 read 里的某条 entry，修改某一条 entry 通过原子操作就能实现不持有锁还能保证并发安全。

然后如果 read 中有一条 entry 被标记删除了，后面还要继续修改这条 entry 的值就得持有锁，并且将该条 entry 移到 dirty 中，再写入新值。例如：

1
2
3
4
m := sync.Map{}
m.Store("foo", 1)
m.Delete("foo") // foo 被 expunge 了
m.Store("foo", 2)
  • 第一次 Store("foo", 1) → 写入 read。
  • Delete("foo") → foo 被标记为 expunged。
  • 再次 Store("foo", 2) → 由于 foo 已被 expunge，不能直接更新 read，
    必须加锁，把 foo 移到 dirty 并取消删除状态，然后写入新值。此时这条 entry 在 dirty 中而不在 read 中。

dirty

dirty 是用于存储新写入的 entry，也就是此前不存在于 read 中的，因为如果已在 read 中的 entry 的更新是可以直接无锁操作的。同时为了保证 dirty 能够快速升级为 read，在 dirty 初始化的时候就将 read 的内容写入到 dirty 中。但我并没有在 Store 方法的源码中看到有同时写入 dirty 的逻辑，那是因为 entry 的结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// An `entry` is a slot in the map corresponding to a particular key.
type `entry` struct {
	// p points to the interface{} value stored for the `entry`.
	//
	// If p == nil, the `entry` has been deleted, and either m.dirty == nil or
	// m.dirty[key] is e.
	//
	// If p == expunged, the `entry` has been deleted, m.dirty != nil, and the `entry`
	// is missing from m.dirty.
	//
	// Otherwise, the `entry` is valid and recorded in m.read.m[key] and, if m.dirty
	// != nil, in m.dirty[key].
	//
	// An `entry` can be deleted by atomic replacement with nil: when m.dirty is
	// next created, it will atomically replace nil with expunged and leave
	// m.dirty[key] unset.
	//
	// An `entry`'s associated value can be updated by atomic replacement, provided
	// p != expunged. If p == expunged, an `entry`'s associated value can be updated
	// only after first setting m.dirty[key] = e so that lookups using the dirty
	// map find the `entry`.
	p atomic.Pointer[any]
}

entry 实际上是个带类型的指针容器，而 dirty 在初始化的时候逻辑为：

1
2
3
4
5
6
7
8
9
10
11
12
13
func (m *Map) dirtyLocked() {
	if m.dirty != nil {
		return
	}

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

简单来说，就是将 read 的值遍历后放进 dirty，而因为 entry 是指针结构，因此在更新 read 的时候，dirty 中也会同步更新。当需删除某条 entry 的时候，会直接将该条 entry 从 dirty 中删除，但对于 read 就只是标记删除：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
	read := m.loadReadOnly()
	e, ok := read.m[key]
	if !ok && read.amended {
		m.mu.Lock()
		read = m.loadReadOnly()
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
			delete(m.dirty, key)
			// Regardless of whether the `entry` was present, record a miss: this key
			// will take the slow path until the dirty map is promoted to the read
			// map.
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if ok {
		return e.delete()
	}
	return nil, false
}

如果 dirty 是 nil，那么在下一次写操作的时候，会通过 read 的浅拷贝来初始化 dirty，此浅拷不会将标记删除的 entry 放进 dirty 中。

misses

misses 是一个计数器，统计从 read 上一次更新以来，也就是从 dirty 升级到 read，查询 read 没有命中的次数，如没有命中 read，就会加锁去 dirty 中查询，这就是一次 miss。当 miss 次数达一定量，就会触发 dirty 到 read 的升级。这样可以避免频繁的持有 mu 去查询 dirty，又能避免每次有新的 entry 就立刻将 dirty 升级为 read 带来的性能开销。

那么具体 misses 到多少的时候会触发 dirty 升级为 read 呢？通过 missLocked 方法可以看到：

1
2
3
4
5
6
7
8
9
func (m *Map) missLocked() {
	m.misses++
	if m.misses < len(m.dirty) {
		return
	}
	m.read.Store(&readOnly{m: m.dirty})
	m.dirty = nil
	m.misses = 0
}

当 misses 的值等于 dirty 的数量的时候，就会触发 dirty 升级为 read，然后 misses 归零。

总结一下，sync.Map 内部有 read 和 dirty 2 个存储结构，read 用于只读查询，并且查询操作是不带锁的，这样查比加了锁的普通 map 更快。而如果没有命中 read 存储，就会加锁查询 dirty，并标记一次 miss。每次新增加的 entry 会直接写入到 dirty。当写入的新 entry 的数量和 miss 的数量相等，就会触发 dirty 升级为 read。很明显升级的开销是比较大的，因此写多读少的场景是不适合 sync.Map 的，因为可能会频繁触发 dirty 升级为 read。

此时再回头看官网文档里说的：

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.

sync.Map 只适用 2 个场景：

一、每个 entry 仅写入一次，之后就是大量的读，此时的 sync.Map 其实就是充当缓存的作用。

  • 这种场景下 entry 一旦写入就会立刻触发 dirty 升级写入到 read 中，之后的查询都是无锁操作，性能会非常高

二、多个 goroutine 读写操作，但操作的是不相交的 key 集合

  • 这个场景下，因为每个 goroutine 操作的 key 不相同，不会产生激烈的锁竞争，read + dirty 的机制的优势同样能够发挥出来。

sync.Map 与 map+sync.RWMutex 性能差异

与 sync.Map 的 read + dirty 机制下的查询几乎无锁操作相比，map + sync.RWMutex 的形式，读写都要抢同一个锁，在高并发下很容易成为性能瓶颈。那么我们就来看看二者之间的性能差异到底有多大。

通过 Go 的 benchmark，我们能够轻易得到 2 种 map 的性能差异：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
package main

import (
	"fmt"
	"strconv"
	"sync"
	"sync/atomic"
	"testing"
)

// ====== 基于 RWMutex 的并发 map ======
type RWMap struct {
	mu sync.RWMutex
	m  map[string]string
}

func NewRWMap() *RWMap {
	return &RWMap{m: make(map[string]string)}
}

func (rm *RWMap) Load(key string) (string, bool) {
	rm.mu.RLock()
	defer rm.mu.RUnlock()
	v, ok := rm.m[key]
	return v, ok
}

func (rm *RWMap) Store(key, value string) {
	rm.mu.Lock()
	defer rm.mu.Unlock()
	rm.m[key] = value
}

// ====== 测试函数（传入读写比例） ======
func benchmarkRWMap(b *testing.B, writePercent int, keyRange int) {
	rm := NewRWMap()
	var reads, writes int64

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			key := strconv.Itoa(i % keyRange)
			if i%100 < writePercent { // 按比例写
				rm.Store(key, "value")
				atomic.AddInt64(&writes, 1)
			} else {
				rm.Load(key)
				atomic.AddInt64(&reads, 1)
			}
			i++
		}
	})
	b.ReportMetric(float64(reads), "reads")
	b.ReportMetric(float64(writes), "writes")
}

func benchmarkSyncMap(b *testing.B, writePercent int, keyRange int) {
	var sm sync.Map
	var reads, writes int64

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			key := strconv.Itoa(i % keyRange)
			if i%100 < writePercent { // 按比例写
				sm.Store(key, "value")
				atomic.AddInt64(&writes, 1)
			} else {
				sm.Load(key)
				atomic.AddInt64(&reads, 1)
			}
			i++
		}
	})
	b.ReportMetric(float64(reads), "reads")
	b.ReportMetric(float64(writes), "writes")
}

// ====== 不同比例测试 ======
func BenchmarkCompare(b *testing.B) {
	proportions := []int{10, 50, 90} // 写占比（%）
	keyRanges := []int{1_000, 10_1000, 100_000, 1_000_000}
	for _, keyRange := range keyRanges {
		for _, p := range proportions {
			b.Run(fmt.Sprintf("RWMap_Write%d%%", p), func(b *testing.B) {
				benchmarkRWMap(b, p, keyRange)
			})
			b.Run(fmt.Sprintf("SyncMap_Write%d%%", p), func(b *testing.B) {
				benchmarkSyncMap(b, p, keyRange)
			})
		}
	}
}

我分别在 key 的数量规模在 1k、1w、10w 和 100w 的级别下，再对分别写操作占比 10%、50%、90% 的场景下跑性能测试，得到以下结果。

首先来看 key 数量级为 1000 的情况：

1
2
3
4
5
6
7
8
9
10
goos: darwin
goarch: amd64
pkg: github.com/alphagao1993/hello-go/map
cpu: Intel(R) Core(TM) i7-8850H CPU @ 2.60GHz
BenchmarkCompare/RWMap_1000_Write10%-12         	 6669214	       178.9 ns/op	   6002244 reads	    666970 writes	       2 B/op	       0 allocs/op
BenchmarkCompare/SyncMap_1000_Write10%-12       	53742982	        29.23 ns/op	  48368622 reads	   5374360 writes	       6 B/op	       1 allocs/op
BenchmarkCompare/RWMap_1000_Write50%-12         	 4398858	       286.9 ns/op	   2199266 reads	   2199592 writes	       2 B/op	       0 allocs/op
BenchmarkCompare/SyncMap_1000_Write50%-12       	36015285	        35.23 ns/op	  18007510 reads	  18007775 writes	      18 B/op	       1 allocs/op
BenchmarkCompare/RWMap_1000_Write90%-12         	 6561000	       174.8 ns/op	    656044 reads	   5904956 writes	       2 B/op	       0 allocs/op
BenchmarkCompare/SyncMap_1000_Write90%-12       	27884427	        48.76 ns/op	   2788395 reads	  25096032 writes	      31 B/op	       2 allocs/op

在写比例 10% 的场景下，RWMap 每次操作的平耗时为 178.9ns，申请内存次为 0，而 sync.Map 的平均操时间是 29.23ns，是 RWMap 的 1/6，平均申请内存 1 次；
在写比例 50% 的场景下，RWMap 每次操作的平耗时为 286.9ns，申请内存次为 0，而 sync.Map 的平均操时间是 35.23ns，是 RWMap 的 1/8，平均申请内存 1 次；
在写比例 90% 的场景下，RWMap 每次操作的平耗时为 174.8ns，申请内存次为 0，而 sync.Map 的平均操时间是 48.76ns，是 RWMap 的 1/3，平均申请内存 2 次；

很明显看到，当写比例达到 90%，sync.Map 的性能出明显下降，几乎每次操作都要申请 2 次内存，但即便如此，sync.Map 的读写性能还是远快于 RWMap。

再来看 key 的数量为 1w 的场景：

1
2
3
4
5
6
BenchmarkCompare/RWMap_10000_Write10%-12        	 5330550	       214.9 ns/op	   4797432 reads	    533118 writes	       3 B/op	       0 allocs/op
BenchmarkCompare/SyncMap_10000_Write10%-12      	35376084	        33.64 ns/op	  31838438 reads	   3537646 writes	       7 B/op	       1 allocs/op
BenchmarkCompare/RWMap_10000_Write50%-12        	 3341437	       338.3 ns/op	   1670533 reads	   1670904 writes	       4 B/op	       0 allocs/op
BenchmarkCompare/SyncMap_10000_Write50%-12      	29461378	        54.60 ns/op	  14730535 reads	  14730843 writes	      19 B/op	       1 allocs/op
BenchmarkCompare/RWMap_10000_Write90%-12        	 4815813	       273.3 ns/op	    481526 reads	   4334287 writes	       4 B/op	       0 allocs/op
BenchmarkCompare/SyncMap_10000_Write90%-12      	18878964	        64.24 ns/op	   1887857 reads	  16991107 writes	      32 B/op	       2 allocs/op

还是能够看出随着写比例的上升，sync.Map 的性能有所下降，但仍然远快于 RWMap;

key 数量级为 10w 的场景：

1
2
3
4
5
6
BenchmarkCompare/RWMap_100000_Write10%-12       	 4503927	       249.3 ns/op	   4053487 reads	    450440 writes	       5 B/op	       0 allocs/op
BenchmarkCompare/SyncMap_100000_Write10%-12     	25254602	        43.32 ns/op	  22729090 reads	   2525512 writes	       9 B/op	       1 allocs/op
BenchmarkCompare/RWMap_100000_Write50%-12       	 3342763	       324.0 ns/op	   1671284 reads	   1671479 writes	       6 B/op	       0 allocs/op
BenchmarkCompare/SyncMap_100000_Write50%-12     	17258281	        59.10 ns/op	   8629031 reads	   8629250 writes	      22 B/op	       2 allocs/op
BenchmarkCompare/RWMap_100000_Write90%-12       	 4746644	       236.0 ns/op	    474600 reads	   4272044 writes	       7 B/op	       0 allocs/op
BenchmarkCompare/SyncMap_100000_Write90%-12     	14010303	        79.63 ns/op	   1400966 reads	  12609337 writes	      34 B/op	       2 allocs/op

依然能够看到当写比上升， sync.Map 的性能在下降，但还是明显高于 RWMap，奇怪的是 RWMap 在写比例为 50% 的时候性能下降，但在写比例 90% 的时候又涨上去了，这有点特殊；

key 数量为 100w 的场景：

1
2
3
4
5
6
BenchmarkCompare/RWMap_1000000_Write10%-12      	 4540042	       251.5 ns/op	   4085982 reads	    454060 writes	       8 B/op	       0 allocs/op
BenchmarkCompare/SyncMap_1000000_Write10%-12    	 5497419	       314.2 ns/op	   4947626 reads	    549793 writes	      47 B/op	       1 allocs/op
BenchmarkCompare/RWMap_1000000_Write50%-12      	 3618709	       344.2 ns/op	   1809258 reads	   1809451 writes	      12 B/op	       1 allocs/op
BenchmarkCompare/SyncMap_1000000_Write50%-12    	 4418014	       353.6 ns/op	   2208906 reads	   2209108 writes	      47 B/op	       2 allocs/op
BenchmarkCompare/RWMap_1000000_Write90%-12      	 5323965	       266.0 ns/op	    532340 reads	   4791625 writes	      15 B/op	       1 allocs/op
BenchmarkCompare/SyncMap_1000000_Write90%-12    	 3304040	       446.7 ns/op	    330360 reads	   2973680 writes	      48 B/op	       3 allocs/o

在这个数量级下，我们终于看到 sync.Map 的性能均低于 RWMap，这应该是大容量内存的拷贝带来的性能开销，已经超过了锁竞争导致的开销，另一方面，当数量级增加，sync.Map 与 RWMap 由不同机制的带来的性能优势也在被抹平。

另外我也观察到一个奇怪的现象，RWMap 在写比例为 50% 的时候性能最差（同等数量级下）,而在写比例上升到 90% 的时候性能又有所提升。这是因为 RWMap 使用的是读写锁，在读写相当的情况下，共享锁的竞争最激烈，锁状态的频繁变化会拖慢读写性能，而当写比例增加到 90% 的时候，基本都是写操作之间锁的竞争，此时 RWMutex 几乎等同于 Mutex，只需要等待其他写操作释放锁即可，相比之下对性能的影响更小。

结论

通过以上源码分析和性能测试的比较，我们得出结论，在数量级较低的情况下，以本人的 CPU(i7-8850H CPU @ 2.60GH) 为例，当 key 数量达到百万级别时，sync.Map 的读写性能均低于 RWMap ，而在百万数量级别以下，sync.Map 始终占据优势。