Golang sync.Map 源码分析

Posted on | Edited on

Background

Golang 内置的 Map 是采用 Array + LinkedList 的实现，很明显在高并发的情况下会出现问题，比如并发的扩容，并发的插入元素。因此在并发的情况下，如果不主动加锁，则需要另外的，线程安全的数据结构。

Java 中有一个 ConcurrentHashMap 的数据结构，是采用减少锁粒度的方式，将 HashMap 进行 shard。这样的话，如果两次 read or write 落在了不同的 shard 上，就可以进行并发的读写，从而在保证线程安全的基础上，增加了效率。

Golang 也有一个类似的第三方库，concurrent-map，也是采用了同样的思路。但是 golang 1.9 引入的 sync.Map 却是采用了另外一种做法。

Overview

首先，仔细看的话，sync.Map 前有这样一段说明：

The Map type is optimized for two common use cases: 
(1) when the entry for a given key is only ever written once but read many times, as in caches that only grow, or 
(2) when multiple goroutines read, write, and overwrite entries for disjoint sets of keys. In these two cases, use of a Map may significantly reduce lock contention compared to a Go map paired with a separate Mutex or RWMutex.

也就是说，golang 官方建议，大多数情况下大家使用 Map + Mutex 的形式就可以了，当你想要使用 sync.Map 的时候，如果你的场景是类似于缓存这种形式，读多写少；或者是并发的写线程一般不会产生交集的时候，可以使用这个数据结构。那么为什么会有这样的建议？

sync.Map 主要利用了空间换时间、CAS来加速并发的读写。核心的数据结构：

Map

type Map struct {
	mu Mutex                        // 锁
	read atomic.Value               // map 其一，稳定的老数据。由 atomic 保证线程安全
	dirty map[interface{}]*entry    // map 其二，在 read 中找不到的情况下，会进入 dirty 寻找
	misses int                      // 进入 dirty 寻找的次数，当大于当前 dirty 的长度时，会将 dirty 中内容复制进 read
}

// read atomic 对应的值
type readOnly struct {
	m       map[interface{}]*entry  // entry保存着实际内容的 unsafePointer
	amended bool                    // true if the dirty map contains some key not in m.
}

注释中简单介绍了各个值的内容，当然，源码中也很清楚的解释了各个字段的意义。

因此在更新的过程中，map 中的 read 和 dirty 会存在如下状态：

  1. 刚初始化时，read 和 dirty 都为空
  2. 刚开始插入数据时，read 为空，dirty 不为空
  3. 不断 load，当 misses 数达到阈值时，flush dirty 到 read。此时 read 不为空，dirty 为空
  4. 继续插入数据，此时 read 和 dirty 都不为空

接下去分析一下核心的 Load、Store、Delete 的实现，代码为 golang 1.11.2 版本

Load

102 // Load returns the value stored in the map for a key, or nil if no
103 // value is present.
104 // The ok result indicates whether value was found in the map.
105 func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
106 	read, _ := m.read.Load().(readOnly)
107 	e, ok := read.m[key]
108 	if !ok && read.amended {
109 		m.mu.Lock()
110 		// Avoid reporting a spurious miss if m.dirty got promoted while we were
111 		// blocked on m.mu. (If further loads of the same key will not miss, it's
112 		// not worth copying the dirty map for this key.)
113 		read, _ = m.read.Load().(readOnly)
114 		e, ok = read.m[key]
115 		if !ok && read.amended {
116 			e, ok = m.dirty[key]
117 			// Regardless of whether the entry was present, record a miss: this key
118 			// will take the slow path until the dirty map is promoted to the read
119 			// map.
120 			m.missLocked()
121 		}
122 		m.mu.Unlock()
123 	}
124 	if !ok {
125		return nil, false
126 	}
127 	return e.load()
128 }

