本文依据 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 的全体模型。 它的全体模型如下：

go 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 的作业流程：

  1. 添加 key：假如是第一次写入 key 的话（假设其值为 value），会先写入 dirty map，在 dirty map 中的 value 是一个指向 entry 结构体的指针。entry 结构体中的 p 字段也是一个指针，它指向了 value 的内存地址。
  2. 读取 key：先从 read 中读取（无锁，原子操作），read 中找不到的时分再去 dirty 中查找（有锁）。
  3. 修正 key：假如 key 在 read map 中存在的话，会直接修正 key 对应的 value。假如 key 在 read map 中不存在的话，会去 dirty map 中查找（有锁），假如在 dirty map 中也不存在的话，则修正失利。
  4. 删去 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 就足够了。）

go sync.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。

go sync.Map 设计与实现

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。
  • 正常状况：能够被正常读取。

它们的转化关系如下：

go sync.Map 设计与实现

阐明：

  1. key 被删去
  2. dirty map 为 nil 的时分，需求写入新的 key，read 中被删去的 key 状况会由 nil 修正为 expunged
  3. 被删去的 key，从头写入
  4. 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 字段便是这儿说的标志字段。单单说文字或许有点笼统，咱们能够结合下图了解一下：

go sync.Map 设计与实现

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 图示

go sync.Map 设计与实现

留意：这儿的 read map 和 dirty map 中都没有包括 entry，咱们知道它们中相同的 key 都指向相同的 entry 就能够了。

Swap 的操作流程

  1. 从 read map 中读取 key，假如存在，就直接交流 value，并回来之前的 value。
  2. 假如 read map 中不存在 key，就加锁，加锁后，再从 read map 中读取 key，假如存在，就直接交流 value，并回来之前的 value。（double checking）
  3. 加锁后，假如在 read map 中仍然找不到 key，再从 dirty map 中读取 key，假如存在，就直接交流 value，并回来之前的 value。
  4. 假如 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() 图示：

go sync.Map 设计与实现

dirtyLocked() 里有个需求留意的当地便是，它会将 read map 中的 nil 的 key 转化为 expunged 状况。 expunged 状况标明这个 key 仅仅在 read map 中，而不在 dirty map 中。 做完迁移之后，dirty map 其实就不包括那些被删去的 key 了。

Swap/Store 要害阐明

Swap 办法里边其实基本现已包括了 sync.Map 首要规划理念了，下文讲解其他办法的时分，其间一些细节不再做过多的解说了：

  1. sync.Map 在做许多操作的时分，都会先从 read map 中读取，假如 read map 中不存在，再从 dirty map 中读取。
  2. 假如需求从 dirty map 中读取，那么会先加锁，然后再从 dirty map 中读取。
  3. 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 的查找都遵从以下的查找流程：

go sync.Map 设计与实现

留意：从 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 图示

go sync.Map 设计与实现

其实 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
}

这个进程能够用下图标明：

go sync.Map 设计与实现

Load 作业流程

Load 办法的作业流程如下：

  1. 经过原子操作获取 read map。假如 read map 中存在 key，则直接回来 key 对应的值。
  2. 假如 dirty map 中包括了一些 read map 中不存在的 key，则需求加锁，再次获取 read map。
  3. 假如 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 图示

go sync.Map 设计与实现

LoadOrStore 作业流程

  1. key 在 read map 中找到，测验在 read map 中 Load 或 Store，操作成功则回来。找不到则加锁，然后二次查看（double checking）。
  2. 在 read map 中仍然找不到，可是 key 在 dirty map 中找到，测验在 dirty map 中 Load 或 Store，操作成功则回来。（missLocked）
  3. 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 的逻辑能够用下图标明：

go sync.Map 设计与实现

在 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。

咱们能够结合下图来考虑一下：

go sync.Map 设计与实现

留意：实践中 entry 并不是连续存储的。

expunged 状况阐明：

  1. p == expunged，key 已被删去，而且 dirty map 不为 nil，而且 dirty 中没有这个 key。
  2. p == nil，key 已被删去，而且 dirty map 为 nil，或 dirty[k] 指向该 entry。(Store)
  3. 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 图示

go sync.Map 设计与实现

LoadAndDelete 作业流程

  1. 从 read map 中查找 key，假如找到了，那么直接删去 key（将 entry 的指针设置为 nil），并回来 value。
  2. 假如 read map 中没有找到 key，而且 read.amended 为 true，那么就需求加锁，然后做 double checking。
  3. 加锁后在 read map 仍然找不到，而且 read.amended 为 true，那么就需求从 dirty map 中查找 key。
  4. 一起在临界区内直接履行 delete 操作，将 key 从 dirty map 中删去。一起累加 misses 次数。
  5. 最终，假如找到了 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 图示

go sync.Map 设计与实现

Range 遍历的时分，只会遍历 read map 中的 key。假如 read.amended 为 true，那么就需求加锁，然后做 double checking， 假如二次查看 read.amended 仍是 true，那么就需求将 dirty map 中的数据掩盖到 read map 中。

Range 作业流程

  1. 为了确保能遍历 sync.Map 中一切的 key，需求判断 read.amended 是否为 true。
  2. 假如为 true，阐明只要 dirty map 中包括了一切的 key，那么就需求将 dirty map 转化为 read map。（这样的优点是，能够在遍历进程中，不需求加锁）
  3. 然后开始遍历，遍历的时分只需求遍历 read map 即可，由于这个时分 read map 中包括了一切的 key。
  4. 遍历进程中，假如发现 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 图示

go sync.Map 设计与实现

其实到这儿，咱们应该发现了，其实 sync.Map 的大多数办法的完结都是先从 read map 中读取，假如没有找到，那么就从 dirty map 中读取。 仅仅从 read map 中读取的时分，需求加锁，然后做 double checking。

CompareAndSwap 作业流程

  1. 首先从 read map 中读取 key 对应的 value。假如找到则进行 CAS 操作，假如没有找到，那么就需求加锁，然后做 double checking。
  2. 假如仍是没找到。则从 dirty map 中查找，找到则做 CAS 操作，然后累加 misses 次数。
  3. 假如仍是没找到，那么就回来 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 图示

go sync.Map 设计与实现

CompareAndDelete 作业流程

  1. 首先从 read map 中读取 key 对应的 value。假如找到则进行 CAS 操作，假如没有找到，那么就需求加锁，然后做 double checking。
  2. 假如仍是没找到。而且 dirty map 中包括了部分 read map 中不存在的 key，则从 dirty map 中查找，找到则做 CAS 操作，然后累加 misses 次数。
  3. 假如找到了 key，会经过原子操作读取其之前的值。假如发现它现已被删去或许旧值不等于 old，则回来 false。不然经过 CAS 操作将其删去，然后回来 true。
  4. 假如没有找到 key，则回来 false。

entry 的一些阐明

entry 这个结构体是 sync.Map 中实践保存值的结构体，它保存了指向了 key 对应值的指针。

在上面阅读代码的进程中，咱们发现，entry 中有许多办法运用了 try 前缀，比方 trySwap, tryLoadOrStore 等。关于这类办法，咱们需求知道的是：

  1. 它并不确保操作必定成功，由于一些写操作是不需求持有互斥锁就能够进行的（比方删去操作，仅仅一个原子操作，将 entry 指向了 nil）。
  2. 这类办法里边，有一个 for 循环，来进行多次测验，直到操作成功，又或许发现 entry 现已被删去的时分就回来。相似自旋锁。
  3. 这类办法里边临 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 功能更好的原因：尽量削减了加锁的次数，许多当地运用原子操作来确保并发安全。（假如咱们的业务场景是写多读少，那么这一点或许就不成立了。）
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。