特别提醒，本文所涉及的源码是go1.21.0 darwin/amd64
文件位置：runtime/map.go

普通的map并不是并发安全的一个数据结构，因此想要使用并发安全的map，sync包下提供了一个sync.map数据结构

1 数据结构

1
2
3
4
5
6
7
type Map struct {
    // 保护并发读写、写写
    mu Mutex
    read atomic.Pointer[readOnly]
    dirty map[any]*entry
    misses int
}
  • read：无锁化的map，实际类型为atomic.Pointer
  • dirty：加锁的map，是一个普通的map
  • misses：每次从read中读取失败，misses都会加1，达到一定阈值后，会将dirty提升为read
1
2
3
4
type readOnly struct {
    m       map[any]*entry
    amended bool 
}
  • m：read中的map，存放k-v对
  • amended：标识read和dirty中的元素是否一致
1
2
3
type entry struct {
    p atomic.Pointer[any]
}
  • p：k-v对中的value，使用atomic.Pointer的形式，通过entry.p的指针来获取值

2 entry的几种状态

2.1 p==nil（软删除）

此时p是nil，m.dirty等于nil或者m.dirty[key]指向该entry

2.2 p==expunged（硬删除）

1
2
// 固定的全局变量，标识该entry已经从m.dirty中删除
var expunged = new(any)

2.3 p指向正常值的地址

这种情况就是k-v对没删除的情况，可以通过m.read.m[key]找到，如果此时dirty也不为nil，同样也可以通过m.dirty[key]找到，两者实际指向的是同一个值。

image-20230913154004629

