乐趣区

深入理解GosyncMap原理剖析

jiezi

Map is like a Go map[interface{}]interface{} but is safe for concurrent use

by multiple goroutines without additional locking or coordination.

Loads, stores, and deletes run in amortized constant time.

上面一段是官方对sync.Map 的描述，从描述中看，sync.Map 跟map 很像，sync.Map 的底层实现也是依靠了map，但是sync.Map 相对于 map 来说，是并发安全的。

1. 结构概览

1.1. sync.Map

sync.Map 的结构体了

type Map struct {
    mu Mutex

  // 后面是 readOnly 结构体，依靠 map 实现，仅仅只用来读
    read atomic.Value // readOnly

    // 这个 map 主要用来写的，部分时候也承担读的能力
    dirty map[interface{}]*entry

    // 记录自从上次更新了 read 之后，从 read 读取 key 失败的次数
    misses int
}

1.2. readOnly

sync.Map.read 属性所对应的结构体了，这里不太明白为什么不把 readOnly 结构体的属性直接放入到 sync.Map 结构体里

type readOnly struct {
  // 读操作所对应的 map
    m       map[interface{}]*entry
  // dirty 是否包含 m 中不存在的 key
    amended bool // true if the dirty map contains some key not in m.
}

1.3. entry

entry 就是 unsafe.Pointer，记录的是数据存储的真实地址

type entry struct {p unsafe.Pointer // *interface{}
}

1.4. 结构示意图

通过上面的结构体，我们可以简单画出来一个结构示意图

2. 流程分析

我们通过下面的动图（也可以手动 debug），看一下在我们执行Store Load Delete 的时候，这个结构体的变换是如何的，先增加一点我们的认知

func main() {m := sync.Map{}
    m.Store("test1", "test1")
    m.Store("test2", "test2")
    m.Store("test3", "test3")
    m.Load("test1")
    m.Load("test2")
    m.Load("test3")
    m.Store("test4", "test4")
    m.Delete("test")
    m.Load("test")
}

以上面代码为例，我们看一下 m 的结构变换

3. 源码分析

3.1. 新增 key

新增一个 key value，通过 Store 方法来实现

func (m *Map) Store(key, value interface{}) {read, _ := m.read.Load().(readOnly)
  // 如果这个 key 存在，通过 tryStore 更新
    if e, ok := read.m[key]; ok && e.tryStore(&value) {return}
  // 走到这里有两种情况，1. key 不存在 2. key 对应的值被标记为 expunged，read 中的 entry 拷贝到 dirty 时，会将 key 标记为 expunged，需要手动解锁
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
    // 第二种情况，先解锁，然后添加到 dirty
        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.
            m.dirty[key] = e
        }
        e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok {
    // m 中没有，但是 dirty 中存在，更新 dirty 中的值
        e.storeLocked(&value)
    } else {
    // 如果 amend==false，说明 dirty 和 read 是一致的，但是我们需要新加 key 到 dirty 里面，所以更新 read.amended
        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.
      // 这一步会将 read 中所有的 key 标记为 expunged
            m.dirtyLocked()
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()}

3.1.1. tryLock

func (e *entry) tryStore(i *interface{}) bool {p := atomic.LoadPointer(&e.p)
  // 这个 entry 是 key 对应的 entry，p 是 key 对应的值，如果 p 被设置为 expunged，不能直接更新存储
    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}
    }
}

tryLock 会对 key 对应的值，进行判断，是否被设置为了 expunged，这种情况下不能直接更新

3.1.2. dirtyLock

这里就是设置 expunged 标志的地方了，而这个函数正是将 read 中的数据同步到 dirty 的操作

func (m *Map) dirtyLocked() {
  // dirty != nil 说明 dirty 在上次 read 同步 dirty 数据后，已经有了修改了，这时候 read 的数据不一定准确，不能同步
    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 {
    // 这里调用 tryExpungeLocked 来给 entry，即 key 对应的值 设置标志位
        if !e.tryExpungeLocked() {m.dirty[k] = e
        }
    }
}

3.1.3. tryExpungeLocked

通过原子操作，给 entry，key 对应的值设置 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
}

3.1.4. unexpungeLocked

