Golang 为并发编程提供了多种并发原语(Mutex、RWMutex、sync.Map)，用于临界区的数据访问和保护；开发应用时，面对不同的场景如何选择合适的并发原语，使功能正常实现的同时提供更高的性能；在互联网应用中，由并发原语保护的临界区从本质上来说无非三种情况：读多写少、写多读少、读写一致。 上篇文章介绍了 sync.RWMutex并发原语，其适用于写多读少的场景；Mutex、RWMutex 其保护的都是某个临界状态区，无论是访问、存储都使用锁进行保护；当操作频繁且要求性能的情况下，锁的优化已无法满足业务需求，此时就需要考虑额外的方式来提升性能。对于读多写少的场景，最常用的方式是进行读写分离，将访问压力分散至其它组件。
Golang为了支持读多写少的场景，提供了sync.Map并发原语，由普通map、Mutex与原子变量组合而成，作为一个并发安全的map，部分情况下读、写数据通过原子操作避免加锁，从而提高临界区访问的性能，同时在高并发的情况下仍能保证数据的准确性，支持Load、Store、 Delete、 Range等操作，可以实现对sync.Map的遍历以及根据key获取value；sync.Map可以有效地替代锁的使用，提高程序的执行效率。
设计原理
讨论设计原理前，先观察下sync.Map的结构定义，主要三种元素组成：map、mutex、atomic
代码语言：javascript复制type Map struct {
mu Mutex
read atomic.Value // readOnly
dirty map[interface{}]*entry
misses int
}
// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
m map[interface{}]*entry
amended bool
}sync.Map 采用了装饰器 模式，在普通的map上组合其它结构进行修饰，在利用map快速定位某个元素的同时增加了读写分离的功能，当元素在只读组件read中时，使用原子操作避免加锁快速访问其数据，在sync.Map中新增元素或访问不存在的元素时操作dirty组件时使用锁操作进行保护，当只读组件read的命中率降低至一定阈值时触发状态转换，将dirty状态提升为最新的read状态，以降低访问sync.Map时加锁的次数。
下面将介绍sync.Map中每个状态字段的功能及其含义
- read 提供读写分离的读功能，使用atomic.Value原子操作提供并发的能力，当数据在read中时原子操作可以避免加锁提供并发访问的能力；当read的命中率降低到一定阈值时，触发将脏数据dirty更新为read，此时需要加锁保护。read实际使用map存储数据，它存储的*entry字段值可以使用CAS操作并发更新，且该*entry与dirty中存储的值指向同一地址，因此CAS修改后操作结果，read与dirty都可以观察到。
- Map.read的原子状态中实际存储的结构为readOnly，它是一个“只读数据”，此处的只读是指readOnly.m的值不会修改，而不是说它存储的key的value值不会修改；因此数据库概念中理解的读写分离不同。
- 其中m存储k-v数据，是dirty的一个子集，注意的是：它存储的某个key的数据值与dirty中该key存储的值指向同一个地址，因此当修改read中某个key的值时，dirty中该key的值也会同步修改；
- amended 表示dirty中是否含有readOnly.m不存在的数据.
- dirty 提供读写分离的写功能，是一个非线程安全的map，用Mutex锁进行保护。包含所有key的数据，其中key可以分为两类，仅存在于dirty的新数据、read与dirty中都存在的数据。当查询某个key时，如果read中不存在，且其amended状态为true，表示dirty中存在read未包含的数据，需要再查询dirty中是否包含该key.
- mu 互斥锁保护 read、dirty，在两种情况下需要加锁对sync.Map的状态进行保护；1. 从dirty中读写数据时，需要使用互斥锁保护，避免并发操作导致非线程安全的map触发panic；2. 从read状态更新开始累计统计加锁操作的数量misses（即命中read状态失败的次数），如果命中失败的次数大于dirty中元素的数量时，sync.Map的命中率太低需要将dirty提升为read，提升过程中使用锁进行保护。
- misses 累计从read更新后进行加锁操作的数量（即read状态命中失败的次数）（例如：当查询key时，如果read中未找到，需要加锁查询dirty；或向 dirty中写入数据需要加锁保护），当misses值大于等于dirty中包含的元素数量时，将dirty提升为read，并将dirty置为nil.
功能实现
sync.Map提供了Load、Store、Delete、Range基础操作，以及LoadAndDelete、LoadOrStore复合操作，下面将介绍sync.Map如何实现这些功能、以及在读多写少情况下提供高性能的原因。
Load 读取操作
- 从read只读的原子状态中查找，避免加锁，如果存在，则返回数据；如果不存在，且amended为false，表示dirty未包含read中不存在的数据，直接返回.
- 快速路径，使用原子操作，避免加锁
- read中不存在且amended为true（表示dirty中含有read不存在的数据），进入慢路径，查询dirty；此时先上锁，再次查询read，防止在获取互斥锁期间 dirty提升为read；仍然不存在且amended仍为true，则查寻dirty，无论是否找到，都调用missLocked将统计值misses递增，表示使用了一次互斥锁。
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
// 1. 先查询只读的原子状态
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
// 2. 不存在，且amended为true，进入慢路径
if !ok && read.amended {
// 2.1 获取互斥锁
m.mu.Lock()
// 2.2 再次查询只读的原子状态，存在获取互斥锁期间read状态被更新的情况
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
// 2.3 仍然不存在，查询dirty
if !ok && read.amended {
e, ok = m.dirty[key]
// 2.4 将统计数据累加，达到条件时，将dirty提升为read
m.missLocked()
}
m.mu.Unlock()
}
if !ok {
return nil, false
}
// 返回存储的数据
return e.load()
}missLocked 有两个功能：
- 累计read更新后命中丢失的次数
- 当命中丢失次数达到阈值时，将dirty提升为read，并将dirty置为nil，misses状态清0；将dirty提升read后，提升下次只读状态read查询的命中率，避免加锁。
func (m *Map) missLocked() {
m.misses
if m.misses < len(m.dirty) {
return
}
m.read.Store(readOnly{m: m.dirty})
m.dirty = nil
m.misses = 0
}entry.load: sync.Map的 read、dirty中存储数据时，实际用户的数据是存储在entry.p中，存储了用户对象的地址，当从read或dirty查询到对象时，需要使用load 方法加载出用户对象。
如果entry.p为nil或expunged，则表示用户对象已被删除。
代码语言：javascript复制type entry struct {
p unsafe.Pointer // *interface{}
}
func (e *entry) load() (value interface{}, ok bool) {
p := atomic.LoadPointer(&e.p)
if p == nil || p == expunged {
return nil, false
}
return *(*interface{})(p), true
}
entry.p 存储值逻辑上有3种状态，value（存储了用户对象）、nil、expunged.
- value: 存储了用户对象，允许从一个old_value更新到new_value
- nil: 当删除对应的key时，不会立即将key从sync.Map中删除，而是将它的值设为nil，表示逻辑上删除；当map运行过程中，从只读的read状态构建写状态dirty时，对于值为nil的key，将其设置为expunged态，对于expunged态的key不写入dirty，当下次dirty提升为read状态时，expunged态的key由于未被任何状态记录从而被统一删除。
- expunged: 将一个key标识为擦除，处于该状态的key只存在于read状态中，dirty中不存在；因此当存储一个key对应的值时，如果它key对应的状态为擦除态，需要先将其修改为nil添加到dirty中，才可以更新entry对应的p值；如果直接由expunged更新为new_value，会导致read与dirty状态不一致。
- 一个key的删除，从逻辑上立即需要两轮 dirty->read的提升才会被真正删除；在删除key后的第一次dirty->read提升，将key的值从nil -> expunged；在第二轮将标记为expunged值丢弃由GC回收.
Store 存储操作
将一个新对象记录到sync.Map或更新已有的对象，对于不同的对象，使用不同的方式提供执行效率。
- 更新一个存在于read状态中的非擦除对象时，使用CAS原子操作避免加锁，提高执行效率。
- 更新一个存在的擦除对象时，需要加锁将对象设置为nil，添加到dirty中，再从nil更新为新值。
- 更新一个存在于dirty中的对象时，加锁将它的值设置为new_value
- 更新一个新对象时，加锁更新read的状态amended为true，表示dirty含有read不存在的对象，并将新key对应的对象存入dirty
Note: 在存储对象时，虽然某些情况下存在加锁行为，但并未累计加锁数量 misses.
代码语言：javascript复制func (m *Map) Store(key, value interface{}) {
// 1. 更新已存在的非擦除态对象
// 使用CAS原子操作，避免加锁
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}
// 2. 加锁
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
// 2.1.1 更新已存在的擦除态对象，先更新它的状态为nil，
// 并将它添加到dirty中
if e.unexpungeLocked() {
// The entry was previously expunged, which implies that there is a
// non-nil dirty map and this entry is not in it.
m.dirty[key] = e
}
// 2.1.2 将nil更新为为new_value
e.storeLocked(&value)
} else if e, ok := m.dirty[key]; ok {
// 2.2 更新存在与dirty中对象，将它的值更新为new_value
e.storeLocked(&value)
} else {
// 2.3.1 添加一个新对象，先更新read.amended，表示dirty中存在
// read不含有得key
if !read.amended {
m.dirtyLocked()
m.read.Store(readOnly{m: read.m, amended: true})
}
// 2.3.2 将key对应的值存入dirty
m.dirty[key] = newEntry(value)
}
m.mu.Unlock()
}
// 将entry中元素的状态由expunged修改为nil
func (e *entry) unexpungeLocked() (wasExpunged bool) {
return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}
func (m *Map) dirtyLocked() {
if m.dirty != nil {
return
}
// 当dirty提升为read后，dirty会被置为nil
// 因此当未来向dirty中添加元素时，需要先构建新dirty的状态
// 因为dirty要包含所有有效的key元素，所以新构建dirty状态时，
// 将read中存储有效值的数据也存储至dirty中
read, _ := m.read.Load().(readOnly)
m.dirty = make(map[interface{}]*entry, len(read.m))
for k, e := range read.m {
// 将包含有效值的元素存入dirty
if !e.tryExpungeLocked() {
m.dirty[k] = e
}
}
}
// 将entry中状态为nil的元素置为expunged，表示它已被逻辑删除
// 当返回值为true时，表示元素已被删除，否则，元素为一个有效值
func (e *entry) tryExpungeLocked() (isExpunged bool) {
p := atomic.LoadPointer(&e.p)
for p == nil {
if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
return true
}
p = atomic.LoadPointer(&e.p)
}
return p == expunged
}Delete 删除操作
删除Key对应的元素，对于不同的对象，有不同的删除方式
- 存在于read中的对象，使用原子操作避免加锁，将查询到的对象使用CAS操作将元素值置为nil，从逻辑上删除
- 仅存在于dirty的对象，累计命中率丢失的次数，并使用CAS操作将元素值置为nil，从逻辑上删除
// Delete deletes the value for a key.
func (m *Map) Delete(key interface{}) {
m.LoadAndDelete(key)
}
func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
//1. 使用原子操作查询read状态
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
if !ok && read.amended {
//2. 未查到，加锁查询dirty
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if !ok && read.amended {
e, ok = m.dirty[key]
delete(m.dirty, key)
//3. 累计加锁的数量，触发状态提升
m.missLocked()
}
m.mu.Unlock()
}
// 4. 查询到key，将key的值置为nil，进行逻辑上删除
if ok {
return e.delete()
}
return nil, false
}
// 将元素从逻辑上进行删除，将状态置为nil
func (e *entry) delete() (value interface{}, ok bool) {
for {
p := atomic.LoadPointer(&e.p)
if p == nil || p == expunged {
return nil, false
}
if atomic.CompareAndSwapPointer(&e.p, p, nil) {
return *(*interface{})(p), true
}
}
}Range 遍历操作
提供了O(N)的方式遍历sync.Map，用户传入遍历key-value的动作函数，如果函数返回false，则遍历终止；即使在遍历过程中发生key的并发读写操作，每个key也仅会被最多遍历一次。 因为 dirty可能包含read中不存在的key的状态，当遍历操作发生时，如果dirty与read存储的有效key的状态不一致，将dirty提升为read。
- read包含所有有效元素时，直接便利read中存储的值
- dirty含有read中不存在的元素时，将dirty提升为read，再遍历新read中存储的值
func (m *Map) Range(f func(key, value interface{}) bool) {
read, _ := m.read.Load().(readOnly)
// 1. dirty中包含read不存在的状态，
// 将dirty提升为read.
if read.amended {
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
if read.amended {
read = readOnly{m: m.dirty}
m.read.Store(read)
m.dirty = nil
m.misses = 0
}
m.mu.Unlock()
}
// 2. 遍历read，当动作函数返回false时，退出遍历。
// 由于遍历过程中可能存在map的并发修改操作，因此当遍历该entry时，
// 实际存储的值被删除时，则不再遍历.
for k, e := range read.m {
v, ok := e.load()
if !ok {
continue
}
if !f(k, v) {
break
}
}
}
func (e *entry) load() (value interface{}, ok bool) {
p := atomic.LoadPointer(&e.p)
if p == nil || p == expunged {
return nil, false
}
return *(*interface{})(p), true
}LoadAndDelete 复合操作
与Delete操作一样，仅增加了返回值传递被删除的对象.
LoadOrStore 复合操作
如果key存在，则返回已存在的值，否则将传入的参数存入Map并返回。loaded 为true ，表示返回的值为以前存在的旧值，值为false，返回的值为传入的参数。
执行逻辑与Store类似，也是4种场景
- read中存在key的有效值，不更新返回已存在的值
- read中存在key但是它的值被逻辑删除nil，则将其更新为传入的新值；
- read中存在key但是它的值被擦除expunged，则先将它的状态更新为nil，将它存入dirty，并更新它为传入的新值
- dirty中存在key的有效值，不更新且返回已存在的值
- dirty中存在key但是它的值被逻辑删除nil，则将其更新为传入的新值
- 一个新加入的key，将它存入dirty，并更新readOnly的amended状态未true
func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
// Avoid locking if it's a clean hit.
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
actual, loaded, ok := e.tryLoadOrStore(value)
if ok {
return actual, loaded
}
}
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
if e.unexpungeLocked() {
m.dirty[key] = e
}
actual, loaded, _ = e.tryLoadOrStore(value)
} else if e, ok := m.dirty[key]; ok {
actual, loaded, _ = e.tryLoadOrStore(value)
m.missLocked()
} else {
if !read.amended {
// We're adding the first new key to the dirty map.
// Make sure it is allocated and mark the read-only map as incomplete.
m.dirtyLocked()
m.read.Store(readOnly{m: read.m, amended: true})
}
m.dirty[key] = newEntry(value)
actual, loaded = value, false
}
m.mu.Unlock()
return actual, loaded
}tryLoadOrStore执行逻辑，entry中存储的值存在三种状态：有效值、nil、expunged
- expunged：该值已被擦除，当前仅存在于read状态中，不允许直接更新为新值，因此直接返回。
- 有效值：存在一个有效值，直接返回该旧值，不更新为新值。
- nil: key对应的对象被逻辑删除，可以被设置为新值，如果设置成功则返回。因为entry会被其它go程并发读写调用，因此更新失败时需要判断它的状态是否为expunged或有效值状态，是则表示值被其它go程更新，返回对应的值。
func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) {
p := atomic.LoadPointer(&e.p)
if p == expunged {
return nil, false, false
}
if p != nil {
return *(*interface{})(p), true, true
}
ic := i
for {
if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) {
return i, false, true
}
p = atomic.LoadPointer(&e.p)
if p == expunged {
return nil, false, false
}
if p != nil {
return *(*interface{})(p), true, true
}
}
}总结
- Map适用的场景：
- 读多写少的场景，具体到key的细节场景为下列两种情况
- key被一写多读的场景，因为当key存在与read中时，利用原子操作来避免上锁来提升效率；同时通过及时将dirty提升为read，减少查询读状态时的miss次数
- 并发更新已存在的不同key的场景，利用原子的CAS操作更新已存在的值
- 读多写少的场景，具体到key的细节场景为下列两种情况
- Map不适用的场景：
- 读写相等或写多读少的场景，原因
- 因为新增的key初始仅存在于dirty中，此时的存储操作需要加锁
- 读写相等的情况下（如key写一次、读一次），读操作时无法从read状态命中，从而需要加锁读取dirty状态，相比于简单的Mutex增加了额外的执行逻辑；写多读少也是类似，dirty的元素增加速率大于read的命中率缺失，从而迟迟无法触发状态提升(dirty->read)，会导致读取操作极容易触发加锁读取dirty的过程
- 大量读取不存在的key的场景，原因
- 频繁触发状态提升 dirty->read，因为key不存在导致read的丢失命中率极容易达到阈值
- Load相比于普通的Mutex加锁处理，多执行很多逻辑
- 读写相等或写多读少的场景，原因
- Map的设计原理
- 读写分离，使用原子操作提升并发场景下的读操作性能
- 采用逻辑删除，批量删除已被擦除的key，将实际的删除成本摊销
- 累计只读read状态的命中率缺失次数，及时将dirty提升为read，提高命中率
- 读写两个状态中存储对象的指针，read中数据被CAS修改后的值对两个状态都可见
