为什么golang的map不支持并发操作？sync.map又是怎么实现的？

sync.map的总结

• 我先把结论贴在前面，让人有一种大概的认知

sync.map的实现原理

dirtyLocked

一起深入

如果要详细聊这个问题，那就要说一说golang中map的问题以及为什么会出现sync.map。

map

map的问题

在go里面，map 是不支持并发写操作的，我们看下面一个例子

• 其实slice也不是并发安全的，但 Go 的运行时只对 map 进行了检测和报错。
  

map的数据结构

/usr/local/Cellar/go/1.17.5/libexec/src/runtime/map.go

type bucket struct {
//next 是一个指向下一个 bucket 的指针
	next    *bucket
//allnext 是一个指向所有 bucket 的指针，用于遍历所有的 bucket。
	allnext *bucket
//typ 是一个枚举类型，表示 bucket 的类型，有 memBucket 或 blockBucket 两种
	typ     bucketType // memBucket or blockBucket (includes mutexProfile)
//hash 是一个无符号整数，表示 bucket 的哈希值，用于在哈希表中定位。
	hash    uintptr
//size 是一个无符号整数，表示 bucket 的大小，即记录数据的大小。
	size    uintptr
//nstk 是一个无符号整数，表示 bucket 的栈深度，即栈字的个数。
	nstk    uintptr
}

• 在并发模式下保证数据安全，最基础的方式往往就是依靠锁、信号量、原子操（使用硬件级别的指令来实现不可分割的操作）作来实现，比如channle是使用了mutex来保证同一时间只有一个goroutine来写。waitgroup则是使用了信号量来控制并发安全。但是在map中我们并没有看到任何保证数据安全的操作。
• 那么这个时候，我们就需要在map并发写入提供适当的同步机制，以确保程序的正确性和稳定性。比如我们可以这样

type MapNew struct {
	sync.RWMutex
	M map[int]int
}

• 但是频繁的上锁解锁肯定会牺牲性能。这个时候sync.map出来了,sync.map一方面利用互斥锁来实现并发安全，另一方面，通过空间换时间的方式，通过只读的read map和可写的dirty map提高了map的读写操作。

sync.Map

sync.Map 是 Go 语言标准库中提供的一个并发安全的 Map 实现。它的设计目标是在多个 goroutine 之间共享数据时，提供高效的读写操作。

数据结构

type Map struct {
//更新dirty map和miss计算器的时候加锁
	mu Mutex
	
// 读map  读这个map里面的任何元素都是安全的，和互斥锁没有关系，但是如果要写这个map，必须要上互斥锁。
	read atomic.Value // readOnly

 最新写入的数据
	dirty map[interface{}]*entry

 计数器，每次需要读 dirty 则 +1,到达一定次数则会将写map升级为读map
	misses int
}

• readOnly 的数据结构

type readOnly struct {
    // 内建 map
    m  map[interface{}]*entry
    // 如果写map中存在读map中不存在的key，标记为true
    amended bool
}


type entry struct {
//该指针指向真正的值的地址
//指针有三种形态，一个是p==nil，表示这个entry已经被删除了,并且m.dirty==nil
//p==expunged entry已经被清除了，但是m.dirty!=nil
    p unsafe.Pointer  // 等同于 *interface{}
}

我们再来看sync.map的四种方法

m.misses >= len(m.dirty)

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	if !ok && read.amended {
		m.mu.Lock()
		// Avoid reporting a spurious miss if m.dirty got promoted while we were
		// blocked on m.mu. (If further loads of the same key will not miss, it's
		// not worth copying the dirty map for this key.)
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
			// Regardless of whether the entry was present, record a miss: this key
			// will take the slow path until the dirty map is promoted to the read
			// map.
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if !ok {
		return nil, false
	}
	return e.load()
}

• Store:存储键值对,如果键值对出现在读map中，并且不是expunged，则通过原子操作直接更新value(相同的key，读map和写map指向同一个地址)，如果 read map 中没有 key 或者 entry 不能更新（可能被标记为 expunged），则需要加锁并处理三种情况：
  • 情况 1：read map 中有 key，但 entry 被标记为 expunged。这时需要先将 entry 的状态改为 nil，并拷贝到 dirty map 中，然后再更新 entry 的值。
  • 情况 2：read map 中没有 key，但 dirty map 中有 key。这时直接更新 dirty map 中的 entry 的值即可。
  • 情况 3：read map 和 dirty map 中都没有 key。这时需要先检查 read map 是否被修改过（amended 字段），如果没有，则调用 dirtyLocked 方法将 read map 拷贝到 dirty map 中（除了被标记删除的数据），并将 amended 改为 true。然后再将新的键值对存入 dirty map 中。

// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
	read, _ := m.read.Load().(readOnly)
	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() {
			// The entry was previously expunged, which implies that there is a
			// non-nil dirty map and this entry is not in it.
			m.dirty[key] = e
		}
		e.storeLocked(&value)
	} else if e, ok := m.dirty[key]; ok {
		e.storeLocked(&value)
	} else {
		if !read.amended {
			// 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.Store(readOnly{m: read.m, amended: true})
		}
		m.dirty[key] = newEntry(value)
	}
	m.mu.Unlock()
}

• Delete:如果read map里面有值，则直接删，如果read map里面没有值，则加锁，并且read.amended是true（其实就是在读写map不一致，并且读map里面没有的情况下），直接删除dirty map

// Delete deletes the value for a key.
func (m *Map) Delete(key interface{}) {
	m.LoadAndDelete(key)
}

• Range:先判断read.amended的值，如果是false，表示readmap和dirty map 一致。如果是true，上锁，将dirty map赋值给read map,将dirty置为nil。

func (m *Map) Range(f func(key, value interface{}) bool) {
	// We need to be able to iterate over all of the keys that were already
	// present at the start of the call to Range.
	// If read.amended is false, then read.m satisfies that property without
	// requiring us to hold m.mu for a long time.
	read, _ := m.read.Load().(readOnly)
	if read.amended {
		// m.dirty contains keys not in read.m. Fortunately, Range is already O(N)
		// (assuming the caller does not break out early), so a call to Range
		// amortizes an entire copy of the map: we can promote the dirty copy
		// immediately!
		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
		}
	}
}