关于go:Golang底层实现系列syncMap底层实现

[最初更新日期：2023-05-08 18:04]

Go 中一般的 map 是非线程平安的，想要线程平安的拜访一个 map，有两种形式一种是 map+mutex 另一种就是原生的 sync.Map，这篇文章会具体的介绍 sync.Map 底层是如何实现的，以及一些罕用的场景。

如何保障线程平安？

sync.Map 的数据结构如下：

type Map struct {
   mu Mutex // 锁，保障写操作及 dirty 晋升为 read 的线程平安
   read atomic.Value // readOnly 只读 map
   dirty map[any]*entry // 脏 map，当外部有数据时就肯定蕴含 read 中的数据
   misses int // read 未命中次数，当达到肯定次数时会触发 dirty 中的护具降职到 read
}

如果只看这个构造咱们可能会有以下几个疑难：

1. sync.Map 中也用了 mutex 那和 map+mutex 的实现形式不就一样了吗？
2. misses 做什么用的？
3. read 的类型是一个 atomic.Value 而 dirty 是map[any]*entry, 为什么不同？

sync.Map 中也用了 mutex 那和 map+mutex 的实现形式不就一样了吗？

1. 在实质上都是通过 map+mutex 的实现形式来实现的
2. sync.Map 通过减少 read map，升高在进行读取操作时的加锁概率，减少读取的性能。

misses 做什么用的？

1. misses 是用于标记 read 中未命中次数的
2. 当 misses 达到肯定值时会触发 dirty 的降职（晋升为 read）

具体源码如下：

// 当执行 Load 操作时没能在 read 中命中 key，则进行一次 miss 记录
func (m *Map) missLocked() {
   // 1.miss 计数加 1
   m.misses++
   // 2. 判断 dirty 是否满足降职条件
   if m.misses < len(m.dirty) {
      // 2.1 不满足间接返回
      return
   }
   // 3. 将 dirty 中的数据转存到 read 的 m 中，旧的 read 中的数据被摈弃
   m.read.Store(readOnly{m: m.dirty})
   // 4. 清空 dirty
   m.dirty = nil
   // 5. 重置 miss 计数
   m.misses = 0
}

从代码中能够看到：

1. 当 misses 值大于等于 dirty 中数据个数的时候会触发 dirty 的降职
2. 在 dirty 降职时，直间接把 read 重置成了一个新生成的 readOnly, 其中 m 为新的 dirty，amended 为默认值 false，保障每次触发降职都主动将 amended 设置为了 false
3. 在 dirty 降职时，并没有触发数据的拷贝

read 的类型是一个 atomic.Value 而 dirty 是map[any]*entry, 为什么不同？

type readOnly struct {m       map[any]*entry // read map 中的数据
   amended bool // 标记 dirty map 中是否有 read 中没有的 key，如果有，则此值为 true
}
type entry struct {p unsafe.Pointer // *interface{}  一个指向具体数据的指针
}

1. read 的类型底层是存储的 readOnly 类型，而 readOnly 类型只是在 map[any]*entry 的根底上减少了一个 amended 标记
2. 如果 amended 为 false，则代表 dirty 中没有 read 中没有的数据，此时能够防止一次 dirty 操作（会加锁），从而升高无意义的加锁。
3. read 被申明为 atomic.Value 类型是为了满足在无锁的状况下多个 Goroutine 同时读取 read 时的数据一致性

sync.Map 实用于那些场景？

sync.Map 更适宜读多写少的场景，而当 map 须要频繁写入的时候，map+mutex 的计划通过管制锁的力度能够达到比 sync.Map 更好的性能。

sync.Map 不反对遍历操作，因为读写拆散的设计使得在遍历过程中可能存在一些未实现的批改操作，导致遍历后果不确定。

为什么 sync.Map 适宜读多写少的场景？

sync.Map 的读取办法为 Load 办法，具体的源码实现如下：