Load 函数的主要分支逻辑如下：

  1. 如果在 read 中找到，则返回
  2. 如果 read 中 amended 标记为 true，则去 dirty 中找
  • line 108 - line 123 执行的是第二个分支。很明显这里用到了双重检查（double check），因为在第一次判断 read 中是否存在 key 到进入 mutex 保护这段时间内，其他的线程可能修改了其中的值。
  • line 120 中的 missLocked 是关键点之一，在这里进行了 misses 的更新及检查。 
    343 func (m *Map) missLocked() {
    344     m.misses++
    345 	if m.misses < len(m.dirty) {
    346 		return
    347 	}
    348 	m.read.Store(readOnly{m: m.dirty})
    349 	m.dirty = nil
    350 	m.misses = 0
    351 }

Store

135	// Store sets the value for a key.
136	func (m *Map) Store(key, value interface{}) {
137	    read, _ := m.read.Load().(readOnly)
138	    if e, ok := read.m[key]; ok && e.tryStore(&value) {
139	        return
140	    }
141	
142	    m.mu.Lock()
143	    read, _ = m.read.Load().(readOnly)
144	    if e, ok := read.m[key]; ok {
145	        if e.unexpungeLocked() {
146	            // The entry was previously expunged, which implies that there is a
147	            // non-nil dirty map and this entry is not in it.
148	            m.dirty[key] = e
149	        }
150	        e.storeLocked(&value)
151	    } else if e, ok := m.dirty[key]; ok {
152	        e.storeLocked(&value)
153	    } else {
154	        if !read.amended {
155	            // We're adding the first new key to the dirty map.
156	            // Make sure it is allocated and mark the read-only map as incomplete.
157	            m.dirtyLocked()
158	            m.read.Store(readOnly{m: read.m, amended: true})
159	        }
160	        m.dirty[key] = newEntry(value)
161	    }
162	    m.mu.Unlock()
163	}

Store 函数的主要分支逻辑如下：

  1. 如果 read 中存在且没有被删除(没有被标记为 expunge)，则直接使用 CAS 进行更新
  2. 如果 read 中存在且被删除了，则将其存在 dirty 中，原因在 Delete 函数的说明中
  3. 如果 dirty 中存在，则将其存在 dirty 中
  4. 这时候，如果 read 中的 amended 标记为 false, 则需要重新构建 dirty map，将 read 中的数据拷贝至 dirty，然后将数据存在 dirty 中
  • dirtyLocked 函数中负责将 read 中没有标记为 expunge 的值拷贝到 dirty 中。在这里会将 nil 改成 expunge

Delete

270  // Delete deletes the value for a key.
271  func (m *Map) Delete(key interface{}) {
272          read, _ := m.read.Load().(readOnly)
273          e, ok := read.m[key]
274          if !ok && read.amended {
275                  m.mu.Lock()
276                  read, _ = m.read.Load().(readOnly)
277                  e, ok = read.m[key]
278                  if !ok && read.amended {
279                          delete(m.dirty, key)
280                  }
281                  m.mu.Unlock()
282          }
283          if ok {
284                  e.delete()
285          }
286  }

相比之下 Delete 函数就显得十分小巧了，

  1. read 中找到了则将其改成 nil
  2. dirty 中找到了则直接删除

小结

理解这三个函数，需要理解一个元素从插入到 Map，然后进行更新，最后到删除是如何在 read 和 dirty 中流转的，以及元素的三个状态，Normal, Expunged, Nil之间的转换。
可以直接参考代码中关于 entry 状态的注释。

eg.

step op read dirty
1 Store (1, 1) nil (1,1)
2 Store (2, 2) nil (1,1) (2,2)
3 Load and trigger missLocked (1,1) (2,2) nil
4 Delete 1 (1,nil) (2,2) nil
5 Store (1, 1) (1,1) (2,2) nil
6 Delete 2 (1,1) (2,nil) nil
7 Store (3, 3) and trigger dirtyLocked (1,1) (2,expunged) (1,1) (3,3)
8 Load and trigger missLocked (1,1) (3,3) nil

You can view sample code from here

Benchmark

运行了 golang 提供的 benchmark，一次典型结果如下：

