go src - sync.Map

小秦哥 · 2023-7-1 23:21:45

前言

在并发编程中，我们经常会遇到多个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
- 在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
- 如果read和dirty有不一致
  - 从dirty中查找
  - 如果找到key
    - 不等于old，结果为false
    - 试图CAS，成功结果为true，失败继续尝试
  - 没找到key，结果为false
- 释放锁
- 返回结果

结论
总的来说，sync.Map是Go标准库提供的一个非常有用的工具，它可以帮助我们简化并发编程，并且在一些特定的场景下能提供良好的性能。
但在使用的时候，我们需要根据具体的应用场景和需求来选择使用sync.Map还是其他的并发原语。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

		自动登录	找回密码
密码			立即注册

go src - sync.Map

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云