源码解读 Golang 的 sync.Map 实现原理
简介
Go 的内建 map
是不支持并发写操作的,原因是 map
写操作不是并发安全的,当你尝试多个 Goroutine 操作同一个 map
,会产生报错:fatal error: concurrent map writes
。
因此官方另外引入了 sync.Map
来满足并发编程中的应用。
sync.Map
的实现原理可概括为:
- 通过 read 和 dirty 两个字段将读写分离,读的数据存在只读字段 read 上,将最新写入的数据则存在 dirty 字段上
- 读取时会先查询 read,不存在再查询 dirty,写入时则只写入 dirty
- 读取 read 并不需要加锁,而读或写 dirty 都需要加锁
- 另外有 misses 字段来统计 read 被穿透的次数(被穿透指需要读 dirty 的情况),超过一定次数则将 dirty 数据同步到 read 上
- 对于删除数据则直接通过标记来延迟删除
数据结构
Map
的数据结构如下:
type Map struct { // 加锁作用,保护 dirty 字段 mu Mutex // 只读的数据,实际数据类型为 readOnly read atomic.Value // 最新写入的数据 dirty map[interface{}]*entry // 计数器,每次需要读 dirty 则 +1 misses int }
其中 readOnly 的数据结构为:
type readOnly struct { // 内建 map m map[interface{}]*entry // 表示 dirty 里存在 read 里没有的 key,通过该字段决定是否加锁读 dirty amended bool }
entry
数据结构则用于存储值的指针:
type entry struct { p unsafe.Pointer // 等同于 *interface{} }
属性 p 有三种状态:
p == nil
: 键值已经被删除,且m.dirty == nil
p == expunged
: 键值已经被删除,但m.dirty!=nil
且m.dirty
不存在该键值(expunged 实际是空接口指针)- 除以上情况,则键值对存在,存在于
m.read.m
中,如果m.dirty!=nil
则也存在于m.dirty
Map
常用的有以下方法:
Load
:读取指定 key 返回 valueStore
: 存储(增或改)key-valueDelete
: 删除指定 key
源码解析
Load
func (m *Map) Load(key interface{}) (value interface{}, ok bool) { // 首先尝试从 read 中读取 readOnly 对象 read, _ := m.read.Load().(readOnly) e, ok := read.m[key] // 如果不存在则尝试从 dirty 中获取 if !ok && read.amended { m.mu.Lock() // 由于上面 read 获取没有加锁,为了安全再检查一次 read, _ = m.read.Load().(readOnly) e, ok = read.m[key] // 确实不存在则从 dirty 获取 if !ok && read.amended { e, ok = m.dirty[key] // 调用 miss 的逻辑 m.missLocked() } m.mu.Unlock() } if !ok { return nil, false } // 从 entry.p 读取值 return e.load() } func (m *Map) missLocked() { m.misses++ if m.misses < len(m.dirty) { return } // 当 miss 积累过多,会将 dirty 存入 read,然后 将 amended = false,且 m.dirty = nil m.read.Store(readOnly{m: m.dirty}) m.dirty = nil m.misses = 0 }
Store
func (m *Map) Store(key, value interface{}) { read, _ := m.read.Load().(readOnly) // 如果 read 里存在,则尝试存到 entry 里 if e, ok := read.m[key]; ok && e.tryStore(&value) { return } // 如果上一步没执行成功,则要分情况处理 m.mu.Lock() read, _ = m.read.Load().(readOnly) // 和 Load 一样,重新从 read 获取一次 if e, ok := read.m[key]; ok { // 情况 1:read 里存在 if e.unexpungeLocked() { // 如果 p == expunged,则需要先将 entry 赋值给 dirty(因为 expunged 数据不会留在 dirty) m.dirty[key] = e } // 用值更新 entry e.storeLocked(&value) } else if e, ok := m.dirty[key]; ok { // 情况 2:read 里不存在,但 dirty 里存在,则用值更新 entry e.storeLocked(&value) } else { // 情况 3:read 和 dirty 里都不存在 if !read.amended { // 如果 amended == false,则调用 dirtyLocked 将 read 拷贝到 dirty(除了被标记删除的数据) m.dirtyLocked() // 然后将 amended 改为 true 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 { for { p := atomic.LoadPointer(&e.p) if p == expunged { return false } if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) { return true } } } 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, _ := m.read.Load().(readOnly) m.dirty = make(map[interface{}]*entry, len(read.m)) for k, e := range read.m { // 判断 entry 是否被删除,否则就存到 dirty 中 if !e.tryExpungeLocked() { m.dirty[k] = e } } } func (e *entry) tryExpungeLocked() (isExpunged bool) { p := atomic.LoadPointer(&e.p) for p == nil { // 如果有 p == nil(即键值对被 delete),则会在这个时机被置为 expunged if atomic.CompareAndSwapPointer(&e.p, nil, expunged) { return true } p = atomic.LoadPointer(&e.p) } return p == expunged }
Delete
func (m *Map) Delete(key interface{}) { m.LoadAndDelete(key) } // LoadAndDelete 作用等同于 Delete,并且会返回值与是否存在 func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) { // 获取逻辑和 Load 类似,read 不存在则查询 dirty read, _ := m.read.Load().(readOnly) e, ok := read.m[key] if !ok && read.amended { m.mu.Lock() read, _ = m.read.Load().(readOnly) e, ok = read.m[key] if !ok && read.amended { e, ok = m.dirty[key] m.missLocked() } m.mu.Unlock() } // 查询到 entry 后执行删除 if ok { // 将 entry.p 标记为 nil,数据并没有实际删除 // 真正删除数据并被被置为 expunged,是在 Store 的 tryExpungeLocked 中 return e.delete() } return nil, false }
总结
可见,通过这种读写分离的设计,解决了并发情况的写入安全,又使读取速度在大部分情况可以接近内建 map
,非常适合读多写少的情况。
sync.Map
还有一些其他方法:
Range
:遍历所有键值对,参数是回调函数LoadOrStore
:读取数据,若不存在则保存再读取
这里就不再详解了,可参见 源码。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
跨域问题是怎样造成的
跨域问题的由来 相信很多人都或多或少了解过跨域问题,尤其在现如今前后端分离大行其道的时候。 你在本地开发一个前端项目,这个项目是通过 node 运行的,端口是9528,而服务端是通过 spring boot 提供的,端口号是7001。 当你调用一个服务端接口时,很可能得到类似下面这样的一个错误: 然后你在发送请求的地方debug,在出现异常的地方你将得到这样的结果: 异常对象很诡异,返回的 response 是 undefined 的,并且 message 消息中只有一个"Network Error"。 看到这里你应该要知道,你遇到跨域问题了。 但是你需要明确的一点是,这个请求已经发出去了,服务端也接收到并处理了,但是返回的响应结果不是浏览器想要的结果,所以浏览器将这个响应的结果给拦截了,这就是为什么你看到的response是undefined。 浏览器的同源策略 那浏览器为什么会将服务端返回的结果拦截掉呢? 这就需要我们了解浏览器基于安全方面的考虑,而引入的 同源策略(same-origin policy) 了。 早在1995年,Netscape 公司就在浏览器中引入了“同源策略”。...
- 下一篇
图数据库应用:金融反欺诈实践
1 背景介绍 1.1 传统反欺诈技术面临挑战 数字技术与金融业的融合发展,也伴随着金融欺诈风险不断扩大,反欺诈形势严峻。数字金融欺诈逐渐表现出专业化、产业化、隐蔽化、场景化的特征,同传统的诈骗相比,数字金融诈骗往往是有组织,成规模的,他们分工明确、合作紧密、协同作案,形成一条完整的犯罪产业链。传统反欺诈技术面临的三大挑战:维度单一、效率低下、范围受限。(引用自《数字金融反欺诈白皮书》) 1.2 图数据库技术应运而生 面对复杂的大数据,如何高效的从大规模数据中获取有价值的信息,传统技术面临巨大挑战。 图数据库这项新兴技术正是反欺诈的一把利剑,基于图数据库技术构建的关系图谱可用于深度数据挖掘,包括:关系推理、关联度检测、集中度测量、语义分析、团伙发现、可视化展示等。 本质上反欺诈面临的核心问题就是如何处理海量的用户关联关系。传统关系型数据库在处理海量关系上做得并不好,面对复杂关系网络的处理存在如下问题:数据规模大难以存储、计算效率低、关系建模难、维护性/易用性/扩展性差等。与传统关系型数据库不同的是,图数据库在处理关联关系上具有天生的优势,这些问题都能很好的一一化解。根据DB-Engine...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2更换Tomcat为Jetty,小型站点的福音
- CentOS8安装Docker,最新的服务器搭配容器使用
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- 设置Eclipse缩进为4个空格,增强代码规范
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS8编译安装MySQL8.0.19
- SpringBoot2整合Redis,开启缓存,提高访问速度
- SpringBoot2配置默认Tomcat设置,开启更多高级功能