Go sync.Map 解读

背景

项目中遇到了需要使用高并发的 map 的场景，众所周知 Go 官方的原生 map 是不支持并发读写的，直接并发的读写很容易触发 panic。

解决的办法有两个：

• 自己配一把锁sync.Mutex或者更加考究一点配一把读写锁sync.RWMutex。这种方案简约直接，但是缺点也明显，就是性能不会太高。
• 使用 Go 语言在 2017 年发布的 Go 1.9 中正式加入了并发安全的字典类型sync.Map。

很显然，方案 2 是优雅且实用的。但是，为什么官方的sync.Map能够在 lock free无锁并发 的前提下，保证足够高的性能❓本文结合源码进行简单的分析。

核心思想

如果要保证并发的安全，最朴素的想法就是使用锁，但是这意味着要把一些并发的操作强制串行化，性能自然就会下降。

事实上，除了使用锁，还有一个办法也可以达到类似并发安全的目的，就是原子操作atomic。sync.Map的设计非常巧妙，充分利用了atmoic和mutex的配合。

• read map 由于是原子包托管，主要负责高性能，但是无法保证拥有全量的 key，因为对于新增 key，会首先加到 dirty 中，所以 read 某种程度上，类似于一个 key 的快照。
• dirty map 拥有全量的 key，当Store操作要新增一个之前不存在的 key 的时候，预先是增加到 dirty 中的。
• 在查找指定的 key 的时候，总会先去只读字典中寻找，并不需要锁定互斥锁。只有当 read 中没有，但 dirty 中可能会有这个 key 的时候，才会在锁的保护下去访问 dirty。
• 在存储键值对的时候，只要 read 中已存有这个 key，并且该键值对未被标记为expunged，就会把新值存到里面并直接返回，这种情况下也不需要用到锁。
• read 和 dirty 之间是会互相转换的，在 dirty 中查找 key 对次数足够多的时候，sync.Map会把 dirty 直接作为 read，即触发 dirty=>read升级，同时在某些情况，也会出现read=>dirty的重塑。

数据结构

尽量使用原子操作，最大程度上减少了锁的使用，从而接近了 lock free 的效果。

sync.Map 类型的底层数据结构如下👇

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

type Map struct {
 mu Mutex
 read atomic.Value // readOnly
 dirty map[interface{}]*entry
 misses int
}

// Map.read 属性实际存储的是 readOnly。
type readOnly struct {
 m       map[interface{}]*entry
 amended bool
}

• mu：互斥锁，用于保护 read 和 dirty。
• read：只读数据，支持并发读取（atomic.Value类型）。如果涉及到更新操作，则只需要加锁来保证数据安全。
• read 实际存储的是 readOnly 结构体，内部也是一个原生 map，amended 属性用于标记 read 和 dirty 的数据是否一致。
• dirty：读写数据，是一个原生 map，也就是非线程安全。操作 dirty 需要加锁来保证数据安全。
• misses：统计有多少次读取 read 没有命中。每次 read 中读取失败后，misses 的计数值都会加 1。

在 read 和 dirty 中，都有涉及到的结构体：

1
2
3

type entry struct {
 p unsafe.Pointer // *interface{}
}

其包含一个指针 p, 用于指向用户存储的元素（key）所指向的 value 值。

Store写入过程

先来看 expunged

1

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

expunged 是一个指向任意类型的指针，用来标记从 dirty map 中删除的 entry。

sync.Map 类型的 Store 方法，该方法的作用是新增或更新一个元素。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func (m *Map) Store(key, value interface{}) {
 read, _ := m.read.Load().(readOnly)
 if e, ok := read.m[key]; ok && e.tryStore(&value) {
  return
 }
  ...
}

// tryStore stores a value if the entry has not been expunged.
//
// If the entry is expunged, tryStore returns false and leaves the entry
// unchanged.
func (e *entry) tryStore(i *interface{}) bool {
	for {
		p := atomic.LoadPointer(&e.p)
		if p == expunged {
			return false
		}
		if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
			return true
		}
	}
}

调用Load方法检查m.read中是否存在这个元素。若存在，且没有被标记为 expunged 删除状态，则尝试存储。

若该元素不存在或已经被标记为删除状态，则继续走到下面流程👇

 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

