七叶笔记 » golang编程 » #Golang源码系列# sync.map 源码剖析

#Golang源码系列# sync.map 源码剖析

分类: golang编程 | 浏览: 165

在 Golang 中，map 是一个很重要的数据类型，日常中经常会用到。但是由于协程用得太爽，会暴露出一个严重的问题：map是不能并发写的。

这个就有点尴尬了，毕竟 并发写 是一个非常常见的场景。所以，各路大神齐显神通除了很多 concurrent map 的库。后来 golang 在 1.9 的时候终于出了官方库，就是 sync.map。

但是一直到现在官方库的性能被吐槽得很厉害，而且应用场景还很局限，只有读远大于写的时候，才比较适用。

不过，不管性能如何，它的实现方法是值得学习一下的。

自己如何实现一个并发map？

如果让我们自己简单的实现一个并发map，大概率会这样写： 

 import "sync"

type ConcurrentMap struct {
    d map[interface{}]interface{}
    l sync.RWMutex
}

func (c *ConcurrentMap) Set(key interface{}, value interface{}) {
    c.l.Lock()
    defer c.l.Unlock()
    c.d[key] = value
}

func (c *ConcurrentMap) Get(key interface{}) (interface{}, bool) {
    c.l.RLock()
    defer c.l.RUnlock()
    v, ok := c.d[key]
    return v, ok
}
复制代码

这样写的方法本身并没错，但问题在于效率太低。原因是锁的开销会比较大。所以，各类的 concurrent map 库都是在“锁”的地方做了一些手脚去优化。万变不离其宗，go官方的 sync.Map 也是通过优化锁的使用来达到效果。

sync.Map 原理

首先来说一下 sync.Map 具体实现的原理： 

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

sync.Map 中，使用了两个原生的 Map 来存放数据，一个叫做 read，一个叫做 dirty；

  • 新增数据，会放到 dirty 中；
  • 数据读取时，会先读取 read 中的数据，如果没有，再读 dirty 中的数据；

read 就相当于 dirty 的缓存一样。

那么，问题来了，什么时候 dirty 的数据会同步到 read 中呢？ 

 func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
  
    read, _ := m.read.Load().(readOnly)     // 拿到 read map
    e, ok := read.m[key]          // 尝试从 read 中获取key的内容
    if !ok && read.amended {      // read 中没有，而且 read 需要被修正时
        m.mu.Lock()                //  加锁
        read, _ = m.read.Load().(readOnly)  // 可能 read 被更新过，重新拿一次
        e, ok = read.m[key]
        if !ok && read.amended {   // 还是没有
            e, ok = m.dirty[key]    // 从 dirty 中拿   
            m.missLocked()          // 处理击穿缓存
        }
        m.mu.Unlock()              // 解锁
    }
    if !ok {
        return nil, false
    }
    return e.load()
}

func (m *Map) missLocked() {
    m.misses++   
    if m.misses < len(m.dirty) {        return
    }   
    
    // 如果 misses 小等 dirty 长度
    // 使用 dirty 覆盖 read，并清空 dirty
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}
复制代码

如上面的代码描述，在 sync.Map 中有一个 misses 的字段，当 read 中读取不到想要的key，就会到 dirty 中拿；在这个过程中，sync.Map 会将 misses 字段自增，表示击穿一次缓存；当这个值大等dirty的长度时，就会将 dirty 中所有的内容复制一份到 read 中。

为什么要这么做呢？原因在于锁！当读取 map 的时候，不需要锁，但是写 map 却需要锁来防止并发写。所以，当把“读”和“写”分开的时候，意味着有部分的操作是不需要加锁的，这样就提高了效率。

那为什么这里读 dirty 的时候，还要加锁呢？这是为了防止在重读 read 的时候不要被后面的更新操作打断，也可以保护后面对于 misses 的操作。

那么问题又来了，dirty 复制给了 read，却把自己置为空，dirty 数据不就不完整了嘛？确实是的，在某一些时刻，read 中的数据集要大于 dirty。当向 sync.Map 写一个 read 中没有的key 时，sync.Map 会将 read 中的数据同步到 dirty 中。

