当前位置:网站首页>golang源代码阅读,sync系列-Map
golang源代码阅读,sync系列-Map
2022-08-09 10:51:00 【ase2014】
总结
- golang的map是不支持并发访问和设置的,否则会panic。在golang的历史中,最开始只有不支持并发的map,但是实际上并发访问map的场景比较多,因此后续golang团队开发了sync.Map
- sync.Map使用场景有限,虽然并发访问的map的场景都可以使用它,但是golang团队注释里面说明了它的使用场景
- 如果有具体的类型,建议使用map+Mutex(or RWMutex)
- 如果掺杂多个类型,为了便于维护,建议使用sync.Map
- sync.Map在两个场景做了优化,这两种场景可以减少锁的使用
- 写一次,读多的场景
- 多个goroutine读、写,并且覆盖的都是对于不同的keys
- 通过两个map加上Mutex来实现的,先把k、v存储在dirty,如果查找多次均不在read,会把dirty迁移到read,后续读取key,会直接从read读取,且不用加锁。
- 只有对于dirty的操作才加锁
关键字
atomic.Value、dirty、readOnly、Mutex
使用
源码分析
- 存贮key、value的时候,会先存入dirty里面,当读取的时候,会检查read里面是否没有,没有则misses加一
- 如果misses大于dirty的长度,则将dirty赋值给read的m,然后将dirty清空,从而再次读取key,直接从readOnly里面读取,并且不用加锁
- 将dirty赋值给read的m时,amended也会设置为false,如果Store的key不在read,会进行dirtyLocked操作,即把read的key也通过循环拷贝到dirty
结构体
type Map struct {
mu Mutex // 锁,主要是加锁操作dirty
read atomic.Value // readOnly 存贮的是readOnly,里面有m的map,用作只读,所以可以不加锁
// 存贮key、value,首先存入dirty,如果misses大于dirty的长度,则迁移到read里的m
dirty map[interface{}]*entry
misses int
// 计数器,记录查找直接从dirty获取key、value的次数,
// 如果超过dirty的长度,则把dirty迁移到read,然后就可以直接从read里面获取,不用加锁
}
type readOnly struct {
m map[interface{}]*entry // 存储用于只读 key、value
amended bool // true if the dirty map contains some key not in m. // 表明dirty里是否有值
}
函数分析
主要分为三部分:查找、删除、存储
Store函数
- 如果开始都是调用Store,则每次都会加锁,即使key已经存在,value也相同,也会加锁,重新赋值,因为read一直为零值,每回都要操作dirty
- 如果超过dirty的长度次数没有命中,会把dirty迁移到read里面,并将dirty设置为nil,后续如果有存入操作,且read里面不存在,则会把read里面的数据迁移到dirty,并将新的数据加入ditry
func (m *Map) Store(key, value interface{}) {
// 从readOnly里面读取,初始化状态read为空,因为下面写的结构体readOnly,read会初始化化为readOnly的零值
read, _ := m.read.Load().(readOnly)
// 存在,则将entry里面的重新赋值为value
// 如果在read里面存在,则会通过cas操作更新read里面的值
// 如果是已经删除的,会继续执行代码
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}
// read里没有,则加锁,对dirty进行操作,整个过程都加锁
m.mu.Lock()
// double check,可能等待加锁时,另一个goroutine已经进入,加锁成功后,read里面已经存在了
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
// 如果key在read里面已经存在,且v为expunged(已经删除的),则将e的p设置为nil
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.
// 将k设置到key
m.dirty[key] = e
}
// 将value设置到e
e.storeLocked(&value)
// 在dirty中,如果key存在,即使e里存储的值跟value相同,也会重新赋值覆盖
} else if e, ok := m.dirty[key]; ok {
e.storeLocked(&value)
} else {
// 初始化场景或者将进行了missLocked(将dirty赋值给readOnly:将数据迁移到readOnly里面,
// amended会被设置为false)
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.
// dirtyLocked会将readOnly里面的值赋值给dirty,防止readOnly里存在,但是dirty为nil的场景,
// 这时会存储两倍的key和value。如果key、value比较多,可能会有内存压力
m.dirtyLocked()
// 将amended设置为true
m.read.Store(readOnly{m: read.m, amended: true})
}
// dirty里面存贮key、value
m.dirty[key] = newEntry(value)
}
m.mu.Unlock()
}
处理场景:
- misses大于dirty的长度,将dirty转移到read里面去,dirty设置为0
- 如果新存贮key、value,这时key不在read,从而会存储到dirty里去
- 如果后续又有获取操作,导致misses大于dirty,又会执行操作1,如果不将read里面的值都拷贝到dirty里去,会导致数据丢失
func (m *Map) dirtyLocked() {
if m.dirty != nil {
return
}
// 如果m.dirty为nil,会把read里面数据迁移到dirty
read, _ := m.read.Load().(readOnly)
m.dirty = make(map[interface{}]*entry, len(read.m))
for k, e := range read.m {
if !e.tryExpungeLocked() {
// 如果key的vaule不是expunged,则都转移到dirty里面去,这时dirty和read里面都存在key、value,
// 会导致k、v翻倍,已经删除的key不会被迁移
// 数据整体迁移,如果量比较大,可能会花费一定时间
m.dirty[k] = e
}
}
}
Load函数
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
// 先从readOnly
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
if !ok && read.amended {
m.mu.Lock()
// Avoid reporting a spurious miss if m.dirty got promoted while we were
// blocked on m.mu. (If further loads of the same key will not miss, it's
// not worth copying the dirty map for this key.)
// double check,可能加锁前有人已经进来修改过read
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if !ok && read.amended {
e, ok = m.dirty[key]
// Regardless of whether the entry was present, record a miss: this key
// will take the slow path until the dirty map is promoted to the read
// map.
// 如果在read里面没有命中,则将misses加一,然后判断misses是否超过dirty的大小
// 如果超过,则将dirty转移到read里面去
m.missLocked()
}
m.mu.Unlock()
}
if !ok {
return nil, false
}
return e.load()
}
- 迁移dirty到read里去,并将amended设置为false
- 调用该函数需要加锁,即mu加锁
func (m *Map) missLocked() {
m.misses++
// 判断misses是否超过dirty的长度
if m.misses < len(m.dirty) {
return
}
// 将dirty赋值给read,并将emended设置为false
m.read.Store(readOnly{m: m.dirty})
// dirty清空,misses设置为0
m.dirty = nil
m.misses = 0
}
LoadOrStore函数
是将Load和Store合并起来,如果key存在,则返回对应value,如果不存在,则将key、value存储进去
func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
// Avoid locking if it's a clean hit.
// 从read里面查找,存在返回
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
// 存在,确认是否为expunged,如果是则返回不存在
// 如果存在直接返回
actual, loaded, ok := e.tryLoadOrStore(value)
if ok {
return actual, loaded
}
}
// 加锁,一直到结束
m.mu.Lock()
// double check
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
// 如果是unexpunge,则存储key、value
if e.unexpungeLocked() {
m.dirty[key] = e
}
// 获取实际值
actual, loaded, _ = e.tryLoadOrStore(value)
} else if e, ok := m.dirty[key]; ok {
// 在dirty里面存在,获取实际值
actual, loaded, _ = e.tryLoadOrStore(value)
// 统计misses,看是否迁移,跟Load里一样的逻辑
m.missLocked()
} else {
// 跟Store里逻辑一样
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)
actual, loaded = value, false
}
m.mu.Unlock()
return actual, loaded
}
tryLoadOrStore函数
func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) {
p := atomic.LoadPointer(&e.p)
// 如果是expunged,则直接返回不存在
if p == expunged {
return nil, false, false
}
// 存在,则返回值
if p != nil {
return *(*interface{})(p), true, true
}
// Copy the interface after the first load to make this method more amenable
// to escape analysis: if we hit the "load" path or the entry is expunged, we
// shouldn't bother heap-allocating.
// 不存在,则设置值,因为tryLoadOrStore不一定在lock里面执行,所以需要for循环,一直到设置成功
ic := i
for {
if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) {
return i, false, true
}
p = atomic.LoadPointer(&e.p)
if p == expunged {
return nil, false, false
}
if p != nil {
return *(*interface{})(p), true, true
}
}
}
LoadAndDelete函数
- 删除key,并返回删除key对应的value,并且返回该key是否存在
- 先从read里面获取,如果存在,将entry里面的p设置为nil
- map删除只是将key、value设置为空,实际内存是不会压缩的
func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
// 从read查找,存在,直接delete
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]
// 从dirty里面删除key,因为加锁了,可以操作,对于read里面的只是将key对应的entry里的p设置为nil
delete(m.dirty, key)
// Regardless of whether the entry was present, record a miss: this key
// will take the slow path until the dirty map is promoted to the read
// map.
m.missLocked()
}
m.mu.Unlock()
}
if ok {
return e.delete()
}
return nil, false
}
将p设置nil
func (e *entry) delete() (value interface{}, ok bool) {
for {
p := atomic.LoadPointer(&e.p)
if p == nil || p == expunged {
return nil, false
}
if atomic.CompareAndSwapPointer(&e.p, p, nil) {
return *(*interface{})(p), true
}
}
}
Delete函数
实际调用的是LoadAndDelete,只是不返回key是否存在,已经对应的value是什么
func (m *Map) Delete(key interface{}) {
m.LoadAndDelete(key)
}
Range函数
- 如果dirty存在,则将dirty赋值给read里面的m
- 循环read里面的m
func (m *Map) Range(f func(key, value interface{}) bool) {
// We need to be able to iterate over all of the keys that were already
// present at the start of the call to Range.
// If read.amended is false, then read.m satisfies that property without
// requiring us to hold m.mu for a long time.
read, _ := m.read.Load().(readOnly)
// 如果dirty存在,则将dirty赋值给read,然后从read里面读取所有的值
if read.amended {
// m.dirty contains keys not in read.m. Fortunately, Range is already O(N)
// (assuming the caller does not break out early), so a call to Range
// amortizes an entire copy of the map: we can promote the dirty copy
// immediately!
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
if read.amended {
read = readOnly{m: m.dirty}
m.read.Store(read)
m.dirty = nil
m.misses = 0
}
m.mu.Unlock()
}
for k, e := range read.m {
v, ok := e.load()
if !ok {
continue
}
if !f(k, v) {
break
}
}
}
边栏推荐
- unix环境编程 第十五章 15.8信号量
- 备战金三银四:如何成功拿到阿里offer(经历+面试题+如何准备)
- String类型的字符串对象转实体类和String类型的Array转List
- Preparation for gold three silver four: how to successfully get an Ali offer (experience + interview questions + how to prepare)
- PoseNet: A Convolutional Network for Real-Time 6-DOF Camera Relocalization论文阅读
- 性能测试(03)-JDBC Request
- 我用开天平台做了一个定时发送天气预报系统【开天aPaaS大作战】
- 真香!肝完Alibaba这份面试通关宝典,我成功拿下今年第15个Offer
- 为什么组合优先于继承
- AQS同步组件-FutureTask解析和用例
猜你喜欢
批量转换经纬度的网页实现方法
Dialogue with the DPO of a multinational consumer brand: How to start with data security compliance?See you on 8.11 Live!
类与对象 (下)
彻底理解工厂模式
pytorch widedeep文档
微信小程序——天气查询
Tensorflow realize parameter adjustment of linear equations
OpenSSF的开源软件风险评估工具:Scorecards
Shell script combat (2nd edition) / People's Posts and Telecommunications Press Script 1 Find programs in the PATH
c语言函数的递归调用(汉诺塔问题,楼梯递归问题等)
随机推荐
VBA实战(11) - 工作表(Sheet) 操作汇总
unix环境编程 第十五章 15.3 函数popen和pclose
UNIX Environment Programming Chapter 15 15.5FIFO
【原创】VMware Workstation实现Openwrt软路由功能,非ESXI,内容非常详细!
json库的dumps()方法和loads()方法
商业技术解决方案与高阶技术专题 - 数据可视化专题
性能测试(01)-jmeter元件-线程组、调试取样器
TensorFlow: NameError: name 'input_data' is not defined
unix系统编程 第十五章 15.2管道
caffe ---make all编辑出错
C语言统计不同单词数
prometheus接入mysqld_exporter
The common problems in laptops, continuously updated
AQS同步组件-FutureTask解析和用例
Unix Environment Programming Chapter 14 14.8 Memory Mapped I/O
unix环境编程 第十五章 15.9 共享存储
autogluon安装,使用指南,代码
Invisible OOM in kubernetes
Getting Started with MNIST Machine Learning
Netscope: Online visualization tool for neural network structures