Map Mutex and Sync.Map
Table of Contents
本文参照 go 版本为 1.15.1
1. Go 中的 map
Go 中的 Map 是非线程安全的
在这里可以看到 go 官方的解释为什么 map 并没有设计成一个线程安全的数据结构
在并发写会导致 panic,例如下图的代码运行时就会出现 concurrent map write 错误
2. 并发的使用 Map
目前有两种方式来使用
2.1. 手动的加锁
var aa = struct {
sync.RWMutex
m map[string]int
}{m: make(map[string]int)}
2.2. sync 包中的 Map
sync 包中提供了 Map 这样一个数据结构可以直接使用，但是使用方式与 map 略有差别
3. sync Map 的实现
在看 sync Map 的具体实现前首先需要做一点准备工作
3.1. Double Check
双检查为了避免程序在加锁的过程中出现准备锁住的数据已经被其他线程更改的情况。
只有加锁后才能确定，数据是不会其他线程改变。所以加锁后要再次的进行一次检查。
3.2. Compare And Swap
CAS 是一种原子操作，目的是为了在多线程中实现不被打断的数据交换操作，
从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题
一般都是基于 CPU 提供的原子指令实现
先判断旧地址与内存中的地址是否相同，如果相同就更改地址为新值返回成功
如果不同返回失败
go 中 CAS 操作的逻辑简化为代码
if *addr == old {
*addr = new
return true
}
return false
3.3. Map 的数据结构
| mu | 是一个锁用来在处理 dirty 中数据是保证安全 |
| read | 实际上是一个保存 readOnly 结构的 atomic.Value,用来只读 |
| dirty | 是一个 map 大部分操作都是在 dirty 上进行，map 的值是一个指针 |
| misses | 用来计数，当 miss 数量大于一定的值时将 dirty 变为 read |
3.4. Store
func (m *Map) Store(key, value interface{})
1.判断 key 是否在 read 中存在，如果存在则尝试将 value 写入跳转到 trystore 流程
2.如果不存在，上锁开始新键的存储过程
3.进行一次 Double check
4.如果在 read 中读取到了值，说明在上锁前有其他的线程存了相同的键，这时候判断这个 key 是否之前被删除过 如果之前被删除了，添加这个数据到 dirty 表中； 将 value 保存到 entry 当中
5.如果在 read 中没有读到了 value，但是在 dirty 中读到了 value，直接修改 value
6.如果 read 和 dirty 表中都没有数据；分为两种情况，1）read 的 amended 字段是 false，这时 read 与 dirty 的数据相同 此时是将 value 保存到一个新的 dirty 表当中,这时要将 read 表中的数据复制给 dirty，将为 nil 的数据置为 expunged 然后修改 read 的 amended 字段。2）read 的 amended 字段是 true，这时 read 与 dirty 的数据已经不同，所以无需操作。无 论是哪一种情况，最后都要将 dirty 中的值修改
7.解锁，存储的过程结束
3.4.1. trystore
func (e *entry) tryStore(i *interface{}) bool
trystore 判断 entry 是否已经被删除了，如果被删除了就返回 false
如果没有被删除，则使用 atomic 中的 CompareAndSwapPointer 对 entry 与 i 进行比较交换
3.5. Load
func (m *Map) Load(key interface{}) (value interface{}, ok bool)
Load 这个函数较为简单，所以我们关注一下是如何取走，以及 missLocked 会触发什么操作
1.先从 read 中读,如果 read 中有那么直接取走
2.如果 read 中没有，且 amended 为 false，那么 dirty 中也没有，直接返回空
3.如果 read 中没有，amended 为 true，开始检查 dirty
4.首先上锁，然后进行双检查，并从 dirty 的 map 中读取，无论是否读到都会触发一次 missLocked
5.解锁返回取到的值或者是 nil
3.5.1. load
func (e *entry) load() (value interface{}, ok bool)
load 操作实际上是 atomic 包中的 LoadPointer，从 Loadpointer 中拿到值后判断是否为空或者是已经被删除， 如果拿到了值返回这个指针
3.5.2. missLocked
misses 这个值决定了什么时候 dirty 变为 read，无论是否读到都会触发一次，官方说这是为了减少 dirty 提升为 read 的步骤
1.将现有的 misses 加一
2.如果现有的值比 dirty 的长度小，就什么都不做
3.misses 大于等于 dirty 长度时,将 dirty 直接保存为 read，然后将 dirty 置为 nil，misses 归零
3.6. Delete && LoadAndDelete
func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool)
func (m *Map) Delete(key interface{})
delete 与 loadAndDelete 逻辑是完全相同的，只是 delete 没有返回值
1.先从 read 中读如果读到了直接进行删除 delete
2.如果 read 中没有读到并且 read 的 amended 字段修改过，dirty 中有可能会存在
3.加锁 双检查 重新读一次这个 key 并触发一次 missLocked 然后解锁进行删除
4.如果 read dirty 都不存在返回 nil
3.6.1. delete
func (e *entry) delete() (value interface{}, ok bool)
delete 操作和 trystore 操作相差不多，只不过在 CAS 的过程里将新的地址换成了 nil
4. 什么场景下用 sync.Map
1.如果 Map 是一个写一次但是会读很多次时
2.如果多 goroutine 去读、写、重写、许多不相交的 key 时