忍不了！下次面试再问sync.Map的原理你就这么说！sync.Map为什么是并发安全的？写的时候是写dirty还是写r

站长

2024年09月26日 00:04 · 阅读数 52

「第15期」距离大叔的80期小目标还有65期，搁了一段时间的大叔又回来了～今天大叔要跟大家分享基础知识点是 —— sync.Map。源于有小伙伴私信大叔说面试的时候被问到sync.Map相关知识点，为什么sync.Map是并发安全的？它是如何读的？如何存储的？却答不上来！结果一面就挂了，可惜可惜。其实面试被 狠抠细节！ 是常态，所以基础还是得夯实。下面一起看看吧。

sync.Map是并发安全的

使用的时候都知道 sync.Map 是并发安全的，被问到为什么它是并发安全的时候，却支支吾吾答不出个所以然来。

其实仔细看过源码就会发现，其核心思想是充分利用了原子操作和 锁 机制。比如：atomic.CompareAndSwapPointer 和 Mutex互斥锁。特别是在写的时候，两者相互配合，确保并发的安全性。

本文将从源码的角度详细分析其数据结构以及读写的实现细节。

文章最后总结了sync.Map在面试中常问的几个问题，看过这篇文章，相信答案能脱口而出。

Map的数据结构：

type Map struct {
    // 加锁作用，保护 dirty 字段
    mu Mutex
    // 只读的数据，实际数据类型为 readOnly
    read atomic.Value
    // 最新写入的数据
    dirty map[interface{}]*entry
    // 计数器，每次需要读 dirty 则 +1
    misses int
}

readOnly 的数据结构

type readOnly struct {
    // 内建 map
    m  map[interface{}]*entry
    // 表示 dirty 里存在 read 里没有的 key，通过该字段决定是否加锁读 dirty
    amended bool
}

Map 常用的有以下方法：

Load：读取指定 key 返回 value
Store：存储（增或改）key-value
Delete：删除指定 key
Range：遍历所有键值对，参数是回调函数

源码分析

Load实现

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 首先尝试从 read 中读取 readOnly 对象
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]

    // 如果不存在则尝试从 dirty 中获取
    if !ok && read.amended {
        m.mu.Lock()
        // 由于上面 read 获取没有加锁，为了安全再检查一次
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]

        // 确实不存在则从 dirty 获取
        if !ok && read.amended {
            e, ok = m.dirty[key]
            // 调用 miss 的逻辑
            m.missLocked()
        }
        m.mu.Unlock()
    }

    if !ok {
        return nil, false
    }
    // 从 entry.p 读取值
    return e.load()
}

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {
        return
    }
    // 当 miss 积累过多，会将 dirty 存入 read，然后 将 amended = false，且 m.dirty = nil
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

// 加载值时，如果该值被标记为删除，直接返回nil
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
}

读取过程：

首先尝试从 read 中读取
如果read中能读到，直接返回
如果该key在read中不存在，且在dirty中存在：

- 加锁，
- 由于上面 read 获取没有加锁，为了安全需要再对read再做一次读取检查
- 如果read能够读取到，解锁，直接返回读取结果
- 如果确实read中不存在，dirty中存在，则从 dirty 获取
- 更新穿透读次数，如果穿透读的次数达到一定数量（大于或等于dirty的长度），将dirty中的数据同步到read中，并清空dirty，同时调整穿透次数为0，
- 解锁，返回读取结果

如果dirty中也不存在，直接返回nil
在返回读取结果时，如果发现该对象已经被标记为删除或者值对象指针被指向一个nil，直接返回nil

Store

func (m *Map) Store(key, value interface{}) {
    read, _ := m.read.Load().(readOnly)
    // 如果 read 里存在，则尝试存到 entry 里
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }

    // 如果上一步没执行成功，则要分情况处理
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    // 和 Load 一样，重新从 read 获取一次
    if e, ok := read.m[key]; ok {
        // 情况1:存在read中，
        // 如果所读的项已经被标记为删除，需要把删除标记去掉，并重新写入dirty，因为dirty中不存在被标记删除的对象
        if e.unexpungeLocked() {
            m.dirty[key] = e
        }
        // 用值更新 entry
        e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok {
        // 情况 2：read 里不存在，但 dirty 里存在，则用值更新 entry
        e.storeLocked(&value)
    } else {
        // 情况 3：read 和 dirty 里都不存在
        if !read.amended {
            // 如果 amended == false，
            // 如果dirty为空，则调用 dirtyLocked 将 read 拷贝到 dirty（除了被标记删除的数据）
            m.dirtyLocked()
            // 然后将 amended 改为 true
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        // 将新的键值存入 dirty
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
}

func (e *entry) tryStore(i *interface{}) bool {
    for {
        p := atomic.LoadPointer(&e.p)
        if p == expunged {
            return false
        }
        if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
            return true
        }
    }
}

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

func (e *entry) storeLocked(i *interface{}) {
    atomic.StorePointer(&e.p, unsafe.Pointer(i))
}

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 {
        // 判断 entry 是否被删除，否则就存到 dirty 中
        if !e.tryExpungeLocked() {
            m.dirty[k] = e
        }
    }
}

