在 Golang 中，map 是一个很重要的数据类型，日常中经常会用到。但是由于协程用得太爽，会暴露出一个严重的问题：map是不能并发写的。
这个就有点尴尬了，毕竟并发写是一个非常常见的场景。所以，各路大神齐显神通除了很多 concurrent map 的库。后来 golang 在 1.9 的时候终于出了官方库，就是 sync.map。
但是一直到现在官方库的性能被吐槽得很厉害，而且应用场景还很局限，只有读远大于写的时候，才比较适用。
不过，不管性能如何，它的实现方法是值得学习一下的。
自己如何实现一个并发map？
如果让我们自己简单的实现一个并发map，大概率会这样写：
import "sync"
type ConcurrentMap struct {
d map[interface{}]interface{}
l sync.RWMutex
}
func (c *ConcurrentMap) Set(key interface{}, value interface{}) {
c.l.Lock()
defer c.l.Unlock()
c.d[key] = value
}
func (c *ConcurrentMap) Get(key interface{}) (interface{}, bool) {
c.l.RLock()
defer c.l.RUnlock()
v, ok := c.d[key]
return v, ok
}
复制代码这样写的方法本身并没错，但问题在于效率太低。原因是锁的开销会比较大。所以，各类的 concurrent map 库都是在“锁”的地方做了一些手脚去优化。万变不离其宗，go官方的 sync.Map 也是通过优化锁的使用来达到效果。
sync.Map 原理
首先来说一下 sync.Map 具体实现的原理：
type Map struct {
mu Mutex
read atomic.Value // readOnly
dirty map[interface{}]*entry
misses int
}
复制代码sync.Map 中，使用了两个原生的 Map 来存放数据，一个叫做 read，一个叫做 dirty；
- 新增数据，会放到 dirty 中；
- 数据读取时，会先读取 read 中的数据，如果没有，再读 dirty 中的数据；
read 就相当于 dirty 的缓存一样。
那么，问题来了，什么时候 dirty 的数据会同步到 read 中呢？
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
read, _ := m.read.Load().(readOnly) // 拿到 read map
e, ok := read.m[key] // 尝试从 read 中获取key的内容
if !ok && read.amended { // read 中没有，而且 read 需要被修正时
m.mu.Lock() // 加锁
read, _ = m.read.Load().(readOnly) // 可能 read 被更新过，重新拿一次
e, ok = read.m[key]
if !ok && read.amended { // 还是没有
e, ok = m.dirty[key] // 从 dirty 中拿
m.missLocked() // 处理击穿缓存
}
m.mu.Unlock() // 解锁
}
if !ok {
return nil, false
}
return e.load()
}
func (m *Map) missLocked() {
m.misses++
if m.misses < len(m.dirty) { return
}
// 如果 misses 小等 dirty 长度
// 使用 dirty 覆盖 read，并清空 dirty
m.read.Store(readOnly{m: m.dirty})
m.dirty = nil
m.misses = 0
}
复制代码misses为什么要这么做呢？原因在于锁！ 当读取 map 的时候，不需要锁，但是写 map 却需要锁来防止并发写。所以，当把“读”和“写”分开的时候，意味着有部分的操作是不需要加锁的，这样就提高了效率。
那为什么这里读 dirty 的时候，还要加锁呢？这是为了防止在重读 read 的时候不要被后面的更新操作打断，也可以保护后面对于 misses 的操作。
那么问题又来了，dirty 复制给了 read，却把自己置为空，dirty 数据不就不完整了嘛？ 确实是的，在某一些时刻，read 中的数据集要大于 dirty。当向 sync.Map 写一个 read 中没有的key 时，sync.Map 会将 read 中的数据同步到 dirty 中。
我们详细看下存储的代码，在标记②的地方，做了这一操作：
func (m *Map) Store(key, value interface{}) {
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok && e.tryStore(&value) {
// 如果 read 中，有要存储的 key，那么就直接尝试使用 CAS 方法来存储；①
return
}
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
if e.unexpungeLocked() {
// 如果 read 中有，但被标记清除了，那么直接把 value 赋值给 dirty；
m.dirty[key] = e
}
// 更新 value 中实际的值
e.storeLocked(&value)
} else if e, ok := m.dirty[key]; ok {
// 如果 read 中没有，dirty 中有，那么更新 dirty 中
e.storeLocked(&value)
} else {
if !read.amended {
// read 和 dirty 都没有，那么就要将 read 中的内容复制一份到 dirty
// 但不包括 标记清除的 key ②
m.dirtyLocked()
m.read.Store(readOnly{m: read.m, amended: true})
}
m.dirty[key] = newEntry(value)
}
m.mu.Unlock()
}
复制代码在上面代码的注释中，多次提到一个概念叫做 “标记清除”。什么是标记清除呢？这里要提到实际存储内容的数据结构
type readOnly struct {
m map[interface{}]*entry
amended bool // true if the dirty map contains some key not in m.
}
type Map struct {
...
read atomic.Value // readOnly
dirty map[interface{}]*entry
...
}
type entry struct {
p unsafe.Pointer // *interface{}
}
复制代码map[interface{}]*entryamended == true使用这种结构有什么好处呢？意味着一个实际的值不需要在 read 和 dirty 中存储两次。因为在上面描述的过程中，read 和 dirty 的存储内容会经常性的进行一些相互同步的工作。如果所有的 map value 存储的是实际的值，那么这么开销会变得非常大。实际上的实现中， read 和 dirty 中，对于同样的 key，存储的是一个 项目 entry 指针。
使用了这种结构之后呢，就可以对于指针的值玩出一点花来。比如说 “标记清除”； 来看删除这块的代码：
func (m *Map) Delete(key interface{}) {
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
if !ok && read.amended { // 如果 read 中没有key，且 read 被标记为修正
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if !ok && read.amended { // 再次验证 read 中没有key，且 read 被标记为修正
delete(m.dirty, key) // 直接删除 dirty 中的 key
}
m.mu.Unlock()
}
if ok { // 如果 read 中有key，则操作 entry 来进行删除
e.delete()
}
// 如果 read 中没有key，且 read 没有标记为修正
}
func (e *entry) delete() (hadValue bool) {
for {
p := atomic.LoadPointer(&e.p) // 获取 entry 的实际内容
if p == nil || p == expunged { // 如果内容已经被置为空，或者 “标记清除”
return false
}
if atomic.CompareAndSwapPointer(&e.p, p, nil) { // CAS “标记清除”
return true
}
}
}
复制代码可以从上面的代码看到，只有当 read 中没有，且 read 是标记修正的情况下，才会加锁去进行删除，否则的话，通过 CAS 的方式，就可以一起将 read 和 dirty 中的key清除掉。
read -> dirty 同步dirty -> read 同步- read -> dirty 同步：不会将 “标记清除” 的 key 同步过去；
- dirty -> read 同步：是直接覆盖；
经过了上面两步，“标记清除” 的 key，就被彻底删除掉了。这也是延迟删除的原理。
sync.Map 绝对不是最好的并发map实现方式，但也许是最合适的。对于支持并发的数据结构来说，一定要针对使用场景选择不同的实现。如果是 “写多读少” 的场景，那么 sync.Map 的开销一定比文章开头最简单的实现也要大。