sync.map的总结

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

sync.map的实现原理

• 通过read map和dirty map 将读写分离，实现高效读写

• 如果read map读取不到并且amended为true(false表示read map和dirty map一致，就没必要再读dirty map了)，则给map加锁并从dirty map读取，将misses+1。如果map中一共有n个元素，但是读了n次都没有在read map中找到（就是misses的值大于等于map的长度），则会将dirty map升级为 read map ，dirty map 重置为nil,misses重置为0；

• 对于value的更新，优先使用read map 原子模式（因为value指向的是entry指针，属于原子类型）实现高效更新。如果read map中没有找到，并且amended是false，代表这个元素真的不存在，怎么办？map上锁并写入dirty map，并将amended设置为true ，代表read map和dirty map 不一致。这里还有一个问题，在读的时候我们说过，在一定情况下，dirty map被置为nil了，你怎么往nil里面写呢？诶，在写之前，会通过dirtyLocked方法查一下dirty map是不是nil，是nil的话就把read map里面的值拷贝给dirty map 。

• 删除的时候优先查找read map并删除。如果read map中没有，并且 amended为true，则取删除dirty map的元素，将misses+1。如果条件满足则升级dirty map。

• 关于expunged和nil 很多网上的文章将expunged和nil 讲的稀碎，估计是自己也没搞懂。我们要先有一个共识，就是expunged和nil都是属于被删除的状态。然后我再说一个问题，我们知道，在一定条件下，dirty map升级为read map ，然后dirty map被置为nil，这个时候如果有delete操作，在read map中就会被标记为nil,那么这个时候，来了一个store操作，read map中的元素会被循环写入到新的dirty map中，read map中的nil 肯定不会被拷贝，那么我们怎么标记这个元素呢？继续用nil肯定不行，因为它不属于dirty map中的删除操作啊。怎么办？那么就在read map向dirty map拷贝的时候，将nil 转换为expunged就行了。

• 有人问，expunged什么时候会被真正的删除呢？如果你有这样的问题，就再读一遍本文！

一起深入

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

map

map的问题

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

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

map的数据结构

• 为什么会出现上面的情况呢，我们就看一看map的实现 golang的map是使用hash表作为底层实现的，一个hash表里面可以有多个hash桶，也就是bucket。
• 在目录/usr/local/Cellar/go/1.17.5/libexec/src/runtime/map.go中我们看到map的数据结构，我们看到几个重要的属性
• 既然bucket存放的数据，我们再看一下bucket的数据结构，我们可以看到一个bucket存放最多8个键值对
• 我们再来看一下bucket的定义

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的四种方法

• Load:先去读map里面查找，查找不到并且读map和写map不一致，则去写map里面查找，这里面有一个小细节，在查找写map之前，需要先加锁，为什么？因为前面说过，当miss超出一个值的时候，这个条件就是m.misses >= len(m.dirty)，这个时候，写map的m就会复制一份给读map，为了避免这种情况，我们先拿到锁，确定写map不在升级过程中，然后再次读取一次读map，真的没有了，才去写map查找。

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