golang sync.Map 原理以及性能分析

谁借莪１个温暖的怀抱￠ 2023-06-27 08:53 1阅读 0赞

### sync.Map 原理以及性能分析 ###

*  支持并发的map
 *  sync.Map
 *   *  数据结构
     *  Load
     *  Store
     *  delete
     *  Range
 *  sync.Map总结
 *  sync.Map，读写锁的适用场景
 *  参考文献

golang支持map关键字，golang的map的读写是编译成runtime的函数调用。但是默认的map是非线程安全的。go 1.9 版本中支持了 sync.Map 用于线程安全的map。

关于go map的实现可以参考：[Golang map实践以及实现原理][Golang map]

# 支持并发的map #

golang内置的map读写操作，很多都是编译器帮我们转换成runtime的函数调用，而且整体的设计比较封闭，没有留下扩展的空间。

要支持线程安全的map，一种方式就是在go内置的map上进行封装。比较简单的就是使用sync提供的锁来实现，这种是最简单的，具体情况这里就不说了。

# sync.Map #

go 1.9 官方提供了sync.Map 来优化线程安全的并发读写的map。该实现也是基于内置map关键字来实现的。

这个实现类似于一个线程安全的 `map[interface{}]interface{}` . 这个map的优化主要适用了以下场景：

（1）给定key的键值对只写了一次，但是读了很多次，比如在只增长的缓存中；  
（2）当多个goroutine读取、写入和覆盖的key值不相交时。

在这两种情况下，使用Map可能比使用单独互斥锁或RWMutex的Go Map大大减少锁争用。

对于其余情况最好还是使用RWMutex保证线程安全。

## 数据结构 ##

先看一下底层的数据结构：

// 封装的线程安全的map
    type Map struct { 
    	// lock
    	mu Mutex
    
    	// 实际是readOnly这个结构
    	// 一个只读的数据结构，因为只读，所以不会有读写冲突。
    	// readOnly包含了map的一部分数据，用于并发安全的访问。(冗余，内存换性能)
    	// 访问这一部分不需要锁。
    	read atomic.Value // readOnly
    
    	// dirty数据包含当前的map包含的entries,它包含最新的entries(包括read中未删除的数据,虽有冗余，但是提升dirty字段为read的时候非常快，不用一个一个的复制，而是直接将这个数据结构作为read字段的一部分),有些数据还可能没有移动到read字段中。
    	// 对于dirty的操作需要加锁，因为对它的操作可能会有读写竞争。
    	// 当dirty为空的时候， 比如初始化或者刚提升完，下一次的写操作会复制read字段中未删除的数据到这个数据中。
    	dirty map[interface{ }]*entry
    
    	// 当从Map中读取entry的时候，如果read中不包含这个entry,会尝试从dirty中读取，这个时候会将misses加一，
    	// 当misses累积到 dirty的长度的时候， 就会将dirty提升为read,避免从dirty中miss太多次。因为操作dirty需要加锁。
    	misses int
    }
    
    // readOnly is an immutable struct stored atomically in the Map.read field.
    type readOnly struct { 
    	m       map[interface{ }]*entry
    	// 如果Map.dirty有些数据不在m中，这个值为true
    	amended bool 
    }
    
    // An entry is a slot in the map corresponding to a particular key.
    type entry struct { 
    	// *interface{}
    	p unsafe.Pointer 
    }

`readOnly.amended`指明`Map.dirty`中有`readOnly.m`未包含的数据，所以如果从Map.read找不到数据的话，还要进一步到Map.dirty中查找。

这里虽然有冗余的两份map数据，但是`Map.dirty`和`readOnly.m`的value都是一个指针变量 `*entry`，所以整体内存占用还好。

sync.Map 的kv都是 `interface{}` ，entry里面的p实际是一个 `*interface{}`，也就是entry实际保存的是指向value的指针。

这里p有三个值：

1.  nil: entry已被删除了，并且m.dirty为nil
2.  expunged: entry已被删除了，并且m.dirty不为nil，而且这个entry不存在于m.dirty中
3.  其它： entry是一个正常的value

sync.Map也是在golang提供的map关键字之上封装实现的。

sync.Map 整体的优化可以描述为以下几点：

1.  空间换时间。 通过冗余的两个数据结构(read、dirty),实现加锁对性能的影响。
2.  map只保存key和对应的value的指针，这样可以并发的读写map, 实际更新指向value的指针再通过基于CAS的无锁atomic。
3.  使用只读数据(read)，避免读写冲突
4.  动态调整，miss次数多了之后，将dirty数据提升为read。
5.  double-checking。
6.  延迟删除。 删除一个键值只是打标记，只有在提升dirty的时候才清理删除的数据。
7.  优先从read读取、更新、删除，因为对read的读取不需要锁。

