go sync.Map源码分析

概述

go 语言中的map并不是并发安全的,在Go 1.6之前,并发读写map会导致读取到脏数据,在1.6之后则程序直接panic. 因此之前的解决方案一般都是通过引入RWMutex(读写锁)进行处理,
关于go为什么支持map的原子操作,概况来说,对map原子操作一定程度上降低了只有并发读,或不存在并发读写等场景的性能.
但作为服务端来说,使用go编写服务之后,大部分情况下都会存在gorutine并发访问map的情况,因此,1.9之后,go 在sync包下引入了并发安全的map.
这里将从源码对其进行解读.

1. sync.Map提供的方法

• 存储数据,存入key以及value可以为任意类型.

func (m *Map) Store(key, value interface{})

• 删除对应key

func (m *Map) Delete(key interface{})

• 读取对应key的值,ok表示是否在map中查询到key

func (m *Map) Load(key interface{}) (value interface{}, ok bool)

• 针对某个key的存在读取不存在就存储,loaded为true表示存在值,false表示不存在值.

func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool)

• 表示对所有key进行遍历,并将遍历出的key,value传入回调函数进行函数调用,回调函数返回false时遍历结束,否则遍历完所有key.

func (m *Map) Range(f func(key, value interface{}) bool)

2. 原理

通过引入两个map,将读写分离到不同的map,其中read map只提供读,而dirty map则负责写.
这样read map就可以在不加锁的情况下进行并发读取,当read map中没有读取到值时,再加锁进行后续读取,并累加未命中数,当未命中数到达一定数量后,将dirty map上升为read map.

另外,虽然引入了两个map,但是底层数据存储的是指针,指向的是同一份值.

具体流程:
如插入key 1,2,3时均插入了dirty map中,此时read map没有key值,读取时从dirty map中读取,并记录miss数

当miss数大于等于dirty map的长度时,将dirty map直接升级为read map,这里直接 对dirty map进行地址拷贝.

当有新的key 4插入时,将read map中的key值拷贝到dirty map中,这样dirty map就含有所有的值,下次升级为read map时直接进行地址拷贝.

3. 源码分析

3.1 主要结构

entry结构,用于保存value的interface指针,通过atomic进行原子操作.

type entry struct {
 p unsafe.Pointer // *interface{}
}

Map结构, 主结构,提供对外的方法,以及数据存储.

type Map struct {
 mu Mutex 
 //存储readOnly,不加锁的情况下,对其进行并发读取
 read atomic.Value // readOnly
 //dirty map用于存储写入的数据,能直接升级成read map.
 dirty map[interface{}]*entry
 //misses 主要记录read读取不到数据加锁读取read map以及dirty map的次数.
 misses int
}

readOnly 结构, 主要用于存储

// readOnly 通过原子操作存储在Map.read中, 
type readOnly struct {
 m map[interface{}]*entry
 amended bool // true if the dirty map contains some key not in m.
}

3.1 Load方法

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()
 //加锁,然后再读取一遍read map中内容,主要防止在加锁的过程中,dirty map转换成read map,从而导致读取不到数据.
 read, _ = m.read.Load().(readOnly)
 e, ok = read.m[key]
 if !ok && read.amended {
 e, ok = m.dirty[key]
 //记录miss数, 在dirty map提升为read map之前,
 //这个key值都必须在加锁的情况下在dirty map中读取到.
 m.missLocked()
 }
 m.mu.Unlock()
 }
 if !ok {
 return nil, false
 }
 return e.load()
}

3.2 Store方法

// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
 //如果在read map读取到值,则尝试使用原子操作直接对值进行更新,更新成功则返回
 read, _ := m.read.Load().(readOnly)
 if e, ok := read.m[key]; ok && e.tryStore(&value) {
 return
 }
 //如果未在read map中读取到值或读取到值进行更新时更新失败,则加锁进行后续处理
 m.mu.Lock()
 read, _ = m.read.Load().(readOnly)
 if e, ok := read.m[key]; ok {
 //在检查一遍read,如果读取到的值处于删除状态,将值写入dirty map中
 if e.unexpungeLocked() {
 m.dirty[key] = e
 }
 //使用原子操作更新key对应的值
 e.storeLocked(&value)
 } else if e, ok := m.dirty[key]; ok {
 //如果在dirty map中读取到值,则直接使用原子操作更新值
 e.storeLocked(&value)
 } else {
 //如果dirty map中不含有值,则说明dirty map已经升级为read map,或者第一次进入
 //需要初始化dirty map,并将read map的key添加到新创建的dirty map中.
 if !read.amended {
 m.dirtyLocked()
 m.read.Store(readOnly{m: read.m, amended: true})
 }
 m.dirty[key] = newEntry(value)
 }
 m.mu.Unlock()
}

3.3 LoadOrStore方法

代码逻辑和Store类似

func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
 // 不加锁的情况下读取read map
 read, _ := m.read.Load().(readOnly)
 if e, ok := read.m[key]; ok {
 //如果读取到值则尝试对值进行更新或读取
 actual, loaded, ok := e.tryLoadOrStore(value)
 if ok {
 return actual, loaded
 }
 }
 m.mu.Lock()
 read, _ = m.read.Load().(readOnly)
 // 在加锁的请求下在确定一次read map
 if e, ok := read.m[key]; ok {
 if e.unexpungeLocked() {
 m.dirty[key] = e
 }
 actual, loaded, _ = e.tryLoadOrStore(value)
 } else if e, ok := m.dirty[key]; ok {
 actual, loaded, _ = e.tryLoadOrStore(value)
 m.missLocked()
 } else {
 if !read.amended {
 m.dirtyLocked()
 m.read.Store(readOnly{m: read.m, amended: true})
 }
 m.dirty[key] = newEntry(value)
 actual, loaded = value, false
 }
 m.mu.Unlock()
 return actual, loaded
}

3.4 Range 方法

func (m *Map) Range(f func(key, value interface{}) bool) {
 //先获取read map中值
 read, _ := m.read.Load().(readOnly)
 //如果dirty map中还有值,则进行加锁检测
 if read.amended {
 m.mu.Lock()
 read, _ = m.read.Load().(readOnly)
 
 if read.amended {
 //将dirty map中赋给read,因为dirty map包含了所有的值
 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
 }
 }
}

3.5 Delete 方法

func (m *Map) Delete(key interface{}) {
 //首先获取read map
 read, _ := m.read.Load().(readOnly)
 e, ok := read.m[key]
 if !ok && read.amended {
 m.mu.Lock()
 //加锁二次检测
 read, _ = m.read.Load().(readOnly)
 e, ok = read.m[key]
 //没有在read map中获取到值,到dirty map中删除
 if !ok && read.amended {
 delete(m.dirty, key)
 }
 m.mu.Unlock()
 }
 if ok {
 e.delete()
 }
}

4. 局限性

从以上的源码可知,sync.map并不适合同时存在大量读写的场景,大量的写会导致read map读取不到数据从而加锁进行进一步读取,同时dirty map不断升级为read map.
从而导致整体性能较低,特别是针对cache场景.针对append-only以及大量读,少量写场景使用sync.map则相对比较合适.

对于map,还有一种基于hash的实现思路,具体就是对map加读写锁,但是分配n个map,根据对key做hash运算确定是分配到哪个map中.
这样锁的消耗就降到了1/n(理论值).具体实现可见:https://github.com/orcaman/co...

相比之下, 基于hash的方式更容易理解,整体性能较稳定. sync.map在某些场景性能可能差一些,但某些场景却能取得更好的效果.
所以还是要根据具体的业务场景进行取舍.

5. 参考

https://golang.org/doc/faq#at...
https://github.com/golang/go/...

本文来自:Segmentfault

感谢作者:沐风

查看原文:go sync.Map源码分析

• 编辑
• 预览