亲宝软件园·资讯

展开

源码解读 Golang 的 sync.Map 实现原理

张凯强-zkqiang 人气:1
## 简介 Go 的内建 `map` 是不支持并发写操作的,原因是 `map` 写操作不是并发安全的,当你尝试多个 Goroutine 操作同一个 `map`,会产生报错:`fatal error: concurrent map writes`。 因此官方另外引入了 `sync.Map` 来满足并发编程中的应用。 `sync.Map` 的实现原理可概括为: * 通过 read 和 dirty 两个字段将读写分离,读的数据存在只读字段 read 上,将最新写入的数据则存在 dirty 字段上 * 读取时会先查询 read,不存在再查询 dirty,写入时则只写入 dirty * 读取 read 并不需要加锁,而读或写 dirty 都需要加锁 * 另外有 misses 字段来统计 read 被穿透的次数(被穿透指需要读 dirty 的情况),超过一定次数则将 dirty 数据同步到 read 上 * 对于删除数据则直接通过标记来延迟删除 ## 数据结构 `Map` 的数据结构如下: ```go type Map struct { // 加锁作用,保护 dirty 字段 mu Mutex // 只读的数据,实际数据类型为 readOnly read atomic.Value // 最新写入的数据 dirty map[interface{}]*entry // 计数器,每次需要读 dirty 则 +1 misses int } ``` 其中 readOnly 的数据结构为: ```go type readOnly struct { // 内建 map m map[interface{}]*entry // 表示 dirty 里存在 read 里没有的 key,通过该字段决定是否加锁读 dirty amended bool } ``` `entry` 数据结构则用于存储值的指针: ```go type entry struct { p unsafe.Pointer // 等同于 *interface{} } ``` 属性 p 有三种状态: * `p == nil`: 键值已经被删除,且 `m.dirty == nil` * `p == expunged`: 键值已经被删除,但 `m.dirty!=nil` 且 `m.dirty` 不存在该键值(expunged 实际是空接口指针) * 除以上情况,则键值对存在,存在于 `m.read.m` 中,如果 `m.dirty!=nil` 则也存在于 `m.dirty` `Map` 常用的有以下方法: * `Load`:读取指定 key 返回 value * `Store`: 存储(增或改)key-value * `Delete`: 删除指定 key ## 源码解析 ### Load ```go func (m *Map) Load(key interface{}) (value interface{}, ok bool) { // 首先尝试从 read 中读取 readOnly 对象 read, _ := m.read.Load().(readOnly) e, ok := read.m[key] // 如果不存在则尝试从 dirty 中获取 if !ok && read.amended { m.mu.Lock() // 由于上面 read 获取没有加锁,为了安全再检查一次 read, _ = m.read.Load().(readOnly) e, ok = read.m[key] // 确实不存在则从 dirty 获取 if !ok && read.amended { e, ok = m.dirty[key] // 调用 miss 的逻辑 m.missLocked() } m.mu.Unlock() } if !ok { return nil, false } // 从 entry.p 读取值 return e.load() } func (m *Map) missLocked() { m.misses++ if m.misses < len(m.dirty) { return } // 当 miss 积累过多,会将 dirty 存入 read,然后 将 amended = false,且 m.dirty = nil m.read.Store(readOnly{m: m.dirty}) m.dirty = nil m.misses = 0 } ``` ### Store ```go func (m *Map) Store(key, value interface{}) { read, _ := m.read.Load().(readOnly) // 如果 read 里存在,则尝试存到 entry 里 if e, ok := read.m[key]; ok && e.tryStore(&value) { return } // 如果上一步没执行成功,则要分情况处理 m.mu.Lock() read, _ = m.read.Load().(readOnly) // 和 Load 一样,重新从 read 获取一次 if e, ok := read.m[key]; ok { // 情况 1:read 里存在 if e.unexpungeLocked() { // 如果 p == expunged,则需要先将 entry 赋值给 dirty(因为 expunged 数据不会留在 dirty) m.dirty[key] = e } // 用值更新 entry e.storeLocked(&value) } else if e, ok := m.dirty[key]; ok { // 情况 2:read 里不存在,但 dirty 里存在,则用值更新 entry e.storeLocked(&value) } else { // 情况 3:read 和 dirty 里都不存在 if !read.amended { // 如果 amended == false,则调用 dirtyLocked 将 read 拷贝到 dirty(除了被标记删除的数据) m.dirtyLocked() // 然后将 amended 改为 true m.read.Store(readOnly{m: read.m, amended: true}) } // 将新的键值存入 dirty m.dirty[key] = newEntry(value) } m.mu.Unlock() } 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 (e *entry) unexpungeLocked() (wasExpunged bool) { return atomic.CompareAndSwapPointer(&e.p, expunged, nil) } func (e *entry) storeLocked(i *interface{}) { atomic.StorePointer(&e.p, unsafe.Pointer(i)) } 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 { // 判断 entry 是否被删除,否则就存到 dirty 中 if !e.tryExpungeLocked() { m.dirty[k] = e } } } func (e *entry) tryExpungeLocked() (isExpunged bool) { p := atomic.LoadPointer(&e.p) for p == nil { // 如果有 p == nil(即键值对被 delete),则会在这个时机被置为 expunged if atomic.CompareAndSwapPointer(&e.p, nil, expunged) { return true } p = atomic.LoadPointer(&e.p) } return p == expunged } ``` ### Delete ```go func (m *Map) Delete(key interface{}) { m.LoadAndDelete(key) } // LoadAndDelete 作用等同于 Delete,并且会返回值与是否存在 func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) { // 获取逻辑和 Load 类似,read 不存在则查询 dirty read, _ := m.read.Load().(readOnly) e, ok := read.m[key] if !ok && read.amended { m.mu.Lock() read, _ = m.read.Load().(readOnly) e, ok = read.m[key] if !ok && read.amended { e, ok = m.dirty[key] m.missLocked() } m.mu.Unlock() } // 查询到 entry 后执行删除 if ok { // 将 entry.p 标记为 nil,数据并没有实际删除 // 真正删除数据并被被置为 expunged,是在 Store 的 tryExpungeLocked 中 return e.delete() } return nil, false } ``` ## 总结 可见,通过这种读写分离的设计,解决了并发情况的写入安全,又使读取速度在大部分情况可以接近内建 `map`,非常适合读多写少的情况。 `sync.Map` 还有一些其他方法: * `Range`:遍历所有键值对,参数是回调函数 * `LoadOrStore`:读取数据,若不存在则保存再读取 这里就不再详解了,可参见 [源码](https://github.com/golang/go/blob/2e8dbae85ce88d02f651e53338984288057f14cb/src/sync/map.go)。

加载全部内容

相关教程
猜你喜欢
用户评论