sync.Map

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。