Go语言源码sync.Map解读，一种高性能并发安全的字典类型

package main

import "time"

func main() {
	m := make(map[int]string)
	m[1] = `test`
	go func() {
		for {
			m[1] = `test`
		}
	}()
	go func() {
		for {
			_ = m[1]
		}
	}()
	time.Sleep(time.Second)
}

fatal error: concurrent map read and map write
goroutine 6 [running]:
runtime.throw(0x107c19c, 0x21)
.....

func main() {
	var m sync.Map
	// 新增
	m.Store(1, `add`)
	// 获取
	if value, ok := m.Load(1); ok {
		fmt.Println(value.(string))
	}
	// 遍历
	m.Range(func(key, value interface{}) bool {
		fmt.Println(key, value)
		return true
	})
	// 删除
	m.Delete(1)
}

type Map struct { 
	mu Mutex
	// read map的 k v(entry) 是不变的，删除只是打标记，插入新key会加锁写到dirty中
	// 因此对read的读取无需加锁
	read atomic.Value // readOnly
	// 读写需要加锁
	dirty map[interface{}]*entry
 	// 当load操作在 read.m 中未找到，尝试从dirty中进行 load 时(不管是否存在)，misses++
	// 当misses >= dirty map len时，dirty被提升为read 并且重新分配dirty == nil
	misses int
}

type readOnly struct {
	m       map[interface{}]*entry
	amended bool // 如果是 true 的话说明 dirty 里面有些 key 在 m 是没有的。
}

type entry struct {	
	// p  指向 *interface{}
	// 如果 p == nil, 说明 kv 已经被删除并且 m.dirty == nil
	// 如果 p == expunged, 说明 kv 已经删除，并且 m.dirty ！= nil, 这个 key 在 dirty 中未找到
	// 其他情况 p 是 interface{}地址，m.dirty != nil 的话说明 read.m[key] 和 dirty[key] 指向一个 *entry
	p unsafe.Pointer // *interface{}
}

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
	read, _ := m.read.Load().(readOnly) // 1
	e, ok := read.m[key]
	if !ok && read.amended {
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly) // 2
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
			// m.misses++
			// 当 miss 数量满足一定条件时，会触发dirty 提升为 read
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if !ok {
		return nil, false
	}
	return e.load()
}

func (e *entry) load() (value interface{}, ok bool) {
	p := atomic.LoadPointer(&e.p)
	if p == nil || p == expunged {
		return nil, false
	}
	return *(*interface{})(p), true
}

func (m *Map) Store(key, value interface{}) {
	read, _ := m.read.Load().(readOnly)
	// 如果 read 有的话，直接尝试修改 read.m[key] = value
	if e, ok := read.m[key]; ok && e.tryStore(&value) {
		return
	}

	m.mu.Lock()
	read, _ = m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok {
		if e.unexpungeLocked() {
			// 如果 read 有这个 key，并且 p == expunged, 说明 m.dirty != nil 并且dirty里面没有这个 key 
			// 1. 设置 p = nil
 			// 2. dirty 中新增 key
			// 3. 让dirty[key] 和 read.m[key] 指向同一个 *entry
			m.dirty[key] = e
		}
 		// e.p = &value
		e.storeLocked(&value)
	} else if e, ok := m.dirty[key]; ok {
 		// read 中没有，dirty中有，直接修改
		e.storeLocked(&value)
	} else {
		if !read.amended {
			// 新增的key 在dirty 中有, 但是read中没有，标记下
			m.dirtyLocked()
			m.read.Store(readOnly{m: read.m, amended: true})
		}
		m.dirty[key] = newEntry(value)
	}
	m.mu.Unlock()
}

func (m *Map) dirtyLocked() {
	if m.dirty != nil {
		return
	}
	// m.dirty == nil的话，将read里面不是expunged kv 复制到dirty
	read, _ := m.read.Load().(readOnly)
	m.dirty = make(map[interface{}]*entry, len(read.m))
	for k, e := range read.m {
		if !e.tryExpungeLocked() {
			m.dirty[k] = e
		}
	}
}

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

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

func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	if !ok && read.amended {
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if ok {
		return e.delete()
	}
	return nil, false
}

// 删除的话，不是直接删除kv,而是让 e.p == nil
func (e *entry) delete() (value interface{}, ok bool) {
	for {
		p := atomic.LoadPointer(&e.p)
		if p == nil || p == expunged {
			return nil, false
		}
		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
			return *(*interface{})(p), true
		}
	}
}

func (m *Map) Range(f func(key, value interface{}) bool) {
	// 如果所有的 key 都在read 中是不用加锁的
	read, _ := m.read.Load().(readOnly)
	if read.amended {
		// m.dirty包含一些不在read.m中的kv,遍历的时候就会触发触发dirty 提升为 read
		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
		}
	}
}