sync.Map
数据结构
type Map struct { // 互斥锁 mu Mutex // 只读，原子的操作read read atomic.Value // readOnly // 加锁才能够拜访 dirty map[any]*entry // 记录未命中次数，当未命中次数等于dirty长度时，将dirty晋升为ready misses int}// readOnly 是一个不可变构造，以原子形式存储在 Map.read 字段中type readOnly struct { m map[any]*entry // dirty中有不在read中的key ===> amended = true amended bool // true if the dirty map contains some key not in m.}// expunged 是一个任意指针，用于标记从dirty map中已删除的条目// 在map中删除一个条目只是将其标记为expunge，并不是真正的删除吗，期待有机会在删除var expunged = unsafe.Pointer(new(any))// entry是map中对应于特定key的槽。type entry struct { // p指向为entry存储的 interface{} 值。 // 如果 p == nil,则该entry已被删除,并且 m.dirty == nil或m.dirty[key]=e。 // 如果 p == expunged，则该entry已被删除，m.dirty != nil，并且m.dirty 中短少该entry（dirty != nil, and the entry is missing from m.dirty）。 // 否则，该entry无效并记录在 m.read.m[key] 中，如果是 m.dirty!= nil，在 m.dirty[key] 中。 // 能够通过用 nil 原子替换来删除entry：当 m.dirty 为下一次创立，它会原子地用 expunged 替换 nil 并来到m.dirty[key] 未设置。 // 一个entry的关联值能够通过原子替换来更新，前提是p != expunged。如果 p == expunged，则在第一次设置 m.dirty[key] = e 之后才应用dirty找到entry更新entry p unsafe.Pointer // *interface{}}newEntry
func newEntry(i any) *entry { return &entry{p: unsafe.Pointer(&i)}}Load
//Load 返回存储在 map 中的 key 值，如果没有值存在则返回 nil//ok后果示意是否在map中找到值。func (m *Map) Load(key any) (value any, ok bool) { // 从read开始，read不须要锁 read, _ := m.read.Load().(readOnly) e, ok := read.m[key] // read中不存在key并且dirty中存在key if !ok && read.amended { // dirty 加锁 m.mu.Lock() // 双重检测 // 防止在load时有其余协程写入数据而本人没有感知到，造成虚伪的未命中 read, _ = m.read.Load().(readOnly) e, ok = read.m[key] if !ok && read.amended { e, ok = m.dirty[key] // 不论entry是否存在，记录一次未命中(miss + 1)：this key将采纳慢速门路，直到将dirty map晋升为read map。 m.missLocked() } m.mu.Unlock() } // 在read map和dirty map都未找到key，返回nil和false if !ok { return nil, false } // 返回读取到的对象 return e.load()}func (e *entry) load() (value any, ok bool) { // LoadPointer 以原子形式加载 *addr // func LoadPointer(addr *unsafe.Pointer) (val unsafe.Pointer) p := atomic.LoadPointer(&e.p) // entry被删除 if p == nil || p == expunged { return nil, false } return *(*any)(p), true}func (m *Map) missLocked() { // 未命中次数加一 m.misses++ // 如果未命中次数小于dirty长度间接返回 if m.misses < len(m.dirty) { return } // 把dirty晋升为read m.read.Store(readOnly{m: m.dirty}) // 清空dirty m.dirty = nil // misses置为0 m.misses = 0}Store
// 设置键值对func (m *Map) Store(key, value any) { read, _ := m.read.Load().(readOnly) // read中存在key，更新值 if e, ok := read.m[key]; ok && e.tryStore(&value) { return } // read中不存在key或cas更新失败，加锁拜访dirty m.mu.Lock() read, _ = m.read.Load().(readOnly) // 双重检测，read中是否存在key if e, ok := read.m[key]; ok { // (p->expunged) ==> (p->nil) ==> (p->失常) 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. // 此我的项目先前曾经被删除了，通过将它的值设置为nil，标记为unexpunged // 勾销删除标记 m.dirty[key] = e } // 更新 e.storeLocked(&value) } else if e, ok := m.dirty[key]; ok { // 在dirty map中间接更新 e.storeLocked(&value) } 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. // 须要创立dirty对象，并且标记read的amended为true,阐明有元素它不蕴含而dirty蕴含 m.dirtyLocked() // (p->nil) ==> (p->expunged) m.read.Store(readOnly{m: read.m, amended: true}) } // 将新值减少到dirty对象中 m.dirty[key] = newEntry(value) } m.mu.Unlock()}// tryStore stores a value if the entry has not been expunged.//// If the entry is expunged, tryStore returns false and leaves the entry// unchanged.func (e *entry) tryStore(i *any) bool { for { p := atomic.LoadPointer(&e.p) if p == expunged { return false } if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) { return true } }}// unexpungeLocked ensures that the entry is not marked as expunged.//// If the entry was previously expunged, it must be added to the dirty map// before m.mu is unlocked.// unexpungeLocked 确保entry未被标记为已删除。//如果该entry之前已被革除，则必须在 m.mu 解锁之前将其增加到dirty map中func (e *entry) unexpungeLocked() (wasExpunged bool) { return atomic.CompareAndSwapPointer(&e.p, expunged, nil)}// storeLocked unconditionally stores a value to the entry.//// The entry must be known not to be expunged.//storeLocked 无条件地将值存储到条目中。////必须晓得该条目不会被删除。func (e *entry) storeLocked(i *any) { atomic.StorePointer(&e.p, unsafe.Pointer(i))}func (m *Map) dirtyLocked() { if m.dirty != nil { return } read, _ := m.read.Load().(readOnly) m.dirty = make(map[any]*entry, len(read.m)) for k, e := range read.m { if !e.tryExpungeLocked() { m.dirty[k] = e } }}func (e *entry) tryExpungeLocked() (isExpunged bool) { p := atomic.LoadPointer(&e.p) for p == nil { if atomic.CompareAndSwapPointer(&e.p, nil, expunged) { return true } p = atomic.LoadPointer(&e.p) } return p == expunged}Delete
// 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.read.Load().(readOnly) e, ok := read.m[key] // 双重检测 if !ok && read.amended { m.mu.Lock() read, _ = m.read.Load().(readOnly) 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}func (e *entry) delete() (value any, ok bool) { for { p := atomic.LoadPointer(&e.p) if p == nil || p == expunged { return nil, false } // (p->失常) ==> (p->nil) if atomic.CompareAndSwapPointer(&e.p, p, nil) { return *(*any)(p), true } }}状态
value 状态：entry 外面寄存的是真正的值。此时 entry 对应的 key，有三种状况，key 只在 read 中均存在；key 只在 dirty 中存在；在 read 和 dirty 中均存在。
nil 状态：read 中的 key 被删除的时候将其对应的 value(即 entry) p 值设置为 nil。此时 key 只存在 read 中 （ditry 为 nil）；在 read 和 dirty 中均存在。
expunge 状态： 此时 key 只存在 read 中而在 dirty 中不存在。
将 sync.Map 形象为 存、取、删除 三种操作。在这三种操作中来看 entry 状态的扭转。
1、存：对于初始状态的 sync.Map, 一个新键值对 k: A v: A, 首先寄存在 dirty 中，此时 entry 为 value 状态，key 只存在 dirty 中。
2、取：首先 read 中不存在，从 dirty 中取值。数次从 read 中取不中，将 dirty 晋升为 read， dirty 被清空。entry 仍为 value 状态，对应的 key 存在于 read 中。
3、存：另一键值对k:B v:B，存入时，产生 read 向 dirty 拷贝，同时 read 的 amended 标记为 true。此时 key A 存在于 read 和 dirty 中，entry 为 value 状态。
4、删除：删除 key A，A 的 entry 中 p 值被设置为 nil。此时 key A 存在于 read 和 dirty 中，entry 为 nil 状态。
5、存：另一键值对k:C v:C。
6、取：屡次读取 key C，触发 dirty 晋升为 read，dirty 被清空。此时 key A 只存在于 read 中, entry 为 nil 状态。
7、存：另一键值对 k:D v:D， 存入时，产生 read 向 dirty 拷贝，key A 的 entry 由 nil 状态转变为 expunge 状态，key A 只存在于 read 中。
8、取：屡次读取 key D，触发 dirty 晋升为 read， dirty 被清空，此时 key A 被齐全删除。
为什么会用 nil 和 expunge 两种状态来标记一个值的删除？
首先明确，什么时候 expunge 呈现。当key A 的值在 read 中为 nil，随后由其余操作触发 read 向 dirty 复制，nil 被转变为 expunge。此时 dirty 不为空，且 key A 在 dirty 中不存在。如果对 key A 从新赋值，批改 read 后，须要同步批改 dirty ，为了保障当 dirty 晋升为 read 时，蕴含所有的值。
再来看 nil 的清空，当 key A 的值为 nil 状态的时候，key A 存在于 read 和 dirty 中或仅存在于 read 中（dirty 为空），因为 read 和 dirty 中雷同的 key 指向同一值的指针，因而在这两种状况下，对 key A 从新赋值，均无需思考 dirty。