Go sync.Map探究

在Go中, 有这样一个数据结构sync.Map, 他的出现是为了提供一个并发安全的map.

Map

在了解sync.Map之前, 我们有必要知道为什么map不是并发安全的, 这里一笔带过了.

map这个数据结构在各个语言中都有实现, 基本上大同小异, 大部分都是通过数组+链表来实现的, 在Go中也不例外. 结构大体上就是:

1. 使用数组存储
2. 当发生hash冲突时, 通过链表解决
3. 当内容过大时, 进行数组扩容

这里对map的具体实现不进行过多介绍, 只思考一下为什么map不是并发安全的. 其实现源码定义在文件runtime/map.go中. 感兴趣 的可以研究一下.

对于map的操作无非两种读/写. 如果只是单纯的读, 是不会有并发问题的. 而在数据发生更新时, 可能正在进行扩容, 可能正在修改链表等等. 其中每一个操作都不是原子性的, 在每一个操作中, 都可能会发生新的读写. 而此时, 内存中的数据可能是残缺的, 甚至于丢失数据. (比如两个写操作都向同一个链表末尾追加元素, 其中一个可能就丢了)

这时候如果考虑并发竞争的情况, 必然会导致执行效率的降低(因为要加锁处理). 因此, 官方的实现比较简单, 在读/写时, 若发现已经在更新了, 则报错. 报错文案如下(也定义在map.go文件中, 感兴趣的可以看一下):

// 当更新与更新冲突时
concurrent map writes
// 当读取与更新冲突时
concurrent map read and map write
1
2
3
4

其实不光是Go, 大部分语言的map都不是并发安全的, 比如Java中的HashMap.

sync.Map

如果我们来实现一个并发安全的map, 我们可以怎么做呢? 很简单, 加读写锁. 当map发生更新的时候, 所有读写操作都等待. 当map读取的时候, 写操作等待, 但并发读是没有问题的.

而sync.Map则是官方为我们提供的一个并发安全的map实现. 一起来看看官方是如何处理map的并发操作的. 结构体定义如下(以下源码分析基于版本go1.18):

