前言
本期，将给大家讲解 sync 库中用于并发读情况下的 map 数据结构：sync.map。针对于 map 结构的考察，面试官一般都会问到这个数据结构，为了快速让大家理解，将从基础结构、操作方法两方面入手讲解。
数据结构
sync.map 数据结构
// sync.Map的核心数据结构type Map struct { mu Mutex // 对 dirty 加锁保护，线程安全 read atomic.Value // readOnly 只读的 map，充当缓存层 dirty map[interface{}]*entry // 负责写操作的 map，当misses = len(dirty)时，将其赋值给read misses int // 未命中 read 时的累加计数，每次+1}
// 上面read字段的数据结构type readOnly struct { m map[interface{}]*entry // amended bool // Map.dirty的数据和这里read中 m 的数据不一样时，为true}
// 上面m字段中的entry类型type entry struct { // 可见value是个指针类型，虽然read和dirty存在冗余情况（amended=false），但是由于是指针类型，存储的空间应该不是问题 p unsafe.Pointer // *interface{}}
复制代码
通过 read 和 dirty 两个字段实现数据的读写分离，读的数据存在只读字段 read 上，将最新写入的数据则存在 dirty 字段上
读取时会先查询 read，不存在再查询 dirty，写入时则只写入 dirty
读取 read 并不需要加锁，而读或写 dirty 则需要加锁
另外有 misses 字段来统计 read 被穿透的次数（被穿透指需要读 dirty 的情况），超过一定次数则将 dirty 数据更新到 read 中（触发条件：misses=len(dirty)）
sync.map 优缺点：
适用场景：读多写少的场景。
通过这种读写分离的设计，解决了并发场景下的写入安全，又使读取速度在大部分情况可以接近内建 map，非常适合读多写少的情况。
接下来为了快速读懂 sync.map，我们可以快速从读、删除、更新 三个动作进行源码分析。
方法
Load 查询
该方法源码结构如下：
func (m *Map) Load(key interface{}) (value interface{}, ok bool) { // 因read只读，线程安全，优先读取 read, _ := m.read.Load().(readOnly) e, ok := read.m[key] // 如果read没有，并且dirty有新数据，那么去dirty中查找（read.amended=true：dirty和read数据不一致） if !ok && read.amended { m.mu.Lock() // 双重检查（原因是前文的if判断和加锁非原子的，害怕这中间发生故事） read, _ = m.read.Load().(readOnly) e, ok = read.m[key] // 如果read中还是不存在，并且dirty中有新数据 if !ok && read.amended { e, ok = m.dirty[key] // m计数+1 m.missLocked() } m.mu.Unlock() } // !ok && read.amended=false：dirty和read数据是一致的，read 和 dirty 中都不存在，返回nil if !ok { return nil, false } // ok && read.amended=true：dirty和read数据不一致，dirty存在但read不存在该key，直接返回dirty中数据~ return e.load()}
// 读取数据func (e *entry) load() (value any, ok bool) { p := atomic.LoadPointer(&e.p) if p == nil || p == expunged { return nil, false } return *(*any)(p), true}
func (m *Map) missLocked() { m.misses++ if m.misses < len(m.dirty) { return } // 将dirty置给read，因为穿透概率太大了(原子操作，耗时很小) m.read.Store(readOnly{m: m.dirty}) m.dirty = nil m.misses = 0}
复制代码
read.amended=true 含义为 dirty 和 read 数据不一致。
当 Load 方法在 read map 中没有命中（miss）目标 key 时，该方法会再次尝试在 dirty 中继续匹配 key；无论 dirty 中是否匹配到，Load 方法都会在锁保护下调用 missLocked 方法增加 misses 的计数（+1）；当计数器 misses 值到达 len(dirty)阈值时，则将 dirty 中的元素整体更新到 read，且 dirty 自身变为 nil。
注意点：
Delete 删除
func (m *Map) Delete(key interface{}) { // 读出read，断言为readOnly类型 read, _ := m.read.Load().(readOnly) e, ok := read.m[key] // 如果read中没有，并且dirty中有新元素，那么就去dirty中去找。这里用到了amended，当read与dirty不同时为true，说明dirty中有read没有的数据。 if !ok && read.amended { m.mu.Lock() // 再检查一次，因为前文的判断和锁不是原子操作，防止期间发生了变化。 read, _ = m.read.Load().(readOnly) e, ok = read.m[key] if !ok && read.amended { // 直接删除 delete(m.dirty, key) } m.mu.Unlock() } if ok { // 如果read中存在该key，则将该value 赋值nil（采用标记的方式删除！） e.delete() }}
func (e *entry) delete() (hadValue bool) { for { // 再次加载数据的指针，如果指针为空或已被标记删除，那么返回false，删除失败 p := atomic.LoadPointer(&e.p) if p == nil || p == expunged { return false } // 原子操作 if atomic.CompareAndSwapPointer(&e.p, p, nil) { return true } }}
复制代码
delete(m.dirty, key)这里采用直接删除 dirty 中的元素，而不是先查再删，这样的删除成本低。读一次需要寻找，删除也需要寻找，无需重复操作。
通过延迟删除对 read 中的值域先进行标记：将 read 中目标 key 对应的 value 值置为 nil（e.delete()→将 read=map[interface{}]*entry 中的值域*entry 置为 nil）
Store 更新写入
func (m *Map) Store(key, value interface{}) { // 如果m.read存在这个key，并且没有被标记删除，则尝试更新。 read, _ := m.read.Load().(readOnly) if e, ok := read.m[key]; ok && e.tryStore(&value) { return } // 如果read不存在或者已经被标记删除 m.mu.Lock() read, _ = m.read.Load().(readOnly) if e, ok := read.m[key]; ok { // read 存在该key // 如果read值域中entry已删除且被标记为expunge，则表明dirty没有key，可添加入dirty，并更新entry if e.unexpungeLocked() { // 加入dirty中，这里是指针 m.dirty[key] = e } // 更新value值 e.storeLocked(&value) } else if e, ok := m.dirty[key]; ok { // dirty 存在该 key，更新 e.storeLocked(&value) } else { // read 和 dirty都没有 // 如果read与dirty相同，则触发一次dirty刷新（因为当read重置的时候，dirty已置为 nil了） if !read.amended { // 将read中未删除的数据加入到dirty中 m.dirtyLocked() // amended标记为read与dirty不相同，因为后面即将加入新数据。 m.read.Store(readOnly{m: read.m, amended: true}) } m.dirty[key] = newEntry(value) } m.mu.Unlock()}
// 将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)) // 遍历read。 for k, e := range read.m { // 通过此次操作，dirty中的元素都是未被删除的，可见标记为expunged的元素不在dirty中！！！ if !e.tryExpungeLocked() { m.dirty[k] = e } }}
// 判断entry是否被标记删除，并且将标记为nil的entry更新标记为expungefunc (e *entry) tryExpungeLocked() (isExpunged bool) { p := atomic.LoadPointer(&e.p) for p == nil { // 将已经删除标记为nil的数据标记为expunged if atomic.CompareAndSwapPointer(&e.p, nil, expunged) { return true } p = atomic.LoadPointer(&e.p) } return p == expunged}
// 对entry尝试更新 （原子cas操作）func (e *entry) tryStore(i *interface{}) bool { p := atomic.LoadPointer(&e.p) if p == expunged { return false } for { if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) { return true } p = atomic.LoadPointer(&e.p) if p == expunged { return false } }}
// read里 将标记为expunge的更新为nilfunc (e *entry) unexpungeLocked() (wasExpunged bool) { return atomic.CompareAndSwapPointer(&e.p, expunged, nil)}
// 更新entryfunc (e *entry) storeLocked(i *interface{}) { atomic.StorePointer(&e.p, unsafe.Pointer(i))}
复制代码
需要注意的是 最好不要用占用内存比较大的类型作为 key，因为 sync.Map 软删除并不会立刻将 key-value 删除掉，只是 value 置为了 nil，所以大 key 有内存泄露的危险。
对于高频读写少的情况下，sync.Map 基本时无锁情况下完成。但是对于写操作比较频繁的情况下，如果 read map 中拿不到数据，就会降级为加锁获取，然后 misses 增长变化速度势必比较快，连锁反应 dirty map 晋升为 read map 的操作也会比较频繁，其性能也势必会下降。所以写频繁的场景下 sync.Map 还是需要慎用。
评论