func (e *entry) unexpungeLocked() (wasExpunged bool) {return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

根据上面分析，我们发现，在新增的时候，分为四种情况：

  1. key 原先就存在于 read 中，获取 key 所对应内存地址，原子性修改
  2. key 存在，但是 key 所对应的值被标记为 expunged，解锁，解除标记，并更新 dirty 中的 key，与 read 中进行同步，然后修改 key 对应的值
  3. read 中没有 key，但是 dirty 中存在这个 key，直接修改 dirty 中 key 的值
  4. read 和 dirty 中都没有值，先判断自从 read 上次同步 dirty 的内容后有没有再修改过 dirty 的内容，没有的话，先同步 read 和 dirty 的值，然后添加新的 key value 到 dirty 上面

当出现第四种情况的时候，很容易产生一个困惑：既然 read.amended == false，表示数据没有修改，为什么还要将 read 的数据同步到 dirty 里面呢？

这个答案在Load 函数里面会有答案，因为，read 同步 dirty 的数据的时候，是直接把 dirty 指向 map 的指针交给了 read.m，然后将 dirty 的指针设置为 nil，所以，同步之后，dirty 就为 nil

下面看看具体的实现

3.2. 读取（Load）

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
  // 如果 read 的 map 中没有，且存在修改
    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.)
    // 再查找一次，有可能刚刚将 dirty 升级为 read 了
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
      // 如果 amended 还是处于修改状态，则去 dirty 中查找
            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.
      // 增加 misses 的计数，在计数达到一定规则的时候，触发升级 dirty 为 read
            m.missLocked()}
        m.mu.Unlock()}
  // read dirty 中都没有找到
    if !ok {return nil, false}
  // 找到了，通过 load 判断具体返回内容
    return e.load()}

func (e *entry) load() (value interface{}, ok bool) {p := atomic.LoadPointer(&e.p)
  // 如果 p 为 nil 或者 expunged 标识，则 key 不存在
    if p == nil || p == expunged {return nil, false}
    return *(*interface{})(p), true
}

为什么找到了 p，但是 p 对应的值为 nil 呢？这个答案在后面解析 Delete 函数的时候会被揭晓

3.2.1. missLocked

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {return}
  // 直接把 dirty 的指针给 read.m，并且设置 dirty 为 nil，这里也就是 Store 函数的最后会调用 m.dirtyLocked 的原因
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

3.3. 删除（Delete）

这里的删除并不是简单的将 key 从 map 中删除

func (m *Map) Delete(key interface{}) {read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
  // read 中没有这个 key，但是 Map 被标识修改了，那么去 dirty 里面看看
    if !ok && read.amended {m.mu.Lock()
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
      // 调用 delete 删除 dirty 的 map，delete 会判断 key 是否存在的
            delete(m.dirty, key)
        }
        m.mu.Unlock()}
  // 如果 read 中存在，则假删除
    if ok {e.delete()
    }
}

func (e *entry) delete() (hadValue bool) {
    for {p := atomic.LoadPointer(&e.p)
    // 已经是被删除了，不需要管了
        if p == nil || p == expunged {return false}
    // 原子性 将 key 的值设置为 nil
        if atomic.CompareAndSwapPointer(&e.p, p, nil) {return true}
    }
}

根据上面的逻辑可以看出，删除的时候，存在以下几种情况

  1. read 中没有，且 Map 存在修改，则尝试删除 dirty 中的 map 中的 key
  2. read 中没有，且 Map 不存在修改，那就是没有这个 key，无需操作
  3. read 中有，尝试将 key 对应的值设置为 nil，后面读取的时候就知道被删了，因为 dirty 中 map 的值跟 read 的 map 中的值指向的都是同一个地址空间，所以，修改了 read 也就是修改了 dirty

3.3. 遍历（Range）

遍历的逻辑就比较简单了，Map 只有两种状态，被修改过和没有修改过

修改过：将 dirty 的指针交给 read，read 就是最新的数据了，然后遍历 read 的 map

没有修改过：遍历 read 的 map 就好了

func (m *Map) Range(f func(key, value interface{}) bool) {read, _ := m.read.Load().(readOnly)
    if read.amended {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}
    }
}

3.4. 适用场景

在官方介绍的时候，也对适用场景做了说明

The Map type is optimized for two common use cases:

(1) when the entry for a given key is only ever written once but read many times, as in caches that only grow,

(2) when multiple goroutines read, write, and overwrite entries for disjoint sets of keys.

In these two cases, use of a Map may significantly reduce lock contention compared to a Go map paired with a separate Mutex or RWMutex.

通过对源码的分析来理解一下产生这两条规则的原因：

读多写少：读多写少的环境下，都是从 read 的 map 去读取，不需要加锁，而写多读少的情况下，需要加锁，其次，存在将 read 数据同步到 dirty 的操作的可能性，大量的拷贝操作会大大的降低性能

读写不同的 key：sync.Map 是针对 key 的值的原子操作，相当于加锁加载 key 上，所以，多个 key 的读写是可以同时并发的

退出移动版