概要

golang 的 map 本身不是 thread-safe 的，但是通过使用读写锁，我们可以构造出一个 thread-safe 的 syncmap，不过这样写出的性能并不是很令人满意（go-syncmap-benchmark)，在某些场景下，我们需要更高效的 syncmap。

因此 golang 官方提供了一个高效的 syncmap（下面 syncmap 就是指这一实现），本篇文章会分析其源码，看看 syncmap 是如何做到更高效的。

直觉

本篇文章的最主要的目的是探究出为什么 syncmap 能够提供高效的并发效率。在具体阐述之前，有一个直觉可以先建立起来——就是说用最简单的词来描述这个原因——lock free。

代码

数据结构

因为想要借助 lock free 来提高访问效率，那么势必需要增加一些辅助的数据结构来支持 lock free 操作。

在 syncmap 中实际存在两个 map：read map & dirty map。 可以看一下代码中的表示:

mu

那么 read map 和 dirty map 里面究竟存的是什么呢？

entry
entryentry
entry
nil
expunged
nildelete(m, key)expunged

这就要回到一开始提到的问题：

read map 和 dirty map 里面究竟存的是什么呢？ 
entryentry.p
nil
unexpunged
entryentryexpungedentry
entryStoreentryentry

现在知道了 read map 和 dirty map 的是什么了，那么还得理解一个重要的问题是： read map 和 dirty map 是用来干什么的，以及为什么这么设计？

第一个问题的答案的具体细节会在下面的代码流程的分析中进行详细的阐述，但这里可以给出一个简略的答案：read map 是用来进行 lock free 操作的（其实可以读写，但是不能做删除操作，因为一旦做了删除操作，就不是线程安全的了，也就无法 lock free），而 dirty map 是用来在无法进行 lock free 操作的情况下，需要 lock 来做一些更新工作的对象。

至于为什么设计成这样，会在最后一节解释一下。

代码流程

Store

Store
  1. 如果从 read map 中能够找到 normal entry 的话，那么就直接 update 这个 entry 就行（lock free)
  2. 否则，就上锁，对 dirty map 进行相关操作
tryStoreentryexpunged
expungedexpungednilentryexpungedentry
expunged

如果发现这个 key 并不属于 read，但属于 dirty 的时候，直接更新相应的值即可。

read.ameded==falsenildirtyLocked
nilexpungedentrynilentryexpungedentry
Storeamended

至此更新完毕。

StoretryExpungedLocked

Load

LoadStoreok
Store

其中 fast path 依旧利用了支持 lock free 的 read map，但是如果发现这个 key 不存在于 read map 中的时候，我们就需要去 dirty map 里面找了（从之前的图我们知道 dirty map 中是存在一部分新加入的、不在 read map 中的 key ）。

entrymisslockedmsslocked
missesnil
entryentry.load
nilexpungedentryok=false

Delete

DeleteLoad

最后看一下 entry 的 delete 方法：

这里比较奇怪的是为什么需要一个 bool 的返回值，其他地方也确实没有使用到这个返回值，这一点笔者也不是很明白。

entrynil
entrynilexpunged
entryunexpungedentrynilexpungedentryexpunged

Load Store Delete

Load Store Delete


read map 和 dirty map 的设计分析

最核心和最基本的原因就是： 通过分离出 readonly 的部分，从而可以形成 lock free 的优化。

entry
entrymissLocked

syncmap 的缺陷

其实通过上面的分析，了解了整个流程的话，读者会很容易理解这个 syncmap 的缺点：当需要不停地新增和删除的时候，会导致 dirty map 不停地更新，甚至在 miss 过多之后，导致 dirty 成为 nil，并进入重建的过程。

关于 lock free 的启发

lock free 会给并发的性能带了较高的提升，目前通过 syncmap 的代码分析，我们也对 lock free 有一些了解，下面会记录一下笔者从 syncmap 中得到的对 lock free 的一些理解。

recheck in slow path when failed in fast path

我们发现，在 read map 中读取失败的时候，我们会有进入持有 lock 的关键区，这个时候，需要注意代码都不能依赖之前的 atomic read，这点虽然很简单，但是也是一种常见的 pattern 吧。

update based on read via CAS

从 syncmap 中，我们还很容易发现这样的代码：

理论上这是使用 CAS 的一种常见操作，就是我们在做一次更新的时候，需要依据某次读操作，只有读操作满足了一定的条件我们才能完成我们的写操作，而 CAS 正是为了这样的 update 而存在的，也是 lock free（其实也包括 lock）实现的关键所在。

safe to check an ending state

其实从上面的这段例子代码，我们可以发现一点细节，为什么需要用 forloop 去不停地检查呢？如果不用 forloop 去做更新的话，代码时这样的：

要说正确性的话，这样做是对的，那么使用 forloop 一定是为了做什么优化了。

p==nilentryp!=nil

但是其实这个 key 已经被删除了，可以不用转移到 dirty 中去了，所以加上 forloop 就能检查出上面提到的这种情况，达到一点点性能上的优化。

expungedStore
expungedexpungedexpungednil
expungedexpungedexpungedexpunged

Reference