前言

前面，我们讲了map的用法以及原理Golang中map的实现原理，但我们知道，map在并发读写的情况下是不安全。需要并发读写时，一般的做法是加锁，但这样性能并不高，Go语言在 1.9 版本中提供了一种效率较高的并发安全的 sync.Map，今天，我们就来讲讲 sync.Map的用法以及原理

使用方法

func main() {
    var m sync.Map
    //插入
    m.Store("1","a")
    //取值
    fmt.Println(m.Load("1"))
    //删除
    m.Delete("1")
    //循环
    m.Range(func(k, v interface{}) bool {
        fmt.Println(k,v)
        return true
    })
}

sync.Map与map不同，不是以语言原生形态提供，而是在 sync 包下的特殊结构：

• 无须初始化，直接声明即可。

• sync.Map 不能使用 map 的方式进行取值和设置等操作，而是使用 sync.Map 的方法进行调用，Store 表示存储，Load 表示获取，Delete 表示删除。

• 使用 Range 配合一个回调函数进行遍历操作，通过回调函数返回内部遍历出来的值，Range 参数中回调函数的返回值在需要继续迭代遍历时，返回 true，终止迭代遍历时，返回 false。

原理

注意：我会把源码中每个方法的作用都注释出来，可以参考注释进行理解。

数据结构

我们下来看下sync.Map结构体

sync/map.go:Map

// 这里的 Map 是为了两种用例来优化的:
// (1) 当某个指定的 key 只会被写入一次，但是会被读取非常多次，例如像不断增长的 caches。
// (2) 当多个 goroutine 分别分布读、写和覆盖不同的 key。
// 这两种场景下，使用 sync.Map，相比普通的 map 配合 Mutex 或 RWMutex，可以大大降低锁的竞争
// Map 的零值是可以使用的空 Map。当 Map 被首次使用之后，就不能再被拷贝了
type Map struct {
    mu Mutex

    // read 包含了 map 内容的一部分，是一个只读的结构，所以没有读写冲突
    read atomic.Value // readOnly

    //dirty 包含了 map 中那些在访问时需要持有 mu 的部分内容
    //为了确保 dirty map 的元素能够被快速地移动到 read map 中
    // 它也包含了那些 read map 中未删除(non-expunged)的项
   //  expunged 掉的 entries 不会在 dirty map 中存储。被 expunged 的 entry，
    // 如果要存新值，需要先执行 expunged 逆操作，然后添加到 dirty map，然后再进行更新
    //当dirty为空的时候， 比如初始化或者刚提升完，下一次的写操作会复制read字段中未删除的数据到这个数据中。
    dirty map[interface{}]*entry

    //当从Map中读取entry的时候，如果read中不包含这个entry,会尝试从dirty中读取，这个时候会将misses加1，
    // 当misses累积到 dirty的长度的时候， 就会将dirty提升为read,避免从dirty中miss太多次。因为操作dirty需要加锁
    misses int
}

sync/map.go:readOnly

//readOnly是原子形式存储在Map.read字段中的不变结构。
type readOnly struct {
    m       map[interface{}]*entry
    //  如果 dirty map 中包含有不在 m 中的项，那么 amended = true
    amended bool 
}

sync/map.go:entry

//entry 是 map 对应一个特定 key 的槽
type entry struct {

    //
    // 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指向为map的interface {} value值。
    //如果 p == nil, 那么说明对应的 entry 被删除了，且m.dirty == nil
    //如果 p == expunged，说明 entry 被删除了，但 m.dirty != nil，且该 entry 在 m.dirty 中不存在
    //除此以外，entry 则是合法的值并且在 m.read.m[key] 中存在
    // 如果 m.dirty != nil，也会在 m.dirty[key] 中
    p unsafe.Pointer // *interface{}

}

结构体之间的关系如下图所示：

在这里插入图片描述

Store方法

sync/map.go:Store

//为某一个 key 的 value 赋值
func (m *Map) Store(key, value interface{}) {
    read, _ := m.read.Load().(readOnly)
    //通过key从read中取出value，并尝试更新这个值且成功
    //则直接返回
    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 {
        if e.unexpungeLocked() {
            //确保e未被标记为删除
            m.dirty[key] = e
        }
        //将value地址赋值给entry中的p
        e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok {
        //key存在dirty中
        //直接更新p
        e.storeLocked(&value)
    } else {
        //新值
        if !read.amended {
            //为 dirty map 增加第一个新的 key
            //将read中为被标记为expunged复制过来给dirty
            m.dirtyLocked()
            // 确保已分配它，并将readOnly标记为，即amended=true
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        //赋值
        m.dirty[key] = newEntry(value)
    }
    //释放锁
    m.mu.Unlock()
}

sync/map.go:tryStore

//更新value
func (e *entry) tryStore(i *interface{}) bool {
    for {
        p := atomic.LoadPointer(&e.p)
        //如果p是删除状态
        if p == expunged {
            //返回失败
            return false
        }
        //否则，cas操作将值更新
        if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
            return true
        }
    }
}

sync/map.go:dirtyLocked

//将read中未被删除的值复制给dirty
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
        }
    }
}

