Golang: 探究sync.map的实现
背景
探究下载并发模式下, sync.map 的实现, 以及该实现方式可能引入的问题
链接
基本使用
package main
import "sync"
func main() {
m := sync.Map{}
m.Load("key")
m.Store("key", "value")
m.LoadOrStore("key", "value")
m.Delete("key")
}
以上就是主要的增删改查的能力.
数据结构
entry
type entry struct {
p atomic.Pointer[any]
}
分析
在sync包的Map类型中，entry是一个结构体，它代表了Map中的一个槽位，对应于一个特定的键。
entry的主要作用是存储Map中的键值对。它包含一个p字段，这是一个原子指针，指向存储在条目中的值。p字段的状态（是否为nil或expunged）决定了条目的状态（是否已被删除或有效）。
此外，entry还提供了一些方法，如load、tryCompareAndSwap、unexpungeLocked、swapLocked、tryLoadOrStore和delete，这些方法用于操作存储在条目中的值，包括加载值、比较并交换值、取消标记删除、交换值、尝试加载或存储值以及删除值。这些操作都是并发安全的，因为它们使用了原子操作来处理p字段。
Why atomic.Pointer?
atomic.Pointer在Go语言中被用于实现并发安全的指针操作。
在多线程或者并发编程中，对共享数据的读写操作可能会发生在不同的goroutine中，这就可能导致数据的不一致性。为了解决这个问题，我们需要一种机制来保证在任何时刻，对共享数据的访问都只能有一个goroutine进行。
atomic.Pointer提供了这样的机制。它提供了一组函数，可以对指针进行原子性的加载（Load）、存储（Store）和比较并交换（CompareAndSwap）操作。这些操作是并发安全的，也就是说，在多个goroutine同时进行这些操作时，不需要额外的锁机制就可以保证数据的一致性。
在你提供的代码中，p atomic.Pointer[any]是entry结构体的一个字段，它存储了对应的键值对的值。通过使用atomic.Pointer，entry可以在多个goroutine中安全地读写这个值，而不需要额外的锁。这对于sync.Map这样的并发数据结构来说是非常重要的，因为它需要在多个goroutine中高效地读写数据。
readOnly
type readOnly struct {
m map[any]*entry
amended bool // true if the dirty map contains some key not in m.
}
分析
readOnly结构体有两个字段：
-
m：这是一个存储entry指针的map，其中entry是Map中的一个槽位，对应于一个特定的键。 -
amended：这是一个布尔值，如果dirty map包含m中没有的键，则为true。
readOnly的主要作用是存储Map的一部分内容，这部分内容是可以安全进行并发访问的，无论是否持有mu锁。readOnly结构体的实例存储在Map的read字段中，可以通过原子操作进行加载和存储。
当Map的dirty map中存在read map中没有的键时，amended字段会被设置为true。这表示read map不再是最新的，需要通过复制dirty map来更新。这种设计可以帮助Map在并发环境中高效地进行读写操作，减少锁的争用。
Map
type Map struct {
mu sync.Mutex
read atomic.Pointer[readOnly]
dirty map[any]*entry
misses int
}
分析
主要优化了两种常见的使用场景：(1) 键值对只写入一次但读取多次，如只增长的缓存；(2) 多个goroutine读写和覆盖不同键的条目。
sync.Map的主要组成部分包括：
-
mu：一个互斥锁，用于保护对dirty map的访问。 -
read：一个原子指针，指向readOnly结构体的实例。readOnly结构体包含一个entry指针的map和一个amended布尔值。read字段中的内容可以在不持有mu锁的情况下并发访问。 -
dirty：一个存储entry指针的map，需要持有mu锁才能访问。dirty map包含了所有需要更新的键值对，以及read map中的所有非删除条目。 -
misses：一个计数器，记录自上次更新read map以来需要锁定mu来确定键是否存在的加载操作的次数。
方法分析
Load
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()
read = m.loadReadOnly()
e, ok = read.m[key]
if !ok && read.amended {
e, ok = m.dirty[key]
m.missLocked()
}
m.mu.Unlock()
}
if !ok {
return nil, false
}
return e.load()
}
代码分析
- 获取read map
- 如果read中存在, 则返回
- 如果read中不存在, 且read已经过时, 则尝试从dirty中获取, 同时 miss + 1
Store
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
}
分析
Swap方法是sync.Map中的一个方法，它用于交换键对应的值，并返回之前的值（如果存在）。如果键在Map中存在，那么loaded返回值为true，否则为false。
Swap方法的实现主要分为两个步骤：
- 首先，它会尝试在只读的
read map中查找键对应的条目。如果找到了，并且可以成功地交换值，那么就直接返回。这是一种优化，可以避免在大多数情况下都需要获取锁。 - 如果在
read map中没有找到键，或者无法交换值，那么就需要获取mu锁，并在dirty map中查找和操作键对应的条目。在这个过程中，可能需要将dirty map提升为read map，或者在dirty map中添加新的条目。
这个方法首先尝试在read map中查找键对应的条目，并尝试交换值。如果成功，就直接返回。如果在read map中没有找到键，或者无法交换值，那么就需要获取mu锁.
并在dirty map中查找和操作键对应的条目。在这个过程中，可能需要将dirty map提升为read map，或者在dirty map中添加新的条目。
注意
expunged 与 nil
区别
-
如果一个entry的p为 expunged, 表示一定发生了一次 dirty的初始化, 此时 entry 的 key 一定不在dirty中
-
如果一个entry的p为nil, 依然表示清除, 但是此时dirty中必然有同样的key
作用
所以, 对于已删除的key来说, 不能在expunged的状态下进行更新操作, 因为这会导致在dirty提升为read时, 出现数据不一致的问题.
这就是, trySwap的设计:
func (e *entry) trySwap(i *any) (*any, bool) {
for {
p := e.p.Load()
if p == expunged {
// 返回nil, false
return nil, false
}
// 如果entry不为nil
if e.p.CompareAndSwap(p, i) {
// 返回entry的值, true
return p, true
}
}
}
unexpungeLocked
func (e *entry) unexpungeLocked() (wasExpunged bool) {
return e.p.CompareAndSwap(expunged, nil)
}
为什么要使用 unexpungeLocked我们可以考虑如果不使用unexpungeLocked将expunged转为nil, 会发生什么?
那么我们在此时的使用就会变成
if e.p.Load() == expunged {
m.dirty[key] = e
}
即虽然我们保证了 read 和 dirty中都存在同一个key, 但是此时的 e.p都为 unexpungeLocked, 无法调用封装的函数进行修改, 而只能直接使用e.p.Store(&i)进行修改了,
这样会有什么问题?
- 原子操作的预期行为：
sync.Map 中的原子操作依赖于expunged 和nil 状态来决定条目是否可以被更新。如果一个条目是expunged 状态，它不能直接被更新，因为这意味着该条目已经从dirty 映射中删除了。如果不先将其置为nil，那么原子操作的预期行为就会被破坏。 - 状态一致性：
sync.Map 维护了read 和dirty 映射之间的一致性。条目从expunged 状态恢复为nil 是一个信号，表明该条目现在可以安全地更新，并且这个更新应该反映在dirty 映射中。 - 并发安全：在并发环境中，其他 goroutines 可能会尝试读取或更新同一个键的条目。如果一个条目从
expunged 状态直接更新为一个新值，其他 goroutines 可能会遇到一个不一致的状态，因为它们预期要么是expunged 要么是nil，然后才是一个有效的值。
因此，正确地处理 expunged 状态是保证 sync.Map 正确行为的关键。在更新一个条目之前，如果它被标记为 expunged，应当首先通过 unexpungeLocked 方法将其状态置为 nil，然后才能安全地进行更新。这样可以确保 sync.Map 的并发安全性和性能优化得到保持。
总结
- sync.Map目前的实现, 非常适合 读多写少的操作. 尤其是有大量非覆盖写的调用, 性能会直接回退到
map+mutex(在覆盖写的情况下, read 和 dirty 可以共享entry, 实现乐观锁的更新, 性能会好一些. - 在研究其代码时, 需要非常注意
nil 以及expunged两种状态的区别.