## Load ##

线程安全的加载key对应的value：

func (m *Map) Load(key interface{ }) (value interface{ }, ok bool) { 
    	// 1.首先从m.read中加载只读的readOnly, 从它的map中查找，无锁。
    	read, _ := m.read.Load().(readOnly)
    	e, ok := read.m[key]
    	// 2. 如果没找到，并且m.dirty中有新数据，需要从m.dirty查找，这个时候需要加锁
    	if !ok && read.amended { 
    		m.mu.Lock()
    		// double check
    		read, _ = m.read.Load().(readOnly)
    		e, ok = read.m[key]
    		if !ok && read.amended { 
    			// // 从m.dirty查找
    			e, ok = m.dirty[key]
    			// 不管m.dirty中存不存在，都将misses计数加一
    			// missLocked()中满足条件后就会提升m.dirty
    			m.missLocked()
    		}
    		m.mu.Unlock()
    	}
    	if !ok { 
    		return nil, false
    	}
    	// 原子加载 *entry 所保存的value。
    	return e.load()
    }
    
    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
    }

整体pipeline如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70]

首先要强调的是，首先是从readonly里面读，读不到时候才加锁去 map.dirty 里面去读，并且加锁之后首先是进行double check(熟悉Java的都知道double check是什么)。

double check 之后即使不存在于m.read中，经过miss几次之后，m.dirty会被提升为m.read，又会从m.read中查找。所以对于更新／增加较少，加载存在的key很多的case,性能基本和无锁的map类似。

missLocked方法中可能会将m.dirty提升，`m,misses`会记录从readOnly中获取不到 `*entry` 的次数，也就是miss的次数，如果达到了 `len(m.dirty)` 就会原子的替换`m.read.m` 为 `m.dirty`。提升后m.dirty、m.misses重置， 并且m.read.amended为false。

## Store ##

安全的更新一个key对应的value:

// Store sets the value for a key.
    func (m *Map) Store(key, value interface{ }) { 
    	// 1. 如果m.read存在这个键，并且这个entry没有被标记删除(expunged)，那么cas自旋更新value。
    	// 因为m.dirty也指向这个entry,所以m.dirty也保持最新的entry。
    	read, _ := m.read.Load().(readOnly)
    	if e, ok := read.m[key]; ok && e.tryStore(&value) { 
    		return
    	}
    	// 2. m.read不存在或者已经被标记删除
    	m.mu.Lock()
    	// double check
    	read, _ = m.read.Load().(readOnly)
    	if e, ok := read.m[key]; ok { 
    		if e.unexpungeLocked() { //标记成未被删除
    			//m.dirty中不存在这个键，所以加入m.dirty
    			m.dirty[key] = e
    		}
    		e.storeLocked(&value)
    	// m.dirty存在这个键，更新
    	} else if e, ok := m.dirty[key]; ok { 
    		e.storeLocked(&value)
    	//新键值
    	} else { 
    		//m.dirty中没有比m.readOnly更新的数据，往m.dirty中增加第一个新键
    		if !read.amended { 
    			// 从m.read中复制未删除的数据
    			// 并标记m.read已经落后于m.dirty
    			m.dirtyLocked()
    			m.read.Store(readOnly{ m: read.m, amended: true})
    		}
    		//将这个entry加入到m.dirty中
    		m.dirty[key] = newEntry(value)
    	}
    	m.mu.Unlock()
    }
    
    // tryStore stores a value if the entry has not been expunged.
    //
    // If the entry is expunged, tryStore returns false and leaves the entry
    // unchanged.
    func (e *entry) tryStore(i *interface{ }) bool { 
    	for { 
    		p := atomic.LoadPointer(&e.p)
    		if p == expunged { 
    			return false
    		}
    		if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) { 
    			return true
    		}
    	}
    }
    
    func (m *Map) dirtyLocked() { 
    	if m.dirty != nil { 
    		return
    	}
    
    	read, _ := m.read.Load().(readOnly)
    	m.dirty = make(map[interface{ }]*entry, len(read.m))
    	for k, e := range read.m { 
    		if !e.tryExpungeLocked() { 
    			m.dirty[k] = e
    		}
    	}
    }

整体的pipeline可以用下图来解释：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 1]  
你可以看到，以上操作都是先从操作m.read开始的，不满足条件再加锁，然后操作m.dirty。

可能会发生两种数据迁移：

