本文依据 Go 1.19
在上一篇文章中(《深入了解 go sync.Map – 基本原理》),咱们探讨了 go 中 sync.Map
的一些基本内容,如 map
并发运用下存在的问题,怎么解决这些问题等。
咱们也知道了 sync.Map
的一些基本操作,可是咱们仍是不知道 sync.Map
是怎么完结的,以及为什么在特定场景下,sync.Map
比 map + Mutex/RWMutex
快。
本篇文章就来持续深入探讨 sync.Map
,对 sync.Map
的规划与完结进行愈加翔实的讲解。
sync.Map 概览
开始之前,咱们先来了解一下 sync.Map
的数据结构,以及其一个大约的模型。这关于咱们了解 sync.Map
的规划十分有优点。
本文用到的一些名词解析
-
read
和read map
:都是指sync.Map
中的只读 map,即sync.Map
中的m.read
。 -
dirty
和dirty map
:都是指sync.Map
中的可写 map,即sync.Map
中的m.dirty
。 -
entry
:sync.Map
中的entry
,这是保存值的结构体,它是一个原子类型的指针。其间的指针指向key
对应的值。
sync.Map 的数据结构
sync.Map
的数据结构如下:
read
和dirty
是sync.Map
中最要害的两个数据结构,它们之间能够彼此转化。
// 在 sync.Map 中的效果是一个特别的符号
var expunged = new(any)
// sync.Map
type Map struct {
// 互斥锁
mu sync.Mutex
// 只读 map,用于读操作
read atomic.Pointer[readOnly]
// dirty map,写入操作会先写入 dirty map
dirty map[any]*entry
// 记载需求从 dirty map 中读取 key 的次数。
// 也便是没有在 read map 中找到 key 的次数。
misses int
}
// readOnly 是一个只读的 map
type readOnly struct {
m map[any]*entry // dirty map 中的 key 的一份快照
amended bool // 记载是否在 dirty map 中有部分 read map 中不存在的 key
}
// 实践存储值的结构体。
// p 有三种状况:nil, expunged, 正常状况。
type entry struct {
p atomic.Pointer[any]
}
阐明:
-
expunged
是一个特别的符号,用于标明entry
中的值现已被删去。而且那个key
在dirty map
中现已不存在了。 -
Map
也便是咱们运用的sync.Map
,它有一个mu
互斥锁,用于维护dirty map
。 -
Map
中有两个map
,一个是read map
,一个是dirty map
。-
read map
是一个只读的map
,但不是咱们在其他当地说的只读。它的只读的意义是,它的key
是不能添加或许删去的。可是value
是能够修正的。 -
dirty map
是一个可读写的map
,新增key
的时分会写入dirty map
。
-
-
misses
是一个int
类型的变量,用于记载read map
中没有找到key
的次数。当misses
到达必定的值的时分,会将dirty map
中的key
同步到read map
中。 -
readOnly
是一个只读的map
,它的m
字段是一个map
,用于保存dirty map
中的key
的一份快照。readOnly
中的amended
字段用于记载dirty map
中是否有read map
中不存在的key
。 -
entry
是一个结构体,它有一个p
字段,用于保存key
对应的值。p
字段有三种状况:nil
、expunged
、正常状况。expunged
是一个特别的符号,用于标明key
对应的值现已被删去,而且那个key
在dirty map
中现已不存在了。
由于在
sync.Map
中是运用了特别的符号来标明删去的,也便是不需求运用delete
函数来删去key
。这样就能够利用到了原子操作了,而不需求加锁。这样就能取得更好的功能了。
sync.Map 的全体模型
上一小节咱们现已介绍了 sync.Map
的数据结构,现在让咱们来看一下 sync.Map
的全体模型。
它的全体模型如下:
要害阐明:
-
read map
是一个只读的map
,不能往里边添加key
。而dirty map
是一个可读写的map
,能够往里边添加key
。 -
sync.Map
完结中,基本都是会先从read map
中查找key
,假如没有找到,再从dirty map
中查找key
。然后依据查找成果来进行后续的操作。 - 假如
read map
中没有找到key
,需求加锁才能从dirty map
中查找key
。由于dirty map
是一个可读写的map
,所以需求加锁来确保并发安全。
这实践上是一种读写别离的理念。
sync.Map 的作业流程
经过看它的数据结构和全体模型,想必咱们仍然对 sync.Map
感到很陌生。现在再来看看 sync.Map
的作业流程,这样咱们就能知道其间一些字段或许结构体的实践效果了。
下面,咱们经过一些 map
的常规操作来看一下 sync.Map
的作业流程:
- 添加
key
:假如是第一次写入key
的话(假设其值为value
),会先写入dirty map
,在dirty map
中的value
是一个指向entry
结构体的指针。entry
结构体中的p
字段也是一个指针,它指向了value
的内存地址。 - 读取
key
:先从read
中读取(无锁,原子操作),read
中找不到的时分再去dirty
中查找(有锁)。 - 修正
key
:假如key
在read map
中存在的话,会直接修正key
对应的value
。假如key
在read map
中不存在的话,会去dirty map
中查找(有锁),假如在dirty map
中也不存在的话,则修正失利。 - 删去
key
:假如key
在read map
中存在的话,会将key
对应的entry
指针设置为nil
(实践上是打符号而已,并没有删去底层map
的key
)。假如在read
中找不到,而且dirty
有部分read
中不存在的key
的话,会去dirty map
中查找(有锁),假如在dirty map
中也不存在的话,则删去失利。
或许咱们看完这一大段阐明仍是不会太懂,可是没关系,下面临每一个操作都有图,结合我画的图应该能够更好地了解。
深入之前需求了解的一些布景常识
在 sync.Map
中有一些咱们需求有基本了解的布景常识,这儿简略说一下。
锁
在 sync.Map
中,需求读写 dirty map
的时分,都需求加锁,加的锁是 sync.Mutex
。关于这把锁,咱们需求知道的是:
sync.Mutex
是一个互斥锁。当一个 goroutine
取得了 sync.Mutex
的运用权之后(Lock
调用成功),其他的 goroutine
就只能等候,直到该 goroutine
开释了 sync.Mutex
(持有锁的 goroutine
运用了 Unlock
开释锁)。
所以,咱们在源码中看到 m.mu.Lock()
这行代码的时分,就应该知道,从这一行代码直到 m.mu.Unlock()
调用之前,其他 goroutine
调用 m.mu.Lock()
的时分都会被阻塞。
在
sync.Map
中,dirty map
的读写都需求加锁,而读read map
的时分不需求锁的。
原子操作
go 语言中的原子操作是指,不会被打断的操作。也便是说,当一个 goroutine
履行了一个原子操作之后,其他的 goroutine
就不能打断它,直到它履行完毕。
这能够确保咱们的一些操作是完整的,比方给一个整数加上一个增量,假如不运用原子操作,而是先取出来再进行加法运算,再写回去这样操作的话,
就会出现问题,由于这个进程有或许被打断,假如别的一个 goroutine
也在进行这个操作的话,就有或许会出现数据紊乱的问题。
而原子操作的 Add
(比方 atomic.Int32
的 Add
办法)能够在加法进程中不被打断,所以咱们能够确保数据的完整性。
这儿说的不被打断说的是:这个原子操作完结之前,其他 goroutine
不能操作这个原子类型。
除了 Add
办法,atomic
包中还有 Load
、Store
、Swap
等办法,这些办法都是原子操作,能够确保数据的完整性。
在
sync.Map
中,对entry
状况的修正都是经过原子操作完结的。
CAS
CAS 是 Compare And Swap
的缩写,意思是比较并交流。CAS
操作是一种原子操作,它的原理是:当且仅当 内存值 == 预期值
时,才会将 内存值
修正为 新值
。
运用代码标明的话,大约如下:
if *addr == old {
*addr = new
return true
}
return false
也便是说:
- CAS 原子操作会先进行比较,假如
内存值 == 预期值
,则履行交流操作,将内存值
修正为新值
,并回来true
。 - 不然,不履行交流操作,直接回来
false
。
CAS 假如比较发现相同就会交流,假如不相同就不交流,这个进程是原子的,不会被打断。在
sync.Map
中,修正entry
的状况的时分,有或许会运用到 CAS。
double-checking(两层检测)
这是一种尽量削减锁占用的策略,在单例模式中或许会用到:
// 第一次查看不运用锁
if instance == nil {
mu.Lock()
defer mu.Unlock()
// 获取到锁后,还要再次查看,
// 由于有或许在等候锁的时分 instance 现已被初始化了
if instance == nil {
instance = new()
}
}
return instance
上面这个例子中,在获取到锁之后,还进行了一次查看,这是由于 mu.Lock()
假如获取不到锁,那么当时 goroutine
就会被挂起,等候锁被开释。
假如在等候锁的进程中,别的一个 goroutine
现已初始化了 instance
,那么当时 goroutine
就不需求再初始化了,所以需求再次查看。
假如第2次查看发现 instance
现已被初始化了,那么就不需求再初始化了,直接回来 instance
即可。
在
sync.Map
中,也有相似的两层检测,比方在Load
办法中,会先从read
中获取entry
,假如没有,就会加锁,获取到锁后,再去查看一下read
中是否有entry
,假如没有,才会从dirty
中获取entry
。这是由于在等候锁的时分或许有其他goroutine
现已将key
放入read
中了(比方做了Range
遍历)。
dirty map 和 read map 之间的转化
上面咱们说了,写入新的 key
的时分,其实是写入到 dirty
中的,那什么时分会将 key
写入到 read
中呢?
准确来说,sync.Map
是不会往 read map
中写入 key
的,可是能够运用 dirty map
来掩盖 read map
。
dirty map 转化为 read map
dirty
map 转化为 read
map 的机遇是:
-
missess
的次数到达了len(dirty)
的时分。这意味着,许多次在read map
中都找不到key
,这种状况下是需求加锁才能再从dirty map
中查找的。这种状况下,就会将dirty map
转化为read map
,这样后续在read map
中能找到key
的话就不需求加锁了。 - 运用
Range
遍历的时分,假如发现dirty map
中有些key
在read map
中没有,那么就会将dirty map
转化为read map
。然后遍历的时分就遍历一下read map
就能够了。(假如read map
中的key
和dirty map
中的key
完全共同,那直接遍历read map
就足够了。)
dirty map
转化为 read map
的操作其实是很简略的,便是运用 dirty map
直接掩盖掉 read map
,然后将 dirty map
置为 nil
,一起 misses
重置为 0
。
简略来说,假如由于新增了
key
需求频频加锁的时分,就会将dirty map
转化为read map
。
read map 转化为 dirty map
read map
转化为 dirty map
的机遇是:
-
dirty map
为nil
的状况下,需求往dirty map
中添加新的key
。
read map
转化为 dirty map
的时分,会将 read map
中正常的 key
复制到 dirty map
中。
可是这个操作完了之后,read map
中的那些被删去的 key
占用的空间是还没有被开释的。
那什么时分开释呢?那便是上面说的 dirty map
转化为 read map
的时分。
sync.Map 中 entry 的状况
在 sync.Map
中,read map
和 dirty map
中相同 key
的 entry
都指向了相同的内容(共享的)。
这样一来,咱们就不需求维护两份相同的 value
了,这一方面削减了内存运用的一起,也能够确保同一个 key
的数据在 read
和 dirty
中看到都是共同的。
由于咱们能够经过原子操作来确保对 entry
的修正是安全的(可是添加 key
仍然是需求加锁的)。
entry
的状况有三种:
-
nil
:被删去了,read map
和dirty map
都有这个key
。 -
expunged
:被删去了,可是dirty map
中没有这个key
。 - 正常状况:能够被正常读取。
它们的转化关系如下:
阐明:
-
key
被删去 -
dirty map
为nil
的时分,需求写入新的key
,read
中被删去的key
状况会由nil
修正为expunged
- 被删去的
key
,从头写入 -
read
中被删去的key
(dirty map
中不存在的),在再次写入的时分会产生
留意:expunged
和正常状况之间不能直接转化,expunged
的 key
需求写入的话,需求先修正其状况为 nil
。正常状况被删去之后先转化为 nil
,然后在创立新的 map
的时分才会转化为正常状况。也便是 1->2
和 4->3
这两种转化)
不存在由正常状况转化为
expunged
或许由expunged
转化为正常状况的状况。
entry 状况存在的意义
entry
的状况存在的意义是什么呢?咱们去翻阅源码的时分会发现,其实 sync.Map
在删去的时分,
假如在 read map
中找到了 key
,那么删去操作仅仅将 entry
的状况修正为 nil
(经过原子操作修正),并没有真实的删去 key
。
也便是并不像咱们运用一般 map
的时分那种 delete
操作,会将 key
从 map
中删去。
这样带来的一个优点便是,删去操作咱们也不需求加锁了,由于咱们仅仅修正了 entry
的状况,而不是真实的删去 key
。
这样就能够取得更好的功能了。
就算转化为了
nil
状况,也仍然能够转化为expunged
或许正常状况,详细看上一个图。
read.amended 的意义
咱们往 sync.Map
中写入新的 key
的时分,会先写入 dirty map
,可是不会写入 read map
。
这样一来,咱们在读取的时分就需求留意了,由于咱们要查找的 key
是有或许只存在于 dirty map
中的,
那么咱们是不是每次在 read map
中找不到的时分都需求先去 dirty map
中查找呢?
答案是否定的。咱们从 dirty map
中进行查找是有代价的,由于要加锁。假如不加锁,遇到其他 goroutine
写入 dirty map
的时分就报错了。
针对这种状况,一种比较简略的解决办法是,添加一个标志,记载一下 read map
跟 dirty map
中的 key
是否是完全共同的。
假如是共同的,那么咱们就不需求再加锁,然后去 dirty map
中查找了。不然,咱们就需求加锁,然后去 dirty map
中查找。
sync.Map
中的 amended
字段便是这儿说的标志字段。单单说文字或许有点笼统,咱们能够结合下图了解一下:
read.amended 的意义便是
read map
跟dirty map
中的key
是否是完全共同的。假如为true
,阐明有些 key 只存在于dirty map
中。
sync.Map 源码分析
sync.Map
供给的办法并不多,它能做的操作跟一般的 map
差不多,仅仅在并发的状况下,它能确保线程安全。
下面是 sync.Map
所能供给的办法:
-
Store
/Swap
(增/改): 往sync.Map
中写入新的key
。(Store
实践调用了Swap
办法) -
Load
(查): 从sync.Map
中读取key
。 -
LoadOrStore
(查/增/改): 从sync.Map
中读取key
,假如不存在,就写入新的key
。 -
Delete
/LoadAndDelete
(删): 从sync.Map
中删去key
。(Delete
实践调用了LoadAndDelete
办法) -
Range
: 遍历sync.Map
中的一切key
。
还有两个或许比较少用到的办法:
-
CompareAndDelete
: 从sync.Map
中删去key
,可是只要在key
的值跟old
持平的时分才会删去。 -
CompareAndSwap
: 从sync.Map
中写入新的key
,可是只要在key
的值跟old
持平的时分才会写入。
接下来咱们会从源码的角度来分析一下 sync.Map
的完结。
Store/Swap 源码分析
Store
实践上是对 Swap
办法的调用,所以咱们看 Swap
办法的源码就够了:
Swap
办法的效果是:交流一个 key
的值,并回来之前的值(假如有的话)。
回来值中的 prev
便是之前的值,loaded
标明 key
是否存在。
下面是 Swap
办法的源码:
func (m *Map) Swap(key, value any) (previous any, loaded bool) {
// 读取 read map
read := m.loadReadOnly()
// 先从 read map 中读取 key
if e, ok := read.m[key]; ok {
// 在 read map 中读取到了 key
if v, ok := e.trySwap(&value); ok { // ok 标明是否成功交流
// swap 成功
if v == nil { // 之前的值为 nil,标明 key 之前现已被删去的了
return nil, false
} // 之前的值不为 nil,标明存在
return *v, true
}
// 履行到这儿标明:
// read map 中存在 key,可是现已被删去。(为 expunged 状况)
}
// read map 中找不到 key,加锁,从 dirty map 中持续找
m.mu.Lock()
// double checking,二次查看,由于有或许等候锁的时分 read map 现已产生了变化
read = m.loadReadOnly()
if e, ok := read.m[key]; ok { // read map 中存在 key
if e.unexpungeLocked() { // 将 entry 由 expunged 状况改为 nil 状况
// key 之前现已被删去了,而且之前 dirty map 中不存在 key,
// 所以这儿需求将 key 添加到 dirty map 中。
m.dirty[key] = e
}
// 写入新的值,v 是旧的值
if v := e.swapLocked(&value); v != nil {
// v 不为 nil,标明之前存在
loaded = true
previous = *v
}
} else if e, ok := m.dirty[key]; ok { // read map 中不存在 key,可是 dirty map 中存在 key
// 写入新的值,v 是旧的值
if v := e.swapLocked(&value); v != nil {
// v 不为 nil,标明之前存在
loaded = true
previous = *v
}
} else { // read map 中不存在 key,dirty map 中也不存在 key(需求写入新的 key)
if !read.amended { // dirty map 和 read map 的 key 完全共同)
// 现在要写入新的 key 了,所以这个 amended 状况得修正了。
// 咱们正在将第一个新键添加到 dirty map 中。
// 确保它已分配并将 read map 的 amended 符号设置为 true。
m.dirtyLocked()
// amended 设置为 true,由于下面要写入一个在 read map 中不存在的 key
m.read.Store(&readOnly{m: read.m, amended: true})
}
// 新增的 key,dirty map 中不存在,所以直接写入
m.dirty[key] = newEntry(value)
}
// 解锁
m.mu.Unlock()
return previous, loaded
}
Swap/Store 图示
留意:这儿的
read map
和dirty map
中都没有包括entry
,咱们知道它们中相同的key
都指向相同的entry
就能够了。
Swap 的操作流程
- 从
read map
中读取key
,假如存在,就直接交流value
,并回来之前的value
。 - 假如
read map
中不存在key
,就加锁,加锁后,再从read map
中读取key
,假如存在,就直接交流value
,并回来之前的value
。(double checking
) - 加锁后,假如在
read map
中仍然找不到key
,再从dirty map
中读取key
,假如存在,就直接交流value
,并回来之前的value
。 - 假如
read map
和dirty map
都不存在key
,就将key
添加到dirty map
中,并回来nil
。在这一步中,假如read map
和dirty map
的key
完全共同,就将read map
的amended
状况设置为true
。
在第 4 步中,还有一个要害操作便是
dirtyLocked()
,这个操作的效果是确保dirty map
初始化,假如dirty map
现已初始化,就不会做任何操作。 假如dirty map
是nil
,那么会初始化,然后将read map
中未被删去的key
添加到dirty map
中。
dirtyLocked() 源码分析
dirtyLocked()
的效果是确保 dirty map
初始化,假如 dirty map
现已初始化,就不会做任何操作。
之所以 dirty map
需求初始化,是由于在 dirty map
转化为 read map
的时分,dirty map
会被设置为 nil
,
可是新增 key
的时分是要写入到 dirty map
的,所以需求从头初始化。
详细能够看上面的 dirty map 和 read map 的之间的转化
这一节。
dirtyLocked()
的完结如下:
// 1. 假如 m.dirty 为 nil,则创立一个新的 dirty map。
// 2. 不然,不做任何操作
func (m *Map) dirtyLocked() {
if m.dirty != nil {
return
}
read := m.loadReadOnly()
// dirty map 初始化
m.dirty = make(map[any]*entry, len(read.m))
// 关于 read map 中的 key,假如不是 expunged,则将其复制到 dirty map 中。
// read map 中 nil 的 key 会被转化为 expunged 状况。
for k, e := range read.m {
// 不是 expunged 的 entry,才会被复制到 dirty map 中。
if !e.tryExpungeLocked() {
m.dirty[k] = e
}
}
}
dirtyLocked()
图示:
dirtyLocked()
里有个需求留意的当地便是,它会将read map
中的nil
的key
转化为expunged
状况。expunged
状况标明这个key
仅仅在read map
中,而不在dirty map
中。 做完迁移之后,dirty map
其实就不包括那些被删去的key
了。
Swap/Store 要害阐明
Swap
办法里边其实基本现已包括了 sync.Map
首要规划理念了,下文讲解其他办法的时分,其间一些细节不再做过多的解说了:
-
sync.Map
在做许多操作的时分,都会先从read map
中读取,假如read map
中不存在,再从dirty map
中读取。 - 假如需求从
dirty map
中读取,那么会先加锁,然后再从dirty map
中读取。 -
sync.Map
在对entry
进行操作的时分,都是经过原子操作进行的。(这是由于有些写操作是没有mu.Lock()
维护的)
而关于
dirty map
和read map
的转化等仅仅一些完结细节的上的问题,咱们假如了解了它的规划理念,那么就能够很简略的了解它的完结了。
Swap/Store 里的原子操作
这儿面用了许多原子操作:
-
m.loadReadOnly()
: 读取read map
。 -
e.trySwap(&value)
: 交流key
的值。key
存在的时分,直接经过原子操作运用新的值掩盖旧的。(假如key
只存在于read map
中的话,这个操作会失利。) -
e.unexpungeLocked()
: 将entry
由expunged
状况改为nil
状况。 -
e.swapLocked(&value)
: 交流key
的值。key
存在的时分,直接经过原子操作运用新的值掩盖旧的。 -
m.read.Store(&readOnly{m: read.m, amended: true})
: 将read map
的amended
状况设置为true
。
为什么运用原子操作
为什么要运用原子操作呢?这是由于 sync.Map
中有一些写操作是没有加锁的,比方删去的时分,
删去的时分仅仅将 entry
的状况经过原子操作改成了 nil
状况。
假如不运用原子操作,那么就会出现并发问题。
比方:在 m.mu.Lock()
维护的临界区内先读取了 entry
的状况,咱们还没来得及对其做任何操作,
在别的一个 goroutine
中 entry
的状况被修正了,那么咱们临界区内的 entry
状况现已成为它的历史状况了,
假如这个时分再依据这个状况做任何操作都会导致并发问题。
Load 源码分析
Load
办法的效果是从 sync.Map
中读取 key
对应的值。
在 sync.Map
的完结中,key
的查找都遵从以下的查找流程:
留意:从
read map
查找不需求加锁,从dirty map
中查找需求加锁。
下面是 Load
办法的源码:
// Load 回来存储在 map 中的键值,假如不存在值则回来 nil。
// ok 成果标明是否在 map 中找到了值。
func (m *Map) Load(key any) (value any, ok bool) {
// 经过原子操作获取只读 map
read := m.loadReadOnly()
e, ok := read.m[key]
// 不在只读 map 中,而且 dirty map 包括一些 key 不在 read.m 中。
if !ok && read.amended {
m.mu.Lock()
// double checking
read = m.loadReadOnly()
e, ok = read.m[key]
if !ok && read.amended { // 仍然不在只读 map 中,而且 dirty map 包括一些 key 不在 read.m 中。
e, ok = m.dirty[key] // 从 dirty map 中获取
// 不管条目是否存在,记载一个未射中:这个键将走慢路径,直到脏映射被提升为读映射。
m.missLocked() // read 中读不到
}
m.mu.Unlock()
}
// key 不存在
if !ok {
return nil, false
}
// key 存在,经过原子操作获取值
return e.load()
}
Load 图示
其实 Load
的进程大约便是前一个图的查找 key
的进程,只不过其间有一步 missLocked()
,
这个操作是用来记载 key
未射中的次数的。在到达必定次数之后,会将 dirty map
提升为 read map
。
missLocked 源码分析
missLocked
的完结是很简略的,便是将 misses
加 1,假如 misses
到达了 dirty map
的巨细,
就会将 dirty map
提升为 read map
。
func (m *Map) missLocked() {
m.misses++
if m.misses < len(m.dirty) {
return
}
// 未射中的次数到达 len(m.dirty),将 dirty map 提升为 read map
m.read.Store(&readOnly{m: m.dirty})
// 重置 dirty map
m.dirty = nil
// 重置 misses
m.misses = 0
}
这个进程能够用下图标明:
Load 作业流程
Load
办法的作业流程如下:
- 经过原子操作获取
read map
。假如read map
中存在key
,则直接回来key
对应的值。 - 假如
dirty map
中包括了一些read map
中不存在的key
,则需求加锁,再次获取read map
。 - 假如
read map
中不存在key
,则从dirty map
中获取key
对应的值(一起调用missLocked()
)。不然回来从read map
中获取到的key
对应的值。
LoadOrStore 源码分析
LoadOrStore
办法的效果是从 sync.Map
中读取 key
对应的值,假如不存在则将 key
和 value
存入 sync.Map
中。
其实它跟 Load
办法全体流程上也是差不多的,只不过它在找到 key
的时分,会将 key
和 value
存入 sync.Map
中。
假如没有找到 key
,则新增 key
到 dirty map
中。
下面是 LoadOrStore
办法的源码:
// LoadOrStore 回来键的现有值(假如存在)。
// 不然,它存储并回来给定的值。
// 回来值:loaded 标明是否是加载的值,而不是存储的值。actual 是当时存储的值。
func (m *Map) LoadOrStore(key, value any) (actual any, loaded bool) {
// 假如从 read map 中获取到了 key,则不需求加锁。
read := m.loadReadOnly()
if e, ok := read.m[key]; ok { // key 是 expunged 状况的时分,ok 为 false
actual, loaded, ok := e.tryLoadOrStore(value)
if ok { // Load 或许 Store 成功
return actual, loaded
}
}
// 加锁
m.mu.Lock()
// double checking
read = m.loadReadOnly()
if e, ok := read.m[key]; ok {
// key 存在于 read map 中
if e.unexpungeLocked() { // 状况:expunged => nil
// 之前是 expunged 状况,现在变成了 nil 状况。需求在 dirty map 中写入 e。
m.dirty[key] = e
}
// 再次对 entry 履行测验 Load 或许 Store 新的值的操作
actual, loaded, _ = e.tryLoadOrStore(value)
} else if e, ok := m.dirty[key]; ok {
// key 存在于 dirty map 中
actual, loaded, _ = e.tryLoadOrStore(value)
m.missLocked() // misses++,标明 read map 中没有该 key
} else {
// key 不存在于 read map 和 dirty map 中。
if !read.amended {
// 下面需求往 dirty map 中写入新的 key,所以需求确保 dirty map 被初始化。
m.dirtyLocked()
// dirty map 中现在有一些 read map 中不存在的 key,所以需求将 read map 的 amended 置为 true。
m.read.Store(&readOnly{m: read.m, amended: true})
}
// 写入 dirty map
m.dirty[key] = newEntry(value)
actual, loaded = value, false
}
m.mu.Unlock()
return actual, loaded
}
LoadOrStore 图示
LoadOrStore 作业流程
-
key
在read map
中找到,测验在read map
中Load
或Store
,操作成功则回来。找不到则加锁,然后二次查看(double checking
)。 - 在
read map
中仍然找不到,可是key
在dirty map
中找到,测验在dirty map
中Load
或Store
,操作成功则回来。(missLocked
) -
key
不存在,往dirty map
中写入key
和value
。(假如dirty map
为nil
,则先进行初始化),然后read map
的amended
修正为true
。
tryLoadOrStore 源码分析
咱们发现,在 LoadOrStore
办法中,找到 key
之后,都是调用 tryLoadOrStore
办法来进行 Load
或 Store
操作的。
它的效果便是在 entry
上测验 Load
或 Store
操作,简略来说便是,假如 key
现已存在则 Load
,不然 Store
(当然,实践上没有这么简略)。
咱们先来看看它的源码:
// 假如 entry 未被删去,tryLoadOrStore 会自动加载或存储一个值。
// 假如 entry 被删去,tryLoadOrStore 将坚持条目不变并回来 ok==false。
//
// 回来值:
// ok:操作是否成功(Load 成功、Store 成功)
// loaded:标明是否是 Load 出来的
// actual:Load 到的值
func (e *entry) tryLoadOrStore(i any) (actual any, loaded, ok bool) {
// 获取 entry 的状况
p := e.p.Load()
// 这个 key 只存在于 read map 中,而且它现已被删去了
if p == expunged {
return nil, false, false
}
// key 是正常状况,Load 成功,回来
if p != nil {
return *p, true, true
}
// p 是 nil,阐明 key 不存在,需求 Store
ic := i
for { // 循环直到 Load 或许 Store 成功(相似自旋锁)
// Store 成功
if e.p.CompareAndSwap(nil, &ic) {
return i, false, true
}
// Store 失利,从头获取 entry 的状况
p = e.p.Load()
// 被删去了
if p == expunged {
return nil, false, false
}
// 还没被删去,阐明 key 存在
if p != nil {
return *p, true, true
}
}
}
tryLoadOrStore
的逻辑能够用下图标明:
在 p
是 nil
的状况下,会有一个 for
循环一向测验 Load
或许 Store
,一旦成功就会回来。
unexpungeLocked 的效果
在 LoadOrStore
办法中,咱们发现,假如 key
在 read map
中找到,会先调用 unexpungeLocked
办法。
读到这儿,或许许多读者对 expunge
和 unexpunge
有点懵逼,不知道它们是干什么的。
简略来说,expunge
便是标明 key
现已被删去了,而且这个 key
只存在于 read map
中(在 dirty map
中不存在)。
而 unexpunge
的效果便是撤销 expunge
的效果(由于要往这个 key
写入新的值了),紧接着咱们会往 dirty map
中写入这个 key
。
咱们能够结合下图来考虑一下:
留意:实践中
entry
并不是连续存储的。
expunged
状况阐明:
-
p == expunged
,key
已被删去,而且dirty map
不为nil
,而且dirty
中没有这个key
。 -
p == nil
,key
已被删去,而且dirty map
为nil
,或dirty[k]
指向该entry
。(Store
) -
p != nil
,key
正常,回来其值。(Load
)
Delete 源码分析
Delete
办法实践上仅仅 LoadAndDelete
的 wrapper 函数,所以咱们看 LoadAndDelete
就够了。
删去操作在 sync.Map
中是一个很简略的操作,假如在 read map
中找到了要删去的 key
,
那么咱们只需求将其设置为 nil
就能够了。虽然它是一个写操作,可是仍然不需求加锁。
假如在
read map
中找到了key
,则能够不加锁也把它删去。由于sync.Map
中的删去仅仅一个符号。
例外的状况是,它在 read map
中找不到,然后就需求加锁,然后做 double checking
,然后再去 dirty map
中查找了。
LoadAndDelete
的源码如下:
// LoadAndDelete 删去键的值,回来以前的值(假如有)。
// loaded 报告 key 是否存在。
func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
// 获取 read map
read := m.loadReadOnly()
// 从 read map 查找 key
e, ok := read.m[key]
if !ok && read.amended { // read map 找不到那个 key,需求持续从 dirty map 中查找
m.mu.Lock() // 加锁
read = m.loadReadOnly() // double checking
e, ok = read.m[key]
if !ok && read.amended { // 需求持续从 dirty map 中查找
e, ok = m.dirty[key] // 从 dirty map 中删去 key
delete(m.dirty, key) // 直接做删去 key 的操作
// 累加未射中 read map 的次数
m.missLocked()
}
m.mu.Unlock()
}
if ok { // key 存在,做删去操作(设置 entry 为 nil 状况)
return e.delete()
}
// key 找不到,不需求做删去操作
return nil, false
}
删去的操作会有两种状况:
- 存在于
read map
中,则直接删去。(设置entry
指针为nil
,可是不会删去read map
中的key
) - 只存在于
dirty map
中,则直接删去。这种状况下,会删去dirty map
中的key
。
LoadAndDelete 图示
LoadAndDelete 作业流程
- 从
read map
中查找key
,假如找到了,那么直接删去key
(将entry
的指针设置为nil
),并回来value
。 - 假如
read map
中没有找到key
,而且read.amended
为true
,那么就需求加锁,然后做double checking
。 - 加锁后在
read map
仍然找不到,而且read.amended
为true
,那么就需求从dirty map
中查找key
。 - 一起在临界区内直接履行
delete
操作,将key
从dirty map
中删去。一起累加misses
次数。 - 最终,假如找到了
key
对应的entry
,则将其删去(设置entry
指针为nil
),并回来value
。
Range 源码分析
Range
办法的效果是遍历 sync.Map
中的一切 key
和 value
,它接受一个函数作为参数,假如这个函数回来 false
,那么就会中止遍历。
Range
的源码如下:
// Range 依次为映射中存在的每个键和值调用 f。 假如 f 回来 false,则 range 中止迭代。
func (m *Map) Range(f func(key, value any) bool) {
// 咱们需求能够遍历在调用 Range 开始时现已存在的一切键。
read := m.loadReadOnly()
if read.amended {
// dirty map 中包括了 read map 中没有的 key
m.mu.Lock()
read = m.loadReadOnly()
if read.amended {
// 运用 m.dirty 中的数据掩盖 m.read 中的数据
read = readOnly{m: m.dirty}
m.read.Store(&read)
// 重置 dirty map
m.dirty = nil
// 重置 misses
m.misses = 0
}
m.mu.Unlock()
}
// 一切的 key 都在 read map 中了,遍历 read map 即可
for k, e := range read.m {
v, ok := e.load()
if !ok { // 现已被删去
continue
}
if !f(k, v) { // f 能够回来一个 bool 值,假如回来 false,那么就中止遍历
break
}
}
}
Range 图示
Range
遍历的时分,只会遍历 read map
中的 key
。假如 read.amended
为 true
,那么就需求加锁,然后做 double checking
,
假如二次查看 read.amended
仍是 true
,那么就需求将 dirty map
中的数据掩盖到 read map
中。
Range 作业流程
- 为了确保能遍历
sync.Map
中一切的key
,需求判断read.amended
是否为true
。 - 假如为
true
,阐明只要dirty map
中包括了一切的key
,那么就需求将dirty map
转化为read map
。(这样的优点是,能够在遍历进程中,不需求加锁) - 然后开始遍历,遍历的时分只需求遍历
read map
即可,由于这个时分read map
中包括了一切的key
。 - 遍历进程中,假如发现
key
现已被删去,则直接跳过。不然将key
和value
传递给f
函数,假如f
函数回来false
,那么就中止遍历。
CompareAndSwap 源码分析
CompareAndSwap
办法的效果是比较 key
对应的 value
是否为 old
,假如是,则将 key
对应的 value
设置为 new
。
CompareAndSwap
的源码如下:
// 假如映射中存储的值等于旧值,则 CompareAndSwap 会交流 key 的旧值和新值
// 旧值必须是可比较的类型。
func (m *Map) CompareAndSwap(key, old, new any) bool {
// 获取 read map
read := m.loadReadOnly()
// 从 read map 读取 key 对应的 value
if e, ok := read.m[key]; ok {
// 在 read map 中找到了,进行 CAS 操作
return e.tryCompareAndSwap(old, new)
} else if !read.amended {
// 在 dirty map 也没有,回来 false
return false
}
// 加锁
m.mu.Lock()
defer m.mu.Unlock()
read = m.loadReadOnly()
swapped := false
if e, ok := read.m[key]; ok { // double checking
// 在 read map 中找到了,进行 CAS 操作
swapped = e.tryCompareAndSwap(old, new)
} else if e, ok := m.dirty[key]; ok {
// 在 dirty map 中找到了,进行 CAS 操作
swapped = e.tryCompareAndSwap(old, new)
// 累加 misses 次数
m.missLocked()
}
return swapped
}
CompareAndSwap 图示
其实到这儿,咱们应该发现了,其实 sync.Map
的大多数办法的完结都是先从 read map
中读取,假如没有找到,那么就从 dirty map
中读取。
仅仅从 read map
中读取的时分,需求加锁,然后做 double checking
。
CompareAndSwap 作业流程
- 首先从
read map
中读取key
对应的value
。假如找到则进行CAS
操作,假如没有找到,那么就需求加锁,然后做double checking
。 - 假如仍是没找到。则从
dirty map
中查找,找到则做 CAS 操作,然后累加misses
次数。 - 假如仍是没找到,那么就回来
false
。
CompareAndDelete 源码分析
CompareAndDelete
办法的效果是比较 key
对应的 value
是否为 old
,假如是,则将 key
对应的 value
删去。
CompareAndDelete
的源码如下:
// 假如 key 的值等于 old,CompareAndDelete 会删去它的条目。
// 旧值必须是可比较的类型。
//
// 假如 map 中的 key 的值不等于 old,则 CompareAndDelete 回来 false(即使旧值是 nil 接口值)。
func (m *Map) CompareAndDelete(key, old any) (deleted bool) {
// 获取 read map
read := m.loadReadOnly()
e, ok := read.m[key]
// read map 中不存在这个 key,而且 dirty map 中包括了一些 read map 中没有的 key
if !ok && read.amended {
// 加锁
m.mu.Lock()
read = m.loadReadOnly()
e, ok = read.m[key]
// double checking
if !ok && read.amended { // dirty map 中包括 read map 中不存在的 key
e, ok = m.dirty[key]
// 累加 misses 次数
m.missLocked()
}
m.mu.Unlock()
}
// 假如 key 存在,而且其值等于 old,则将其删去。
for ok {
p := e.p.Load()
// 现已被删去,或许值不等于 old,回来 false,标明删去失利
if p == nil || p == expunged || *p != old {
return false
}
// 将其删去(本质上是一个 CAS 操作,将其状况修正为了 nil)
if e.p.CompareAndSwap(p, nil) {
return true
}
}
// key 找不到,回来 false
return false
}
CompareAndDelete 图示
CompareAndDelete 作业流程
- 首先从
read map
中读取key
对应的value
。假如找到则进行CAS
操作,假如没有找到,那么就需求加锁,然后做double checking
。 - 假如仍是没找到。而且
dirty map
中包括了部分read map
中不存在的key
,则从dirty map
中查找,找到则做 CAS 操作,然后累加misses
次数。 - 假如找到了
key
,会经过原子操作读取其之前的值。假如发现它现已被删去或许旧值不等于old
,则回来false
。不然经过CAS
操作将其删去,然后回来true
。 - 假如没有找到
key
,则回来false
。
entry 的一些阐明
entry
这个结构体是 sync.Map
中实践保存值的结构体,它保存了指向了 key
对应值的指针。
在上面阅读代码的进程中,咱们发现,entry
中有许多办法运用了 try
前缀,比方 trySwap
, tryLoadOrStore
等。关于这类办法,咱们需求知道的是:
- 它并不确保操作必定成功,由于一些写操作是不需求持有互斥锁就能够进行的(比方删去操作,仅仅一个原子操作,将
entry
指向了nil
)。 - 这类办法里边,有一个
for
循环,来进行多次测验,直到操作成功,又或许发现entry
现已被删去的时分就回来。相似自旋锁。 - 这类办法里边临
entry
状况的修正是经过CAS
操作来完结的。
sync.Map 源码总结
一顿源码看下来,咱们不难发现,sync.Map
的大部分办法全体处理流程上是十分相似的,都是先从 read map
中读取,假如没有找到,那么就需求加锁,然后做 double checking
。假如仍是没找到,那么就从 dirty map
中查找,假如仍是没找到,那么就回来 false
。
这样做的目的都是在尽量地削减锁的占用,然后取得更好的功能。
一起,假如在 dirty map
中查找的次数多了,会触发 dirty map
转化为 read map
的操作流程,这样一来,下一次查找相同的 key
就不再需求加锁了。
最终一个要害的点是,在 sync.Map
中没有被锁维护的当地,都是经过原子操作来完结的,这样一来,就能够确保在多核 CPU 上的并发安全。
总结
-
sync.Map
中的key
有两份,一份在read map
中,一份在dirty map
中。read map
中的key
是不可变的,而dirty map
中的key
是可变的。 -
sync.Map
中的大多数操作的操作流程如下:- 首先从
read map
中读取key
对应的value
。找到则做相应操作。 - 假如没找到,则加锁,再做一次
double checking
。找到则做相应操作。 - 假如仍是没找到,那么就从
dirty map
中查找,找到则做相应操作。 - 从
dirty map
找到的时分,需求累加misses
次数,假如misses
次数超过了dirty map
的巨细,那么就会触发dirty map
转化为read map
的操作流程。
- 首先从
-
sync.Map
中的read map
和dirty map
中相同的key
指向了同一个value
(是一个entry
结构体实例)。 -
entry
有三种状况:-
nil
: 标明key
已被删去。 -
expunged
: 标明key
已被删去,而且dirty map
中没有这个key
,这个key
只存在于read map
中。 -
*v
: 标明一个指向详细值的指针,是正常状况。
-
-
sync.Map
中的大部分办法都是经过原子操作来完结的,这样一来,就能够确保在多核 CPU 上的并发安全。就算没有在锁维护的临界区内,这种操作仍然能够确保对map
的操作不会出现紊乱的状况。 -
read map
中有一个字段标识了是否dirty map
中存在部分read map
中不存在的key
。这样一来,假如在read map
中找不到key
的时分,就能够先判断一下read.amended
是否为true
,假如是true
,才需求进行加锁,然后再去dirty map
中查找。这样一来,就能够削减加锁的次数,然后取得更好的功能。 -
dirty map
和read map
之间是会彼此转化:- 在
dirty map
中查找key
的次数超过了dirty map
的巨细,就会触发dirty map
转化为read map
的操作流程。 - 需求写入新的
key
的时分,假如dirty map
为nil
,那么会将read map
中未删去的key
写入到一个新创立的dirty map
中。
- 在
-
sync.Map
功能更好的原因:尽量削减了加锁的次数,许多当地运用原子操作来确保并发安全。(假如咱们的业务场景是写多读少,那么这一点或许就不成立了。)