func (e *entry) tryExpungeLocked() (isExpunged bool) {
    p := atomic.LoadPointer(&e.p)
    for p == nil {
        // 如果有 p == nil（即键值对被 delete），则会在这个时机被置为 expunged
        if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
            return true
        }
        p = atomic.LoadPointer(&e.p)
    }
    return p == expunged
}

存储过程：

如果read中存在，且该对象在read中未被标识为删除，直接存到read的对象中
如果第一步未成功，需要分情况处理，接下来的操作需要在加锁环境下进行

- 加锁
- 再次尝试从read中获取该key对应的对象，如果该对象存在：

- - 说明该key已经被标识为删除，需要把该删除标识去掉，同时把该对象的地址初始化为nil
  - 重新将该对象写入到dirty中

- 如果该key不存在read中，则判断是否存在dirty中，如果存在，直接更新dirty中的值
- 如果该key 在 read 和 dirty 里都不存在

- - 如果 read 的 amended 的值为 false，且dirty是空的，需要把read中未被标识为删除的对象拷贝到dirty中；同时将read的 amended 属性值设置为 true，表示 dirty 中包含一些不存在read中的key
  - 将key和值对象存到dirty中

- 释放锁

Range

func (m *Map) Range(f func(key, value any) bool) {
	// We need to be able to iterate over all of the keys that were already
	// present at the start of the call to Range.
	// If read.amended is false, then read.m satisfies that property without
	// requiring us to hold m.mu for a long time.
	read, _ := m.read.Load().(readOnly)
	if read.amended {
		// m.dirty contains keys not in read.m. Fortunately, Range is already O(N)
		// (assuming the caller does not break out early), so a call to Range
		// amortizes an entire copy of the map: we can promote the dirty copy
		// immediately!
		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
		}
	}
}

遍历过程：

如果 dirty 里存在 read 里没有的 key，解锁把 dirty 的数据同步到 read 中，并清空 dirty 和初始化穿透读的次数为0，解锁
直接用 for range 遍历read中的数据，并调用传过来的函数

Delete

func (m *Map) Delete(key interface{}) {
    m.LoadAndDelete(key)
}

// LoadAndDelete 作用等同于 Delete，并且会返回值与是否存在
func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
    // 获取逻辑和 Load 类似，read 不存在则查询 dirty
    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]
            // 直接删除dirty中对应的key
            delete(m.dirty, key)
            m.missLocked()
        }
        m.mu.Unlock()
    }
    // 查询到 entry 后执行删除
    if ok {
        // 将 entry.p 标记为 nil，数据并没有实际删除
        // 真正删除数据并被被置为 expunged，是在 Store 的 tryExpungeLocked 中
        return e.delete()
    }
    return nil, false
}

func (e *entry) delete() (value any, ok bool) {
	for {
		p := atomic.LoadPointer(&e.p)
		if p == nil || p == expunged {
			return nil, false
		}
		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
			return *(*any)(p), true
		}
	}
}

删除过程

如果 key 在 read 中不存在，但 dirty 中存在：

- 加锁
- 直接删除dirty中的值对象，并更新穿透读次数，如果穿透读的次数达到一定数量（大于或等于dirty的长度），将dirty中的数据同步到read中，并清空dirty，同时调整穿透次数为0
- 解锁

不管key存在read中还是dirty中，最终都会将该key对应的对象的指针地址设置为nil，（真正设置为 expunged 删除标识是在 store时，在给dirty同步read数据时，针对nil对象会把该对象设置为 expunged 标识）

总结

sync.Map之所以是并发安全的，其核心思想是充分利用了 atmoic 和 mutex 互斥锁的配合，比如 atomic.CompareAndSwapPointer

