前言
在并发编程中,我们经常会遇到多个goroutine同时操作一个map的情况。如果在这种情况下直接使用普通的map,那么就可能会引发竞态条件,造成数据不一致或者更严重的问题。
sync.Map
是Go语言中内置的一种并发安全的map,但是他的实现和用法与普通的map完全不同,这篇文章将详细介绍这些区别。
一、使用方法
创建sync.Map
非常简单,只需要声明即可:
var m sync.Map
使用Store
方法存储键值对:
m.Store("hello", "world")
使用Load
方法获取值:
value, ok := m.Load("hello") if ok { fmt.Println(value) // 输出:world }
使用Delete
方法删除键值对:
m.Delete("hello")
二、原理
sync.Map
的核心实现依赖于两个主要的数据结构:一个只读的read
字段,以及一个可写的dirty
字段。
读操作:
当我们进行读取操作(Load
)时,首先会尝试从read
字段读取数据,这个过程是完全无锁的。
如果read
中没有找到,那么会尝试加锁后从dirty
中读取。这个设计保证了在大部分读多写少的场景下,读操作是无锁的,大大提升了性能。
写操作:
写入操作(key不存在
)时,会直接在dirty
中进行写入,并将read
的amended
标记为true
,表示read
字段有待更新的数据。
然后再有新的读取操作到来时,如果amended
为true并且miss数量超过dirty长度
,则会从dirty
中拷贝数据到read
,并清除amended
标记。
总结:
在这个设计中,读操作在大部分情况下是无锁的,而写操作(key不存在时)则需要获取dirty
的锁,从而实现了对于读多写少场景的优化。
三、优点
sync.Map
在以下两种情况下表现得特别好:
- 键值对的数量相对稳定,读操作明显多于写操作的场景
- 多个goroutine并发读取不重叠的键集的场景
这是因为sync.Map
的设计将读取操作优化至极致,同时尽量减少在写入新键值对时的锁竞争。
四、缺点
然而,sync.Map
并不是银弹,也有一些局限:
-
sync.Map
没有像普通map那样的直观语法,必须使用特定的方法来操作键值对 - 对于键值对数量快速增长、写操作频繁的场景,
sync.Map
的性能可能不如使用普通map加锁的方式 - 读操作无锁情况下,可能会出现时间竞态问题
五、实现
sync.Map
type Map struct { mu Mutex // read contains the portion of the map's contents that are safe for // concurrent access (with or without mu held). read atomic.Pointer[readOnly] // dirty contains the portion of the map's contents that require mu to be // held. To ensure that the dirty map can be promoted to the read map quickly, // it also includes all of the non-expunged entries in the read map. dirty map[any]*entry // misses counts the number of loads since the read map was last updated that // needed to lock mu to determine whether the key was present. misses int }
readonly
// readOnly is an immutable struct stored atomically in the Map.read field. type readOnly struct { m map[any]*entry amended bool // true if the dirty map contains some key not in m. }
entry
// An entry is a slot in the map corresponding to a particular key. type entry struct { // p points to the interface{} value stored for the entry. p atomic.Pointer[any] }
expunged
// expunged is an arbitrary pointer that marks entries which have been deleted // from the dirty map. var expunged = new(any)
状态机:
总结:
- 当key从read中删除时,会先被标记为nil,不会立马删除key
- 当重新初始化dirty时(将read.m克隆到dirty),如果key的值为nil,会设置为expunged,并不在dirty中创建这个key。
- 如果key为expunged,LoadOrStore/Swap/CompareAndDelete/CompareAndSwap都会不执行写操作并返回false。
Load
// Load returns the value stored in the map for a key, or nil if no // value is present. // The ok result indicates whether value was found in the map. func (m *Map) Load(key any) (value any, ok bool) { read := m.loadReadOnly() e, ok := read.m[key] if !ok && read.amended { m.mu.Lock() // Avoid reporting a spurious miss if m.dirty got promoted while we were // blocked on m.mu. (If further loads of the same key will not miss, it's // not worth copying the dirty map for this key.) read = m.loadReadOnly() e, ok = read.m[key] if !ok && read.amended { e, ok = m.dirty[key] // Regardless of whether the entry was present, record a miss: this key // will take the slow path until the dirty map is promoted to the read // map. m.missLocked() } m.mu.Unlock() } if !ok { return nil, false } return e.load() } func (m *Map) loadReadOnly() readOnly { if p := m.read.Load(); p != nil { return *p } return readOnly{} }
总结:
- 如果查询的key在read中找到了,返回entry.load()
- 如果查询的key在read中未找到,并且read和dirty一致,返回nil, false
- key未找到,并且read与dirty不一致
- 加锁
- 重新查询read,类似上面1、2流程,如果未找到并且read和dirty不一致则继续
- 在dirty中查询
- misses加一
- 如果misses数大于dirty长度,将dirty同步到read,重置dirty和misses
- 释放锁
- 返回结果
LoadOrStore
// LoadOrStore returns the existing value for the key if present. // Otherwise, it stores and returns the given value. // The loaded result is true if the value was loaded, false if stored. func (m *Map) LoadOrStore(key, value any) (actual any, loaded bool) { // Avoid locking if it's a clean hit. read := m.loadReadOnly() if e, ok := read.m[key]; ok { actual, loaded, ok := e.tryLoadOrStore(value) if ok { return actual, loaded } } m.mu.Lock() read = m.loadReadOnly() if e, ok := read.m[key]; ok { if e.unexpungeLocked() { m.dirty[key] = e } actual, loaded, _ = e.tryLoadOrStore(value) } else if e, ok := m.dirty[key]; ok { actual, loaded, _ = e.tryLoadOrStore(value) m.missLocked() } else { if !read.amended { // We're adding the first new key to the dirty map. // Make sure it is allocated and mark the read-only map as incomplete. m.dirtyLocked() m.read.Store(&readOnly{m: read.m, amended: true}) } m.dirty[key] = newEntry(value) actual, loaded = value, false } m.mu.Unlock() return actual, loaded } // tryLoadOrStore atomically loads or stores a value if the entry is not // expunged. // // If the entry is expunged, tryLoadOrStore leaves the entry unchanged and // returns with ok==false. func (e *entry) tryLoadOrStore(i any) (actual any, loaded, ok bool) { p := e.p.Load() if p == expunged { return nil, false, false } if p != nil { return *p, true, true } // Copy the interface after the first load to make this method more amenable // to escape analysis: if we hit the "load" path or the entry is expunged, we // shouldn't bother heap-allocating. ic := i for { if e.p.CompareAndSwap(nil, &ic) { return i, false, true } p = e.p.Load() if p == expunged { return nil, false, false } if p != nil { return *p, true, true } } }
总结:
- 如果key在read中找到了,并且不为expunged
- 如果为nil,则CAS新的值,并返回value, false
- 如果不为nil,则返回*p, true
- 如果key在read中不存在,或者为expunged
- 加锁
- 再次在read中查找,如果找到了
- 如果为expunged,结果为nil, false
- 如果为nil,则CAS新的值,结果为value, false
- 如果不为nil,结果为*p, true
- 如果在dirty中找到了,重复2的逻辑判断
- 在read和dirty中都没有,则创建一个新的entry
- 释放锁
- 返回结果
Delete/LoadAndDelete
// Delete deletes the value for a key. func (m *Map) Delete(key any) { m.LoadAndDelete(key) }
// LoadAndDelete deletes the value for a key, returning the previous value if any. // The loaded result reports whether the key was present. func (m *Map) LoadAndDelete(key any) (value any, loaded bool) { read := m.loadReadOnly() e, ok := read.m[key] if !ok && read.amended { m.mu.Lock() read = m.loadReadOnly() e, ok = read.m[key] if !ok && read.amended { e, ok = m.dirty[key] delete(m.dirty, key) // Regardless of whether the entry was present, record a miss: this key // will take the slow path until the dirty map is promoted to the read // map. m.missLocked() } m.mu.Unlock() } if ok { return e.delete() } return nil, false }
总结:
- 如果要删除的key在read中存在,将它置为nil
- 如果要删除的key在read中未找到,并且read和dirty一致,说明key不存在,返回nil, false
- key未找到,并且read和dirty不一致
- 加锁
- 重新查询read,类似上面1、2流程,如果key未找到,并且read和dirty不一致继续
- 在dirty中查询并删除
- misses加一
- 如果misses数大于dirty长度,将dirty同步到read,重置dirty和misses
- 释放锁
- 如果key在dirty中也不存在,返回nil, false;反之,将它置为nil
Store/Swap
// Store sets the value for a key. func (m *Map) Store(key, value any) { _, _ = m.Swap(key, value) } // Swap swaps the value for a key and returns the previous value if any. // The loaded result reports whether the key was present. func (m *Map) Swap(key, value any) (previous any, loaded bool) { read := m.loadReadOnly() if e, ok := read.m[key]; ok { if v, ok := e.trySwap(&value); ok { if v == nil { return nil, false } return *v, true } } m.mu.Lock() read = m.loadReadOnly() if e, ok := read.m[key]; ok { if e.unexpungeLocked() { // The entry was previously expunged, which implies that there is a // non-nil dirty map and this entry is not in it. m.dirty[key] = e } if v := e.swapLocked(&value); v != nil { loaded = true previous = *v } } else if e, ok := m.dirty[key]; ok { if v := e.swapLocked(&value); v != nil { loaded = true previous = *v } } else { if !read.amended { // We're adding the first new key to the dirty map. // Make sure it is allocated and mark the read-only map as incomplete. m.dirtyLocked() m.read.Store(&readOnly{m: read.m, amended: true}) } m.dirty[key] = newEntry(value) } m.mu.Unlock() return previous, loaded } // trySwap swaps a value if the entry has not been expunged. // // If the entry is expunged, trySwap returns false and leaves the entry // unchanged. func (e *entry) trySwap(i *any) (*any, bool) { for { p := e.p.Load() if p == expunged { return nil, false } if e.p.CompareAndSwap(p, i) { return p, true } } }
总结:
- 如果key在read中找到了,并且不为expunged,则试图CAS并返回结果
- key在read中未找到,或者为expunged
- 加锁
- 在read中查询
- 如果查到了,试图unexpunge
- 如果需要unexpunge,会将entry置(CAS)为nil,并在dirty中插入key
- 执行entry的Swap
- 如果查到了,试图unexpunge
- 在ditry中查询
- 如果查到了,执行entry的Swap
- 都没查到,则检查dirty是否存在,初始化dirty,并在dirty增加新的entry
- 释放锁
- 返回结果
CompareAndSwap
// CompareAndSwap swaps the old and new values for key // if the value stored in the map is equal to old. // The old value must be of a comparable type. func (m *Map) CompareAndSwap(key, old, new any) bool { read := m.loadReadOnly() if e, ok := read.m[key]; ok { return e.tryCompareAndSwap(old, new) } else if !read.amended { return false // No existing value for key. } m.mu.Lock() defer m.mu.Unlock() read = m.loadReadOnly() swapped := false if e, ok := read.m[key]; ok { swapped = e.tryCompareAndSwap(old, new) } else if e, ok := m.dirty[key]; ok { swapped = e.tryCompareAndSwap(old, new) // We needed to lock mu in order to load the entry for key, // and the operation didn't change the set of keys in the map // (so it would be made more efficient by promoting the dirty // map to read-only). // Count it as a miss so that we will eventually switch to the // more efficient steady state. m.missLocked() } return swapped } // tryCompareAndSwap compare the entry with the given old value and swaps // it with a new value if the entry is equal to the old value, and the entry // has not been expunged. // // If the entry is expunged, tryCompareAndSwap returns false and leaves // the entry unchanged. func (e *entry) tryCompareAndSwap(old, new any) bool { p := e.p.Load() if p == nil || p == expunged || *p != old { return false } // Copy the interface after the first load to make this method more amenable // to escape analysis: if the comparison fails from the start, we shouldn't // bother heap-allocating an interface value to store. nc := new for { if e.p.CompareAndSwap(p, &nc) { return true } p = e.p.Load() if p == nil || p == expunged || *p != old { return false } } }
总结:
- 如果key在read中找到了
- 如果为nil/expunged/不等于old,则返回false
- 试图进行entry的CAS,成功返回true,失败继续1、2流程
- 如果key在read中未找到,并且read与dirty没有不一致,返回false
- 如果key在read中未找到,并且read与dirty不一致
- 加锁
- 如果key在read中找到
- 如果仍然为nil/expunged/不等于old,结果为false
- 试图进行entry的CAS,CAS成功,则结果为true;否则继续1、2流程
- 如果key在dirty中找到
- 如果不等于old,结果为false
- 试图进行entry的CAS,CAS成功,则结果为true;否则继续1、2流程
- misses加一
- 如果misses数大于dirty长度,将dirty同步到read,重置dirty和misses
- 释放锁
- 返回结果
CompareAndDelete
// CompareAndDelete deletes the entry for key if its value is equal to old. // The old value must be of a comparable type. // // If there is no current value for key in the map, CompareAndDelete // returns false (even if the old value is the nil interface value). func (m *Map) CompareAndDelete(key, old any) (deleted bool) { read := m.loadReadOnly() e, ok := read.m[key] if !ok && read.amended { m.mu.Lock() read = m.loadReadOnly() e, ok = read.m[key] if !ok && read.amended { e, ok = m.dirty[key] // Don't delete key from m.dirty: we still need to do the “compare” part // of the operation. The entry will eventually be expunged when the // dirty map is promoted to the read map. // // Regardless of whether the entry was present, record a miss: this key // will take the slow path until the dirty map is promoted to the read // map. m.missLocked() } m.mu.Unlock() } for ok { p := e.p.Load() if p == nil || p == expunged || *p != old { return false } if e.p.CompareAndSwap(p, nil) { return true } } return false }
总结:
- 如果key在read中找到了
- 如果为nil/expunged/不等于old,则返回false
- 试图进行entry的CAS,成功返回true,失败继续1、2流程
- 如果key在read中未找到,并且read和dirty没有不一致,返回false
- 如果key在read中未找到,并且read和dirty不一致
- 加锁
- 从read中查找
- 如果找到key
- 为nil/expunged/不等于old,结果为false
- 试图进行CAS,成功结果为true,失败继续尝试
- 如果没找到,并且没有不一致,结果为false
- 如果找到key
- 如果read和dirty有不一致
- 从dirty中查找
- 如果找到key
- 不等于old,结果为false
- 试图CAS,成功结果为true,失败继续尝试
- 没找到key,结果为false
- 释放锁
- 返回结果
结论
总的来说,sync.Map
是Go标准库提供的一个非常有用的工具,它可以帮助我们简化并发编程,并且在一些特定的场景下能提供良好的性能。文章来源:https://www.toymoban.com/news/detail-513947.html
但在使用的时候,我们需要根据具体的应用场景和需求来选择使用sync.Map
还是其他的并发原语。文章来源地址https://www.toymoban.com/news/detail-513947.html
到了这里,关于go src - sync.Map的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!