func (m *Map) Store(key, value interface{}) {
    ...
    m.mu.Lock()
	read, _ = m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok {
		if e.unexpungeLocked() {
			// 如果 read map 中存在该 key，但 p == expunged，则说明 m.dirty != nil 并且 m.dirty 中不存在该 key 值 此时:
			//    a. 将 p 的状态由 expunged  更改为 nil
			//    b. dirty map 插入 key
			m.dirty[key] = e
		}
		// 更新 entry.p = value (read map 和 dirty map 指向同一个 entry)
		e.storeLocked(&value)
	} else if e, ok := m.dirty[key]; ok {
		// 如果 read map 中不存在该 key，但 dirty map 中存在该 key，直接写入更新 entry(read map 中仍然没有这个 key)
		e.storeLocked(&value)
	} else {
		// 如果 read map 和 dirty map 中都不存在该 key，则：
		//	  a. 如果 dirty map 为空，则需要创建 dirty map，并从 read map 中拷贝未删除的元素到新创建的 dirty map
		//    b. 更新 amended 字段，标识 dirty map 中存在 read map 中没有的 key
		//    c. 将 kv 写入 dirty map 中，read 不变
		if !read.amended {
		    // 到这里就意味着，当前的 key 是第一次被加到 dirty map 中。
			// store 之前先判断一下 dirty map 是否为空，如果为空，就把 read map 浅拷贝一次。
			m.dirtyLocked()
			m.read.Store(readOnly{m: read.m, amended: true})
		}
		// 写入新 key，在 dirty 中存储 value
		m.dirty[key] = newEntry(value)
	}
	m.mu.Unlock()
}

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
		}
	}
}

func (e *entry) tryExpungeLocked() (isExpunged bool) {
	p := atomic.LoadPointer(&e.p)
	for p == nil {
		// 将已经删除标记为nil的数据标记为expunged
		if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
			return true
		}
		p = atomic.LoadPointer(&e.p)
	}
	return p == expunged
}

这里使用了双检查的处理，因为在下面的两个语句中，这两行语句并不是一个原子操作。

1
2

if !ok && read.amended {
		m.mu.Lock()

虽然第一句执行的时候条件满足，但是在加锁之前，m.dirty可能被提升为m.read，所以加锁后还得再检查一次m.read，后续的方法中都使用了这个方法。

由于已经走到了 dirty 的流程，因此开头就直接调用了Lock方法上互斥锁，保证数据安全，也是凸显性能变差的第一幕。

写入过程的整体流程是👇

1. 如果在 read 里能够找到待存储的 key，并且对应的 entry 的 p 值不为 expunged，也就是没被删除时，直接更新对应的 entry 即可。
2. 如果第一步没有成功，要么 read 中没有这个 key，要么 key 被标记为删除。则先加锁，再进行后续的操作。
3. 再次在 read 中查找是否存在这个 key，也就是 double check 双检查一下，这是 lock-free 编程的常见套路。如果 read 中存在该 key，但p == expunged，说明m.dirty != nil（m.dirty是被初始化过的）并且m.dirty中不存在该 key 值（因为已经被删除了，dirty 中的删除直接就删除了；read 中的删除，会先标记为 nil，read=>dirty重塑时再标记为expunged），此时👇
   1. 将 p 的状态由expunged更改为nil
   2. dirty map 插入 key。然后，直接更新对应的 value
4. 如果 read 中没有此 key，那就查看 dirty 中是否有此 key，如果有，则直接更新对应的 value，这时 read 中还是没有此 key。
5. 最后一步，如果 read 和 dirty 中都不存在该 key，则👇
   1. 如果dirty为空，则需要创建dirty，并从read中拷贝未被删除的元素
   2. 更新amended字段为 true，标识 dirty map 中存在 read map 中没有的key
   3. 将k-v写入 dirty map 中，read.m不变。最后，更新此 key 对应的value。

为什么 read 中存在 key，但是p == expunged时需要把 p 的状态由expunged更改为nil ❓

我理解的是 p 的 nil 是一个中间状态，其实是把 p 的状态从expunged->nil->新的entry

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

if e.unexpungeLocked() {
      // The entry was previously expunged, which implies that there is a
      // non-nil dirty map and this entry is not in it.
      m.dirty[key] = e
  }
  e.storeLocked(&value)

// storeLocked unconditionally stores a value to the entry.
//
// The entry must be known not to be expunged.
func (e *entry) storeLocked(i *interface{}) {
	atomic.StorePointer(&e.p, unsafe.Pointer(i))
}

Store 可能会在某种情况下（初始化或者m.dirty刚被提升后，此时m.read中的数据和m.dirty中的相等，readOnly 中的amended为false，也就是说可能存在一个 key，read 中找不到 dirty 中也找不到）从m.read中复制数据，如果这个时候m.read中数据量非常大，可能会影响性能。

综上可知，sync.Map 类型不适合写多的场景，读多写少是比较好的。若有大数据量的场景，则需要考虑 read 复制数据时的偶然性能抖动是否能够接受。

Load查找过程

sync.Map 类型本质上是有两个“map”。一个叫 read、一个叫 dirty，长的也差不多👇

当我们从 sync.Map 类型中读取数据时，其会先查看 read 中是否包含所需的元素：

• 若有，则通过 atomic 原子操作读取数据并返回。
• 若无，则会判断 read.readOnly 中的 amended 属性，他会告诉程序，dirty 是否包含read.readOnly.m中没有的数据；如果存在，也就是 amended 为 true，将会进 一步到 dirty 中查找数据。

 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

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
	// 1.首先从m.read中得到只读readOnly,从它的map中查找，不需要加锁
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	// 2. 如果没找到，并且m.dirty中有新数据，需要从m.dirty查找，这个时候需要加锁
	if !ok && read.amended {
		m.mu.Lock()
		// 双检查，避免加锁的时候m.dirty提升为m.read,这个时候m.read可能被替换了。
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		// 如果m.read中还是不存在，并且m.dirty中有新数据
		if !ok && read.amended {
			// 从m.dirty查找
			e, ok = m.dirty[key]
			// 不管m.dirty中存不存在，都将misses计数加一
			// missLocked()中满足条件后就会提升m.dirty
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if !ok {
		return nil, false
	}
	return e.load()
}

处理路径分为 fast path 和 slow path，整体流程如下：

1. 首先是 fast path，直接在 read 中找，如果找到了直接调用 entry 的 load 方法，取出其中的值。
2. 如果 read 中没有这个 key，且 amended 为 fase，说明 dirty 为空，那直接返回空和 false。
3. 如果 read 中没有这个 key，且 amended 为 true，说明 dirty 中可能存在我们要找的 key。当然要先上锁，再尝试去 dirty 中查找。在这之前，仍然有一个 double check 的操作。若还是没有在 read 中找到，那么就从 dirty 中找。不管 dirty 中有没有找到，都要“记一笔”，因为在 dirty 被提升为 read 之前，都会进入这条路径

那么m.dirty是如何被提升的❓，missLocked方法中可能会将m.dirty提升。

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 的值加 1。表示一次未命中，如果 misses 值小于m.dirty的长度，就直接返回。否则，将m.dirty晋升为 read，并清空 dirty，清空 misses 计数值，并且m.read.amended为false。这样，之前一段时间新加入的 key 都会进入到 read 中，从而能够提升 read 的命中率。

再来看下 entry 的 load 方法：

1
2
3
4
5
6
7

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

对于 nil 和 expunged 状态的 entry，直接返回ok=false；否则，将 p 转成interface{}返回。

sync.Map 的读操作性能如此之高的原因，就在于存在 read 这一巧妙的设计，其作为一个缓存层，提供了快路径fast path的查找。

Delete删除过程

写入过程，理论上和删除不会差太远。怎么 sync.Map 类型的删除的性能似乎还行，那这里面到底是如何实现的呢❓

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func (m *Map) Delete(key interface{}) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	// 如果 read 中没有这个 key，且 dirty map 不为空
	if !ok && read.amended {
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
			delete(m.dirty, key) // 直接从 dirty 中删除这个 key
		}
		m.mu.Unlock()
	}
	if ok {
		e.delete() // 如果在 read 中找到了这个 key，将 p 置为 nil
	}
}

