sync.Map原理

普通map的实现不是并发安全,并发读写会painc

思想:读写分离,以空间换时间,动态调整

用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func Test_sync_map(t *testing.T) {  
var smp sync.Map
smp.Store("a", "111111")
smp.Store("b", "222")
smp.Store("c", "222")
smp.Store("d", "222")

// load
v, ok := smp.Load("a")

if !ok {
t.Error("a not exist")
return
}
str, _ := v.(string)
smp.Range(func(key, value any) bool {
t.Logf("key:%v value:%v", key, value)
return key != "c"
})
t.Log(str)
}

数据结构

思路,类似缓存机制
sync.map:空间换时间,一个 map 只读(无锁化),一个 map 读写(上锁)
得到 misses 阈值会进行 read map 和 dirty map 的更新轮换

entry

1
2
3
type entry struct { 
p atomic.Pointer[any]
}

三种状态
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