我们都知道map是不并发安全的,通常通过加互斥锁或读写锁进行并发,而官方提供了一个解决方案sync.Map。适用于读多写少的场景,那么它的内部也是通过加锁控制的吗?
一、写时复制(COW)
在Linux程序中,fork()会产生一个和父进程完全相同的子进程,但子进程在此后多会exec系统调用,出于效率考虑,linux中引入了“写时复制“技术,也就是只有进程空间的各段的内容要发生变化时,才会将父进程的内容复制一份给子进程。
写时复制技术:内核只为新生成的子进程创建虚拟空间结构,它们来复制于父进程的虚拟究竟结构,但是不为这些段分配物理内存,它们共享父进程的物理空间,当父子进程中有更改相应段的行为发生时,再为子进程相应的段分配物理空间。
其实我们之前已经见过这种方式了,就是 ,底层赋值是直接用指针替代的。
二、并发安全
1、常用的几种并发安全的map
实现方式 | 原理 | 常用场景 |
map+互斥锁 | 通过Mutex互斥锁来实现map的串行访问 | 读写都需要加锁,适用于读写比较接近的场景 |
map+读写锁 | 通过RWMutex读写锁对map读写加锁,使并发读性能提高 | 读多写少的场景 |
sync.Map | 底层通过读写分离来实现读的无锁 | 读多写少的场景 |
因为go没有泛型,所以使用interface{}能匹配所有数据。
sync.Map对以下两种常用场景进行了优化:
- entry只写一次但是读很多次,比如只增长的缓存
- 多个goroutine在读写entry,互不干扰
在这两种情况下,使用sync.Map比单独使用互斥锁或读写锁的map好。
2、数据结构
type Map struct {
mu Mutex
read atomic.Value // readOnly
dirty map[interface{}]*entry
misses int
}
- 当涉及到脏数据时,需要用到锁
- read中包含了map内容中对并发访问是安全的部分,存储在read中的entry可以在没有锁的情况下并发更新,但是更新前删除的entry需要将entry复制给dirty,并保证不被删除。
- ditry包含了部分键值对,而dirty中的元素最终都会被赋值给read
- misses就是计数器,用于记录read中没有而在dirty中存在的数量,当misses=len(dirty),那么就会把dirty迁移到read中。
而read的指针指向的是readOnly结构体
type readOnly struct {
m map[interface{}]*entry
amended bool
}
这个amended是个标志位,如果为ture表明当前read只读数据m不完整,dirty中包含部分数据。
entry其实就是个指针,有以下几种情况:
- nil:entry被删除,并且m.dirty为空
- expunged:entry被删除,但m.dirty不为空,也不在m.dirty中
- 其他:正常值,指向了interface{}值,并记录在m.read.m[key]中
三、操作
1、查找
1.1、无锁读
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
if !ok {
return nil, false
}
优先从read的map中查找,如果没有找到就是不存在。此时从read中读取是不加锁的,是不影响性能的。
1.2、读写分离
if !ok && read.amended {
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if !ok && read.amended {
e, ok = m.dirty[key]
m.missLocked()
}
m.mu.Unlock()
}
如果没有找到,并且标识dirty中存在数据,那么就要从dirty中查找,而在dirty操作时是需要加锁的。
这里有一点要特别注意,在加锁后,重新判断了一个read,这个是 二次检查 ,防止在加锁之前,dirty已经迁移到read中。
在进入dirty查找时,不管有没有找到,都要使misses+1,因为去dirty查找了一次。
如果misses大于dirty的长度,那么就开始迁移dirty的数据到read中。
2、新增/更新
2.1、更新
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}
先读取read,如果存在key,就尝试更新。这一步也是不加锁的
2.2、新增
如果不存在,那就要新增key了。新增这一步就需要加锁了
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
if e.unexpungeLocked() {
m.dirty[key] = e
}
e.storeLocked(&value)
} else if e, ok := m.dirty[key]; ok {
e.storeLocked(&value)
} else {
if !read.amended {
m.dirtyLocked()
m.read.Store(readOnly{m: read.m, amended: true})
}
m.dirty[key] = newEntry(value)
}
而这里对应着以下场景
- 如果在read中,而key对应的value标识是已删除,那么先去dirty中添加,然后再更新
- 如果不在read中,在dirty中,直接更新值
- 如果都不存在,那么就把数据存在dirty中,然后修改read中的标志位。如果此时dirty没有数据,那么就从read中复制数据,并把标识为删除的数据清除。
这里在dirty写数据,不影响read中读取的数据,可以保证读取read的时候并发安全。
3、删除
看到这里,应该很容易推理出删除的逻辑
1、从read中查找key是否存在,如果不存在但是标志位显示dirty中有新数据,那么就加锁去dirty中查看,然后清除key。
2、如果真不存在,就结束
3、如果存在read中,就将entry置nil
其他几种方法,如LoadOrStore,Range就很容易知道是如何实现的了。
四、生命周期
以上,我们就能分析出key的生命周期
1、新增操作,将key保存在dirty中,并且标识read数据不完整
2、查询操作,在dirty中找到了key,并且满足迁移的条件,将dirty移到read中,修改标识,read数据完整
3、查询操作,直接在read中查询到key了
4、更新操作,直接在read中更新key
5、删除操作,把key对应的value置为nil
6、新增其他的key1,触发迁移条件,将read的数据复制到dirty中,此时key对应的value==nil,被修改为expunged,并且不添加到dirty中。
7、在下一次满足将dirty迁移到read中,就会将这个不存在的key删除
五、总结
1、空间换时间:通过两个冗余的数据结构(read,dirty),减少锁对性能的影响
2、读操作尽量在read中进行,避免读写冲突
3、命中到dirty累加misses的值,当超出限制时,迁移dirty,避免dirty数据过多
4、二次检查,避免在非原子操作时产生数据错误
5、延迟删除,删除一个键值对只是打了个标签,只有在迁移到read中才清除删除的数据
6、优先从read中读、改和删除,因为对read的操作不用加锁,大大提升性能