Go源码解读——sync.Map

源码

CAS

CompareAndSwap（CAS）是非阻塞原子操作，它有可能会失败（有其他协程在这期间修改了这个值）

方法调用者.CompareAndSwap(old, new) ：如果当前值等于old则修改为 new，返回 true；否则什么也不做，返回 false

CAS + for 自旋重试 模式：

• 保证即使多个协程并发执行，只会有一个成功修改

• 失败的协程自动重新读取并重试，直到成功或发现值已不可修改

• 无锁但线程安全

结构体

type Map struct {
    // 互斥锁，保护dirty map和misses字段的访问
    mu Mutex
    
    // 读结构，安全并发读写的指针类型，指向结构体readOnly
    read atomic.Pointer[readOnly]
    
    // 写结构，标准go map，保存已被修改但尚未同步到read的数据
    dirty map[any]*entry
    
    // 计数器，统计未命中次数，达到阈值后，会将dirty中的数据同步到read，重置misses
    misses int
}
// 未命中：指在read中未找到某个key，需要到dirty中查找

// 只读变量
type readOnly struct {
    // 存储symc.Map中的键值对，提供只读访问
    m       map[any]*entry
    // 标记read是否被修改过
    // flase表示没有脏数据，所有键值都在read.m中可以直接访问；true表示有些脏数据在dirty中
    amended bool 
}

// 插槽（存储value p）
type entry struct {
    // 充当每个键值对的插槽，通过atomic.Pointer原子性来避免加锁（更高效），p可指向任意类型
    p atomic.Pointer[any]
}

// 标识一个 entry 已被“移除”
// 该状态的引入是为了优化内存和性能管理
var expunged = new(any)

函数

内部函数

// 加载（获取）只读map，并返回
func (m *Map) loadReadOnly() readOnly {
    if p := m.read.Load(); p != nil {
        return *p
    }
    return readOnly{}
}

// 加载初始化dirty
func (m *Map) dirtyLocked() {
    if m.dirty != nil {
        return
    }

    read := m.loadReadOnly()
    m.dirty = make(map[any]*entry, len(read.m))
    // 遍历只读map
    for k, e := range read.m {
        // 如果值为nil，则更新为已删除；如果值有效，则复制键值对到dirty中
        if !e.tryExpungeLocked() {
            m.dirty[k] = e
        }
    }
}

// 判断key对应的值是否失效，在dirtyLocked函数中使用
// e.p旧值为nil并且将其更新为已删除 或者 e.p旧值为已删除，返回true
// e.p旧值不为nil或者不为已删除，e.p旧值为有效的，返回false
func (e *entry) tryExpungeLocked() (isExpunged bool) {
    p := e.p.Load()
    for p == nil {
        // 如果e.p当前值为nil，则将e.p改为expunged，返回是否赋值成功
        if e.p.CompareAndSwap(nil, expunged) {
                return true
        }
        // 此处说明其他协程修改了值，导致CAS失败。则重新获取e.p，重新for循环判断
        p = e.p.Load()
    }
    return p == expunged
}

