golang并发安全-sync.map
sync.map解决的问题
golang 原生map是存在并发读写的问题，在并发读写时候会抛出异常
func main() {mT := make(map[int]int)g1 := []int{1, 2, 3, 4, 5, 6}g2 := []int{4, 5, 6, 7, 8, 9}go func() {for i := range g1 {mT[i] = i}}()go func() {for i := range g2 {mT[i] = i}}()time.Sleep(3 * time.Second)
}
抛出异常 fatal error: concurrent map writes
如果将map换成sync.map 那么就不会出现这个问题，下面就简单说说syn.map怎么实现的
基本结构
Map结构体
// Map类型针对两种常见的用例进行了优化：1-当给定键的条目只写一次但读多次时，如在只增长的缓存中，2-当多个goroutine读取、写入和覆盖不相交的键集的条目时。在这两种情况下，与单独的Mutex或RWMutex配对的Go映射相比，使用Map可以显著减少锁争用。
type Map struct { // 互斥锁mu，操作dirty需先获取mu mu Mutex // read是只读的数据结构，可安全并发访问部分，访问它无须加锁，sync.map的所有操作都优先读read // read中存储结构体readOnly，readOnly中存着真实数据，储存数据时候需要加锁// read中可能会存在脏数据：即entry被标记为已删除read atomic.Value // readOnly// dirty是可以同时读写的数据结构，访问它要加锁，新添加的key都会先放到dirty中 // dirty == nil的情况：// 1.被初始化 // 2.提升为read后，但它不能一直为nil，否则read和dirty会数据不一致。 // 当有新key来时，会用read中的数据(不是read中的全部数据，而是未被标记为已删除的数据，)填充dirty // dirty != nil时它存着sync.map的全部数据（包括read中未被标记为已删除的数据和新来的数据）dirty map[interface{}]*entry // 统计访问read没有未命中然后穿透访问dirty的次数 // 若miss等于dirty的长度，dirty会提升成read，提升后可以增加read的命中率，减少加锁访问dirty的次数 misses int
}readOnly结构体
//第一点的结构read存的就是readOnly
type readOnly struct {m map[any]*entry //m是一个map，key是interface，value是指针entry，其指向真实数据的地址，amended bool // amended等于true代表dirty中有readOnly.m中不存在的entry。
}
entry结构体
type entry struct { // p:// expunged: 删除； nil: 逻辑删除但存在dirty; 数据 p unsafe.Pointer // *interface{}
}
Load方法
代码解说
Load：读取数据
// Load 返回 map 中key 对应的值，如果没有值，则返回 nil。
// ok 结果表示是否在 map 中找到了 value。
func (m *Map) Load(key any) (value any, ok bool) {read, _ := m.read.Load().(readOnly) // 从read 读取数据，并转换readonlye, ok := read.m[key]if !ok && read.amended { // readonly没有找到对应数据m.mu.Lock()// 双重检测:// 再检查一次readonly，以防中间有Map.dirty被替换为readonlyread, _ = m.read.Load().(readOnly)e, ok = read.m[key]if !ok && read.amended { // 去 dirty查找对应数据e, ok = m.dirty[key]// 无论Map.dirty中是否有这个key，miss都加一，// 若miss大小等于dirty的长度，dirty中的元素会被加到Map.read中 m.missLocked()}m.mu.Unlock()}if !ok {return nil, false}return e.load()// 若entry.p被删除（等于nil或expunged）返回nil和不存在（false），否则返回对应的值和存在（true）
}missLocked：dirty是如何提升为read
func (m *Map) missLocked() {m.misses++ // 每次misses+1if m.misses < len(m.dirty) {return}// 当misses等于dirty的长度，m.dirty转换readOnly，amended被默认赋值成false m.read.Store(readOnly{m: m.dirty})m.dirty = nilm.misses = 0
}流程图
load： 会先从readOnly查找数据, 如果没有开启加锁，再次访问readOnly, 再次没有再去dirty去查。
Store方法
代码解说
store： 赋值
// Store 设置key value
func (m *Map) Store(key, value any) {read, _ := m.read.Load().(readOnly) // 转换readOnly// 若key在readOnly.m中且 e.tryStore 不为 false（没有逻辑删除）if e, ok := read.m[key]; ok && e.tryStore(&value) {return}m.mu.Lock()// 双重检测:// 再检查一次readonly，以防中间有Map.dirty被替换为readonlyread, _ = m.read.Load().(readOnly)if e, ok := read.m[key]; ok {// entry.p状态是expunged置为nil// 如果是逻辑删除就需要清除标记了if e.unexpungeLocked() {// 之前dirty中没有此key，所以往dirty中添加此key m.dirty[key] = e}// cas: 赋值e.storeLocked(&value)} else if e, ok := m.dirty[key]; ok {e.storeLocked(&value)} else {// dirty中没有新数据，往dirty中添加第一个新key if !read.amended {// 把readOnly中未标记为删除的数据拷贝到dirty中 m.dirtyLocked()// amended:true，现在dirty有readOnly中没有的key m.read.Store(readOnly{m: read.m, amended: true})}m.dirty[key] = newEntry(value)}m.mu.Unlock()
}tryStore：尝试写入数据
func (e *entry) tryStore(i *any) bool {for { p := atomic.LoadPointer(&e.p) if p == expunged { // 如果逻辑删除就返回false return false } // 不是就将value写入if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) { return true } }
}
dirtyLocked： 将readOnly 未删除的放到dirty
func (m *Map) dirtyLocked() { if m.dirty != nil { return } // dirty为nil时，把readOnly中没被标记成删除的entry添加到dirty read, _ := m.read.Load().(readOnly) m.dirty = make(map[interface{}]*entry, len(read.m)) for k, e := range read.m { // tryExpungeLocked函数在entry未被删除时返回false，反之返回true if !e.tryExpungeLocked() { // entry没被删除 m.dirty[k] = e } }
}流程图
sync.map不适合用于频繁插入新key-value的场景，因为此操作会频繁加锁访问dirty会导致性能下降。更新操作在key存在于readOnly中且值没有被标记为删除(expunged)的场景下会用无锁操作CAS进行性能优化，否则也会加锁访问dirty。
Delete方法
代码解说
LoadAndDelete：查找删除
func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {read, _ := m.read.Load().(readOnly) e, ok := read.m[key]if !ok && read.amended { // readOnly不存在此key，但dirty中可能存在 // 加锁访问dirty m.mu.Lock() // 双重检测 read, _ = m.read.Load().(readOnly) e, ok = read.m[key] // readOnly不存在此key，但是dirty中可能存在 if !ok && read.amended { e, ok = m.dirty[key] delete(m.dirty, key) m.missLocked() // 判断dirty是否可以转换readOnly，可以就转换} m.mu.Unlock() } if ok { // 如果entry.p不为nil或者expunged，则把逻辑删除（标记为nil） return e.delete() } return nil, false
}delete：逻辑删除
func (e *entry) delete() (value any, ok bool) {for {p := atomic.LoadPointer(&e.p)if p == nil || p == expunged { // 已经处理或者不存在return nil, false}if atomic.CompareAndSwapPointer(&e.p, p, nil) { // 逻辑删除return *(*any)(p), true}}
}流程图
Range方法
代码解说
Range：轮训元素
func (m *Map) Range(f func(key, value any) bool) {read, _ := m.read.Load().(readOnly) if read.amended { // 如果dirty存在数据m.mu.Lock() // 双重检测 read, _ = m.read.Load().(readOnly) if read.amended { // readOnly.amended被默认赋值成false read = readOnly{m: m.dirty} m.read.Store(read) m.dirty = nil m.misses = 0 } m.mu.Unlock() } // 遍历readOnly.m for k, e := range read.m { v, ok := e.load() if !ok { continue } if !f(k, v) { break } }
}流程图
Range：全部key都存在于readOnly中时，是无锁遍历的，性能最优。如果readOnly只存在Map中的部分key时，会一次性加锁拷贝dirty的元素到readOnly，减少多次加锁访问dirty中的数据。
总结
1- sync.map 结构体加了readOnly 和 dirty 来实现读写分离，load，store, delete，range 每次都会优先访问read，后面访问dirty都会双重检测以防加锁前Map.dirty可能已被提升为read
2- sync.map不适合写多读少，从store 代码中可以看出会频繁加锁访问dirty，双重检测等等，这些都会导致性能下降
3- sync.map 没有提供对read， dirty 的长度方法，这个对象使用在于并发场景下，会额外带来锁竞争的问题
4- misses 是 统计访问read没有未命中然后穿透访问dirty的次数 ，如果等于dirty会转换readOnly
5- entry 有三种类型 expunged: 删除； nil: 逻辑删除但存在dirty; 数据 。其中expunged 会在 unexpungeLocked 方法中进行赋值（在store时候会加锁访问dirty，把readOnly中的未被标记为删除的所有entry指针放到dirty，之前被delete方法标记为删除状态的entry=nil都变为expunged，那这些被标记为expunged的entry将不会出现在dirty中。）