深度解密 Go 语言中的 sync.map

2020-06-16 17:00:00于海丽

read 是 atomic.Value 类型,可以并发地读。但如果需要更新 read,则需要加锁保护。对于 read 中存储的 entry 字段,可能会被并发地 CAS 更新。但是如果要更新一个之前已被删除的 entry,则需要先将其状态从 expunged 改为 nil,再拷贝到 dirty 中,然后再更新。

dirty 是一个非线程安全的原始 map。包含新写入的 key,并且包含 read 中的所有未被删除的 key。这样,可以快速地将 dirty 提升为 read 对外提供服务。如果 dirty 为 nil,那么下一次写入时,会新建一个新的 dirty,这个初始的 dirtyread 的一个拷贝,但除掉了其中已被删除的 key。

每当从 read 中读取失败,都会将 misses 的计数值加 1,当加到一定阈值以后,需要将 dirty 提升为 read,以期减少 miss 的情形。

read mapdirty map 的存储方式是不一致的。
前者使用 atomic.Value,后者只是单纯的使用 map。
原因是 read map 使用 lock free 操作,必须保证 load/store 的原子性;而 dirty map 的 load+store 操作是由 lock(就是 mu)来保护的。

真正存储 key/value 的是 read 和 dirty 字段。read 使用 atomic.Value,这是 lock-free 的基础,保证 load/store 的原子性。dirty 则直接用了一个原始的 map,对于它的 load/store 操作需要加锁。

read 字段里实际上是存储的是:

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
	m  map[interface{}]*entry
	amended bool // true if the dirty map contains some key not in m.
}

注意到 read 和 dirty 里存储的东西都包含 entry,来看一下:

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

很简单,它是一个指针,指向 value。看来,read 和 dirty 各自维护一套 key,key 指向的都是同一个 value。也就是说,只要修改了这个 entry,对 read 和 dirty 都是可见的。这个指针的状态有三种:

p == nil 时,说明这个键值对已被删除,并且 m.dirty == nil,或 m.dirty[k] 指向该 entry。

p == expunged 时,说明这条键值对已被删除,并且 m.dirty != nil,且 m.dirty 中没有这个 key。

其他情况,p 指向一个正常的值,表示实际 interface{} 的地址,并且被记录在 m.read.m[key] 中。如果这时 m.dirty 不为 nil,那么它也被记录在 m.dirty[key] 中。两者实际上指向的是同一个值。

当删除 key 时,并不实际删除。一个 entry 可以通过原子地(CAS 操作)设置 p 为 nil 被删除。如果之后创建 m.dirty,nil 又会被原子地设置为 expunged,且不会拷贝到 dirty 中。