read map 由于是原子包托管，主要负责高性能，但是无法保证拥有全量的 key，因为对于新增 key，会首先加到 dirty 中，所以 read 某种程度上，类似于一个 key 的快照，这个快照在某些情况下可能是全量快照。
dirty map 拥有全量的 key，当 Store 操作要新增一个之前不存在的 key 的时候，会先增加到 dirty 中的。
在查找指定的 key 的时候，总会先去 read map 中寻找，并不需要锁定互斥锁。只有当 read 中没有，但 dirty 中可能会有这个 key 的时候，才会在锁的保护下去访问 dirty。
在存储键值对的时候，只要 read 中已存有这个 key，并且该键值对未被标记为 expunged，就会把新值存到里面并直接返回，这种情况下也不需要用到锁。
read 和 dirty 之间是会互相转换的，在 dirty 中查找 key 对次数足够多的时候，sync.Map 会把 dirty 直接作为 read，即触发 dirty->read 的转变，此时 read 中拥有全量的 key。同时在某些情况，也会出现 read->dirty 的转变，比如当写入一个key在read 和 dirty中都不存在时，如果此时diry为空，需要把read中未被标记为删除的数据同步到dirty。

具体操作流程

通过 read 和 dirty 两个字段将读写分离。实际上也不是正在的读写分离，在写入数据时，还是尝试往read中写（前提是，这个key存在read中，且没有被标识为删除）
读取时会先查询 read，不存在再查询 dirty，查询dirty过程需要加锁；
写入时，如果read存在该key，会尝试先写read，前提该key未被标识为删除；否则，则分情况写入：

- 再次尝试从read中获取该key对应的对象，如果该对象存在：

- - 说明该key已经被标识为删除，需要把该删除标识去掉，同时把该对象的地址初始化为nil
  - 重新将该对象写入到dirty中

- 如果该key不存在read中，则判断是否存在dirty中，如果存在，直接更新dirty中的值
- 如果该key 在 read 和 dirty 里都不存在

- - 如果 read 的 amended 的值为 false，且dirty是空的，需要把read中未被标识为删除的对象拷贝到dirty中，并对read中为nil对象设置为为删除标识；同时将read的 amended 属性值设置为 true，表示 dirty 中包含一些不存在read中的key
  - 将key和值对象存到dirty中

读取 read 并不需要加锁，而读、写或删除 dirty 都需要加锁
另外有 misses 字段来统计 read 被穿透的次数（被穿透指需要读 dirty 的情况），超过一定次数（dirty的长度）则将 dirty 数据同步到 read 上
对于删除数据，如果key存在read还是存在dirty中，都会将该值对象的指针地址设置为 nil，如果 key 在 read 中不存在，但 dirty 中存在，直接删除dirty中的值对象，并更新穿透读次数，如果穿透读的次数达到一定数量（大于或等于dirty的长度），将dirty中的数据同步到read中，并清空dirty，同时调整穿透次数为0

问题1：有人说既写read，又写dirty，会不会出现同一个key在 read 和 dirty中数据不一致的问题？

答案是不会，原因是如果发生dirty 同步数据到 read 操作，dirty会被清空；如果发生read同步数据到dirty操作（当写入一个既不存在read也不存在dirty，且dirty为空的情况下会发生read同步dirty操作），dirty会得到read中未被删除的所有最新数据，该同步过程是加锁的，确保并发读写的安全性

问题2: 删除时 e.p 设置成了 nil 还是 expunged？

答案是：不管 key 是在 read 中还是 dirty 中，最后都调用了 e.delete() 方法，将 e.p 设置为 nil

问题3：什么时候 e.p 由 nil 变成 expunged

答案是：read->dirty 重塑的时候。当写入一个key的时候，如果该key 在 read 和 dirty 里都不存在，且 dirty 为 nil，需要把read中未被标识为删除（expunged）的对象拷贝到dirty中，并对read中为nil对象设置为为删除标识(expunged)

问题4：既然 nil 表示标记删除，expunged 的意义是什么

避免了 nil 值可能带来的歧义：nil 值可能是键的有效值，因此不能简单地依靠 nil 值来判断键是否存在或已被删除
提高了删除操作的效率：直接将值标记为 expunged，而不是删除键值对，可以避免重新分配内存或进行其他复杂的操作，从而提高了删除操作的效率
保持了并发安全性：通过将键的对应值设置为 expunged，sync.Map 在并发环境中仍然能够保持正确的状态和操作一致性

转载自:https://juejin.cn/post/7411452970082730021