go sync.Map源码分析

5,076 阅读6分钟

概述

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(理论值).具体实现可见:concurrent-map

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

5. 参考

go
sync.map