Golang源码笔记

sync.Map 源码解析

结构体

type Map struct {
    mu Mutex
    read atomic.Value // readOnly
    dirty map[interface{}]*entry
    misses int
}

// readonly是read存储的结构
// m就是map
// amended只有dirty map是nil
type readOnly struct {
    m       map[interface{}]*entry
    amended bool // true if the dirty map contains some key not in m.
}

// 这里entry p指向很巧妙
type entry struct {
    // p points to the interface{} value stored for the entry.
    //
    // If p == nil, the entry has been deleted, and either m.dirty == nil or
    // m.dirty[key] is e.
    //
    // If p == expunged, the entry has been deleted, m.dirty != nil, and the entry
    // is missing from m.dirty.
    //
    // Otherwise, the entry is valid and recorded in m.read.m[key] and, if m.dirty
    // != nil, in m.dirty[key].
    //
    // An entry can be deleted by atomic replacement with nil: when m.dirty is
    // next created, it will atomically replace nil with expunged and leave
    // m.dirty[key] unset.
    //
    // An entry's associated value can be updated by atomic replacement, provided
    // p != expunged. If p == expunged, an entry's associated value can be updated
    // only after first setting m.dirty[key] = e so that lookups using the dirty
    // map find the entry.
    p unsafe.Pointer // *interface{}
}

Map结构体中,有个readdirty的两个结构,其中read是个atomic.Value,这个可以保证它的并发安全性,而dirty是个正常的map结构,主要是写操作,在写的时候,会使用mu这个锁来保证并发安全。至于misses是一个计数值,用来决定什么时候使用dirty替换read
map主要有获取、存储、删除里面数据的三个方法,下面来看看这三个方法分别是如何实现。

load

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    // 如果不在read的map里,但是在dirty里面
    if !ok && read.amended { 
        m.mu.Lock()
        // 这里使用锁之后,再次重新在read map中判断结果
        // 如果使用上面的read,那么有可能在获取自旋锁的时候
        // 会出现数据已经刷到read,而造成一次假miss
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            e, ok = m.dirty[key]
            // 不管在不在dirty里面都记一次miss
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load()
}
// 在misses数目达到dirty的容量时,将read用dirty覆盖
// 然后dirty改为nil,此时amended为false
func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {
        return
    }
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

store

// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
    // 如果已经在read里面直接赋值更改
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }
    // 开始上锁
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)

    if e, ok := read.m[key]; ok {
    // 这里出现的情况只是e.tryStore失败了,这种失败只有当前entry是expunge
        if e.unexpungeLocked() {
        // 尝试!将entry的p指针修改成nil
        // 修改成功放入dirty map。暂时还不知道放进去干嘛
        // 只知道被删除的key放进map了,但是这个key会被重新赋值
            m.dirty[key] = e
        }
        // 这里的entry的p指向value
        e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok {
        // read已经删除,dirty里面还有
        e.storeLocked(&value)
    } else {

        if !read.amended {
            // 首次存储key的时候
            m.dirtyLocked()
            // 将read修改为amended,意思也就是与dirty不一致了
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        // dirty存储这个值,此时其实read没有这个值
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
}
// 这个函数的作用dirty初始化
// 将read的数据刷到dirty中去
// 在read中删除的都是标记nil,此类数据不会刷进dirty
// 而是指向expunged
func (m *Map) dirtyLocked() {
    if m.dirty != nil {
        return
    }

    read, _ := m.read.Load().(readOnly)
    m.dirty = make(map[interface{}]*entry, len(read.m))
    for k, e := range read.m {
        if !e.tryExpungeLocked() {
            m.dirty[k] = e
        }
    }
}
// 如果entry是nil就转成expunged,如果不是,判断是不是expunged
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

// 直接用的LoadAndDelete,呵呵,估计后续有什么更改吧先保留吧
func (m *Map) Delete(key interface{}) {
    m.LoadAndDelete(key)
}

func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended {
        // 如果不在read中,但是dirty有不一致的情况,就要去diry里面看看了
        m.mu.Lock()
        // 这里跟load一模一样,要是强迫症估计要考虑将重复代码合并了
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            // 看看在不在dirty里面
            e, ok = m.dirty[key]
            // 不管在不在,删它丫的
            delete(m.dirty, key)
            // 不管在不在,记录它丫的
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if ok {
        // 这个ok就是可能在read里面,也可能是在dirty里面
        // 但是在dirty里面已经调用delete了,肯定是不在了
        // 所以基本就是read里面了,但是不管,都要进行处理
        return e.delete()
    }
    return nil, false
}

// 这里还是保证并发安全的,将p修改为nil
func (e *entry) delete() (value interface{}, ok bool) {
    for {
        p := atomic.LoadPointer(&e.p)
        if p == nil || p == expunged {
            return nil, false
        }
        if atomic.CompareAndSwapPointer(&e.p, p, nil) {
            return *(*interface{})(p), true
        }
    }
}

总结

  • 读取的时候先读取read map,这个是不用锁的,如果存在直接返回,如果不存在就查dirty map
  • 存储的时候,如果read中直接找到并且确定此entry在dirty里,直接更改entry的指针,如果不在read中,在dirty里面则也是直接更改,如果二者都不在,只存储在dirty里面
  • 删除时,如果在read中直接修改entry为nil,如果不在read,将从dirty里面移除

鉴于上述操作,感觉官方达到一个平衡,如果是多读少写的话,只是在read中未命中的时候,才会锁,去dirty中获取值,然后达到一定次数会同步到read。如果是并发读写的话,或者频繁更新,更新在read中的值也会减少一定的锁,比读写锁的优势就出来了。

发表评论

您的电子邮箱地址不会被公开。

2 × 5 =