专栏首页大猪的笔记go: 当我们在使用sync.Map时,发生了什么

go: 当我们在使用sync.Map时,发生了什么

sync.Map是我比较喜欢的一个库,用了非常久,今天突发奇想瞧瞧它的实现。又一次被宇宙中第二NB的语言--go 折服了。 这里准备写一篇文章,讨论下当使用sync.Map执行操作的时候,会发生什么。

map结构

代码很简单,sync/map.go中一百多行。总体讲一讲Load, Store, Delete三个接口发生了什么。 首先是sync.Map的结构:

sync.Map {
        read ,一个真实的map ]
        amended,  bool变量;
        dirty , 一个真实的map
        misses , int 记录读取的时候,在read map中miss的次数
}

操作一下

Store key:1

此时会初始化dirty map,初始化read map,并把amended设为true,这个key存到dirty map中。这里加锁。

执行的代码如下:

        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)

Store key 2,3

此时直接存dirty map,上面的if !read.amended不会执行了。这里加锁。 只有store 已存在的key(修改操作),可以无锁执行。使用的是atomic.Value结构的功能。

Load key 1

load命令首先会从read map查,如果查不到,amended又是true,那就尝试从dirty map中查,并且记miss。

再Load key:1 两次

当miss的数量等于dirty map的长度的时候,dirty map将直接升级为read map。并且dirty map置为nil。这里需要加锁。

参考代码:

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {
        return
    }
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

store key: 4

存入一个不存在的key,非常有意思的事情会发生。 此时,dirty map还是nil,它会进行初始化。将read map 拷贝一份过来。然后,将新值存在dirty map,并标记read map amended 为 true。这里加锁。

参考代码:

        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()  //  就是在这里初始化dirty map
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        m.dirty[key] = newEntry(value)

删除 key: 4

因为key:4 不在read中,在dirty map中且amended为true。所以,直接在dirty map中把key:4 删除。这里加锁。

删除 key: 3

key 3在read map中,直接将key:3 指向nil,注意不是(expunge)。这里无锁。

Store key:3 val: 1234

store一个已存在的key。 如果在read map中,直接修改val为1234。 这里值得一提的是,无论是read map还是dirty map,同一个key,指向的是一个val。这里无锁。

Delete key:3; Store key: 4 ; Load key:4 4次;Store key:5

Delete key:3, 此时,key:3 指向nil。这里无锁。

store key 4; Load key:4 4次。按照上面的情况分析,此时,dirty map被升级为read map,dirty map=nil 。

此时再store key:5, amended 被标记为true,dirty 复制read的数据。 在复制过程中,会判定 3的值是不是nil,如果是,则将值设置为 expunged。并且,不再复制到dirty。 如果一直没有人再执行Store key:3 。在下次dirty 升级的时候,key:3 就会被丢弃。

参考代码:

func (e *entry) tryExpungeLocked() (isExpunged bool) {
    p := atomic.LoadPointer(&e.p)
    for p == nil {
        if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {  // 这个原子操作将nil的值改为 expunged值。return true使这个key不会被添加到dirty
            return true
        }
        p = atomic.LoadPointer(&e.p)
    }
    return p == expunged
}

Store key:3 val: 1234

如果在read map中,key:3 存在,且被标记为删除(expunged),那么,把这个key添加到dirty map中。并修改值为1234。这里有锁。

参考代码:

        if e.unexpungeLocked() {
            // The entry was previously expunged, which implies that there is a
            // non-nil dirty map and this entry is not in it.
            m.dirty[key] = e
        }

为什么read中存在值为expunged的key时,这个时候dirty map一定不为nil呢。 1. 因为 expunged 的设置命令出现在dirtyLocked -> tryExpungeLocked这个调用的原子操作中(详细见上面一节),执行时,dirty 已经存在。所以,如果read中有值为 expunged 的key。那一定在dirtyLocked执行之后。 2. 因为dirty 中不可能存在值为expunged的key。dirty如果升级,read中一定不会有值为 expunged 的key。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python笔记:正则表达式

    超级大猪
  • sanic(3):调用templates

    经过上文,我们已经能输出hello这个单词。这说明服务已经成功响应。这里,我们将使用jinja2来进行html的渲染。 jinja2怎么用,已经超出了本文范围...

    超级大猪
  • go语言实现设计模式(一):策略模式

    策略模式定义了算法家族,在调用算法家族的时候不感知算法的变化,客户也不会受到影响。

    超级大猪
  • C++ map 和 hashmap 区别

    1. stl map is an associative array where keys are stored in sorted order using b...

    用户7436765
  • 《Golang从入门到跑路》之map的初识

    map是一种无序的,基于key-value 的数据结构。它是Go语言中的映射关系容器,其内部是使用散列表(hash) 实现的。

    极客运维圈
  • 遍历取出Map集合key-value数据的4种方法

    知识补充: list和set集合都实现了Iterable接口,所以他们的实现类可以使用迭代器遍历,map集合未实现该接口,若要使用迭代器循环遍历,需要借助se...

    似水的流年
  • Vue2.0 歌手数据获取及排序

    本次的系列博文的知识点讲解和代码,主要是来自于 黄轶 在慕课网的 Vue 2.0 高级实战-开发移动端音乐WebApp 课程,由个人总结并编写,其代码及知识点...

    Nian糕
  • golang-101-hacks(18)——map类型访问

    Map是一种指向哈希表的引用类型,可以使用map构造一个“键值”类型的数据库,这在实际编程中非常高效。例如,下面的代码是统计切片中每个元素的总数:

    羊羽shine
  • 数据存储漫谈

    数据系统的核心就是两件事,读和写,当数据量还少的时候,读写的性能不会有明显区别,随着数据量的增大,读写变成了一个trade-off,当你拥有优秀的写性能时,读数...

    哒呵呵
  • Openlayers3中统计图的实现

    在前文中讲到了在Arcgis for js中统计图的实现,在本文,讲述在Openlayers3中结合highcharts实现统计图。

    lzugis

扫码关注云+社区

领取腾讯云代金券