Golang sync.Map原理分析

Golang sync.Map原理分析

GO语言内置的map

go语言内置一个map数据结构，使用起来非常方便，但是它仅支持并发的读，不支持并发的写，比如下面的代码：

在main函数中开启两个协程同时对m进行并发读和并发写，程序运行之后会报错：

package main

func main()  {
	m := make(map[int]int)

	go func()  {
		for {
			_ = m[1]
		}
	}()

	go func()  {
		for {
			m[2] = 2
		}
	}()

	select {}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

改进

既然不可以并发的写，我们可以给map加一个读写锁，这样就不会有并发写冲突的问题了：

import "sync"

func main() {
	m := make(map[int]int)
	var lock sync.RWMutex

	go func() {
		for {
			lock.RLock()
			_ = m[1]
			lock.RUnlock()
		}
	}()

	go func() {
		for {
			lock.Lock()
			m[2] = 2
			lock.Unlock()
		}
	}()

	select {}
}

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

这种方式的实现非常简洁，但也存在一些问题，比如在map的数据非常大的情况下，一把锁会导致大并发的客户端共争一把锁。

sync.Map

sync.Map是官方在sync包中提供的一种并发map，使用起来非常简单，和普通map相比，只有遍历的方式有区别：

package main

import (
	"fmt"
	"sync"
)

func main() {
	var m sync.Map
	// 1. 写入
	m.Store("apple", 1)
	m.Store("banana", 2)

	// 2. 读取
	price, _ := m.Load("apple")
	fmt.Println(price.(int))

	// 3. 遍历
	m.Range(func(key, value interface{}) bool {
		fruit := key.(string)
		price := value.(int)
		fmt.Println(fruit, price)
		return true
	})

	// 4. 删除
	m.Delete("apple")

	// 5. 读取或写入
	m.LoadOrStore("peach", 3)
}
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

sync.Map是通过 read 和 dirty 两个字段将读写分离，读的数据存在只读字段 read 上，将最新写入的数据则存在 dirty 字段上。
读取时会先查询 read，不存在再查询 dirty，写入时则只写入 dirty。
读取 read 并不需要加锁，而读或写 dirty 都需要加锁，另外有 misses 字段来统计 read 被穿透的次数（被穿透指需要读 dirty 的情况），超过一定次数则将 dirty 数据同步到 read 上，对于删除数据则直接通过标记来延迟删除。

在map + 锁的基础上，它有着几个优化点：

1. 空间换时间。 通过冗余的两个数据结构(read、dirty)，实现加锁对性能的影响。
2. 使用只读数据(read)，避免读写冲突。
3. 动态调整，miss次数多了之后，将dirty数据提升为read。
4. double-checking。
5. 延迟删除。 删除一个键值只是打标记，只有在提升dirty的时候才清理删除的数据。
6. 优先从read读取、更新、删除，因为对read的读取不需要锁。

sync.Map原理分析

sync.Map的结构

sync.Map的实现在src/sync/map.go中，首先来看Map结构体：

type Map struct {
    // 当涉及到脏数据(dirty)操作时候，需要使用这个锁
    mu Mutex
    
    // read是一个只读数据结构，包含一个map结构，
    // 读不需要加锁，只需要通过 atomic 加载最新的指正即可
    read atomic.Value // readOnly
    
    // dirty 包含部分map的键值对，如果操作需要mutex获取锁
    // 最后dirty中的元素会被全部提升到read里的map去
    dirty map[interface{}]*entry
    
    // misses是一个计数器，用于记录read中没有的数据而在dirty中有的数据的数量。
    // 也就是说如果read不包含这个数据，会从dirty中读取，并misses+1
    // 当misses的数量等于dirty的长度，就会将dirty中的数据迁移到read中
    misses int
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

上述结构体中的read字段实际上是一个包含map的结构体，该结构体中的map是一个read map，对该map的访问不需要加锁，但是增加的元素不会被添加到这个map中，元素会被先增加到dirty中，后续才会被迁移到read只读map中。
readOnly结构体中还有一个amended字段，该字段是一个标志位，用来表示read map中的数据是否完整。假设当前要查找一个key，会先去read map中找，如果没有找到，会判断amended是否为true，如果为true，说明read map的数据不完整，需要去dirty map中找。

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
    // m包含所有只读数据，不会进行任何的数据增加和删除操作 
    // 但是可以修改entry的指针因为这个不会导致map的元素移动
    m       map[interface{}]*entry
    
    // 标志位，如果为true则表明当前read只读map的数据不完整，dirty map中包含部分数据
    amended bool // true if the dirty map contains some key not in m.
}
1
2
3
4
5
6
7
8
9

entry

readOnly.m和Map.dirty存储的值类型是*entry,它包含一个指针p, 指向用户存储的value值，结构如下：

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

其中p对应着三种值：

• p == nil: 键值已经被删除，且 m.dirty == nil，这个时候dirty在等待read的同步数据。
• p == expunged: 键值已经被删除，但 m.dirty!=nil 且 m.dirty 不存在该键值（dirty已经得到了read的数据同步，原来为nil的值已经被标记为了expunged没有被同步过来）。
• 除以上情况，则键值对存在，存在于 m.read.m 中，如果 m.dirty!=nil 则也存在于 m.dirty

下面是sync.Map的结构示意图：

查找

查找元素会调用Load函数，该函数的执行流程：

1. 首先去read map中找值，不用加锁，找到了直接返回结果。
2. 如果没有找到就判断read.amended字段是否为true，true说明dirty中有新数据，应该去dirty中查找，开始加锁。
3. 加完锁以后又去read map中查找，因为在加锁的过程中，m.dirty可能被提升为m.read。
4. 如果二次检查没有找到key，就去m.dirty中寻找，然后将misses计数加一。

// src/sync/map.go

// Load returns the value stored in the map for a key, or nil if no
// value is present.
// The ok result indicates whether value was found in the map.
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 首先从只读ready的map中查找，这时不需要加锁
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    
    // 如果没有找到，并且read.amended为true，说明dirty中有新数据，从dirty中查找，开始加锁了
    if !ok && read.amended {
        m.mu.Lock() // 加锁
        
       // 又在 readonly 中检查一遍，因为在加锁的时候 dirty 的数据可能已经迁移到了read中
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        
        // read 还没有找到，并且dirty中有数据
        if !ok && read.amended {
            e, ok = m.dirty[key] //从 dirty 中查找数据
            
            // 不管m.dirty中存不存在，都将misses + 1
            // missLocked() 中满足条件后就会把m.dirty中数据迁移到m.read中
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.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

misses计数

misses计数是有上限的，如果misses次数达到m.dirty的长度，就开始迁移数据，程序会直接将m.dirty提升为m.read，然后将m.dirty置为nil，等到下次插入新数据的时候，程序才会把read map中的值全部复制给dirty map。

// src/sync/map.go

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {//misses次数小于 dirty的长度，就不迁移数据，直接返回
        return
    }
    m.read.Store(readOnly{m: m.dirty}) //开始迁移数据
    m.dirty = nil   //迁移完dirty就赋值为nil
    m.misses = 0  //迁移完 misses归0
}
1
2
3
4
5
6
7
8
9
10
11

新增和更新

新增或者更新元素会调用Store函数，该函数的前面几个步骤与Load函数是一样的：

1. 首先去read map中找值，不用加锁，找到了直接调用tryStore()函数更新值即可。
2. 如果没有找到就开始对dirty map加锁，加完锁之后再次去read map中找值，如果存在就判断该key对应的entry有没有被标记为unexpunge，如果没有被标记，就直接调用storeLocked()函数更新值即可。
3. 如果在read map中进行二次检查还是没有找到key，就去dirty map中找，找到了直接调用storeLocked()函数更新值。
4. 如果dirty map中也没有这个key，说明是新加入的key，首先要将read.amended标记为true，然后将read map中未删除的值复制到dirty中，最后向dirty map中加入这个值。

// src/sync/map.go

// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
   // 直接在read中查找值，找到了，就尝试 tryStore() 更新值
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }
    
    // m.read 中不存在
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        if e.unexpungeLocked() { // 未被标记成删除，前面讲到entry数据结构时，里面的p值有3种。1.nil 2.expunged，这个值含义有点复杂，可以看看前面entry数据结构 3.正常值
            
            m.dirty[key] = e // 加入到dirty里
        }
        e.storeLocked(&value) // 更新值
    } else if e, ok := m.dirty[key]; ok { // 存在于 dirty 中，直接更新
        e.storeLocked(&value)
    } else { // 新的值
        if !read.amended { // m.dirty 中没有新数据，增加到 m.dirty 中
            // 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中复制未删除的数据
            m.read.Store(readOnly{m: read.m, amended: true}) 
        }
        m.dirty[key] = newEntry(value) //将这个entry加入到m.dirty中
    }
    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

