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