总结
  1. golang的map是不支持并发访问和设置的,否则会panic。在golang的历史中,最开始只有不支持并发的map,但是实际上并发访问map的场景比较多,因此后续golang团队开发了sync.Map
  2. sync.Map使用场景有限,虽然并发访问的map的场景都可以使用它,但是golang团队注释里面说明了它的使用场景
    • 如果有具体的类型,建议使用map+Mutex(or RWMutex)
    • 如果掺杂多个类型,为了便于维护,建议使用sync.Map
  3. sync.Map在两个场景做了优化,这两种场景可以减少锁的使用
    • 写一次,读多的场景
    • 多个goroutine读、写,并且覆盖的都是对于不同的keys
  4. 通过两个map加上Mutex来实现的,先把k、v存储在dirty,如果查找多次均不在read,会把dirty迁移到read,后续读取key,会直接从read读取,且不用加锁。
  5. 只有对于dirty的操作才加锁
关键字

atomic.Value、dirty、readOnly、Mutex

使用 源码分析
  1. 存贮key、value的时候,会先存入dirty里面,当读取的时候,会检查read里面是否没有,没有则misses加一
  2. 如果misses大于dirty的长度,则将dirty赋值给read的m,然后将dirty清空,从而再次读取key,直接从readOnly里面读取,并且不用加锁
  3. 将dirty赋值给read的m时,amended也会设置为false,如果Store的key不在read,会进行dirtyLocked操作,即把read的key也通过循环拷贝到dirty

结构体

type Map struct {
    mu Mutex  // 锁,主要是加锁操作dirty

    read atomic.Value // readOnly 存贮的是readOnly,里面有m的map,用作只读,所以可以不加锁

    // 存贮key、value,首先存入dirty,如果misses大于dirty的长度,则迁移到read里的m
    dirty map[interface{}]*entry 

    misses int 
    // 计数器,记录查找直接从dirty获取key、value的次数,
    // 如果超过dirty的长度,则把dirty迁移到read,然后就可以直接从read里面获取,不用加锁
}
type readOnly struct {
    m       map[interface{}]*entry  // 存储用于只读 key、value
    amended bool // true if the dirty map contains some key not in m. // 表明dirty里是否有值
}

函数分析

主要分为三部分:查找、删除、存储

Store函数

  1. 如果开始都是调用Store,则每次都会加锁,即使key已经存在,value也相同,也会加锁,重新赋值,因为read一直为零值,每回都要操作dirty
  2. 如果超过dirty的长度次数没有命中,会把dirty迁移到read里面,并将dirty设置为nil,后续如果有存入操作,且read里面不存在,则会把read里面的数据迁移到dirty,并将新的数据加入ditry
func (m *Map) Store(key, value interface{}) {
    // 从readOnly里面读取,初始化状态read为空,因为下面写的结构体readOnly,read会初始化化为readOnly的零值
    read, _ := m.read.Load().(readOnly)
    // 存在,则将entry里面的重新赋值为value
    // 如果在read里面存在,则会通过cas操作更新read里面的值
    // 如果是已经删除的,会继续执行代码
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }

    // read里没有,则加锁,对dirty进行操作,整个过程都加锁
    m.mu.Lock()
    // double check,可能等待加锁时,另一个goroutine已经进入,加锁成功后,read里面已经存在了
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        // 如果key在read里面已经存在,且v为expunged(已经删除的),则将e的p设置为nil
        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.
            // 将k设置到key
            m.dirty[key] = e
        }
        // 将value设置到e
        e.storeLocked(&value)
    // 在dirty中,如果key存在,即使e里存储的值跟value相同,也会重新赋值覆盖
    } else if e, ok := m.dirty[key]; ok {
        e.storeLocked(&value)
    } else {
        // 初始化场景或者将进行了missLocked(将dirty赋值给readOnly:将数据迁移到readOnly里面,
        // amended会被设置为false)
        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.
            // dirtyLocked会将readOnly里面的值赋值给dirty,防止readOnly里存在,但是dirty为nil的场景,
            // 这时会存储两倍的key和value。如果key、value比较多,可能会有内存压力
            m.dirtyLocked()
            // 将amended设置为true
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        // dirty里面存贮key、value
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
}

处理场景:

  1. misses大于dirty的长度,将dirty转移到read里面去,dirty设置为0
  2. 如果新存贮key、value,这时key不在read,从而会存储到dirty里去
  3. 如果后续又有获取操作,导致misses大于dirty,又会执行操作1,如果不将read里面的值都拷贝到dirty里去,会导致数据丢失
func (m *Map) dirtyLocked() {
    if m.dirty != nil {
        return
    }

   // 如果m.dirty为nil,会把read里面数据迁移到dirty
    read, _ := m.read.Load().(readOnly)
    m.dirty = make(map[interface{}]*entry, len(read.m))
    for k, e := range read.m {
        if !e.tryExpungeLocked() {
            // 如果key的vaule不是expunged,则都转移到dirty里面去,这时dirty和read里面都存在key、value,
            // 会导致k、v翻倍,已经删除的key不会被迁移
            // 数据整体迁移,如果量比较大,可能会花费一定时间
            m.dirty[k] = e
        }
    }
}