在Store函数中我们用到了两个用于更新值的函数：tryStore以及storeLocked，tryStore函数是先判断p有没有被标记为expunged（软删除），如果被标记了就直接返回false，如果没有被标记，就将p指向的值进行更新然后返回true。
storeLocked函数是直接将p指向的值进行更新。

// 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
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 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))
}
1
2
3
4
5
6

将read map中的值复制到dirty map中：

m.dirtyLocked()函数用于将read map中的值复制到dirty map中：

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 {
		// 判断值是否被删除，被标记为expunged的值不会被复制到read map中
		if !e.tryExpungeLocked() {
			m.dirty[k] = e
		}
	}
}

// expunged实际上是一个指向空接口的unsafe指针
var expunged = unsafe.Pointer(new(interface{}))

func (e *entry) tryExpungeLocked() (isExpunged bool) {
	p := atomic.LoadPointer(&e.p)
	// 如果p为nil，就会被标记为expunged
	for p == nil {
		if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
			return true
		}
		p = atomic.LoadPointer(&e.p)
	}
	return p == 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

下面是对sync.Map进行读写操作的示意图，正常读写且read map中有数据，程序只会访问read map，而不会去加锁：

删除

删除会调用Delete函数，该函数的步骤如下：

1. 首先去read map中找key，找到了就调用e.delete()函数删除。
2. 如果在read map中没有找到值就开始对dirty map加锁，加锁完毕之后再次去read map中查找，找到了就调用e.delete()函数删除。
3. 如果二次检查都没有找到key（说明这个key是被追加之后，还没有提升到read map中就要被删除），就去dirty map中删除这个key。

