go 源码之 sync.Map

参考资料

Golang sync.Map 原理（两个 map 实现读写分离、适用读多写少场景） (dgrt.cn)

总结

sync.Map 是并发安全的，内部采用读（read）写（dirty）分离，常用于多读少写场景
不适用存储大量数据，因为最坏情况下，sync.Map 的内存会翻倍
设计理念
- 读写分离
  
  read：只读结构，采用原子操作，无须加锁，提高性能
  
  dirty：普通 map，读写都加锁
  
  misses：从 dirty 中读取的次数，misses>=Len(dirty) dirty 升级为 read （直接复制）
- 延迟删除
  
  删除只是为 value 打一个标记，在 dirty map 提升时才执行真正的删除
- 降低锁的粒度
  
  使用只读结构 read，原子操作，降低锁的粒度

源码

结构


// 安全读写 map
type Map struct {
	mu    Mutex          // 当写read map 或读写dirty map时 需要上锁
	read  atomic.Value   // readOnly 只读结构，,原子操作，包含了map中的一部分key：value，另外在dirty字段中
	dirty map[any]*entry // dirty 字段包括读写都需要加锁的字段，会升级为read字段

	misses int // 每次从 dirty 查找时 misses+1 当 misses 达到diry map len时，dirty被提升为read 并且重新分配dirty
}


type readOnly struct { // read 结构
	m       map[any]*entry // 存储实际元素
	amended bool           // true：表 dirty 有 read 无，可快速判断 dirty 是否存在元素
}

type entry struct {
	p unsafe.Pointer // 指向元素的地址  1. nil：正常；2. expunged：被删除；3. 指向实际元素地址
}

读 Load

read 中存在：直接返回
read 中不存在：
- amended =false，则返回 false
- amended = true，表示 dirty 中存在 read 没有的数据，加锁，从 dirty 中读取；
  
  misses++，当 misses== len(dirty)：将 dirty 数据赋值给 read ，并且 read 内的 amended=false，清空 dirty

func (m *Map) Load(key any) (value any, ok bool) {
  if read  中存在：直接返回 {
    return value,ok
  }
  
  if read  中不存在 {
    if read.amended ==false{
      return nil,false
    }
    上锁
    从 dirty 读取  value，ok 
    misses++
    if  misses== len(dirty) {
      read=dirty
      amended=false
      dirty=nil
    }
    解锁
    return value,ok
  }
}

// 读取
func (m *Map) Load(key any) (value any, ok bool) {
	// 原子操作，先从read结构中读取
	read, _ := m.read.Load().(readOnly)
	// 读取元素
	e, ok := read.m[key]
	// 元素在read结构中不存在，但是 amended=true，表示在dirty中存在
	if !ok && read.amended {
		// 存在dirty，加锁读取
		m.mu.Lock()
		// double check，避免在加锁的时候dirty map提升为read map
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended { // read 不存在，但是amended=true表示在 dirty 中存在
			e, ok = m.dirty[key] // 从dirty中读取
			m.missLocked()       // misses+1 && 判断是否需要提升dirty 为 read
		}
		m.mu.Unlock()
	}
	if !ok {
		return nil, false
	}
	// 返回结果
	return e.load()
}

dirty 升级为 read

func (m *Map) missLocked() {
	m.misses++

	if m.misses < len(m.dirty) {
		return
	}
	// 如果misses 大于等于 dirty的长度；则提升 dirty 为read
	m.read.Store(readOnly{m: m.dirty})
	m.dirty = nil
	m.misses = 0
}

写 Store

read 中存在 key，并且不是删除状态，则直接原子操作更新
read 中不存在 key 或该 key 不可直接更新：
- 上锁
- read 中存在 key：则同时更新 read 和 dirty
- read 中不存在 key，但是存在 dirty：则更新 dirty
- 全新的 key，不存在 read 和 dirty：
  - 首先判断如果 read.amended == false，则改为 true，并且判断 dirty==nil 时，将 read 加载到 dirty
  - 最后更新 dirty
- 解锁

