Map

Architecture

图 1：sync.Map 主要结构关系图

sync.Map 是一种并发安全的 map 结构，其中核心字段及其关系如图 1 所示。

sync.Map 使用读写分离的思想结合内置 map 加锁实现了并发安全，其中 read 字段负责常用数据的存储，dirty 字段负责非常用数据的存储，misses 用来判断是否将 dirty 内存储的数据刷新到 read，具体结构如下所示。

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

sync.Map 通过使用 atomic.Value 原子类型来保证了常用数据存储操作的并发安全，因其与本章内容关系不大，因此在这里不做详细展开，只需了解 read 的类型实际上是 sync.readOnly 即可。

type readOnly struct {
    m       map[any]*entry
    amended bool 
}

amended 字段是用来判断数据是否是只存储在 dirty 中的 flag，同时可以注意到最终存储到 map 中的都是 entry 结构，其 p 字段存储了最终数据的指针，p 有 nil、expunged 和 otherwise 三种状态，其中 expunged 用来作为 entry 已经被 dirty 删除的标记。

var expunged = unsafe.Pointer(new(any))
type entry struct {
    p unsafe.Pointer 
}

Method

Load

sync.Map 提供了如 Load、Store、Delete、Range 等许多基础方法，让 sync.Map 的使用变得像普通 map 一样简单，下面是 Load 方法的执行逻辑。

func (m *Map) Load(key any) (value any, ok bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    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]
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load()
}

sync.Map 加载数据的情况共分为三种，L14 ~ L16 是 read 和 dirty 都未命中的情况；L17 是直接在 read 中命中数据的情况；L4 ~ L13 是指在 read 中读取不到但是在 dirty 中能够读取到数据的情况，这时会直接在 dirty 中读取数据，这里需要注意的是 L10 的函数，这个函数的作用是刷新 misses 字段的值，同时如果满足一定条件会将 dirty 中的数据刷新到 read 中。

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

L3 ~ L5 是指在 read 中命中并且 entry 未被删除的情况直接存储在 read 中；L8 ~ L12 是将 read 中命中的 entry 存储到 dirty 中并将数据存储到 entry；L13 ~ L14 是在 dirty 命中的 entry 中存储数据；L15 ~ L22 是将 dirty 初始化并将数据存储到 dirty 中。

func (m *Map) Store(key, value any) {
    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 {
        if e.unexpungeLocked() {
            m.dirty[key] = e
        }
        e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok {
        e.storeLocked(&value)
    } else {
        if !read.amended {
            m.dirtyLocked()
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
}

Delete

Delete 方法调用了 LoadAndDelete 方法，L8 ~ L18 是在数据只存在 dirty 中的情况下根据 key 值将entry 删除，同时尝试将最新数据刷新到 read；L19 ~ L21 是指在 read 中命中 entry，然后将 entry 中数据直接删除。

func (m *Map) Delete(key any) {
    m.LoadAndDelete(key)
}
func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    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]
            delete(m.dirty, key)
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if ok {
        return e.delete()
    }
    return nil, false
}

Range

Range 方法允许使用者提供处理数据的函数并通过一个 bool 类型来控制 sync.Map 遍历的中断，L3 ～ L13 是指在数据只存在于 dirty 的情况下将数据刷新到 read 中；L5 ～ L23 是真正执行 Range 函数使用者自定义数据处理函数的位置。

func (m *Map) Range(f func(key, value any) 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
        }
    }
}