go-syncmap实现

golang map 是非 goroutine 安全，如果多个 goroutine 使用 map 需要加锁。但在高并发场景下，锁的争用会造成系统性能的下降。为了解决这种问题，go 1.9 之后提供了线程安全：sync.map。sync.map 引入了两个数据结构 read，dirty 来存储，他们的底层都是用 map 来实现。

Golang 选择了 CAS 这种不用加锁的方案来更新值, 实现并发安全的 map。

---

下面例举了三个结构体

map: sync.map 的结构体，包含 read 和 dirty，read 和 dirty 存储了 map 中真实存储的 key/value 值。misses 表示从 dirty 读取值的次数
readonly：Map.read 值的结构体类型，m 存储 key/value 真实值。readOnly.amended 表示 read 是否创建了 dirty 副本
entry: read 和 dirty 中存储 value 的指针

type Map struct {
    mu Mutex
    read atomic.Value // readOnly
    dirty map[interface{}]*entry
    misses int
}

type readOnly struct {m       map[interface{}]*entry
    amended bool 
}

type entry struct {p unsafe.Pointer // *interface{}
}

read 是 readOnly 结构体，真实数据存储在 readOnly.m。

read 和 dirty 的关联：

1: read 相当于 cache，读取数据时，先从 read 读取，没有取到，从 dirty 读取，Map.misses++。
当 Map.misses 达到 dirty 长度时，把 dirty 里面的数据全部 copy 到 read 中，并且 dirty 置为 nil。

2: read 和 dirty map 存储的元素值是放在 entry 结构体中。read 和 dirty 中相同 key 值指向同一个 entry 地址，所以当对 read 的 key 对应的 value 值进行修改，dirty 中的值也会相应的被修改。

entry.p 的状态：
1: nil 表示 entry 被删除，并且 Map.dirty = nil
2: expunged(初始化的 entry.p)表示 entry 被删除，但是 Map.dirty != nil
3: 其他情况表示值存在

snyc.Map 主要提供了插入，查找，删除操作，接下来会主要会讲这三个方法的实现

插入流程
插入 key, value
1: 先从 read 中获取 key，如果存在，并且这个 key 没有被删除，则直接更新 read[key] = entry{p: value}返回
2: 否则，key 存在但是被删除了，在 dirty 中插入这个 key，value 值。dirty[key] = entry{p: value} 返回
3: 如果 dirty 为 nil，则将 read map 的 key,entry 添加到新创建的 dirty map 中；不为 nil，则跳过第 3 步
4: 将 key, value 插入 dirty map 中。dirty[key] = entry{p: value}

插入总结：
新加入的 key 值，会插入 dirty 中
以前存在，但是删除过的 key，会插入 dirty 中
以前存在，但是没被删除的 key，read 会更新这个 key 对应的 value 值，
所以 dirty 不为 nil 的时候，会全量保存 key 值。

查找流程
查找 key
1: 从 read 中读取到，直接返回
2: 没有读取到，并且 dirty 不为 nil，对 map 加锁, 然后再读取一遍 read map 中内容（主要防止在加锁的过程中, 有可能 dirty map 全部 copy 到 read map,dirty 置为 nil）, 如果 read 存在 key，直接返回
3: read 不存在，从 dirty 中读取 key 对应的 value 值返回，并且 map.misses++。当 map.misses 达到一定 dirty 长度，将 dirty map 全部 copy 到 read map,dirty 置为 nil。

查找总结：
读 read 没读到，会从 dirty 中读取，并且 misses 次数 +1，当次数达到一定 dirty 长度，会把 dirty map 全部 copy 到 read map,dirty 置为 nil。

删除流程
1: 从 read 中去读 key，如果存在，直接将从 read[key] 获取到 entry.p 置为 nil
2: 否则，从 dirty 中删除这个 key 值
所以可以得出，read 删除是直接把 entry 的 p 置为 nil,key 保留。从 dirty 中删除是直接删除这个 key