Gang's Blog.
Gang's Blog.

Golang中sync.map深入探究

Gang Gang 收录于 Golang
 约 900 字 预计阅读 5 分钟 

sync.Map 是 Go 语言标准库中提供的并发安全的 map 实现，采用了以空间换取时间的策略。

数据结构

Map 

1
2
3
4
5
6

type Map struct {
    mu Mutex				// 互斥锁
    read atomic.Value 		// 只读map
    dirty map[any]*entry	// 
    misses int				// 只读map中miss的次数
}

在Map中的字段意义如下：

  • mu：互斥锁
  • read：无锁只读的map，对应的类型实际上是readOnly
  • dirty：加锁的map
  • misses：只读map的miss次数

readOnly 

1
2
3
4

type readOnly struct {
	m       map[any]*entry	// 只读map
	amended bool 			// 如果dirty map中有一些key在只读map中时没有的，则为true .
}

当amended字段为true的时候，则说明在dirty的map中有只读map中不存在的值，这时候在访问的话，除了readonly这个map需要访问，还需要访问dirty这个map。

entry 

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

type entry struct {
    // p 指向存储在条目中的 interface{} 值。
    //
    // 如果 p == nil，则条目已被删除，并且 m.dirty == nil 或 m.dirty[key] 是 e。
    //
    // 如果 p == expunged，则条目已被删除，m.dirty != nil，并且该条目在 m.dirty 中缺失。
    //
    // 否则，该条目是有效的，并记录在 m.read.m[key] 中，并且如果 m.dirty != nil，也记录在 m.dirty[key] 中。
    //
    // 可以通过原子替换为 nil 来删除条目：当 m.dirty 下一次创建时，它将原子地将 nil 替换为 expunged，并且不设置 m.dirty[key]。
    //
    // 条目的关联值可以通过原子替换来更新，前提是 p != expunged。如果 p == expunged，条目的关联值只能在首先设置 m.dirty[key] = e 后更新，以便使用 dirty map 的查找找到该条目。
    p unsafe.Pointer // *interface{}
}

在entry中的p有三种状态：

  1. p = nil：软删除状态。表示条目已经被删除了，dirty中还存在
  2. p = expunged：硬删除状态。表示条目已经被删除了，且dirty中也不存在了。
  3. 存活状态。

读数据流程

Map.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

func (m *Map) Load(key any) (value any, ok bool) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
    
    // 如果没有找到，并且只读map中的amended字段为true的话，就还需要去dirtymap中找
	if !ok && read.amended {
        
        // 加锁
		m.mu.Lock()
        
        // double check，再次确认一下
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
			// 更新一下misses
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if !ok {
		return nil, false
	}
    
    // 见下面
	return e.load()
}

entry.load() 

1
2
3
4
5
6
7
8

func (e *entry) load() (value any, ok bool) {
	p := atomic.LoadPointer(&e.p)
	if p == nil || p == expunged {
        // 这两种情况（软删除，硬删除）都是已经删除的情况，所以直接return了nil
		return nil, false
	}
	return *(*any)(p), true
}

Map.missLocked() 

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

func (m *Map) missLocked() {
    // 累加misses次数
	m.misses++
	if m.misses < len(m.dirty) {
        // 如果misses的次数还小于dirtymap的容量，就暂时什么都不做，直接返回
		return
	}
    
    // 如果misses的次数已经超过了dirtymap的容量了，则将dirtymap直接覆盖到只读map去
    // 此时readOnly中的amended也被初始化为了false
	m.read.Store(readOnly{m: m.dirty})
    
    // 清空dirtymap
	m.dirty = nil
    
    // 重置misses次数
	m.misses = 0
}

只读map没有写的操作，只有上面看到的直接被替换的过程。

写数据流程

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
24
25
26
27
28
29

func (m *Map) Store(key, value any) {
	read, _ := m.read.Load().(readOnly)
    // 首先看下是否是软删除的，如果是软删除则直接通过cas修改引用就可以了，
    // 因为软删除的数据在dirtymap中还是存在的，两个map的数据的引用指向同一个地方
	if e, ok := read.m[key]; ok && e.tryStore(&value) {
		return
	}

	m.mu.Lock()
	read, _ = m.read.Load().(readOnly)
    // double check
	if e, ok := read.m[key]; ok {
		if e.unexpungeLocked() {
			m.dirty[key] = e
		}
		e.storeLocked(&value)
	} else if e, ok := m.dirty[key]; ok {
		e.storeLocked(&value)
	} else {
        // 两个map都没有
		if !read.amended {
            // 如果原来amended为false的话，将被设置为true
			m.dirtyLocked()
			m.read.Store(readOnly{m: read.m, amended: true})
		}
		m.dirty[key] = newEntry(value)
	}
	m.mu.Unlock()
}

entry.tryStore() 

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

// 尝试恢复一个软删除的数据
func (e *entry) tryStore(i *any) bool {
	for {
		p := atomic.LoadPointer(&e.p)
		if p == expunged {
            // 如果是硬删除，那就没办法了，直接返回
			return false
		}
		if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
            // 如果是软删除的，则通过cas恢复只读map中的值的引用
			return true
		}
	}
}

Map.dirtyLocked() 

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

func (m *Map) dirtyLocked() {
	if m.dirty != nil {
        // 此时dirty和map应该会有一样的数据，应为在上面判断了!read.amended进来的。
		return
	}

	read, _ := m.read.Load().(readOnly)
	m.dirty = make(map[any]*entry, len(read.m))
    
    // 将非删除态的数据全部同步至dirtymap中。
    // 在这里软删除态的会被更新成硬删除，并且会被过滤掉
	for k, e := range read.m {
		if !e.tryExpungeLocked() {
			m.dirty[k] = e
		}
	}
}

entry.tryExpungeLocked() 

 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 {
        // 如果是软删除，则更新成硬删除，并返回true
		if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
			return true
		}
		p = atomic.LoadPointer(&e.p)
	}
	return p == expunged
}

删数据流程

Map.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

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

func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
	read, _ := m.read.Load().(readOnly)
    // 首先还是从只读map中查询
	e, ok := read.m[key]
    
    // 如果不存在，且dirtymap中有额外的数据
    // 则再去dirtymap中查询
	if !ok && read.amended {
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
        // double check
		if !ok && read.amended {
			e, ok = m.dirty[key]
			delete(m.dirty, key)
			m.missLocked()
		}
		m.mu.Unlock()
	}
    
    // 如果再只读map中存在
	if ok {
        
        // 使用cas的方法将当前entry的指针指向nil
        // 即成为软删除状态
		return e.delete()
	}
	return nil, false
}

entry.delete() 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

遍历流程

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

func (m *Map) Range(f func(key, value any) bool) {
	
	read, _ := m.read.Load().(readOnly)
    // 判断一下只读map中的数据是否完整
	if read.amended {
		// 不完整，执行以下类似于missLocked方法的操作
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly)
		if read.amended {
			read = readOnly{m: m.dirty}
			m.read.Store(read)
			m.dirty = nil
			m.misses = 0
		}
		m.mu.Unlock()
	}

	for k, e := range read.m {
		v, ok := e.load()
		if !ok {
			continue
		}
		if !f(k, v) {
			break
		}
	}
}

相关内容

更新于 2023-12-23 
CC BY-NC-SA 4.0
Golang源码阅读
返回 | 主页
0%