【Go】sync.Map 源码（2）

昨天到了原生 map 不是并发安全的，为了安全地使用 map, 1.7 之后推出了 sync.Map 并分析了 Store 和 Load 地源码，今天看看 LoadOrStore 和 Random 地源码，并做个总结。。。┏┛墓┗┓...(((m -__-)m

sync.Map 源码（2）

LoadOrStore

LoadOrStore() 的作用是如果 key 存在，就 Load, 否则就 Store, 其逻辑与 Load 和 Store 基本一致，

代码语言：javascript复制

func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
    // 命中 read
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        actual, loaded, ok := e.tryLoadOrStore(value)
        if ok {
            return actual, loaded
        }
    }
  
    // 未命中read 或 `expunged`
    m.mu.Lock()
    // ...
    m.mu.Unlock()
    
    return actual, loaded
}

代码语言：javascript复制

func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) {
    p := atomic.LoadPointer(&e.p)
    if p == expunged {
        return nil, false, false
    }
    if p != nil {
        return *(*interface{})(p), true, true
    }
    
    // p == nil
    ic := i
    for {
        // 赋新值
        if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) {
            return i, false, true
        }
        // 已经被别的协程修改，重新判断
        p = atomic.LoadPointer(&e.p)
        if p == expunged {
            return nil, false, false
        }
        if p != nil {
            return *(*interface{})(p), true, true
        }
    }
}

如果 key 在 read 中，会进入 tryLoadOrStore：

e.p == expunged 时，说明 Key 已经被标记删除，这时为了同时更新 dirty，会延时到加锁后执行。
e.p != nil 时，说明 Key Value 存在，直接返回 Value
e.p == nil 时，说明键值对已经被删除，但还没有进行 dirty 的提升，会通过 CAS 赋新值（没有提升，也就不需要像第一种情况一样考虑 dirty），如果 CAS 没有通过，说明已经有其他协程修改了这个键值，再次判断其是 nil 或 expunged

read 没有命中或 entry.p == expunged 时，需要加锁对 dirty 进行操作，流程与 Store 完全一样，不再赘述。

代码语言：javascript复制

func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
    // Avoid locking if it's a clean hit.
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        actual, loaded, ok := e.tryLoadOrStore(value)
        if ok {
            return actual, loaded
        }
    }
    
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        if e.unexpungeLocked() {
            m.dirty[key] = e
        }
        actual, loaded, _ = e.tryLoadOrStore(value)
    } else if e, ok := m.dirty[key]; ok {
        actual, loaded, _ = e.tryLoadOrStore(value)
        m.missLocked()
    } else {
        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.
            m.dirtyLocked()
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        m.dirty[key] = newEntry(value)
        actual, loaded = value, false
    }
    m.mu.Unlock()
    
    return actual, loaded
}

Range

我们可以使用安全的 for-range 对一个原生的 map 进行随机遍历，但 Map 使用不了这种简单的方法，好在其提供了 Map.Range,可以通过回调的方式随机遍历其中的键值。

Range 接受一个回调函数，在调用时，Range 会把当前遍历到的键值对传给这个给回调 f, 当 f 返回 false 时，遍历结束。

Range 的源码很简单，为了保证遍历完整进行，在真正遍历之前，他会通过 double-checking 提升 dirty.

代码语言：javascript复制

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
        }
    }
}

总结

原生的 map 并不是并发安全的，在并发环境下使用原生 map 会直接导致一个 panic，为此，Go 官方从 1.7 之后添加了 sync.Map,用于支持并发环境下的键值对存取操作。

实现并发安全的两个思路分别是 原子操作 和加锁，原子操作由于是直接面向硬件的一组不可分割的指令，所以效率要比加锁高很多，因此 Map 的基本思路就是尽可能多的使用原子操作，直到迫不得已才去使用锁机制，Map 的做法是将数据冗余存储了两个数据结构中，read 是一个只读的 sync.Value 类型的结构，其上存储的数据可以通过 Value.Load()和 Value.Store() 安全存取，另外，新的数据会被存储在 dirty 中，等实际成熟， dirty 会被升级为 read.所有的读和修改操作都会优先在 read 上进行，以此尽量避免使用锁。

Map 的优势主要集中于下面两个场景：

(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.

即：

一次写，多次读
多个 goroutine 操作的键不相交时

关于源码

源码中的一些核心思想：

空间换时间
缓存思想
double-checking
延迟删除

关于 dirty 的提升

Map 中维持了一个 int 类型的 misses 每当 Map 未命中 read 时，会将该值自增 1，当该值大于 dirty 的长度后，dirty 就会被提升为 read，提升之后，dirty 和 misses 会被重置，等下一次插入新值时，会将 read 中未删除的数据复制到 dirty 中。

除此之外，执行 Range 时，也会先进行一次提升。

关于延迟删除

当执行 Delete 时，如果 read 没有击中，就会直接从 dirty 中删除，否则如果键值在 read 中，会先将其 Value 的指针（enter.p）标记为 nil, 等下一次执行复制时，这些被标记为 nil 的键值会被重新标记为 expunged，即 enter.p 有三种可能的值：

nil: 表示键值已经被删除，但这一版的 read 还没有被复制到 dirty 中，所以 dirty 此时为 nil, 遇到要重新插入这个key时，可以直接修改 read，之后进行复制时，这个最新的值会被同步回 dirty。
expunged: 表示该键值已经被删除并且经历了复制， dirty 不为 nil，这时需要同时修改 read 和 dirty，避免 read 的数据比 dirty 中的数据新，导致下一次提升时丢失新数据。
!= nil: 表示存储的是具体的 value 的指针。

被删除的数据直到下一次提升时才会被真正删除

double key load map store

0 人点赞