goos: windows
goarch: amd64
pkg: sync
BenchmarkLoadMostlyHits/*sync_test.DeepCopyMap-8         	100000000	        11.7 ns/op	       7 B/op	       0 allocs/op
BenchmarkLoadMostlyHits/*sync_test.RWMutexMap-8          	30000000	        47.0 ns/op	       7 B/op	       0 allocs/op
BenchmarkLoadMostlyHits/*sync.Map-8                      	100000000	        12.0 ns/op	       7 B/op	       0 allocs/op
BenchmarkLoadMostlyMisses/*sync_test.DeepCopyMap-8       	200000000	         7.97 ns/op	       7 B/op	       0 allocs/op
BenchmarkLoadMostlyMisses/*sync_test.RWMutexMap-8        	30000000	        50.9 ns/op	       7 B/op	       0 allocs/op
BenchmarkLoadMostlyMisses/*sync.Map-8                    	200000000	         8.25 ns/op	       7 B/op	       0 allocs/op
BenchmarkLoadOrStoreBalanced/*sync_test.RWMutexMap-8     	 3000000	       377 ns/op	      71 B/op	       2 allocs/op
BenchmarkLoadOrStoreBalanced/*sync.Map-8                 	 3000000	       361 ns/op	      70 B/op	       3 allocs/op
BenchmarkLoadOrStoreUnique/*sync_test.RWMutexMap-8       	 2000000	       745 ns/op	     178 B/op	       2 allocs/op
BenchmarkLoadOrStoreUnique/*sync.Map-8                   	 2000000	       783 ns/op	     163 B/op	       4 allocs/op
BenchmarkLoadOrStoreCollision/*sync_test.DeepCopyMap-8   	200000000	         6.58 ns/op	       0 B/op	       0 allocs/op
BenchmarkLoadOrStoreCollision/*sync_test.RWMutexMap-8    	20000000	        86.0 ns/op	       0 B/op	       0 allocs/op
BenchmarkLoadOrStoreCollision/*sync.Map-8                	200000000	         6.71 ns/op	       0 B/op	       0 allocs/op
BenchmarkRange/*sync_test.DeepCopyMap-8                  	  500000	      3511 ns/op	       0 B/op	       0 allocs/op
BenchmarkRange/*sync_test.RWMutexMap-8                   	   30000	     51957 ns/op	   16384 B/op	       1 allocs/op
BenchmarkRange/*sync.Map-8                               	  500000	      3701 ns/op	       0 B/op	       0 allocs/op
BenchmarkAdversarialAlloc/*sync_test.DeepCopyMap-8       	 2000000	       876 ns/op	     535 B/op	       1 allocs/op
BenchmarkAdversarialAlloc/*sync_test.RWMutexMap-8        	20000000	        64.5 ns/op	       8 B/op	       1 allocs/op
BenchmarkAdversarialAlloc/*sync.Map-8                    	 5000000	       266 ns/op	      52 B/op	       1 allocs/op
BenchmarkAdversarialDelete/*sync_test.DeepCopyMap-8      	10000000	       225 ns/op	     168 B/op	       1 allocs/op
BenchmarkAdversarialDelete/*sync_test.RWMutexMap-8       	20000000	        77.7 ns/op	      25 B/op	       1 allocs/op
BenchmarkAdversarialDelete/*sync.Map-8                   	20000000	        66.6 ns/op	      19 B/op	       1 allocs/op
PASS
ok  	sync	42.080s
Success: Benchmarks passed.

可以看到在读场景下，几乎和不加锁有一样的性能，遥遥领先单纯的简单加锁实现；
在需要不断的写入的场景时，每次写入其实都需要加锁，和简单加锁实现的性能几乎一致；
在读取 key 比较分散的场景下和不加锁性能几乎一样；
在 BenchmarkAdversarialAlloc 中，因为每次 load 都触发了锁，性能下降明显。

因此，这个数据结构和单纯的加锁来看，在读多写少的场景下有很明显的提升，但是对于读写比例差不多的情况下，并没有比加锁的版本有很大的性能提升；在一些极端场景下，比如一直有写入，并且一直读新值，甚至还不如单纯的加锁实现。根据自己的场景，选择合理的数据结构很重要。

EOF