我们详细看下存储的代码，在标记②的地方，做了这一操作： 

 func (m *Map) Store(key, value interface{}) {
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
    // 如果 read 中，有要存储的 key，那么就直接尝试使用 CAS 方法来存储；①
        return
    }

    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        if e.unexpungeLocked() {
            // 如果 read 中有，但被标记清除了，那么直接把 value 赋值给 dirty；
            m.dirty[key] = e
        }
        // 更新 value 中实际的值
        e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok {
       // 如果 read 中没有，dirty 中有，那么更新 dirty 中
        e.storeLocked(&value)
    } else {
        if !read.amended {
            // read 和 dirty 都没有，那么就要将 read 中的内容复制一份到 dirty
            // 但不包括 标记清除的 key  ②
            m.dirtyLocked()
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
}

在上面代码的注释中，多次提到一个概念叫做 “标记清除”。什么是标记清除呢？这里要提到实际存储内容的数据结构 

 type readOnly struct {
    m       map[interface{}]*entry
    amended bool // true if the dirty map contains some key not in m.
}

type Map struct {
    ...
    read atomic.Value // readOnly
    dirty map[interface{}]*entry
    ...
}

type entry struct {
    p unsafe.Pointer // *interface{}
}
复制代码

从上面代码可以看到对于 read 和 dirty 来说，实际存储内容的 map 的定义为 map[interface{}]*entry ，map的值是一个 entry 结构的指针，实际的内容是放在 entry 中的一个指针里。

read 的实际结构是 readOnly，里面包含一个 map 和 布尔字段 amended。 map 是实际存储数据的地方。amended 表示 “是否被修正”。如果 amended == true 那么意味着，dirty 里面已经有了 read 中不存在的数据，如果后续读取 key 时，在 read 中没有，就需要到 dirty 中尝试。

使用这种结构有什么好处呢？意味着一个实际的值不需要在 read 和 dirty 中存储两次。因为在上面描述的过程中，read 和 dirty 的存储内容会经常性的进行一些相互同步的工作。如果所有的 map value 存储的是实际的值，那么这么开销会变得非常大。实际上的实现中， read 和 dirty 中，对于同样的 key，存储的是一个 项目 entry 指针。

使用了这种结构之后呢，就可以对于指针的值玩出一点花来。比如说 “标记清除”； 来看删除这块的代码： 

 func (m *Map) Delete(key interface{}) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended {  // 如果 read 中没有key，且 read 被标记为修正
        m.mu.Lock()
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended { // 再次验证 read 中没有key，且 read 被标记为修正
            delete(m.dirty, key)  // 直接删除 dirty 中的 key
        }
        m.mu.Unlock()
    }
    if ok {  // 如果 read 中有key，则操作 entry 来进行删除
        e.delete()
    }
    
    // 如果 read 中没有key，且 read 没有标记为修正
}

func (e *entry) delete() (hadValue bool) {
    for {
        p := atomic.LoadPointer(&e.p)  // 获取 entry 的实际内容
        if p == nil || p == expunged {  // 如果内容已经被置为空，或者 “标记清除”
            return false
        }
        if atomic.CompareAndSwapPointer(&e.p, p, nil) { // CAS “标记清除”
            return true
        }
    }
}

可以从上面的代码看到，只有当 read 中没有，且 read 是标记修正的情况下，才会加锁去进行删除，否则的话，通过 CAS 的方式，就可以一起将 read 和 dirty 中的key清除掉。

但是，此时 “标记清除” 只是将 key 所对应的 entry 标记为了 “expunged”，key还在。什么时候 key 会被删除呢？需要经历一次 “ read -> dirty 同步 + dirty -> read 同步 ”。

  • read -> dirty 同步：不会将 “标记清除” 的 key 同步过去；
  • dirty -> read 同步：是直接覆盖；

经过了上面两步，“标记清除” 的 key，就被彻底删除掉了。这也是延迟删除的原理。

sync.Map 绝对不是最好的并发map实现方式，但也许是最合适的。对于支持并发的数据结构来说，一定要针对使用场景选择不同的实现。如果是 “写多读少” 的场景，那么 sync.Map 的开销一定比文章开头最简单的实现也要大。

相关文章