sync.Map源码分析

chasiny · · 339 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

## [博客地址:sync.Map源码分析](https://github.com/Chasiny/Blog/blob/master/blog/go/sync.Map%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90.md) ## 普通的map go普通的map是不支持并发的,例如简单的写 ```go func main() { wg := sync.WaitGroup{} wg.Add(10) m := make(map[int]int) for i := 0; i < 10; i++ { go func(i int) { m[i] = i wg.Done() }(i) } wg.Wait() } ``` ```bash fatal error: concurrent map writes ``` ## sync.Map go的sync.Map几个优化点 * 通过使用优先读的结构体read减少锁的冲突 * 使用双重检测 * 使用延迟删除(删除存在于read中的数据只是将其置为nil) * 动态调整,miss次数多了之后,将dirty数据提升为read 从sync/map.go看Map的结构体 ```go type Map struct { mu Mutex //互斥锁,用于锁定dirty map read atomic.Value //读map,实际上不是只读,是优先读 dirty map[interface{}]*entry //dirty是一个当前最新的map,允许读写 misses int //标记在read中没有命中的次数,当misses等于dirty的长度时,会将dirty复制到read } //read存储的实际结构体 type readOnly struct { m map[interface{}]*entry //map amended bool //如果有些数据在dirty中但没有在read中,该值为true } type entry struct { p unsafe.Pointer //数据指针 } ``` ### entry的几种类型 * nil: 表示为被删除,此时read跟dirty同时有该键(一般该键值如果存在于read中,则删除是将其标记为nil) * expunged: 也是表示被删除,但是该键只在read而没有在dirty中,这种情况出现在将read复制到dirty中,即复制的过程会先将nil标记为expunged,然后不将其复制到dirty * 其他: 表示存着真正的数据 ## sync.Map几种方法: 首先先说明read跟dirty不是直接存对象,而是存指针,这样的话如果键值同时存在在read跟dirty中,直接原子修改read也相当于修改dirty中的值,并且当read跟dirty存在大量相同的数据时,也不会使用太多的内存 ### Load ```go func (m *Map) Load(key interface{}) (value interface{}, ok bool) { read, _ := m.read.Load().(readOnly) e, ok := read.m[key] if !ok && read.amended { //如果不在read中,并且dirty有新数据,则从dirty拿 m.mu.Lock() //双重检查,因为有可能在加锁前read刚好插入该值 read, _ = m.read.Load().(readOnly) e, ok = read.m[key] if !ok && read.amended { //没有在read中,则从dirty拿 e, ok = m.dirty[key] m.missLocked() } m.mu.Unlock() } if !ok { return nil, false } return e.load() } func (m *Map) missLocked() { //没有命中的计数加一 m.misses++ if m.misses < len(m.dirty) { return } //当没有命中的次数等于dirty的大小,将dirty复制给read m.read.Store(readOnly{m: m.dirty}) m.dirty = nil m.misses = 0 } ``` read主要用于读取,每次Load都先从read读取,当read中不存在且amended为true,就从dirty读取数据 无论dirty是否存在该key,都会执行missLocked函数,该函数将misses+1,当misses等于dirty的大小时,便会将dirty复制到read,此时再将dirty置为nil ### Delete ```go func (m *Map) Delete(key interface{}) { read, _ := m.read.Load().(readOnly) e, ok := read.m[key] if !ok && read.amended { //如果不在read中,并且dirty有新数据,则从dirty中找 m.mu.Lock() //双重检查 read, _ = m.read.Load().(readOnly) e, ok = read.m[key] if !ok && read.amended { //这是表示键值只存在于dirty,直接删除dirty中的键值即可 delete(m.dirty, key) } m.mu.Unlock() } if ok { //如果在read中,则将其标记为删除(nil) e.delete() } } func (e *entry) delete() (hadValue bool) { for { p := atomic.LoadPointer(&e.p) if p == nil || p == expunged { return false } if atomic.CompareAndSwapPointer(&e.p, p, nil) { return true } } } ``` 先判断是否在read中,不在的话再从dirty删除 ### Store ```go func (m *Map) Store(key, value interface{}) { //如果read存在这个键,并且这个entry没有被标记删除,尝试直接写入 //dirty也指向这个entry,所以修改e也可以使dirty也保持最新的entry 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 { //该键值存在在read中 if e.unexpungeLocked() { //该键值在read中被标记为抹除,则将其添加到dirty m.dirty[key] = e } //更新entry e.storeLocked(&value) } else if e, ok := m.dirty[key]; ok { //如果不在read中,在dirty中,则更新 e.storeLocked(&value) } else { //既不在read中,也不在dirty中 if !read.amended { //从read复制没有标记删除的数据到dirty中 m.dirtyLocked() m.read.Store(readOnly{m: read.m, amended: true}) } //添加到dirty中 m.dirty[key] = newEntry(value) } m.mu.Unlock() } func (e *entry) tryStore(i *interface{}) bool { p := atomic.LoadPointer(&e.p) if p == expunged { return false } for { if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) { return true } p = atomic.LoadPointer(&e.p) if p == expunged { return false } } } func (e *entry) unexpungeLocked() (wasExpunged bool) { return atomic.CompareAndSwapPointer(&e.p, expunged, nil) } func (e *entry) storeLocked(i *interface{}) { atomic.StorePointer(&e.p, unsafe.Pointer(i)) } func (m *Map) dirtyLocked() { if m.dirty != nil { return } //从read复制到dirty read, _ := m.read.Load().(readOnly) m.dirty = make(map[interface{}]*entry, len(read.m)) for k, e := range read.m { //如果标记为nil或者expunged,则不复制到dirty 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 } ``` sync.Map 写入就稍微麻烦很多了 1. 首先会先判断键值是否已经存在read中,存在的话便尝试直接写入(read不只是读,此时被写入),由于从read获取的是entry指针,因此对从read读取entry进行修改便相当于修改dirty中对应的entry,此时写入的是使用原子操作。 2. 键值存在在read中并且该entry被标记为expunged(这种情况出现在从read复制数据到dirty中,看tryExpungeLocked函数,将所有键为nil置为expunged,表示该键被删除,但没有在dirty中) 3. 从read复制到dirty的过程来说,主要是用dirtyLocked函数实现的,复制除了entry为nil跟expunged的数据 --- 参考 * [Go sync.Map](https://github.com/golang/go/blob/master/src/sync/map.go) * [Go 1.9 sync.Map揭秘](http://colobu.com/2017/07/11/dive-into-sync-Map/)

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

339 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传