// read未命中时的处理
func (m *Map) missLocked() {
    // 增加计数器
    m.misses++
    // 检查未命中次数
    if m.misses < len(m.dirty) {
        return     
    }
    // 将dirty提升为新的只读map，随后dirty置空，计数器置0
    m.read.Store(&readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

// 删除键值对，如果e.p值为nil或expunged已删除则不处理，否则赋值为nil 
func (e *entry) delete() (value any, ok bool) {
    for {
       p := e.p.Load()
       if p == nil || p == expunged {
          return nil, false
       }
       if e.p.CompareAndSwap(p, nil) {
          return *p, true
       }
    }
}

// 获取e.p，值
func (e *entry) load() (value any, ok bool) {
    p := e.p.Load()
    // 如果值等于nil或者该字段key已经标记被删除, 则返回空
    if p == nil || p == expunged {
        return nil, false
    }
    return *p, true
}

// 将entry中的旧值更新为新值，旧值有效才更新
func (e *entry) tryCompareAndSwap(old, new any) bool {
    // 获取entry中的value
    p := e.p.Load()
    // 如果值等于nil或者该字段key已经标记被删除
    // 如果*p != old则表示当前值与期望的旧值不同，则不执行交换操作
    if p == nil || p == expunged || *p != old {
            return false
    }

    // 开始尝试执行更新操作
    // 将要更新成的新值new赋值给nc
    nc := new
    for {
        // 如果e.p尚未被其他线程修改，则赋值为&nc
        if e.p.CompareAndSwap(p, &nc) {
            return true
        }
        
        // 如果失败，说明其他线程在此期间修改了e.p，需要重新加载最新值
        p = e.p.Load()
        if p == nil || p == expunged || *p != old {
            return false
        }
    }
}

// 加载或存储：如果e.p旧值有效，则直接返回旧值；值为已删除，则不做处理；值为nil则尝试将e.p更新为&i
// actual返回实际的值，loaded表示是否是旧值，ok表示这次操作是否成功
func (e *entry) tryLoadOrStore(i any) (actual any, loaded, ok bool) {
    p := e.p.Load()
    // 如果entry已经是被标记为删除则不作任何处理
    if p == expunged {
        return nil, false, false
    }
    // 如果能成功加载 则返回加载出来的值
    if p != nil {
        return *p, true, true
    }

    ic := i
    for {
        // 如果原来值为空, 则将&ic赋值给e.p，返回是否赋值成功
        if e.p.CompareAndSwap(nil, &ic) {
            return i, false, true
        }
        // 此处说明赋值失败，与其他协程产生并发冲突，因此重新获取e.p的最新值
        // 如果p被标记为删除则不作任何处理, 返回false
        p = e.p.Load()
        if p == expunged {
            return nil, false, false
        }
        // 如果p不为空, 则返回数据
        if p != nil {
            return *p, true, true
        }
    }
}

外部函数

// 获取值，先从只读map找，再去dirty中找
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 先加载只读map
    read, _ := m.read.Load().(readOnly)
    // 从只读map中获取key对应的value
    e, ok := read.m[key]
    
    // 如果从read.m中没有获取到值，并且readOnly.amended为true（有脏数据在dirty中）
    if !ok && read.amended {
       // 加锁
       m.mu.Lock() 
       
       // 再从只读map中查找，因为加锁时可能有其他协程向其中添加数据
       read, _ = m.read.Load().(readOnly)
       e, ok = read.m[key]
       // 如果没有找到key并且只读map有脏数据
       if !ok && read.amended {
          // 从dirty中获取值，ok记录是否获取到
          e, ok = m.dirty[key]
          // 只读map未命中，进行相关处理
          m.missLocked()
       }
       
       // 释放锁
       m.mu.Unlock()
    }
    // 如果dirty中也没有找到
    if !ok {
       return nil, false
    }
    return e.load()
}

// 清空map
func (m *Map) Clear() {
    // 加载只读map
    read := m.loadReadOnly()

    // 如果只读map为空且没有脏数据则直接返回
    if len(read.m) == 0 && !read.amended {
       return
    }

    // 加锁
    m.mu.Lock()
    defer m.mu.Unlock()

    // 再次加载只读map
    read = m.loadReadOnly()
    // 如果只读map不为空或者有脏数据
    if len(read.m) > 0 || read.amended {
       // 将只读map更新为空
       m.read.Store(&readOnly{})
    }

    // 清空dirty，并重置misses计数
    clear(m.dirty)
    m.misses = 0
}

// e.p旧值为已删除，将其更新为nil，返回true
// e.p旧值不为已删除 或者 更新失败，返回false
func (e *entry) unexpungeLocked() (wasExpunged bool) {
    return e.p.CompareAndSwap(expunged, nil)
}

// 加载或存储：根据指定的键值对去查找，如果存在则更新为新值，如果不存在则插入
// loaded为true表示是查询到，false表示未查询到从而新插入
func (m *Map) LoadOrStore(key, value any) (actual any, loaded bool) {
    // 从只读map中查找key
    read := m.loadReadOnly()
    // 如果查询到
    if e, ok := read.m[key]; ok {
       // 尝试更新key对应的值
       actual, loaded, ok := e.tryLoadOrStore(value)
       // 如果更新成功（旧值不为已删除），则直接返回
       if ok {
          return actual, loaded
       }
    }

    // 此处说明，只读map中没有查询到key，或者查询到但是更新失败（旧值为已删除）
    // 加锁
    m.mu.Lock()
    // 重新获取只读map
    read = m.loadReadOnly()
    // 如果只读map中查找到key
    if e, ok := read.m[key]; ok {
       // 将只读map中的旧值置nil（如果旧值为已删除），使其重新恢复
       if e.unexpungeLocked() {
          // 在dirty中添加此键值对
          m.dirty[key] = e
       }
       // 将的旧值（nil）更新为value（由于存储的是指针，所以只读map和dirty都会更新）
       actual, loaded, _ = e.tryLoadOrStore(value)
    } else if e, ok := m.dirty[key]; ok { // 如果只读map中没有，dirty中有
       // 更新dirty中key对应的value
       actual, loaded, _ = e.tryLoadOrStore(value)
       // 增加未命中计数器
       m.missLocked()
    } else { // 如果只读map和dirty中都没有key（在dirty中进行插入操作）
       if !read.amended { // 如果只读map中没有脏数据
          // 将只读map中有效的键值对拷贝进新的dirty中
          m.dirtyLocked()
          // 更新只读map，标记为已修改（有脏数据）
          m.read.Store(&readOnly{m: read.m, amended: true})
       }
       // 在dirty中插入要更新的键值对
       m.dirty[key] = newEntry(value)
       actual, loaded = value, false
    }
    m.mu.Unlock()

    return actual, loaded
}

// 删除键，先找只读map，存在则直接删除（软删除，置nil）；再找dirty，存在则直接删除（硬删除）
func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
    // 从只读map中查找键
    read := m.loadReadOnly()
    e, ok := read.m[key]
    // 如果在只读map中未找到，并且只读map被标记为有脏数据
    if !ok && read.amended {
       m.mu.Lock()
       // 防止加锁时其他协程操作过，所以重新获取只读map
       read = m.loadReadOnly()
       e, ok = read.m[key]
       // 如果在只读map中未找到，并且只读map被标记为有脏数据
       if !ok && read.amended {
          // 在dirty中查找并删除该键
          e, ok = m.dirty[key]
          delete(m.dirty, key)
          // 未命中，相关处理
          m.missLocked()
       }
       m.mu.Unlock()
    }

    // 如果只读map中键存在，则直接删除（置nil），只读和dirty会一起置nil
    if ok {
       return e.delete()
    }
    // 此处说明，只读map中键不存在并且只读map没有脏数据，则dirty中也不存在，则无需处理
    return nil, false
}

