sync.Map分析(1.20)

sync.Map

sync.Map是Go语言标准库中提供的并发安全的映射（Map）类型。它在多个Goroutine之间提供了安全的并发访问和修改映射的能力，适用于高并发的场景。

sync.Map的一些特点

  • 并发安全：sync.Map内部使用细粒度的锁机制
  • 无需显式锁：与传统互斥锁不同，sync.Map不需要每次在读写操作时显式加锁和解锁
  • 动态增长：sync.Map的容量会按需要动态增长
  • 值类型限制：sync.Map键和值可以是任意类型，但是键的类型必须的课比较的（comparale）。因为内部查找和操作元素需要键的比较。否则会panic: panic: runtime error: hash of unhashable type map[int]string
  • 基本操作：sync.Map提供了一些基本的操作方法，如Store、Load、LoadOrStore、Delete和Range等。
    • Store(key, value)：存储键值对到映射中。
    • Load(key)：加载指定键对应的值。
    • LoadOrStore(key, value)：加载指定键对应的值，如果键不存在则存储给定的键值对。
    • Delete(key)：删除指定键值对。
    • Range(func(key, value interface{}) bool)：遍历映射并对每个键值对执行指定的函数。
  • 无序：sync.Map的方法Range在遍历时是无序的

使用示例：

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
package main

import (
	"fmt"
	"sync"
)

func main() {
	var m sync.Map

	// 存储键值对
	m.Store("key1", "value1")
	m.Store("key2", "value2")

	// 加载值
	value1, ok := m.Load("key1")
	if ok {
		fmt.Println("Value1:", value1)
	}

	// 加载或存储值
	value3, loaded := m.LoadOrStore("key3", "value3")
	if loaded {
		fmt.Println("Loaded Value3:", value3)
	} else {
		fmt.Println("Stored Value3:", value3)
	}

	// 删除键值对
	m.Delete("key2")

	// 遍历映射
	m.Range(func(key, value interface{}) bool {
		fmt.Println("Key:", key, "Value:", value)
		return true
	})
}

深入了解(1.20版本)

sync.Map的数据结构

1
2
3
4
5
6
7
8
9
10
type Map struct {
    /// 该锁⽤来保护dirty
	mu Mutex
	// 存读的数据，因为是atomic.value类型，只读类型，所以它的读是并发安全的
	read atomic.Pointer[readOnly]
	//包含最新的写⼊的数据，并且在写的时候，会把read 中未被删除的数据拷⻉到该dirty中，因为是普通的map存在并发安全问题，需要⽤到上⾯的mu字段。
	dirty map[any]*entry
	// 从read读数据未命中的时候，会将该字段+1，当等于len（dirty）的时候，会将dirty拷⻉到read中（从⽽提升读的性能）。
	misses int
}

readOnly的数据结构

1
2
3
4
5
6
type readOnly struct {
	m       map[any]*entry
    // 修正字段，如果Map.dirty的数据和m中的数据不⼀样是为true
	amended bool 
}

entry的数据结构

1
2
3
4
type entry struct {
    //可⻅value是个指针类型，虽然read和dirty存在冗余情况（amended=false），但是由于是指针类型，存储的空间应该不是问题
	p atomic.Pointer[any]
}

细节：nil和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
nil的状态来源为read中删除元素，万能指针p被标记删除为nil
	- 在store中，如果key被标记为nil，那么可以重新赋值使用，可以绕过dirty赋值和misses字段更新
	- 如果被标记为expunged，那么只能在dirty中新增数据，然后更新misses

expunged：在store时，read和dirty都不存在该key，就必须在dirty新增数据，将数据返回。
	在dirty新增数据过程中，会重新将read的数据放入dirty（标记为nil的p则会被标记为expunged，标记为expunged则不放入dirty，那么被标记为expunged的字段，会就在delete方法中被直接删除）

万能指针 ：删除-> nil -> expunged ->被删除（调用delete)，这是一个数据被删除的其中过程。
而nil的状态，可以让Store方法减少dirty更新流程，达到复用key的作用。（直接使用使用一种状态的话，那就只有删除和未删除的状态，必须涉及map增减）



func (e *entry) trySwap(i *any) (*any, bool) {
	for {
		p := e.p.Load()
        // 在store方法中会调用，如果p为nil，那么可以重新使用
		if p == expunged {
			return nil, false
		}
		if e.p.CompareAndSwap(p, i) {
			return p, true
		}
	}
}

Delete方法

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
/*
删除时
- 当read中存在，就将p标记删除为nil
	- 在store方法中，如果read中标记为nil的p还没有被标记expunge，就可以直接使用更新p，而不用重新在dirty中增加值（很细节)
	- 在store方法中，如果read中标记为nil的p已经被标记expunge，那就要在dirty中增加值
- 当read中不存在，dirty中存在，直接删除dirty中的数据
*/

func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
	read := m.loadReadOnly()
	e, ok := read.m[key]
    // 如果read中没有，而且amended为true，read和dirty数据不同步，就从dirty中找
	if !ok && read.amended {
		m.mu.Lock()
        // 这是双检查（因为上面的if判断和锁不是原子操作，并发状态下可能会改变）
		read = m.loadReadOnly()
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
			delete(m.dirty, key)
			// read中为命中数据，更新misses字段
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if ok {
        // read中存在该key，标记删除
		return e.delete()
	}
    // read和dirty都不存在该key
	return nil, false
}