type Map struct {
	// 互斥锁
	mu Mutex
	// 这是一个只读的 map. 其值为 readOnly 结构体(在下面)
	read atomic.Value // readOnly
	// 脏数据. 这个 map 用于数据更新
	dirty map[any]*entry
	// 记录在 read 中读取数据失败的次数
	misses int
}
// 内存中的只读 map
type readOnly struct {
	m       map[any]*entry
	// Map.dirty 的数据和这里的数据不一样的时候，为true
	amended bool
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

可以看到, 其内部也是通过添加互斥锁实现的. 与我们不同的是, 其内部维护了两个map, 其中一个是只读的map. 通过其结构体, 我们可以大致猜测出其实现思路, 一句话概括就是: 将map拆分出一个read只用作读取. 数据更新的时候操作dirty, 这样在读取数据时无需加锁, 提高并发性能.

读取

我们先来看一下是如何从中读取数据的:

func (m *Map) Load(key any) (value any, ok bool) {
	// 从 read 中读取数据
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	// 若 read 中没有读到, 且 read 与 dirty 不一致, 则从 dirty 中读取
	if !ok && read.amended {
		m.mu.Lock()
		// 这里从 read 中再读一次, 双重检查. 
		// 因为上面的 读取 与 if 判断没有加锁, 在这期间可能数据已经添加过来了	
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		// 同上, 从 dirty 中读取
		if !ok && read.amended {
			e, ok = m.dirty[key]
			// 记录 dirty 与 read 数据不一致, 触发数据同步
			// 因为这个 key 会导致加锁操作, 所以不管数据在不在都进行记录
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if !ok {
		return nil, false
	}
	return e.load()
}

// read 中数据 miss
// 这个操作全程被锁保护着
func (m *Map) missLocked() {
	m.misses++
	// 当 miss 次数大于 map 中元素数量时, 触发数据同步
	if m.misses < len(m.dirty) {
		return
	}
	// 将 dirty 数据同步给 read
  // 这里是原子操作
	m.read.Store(readOnly{m: m.dirty})
  // 清空 dirty, 为了减少空间占用
	m.dirty = nil
	m.misses = 0
}
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

从这个读取操作中, 我们可以看到读取数据的步骤是:

1. 从read中读取
2. 若read中没有, 且与dirty存在差异, 则加锁从dirty中读取

read内容的更新也仅仅在read中, 且更新全程被锁保护.

如此, 我们能够想到的是, 添加数据的时候加锁并修改dirty同时将read.amended置为TRUE. 但是更新和删除操作如何同步给read呢?

删除

当从map中删除数据的时候, 如何通知read呢?

func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
	// 以下部分做的一件事就是, 从 read/dirty 中将数据读出来
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	if !ok && read.amended {
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
      // 将数据从 dirty 中删除
			delete(m.dirty, key)
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if ok {
		// 若数据存在, 调用其 delete 方法, 在下面
		return e.delete()
	}
	return nil, false
}

// 删除元素
// 其操作是, 通过原子操作将数据置为 nil
// 对应与读取时的 load 函数, 也会进行 nil 的判断
func (e *entry) delete() (value any, ok bool) {
	for {
		p := atomic.LoadPointer(&e.p)
		if p == nil || p == expunged {
			return nil, false
		}
		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
			return *(*any)(p), true
		}
	}
}
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

可以看到, 数据删除的时候, 其实map中的元素仍然在, 只是将其p字段置为nil. 这也是为了保证read的读取性能, 减少read的加锁范围及加锁时间, 所以不对read进行修改, 而仅仅是修改元素.

有没有发现, 删除操作是没有加锁的(当数据在read中存在时). 为什么嘞? 因为删除操作没有修改map, 而是仅仅修改元素. 是不是很妙?

添加

这里操作就不将所有源码都列出来了, 只列出一些主要步骤, 感兴趣的可自行查看.

添加和更新时同一个函数:

func (m *Map) Store(key, value any) {
	// 若数据在 read 中存在, 则尝试更新 read, 直接将指针指向新的地址
	// tryStore 中是一个自旋锁
	read, _ := m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok && e.tryStore(&value) {
		return
	}

	// 全程加锁
	m.mu.Lock()
	// 这里从 read 中再读一次, 原因相同. 因为上面的读取操作没有加锁
	read, _ = m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok {
		// 若元素已经在 read 中被删除了, 则说明 dirty 中不存在此 key
		// 原因可看上面的删除操作, 数据在删除时会将 dirty 中对应 key 删除
		if e.unexpungeLocked() {
			m.dirty[key] = e
		}
		// 将值指向新的地址
		e.storeLocked(&value)
	} else if e, ok := m.dirty[key]; ok {
		// 若在 read 中没有, 但在 dirty 中存在, 则直接修改
		e.storeLocked(&value)
	} else { // 若 read/dirty 中均没有
		// 若当前 read dirty 相同
		if !read.amended {
			// dirty 数据初始化
			// 因为在 missLocked 同步数据时, 将 dirty 置为 nil 了
			// 所以这里需要对其初始化
      // 初始化操作就是, 将 read 中的所有内容赋值给 dirty
			m.dirtyLocked()
			// 将 amended 标记为 true
			m.read.Store(readOnly{m: read.m, amended: true})
		}
		// 记录新数据
		m.dirty[key] = newEntry(value)
	}
	m.mu.Unlock()
}
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

在添加的时候, 若数据存在则更新, 不存在则新建. 那么更新操作是如何同步给read的呢? 因为其全程使用指针存储, 不管数据从read中还是dirty中读到, 修改指针后, 双方同步修改.

总结

看了sync.Map的源码后, 确实要比我自己想的实现高明许多, 其主要设计有这么几个点:

1. 将map单独拆分一个只读read, 这样读操作不需要加锁
2. 数据更新全程使用指针, 既map本身没有修改, 而是修改元素. 因此也不需要加锁
3. 数据删除将元素中的指针变量置为nil, 元素本身仍然存在. map也没有修改, 不需要加锁
4. 等等吧…

可以看到, 通过只读map, 可以满足大量的并发读取. 但是, 当写多读少的时候, 因为其写操作进行了一些额外的处理, 所以性能并没有比map+metux更好. 而且sync.Map在写时, 可能会触发read map的全量复制, 会降低效率.

可以看到sync.Map的整体思路是读写分离, 在读多写少的情况性能较好. 但是在写多读少的情况下, 性能并没有比普通加锁实现更好.

那么最初的map+metux的方式, 如何能够提高性能呢? 有了, 如果我们将1个map拆分为 n 个map, 这样每次操作的时候, 加锁的范围就变小了, 并发性能不就自然提高了么? 别说, 还真有人这么干了, 地址放这了, 有时间翻翻源码看看. https://github.com/orcaman/concurrent-map

原文地址: https://hujingnb.com/archives/849