// 遍历map
func (m *Map) Range(f func(key, value any) bool) {
    // 加载只读map
    read := m.loadReadOnly()
    // 如果有脏数据
    if read.amended {
       // 加锁
       m.mu.Lock()
       read = m.loadReadOnly()
       if read.amended {
          // 将dirty提升为只读map，随后dirty置nil，计数清零
          read = readOnly{m: m.dirty}
          copyRead := read
          m.read.Store(&copyRead)
          m.dirty = nil
          m.misses = 0
       }
       m.mu.Unlock()
    }

    // 遍历只读map并执行回调
    for k, e := range read.m {
       v, ok := e.load()
       if !ok {
          continue // 跳过被删除的键
       }
       if !f(k, v) {
          break // 若回调返回 false，则提前退出
       }
    }
}

结构设计和流程

 ​​

只读map 和 dirty map 存储的都是指向同一个 *entry 的指针，entry 内部才真正存储具体值（通过原子变量 p）。因此，当只读 map 中的键值对拷贝到 dirty map 时，实际是共享同一个 entry 实例。后续无论从 read 还是 dirty 修改该值，都会影响同一份数据

总结

sync.Map 采用了“只读map”和“脏数据 dirty map”分离的方式。read字段是只读map（普通map+标识字段，标识dirty是否已初始化），用于大多数读操作，实现原子读取无需加锁；dirty字段是脏map（普通map），用于写操作和部分读未命中时进行操作，必须加锁才能访问