// src/sync/map.go

// Delete deletes the value for a key.
func (m *Map) Delete(key interface{}) {
    // 从 m.read 中开始查找
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    
    if !ok && read.amended { // m.read中没有找到，并且可能存在于m.dirty中，加锁查找
        m.mu.Lock() // 加锁
        read, _ = m.read.Load().(readOnly) // 再在m.read中查找一次
        e, ok = read.m[key]
        if !ok && read.amended { //m.read中又没找到，amended标志位true，说明在m.dirty中
            delete(m.dirty, key) // 删除
        }
        m.mu.Unlock()
    }
    if ok { // 在 m.read 中就直接删除
        e.delete()
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

func (e *entry) delete() (hadValue bool) {
	for {
		p := atomic.LoadPointer(&e.p)
		// 已标记为删除
		if p == nil || p == expunged {
			return false
		}
		// 原子操作，e.p标记为nil，GO的GC会将对象自动删除
		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
			return true
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

key究竟什么时候会被删除

我们可以发现，如果read map中存在待删除的key时，程序并不会去直接删除这个key，而是将这个key对应的p指针指向nil。
在下一次read -> dirty的同步时，指向nil的p指针会被标记为expunged，程序不会将被标记为expunged的 key 同步过去。
等到再一次dirty -> read同步的时候，read会被dirty直接覆盖，这个时候被标记为expunged的key才真正被删除了，这就是sync.Map的延迟删除。