3 Load

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) Load(key any) (value any, ok bool) {
    read := m.loadReadOnly()
    e, ok := read.m[key]
    // read中没找到，则判断amended是否为true
    if !ok && read.amended {
        m.mu.Lock()
        read = m.loadReadOnly()
        // double check，有可能在上锁的过程中，其中goroutine将dirty提升为read了
        e, ok = read.m[key]
        // 还是没有在read中找到对应key的value
        if !ok && read.amended {
            e, ok = m.dirty[key]
            // misses++，如果超过阈值则将dirty提升为read
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load()
}

首先会调用loadReadOnly函数获取read

1
2
3
4
5
6
7
func (m *Map) loadReadOnly() readOnly {
    // 因为read是atomic包下的类型，因此需要使用load函数获取
    if p := m.read.Load(); p != nil {
        return *p
    }
    return readOnly{}
}

如果未初始化，则在该函数中初始化，否则直接返回m.read

通过key来读取read.m中的value，然后存在该元素则直接返回值就行，否则要上锁，再判断m中是否存在该key，如果还是不存在则去dirty中查找。

1
2
3
4
5
6
7
8
9
10
func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {
        return
    }
    // misses超过dirty的长度，则将dirty提升为read，并将dirty置为nil
    m.read.Store(&readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

如果在read和dirty都没找到，则返回nil，如果找到了则调用load返回对应的值

1
2
3
4
5
6
7
8
9
func (e *entry) load() (value any, ok bool) {
    p := e.p.Load()
    // 然后p处于硬删除或者软删除状态，则返回nil
    if p == nil || p == expunged {
        return nil, false
    }
    // 返回地址p所指向的值
    return *p, true
}

4 Store

1
2
3
func (m *Map) Store(key, value any) {
    _, _ = m.Swap(key, value)
}

Store函数是通过调用Swap函数来实现逻辑功能的：

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
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
        }
    }
    m.mu.Lock()
    // double check
    read = m.loadReadOnly()
    if e, ok := read.m[key]; ok {
        if e.unexpungeLocked() {
            // 如果p == expunged，则将read中p的状态更新为nil，然后在dirty插入该key
            m.dirty[key] = e
        }
        // p不为nil的话，则直接更新
        if v := e.swapLocked(&value); v != nil {
            loaded = true
            previous = *v
        }
    } else if e, ok := m.dirty[key]; ok {
        // read中不存在该key，但是dirty中存在，则也是直接更新
        if v := e.swapLocked(&value); v != nil {
            loaded = true
            previous = *v
        }
    } else {
        // 如果都不存在该key
        if !read.amended {
            // dirty为nil，则需要创建dirty，并从read中拷贝未删除的元素到dirty中
            m.dirtyLocked()
            // 并且更新amended字段
            m.read.Store(&readOnly{m: read.m, amended: true})
        }
        // 在dirty中写入新key
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
    return previous, loaded
}
1
2
3
4
5
6
7
8
9
10
11
12
13
func (e *entry) trySwap(i *any) (*any, bool) {
    for {
        p := e.p.Load()
        // 如果p被硬删除了，则直接返回false
        if p == expunged {
            return nil, false
        }
        // 否则将其存到entry中
        if e.p.CompareAndSwap(p, i) {
            return p, true
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (m *Map) dirtyLocked() {
    // dirty 不为 nil则直接返回
    if m.dirty != nil {
        return
    }
    read := m.loadReadOnly()
    m.dirty = make(map[any]*entry, len(read.m))
    // 遍历未被删除的key
    for k, e := range read.m {
        if !e.tryExpungeLocked() {
            m.dirty[k] = e
        }
    }
}

5 Delete

1
2
3
func (m *Map) Delete(key any) {
    m.LoadAndDelete(key)
}

map的Delete操作都是调用LoadAndDelete来实现的，因此直接看它是怎么实现的即可：

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) LoadAndDelete(key any) (value any, loaded bool) {
    read := m.loadReadOnly()
    e, ok := read.m[key]
    // read中不存在，并且dirty有read没有的key
    if !ok && read.amended {
        // 上锁
        m.mu.Lock()
        read = m.loadReadOnly()
        e, ok = read.m[key]
        // double check
        if !ok && read.amended {
            // 在dirty中找到该key，则直接删除，并且调用missLocked
            e, ok = m.dirty[key]
            delete(m.dirty, key)
            m.missLocked()
        }
        m.mu.Unlock()
    }
    // read中存在，直接删除
    if ok {
        return e.delete()
    }
    // read和dirty都不存在该key，返回false
    return nil, false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
func (e *entry) delete() (value any, ok bool) {
    for {
        p := e.p.Load()
        // 如果p为nil和expunged则返回false
        if p == nil || p == expunged {
            return nil, false
        }
        // 否者将其p删除，置为nil
        if e.p.CompareAndSwap(p, nil) {
            return *p, true
        }
    }
}

为什么这里删除p的时候不是直接将其置为expunged而是置为nil呢？

因为在tryExpungeLocked函数中，会将nil设置为expunged

1
2
3
4
5
6
7
8
9
10
11
func (e *entry) tryExpungeLocked() (isExpunged bool) {
    p := e.p.Load()
    for p == nil {
        // p == nil，则将其置为expunged
        if e.p.CompareAndSwap(nil, expunged) {
            return true
        }
        p = e.p.Load()
    }
    return p == expunged
}

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

6 Range

由用户实现，Range将遍历map中的所有k-v对，将他们传给f函数，如果f返回false则停止遍历

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
func (m *Map) Range(f func(key, value any) bool) {
    read := m.loadReadOnly()
    // amended为true
    if read.amended {
        m.mu.Lock()
        read = m.loadReadOnly()
        // double check
        if read.amended {
            // 将dirty拷贝给read
            read = readOnly{m: m.dirty}
            m.read.Store(&read)
            m.dirty = nil
            m.misses = 0
        }
        m.mu.Unlock()
    }
    // 遍历read
    for k, e := range read.m {
        v, ok := e.load()
        if !ok {
            continue
        }
        if !f(k, v) {
            break
        }
    }
}

7 总结

什么时候会出现expunge？

当key的值在 read 中为 nil，随后由其他操作触发read 向 dirty 复制，nil 被转变为expunge。此时 dirty 不为空，且key 在dirty 中不存在。

image-20230913193828380