Go问答 sync.Map源码分析

chasiny · 2018年06月07日 · 446 次阅读

博客地址:sync.Map 源码分析

普通的 map

go 普通的 map 是不支持并发的,例如简单的写

func main() {
    wg := sync.WaitGroup{}
    wg.Add(10)

    m := make(map[int]int)

    for i := 0; i < 10; i++ {
        go func(i int) {
            m[i] = i
            wg.Done()
        }(i)
    }

    wg.Wait()
}
fatal error: concurrent map writes

sync.Map

go 的 sync.Map 几个优化点

  • 通过使用优先读的结构体 read 减少锁的冲突
  • 使用双重检测
  • 使用延迟删除(删除存在于 read 中的数据只是将其置为 nil)
  • 动态调整,miss 次数多了之后,将 dirty 数据提升为 read

从 sync/map.go 看 Map 的结构体

type Map struct {
    mu Mutex                        //互斥锁,用于锁定dirty map

    read atomic.Value               //读map,实际上不是只读,是优先读
    dirty map[interface{}]*entry    //dirty是一个当前最新的map,允许读写

    misses int                      //标记在read中没有命中的次数,当misses等于dirty的长度时,会将dirty复制到read
}

//read存储的实际结构体
type readOnly struct {
    m       map[interface{}]*entry      //map
    amended bool                        //如果有些数据在dirty中但没有在read中,该值为true
}

type entry struct {
    p unsafe.Pointer                //数据指针
}

entry 的几种类型

  • nil: 表示为被删除,此时 read 跟 dirty 同时有该键(一般该键值如果存在于 read 中,则删除是将其标记为 nil)
  • expunged: 也是表示被删除,但是该键只在 read 而没有在 dirty 中,这种情况出现在将 read 复制到 dirty 中,即复制的过程会先将 nil 标记为 expunged,然后不将其复制到 dirty
  • 其他: 表示存着真正的数据

sync.Map 几种方法:

首先先说明 read 跟 dirty 不是直接存对象,而是存指针,这样的话如果键值同时存在在 read 跟 dirty 中,直接原子修改 read 也相当于修改 dirty 中的值,并且当 read 跟 dirty 存在大量相同的数据时,也不会使用太多的内存

Load

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended {
        //如果不在read中,并且dirty有新数据,则从dirty拿

        m.mu.Lock()

        //双重检查,因为有可能在加锁前read刚好插入该值
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            //没有在read中,则从dirty拿

            e, ok = m.dirty[key]
            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
    }
    //当没有命中的次数等于dirty的大小,将dirty复制给read
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

read 主要用于读取,每次 Load 都先从 read 读取,当 read 中不存在且 amended 为 true,就从 dirty 读取数据
无论 dirty 是否存在该 key,都会执行 missLocked 函数,该函数将 misses+1,当 misses 等于 dirty 的大小时,便会将 dirty 复制到 read,此时再将 dirty 置为 nil

Delete

func (m *Map) Delete(key interface{}) {
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended {
        //如果不在read中,并且dirty有新数据,则从dirty中找

        m.mu.Lock()

        //双重检查
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            //这是表示键值只存在于dirty,直接删除dirty中的键值即可
            delete(m.dirty, key)
        }
        m.mu.Unlock()
    }

    if ok {
        //如果在read中,则将其标记为删除(nil)
        e.delete()
    }
}

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

先判断是否在 read 中,不在的话再从 dirty 删除

Store

func (m *Map) Store(key, value interface{}) {
    //如果read存在这个键,并且这个entry没有被标记删除,尝试直接写入
    //dirty也指向这个entry,所以修改e也可以使dirty也保持最新的entry
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }

    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        //该键值存在在read中

        if e.unexpungeLocked() {
            //该键值在read中被标记为抹除,则将其添加到dirty

            m.dirty[key] = e
        }

        //更新entry
        e.storeLocked(&value)

    } else if e, ok := m.dirty[key]; ok {

        //如果不在read中,在dirty中,则更新
        e.storeLocked(&value)

    } else {
        //既不在read中,也不在dirty中

        if !read.amended {
            //从read复制没有标记删除的数据到dirty中
            m.dirtyLocked()
            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 {
    p := atomic.LoadPointer(&e.p)
    if p == expunged {
        return false
    }
    for {
        if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
            return true
        }
        p = atomic.LoadPointer(&e.p)
        if p == expunged {
            return false
        }
    }
}

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复制到dirty
    read, _ := m.read.Load().(readOnly)
    m.dirty = make(map[interface{}]*entry, len(read.m))
    for k, e := range read.m {

        //如果标记为nil或者expunged,则不复制到dirty
        if !e.tryExpungeLocked() {
            m.dirty[k] = e
        }
    }
}

func (e *entry) tryExpungeLocked() (isExpunged bool) {
    p := atomic.LoadPointer(&e.p)
    for p == nil {
        //尝试将nil置为expunged
        if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
            return true
        }
        p = atomic.LoadPointer(&e.p)
    }
    return p == expunged
}

sync.Map 写入就稍微麻烦很多了

  1. 首先会先判断键值是否已经存在 read 中,存在的话便尝试直接写入(read 不只是读,此时被写入),由于从 read 获取的是 entry 指针,因此对从 read 读取 entry 进行修改便相当于修改 dirty 中对应的 entry,此时写入的是使用原子操作。
  2. 键值存在在 read 中并且该 entry 被标记为 expunged(这种情况出现在从 read 复制数据到 dirty 中,看 tryExpungeLocked 函数,将所有键为 nil 置为 expunged,表示该键被删除,但没有在 dirty 中)
  3. 从 read 复制到 dirty 的过程来说,主要是用 dirtyLocked 函数实现的,复制除了 entry 为 nil 跟 expunged 的数据

参考

更多原创文章干货分享,请关注公众号
  • 加微信实战群请加微信(注明:实战群):gocnio
暂无回复。
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册