Golang底层实现系列——sync.Map底层实现

Posted on by hackdl

[最后更新日期：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

从代码中可以看到：

  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的删除。

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: ChatGPT 背后基础设施的算力概念

在人工智能领域，算力通常指的是计算机系统的处理能力和性能，它是评估和衡量计算机硬件和软件系统的一个重要指标。随着深度学习模型的不断发展和复杂化，对算力的需求也越来越大。高性能计算机、GPU（图形处理器）、TPU（Tensor Processing Unit，张…

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: