关于go:syncMap

8次阅读

共计 5955 个字符，预计需要花费 15 分钟才能阅读完成。

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{}}

func newEntry(i any) *entry {return &entry{p: unsafe.Pointer(&i)}
}

//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
}

// 设置键值对
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 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。

正文完