func (m *Map) Load(key any) (value any, ok bool) {
   // 1. 将 read 中的数据强转为 readOnly
   read, _ := m.read.Load().(readOnly)
   // 2. 从 read 中查问 key，检查数据是否存在
   e, ok := read.m[key]
   // 3. 如果 read 中不存在，且 amended 标记显示 dirty 中存在 read 中没有的 key，则去 dirty 中查问
   if !ok && read.amended {
      // 3.1 开始操作 dirty，须要加锁保障线程平安
      m.mu.Lock()
      // 3.2 从新从 read 中查看一次，防止在 Lock 执行前 dirty 中的数据触发了降职到 read 的操作
      read, _ = m.read.Load().(readOnly)
      e, ok = read.m[key]
      // 3.3 同 3
      if !ok && read.amended {
         // 3.4 从 dirty 中查问
         e, ok = m.dirty[key]
         // 3.5 无论是否从 dirty 中查问到数据，都相当于从 read 中 miss 了，须要更新 miss 计数（更新计数可能会触发 dirty 数据的降职）m.missLocked()}
      // 3.5 操作实现解锁
      m.mu.Unlock()}
   // 4. 检测后果,ok 为 false 代表没有查问到数据
   // ok 为 true 分为两种状况：1. 从 read 中查问到了数据，read 命中；2. 从 dirty 中查问到了数据
   // ok 为 false 分为两种状况：//    1.read 没有命中，但 read.amended 为 false
   //    2.read 没有命中，read.amended 为 true，但 dirty 中也不存在
   if !ok {return nil, false}
   // 返回查问到的数据（这个值也并不一定是真的存在，须要依据 p 确定是一个失常的值还是一个 nil）return e.load()}
// 当从 read 或者 dirty 中获取到一个 key 的值的指针时，须要去加载对应指针的值
func (e *entry) load() (value any, ok bool) {    
   // 1. 院子操作获取对应地址的值
   p := atomic.LoadPointer(&e.p)
   // 2. 如果值曾经不存在或者标记为被删除则返回 nil,false
   if p == nil || p == expunged {return nil, false}
   // 3. 返回具体的值，true
   return *(*any)(p), true
}

每次读取数据时，优先从 read 中读取，且 read 中数据的读取不须要进行加锁操作；当 read 中未命中且 amended 标记显示 dirty 中存在 read 中没有的数据时，才进行 dirty 查问，并加锁。在读多写少的状况下，大多数时候数据都在 read 中所以能够防止加锁，以此来进步并发读的性能。

sync.Map 的写操作方法为 Store 办法

func (m *Map) Store(key, value any) {
   // 1. 从 read 中查问数据是否曾经存在，如果存在则尝试批改
   read, _ := m.read.Load().(readOnly)
   if e, ok := read.m[key]; ok && e.tryStore(&value) {
      // 1.1 read 中存在数据，且更新实现，间接返回
      return
   }
   //2.read 中没有，筹备操作 dirty，为保障线程平安加锁
   m.mu.Lock()
   read, _ = m.read.Load().(readOnly)
   if e, ok := read.m[key]; ok {
   // 3. 如果在 read 中查问到数据，则查看是否曾经被标记为删除，if e.unexpungeLocked() {
      // 3.1 如果被标记为删除须要清空标记并退出到 dirty 中
         m.dirty[key] = e
      }
      // 3.2 更新 entry 的值
      e.storeLocked(&value)
   } else if e, ok := m.dirty[key]; ok {
      // 4 如果存在于 dirty 中，则间接更新 entry 的值
      e.storeLocked(&value)
   } else {
   // 5 如果之前这个 key 不存在，则将新的 key-value 退出到 dirty 中
      if !read.amended {
      // 5.1 如果 read.amended 标记显示之前 dirty 中不存在 read 中没有的 key，则重置 dirty，并标 amended 为 true
         // 5.1.1 将 read 中所有未被标记为删除的 entry 重新加入到 dirty 中
         m.dirtyLocked()
         // 5.1.2 更新 read.amended 标记
         m.read.Store(readOnly{m: read.m, amended: true})
      }
      // 5.2 将新的 key-value 退出到 dirty 中
      m.dirty[key] = newEntry(value)
   }
   m.mu.Unlock()}
// 判断 entry 是否被标记为删除，如果是将其批改为 nil
func (e *entry) unexpungeLocked() (wasExpunged bool) {return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

写操作分为以下几种状况：

1. 数据在 read 中
2. 数据在 read 中但曾经被标记为删除
3. 数据在 dirty 中
4. 一个全新的数据

当数据在 read 中时，Store 会尝试通过原子操作批改数据，如果原子操作胜利，则相当于数据更新实现；

具体的代码如下：

func (e *entry) tryStore(i *any) bool {
   for {
       // 1. 获取 entry 具体的值
      p := atomic.LoadPointer(&e.p)
      // 2. 如果数据曾经被标记删除，则返回 false
      if p == expunged {return false}
      // 3. 更新以后值，并返回 true
      if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {return true}
   }
}

当数据在 read 中曾经被标记为删除，此时须要从新将 entry 退出到 dirty 中，并更新值（这里实质上减少了一个新的 entry 只是服用了之前 entry 的地址空间）

当数据在 dirty 中时，则间接通过原子操作更新 entry 的指针；

当数据是一个新数据时，会创立一个新的 entry 退出到 dirty 中，并且如果是 dirty 中的第一个数据则会执行 dirtyLocked 办法，将 read 中以后的数据（未标记删除的）退出到 dirty 中。

dirtyLocked 的具体实现如下：

func (m *Map) dirtyLocked() {
    //1 dirty 之前是 nil 的状况才能够进行重置操作
   if m.dirty != nil {return}
   // 2 获取 read 中的数据
   read, _ := m.read.Load().(readOnly)
   // 3 初始化 dirty
   m.dirty = make(map[any]*entry, len(read.m))
   // 4 遍历 read
   for k, e := range read.m {
      // 4.1 将非 nil 且未被标记为删除的对象退出到 dirty 中
      if !e.tryExpungeLocked() {m.dirty[k] = e
      }
   }
}
// 判断 entry 是否被标记为删除，如果 entry 的值为 nil，则将其标记为删除
func (e *entry) tryExpungeLocked() (isExpunged bool) {
    // 1 获取 entry 的值
   p := atomic.LoadPointer(&e.p)
   for p == nil {
       // 2 如果以后 entry 的值为空，则尝试将此 key 标记为删除
      if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {return true}
      p = atomic.LoadPointer(&e.p)
   }
   // 3 判断 p 是否为被标记为删除
   return p == expunged
}

通过下面的剖析咱们能够发现当写操作频繁时存在以下几个问题

1. dirty 中存在大量数据，而 read 的查问会大概率无奈命中，从而导致查问须要查问 read 和 dirty 两个 map 且有额定的冗余操作，所以读性能被大大降低
2. 频繁的无奈命中导致 dirty 数据的降职，尽管降职时只是进行指针切换及 dirty 的清空，但每次降职后的第一次写入都会导致 dirty 对 read 进行拷贝，大大降低性能。
3. 每次写操作为了因为不确定数据是在 read 还是 dirty 或者新数据须要进行额定的检查和操作
4. dirty 中和 read 中在某些状况下存在数据反复，内存占用会高一些

综上，在写操作比拟频繁的时候，sync.Map 的各方面性能都大大降低；而对于一些只有极少写操作的数据（比方：只在服务器启动时加载一次的表格数据），sync.Map 能够进步并发操作的性能。

如何删除数据

在下面的 dirtyLoacked 办法中咱们看到当初始化 dirty 后，会遍历 read 中的数据，将非 nil 且未被标记为删除的对象退出到 dirty 中。由此能够看出 read 中的数据在删除时并不会立即删除只是将对象标记为 nil 或者 expunged。

具体代码如下：（Delete 办法实质上就是执行的 LoadAndDelete）

func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {read, _ := m.read.Load().(readOnly)
   // 1 从 read 中查问数据
   e, ok := read.m[key]
   // 2 如果 read 中不存在，且 amended 标记显示 dirty 中存在 read 中没有的 key，则去 dirty 中查问
   if !ok && read.amended {
      // 3.1 开始操作 dirty，须要加锁保障线程平安
      m.mu.Lock()
      read, _ = m.read.Load().(readOnly)
      // 3.2 从新从 read 中查看一次，防止在 Lock 执行前 dirty 中的数据触发了降职到 read 的操作
      e, ok = read.m[key]
      if !ok && read.amended {
         // 3.3 从 dirty 中查问
         e, ok = m.dirty[key]
         // 3.4 从 dirty 中删除
         delete(m.dirty, key)
         // 3.5 无论是否从 dirty 中查问到数据，都相当于从 read 中 miss 了，须要更新 miss 计数（满足条件后会触发 dirty 降职）m.missLocked()}
      m.mu.Unlock()}
   // 4 和 load 一样，这里 ok 为 true 可能是在 read 中读取到数据或者 dirty 中读取到数据，// dirty 中的话尽管曾经删除但须要清空 entry 中的指针 p
   if ok {
      // 5 标记删除
      return e.delete()}
   return nil, false
}

如上述代码第 5 局部所示，无论 entry 存在哪里，最终都须要将 entry 标记为删除。如果存在 read 中会在 dirty 初始化时不被退出到 dirty 中，当 dirty 再次降职时 read 中的数据也就被抛弃了。如果存在 dirty 中则间接清空了数据并标记 entry 被删除。

sync.Map 的 Range 办法

sync.Map 并不反对遍历，但却提供了一个 Range 办法，此办法并不是和 range 关键字一样对 map 的遍历。

Range 办法的具体作用：

1. 遍历所有 read 中的元素，对其中的每个元素执行函数 f
2. 如果当任何一个元素作为参数执行函数 f 返回 false，则立即中断遍历

尽管在执行初始阶段 Range 会将 dirty 的数据降职一次，但依然不能保障在执行过程中没有新的数据，所以 Range 只是遍历了最新的 read 中的数据，而非全副数据。

// 遍历 sync.Map
func (m *Map) Range(f func(key, value any) bool) {read, _ := m.read.Load().(readOnly)
   // 1 如果存在未降职的数据，则先进行一次 dirty 数据降职
   if read.amended {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()}
   // 2 遍历 read 中的所有 entry，别离执行 f 函数
   for k, e := range read.m {v, ok := e.load()
      if !ok {continue}
      // 3 当某个 entery 执行 f 函数返回 false，则中断遍历
      if !f(k, v) {break}
   }
}

其余

问：什么时候革除被标记删除的 value

答：当首次向 dirty 中存入数据时，会触发 dirty 复制 read 中的内容，此时再复制时只复制了非 nil 且未被标记删除的 entry，当 dirty 再次降职时就笼罩掉了 read 中的数据，实现被标记删除的 entry 的删除。