1.  从m.dirty到m.read的迁移，这个迁移过程其实是指针的的修改，所以效率高；
2.  从read map到dirty map的迁移, 这个迁移需要创建一个新的map来复制key-value，所以效率会低一些

Store可能会在某种情况下（在刚初始化和将所有元素迁移到read中后，dirty默认都是nil元素，而此时如果有新的元素增加，则需要先将read map中的所有未删除数据先迁移到dirty中）从m.read中复制数据到m.dirty，如果这个时候m.read中数据量非常大，可能会影响性能。

## delete ##

删除一个键值对：

func (m *Map) Delete(key interface{ }) { 
    	// 1. 如果不存在于 m.read中，而且 m.dirty 和 m.read 数据不一致。
    	read, _ := m.read.Load().(readOnly)
    	e, ok := read.m[key]
    	if !ok && read.amended { 
    		// 加锁，double check， 然后删除对应的key。
    		m.mu.Lock()
    		read, _ = m.read.Load().(readOnly)
    		e, ok = read.m[key]
    		if !ok && read.amended { 
    			delete(m.dirty, key)
    		}
    		m.mu.Unlock()
    	}
    	if ok { 
    		e.delete()
    	}
    }

整体pipeline:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 2]  
这里会删除 m.dirty 对应的key-value, 但是m.read中的key-value其实并没有删除，只是设置了删除的标志为expunged。这里的惰性删除避免了重新创建 entry 实体，只用更新指针和value指针。

func (e *entry) delete() (hadValue bool) { 
    	for { 
    		p := atomic.LoadPointer(&e.p)
    		if p == nil || p == expunged { 
    			return false
    		}
    		if atomic.CompareAndSwapPointer(&e.p, p, nil) { 
    			return true
    		}
    	}
    }

## Range ##

这里sync.Map是对map关键字的封装，肯定无法使用系统提供的 for range 操作。所以这里采用了一个回调的操作：

func (m *Map) Range(f func(key, value interface{ }) bool) { 
    	// 如果m.dirty中有新数据，则提升m.dirty,然后在遍历
    	read, _ := m.read.Load().(readOnly)
    	if read.amended { 
    		///提升m.dirty
    		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()
    	}
    	// 遍历, for range是安全的
    	for k, e := range read.m { 
    		v, ok := e.load()
    		if !ok { 
    			continue
    		}
    		if !f(k, v) { 
    			break
    		}
    	}
    }

Range方法调用前可能会做一个m.dirty的提升，不过提升m.dirty不是一个耗时的操作。

# sync.Map总结 #

sync.Map的优化策略简单总结可以理解为：

1.  无锁读与读写分离；  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 3]
2.  写加锁与延迟提升；  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 4]
3.  指针与惰性删除，map保存的value都是指针。惰性删除，实际删除是在 Store时候去check 然后删除。

# sync.Map，读写锁的适用场景 #

<table> 
 <thead> 
  <tr> 
   <th>实现方式</th> 
   <th>原理</th> 
   <th>适用场景</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>map+Mutex</td> 
   <td>通过Mutex互斥锁来实现多个goroutine对map的串行化访问</td> 
   <td>读写都需要通过Mutex加锁和释放锁，适用于读写比接近的场景</td> 
  </tr> 
  <tr> 
   <td>map+RWMutex</td> 
   <td>通过RWMutex来实现对map的读写进行读写锁分离加锁，从而实现读的并发性能提高</td> 
   <td>同Mutex相比适用于读多写少的场景</td> 
  </tr> 
  <tr> 
   <td>sync.Map</td> 
   <td>底层通分离读写map和原子指令来实现读的近似无锁，并通过延迟更新的方式来保证读的无锁化</td> 
   <td>读多修改少，元素增加删除频率不高的情况，在大多数情况下替代上述两种实现</td> 
  </tr> 
 </tbody> 
</table>

源码提供分析背景，实际情况还是要case by case的测试。

# 参考文献 #

官方源码：[src/sync/map.go][src_sync_map.go]  
Go 1.9 sync.Map揭秘 [https://colobu.com/2017/07/11/dive-into-sync-Map/][https_colobu.com_2017_07_11_dive-into-sync-Map]

[Golang map]: https://louyuting.blog.csdn.net/article/details/99699350
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200112110724714.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200112110342685.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200112111125713.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200112110232202.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200112110214618.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9sb3V5dXRpbmcuYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70
[src_sync_map.go]: https://github.com/golang/go/blob/master/src/sync/map.go
[https_colobu.com_2017_07_11_dive-into-sync-Map]: https://colobu.com/2017/07/11/dive-into-sync-Map/