本文Golang版本为go version go1.14 darwin/amd64

前言

Go中的map不是并发安全的,因此Go提供了sync.Map以在并发编程中使用,sync.Map是针对以下两种场景优化的:

  1. 某个指定的key只会被写入一次,但是会被读取多次,像不断增长的cache
  2. 多个goroutine读、写、覆盖不同的key

对于这两种场景,sync.Map比map配合Mutex/RWMutex可以大大降低锁的竞争。

数据结构

我们先看下sync.Map的定义

type Map struct {
	mu Mutex // 锁
	read atomic.Value // readOnly 读的时候先从read读
	dirty map[interface{}]*entry
	misses int // 当read没读到的时候+1(无论dirty中有没有)
}

read实际是readOnly结构体的一个实例,其定义:

type readOnly struct {
	m       map[interface{}]*entry
	// true表示dirty里存在read没有的key
	// 只有两种情况下amended为false
	// 1. map刚初始化的时候
	// 2. misses>=len(dirty)会将dirty赋值给read,同时dirty置为nil,amended置为false
	amended bool
}

entry定义:

type entry struct {
	p unsafe.Pointer
}

expunged定义:

var expunged = unsafe.Pointer(new(interface{}))

p的状态有以下三种:

状态 说明
nil entry已被删除,且dirty==nil
expunged entry已被删除,但dirty!=nil且dirty不存在该entry
其他 entry有效,并且存在于m.read中,如果m.dirty!=nil,则dirty中也存在该entry

基本原理

  • 通过read和dirty两个字段进行读写分离,read只用来读,将最新写入的数据存在dirty上
  • 读取时会先查询read,没有再去读dirty,写入则只写入dirty
  • 读read不需要加锁,读写dirty需要加锁
  • 通过misses字段来记录read被穿透的次数,穿透一定的次数则将dirty赋值给read
  • 删除为标记删除

写入

我们先看下写入即Store()方法 image.png

func (m *Map) Store(key, value interface{}) {
	// 将m.read原子读出
	read, _ := m.read.Load().(readOnly)
	// 如果read中存在要写入的key,则尝试修改
	if e, ok := read.m[key]; ok && e.tryStore(&value) {
		// 如果entry是expunged说明该entry已被删除,则不修改
		// 如果不是expunged则修改为新值,修改成功直接return
		// 此时最新值存在于read中,m.dirty不存在或者不是最新值
		return
	}

	// 走到这有两种可能
	// 1. read中没有我们要修改的key
	// 2. read中有我们要修改的key,但是已被删除
	m.mu.Lock()
	// 重新读取一遍
	read, _ = m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok {
		// 如果read中存在key的话,又走到这里的话entry基本是expunged
		// 将entry通过由expunded修改为nil
		if e.unexpungeLocked() {
			// 如果修改成功的话说明entry确实是expunged
			// 说明该dirty!=nil且entry不在dirty中
			// 将此entry加到dirty中
			// 此时dirty[key]与read[key]指向同一个entry
			// 下面修改entry值就会将read和dirty一并修改了
			m.dirty[key] = e
		} 
		// 如果修改失败的话说明在加锁之前entry由expunged被修改为了其他值
		// 可能是在另一个也是修改该key的线程中在加锁前抢先执行了if里面的代码		
		// 所以这时dirty中已经有这个key了

		// 将新值写入entry
		// read与dirty都得到了更新
		e.storeLocked(&value)
	} else if e, ok := m.dirty[key]; ok {
		// 如果read中不存在但dirty中存在的话
		// 将新值写入到dirty中的entry中
		e.storeLocked(&value)
	} else {
		// 如果read和dirty中都没有
		if !read.amended {
			// amended=false有两种可能性:
			// 1. map初始化后还没有写入值
			// 2. misses>=len(dirty),dirty被赋值给了read同时置为了nil
			// 创建新dirty并将read拷贝到新的dirty中
			m.dirtyLocked()
			// dirty拥有read全部数据,更新read.amended为true
			m.read.Store(readOnly{m: read.m, amended: true})
		} // amended=true说明dirty中存在read中没有的key
		// 向dirty中写入一个新entry
		// 此时新entry只存在于dirty中,read中没有
		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
		}
		// 将entry中的值替换为新值
		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))
}

// 将read数据复制到dirty中,删除数据除外
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 {
		// 如果p是nil修改为expunged
		// 如果p是expunged则不复制到dirty
		if !e.tryExpungeLocked() {
			m.dirty[k] = e
		}
	}
}

// 如果p是nil的修改为expunged,返回e是否是expunged
func (e *entry) tryExpungeLocked() (isExpunged bool) {
	p := atomic.LoadPointer(&e.p)
	for p == nil {
		if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
			return true
		}
		p = atomic.LoadPointer(&e.p)
	}
	return p == expunged
}

删除Delete()

image.png

func (m *Map) Delete(key interface{}) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	if !ok && read.amended {
		// 如果read中不存在要删除的key,且dirty中存在read中不存在的key
		// 则从dirty中删除key
		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 {
		// 如果read中存在,则将read中key对应的value修改为nil
		e.delete()
	}
}

// 把e.p改成nil,如果p为nil/expunged则不修改并返回false
func (e *entry) delete() (hadValue bool) {
	for {
		p := atomic.LoadPointer(&e.p)
		if p == nil || p == expunged {
			return false
		}
		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
			return true
		}
	}
}

查找Load()

image.png

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
	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()
	}
	if !ok {
		return nil, false
	}
	return e.load()
}

func (m *Map) missLocked() {
	m.misses++
	if m.misses < len(m.dirty) {
		return
	}
	m.read.Store(readOnly{m: m.dirty})
	m.dirty = nil
	m.misses = 0
}

func (e *entry) load() (value interface{}, ok bool) {
	p := atomic.LoadPointer(&e.p)
	if p == nil || p == expunged {
		return nil, false
	}
	return *(*interface{})(p), true
}

Range()和LoadOrStore()方法的逻辑都比较简单这里就不再赘述了,看懂了上面的代码基本就能看懂。