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

2023-06-06 19:16:02 302 林溪

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