func (e *entry) delete() (value any, ok bool) {
	for {
		p := e.p.Load()
        // key不存在或者该key已被擦除
		if p == nil || p == expunged {
			return nil, false
		}
        // 原子性将该key标记为nil(标记删除)
		if e.p.CompareAndSwap(p, nil) {
			return *p, true
		}
	}
}

Store方法

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
// swap将值与键进行交换并返回以前的值（如果有的话）。 
// 加载的结果报告键是否存在。
func (m *Map) Swap(key, value any) (previous any, loaded bool) {
	read := m.loadReadOnly()
    // read中存在该key，尝试更新，trySwap中（如果没有被标记删除，则尝试更新）
	if e, ok := read.m[key]; ok {
		if v, ok := e.trySwap(&value); ok {
			if v == nil {
				return nil, false
			}
			return *v, true
		}
	}
	// read中不存在或者该key已经被擦除
	m.mu.Lock()
	read = m.loadReadOnly()
    // 这是双检查，由于read没有并发控制
	if e, ok := read.m[key]; ok {
        // 如果read中存在该key，且没有被标记expunge，那么将该key更新到dirty中
		if e.unexpungeLocked() {
			m.dirty[key] = e
		}
        // 更新value值
		if v := e.swapLocked(&value); v != nil {
			loaded = true
			previous = *v
		}
        // read中不存在该key，且dirty中存在该key，则更新dirty
	} else if e, ok := m.dirty[key]; ok {
		if v := e.swapLocked(&value); v != nil {
			loaded = true
			previous = *v
		}
	} else {
        // read和dirty不一致了，更新amended值
		if !read.amended {
            //将read中未删除的数据加⼊到dirty中
			m.dirtyLocked()
			m.read.Store(&readOnly{m: read.m, amended: true})
		}
        // dirty不存在该key，往dirty中添加新键
		m.dirty[key] = newEntry(value)
	}
	m.mu.Unlock()
	return previous, loaded
}

//如果条目没有被删除，则trySwap交换一个值。
//如果条目被删除，trysswap返回false并离开条目不变。
func (e *entry) trySwap(i *any) (*any, bool) {
	for {
		p := e.p.Load()
        // 判断该key是否被擦除
		if p == expunged {
			return nil, false
		}
        // 原子交换
		if e.p.CompareAndSwap(p, i) {
			return p, true
		}
	}
}

// 将read中未删除的数据加⼊到dirty中
func (m *Map) dirtyLocked() {
	if m.dirty != nil {
		return
	}
	read := m.loadReadOnly()
	m.dirty = make(map[any]*entry, len(read.m))
    // 这里read如果比较大，可能影响性能
	for k, e := range read.m {
        // 被expunge的元素不会加入dirty中
		if !e.tryExpungeLocked() {
			m.dirty[k] = e
		}
	}
}


//判断entry是否被标记删除，并且将标记为nil的entry更新标记为expunge
func (e *entry) tryExpungeLocked() (isExpunged bool) {
	p := e.p.Load()
	for p == nil {
        // 将已经删除标记为nil的数据标记为expunged
		if e.p.CompareAndSwap(nil, expunged) {
			return true
		}
		p = e.p.Load()
	}
	return p == expunged
}


Load方法

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
func (m *Map) Load(key any) (value any, ok bool) {
    //因read只读，线程安全，先查看是否满⾜条件
	read := m.loadReadOnly()
	e, ok := read.m[key]
    //如果read没有，并且dirty有新数据，那从dirty中查找，由于dirty是普通map，线程不安全，这个时候⽤到互斥锁了
	if !ok && read.amended {
		m.mu.Lock()
        // 双重检查
		read = m.loadReadOnly()
		e, ok = read.m[key]
        // 如果read中还是不存在，并且dirty中有新数据
		if !ok && read.amended {
			e, ok = m.dirty[key]
			/// mssLocked（）函数是性能是sync.Map 性能得以保证的重要函数，⽬的讲有锁的dirty数据，替换到只读线程安全的read⾥
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if !ok {
		return nil, false
	}
	return e.load()
}

//dirty 提升⾄read 关键函数，当misses 经过多次因为load之后，⼤⼩等于len（dirty）时候，讲dirty替换到read⾥，以此达到性能提升。
// Store 和 Delete未命中，都会调用
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
}

Delete方法

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) LoadAndDelete(key any) (value any, loaded bool) {
	read := m.loadReadOnly()
	e, ok := read.m[key]
    //如果read中没有，并且dirty中有新元素，那么就去dirty中去找
	if !ok && read.amended {
		m.mu.Lock()
        //这是双检查（上⾯的if判断和锁不是⼀个原⼦性操作）
		read = m.loadReadOnly()
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
            //直接删除
			delete(m.dirty, key)
			// 更新未命中次数
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if ok {
		return e.delete()
	}
	return nil, false
}

sync.Map是通过冗余的两个数据结构(read、dirty),实现性能的提升。为了提升性能，load、delete、store等操作 尽量使⽤只读的read；为了提⾼read的key击中概率，采⽤动态调整，将dirty数据提升为read；对于数据的删除， 采⽤延迟标记删除法，只有在提升dirty的时候才删除。