sync.Map的实现原理可概括为:
- 通过 read 和 dirty 两个字段将读写分离,读取时会先查询 read,不存在再查询 dirty,写入时则只写入 dirty,所以read相当于dirty的缓存。
- 读取 read 并不需要加锁,而读或写 dirty 都需要加锁。
- misses 字段统计 read 被穿透的次数,被穿透指需要读 dirty 的情况,超过一定次数则交换read和dirty指针,使dirty成为新的read,而dirty将被设为nil
- 对于删除数据则直接通过标记来延迟删除
这些概括过于简练,也不能完全准确的描述sunc.map的原理,我们直接来看源码
type Map struct {
mu Mutex // 读写dirty上的锁
read atomic.Value // readOnly
dirty map[interface{}]*entry
misses int // 穿透次数
}
type readOnly struct {
m map[interface{}]*entry
amended bool // 这个值标志着read和dirty是否完全相同,不完全相同则为true
}
type entry struct {
p unsafe.Pointer // *interface{}
}
请注意,read和dirty都是指针类型,并且经过实验,我们可以确定read和dirty中相同的键值对实际上是指向了同一块地址,所以map中并不是存储了两份数据。
- 读取键值
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
// 首先尝试从 read 中读取
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
// read中如果不存在且read和dirty不完全相同,则尝试从 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不是新的,而是复用旧的,可以传出去的
e, ok = m.dirty[key]
// read穿透,统计穿透次数
m.missLocked()
}
m.mu.Unlock()
}
// dity中也没有
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}) // dirty成为新的read
m.dirty = nil
m.misses = 0
}
- 添加或更改键值
func (m *Map) Store(key, value interface{}) {
read, _ := m.read.Load().(readOnly)
// 如果 read 里存在,则尝试直接修改read
// 如果read中的这个值其实被删除,那就不要改read了
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()
// 当我们添加一个在read和dirty中都不存在的键值时,会先把read中的nil数据先设置成哨兵,然后将read中的不是nil也不是哨兵的数据添加到dirty中
// 然后将 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
}
- 删除键值
func (m *Map) Delete(key interface{}) {
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 {
delete(m.dirty, key)
}
m.mu.Unlock()
}
if ok {
e.delete()
}
}
func (e *entry) delete() (hadValue bool) {
for {
p := atomic.LoadPointer(&e.p)
// 已标记为删除
if p == nil || p == expunged {
return false
}
// 原子操作,e.p标记为nil
if atomic.CompareAndSwapPointer(&e.p, p, nil) {
return true
}
}
}
问题1:为什么sync.map要有nil和expunged两个删除标记,全用nil不可以吗?
我猜想有可能是因为想要去分两种情况,一种是有这read中有这个键值对,但是被删除了,另一种情况是,根本就没有过这个键值对,这两种情况做不同的处理。
问题2:如果store只修改了read中的数据,而没有修改dirty中的数据,当我们下一此promote的时候dirty中的旧数据不会覆盖read中的新数据吗?
例如,我先存几个数据,然后连续miss让数据全部上到read,清空dirty,现在存一个新的值到dirty,会把read也复制下来,这样,dirty和read会有重合的数据,现在只更新read,然后连续miss,让dirty替换read,read中不就出现脏数据了吗?然而我做了实验,并不会这样。
package main
import (
"fmt"
"sync"
)
func main() {
// 创建一个 sync.Map
var myMap sync.Map
// 向 sync.Map 中添加键值对
myMap.Store("key1", "value1")
myMap.Store("key2", "value2")
myMap.Store("key3", "value3")
// 从 sync.Map 中获取值
value, ok := myMap.Load("key5")
value, ok = myMap.Load("key5")
value, ok = myMap.Load("key5")
myMap.Store("key4", "value4")
myMap.Store("key1", "modify")
value, ok = myMap.Load("key5")
value, ok = myMap.Load("key5")
value, ok = myMap.Load("key5")
value, ok = myMap.Load("key1")
if ok {
fmt.Println("Found value for key1:", value)
} else {
fmt.Println("Value not found for key1")
}
}
初步判断和amended有关