可以看到，基本套路还是和 Load，Store 类似，都是先从 read 里查是否有这个 key，如果有则执行entry.delete方法，将 p 置为 nil，这样 read 和 dirty 都能看到这个变化，因为它们指向的是同一块内存地址。

如果没在 read 中找到这个 key，并且 dirty 不为空，那么就要操作 dirty 了，操作之前，还是要先上锁。然后进行 double check，如果仍然没有在 read 里找到此 key，则从 dirty 中删掉这个 key。但 不是真正地从 dirty 中删除，而是更新 entry 的状态。

以下是entry.delete方法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

它真正做的事情是将正常状态（指向一个 interface{}）的 p 设置成 nil。没有设置成 expunged 的原因是，当 p 为 expunged 时，表示它已经不在 dirty 中了。这是 p 的状态决定的，在tryExpungeLocked函数中，会将 nil 原子地设置成 expunged。

tryExpungeLocked是在新创建 dirty 时调用的，会将已被删除的entry.p从 nil 改成 expunged，这个 entry 就不会写入 dirty 了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func (e *entry) tryExpungeLocked() (isExpunged bool) {
	p := atomic.LoadPointer(&e.p)
	for p == nil {
		// 如果原来是 nil，说明原 key 已被删除，则将其转为 expunged。
		if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
			return true
		}
		p = atomic.LoadPointer(&e.p)
	}
	return p == expunged
}

注意到如果 key 同时存在于 read 和 dirty 中时，删除只是做了一个标记，将 p 置为 nil；而如果仅在 dirty 中含有这个 key 时，会直接删除这个 key。原因在于，若两者都存在这个 key，仅做标记删除，可以在下次查找这个 key 时，命中 read，提升效率。若只有在 dirty 中存在时，read 起不到“缓存”的作用，直接删除。

