并发map #
设计一个并发的map,最简单的就是使用锁加普通map来实现。
type simpleConcurrentMap struct{
mu sync.Mutex
m map[interface{}]interface{}
}
上面情形，不管是读还是写都需要先加锁，性能太低，假设我们要设计一个高并发的map呢？我们按读写操作来分一下类：
- 读多写少
- 读少写多
- 读写平衡 可以分为上述三类。
读多写少场景 #
可以让它们读写分离,分成两个map（readMap与writeMap）, 类似mysql的读写分离吗? 那么插入/更新(删除)的时候怎么从writeMap同步到readMap呢？不可能实时同步，否则readMap也转变为了writeMap,也需要加锁!!! 这么看读写分离就没有必要了，徒增复杂度。
那么可以设计成类似缓存的cacheMap(不加锁，原子锁)与持久化的persistentMap(加锁)？且把真实的value保存在第三方，自己保留的是第三方的句柄(handle), 类似下图的结构:
cacheMap: nil
key--->ValuePtr(第三方句柄) /
\ /
\ /
--->valuePtr/----->value(真实的值)
/ 可理解为第三方的唯一键
persistentMap: /
key--->valuePtr(第三方句柄)
当删除的时候，如果在cacheMap中存在，就把对应的ValuePtr设置为nil(代表删除) 当更新的的时候，如果在cacheMap中存在，就把对应的ValuePtr所指向的value改为newValue(这样persistentMap也更新了) 当查询的时候，先去cacheMap查(如果key存在，valuePtr为nil则说明删除了，但是没有同步到persistentMap)，再去persistentMap查 当插入新的key时候，操作persistentMap。但是这也会遇到什么时候同步到cacheMap中去的问题，因为如果一直不同步，会导致查询的时候都会到persistentMap中去，也是要加锁的。
一个补偿措施是: 加一个计数器misses，在查询的时候，如果只有在persistentMap中才查到则misses++，到了一定条件，我们把persistentMap安全地同步到cacheMap中，并且清空persistentMap。
cacheMap是 persistentMap的一个只读拷贝，禁止自行增加新key，只能读或者改。
golang中的sync.Map就是一种适合读多写少的并发map; 把我们的 persistentMap 叫做了 dirtyMap，把persistentMap 同步到 cacheMap 叫做了promote（升级）。
读取 Map.Load
if is exist readMap[key]
读取返回
ret
lock()
if is exist readMap[key] // double-checking
读取返回
else if is exist dirtyMap[key]
读到了，在dirtyMap存在，但是在readMap中不存在
misses++ // 未命中自增
if misses >= len(dirtyMap) // 判断是否需要把dirtyMap提升级为readMap
readMap = dirtyMap
dirtyMap = nil // dirtyMap置空
else
key is not exist
unlock()
写入 Map.Store
if is exist readMap[key]
原子操作直接修改值指针
ret
lock()
if is exist readMap[key] // double-checking
原子操作直接修改值指针
else if is exist dirtyMap[key]
修改值指针
else
dirtyMap新增一个key，方便之后dirtyMap升级成readMmap，我们还要把原先的readMap中没删除的全复制过来
unlock()
这里补充一下两个字段的解释：
一个是misses,一个是readOnly.amended; 而dirty与readOnly.m数据类型是一样的。
readOnly.amended是判断是否dirtyMap中容纳readMap所没有的key, 首先说下它的位置，它是和readMap一起放在readOnly结构体中的, 这是方便进行原子的操作, readOnly是不能修改的。如果要修改只能是用一个新的readOnly去替换旧的only，m.read.Store(readOnly{m: read.m, amended: true})比如这个，要修改readOnly.amended，就是构造一个新的readOnly去原子替换, 所以它没有与misses一样放在外面。
type Map struct {
mu Mutex
read atomic.Value // readOnly
dirty map[interface{}]*entry
misses int
}
type readOnly struct {
m map[interface{}]*entry
amended bool // true if the dirty map contains some key not in m.
}
疑问 #
- read 字段时可以用 CAS，那么只用 read 这一个结构行吗？为什么还需要 dirty？ 首先，不管是read还是dirty本质上都是map，sync.map 解决的是普通map无法并发读写的问题，所以不可能只用一个map就能实现并发读写。但为什么read可以在不加锁的时候更新呢，这时因为read 里面存了一个 map[interface{}]*entry结构，只要key被加入到read里，key对应的value指针永远是不变的，而且你可以全篇都搜一下，我们对read这个map用的永远都是 e, ok := read.m[key] 类似这样的操作，这其实只是一个map的读操作，就算并发也是没有问题的，我们用CAS修改的只是e里面的pointer，所以在这里read 起了一个缓存的作用，并不是一个map的写操作
其实也可以从上面的图中看出来，readMap(cacheMap)它是readOnly,我们原子修改的只是它的valuePtr锁指向的真正位置的值
- 什么时候使用sync.Map?
The Map type is specialized. Most code should use a plain Go map instead, with separate locking or coordination, for better type safety and to make it easier to maintain other invariants along with the map content.
map类型是专门化的。大多数代码应该使用普通的Go map加单独的锁定或协调，以获得更好的类型安全性，并使维护map与其他不变量变得更容易。
(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.
多读少写/多goroutine操作键值情形使用，能避免锁竞争。
- 使用sync.Map会导致异常泄漏？
从删除中我们知道，如果key本来在readMap中，它的删除不会动这个Key,只会更改*Entry.p为nil。
在极端情况下，从删除这个key后(假删除)，没有misses到一定的值让 dirtyMap 提升为readMap，从而间接释放key,那它都是永远不会被删除的。
此种情形下，如Key 中放了一个大的对象，或者关联有内存，就会导致内存泄漏。
⚠️：如果key不在readMap,而在dirtyMap，那么删除key的时候，会调用delete(map, key)删除。
读少写多/读写平衡场景 #
使用读写锁和减少锁的粒度（一个 map 分成若干个小 map，对 key 进行哈希，每个区有自己的锁）
- 参考这个实现：https://github.com/orcaman/concurrent-map