map是不支持并发操作的,当出现并发操作的时候map会抛出”concurrent map writes”异常。golang提供了一个支持并发操作的map–sync.Map。
一、原理
为了减少并发抢锁导致的阻塞,sync.Map分出了read和dirty两个map,里面存的都是指针。存、删和查都先操作read,并用atomic进行并发保护,速度较快,直到read不能满足需求才去操作dirty,操作dirty的时用Mutex锁进行并发保护,速度较慢。
二、结构
1 | type Map struct { |
- mu 互斥锁,在操作dirty的时候使用
- read 优先读map,通过原子操作保证并发安全,他的实际结构为下面要说明的readOnly。
- dirty dirty是当前最新的map数据,加锁进行操作。当misses达到len(dirty)后会复制至read。
- misses 未命中read的次数。
1 | type readOnly struct { |
readOnly 主要用于存储,通过原子操作存储在Map.read中元素。
- m 存放实际的元素
- amended 如果数据在dirty中但没有在read中,该值为true,作为修改标识、
1
2
3
4type entry struct {
p unsafe.Pointer
} - p 用于保存value的interface指针,通过atomic进行原子操作
三、主要原理
sync.Map的原理很简单,使用了空间换时间策略,通过冗余的两个数据结构(read、dirty),实现加锁对性能的影响。通过引入两个map将读写分离到不同的map,其中read map提供并发读和已存元素原子写,而dirty map则负责读写。 这样read map就可以在不加锁的情况下进行并发读取,当read map中没有读取到值时,再加锁进行后续读取,并累加未命中数,当未命中数大于等于dirty map长度,将dirty map上升为read map。从之前的结构体的定义可以发现,虽然引入了两个map,但是底层数据存储的是指针,指向的是同一可空间。
四、主要方法
- func (m *Map) Load(key interface{}) (value interface{}, ok bool)
获取数据 - func (m *Map) Store(key, value interface{})
存储数据 - func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool)
获取数据如果没有命中则存储数据 - func (m *Map) Delete(key interface{})
删除数据 - func (m *Map) Range(f func(key, value interface{}) bool)
遍历数据
五、主要方法理解
1、Load
1 | func (m *Map) Load(key interface{}) (value interface{}, ok bool) { |
Load方法使用起来同value, ok := map[key]方式类似。获取是先从read中获取,如果没有命中,则对mu进行加锁并再次从read中获取。如果依然没有命中则会从dirty中获取。如果dirty中命则会执行missLock操作。
1 | func (m *Map) missLocked() { |
missLocked会对misses自增,当misses小于len(dirty)时返回,当misses达到len(dirty)时会将dirty中的数据复制到read中。清空dirty、misses数据。复制过程通过CAS操作保证原子性,因为复制的是指针类型的值所以开销不是很大。
2、Store
1 | func (m *Map) Store(key, value interface{}) { |
首先会先从read中获取目标key对应的值,如果命中则会尝试向read中存储,如果这个entry没有被抹除则以CAS方式进行存储,若果这个entry抹除则尝试存储失败。
read存在并已被标记删除时,标记成未被删除。dirty中不存在这个键,所以加入dirty。更新这个键对应的值。
如果dirty存在这个键时,则更新这个键对应的值。
key不在read里面,也不在dirty里面时。amended若为false,则表示dirty未被初始化过。初始化dirty,将read中未被删除的数据全都复制到dirty中,read中指向nil的数据才会被标记为expunged。
将amended改为true。
将值存入dirty。
这个对dirty的操作是在锁保护中进行。
3、LoadOrStore
1 | func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) { |
LoadOrStore整个过程和Store类似,当read没有命中,dirty命中的情况会进行一次missLocked。
4、Delete
1 | func (m *Map) Delete(key interface{}) { |
不在read中,且dirty中有新数据。
直接删除dirty的数据。
read中存在key,将这个key标记为删除状态(nil)。
5、Range
1 | func (m *Map) Range(f func(key, value interface{}) bool) { |
遍历相对简单些,先判断amended,是否有数据在dirty没有在read中如果是的话将dirty的数据迁到read中。
最后遍历read。