//判断是否被被标记为expunged
func (e *entry) tryExpungeLocked() (isExpunged bool) {
    p := atomic.LoadPointer(&e.p)
    // 将已经删除标记为nil的数据标记为expunged
    for p == nil {
        if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
            return true
        }
        p = atomic.LoadPointer(&e.p)
    }
    return p == expunged
}

总结一下：

1. 判断ready中是否存在该key：如果存在，则直接通过cas操作更新value的值
2. 通过mu.Lock()加锁，判断key的位置：
   1. 如果key存在ready中，且未被标记expunged（删除），更新ready中key对应的value值
   2. 如果key存在dirty中，更新dirty中key对应的value值
   3. 否则，key为新值。将ready中未删除的值全部赋值给dirty，并将key新值赋值给dirty
3. 最后，释放锁，结束赋值过程

Load方法

sync/map.go:Load

//查询
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    //如果key不在ready中
    //且存在dirty中
    if !ok && read.amended {
        //加锁
        //说明需要去dirty中寻找
        m.mu.Lock()
        //双重校验，防止在加锁区间，m.dirty提升为m.read
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            e, ok = m.dirty[key]
            //misses++
            //同时判断misses是否超过dirty的length
            //如果超过，则将dirty整个结构体赋给ready，同时将dirty=nil，misses=0
            m.missLocked()
        }
        //释放锁
        m.mu.Unlock()
    }
    //如果ready和dirty都不存在，返回false
    if !ok {
        return nil, false
    }
    //否则，就是存在ready中，则直接返回val
    return e.load()
}

sync/map.go:missLocked

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {
        return
    }
    //直接将结构体赋给read，不用一个一个值赋值，速度更快
    m.read.Store(readOnly{m: m.dirty})
    //清0
    m.dirty = nil
    m.misses = 0
}

sync/map.go:load

func (e *entry) load() (value interface{}, ok bool) {
    p := atomic.LoadPointer(&e.p)
    //如果被删除或者标记为删除状态
    if p == nil || p == expunged {
        return nil, false
    }
    return *(*interface{})(p), true
}

Load方法比较简单，总结一下：

1. 如果key不存在ready中，且存在dirty中，则需要加锁，同时再次确认该key是不存在ready，但存在dirty中（双重校验，防止加锁区间，m.dirty提升为m.read）。从dirty中获取值，同时，misses加1，并且判断是否满足m.dirty提升为m.read的条件，最后，释放锁
2. 如果key即不存在于ready中，也不存在于dirty中，则直接返回false和nil值
3. 最后，key存在ready中，直接去ready中未被删除的值中寻找

Delete方法

sync/map.go:Delete

func (m *Map) Delete(key interface{}) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    //存在dirty中
    if !ok && read.amended {
        m.mu.Lock()
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        //同上，双重校验
        if !ok && read.amended {
            //调用map的内置函数，直接删除
            delete(m.dirty, key)
        }
        m.mu.Unlock()
    }
    //存放在ready中
    if ok {
        e.delete()
    }
}

sync/map.go:delete

func (e *entry) delete() (hadValue bool) {
    for {
        p := atomic.LoadPointer(&e.p)
        if p == nil || p == expunged {
            return false
        }
        //将值变为nil
        if atomic.CompareAndSwapPointer(&e.p, p, nil) {
            return true
        }
    }
}

总结如下：

1. key存在dirty中，则加锁并进行双重检验，然后通过map的内置函数delete删除
2. key存在ready中，则将value的地址变为nil

总结

• sync.Map采用空间换时间的思想， 通过冗余的两个数据结构(read、dirty),减少加锁对性能的影响
• 使用只读数据(read)，避免读写冲突
• 优先从read读取、更新、删除，因为对read的读取不需要锁
• 采用了延迟删除，删除一个键值只是打标记（会将key对应value的pointer置为nil，但read中仍然有这个key:key;value:nil的键值对），只有在提升dirty的时候才清理删除的数据

有疑问加站长微信联系（非本文作者）