Load函数

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 先从readOnly
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended {
        m.mu.Lock()
        // Avoid reporting a spurious miss if m.dirty got promoted while we were
        // blocked on m.mu. (If further loads of the same key will not miss, it's
        // not worth copying the dirty map for this key.)
        // double check,可能加锁前有人已经进来修改过read
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            e, ok = 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.
            // 如果在read里面没有命中,则将misses加一,然后判断misses是否超过dirty的大小
            // 如果超过,则将dirty转移到read里面去
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load()
}
  1. 迁移dirty到read里去,并将amended设置为false
  2. 调用该函数需要加锁,即mu加锁
func (m *Map) missLocked() {
    m.misses++
    // 判断misses是否超过dirty的长度
    if m.misses < len(m.dirty) {
        return
    }
    // 将dirty赋值给read,并将emended设置为false
    m.read.Store(readOnly{m: m.dirty})
    // dirty清空,misses设置为0
    m.dirty = nil
    m.misses = 0
}

LoadOrStore函数

是将Load和Store合并起来,如果key存在,则返回对应value,如果不存在,则将key、value存储进去

func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
    // Avoid locking if it's a clean hit.
    // 从read里面查找,存在返回
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        // 存在,确认是否为expunged,如果是则返回不存在
        // 如果存在直接返回
        actual, loaded, ok := e.tryLoadOrStore(value)
        if ok {
            return actual, loaded
        }
    }

    // 加锁,一直到结束
    m.mu.Lock()
    // double check
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        // 如果是unexpunge,则存储key、value
        if e.unexpungeLocked() {
            m.dirty[key] = e
        }
        // 获取实际值
        actual, loaded, _ = e.tryLoadOrStore(value)
    } else if e, ok := m.dirty[key]; ok {
        // 在dirty里面存在,获取实际值
        actual, loaded, _ = e.tryLoadOrStore(value)
        // 统计misses,看是否迁移,跟Load里一样的逻辑
        m.missLocked()
    } else {
        // 跟Store里逻辑一样
        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)
        actual, loaded = value, false
    }
    m.mu.Unlock()

    return actual, loaded
}

tryLoadOrStore函数

func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) {
    p := atomic.LoadPointer(&e.p)
    // 如果是expunged,则直接返回不存在
    if p == expunged {
        return nil, false, false
    }
    // 存在,则返回值
    if p != nil {
        return *(*interface{})(p), true, true
    }

    // Copy the interface after the first load to make this method more amenable
    // to escape analysis: if we hit the "load" path or the entry is expunged, we
    // shouldn't bother heap-allocating.
    // 不存在,则设置值,因为tryLoadOrStore不一定在lock里面执行,所以需要for循环,一直到设置成功
    ic := i
    for {
        if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) {
            return i, false, true
        }
        p = atomic.LoadPointer(&e.p)
        if p == expunged {
            return nil, false, false
        }
        if p != nil {
            return *(*interface{})(p), true, true
        }
    }
}

LoadAndDelete函数

  1. 删除key,并返回删除key对应的value,并且返回该key是否存在
  2. 先从read里面获取,如果存在,将entry里面的p设置为nil
  3. map删除只是将key、value设置为空,实际内存是不会压缩的
func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    // 从read查找,存在,直接delete
    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]
            // 从dirty里面删除key,因为加锁了,可以操作,对于read里面的只是将key对应的entry里的p设置为nil
            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
}

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

Delete函数

实际调用的是LoadAndDelete,只是不返回key是否存在,已经对应的value是什么

func (m *Map) Delete(key interface{}) {
    m.LoadAndDelete(key)
}

Range函数

  1. 如果dirty存在,则将dirty赋值给read里面的m
  2. 循环read里面的m
func (m *Map) Range(f func(key, value interface{}) bool) {
    // We need to be able to iterate over all of the keys that were already
    // present at the start of the call to Range.
    // If read.amended is false, then read.m satisfies that property without
    // requiring us to hold m.mu for a long time.
    read, _ := m.read.Load().(readOnly)
    // 如果dirty存在,则将dirty赋值给read,然后从read里面读取所有的值
    if read.amended {
        // m.dirty contains keys not in read.m. Fortunately, Range is already O(N)
        // (assuming the caller does not break out early), so a call to Range
        // amortizes an entire copy of the map: we can promote the dirty copy
        // immediately!
        m.mu.Lock()
        read, _ = m.read.Load().(readOnly)
        if read.amended {
            read = readOnly{m: m.dirty}
            m.read.Store(read)
            m.dirty = nil
            m.misses = 0
        }
        m.mu.Unlock()
    }

    for k, e := range read.m {
        v, ok := e.load()
        if !ok {
            continue
        }
        if !f(k, v) {
            break
        }
    }
}