// Store sets the value for a key.
func (m *Map) Store(key, value any) {
	// 如果read map中存在该key 且不是删除状态  则尝试直接更改(由于修改的是entry内部的pointer，因此dirty map也可见)
	read, _ := m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok && e.tryStore(&value) {
		return
	}

	// 无法在`read`中更新，则更新在 dirty
	m.mu.Lock()
	read, _ = m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok { // 如果 key 在 read 中存在
		if e.unexpungeLocked() { // 但 p == expunged，则说明 key 被删除，则 将p的状态由 expunged  更改为 nil
			m.dirty[key] = e // b. dirty map 插入 key
		}
		e.storeLocked(&value) // 将 value 存储
	} else if e, ok := m.dirty[key]; ok {
		// 如果 key 在 read 不存在，但是 dirty 存在
		e.storeLocked(&value) // 则更新value
	} else {
		// 如果 key 在 read 和 dirty 都不存在
		if !read.amended {
			m.dirtyLocked()                                  // 将 read 中所有的非删除的元素 加载 到 dirty
			m.read.Store(readOnly{m: read.m, amended: true}) // 将amended=true，表示 read 中没有，但是 dirty 中有
		}
		// 存入 dirty
		m.dirty[key] = newEntry(value)
	}
	m.mu.Unlock()
}

m.dirtyLocked()

是一个整体的指针交换操作。
当之前执行 Load() 方法且满足条件 misses=len(dirty) 时，会将 dirty 数据整体迁移到 read 中。

sync.Map 直接将原 dirty 指针 store 给 read 并将 dirty 自身也置为 nil。

因此 sync.Map 若想要保证在 amended=true（read 和 dirty 中数据不一致），并且下一次发生数据迁移时（dirty → read）不会丢失数据，dirty 中就必须拥有整个 Map 的全量数据才行。所以这里 m.dirtyLocked() 又会【将 read 中未删除的数据加入到 dirty 中】。
不过 dirtyLocked() 是通过一个迭代实现的元素从 read 到 dirty 的复制，如果 Map 中元素数量很大，这个过程付出的损耗将很大，并且这个过程是在锁保护下的。这里迭代遍历复制的方式可能会存在性能问题。

// 将 read 中所有未删除的元素复制到 dirty
func (m *Map) dirtyLocked() {
	if m.dirty != nil {
		return
	}

	read, _ := m.read.Load().(readOnly)
	m.dirty = make(map[any]*entry, len(read.m))
	for k, e := range read.m {
		if !e.tryExpungeLocked() {
			m.dirty[k] = e
		}
	}
}

删 Delete

存在 read 中，则直接将元素置为 nil
不存在 read 但是存在 dirty 中，则直接 delete 删除

func (m *Map) Delete(key any) {
	m.LoadAndDelete(key)
}
func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	if !ok && read.amended {
		// 存在 dirty 中
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
			// 从 dirty 中读取
			e, ok = m.dirty[key]
			delete(m.dirty, key) // 删除

			m.missLocked() // misses++
		}
		m.mu.Unlock()
	}
	if ok { // read 中存在，则直接将元素p置为nil
		return e.delete()
	}
	return nil, false
}

常见问题

1. sync.Map 结构用了原子操作 read atomic.Value，那为什么不直接使用原子操作即可，还要加一个 dirty

原子操作可以提高读的效率，无法提高写的效率，相反写的效率还不如锁，这也就是为什么 sync.Map 推荐多读少写的原因；

假设 sync.Map 只用 read 实现，那读操作可以提高效率，但是写的性能将会很差，而且使用 dirty + 锁，可以提高 read 并发写的效率

总而言之，原子操作读的效率较高，写的效率还不如加锁，加锁只是应用层面上的控制，原子操作上独占 CPU 操作，简单的操作会比较快，如果写操作，需要进行额外的同步和协调操作

2. sync.Map 的使用场景

多读少写；原因：

写 dirty 需要加锁
写 read 是原子操作，性能差
全新的 key 时，如果 dirty =nil 时，还会将 read 中所有数据加载到 dirty ，这个过程是加锁的，耗时

3. 为什么 sync.Map 不能被复制

内置了一个 sync.Mutex，不可复制

4. sync.Map 是如何从 dirty 升级为 read 的

每次读取 dirty 时，字段 misses++，直到 misses >= Len(dirty) 时，dirty 的数据赋值给 read，然后清空 dirty

5. sync.Map 的设计理念

读写分离、空间换取时间、降低锁的粒度、

6. sync.Map 中的 readOnly 中的 amended 的设计？

amended 表示 read 和 dirty 元素不一致，也就是 dirty 中存在 read 没有的元素

7. 什么情况下元素会同时存在 read 和 dirty，并且为什么？

当 dirty==nil 时，且插入一个全新的 key 时，read 的数据会全部加载到 dirty；

数据重复是因为，当 dirty 升级为 read 时，如果 dirty 没有 read 的数据，那么数据就会丢失

8. sync.Map 最坏情况下内存翻倍

为了能将 dirty 中的数据快速提升为 readonly，dirty 中包含了 readonly 中的全部数据，意味着最坏情况下内存占用翻倍，

如果存储了大量数据的话，需要关注这点