浅析 Go 语言之 sync.map

Go中的 map不是并发安全的，在Go 1.9之后，引入了 sync.Map，即并发安全的map。

先介绍下 sync.Map 的几个特点:

以空间换效率，通过read和dirty两个map来提高读取效率
优先从read map中读取(无锁)，否则再从dirty map中读取(加锁)
动态调整，当misses次数过多时，将dirty map提升为read map
延迟删除，删除只是为value打一个标记，在dirty map提升时才执行真正的删除

有并发问题的map

在Go 1.6之前，内置的map类型是部分goroutine安全的，并发的读没有问题，并发的写可能有问题。官方的 FAQ 已经提到:

内建的map不是线程(goroutine)安全的。

首先，让我们看一段并发读写的代码,下列程序中一个goroutine一直读，一个goroutine一只写同一个键值，即即使读写的键不相同，而且map也没有”扩容”等操作，代码还是会报错。

package main
func main() {
    m := make(map[int]int)
    go func() {
        for {
            _ = m[1]
        }
    }()
    go func() {
        for {
            m[2] = 2
        }
    }()
    select {}
}

错误信息是:

fatal error: concurrent map read and map write。

如果你查看Go的源代码: hashmap_fast.go#L118,会看到读的时候会检查hashWriting标志，如果有这个标志，就会报并发错误。

写的时候会设置这个标志: hashmap.go#L542

h.flags |= hashWriting

hashmap.go#L628设置完之后会取消这个标记。

当然，代码中还有好几处并发读写的检查，比如写的时候也会检查是不是有并发的写，删除键的时候类似写，遍历的时候并发读写问题等。

有时候，map的并发问题不是那么容易被发现, 你可以利用 -race 参数来检查。

Go 1.9之前的解决方案

但是，很多时候，我们会并发地使用map对象，尤其是在一定规模的项目中，map总会保存goroutine共享的数据。在Go官方blog的 Go maps in action一文中，提供了一种简便的解决方案。

var counter = struct{
    sync.RWMutex
    m map[string]int
}{m: make(map[string]int)}

它使用嵌入struct的方式为map增加一个读写锁。

读数据的时候很方便的加锁：

counter.RLock()
n := counter.m["some_key"]
counter.RUnlock()
fmt.Println("some_key:", n)

写数据的时候:

1
2
3

unter.Lock()
counter.m["some_key"]++
counter.Unlock()

sync.Map

可以说，上面的解决方案相当简洁，并且利用读写锁而不是Mutex可以进一步减少读写的时候因为锁带来的性能。

但是，它在一些场景下也有问题，如果熟悉Java的同学，可以对比一下ConcurrentHashMap的实现，在map的数据非常大的情况下，一把锁会导致大并发的客户端共争一把锁，Java的解决方案是:

shard，内部使用多个锁，每个区间共享一把锁，这样减少了数据共享一把锁带来的性能影响。

在Go 1.9 中sync.Map 使用非常简单，和普通 map 相比，仅遍历的方式略有区别：

package main

import (
	"fmt"
	"sync"
)

func main()  {
	var m sync.Map
	// 1. 写入
	m.Store("qcrao", 18)
	m.Store("stefno", 20)

	// 2. 读取
	age, _ := m.Load("qcrao")
	fmt.Println(age.(int))

	// 3. 遍历
	m.Range(func(key, value interface{}) bool {
		name := key.(string)
		age := value.(int)
		fmt.Println(name, age)
		return true
	})

	// 4. 删除
	m.Delete("qcrao")
	age, ok := m.Load("qcrao")
	fmt.Println(age, ok)

	// 5. 读取或写入
	m.LoadOrStore("stefno", 100)
	age, _ = m.Load("stefno")
	fmt.Println(age)
}

第 1 步，写入两个 k-v 对；

第 2 步，使用 Load 方法读取其中的一个 key；

第 3 步，遍历所有的 k-v 对，并打印出来；

第 4 步，删除其中的一个 key，再读这个 key，得到的就是 nil；

第 5 步，使用 LoadOrStore，尝试读取或写入 “Stefno”，因为这个 key 已经存在，因此写入不成功，并且读出原值。

程序输出：

18
stefno 20
qcrao 18
<nil> false
20

sync.map 适用于 读多写少 的场景，对于写多的场景，会导致 read map 缓存失效，需要加锁，导致冲突变多；而且由于未命中 read map 次数过多，导致 dirty map 提升为 read map，这是一个 O(N) 的操作，会进一步降低性能。

源码简析

看下 sync.Map 的数据结构：

