普通map的实现不是并发安全,并发读写会painc
思想:读写分离,以空间换时间,动态调整
用法
1 | func Test_sync_map(t *testing.T) { |
数据结构
思路,类似缓存机制
sync.map:空间换时间,一个 map 只读(无锁化),一个 map 读写(上锁)
得到 misses 阈值会进行 read map 和 dirty map 的更新轮换
entry
1 | type entry struct { |
三种状态
1 存活态:正常指向元素
2 软删除态:nil
3 硬删除态:指向expunged
如果key value 被软删除,dirty仍然存在,如果再插入,可以不用加锁,借助CAS(Compare And Swap比较交换,是一种无锁原子算法)
如果key value 被硬删除,则需要加锁
readOnly
如果amended为false,说明可以直接用
否则访问dirty兜底
读流程
写流程
如果amended 是false
dirtyLocked,
因为entry是指针,readOnly和dirty,所以修改是同步的
missLock 把更新的数据覆盖到read,同时dirty置nil O(1)
dirtyLock 把read的数据拷贝回dirty(把被删除的屏蔽掉)O(n)
dirty 一定不存在硬删除态
希望dirtyLock尽可能少
missLock -> store全新的key value对 ->dirtyLock,写(插入)多读少
删流程
在dirty会做物理意义上的删除
而read只会做软删除
misscnt也会在删除累加
遍历流程
软硬删除
为什么用 expunged 标识硬删除态
软删除:key-value仍存在,nil,插入CAS操作,无需加锁
硬删除:只会在dirtyLock出现,一定不会在dirty map存在。要保证dirty比read全
数据流转
d->r big O(1),因为要遍历除掉硬删除和软删除
r->d O(n)
总结
- 适用于读多、更新多、删除多、插入少的场景
- 若插入次数太多,sync.Map等价于互斥锁+map
- sync.Map可能存在性能抖动问题,在读/删流程miss readOnly 次数过多时(触发missLocked 流程),下一次插入操作的过程中(dirtyLocked流程)
参考
1 Golang sync.Map 实现原理
2 syncmap package - golang.org/x/sync/syncmap - Go Packages