vlambda博客
学习文章列表

并发安全的 map:sync.Map源码分析

概述

go语言中的map并不是并发安全的,在Go 1.6之前,并发读写map会导致读取到脏数据,在1.6之后则程序直接panic,所以go 1.9之前的解决方案是额外绑定一个锁,封装成一个新的struct或者单独使用锁都可以。直到sync.Map出现提供了一种空间换时间有效减少锁的实现方法。

原理

为了减少并发抢锁导致的阻塞,sync.Map分出了read和dirty两个map,里面存的都是指针。存、删和查都先操作read,并用atomic进行并发保护,速度较快,直到read不能满足需求才去操作dirty,操作dirty的时用Mutex锁进行并发保护,速度较慢。

源码分析

主要结构

//用于保存value的interface指针,通过atomic进行原子操作type entry struct { p unsafe.Pointer // *interface{}}
//Map.read 用的就是readOnly,对其进行操作的时候,使用atomic进行保护type readOnly struct { m map[interface{}]*entry // 存储写入的数据 amended bool // 如果Map.dirty有些数据不在中的时候,这个值为true}
//sync.Map的主结构type Map struct { mu Mutex // 锁,操作dirty的时候用的  read atomic.Value // 存的是readOnly结构体,用atomic保护进行操作,无需加锁 dirty map[interface{}]*entry//加锁进行操作,和read构成冗余,misses达到len(dirty)后升级为read  misses int// 未命中read的次数}

主要方法

//加载方法,也就是提供一个键key,查找对应的值value,如果不存在,通过ok反映func (m *Map) Load(key interface{}) (value interface{}, ok bool) { read, _ := m.read.Load().(readOnly) e, ok := read.m[key] // 不存在,且dirty中有新数据 if !ok && read.amended { m.mu.Lock()//加锁    // 双检查,避免加锁的时候m.dirty提升为m.read,这个时候m.read可能被替换了。 read, _ = m.read.Load().(readOnly) e, ok = read.m[key] if !ok && read.amended { e, ok = m.dirty[key]      // 不管m.dirty中存不存在,都将misses计数加一 // missLocked()中满足条件后就会提升m.dirty m.missLocked()  } m.mu.Unlock() } if !ok { return nil, false } return e.load()// 使用原子操作读取数据} // Map.misses += 1, 如果misses == len(dirty) ,dirty升级为read ,然后dirty指向nilfunc (m *Map) missLocked() { m.misses++ if m.misses < len(m.dirty) { return } m.read.Store(readOnly{m: m.dirty}) m.dirty = nil m.misses = 0}
// 更新或者新增一个entryfunc (m *Map) Store(key, value interface{}) { read, _ := m.read.Load().(readOnly) // 如果m.read存在这个键,并且这个entry没有被标记删除,尝试直接存储。 // 因为m.dirty也指向这个entry,所以m.dirty也保持最新的entry。 if e, ok := read.m[key]; ok && e.tryStore(&value) { return }  // 如果m.read不存在或者已经被标记删除 m.mu.Lock() read, _ = m.read.Load().(readOnly) if e, ok := read.m[key]; ok {//m.read存在并已被标记删除时 if e.unexpungeLocked() {//标记成未被删除 m.dirty[key] = e //m.dirty中不存在这个键,所以加入m.dirty } e.storeLocked(&value)//更新 } else if e, ok := m.dirty[key]; ok {// m.dirty存在这个键时 e.storeLocked(&value)//更新 } else {// key不在read里面,也不在dirty里面时 if !read.amended {// amended 若为false,则表示dirty未被初始化过 m.dirtyLocked()// 初始化dirty,将dirty中未被删除的数据全都复制到dirty中,read中指向nil的数据才会被标记为expunged m.read.Store(readOnly{m: read.m, amended: true})//将amended改为true } m.dirty[key] = newEntry(value)// 将值存入dirty } m.mu.Unlock()} func (m *Map) dirtyLocked() { if m.dirty != nil { return } read, _ := m.read.Load().(readOnly) m.dirty = make(map[interface{}]*entry, len(read.m)) for k, e := range read.m { if !e.tryExpungeLocked() { m.dirty[k] = e } }}func (e *entry) tryExpungeLocked() (isExpunged bool) { p := atomic.LoadPointer(&e.p) for p == nil { // 将已经删除标记为nil的数据标记为expunged if atomic.CompareAndSwapPointer(&e.p, nil, expunged) { return true } p = atomic.LoadPointer(&e.p) } return p == expunged}
//删除一个键值func (m *Map) Delete(key interface{}) { read, _ := m.read.Load().(readOnly) e, ok := read.m[key] if !ok && read.amended {//不在read中,且dirty中有新数据 m.mu.Lock()    //双检查 read, _ = m.read.Load().(readOnly) e, ok = read.m[key] if !ok && read.amended { delete(m.dirty, key)//直接删除dirty的数据 } m.mu.Unlock() } if ok { // read中存在key,将这个key标记为删除状态,但并不删除数据 e.delete() }}
//遍历map(通过回调的方式)func (m *Map) Range(f func(key, value interface{}) bool) { read, _ := m.read.Load().(readOnly) if read.amended {// amended==true,表示dirty中有read没有的数据,此时dirty的数据最全 m.mu.Lock() read, _ = m.read.Load().(readOnly) if read.amended {// 双检查,判断获取锁之前,该值是否变了      // 将dirty升级为read read = readOnly{m: m.dirty} m.read.Store(read) m.dirty = nil m.misses = 0 } m.mu.Unlock() } // 遍历read.m,将值传入回调函数f for k, e := range read.m { v, ok := e.load() if !ok { continue } if !f(k, v) { break } }}

特别提醒

sync.Map在初始化时会将read中所有未删除的数据复制到dirty,而频繁往map中插入新数据会导致dirty中有大量read中没有的数据,从而导致read的命中率过低,需要频繁调用锁进行操作,并且未命中次数达到len(dirty)后,dirty会被升级为read,再次有新数据插入的时候,又会重复dirty初始化的过程。这一系列流程均会造成较大的开销影响整体性能。

适用场景

综上sync.Map适用于读多更新多,新增少的场景。

注:这里更新多特指当read中存在该键且未被标记删除时更新操作,此场景可直接原子更新无需加锁。



推荐阅读




喜欢本文的朋友,欢迎关注“Go语言中文网