rk呓语

reposkeeper

Golang sync.Map 源码解析

在 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 的开销一定比文章开头最简单的实现也要大。

Golang sync.Pool 源码解析

上一篇

Golang Context 源码解析

下一篇
评论
发表评论 说点什么
还没有评论
116
0