map中三种value：有效、nil（软删除，还可以重新被更新赋值使用）、已删除（定义的全局变量字段，表示已移除不能被使用，除非被unexpungeLocked()方法重新置nil），value中存储的是entry指针，所以在只读map中更新数据，dirty也会同步修改

dirty中记录了 上一次初始化dirty时只读map中的有效字段（非nil，非已删除）和 新加入的键值对

• 查、改、删操作时，先去只读map中查，查不到再去dirty中查，只要在任意一方查到则直接更新，在只读map中更新会同步到dirty中，保证dirty记录着数据的最新值，后续可直接提升为只读map。

  • 更新操作：

    • 如果只读map中找到。如果旧值为nil，则直接更新（dirty中也一定存在这个旧值，并且会同步更新）；如果旧值为已删除（dirty中一定不存在这个旧值），则调用unexpungeLocked()方法重新置nil，随后将key加入dirty，最后一起同步更新只读map和dirty

    • 如果只读map没找到，dirty中找到（说明是新添加进dirty的数据），则直接在dirty中更新

  • 删除操作

    • 只读map中找到，直接置nil（dirty也会同步置nil）

    • 只读map没找到，dirty找到，直接彻底删除

• 增操作，先根据只读map中的标识字段判断dirty是否已初始化，如果没有则重新初始化dirty（将只读map中nil改为已删除，将有效键值对拷贝进dirty），然后在dirty中插入新数据，最后把标识字段改为true表示dirty已初始化

dirty 提升：当 misses 次数（只读map未命中）超过阈值时，会将 dirty 提升为新的只读map，dirty置nil

Range()方法遍历map时，如果只读map标记dirty已初始化，则直接将dirty提升为只读map，随后遍历只读map

查/改流程

传参key value 先查，如果旧值有效则直接返回，否则恢复旧值使其置nil，再执行改更新操作

1. 从只读map查找key对应的entry

• 如果存在且entry.p不是 expunged已删除，直接尝试更新；

• 如果是expunged已删除，说明值已彻底删除 → 加锁处理；

      2. 加锁后再次检查只读map

• 如果entry还存在且不是 expunged已删除，则直接返回旧值（旧值有效）或更新（旧值为nil）；

• 如果entry还存在但是expunged已删除，尝试 unexpunge（将已删除重新置nil），把它加入 dirty，再次一起更新

• 如果entry不存在：

  • 检查 read.amended，如果是 true，则去只读map中查找或修改；否则说明不存在，执行增流程

增流程

创建 entry 插入 dirty，如果dirty不存在则会初始化，将只读map中的nil改为已删除，将有效键值拷贝进dirty

删流程

1. 尝试从只读map删除

• 找到则设置 entry.p = nil（标记逻辑删除），然后返回旧值（dirty也会被同步置nil）

      2. read 中找不到，判断 amended 是否为 true

• 若 true，则加锁去 dirty 中删除，dirty 中是直接从 map 删除键值对（彻底删除），删除后调用 missLocked()，如果 miss 次数太多，可能触发 dirty → read 的升级

dirty 的更新时机

dirty 一旦创建，不会主动清理，而是会：

1. 插入新key时，清洗只读map（将nil改为已删除），将只读map中的有效键值拷贝进新的dirty，在新的dirty中插入新key

2. 只读map中 有效key被更新（只读map中有效，则dirty中也一定存在），由于entry中存指针，所以只读map和dirty可以一起更新；标识被删除的key被unexpunge重置nil时，将其加入dirty，随后一起更新

3. misses次数达到阈值，dirty被提升为只读map，旧dirty置nil

4. Range()遍历时，如果只读map标识为有脏数据，则提升dirty为只读map，旧dirty置nil