dirty和read互转，分别在什么样的时机下进行

• dirty=>read：随着 load 的 miss 不断自增，达到阈值（m.misses >= len(m.dirty)）后触发升级转储。
• read=>dirty：当有 read 中不存在的新 key 需要增加，且 read 和 dirty 一致的时候，触发重塑，且read.amended置为 true，然后再在 dirty 新增。重塑的过程，会将 nil 状态的 entry，全部挤压到 expunged 状态中，同时将非 expunged 的 entry 浅拷贝到 dirty 中，这样可以避免 read 的 key 无限的膨胀（存在大量逻辑删除的 key）。最终，在 dirty 再次升级为 read 的时候，这些逻辑删除的 key 就可以一次性丢弃释放（因为是直接覆盖上去）。

1
2
3
4
5
6

if !read.amended {
   // We're adding the first new key to the dirty map.
   // Make sure it is allocated and mark the read-only map as incomplete.
   m.dirtyLocked()
   m.read.Store(readOnly{m: read.m, amended: true})
}

read从何而来，存在的意义是什么

• read 是由 dirty 升级而来，是利用了atomic.Store一次性覆盖，而不是一点点的 set 操作出来的。所以，read 更像是一个快照，read 中 key 的集合不能被改变（注意，这里说的 read 的 key 不可改变，不代表指定的 key 的 value 不可改变，value 是可以通过原子CAS来进行更改的），所以其中的键的集合有时候可能是不全的。
• 脏字典中的键值对集合总是完全的，但是其中不会包含 expunged 的键值对。
• read 的存在价值，在于加速读性能（通过原子操作避免了锁）。

dirty什么时候是nil

dirty 数据提升为 read 时m.dirty会置为 nil。此时，m.read和·m.dirty·相等，m.amended为 false，也就是说，read 中找不到的数据，dirty 中同样找不到。

1

amended bool // true if the dirty map contains some key not in m.

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
}

entry的p可能的状态有哪些

• e.p==nil：entry 已经被标记删除，不过此时还未经过read=>dirty重塑，此时可能仍然属于 dirty（如果 dirty 非 nil）。
• e.p==expunged：entry 已经被标记删除，经过read=>dirty重塑，不属于 dirty，仅仅属于 read，下一次dirty=>read升级，会被彻底清理（因为升级的操作是直接覆盖，read 中的 expunged 会被自动释放回收）
• e.p==普通指针：此时 entry 是一个普通的存在状态，属于 read，如果 dirty 非 nil，也属于 dirty。

删除时e.p是设置成了nil还是expunged

• 如果 key 不在 read 中，但是在 dirty 中，则直接 delete。
• 如果 key 在 read 中，则逻辑删除，e.p赋值为 nil，后续在read=>dirty重塑的时候，nil 会变成 expunged。

什么时候e.p由nil变成expunged

• read=>dirty重塑的时候，此时 read 中仍然是 nil 的会变成 expunged，表示这部分 key 等待被最终丢弃（expunged 是最终态，等待被丢弃，除非又出现了重新 store 的情况）
• 最终丢弃的时机就是dirty=>read升级的时候，dirty 的直接粗暴覆盖，会使得 read 中的所有成员都被丢弃，包括 expunged。

既然nil也表示标记删除，再设计出一个expunged的意义是什么

expunged 是有存在意义的，它作为删除的最终状态 （待释放），这样 nil 就可以作为一种中间状态。如果仅仅使用 nil，那么，在read=>dirty重塑的时候，可能会出现如下的情况👇

• 如果 nil 在 read 浅拷贝至 dirty 的时候仍然保留 entry 的指针（即拷贝完成后，对应键值下 read 和 dirty 中都有对应键下 entry e 的指针，且e.p=nil）那么之后在dirty=>read升级 key 的时候对应 entry 的指针仍然会保留。那么最终的合集会越来越大，存在大量 nil 的状态，永远无法得到清理的机会。
• 如果 nil 在 read 浅拷贝时不进入 dirty，那么之后 Store 某个 key 键的时候，可能会出现 read 和 dirty 不同步的情况，即此时 read 中包含 dirty 不包含的键，那么之后用 dirty 替换 read 的时候就会出现数据丢失的问题。
• 如果 nil 在 read 浅拷贝时直接把 read 中对应键删除（从而避免了不同步的问题），但这又必须对 read 加锁，违背了 read 读写不加锁的初衷。

综上，为了保证 read 作为快照的性质（不能单独删除或新增key），同时要避免 Map 中 nil 的 key 不断膨胀等多个前提要求，才设计成了 expunged 的状态。

参考

• 不得不知道的Golang之sync.Map解读！
• 一口气搞懂 Go sync.map 所有知识点
• Go 1.9 sync.Map揭秘
• 深度解密 Go 语言之 sync.map