// sync/map.go
type Map struct {
   // 当写read map 或读写dirty map时 需要上锁
   mu Mutex

   // read map的 k v(entry) 是不变的，删除只是打标记，插入新key会加锁写到dirty中
   // 因此对read map的读取无需加锁
   read atomic.Value // 保存readOnly结构体

   // dirty map 对dirty map的操作需要持有mu锁
   dirty map[interface{}]*entry

   // 当Load操作在read map中未找到，尝试从dirty中进行加载时(不管是否存在)，misses+1
   // 当misses达到diry map len时，dirty被提升为read 并且重新分配dirty
   misses int
}

// read map数据结构
type readOnly struct {
   m       map[interface{}]*entry
   // 为true时代表dirty map中含有m中没有的元素
   amended bool
}

type entry struct {
   // 指向实际的interface{}
   // p有三种状态:
   // p == nil: 键值已经被删除，此时，m.dirty==nil 或 m.dirty[k]指向该entry
   // p == expunged: 键值已经被删除， 此时, m.dirty!=nil 且 m.dirty不存在该键值
   // 其它情况代表实际interface{}地址 如果m.dirty!=nil 则 m.read[key] 和 m.dirty[key] 指向同一个entry
   // 当删除key时，并不实际删除，先CAS entry.p为nil 等到每次dirty map创建时(dirty提升后的第一次新建Key)，会将entry.p由nil CAS为expunged
   p unsafe.Pointer // *interface{}
}

read map 和 dirty map 的存储方式是不一致的。

前者使用 atomic.Value，后者只是单纯的使用 map。原因是:

read map 使用 lock free 操作，必须保证 load/store 的原子性；而 dirty map 的 load+store 操作是由 lock（就是 mu）来保护的。

结合例子看各种操作的流程图片：

除了Load/Store/Delete之外，sync.Map还提供了LoadOrStore/Range操作，但没有提供Len()方法(这部分只能看官方后续支持)，这是因为:

要统计有效的键值对只能先提升dirty map(可能有read map中没有的键值对)，再遍历m.read(由于延迟删除，不是所有的键值对都有效)，这其实就是Range做的事情，因此在不添加新数据结构支持的情况下，sync.Map的长度获取和Range操作是同一复杂度的。

sync.Map的性能

Go 1.9源代码中提供了性能的测试： map_bench_test.go、map_reference_test.go

我也基于这些代码修改了一下，得到下面的测试数据，相比较以前的解决方案，性能多少回有些提升，如果你特别关注性能，可以考虑sync.Map。

BenchmarkHitAll/*sync.RWMutexMap-4       20000000            83.8 ns/op
BenchmarkHitAll/*sync.Map-4              30000000            59.9 ns/op
BenchmarkHitAll_WithoutPrompting/*sync.RWMutexMap-4             20000000            96.9 ns/op
BenchmarkHitAll_WithoutPrompting/*sync.Map-4                    20000000            64.1 ns/op
BenchmarkHitNone/*sync.RWMutexMap-4                             20000000            79.1 ns/op
BenchmarkHitNone/*sync.Map-4                                    30000000            43.3 ns/op
BenchmarkHit_WithoutPrompting/*sync.RWMutexMap-4                20000000            81.5 ns/op
BenchmarkHit_WithoutPrompting/*sync.Map-4                       30000000            44.0 ns/op
BenchmarkUpdate/*sync.RWMutexMap-4                               5000000           328 ns/op
BenchmarkUpdate/*sync.Map-4                                     10000000           146 ns/op
BenchmarkUpdate_WithoutPrompting/*sync.RWMutexMap-4              5000000           336 ns/op
BenchmarkUpdate_WithoutPrompting/*sync.Map-4                     5000000           324 ns/op
BenchmarkDelete/*sync.RWMutexMap-4                              10000000           155 ns/op
BenchmarkDelete/*sync.Map-4                                     30000000            55.0 ns/op
BenchmarkDelete_WithoutPrompting/*sync.RWMutexMap-4             10000000           173 ns/op
BenchmarkDelete_WithoutPrompting/*sync.Map-4                    10000000           147 ns/op

总结

sync.map 是线程安全的，读取，插入，删除也都保持着常数级的时间复杂度。
通过读写分离，降低锁时间来提高效率，适用于读多写少的场景。
Range 操作需要提供一个函数，参数是 k,v，返回值是一个布尔值：f func(key, value interface{}) bool。
调用 Load 或 LoadOrStore 函数时，如果在 read 中没有找到 key，则会将 misses 值原子地增加 1，当 misses 增加到和 dirty 的长度相等时，会将 dirty 提升为 read。以期减少“读 miss”。
新写入的 key 会保存到 dirty 中，如果这时 dirty 为 nil，就会先新创建一个 dirty，并将 read 中未被删除的元素拷贝到 dirty。
当 dirty 为 nil 的时候，read 就代表 map 所有的数据；当 dirty 不为 nil 的时候，dirty 才代表 map 所有的数据。

参考

由浅入深聊聊Golang的sync.Map