泽民博客 ☰ Menu

sync.Map

package main
import (
“sync”
“fmt”
)



func main() {
//开箱即用
var sm sync.Map
//store 方法,添加元素
sm.Store(1,”a”)
//Load 方法，获得value
if v,ok:=sm.Load(1);ok{
fmt.Println(v)
}
//LoadOrStore方法，获取或者保存
//参数是一对key：value，如果该key存在且没有被标记删除则返回原先的value（不更新）和true；不存在则store，返回该value 和false
if vv,ok:=sm.LoadOrStore(1,”c”);ok{
fmt.Println(vv)
}
if vv,ok:=sm.LoadOrStore(2,”c”);!ok{
fmt.Println(vv)
}
//遍历该map，参数是个函数，该函数参的两个参数是遍历获得的key和value，返回一个bool值，当返回false时，遍历立刻结束。
sm.Range(func(k,v interface{})bool{
fmt.Print(k)
fmt.Print(“:”)
fmt.Print(v)
fmt.Println()
return true
})
}

sync.Map 源码解析
源码位于：src\sync\map.go
首先查看一下sync.Map的数据结构：



type Map struct {
// 该锁用来保护dirty
mu Mutex
// 存读的数据，因为是atomic.value类型，只读类型，所以它的读是并发安全的
read atomic.Value // readOnly
//包含最新的写入的数据，并且在写的时候，会把read 中未被删除的数据拷贝到该dirty中，因为是普通的map存在并发安全问题，需要用到上面的mu字段。
dirty map[interface{}]*entry
// 从read读数据的时候，会将该字段+1，当等于len（dirty）的时候，会将dirty拷贝到read中（从而提升读的性能）。
misses int
}
read的数据结构是：



type readOnly struct {
m map[interface{}]*entry
// 如果Map.dirty的数据和m 中的数据不一样是为true
amended bool
}



entry的数据结构：



type entry struct {
//可见value是个指针类型，虽然read和dirty存在冗余情况（amended=false），但是由于是指针类型，存储的空间应该不是问题
p unsafe.Pointer // *interface{}
}



Delete
首先来看delete方法



func (m *Map) Delete(key interface{}) {
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
//如果read中没有，并且dirty中有新元素，那么就去dirty中去找
if !ok && read.amended {
m.mu.Lock()
//这是双检查（上面的if判断和锁不是一个原子性操作）
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if !ok && read.amended {
//直接删除
delete(m.dirty, key)
}
m.mu.Unlock()
}
if ok {
//如果read中存在该key，则将该value 赋值nil（采用标记的方式删除！）
e.delete()
}
}
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
}
}
}
Store
新加元素



func (m *Map) Store(key, value interface{}) {
// 如果m.read存在这个key，并且没有被标记删除，则尝试更新。
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}
// 如果read不存在或者已经被标记删除
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
//如果entry被标记expunge，则表明dirty没有key，可添加入dirty，并更新entry
if e.unexpungeLocked() {
//加入dirty中
m.dirty[key] = e
}
//更新value值
e.storeLocked(&value)
//dirty 存在该key，更新
} else if e, ok := m.dirty[key]; ok {
e.storeLocked(&value)
//read 和dirty都没有，新添加一条
} else {
//dirty中没有新的数据，往dirty中增加第一个新键
if !read.amended {
//将read中未删除的数据加入到dirty中
m.dirtyLocked()
m.read.Store(readOnly{m: read.m, amended: true})
}
m.dirty[key] = newEntry(value)
}
m.mu.Unlock()
}



//将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))
//read如果较大的话，可能影响性能
for k, e := range read.m {
//通过此次操作，dirty中的元素都是未被删除的，可见expunge的元素不在dirty中
if !e.tryExpungeLocked() {
m.dirty[k] = e
}
}
}
//判断entry是否被标记删除，并且将标记为nil的entry更新标记为expunge
func (e *entry) tryExpungeLocked() (isExpunged bool) {
p := atomic.LoadPointer(&e.p)
for p == nil {
// 将已经删除标记为nil的数据标记为expunged
if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
return true
}
p = atomic.LoadPointer(&e.p)
}
return p == expunged
}
//对entry 尝试更新
func (e *entry) tryStore(i *interface{}) bool {
p := atomic.LoadPointer(&e.p)
if p == expunged {
return false
}
for {
if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
return true
}
p = atomic.LoadPointer(&e.p)
if p == expunged {
return false
}
}
}
//read里 将标记为expunge的更新为nil
func (e *entry) unexpungeLocked() (wasExpunged bool) {
return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}
//更新entry
func (e *entry) storeLocked(i *interface{}) {
atomic.StorePointer(&e.p, unsafe.Pointer(i))
}



可见，每次操作先检查read，因为read 并发安全，性能好些；read不满足，则加锁检查dirty，一旦是新的键值，dirty会被read更新。
Load
加载方法，查找key。



func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
//因read只读，线程安全，先查看是否满足条件
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
//如果read没有，并且dirty有新数据，那从dirty中查找，由于dirty是普通map，线程不安全，这个时候用到互斥锁了
if !ok && read.amended {
m.mu.Lock()
// 双重检查
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
// 如果read中还是不存在，并且dirty中有新数据
if !ok && read.amended {
e, ok = m.dirty[key]
// mssLocked（）函数是性能是sync.Map 性能得以保证的重要函数，目的讲有锁的dirty数据，替换到只读线程安全的read里
m.missLocked()
}
m.mu.Unlock()
}
if !ok {
return nil, false
}
return e.load()
}
//dirty 提升至read 关键函数，当misses 经过多次因为load之后，大小等于len（dirty）时候，讲dirty替换到read里，以此达到性能提升。
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
}
源码用的是1.9版本，通过阅读源码我们发现sync.Map是通过冗余的两个数据结构(read、dirty),实现性能的提升。为了提升性能，load、delete、store等操作尽量使用只读的read；为了提高read的key击中概率，采用动态调整，将dirty数据提升为read；对于数据的删除，采用延迟标记删除法，只有在提升dirty的时候才删除



Go官方的faq已经提到内建的map不是线程(goroutine)安全的。在Go 1.6之前， 内置的map类型是部分goroutine安全的，并发的读没有问题，并发的写可能有问题。自go 1.6之后， 并发地读写map会报错，这在一些知名的开源库中都存在这个问题，所以go 1.9之前的解决方案是额外绑定一个锁，封装成一个新的struct或者单独使用锁都可以。另外笔者在go 1.9之前通常是使用concurrent-map来解决这类问题，但是不是所有的第三方库都以此来解决问题。



我们先来看看这个代码样例：程序中一个goroutine一直读，一个goroutine一直写同一个键值，即使读写的键不相同，而且map也没有”扩容”等操作，代码还是会报错的，错误信息是: fatal error: concurrent map read and map write。。



package main
func main() {
m := make(map[int]int)
go func() {
for {
_ = m[1]
}
}()
go func() {
for {
m[2] = 2
}
}()
select {}
}
问题的根源在Go的源代码: hashmap_fast.go#L118,会看到读的时候会检查hashWriting标志， 如果有这个标志，就会报并发错误。



写的时候会设置这个标志: hashmap.go#L542



h.flags |= hashWriting
hashmap.go#L628设置完之后会取消这个标记。这样并发读写的检查有很多处， 比如写的时候也会检查是不是有并发的写，删除键的时候类似写，遍历的时候并发读写问题等。map的并发问题并不是那么容易被发现, 你可以利用-race参数来检查。



并发地使用map对象是我们日常开发中一个很常见的需求，特别是在一些大项目中。map总会保存goroutine共享的数据。Go 1.9之前在Go官方blog的Go maps in action一文中，给出了一种简便的解决方案。



首先，通过嵌入struct为map增加一个读写锁



var counter = struct{
sync.RWMutex
m map[string]int
}{m: make(map[string]int)}



读写数据时，可以很方便的加锁



counter.RLock()
n := counter.m[“some_key”]
counter.RUnlock()
fmt.Println(“some_key:”, n)



counter.Lock()
counter.m[“some_key”]++
counter.Unlock()
当然，你也可以使用concurrent-map来解决问题



// Create a new map.
map := cmap.New()



// Sets item within map, sets “bar” under key “foo”
map.Set(“foo”, “bar”)



// Retrieve item from map.
if tmp, ok := map.Get(“foo”); ok {
bar := tmp.(string)
}



// Removes item under key “foo”
map.Remove(“foo”)
两者本质上都是使用sync.RWMutex来保障线程(goroutine)安全的。这种解决方案相当简洁，并且利用读写锁而不是Mutex可以进一步减少读写的时候因为锁带来的性能。但在map的数据非常大的情况下，一把锁会导致大并发的客户端共争一把锁，这时，在Go 1.9中sync.Map就非常实用。（除了以上这些之外，还有一个笔者想提到的库，cmap也是一个相当好，安全且性能出色的第三方库）



Go 1.9中sync.Map的实现有以下优化点：



空间换时间。 通过冗余的两个数据结构(read、dirty),实现加锁对性能的影响。
使用只读数据(read)，避免读写冲突。
动态调整，miss次数多了之后，将dirty数据提升为read。
double-checking。
延迟删除。 删除一个键值只是打标记，只有在提升dirty的时候才清理删除的数据。
优先从read读取、更新、删除，因为对read的读取不需要锁。
sync.Map数据结构很简单，包含四个字段：read、mu、dirty、misses。



type Map struct {
// 当涉及到dirty数据的操作的时候，需要使用此锁
mu Mutex
// 一个只读的数据结构，因为只读，所以不会有读写冲突。
// 所以从这个数据中读取总是安全的。
// 实际上，实际也会更新这个数据的entries,如果entry是未删除的(unexpunged), 并不需要加锁。如果entry已经被删除了，需要加锁，以便更新dirty数据。
read atomic.Value // readOnly
// dirty数据包含当前的map包含的entries,它包含最新的entries(包括read中未删除的数据,虽有冗余，但是提升dirty字段为read的时候非常快，不用一个一个的复制，而是直接将这个数据结构作为read字段的一部分),有些数据还可能没有移动到read字段中。
// 对于dirty的操作需要加锁，因为对它的操作可能会有读写竞争。
// 当dirty为空的时候， 比如初始化或者刚提升完，下一次的写操作会复制read字段中未删除的数据到这个数据中。
dirty map[interface{}]*entry
// 当从Map中读取entry的时候，如果read中不包含这个entry,会尝试从dirty中读取，这个时候会将misses加一，
// 当misses累积到 dirty的长度的时候， 就会将dirty提升为read,避免从dirty中miss太多次。因为操作dirty需要加锁。
misses int
}



read的数据结构



type readOnly struct {
m map[interface{}]entry
amended bool // 如果Map.dirty有些数据不在其中的时候，这个值为true
}
这里的精髓是，使用了冗余的数据结构read、dirty。dirty中会包含read中未删除的entries，新增加的entries会加入到dirty中。amended指明Map.dirty中有readOnly.m未包含的数据，所以如果从Map.read找不到数据的话，还要进一步到Map.dirty中查找。而对Map.read的修改是通过原子操作进行的。虽然read和dirty有冗余数据，但这些数据是通过指针指向同一个数据，所以尽管Map的value会很大，但是冗余的空间占用还是有限的。readOnly.m和Map.dirty存储的值类型是entry,它包含一个指针p, 指向用户存储的value值。



type entry struct {
p unsafe.Pointer // *interface{}
}
p有三种值：



nil: entry已被删除了，并且m.dirty为nil
expunged: entry已被删除了，并且m.dirty不为nil，而且这个entry不存在于m.dirty中
其它： entry是一个正常的值
理解了sync.Map的数据结构，那么我们先来看看sync.Map的Load方法实现



func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
// 1.首先从m.read中得到只读readOnly,从它的map中查找，不需要加锁
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
// 2. 如果没找到，并且m.dirty中有新数据，需要从m.dirty查找，这个时候需要加锁
if !ok && read.amended {
m.mu.Lock()
// 双检查，避免加锁的时候m.dirty提升为m.read,这个时候m.read可能被替换了。
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
// 如果m.read中还是不存在，并且m.dirty中有新数据
if !ok && read.amended {
// 从m.dirty查找
e, ok = m.dirty[key]
// 不管m.dirty中存不存在，都将misses计数加一
// missLocked()中满足条件后就会提升m.dirty
m.missLocked()
}
m.mu.Unlock()
}
if !ok {
return nil, false
}
return e.load()
}
Load加载方法，提供一个键key,查找对应的值value,如果不存在，通过ok反映。这里的精髓是从m.read中加载，不存在的情况下，并且m.dirty中有新数据，加锁，然后从m.dirty中加载。另外一点是这里使用了双检查的处理，因为在下面的两个语句中，这两行语句并不是一个原子操作。



if !ok && read.amended {
m.mu.Lock()



虽然第一句执行的时候条件满足，但是在加锁之前，m.dirty可能被提升为m.read,所以加锁后还得再检查m.read，后续的方法中都使用了这个方法。如果我们查询的键值正好存在于m.read中，则无须加锁，直接返回，理论上性能优异。即使不存在于m.read中，经过miss几次之后，m.dirty会被提升为m.read，又会从m.read中查找。所以对于更新／增加较少，加载存在的key很多的场景,性能基本和无锁的map相差无几。



经过miss几次之后，m.dirty会被提升为m.read，那么m.dirty又是如何被提升的呢？重点在missLocked方法中。



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
}
最后三行代码就是提升m.dirty的，很简单的将m.dirty作为readOnly的m字段，原子更新m.read。提升后m.dirty、m.misses重置， 并且m.read.amended为false。



sync.Map的Store方法实现



func (m *Map) Store(key, value interface{}) {
// 如果m.read存在这个键，并且这个entry没有被标记删除，尝试直接存储。
// 因为m.dirty也指向这个entry,所以m.dirty也保持最新的entry。
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}
// 如果m.read不存在或者已经被标记删除
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
if e.unexpungeLocked() { //标记成未被删除
m.dirty[key] = e //m.dirty中不存在这个键，所以加入m.dirty
}
e.storeLocked(&value) //更新
} else if e, ok := m.dirty[key]; ok { // m.dirty存在这个键，更新
e.storeLocked(&value)
} else { //新键值
if !read.amended { //m.dirty中没有新的数据，往m.dirty中增加第一个新键
m.dirtyLocked() //从m.read中复制未删除的数据
m.read.Store(readOnly{m: read.m, amended: true})
}
m.dirty[key] = newEntry(value) //将这个entry加入到m.dirty中
}
m.mu.Unlock()
}



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 {
if !e.tryExpungeLocked() {
m.dirty[k] = e
}
}
}



func (e *entry) tryExpungeLocked() (isExpunged bool) {
p := atomic.LoadPointer(&e.p)
for p == nil {
// 将已经删除标记为nil的数据标记为expunged
if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
return true
}
p = atomic.LoadPointer(&e.p)
}
return p == expunged
}
Store方法是更新或者新增一个entry。以上操作都是先从操作m.read开始的，不满足条件再加锁，然后操作m.dirty。Store可能会在某种情况下(初始化或者m.dirty刚被提升后)从m.read中复制数据，如果这个时候m.read中数据量非常大，可能会影响性能。



sync.Map的Delete方法实现



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
}
}
}
Delete方法删除一个键值。和Store方法一样，删除操作还是从m.read中开始， 如果这个entry不存在于m.read中，并且m.dirty中有新数据，则加锁尝试从m.dirty中删除。注意，还是要双检查的。 从m.dirty中直接删除即可，就当它没存在过，但是如果是从m.read中删除，并不会直接删除，而是打标记而已。



sync.Map的Range方法实现



func (m *Map) Range(f func(key, value interface{}) bool) {
read, _ := m.read.Load().(readOnly)
// 如果m.dirty中有新数据，则提升m.dirty,然后在遍历
if read.amended {
//提升m.dirty
m.mu.Lock()
read, _ = m.read.Load().(readOnly) //双检查
if read.amended {
read = readOnly{m: m.dirty}
m.read.Store(read)
m.dirty = nil
m.misses = 0
}
m.mu.Unlock()
}
// 遍历, for range是安全的
for k, e := range read.m {
v, ok := e.load()
if !ok {
continue
}
if !f(k, v) {
break
}
}
}
在Go语言中，for … range map是内建的语言特性，所以没有办法使用for range遍历sync.Map, 于是变通的有了Range方法，通过回调的方式遍历。Range方法调用前可能会做一个m.dirty的提升，不过提升m.dirty不是一个耗时的操作。



sync.Map的LoadOrStore 方法实现



func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
actual, loaded, ok := e.tryLoadOrStore(value)
if ok {
return actual, loaded
}
}



m.mu.Lock()

read, _ = m.read.Load().(readOnly)

if e, ok := read.m[key]; ok {

	if e.unexpungeLocked() {

		m.dirty[key] = e

	}

	actual, loaded, _ = e.tryLoadOrStore(value)

} else if e, ok := m.dirty[key]; ok {

	actual, loaded, _ = e.tryLoadOrStore(value)

	m.missLocked()

} else {

	if !read.amended {

		// 给dirty添加一个新key，

		// 标记只读为不完整

		m.dirtyLocked()

		m.read.Store(readOnly{m: read.m, amended: true})

	}

	m.dirty[key] = newEntry(value)

	actual, loaded = value, false

}

m.mu.Unlock()



return actual, loaded }


func (e entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) {
p := atomic.LoadPointer(&e.p)
if p == expunged {
return nil, false, false
}
if p != nil {
return *(interface{})(p), true, true
}
ic := i
for {
if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) {
return i, false, true
}
p = atomic.LoadPointer(&e.p)
if p == expunged {
return nil, false, false
}
if p != nil {
return (interface{})(p), true, true
}
}
}
LoadOrStore方法如果提供的key存在，则返回已存在的值(Load)，否则保存提供的键值(Store)。同样是从m.read开始，然后是m.dirty，最后还有双检查机制。



Go 1.9源代码中提供了性能的测试： map_bench_test.go、map_reference_test.go，和以前的解决方案比较，性能会有不少的提升。



最后sync.Map没有Len方法，并且目前没有迹象要加上 (issue#20680),所以如果想得到当前Map中有效的entries的数量，需要使用Range方法遍历一次。



https://github.com/orcaman/concurrent-map
众所周知,go普通的map是不支持并发的，换而言之,不是线程(goroutine)安全的。博主是从golang 1.4开始使用的，那时候map的并发读是没有支持，但是并发写会出现脏数据。golang 1.6之后，并发地读写会直接panic：
fatal error: concurrent map read and map write
复制代码package main
func main() {
m := make(map[int]int)
go func() {
for {
_ = m[1]
}
}()
go func() {
for {
m[2] = 2
}
}()
select {}
}
复制代码所以需要支持对map的并发读写时候，博主使用两种方法：



第三方类库 concurrent-map。
map加上sync.RWMutex来保障线程(goroutine)安全的。



golang 1.9之后,go 在sync包下引入了并发安全的map，也为博主提供了第三种方法。本文重点也在此，为了时效性，本文基于golang 1.10源码进行分析。
sync.Map
结构体
Map
type Map struct {
mu Mutex //互斥锁，用于锁定dirty map



read atomic.Value //优先读map,支持原子操作，注释中有readOnly不是说read是只读，而是它的结构体。read实际上有写的操作



dirty map[interface{}]*entry // dirty是一个当前最新的map，允许读写



misses int // 主要记录read读取不到数据加锁读取read map以及dirty map的次数，当misses等于dirty的长度时，会将dirty复制到read } 复制代码readOnly readOnly 主要用于存储，通过原子操作存储在Map.read中元素。 type readOnly struct {

m       map[interface{}]*entry

amended bool // 如果数据在dirty中但没有在read中，该值为true,作为修改标识 } 复制代码entry type entry struct {

// nil: 表示为被删除，调用Delete()可以将read map中的元素置为nil

// expunged: 也是表示被删除，但是该键只在read而没有在dirty中，这种情况出现在将read复制到dirty中，即复制的过程会先将nil标记为expunged，然后不将其复制到dirty

//  其他: 表示存着真正的数据

p unsafe.Pointer // *interface{} } 复制代码原理 如果你接触过大Java，那你一定对CocurrentHashMap利用锁分段技术增加了锁的数目，从而使争夺同一把锁的线程的数目得到控制的原理记忆深刻。 那么Golang的sync.Map是否也是使用了相同的原理呢？sync.Map的原理很简单，使用了空间换时间策略，通过冗余的两个数据结构(read、dirty),实现加锁对性能的影响。 通过引入两个map将读写分离到不同的map，其中read map提供并发读和已存元素原子写，而dirty map则负责读写。 这样read map就可以在不加锁的情况下进行并发读取,当read map中没有读取到值时,再加锁进行后续读取,并累加未命中数,当未命中数大于等于dirty map长度,将dirty map上升为read map。从之前的结构体的定义可以发现，虽然引入了两个map，但是底层数据存储的是指针，指向的是同一份值。 开始时sync.Map写入数据 X=1 Y=2 Z=3 dirty map主要接受写请求，read map没有数据 读取数据的时候从read map中读取，此时read map并没有数据，miss记录从read map读取失败的次数，当misses>=len(dirty map)时，将dirty map直接升级为read map,这里直接对dirty map进行地址拷贝并且dirty map被清空，misses置为0。


现在有需求对Z元素进行修改Z=4，sync.Map会直接修改read map的元素。



新加元素K=5，新加的元素就需要操作dirty map了，如果misses达到阀值后dirty map直接升级为read map并且dirty map为空map(read的amended==false)，则dirty map需要从read map复制数据。

升级后的效果如下。



如果需要删除Z，需要分几种情况：
一种read map存在该元素且read的amended==false：直接将read中的元素置为nil。



另一种为元素刚刚写入dirty map且未升级为read map:直接调用golang内置函数delete删除dirty map的元素；



还有一种是read map和dirty map同时存在该元素：将read map中的元素置为nil，因为read map和dirty map 使用的均为元素地址，所以均被置为nil。



优化点



空间换时间。通过冗余的两个数据结构(read、dirty),实现加锁对性能的影响。
使用只读数据(read)，避免读写冲突。
动态调整，miss次数多了之后，将dirty数据提升为read。
double-checking（双重检测）。
延迟删除。 删除一个键值只是打标记，只有在提升dirty的时候才清理删除的数据。
优先从read读取、更新、删除，因为对read的读取不需要锁。



方法源码分析
Load
Load返回存储在映射中的键值，如果没有值，则返回nil。ok结果指示是否在映射中找到值。
func (m Map) Load(key interface{}) (value interface{}, ok bool) {
// 第一次检测元素是否存在
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
if !ok && read.amended {
// 为dirty map 加锁
m.mu.Lock()
// 第二次检测元素是否存在，主要防止在加锁的过程中,dirty map转换成read map,从而导致读取不到数据
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if !ok && read.amended {
// 从dirty map中获取是为了应对read map中不存在的新元素
e, ok = m.dirty[key]
// 不论元素是否存在，均需要记录miss数，以便dirty map升级为read map
m.missLocked()
}
// 解锁
m.mu.Unlock()
}
// 元素不存在直接返回
if !ok {
return nil, false
}
return e.load()
}
复制代码dirty map升级为read map
func (m *Map) missLocked() {
// misses自增1
m.misses++
// 判断dirty map是否可以升级为read map
if m.misses < len(m.dirty) {
return
}
// dirty map升级为read map
m.read.Store(readOnly{m: m.dirty})
// dirty map 清空
m.dirty = nil
// misses重置为0
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
}
复制代码read map主要用于读取，每次Load都先从read读取，当read中不存在且amended为true，就从dirty读取数据 。无论dirty map中是否存在该元素，都会执行missLocked函数，该函数将misses+1，当m.misses < len(m.dirty)时，便会将dirty复制到read，此时再将dirty置为nil,misses=0。
storage
设置Key=>Value。
func (m *Map) Store(key, value interface{}) {
// 如果read存在这个键，并且这个entry没有被标记删除，尝试直接写入,写入成功，则结束
// 第一次检测
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}
// dirty map锁
m.mu.Lock()
// 第二次检测
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
// unexpungelocc确保元素没有被标记为删除
// 判断元素被标识为删除
if e.unexpungeLocked() {
// 这个元素之前被删除了，这意味着有一个非nil的dirty，这个元素不在里面.
m.dirty[key] = e
}
// 更新read map 元素值
e.storeLocked(&value)
} else if e, ok := m.dirty[key]; ok {
// 此时read map没有该元素，但是dirty map有该元素，并需修改dirty map元素值为最新值
e.storeLocked(&value)
} else {
// read.amended==false,说明dirty map为空，需要将read map 复制一份到dirty map
if !read.amended {
m.dirtyLocked()
// 设置read.amended==true，说明dirty map有数据
m.read.Store(readOnly{m: read.m, amended: true})
}
// 设置元素进入dirty map，此时dirty map拥有read map和最新设置的元素
m.dirty[key] = newEntry(value)
}
// 解锁，有人认为锁的范围有点大，假设read map数据很大，那么执行m.dirtyLocked()会耗费花时间较多，完全可以在操作dirty map时才加锁，这样的想法是不对的，因为m.dirtyLocked()中有写入操作
m.mu.Unlock()
}
复制代码尝试存储元素。
func (e *entry) tryStore(i *interface{}) bool {
// 获取对应Key的元素，判断是否标识为删除
p := atomic.LoadPointer(&e.p)
if p == expunged {
return false
}
for {
// cas尝试写入新元素值
if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
return true
}
// 判断是否标识为删除
p = atomic.LoadPointer(&e.p)
if p == expunged {
return false
}
}
}
复制代码unexpungelocc确保元素没有被标记为删除。如果这个元素之前被删除了，它必须在未解锁前被添加到dirty map上。
func (e *entry) unexpungeLocked() (wasExpunged bool) {
return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}
复制代码从read map复制到dirty map。
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 {

	// 如果标记为nil或者expunged，则不复制到dirty map

	if !e.tryExpungeLocked() {

		m.dirty[k] = e

	}

} } 复制代码LoadOrStore 如果对应的元素存在，则返回该元素的值，如果不存在，则将元素写入到sync.Map。如果已加载值，则加载结果为true;如果已存储，则为false。 func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {

// 不加锁的情况下读取read map

// 第一次检测

read, _ := m.read.Load().(readOnly)

if e, ok := read.m[key]; ok {

	// 如果元素存在（是否标识为删除由tryLoadOrStore执行处理），尝试获取该元素已存在的值或者将元素写入

	actual, loaded, ok := e.tryLoadOrStore(value)

	if ok {

		return actual, loaded

	}

}



m.mu.Lock()

// 第二次检测

// 以下逻辑参看Store

read, _ = m.read.Load().(readOnly)

if e, ok := read.m[key]; ok {

	if e.unexpungeLocked() {

		m.dirty[key] = e

	}

	actual, loaded, _ = e.tryLoadOrStore(value)

} else if e, ok := m.dirty[key]; ok {

	actual, loaded, _ = e.tryLoadOrStore(value)

	m.missLocked()

} else {

	if !read.amended {

		m.dirtyLocked()

		m.read.Store(readOnly{m: read.m, amended: true})

	}

	m.dirty[key] = newEntry(value)

	actual, loaded = value, false

}

m.mu.Unlock()



return actual, loaded } 复制代码如果没有删除元素，tryLoadOrStore将自动加载或存储一个值。如果删除元素，tryLoadOrStore保持条目不变并返回ok= false。 func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) {

p := atomic.LoadPointer(&e.p)

// 元素标识删除，直接返回

if p == expunged {

	return nil, false, false

}

// 存在该元素真实值，则直接返回原来的元素值

if p != nil {

	return *(*interface{})(p), true, true

}



// 如果p为nil(此处的nil，并是不是指元素的值为nil，而是atomic.LoadPointer(&e.p)为nil，元素的nil在unsafe.Pointer是有值的)，则更新该元素值

ic := i

for {

	if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) {

		return i, false, true

	}

	p = atomic.LoadPointer(&e.p)

	if p == expunged {

		return nil, false, false

	}

	if p != nil {

		return *(*interface{})(p), true, true

	}

} } 复制代码Delete 删除元素,采用延迟删除，当read map存在元素时，将元素置为nil，只有在提升dirty的时候才清理删除的数,延迟删除可以避免后续获取删除的元素时候需要加锁。当read map不存在元素时，直接删除dirty map中的元素 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 {

		// 不论dirty map是否存在该元素，都会执行删除

		delete(m.dirty, key)

	}

	m.mu.Unlock()

}

if ok {

	// 如果在read中，则将其标记为删除（nil）

	e.delete()

} } 复制代码元素值置为nil 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

	}

} } 复制代码Range 遍历获取sync.Map中所有的元素，使用的为快照方式，所以不一定是准确的。 func (m *Map) Range(f func(key, value interface{}) bool) {

// 第一检测

read, _ := m.read.Load().(readOnly)

// read.amended=true,说明dirty map包含所有有效的元素（含新加，不含被删除的），使用dirty map

if read.amended {

	// 第二检测

	m.mu.Lock()

	read, _ = m.read.Load().(readOnly)

	if read.amended {

		// 使用dirty map并且升级为read map

		read = readOnly{m: m.dirty}

		m.read.Store(read)

		m.dirty = nil

		m.misses = 0

	}

	m.mu.Unlock()

}

// 一贯原则，使用read map作为读

for k, e := range read.m {

	v, ok := e.load()

	// 被删除的不计入

	if !ok {

		continue

	}

	// 函数返回false，终止

	if !f(k, v) {

		break

	}

} } 复制代码总结 经过了上面的分析可以得到,sync.Map并不适合同时存在大量读写的场景,大量的写会导致read map读取不到数据从而加锁进行进一步读取,同时dirty map不断升级为read map。 从而导致整体性能较低,特别是针对cache场景.针对append-only以及大量读,少量写场景使用sync.Map则相对比较合适。 sync.Map没有提供获取元素个数的Len()方法，不过可以通过Range()实现。 func Len(sm sync.Map) int {

lengh := 0

f := func(key, value interface{}) bool {

	lengh++

	return true

}

one:=lengh

lengh=0

sm.Range(f)

if one != lengh {

    one = lengh

	lengh=0

	sm.Range(f)

	if one <lengh {

		return lengh

	}

	

}

return one }


sync.Map实现分析
golang的SDK中提供线程安全的map实现sync.Map。它是针对RWMutex+map的实现方案中存在cache line的false share提出来的。主要适用于两个场景：



针对一个key一次写多次读。
多个goroutine并发读写修改的key是没有交集。



在这两种情况下，相比一个Mutex或者RWMutex加上普通的map，锁的竞争要少的多。那为什么呢？



数据结构
type Map struct {
mu Mutex



// read contains the portion of the map’s contents that are safe for
// concurrent access (with or without mu held).
//
// The read field itself is always safe to load, but must only be stored with
// mu held.
//
// Entries stored in read may be updated concurrently without mu, but updating
// a previously-expunged entry requires that the entry be copied to the dirty
// map and unexpunged with mu held.
read atomic.Value // readOnly



// dirty contains the portion of the map’s contents that require mu to be
// held. To ensure that the dirty map can be promoted to the read map quickly,
// it also includes all of the non-expunged entries in the read map.
//
// Expunged entries are not stored in the dirty map. An expunged entry in the
// clean map must be unexpunged and added to the dirty map before a new value
// can be stored to it.
//
// If the dirty map is nil, the next write to the map will initialize it by
// making a shallow copy of the clean map, omitting stale entries.
dirty map[interface{}]*entry



// misses counts the number of loads since the read map was last updated that
// needed to lock mu to determine whether the key was present.
//
// Once enough misses have occurred to cover the cost of copying the dirty
// map, the dirty map will be promoted to the read map (in the unamended
// state) and the next store to the map will make a new dirty copy.
misses int
}



// 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.
}



// An entry is a slot in the map corresponding to a particular key.
type entry struct {
// p points to the interface{} value stored for the entry.
//
// If p == nil, the entry has been deleted and m.dirty == nil.
//
// If p == expunged, the entry has been deleted, m.dirty != nil, and the entry
// is missing from m.dirty.
//
// Otherwise, the entry is valid and recorded in m.read.m[key] and, if m.dirty
// != nil, in m.dirty[key].
//
// An entry can be deleted by atomic replacement with nil: when m.dirty is
// next created, it will atomically replace nil with expunged and leave
// m.dirty[key] unset.
//
// An entry’s associated value can be updated by atomic replacement, provided
// p != expunged. If p == expunged, an entry’s associated value can be updated
// only after first setting m.dirty[key] = e so that lookups using the dirty
// map find the entry.
p unsafe.Pointer // *interface{}
}
Map.read包含了部分数据，读写请求优先考虑read，针对它的操作都是CAS，无锁的。



Map.dirty包含的数据是read的超集，对他的操作需要加锁。



readOnly.m表示当前read的数据，readOnly.amended表示是否有数据在dirty中。



entry保存具体数值的指针。有三种情况：



nil，表示已经删除，这个时候dirty中entry的值也是nil，因为他们是同一个entry的地址。
expunged，表示数据已经擦除，entry不在dirty中。
具体的数据值，一定会在dirty中。



接口
sync.Map包含五个接口：Load、Store、LoadOrStore、Delete和Range。



Load、Store、LoadOrStore和Delete
这几个接口都有类似的模式：



read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
ret := do_the_operation()
if ret is success {
return
}
}
m.mu.Lock()
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
ret := do_the_operation()
} else if e, ok := m.dirty[key]; ok {
ret := do_the_operation()
}
m.mu.Unlock()
利用read的CAS操作减少锁并发，同时由于并发存在获取锁之后还是有可能数据已经在read中，因此还是对read再做一次同样的操作，复用内存。如果数据仍然不在read中才会考虑操作dirty。针对数据是否在read中这几个接口的逻辑如下：



read包含了部分数据，如果key存在并而且与它对应的entry不是expunged，数据操作优先在这里进行。



Store：直接更新entry值。
Load：直接返回entry值。
LoadOrStore:针对entry做tryLoadOrStore操作。
Delete:把entry设置成nil。



当数据不在read中时，就会涉及到dirty了：



Store：
a. 如果entry在read中并且是expunged，则复用，同时把它修改成nil，然后把entry赋值到dirty，这样就避免了只在read不在dirty的情况。
b. 如果entry在dirty中，那么更新entry值。
c. 如果entry也不在dirty中，如果dirty是nil，则复制read中的entry值非nil的数据。然后，添加值到dirty。
Load：从dirty查找，同时增加misses。如果超过一定的阀值，就会发生数据从dirty到read的迁移。
LoadOrStore：流程和Store接口类似，只是返回值和对entry的处理逻辑不一样。
a. 如果entry有值，则返回具体值以及存在的标识。
b. 如果entry值为nil，设置entry为新的值并返回它和不存在标识。
c. 如果entry值是expunged，则返回nil和存在标志，这个是比较特殊。在LoadOrStore同时，并发的把entry从read复制到dirty，这种情况就会发生。



Range
Range接口相对简单，如果有部分数据在dirty中就会把dirty的数据提升到read中，并重置dirty。然后，遍历的是dirty数据。否则，只遍历read中的数据。这里不保证能遍历到之后添加的数据。



通过上面的逻辑我们发现read和dirty直接数据流转逻辑如下：



read到dirty：在Store和LoadOrStore的时候，如果需要保存的key既不在read也不在dirty，而且这时dirty是nil，就会把read中的nil数据变成expunged，并复制除了这份以外的数据到dirty。
dirty到read：
a. 在Load和LoadOrStore的时候，如果read中不存在，需要从dirty中获取数据，就会增加misses，当misses等于dirty的大小时，就会把dirty封装成readOnly，然后原子的赋值给read，并重置dirty。
b. 在Range的时候，如果有数据不在read中同样会把dirty封装成readOnly，然后原子的赋值给read，并重置dirty数据。



疑问
为什么需要expunged状态？



如果没有这个状态，更新已经删除的但是已经存在的数据就需要加锁了。




为什么newEntry的时候取的是参数interface{}的地址，这个地址不是栈上的么，会不会有问题？



参数i的地址被保存到map中时，变量&i已经逃逸到堆上面去了。




总结
文中开头提到的两个主要使用场景的原因主要使用的以下技术：



无锁的CAS操作。
读写分离，通过一份只读的数据结合CAS操作减少锁竞争。
延迟删除，只有当只读的数据被写的数据覆盖以后才会被gc回收。
内存复用，已经删除的数据所在的内存，当同一个key赋值的时候，可以被重新被使用。
分摊分析。



sync.Map
type Map struct {
// 常用的锁,在操作dirty时会用到
mu Mutex



read atomic.Value // readOnly



// dirty值要么为空,要么为全部键值对

dirty map[interface{}]*entry



// 在查询read时,命中失败的次数,当misses大于dirty长度时,read.m 会直接指向dirty

misses int } Map.read实际值是readOnly结构体,可以看成是比dirty多了一个amended字段的结构


注意这个并不是真正的只读,添加操作是通过直接将m字段指向整个dirty完成的,删除操作是通过修改entry为expunged完成的



readOnly
type readOnly struct {
m map[interface{}]*entry
amended bool
}
主要看下readOnly.amended的值变化情况



在Store方法中,添加新的键值对时,如果amended==false,会遍历read值,将其中未被标记为删除的记录,复制到dirty中,然后read.amended会被修改为true



在Load方法中,如果miss次数大于diry长度时,会将read.m直接指向dirty,且read.amended被置为false



如果amended==true,说明当前map时间节点处于新添加键值对之后,复制dirty到read之前,此时dirty不为空,且dirty包括所有Map中未被删除的数据,read中的数据可能少于dirty



如果amended==false,说明说明dirty为空



entry
type entry struct {
p unsafe.Pointer // *interface{}
}
实际是键值对中的value



关键操作
寻值
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() // 如果read中没有,查询dirty
}
m.mu.Unlock()
}
if !ok {
return nil, false
}
return e.load()
}
复制dirty到read,并清空dirty
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 (m *Map) Store(key, value interface{}) {
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}



m.mu.Lock()

read, _ = m.read.Load().(readOnly)

if e, ok := read.m[key]; ok {

    if e.unexpungeLocked() {

        m.dirty[key] = e

    }

    e.storeLocked(&value)

} else if e, ok := m.dirty[key]; ok {

    e.storeLocked(&value)

} else {

    if !read.amended {

        m.dirtyLocked()

        m.read.Store(readOnly{m: read.m, amended: true})

    }

    m.dirty[key] = newEntry(value)

}

m.mu.Unlock() } 场景分析 map.Store(a,”a”) -> map.Store(b,”b”) 第一次map.Store(“a”,”a”)


因为备份标记为false,执行m.dirtyLocked()
复制read -> dirty
将备份标记read.amended更新为true
将a存在dirty中
第二次map.Store(“b”,”b”)



跳过if !read.amended 判断
向dirty中存储数据
map.Store(“a”,”a”) ->map.Load(“a”) map.Store(“b”,”b”)
map.Store(“a”,”a”)



因为备份标记为false,执行m.dirtyLocked()
复制read -> dirty
将read.amended更新为true
将a存在dirty中
map.Load(“a”)



从read中读取失败
从dirty中读取
m.missLocked()
miss+1
因为miss >= len(dirty),直接将m.dirty复制到m.read中
备份标记m.read.amended = false
清空dirty
map.Store(“b”,”b”)



因为备份标记为false,执行m.dirtyLocked()
复制read -> dirty
将read.amended更新为true
将a存在dirty中
总结
sync.Map是如何保证性能比直接在map中加锁的性能好
当写入操作较多时,性能是无法保证的,因为每次都有可能要遍历read复制到dirty中



当读多写少时,read是atomic.Value类型, 读取时利用了atomic.Value.Load实现了原子操作,没有用到锁,所以性能有所提升



怎么理解read.amended
可以把amended理解为一个备份标记,从read中遍历数据,复制到dirty中,相当于完成备份,amended为true,dirty为nil时,说明未备份,amended为false



Map.read 和 Map.dirty的关系
可以把read看成是缓存,当缓存命中失败次数过多时,会从dirty中复制数据到read中,如果dirty不为空,那么dirty的数据大于等于read



从dirty中复制数据到read中,是否会导致原来的read中的数据丢失
不会,每次dirty创建时,都是从read中读取未被标记删除的数据复制到dirty中,之后dirty中的数据只会多于read,所以在从dirty中复制数据到read中时,只是会丢失已被标记删除的数据,而不会丢失实际数据



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的关联：
image.png



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
Map is like a Go map[interface{}]interface{} but is safe for concurrent use
by multiple goroutines without additional locking or coordination.
Loads, stores, and deletes run in amortized constant time.



上面一段是官方对sync.Map 的描述，从描述中看，sync.Map 跟map 很像，sync.Map 的底层实现也是依靠了map，但是sync.Map 相对于 map 来说，是并发安全的。



  1. 结构概览
    1.1. sync.Map
    sync.Map的结构体了
    type Map struct {
    mu Mutex



// 后面是readOnly结构体，依靠map实现，仅仅只用来读
read atomic.Value // readOnly



// 这个map主要用来写的，部分时候也承担读的能力

dirty map[interface{}]*entry



// 记录自从上次更新了read之后，从read读取key失败的次数

misses int } 复制代码1.2. readOnly sync.Map.read属性所对应的结构体了，这里不太明白为什么不把readOnly结构体的属性直接放入到sync.Map结构体里 type readOnly struct {   // 读操作所对应的map

m       map[interface{}]*entry   // dirty是否包含m中不存在的key

amended bool // true if the dirty map contains some key not in m. } 复制代码1.3. entry entry就是unsafe.Pointer，记录的是数据存储的真实地址 type entry struct {

p unsafe.Pointer // *interface{} }


复制代码1.4. 结构示意图
通过上面的结构体，我们可以简单画出来一个结构示意图





  1. 流程分析
    我们通过下面的动图（也可以手动debug），看一下在我们执行Store Load Delete 的时候，这个结构体的变换是如何的，先增加一点我们的认知
    func main() {
    m := sync.Map{}
    m.Store(“test1”, “test1”)
    m.Store(“test2”, “test2”)
    m.Store(“test3”, “test3”)
    m.Load(“test1”)
    m.Load(“test2”)
    m.Load(“test3”)
    m.Store(“test4”, “test4”)
    m.Delete(“test”)
    m.Load(“test”)
    }
    复制代码以上面代码为例，我们看一下m的结构变换




  2. 源码分析
    3.1. 新增key
    新增一个key value，通过Store方法来实现
    func (m *Map) Store(key, value interface{}) {
    read, _ := m.read.Load().(readOnly)
    // 如果这个key存在，通过tryStore更新
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
    return
    }
    // 走到这里有两种情况，1. key不存在 2. key对应的值被标记为expunged，read中的entry拷贝到dirty时，会将key标记为expunged，需要手动解锁
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
    // 第二种情况，先解锁，然后添加到dirty
    if e.unexpungeLocked() {
    // The entry was previously expunged, which implies that there is a
    // non-nil dirty map and this entry is not in it.
    m.dirty[key] = e
    }
    e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok {
    // m中没有，但是dirty中存在，更新dirty中的值
    e.storeLocked(&value)
    } else {
    // 如果amend==false，说明dirty和read是一致的，但是我们需要新加key到dirty里面，所以更新read.amended
    if !read.amended {
    // We’re adding the first new key to the dirty map.
    // Make sure it is allocated and mark the read-only map as incomplete.
    // 这一步会将read中所有的key标记为 expunged
    m.dirtyLocked()
    m.read.Store(readOnly{m: read.m, amended: true})
    }
    m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
    }
    复制代码3.1.1. tryLock
    func (e *entry) tryStore(i *interface{}) bool {
    p := atomic.LoadPointer(&e.p)
    // 这个entry是key对应的entry，p是key对应的值，如果p被设置为expunged，不能直接更新存储
    if p == expunged {
    return false
    }
    for {
    // 原子更新
    if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
    return true
    }
    p = atomic.LoadPointer(&e.p)
    if p == expunged {
    return false
    }
    }
    }
    复制代码tryLock会对key对应的值，进行判断，是否被设置为了expunged，这种情况下不能直接更新
    3.1.2. dirtyLock
    这里就是设置 expunged 标志的地方了，而这个函数正是将read中的数据同步到dirty的操作
    func (m *Map) dirtyLocked() {
    // dirty != nil 说明dirty在上次read同步dirty数据后，已经有了修改了，这时候read的数据不一定准确，不能同步
    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 {
    // 这里调用tryExpungeLocked 来给entry，即key对应的值 设置标志位
    if !e.tryExpungeLocked() {
    m.dirty[k] = e
    }
    }
    }
    复制代码3.1.3. tryExpungeLocked
    通过原子操作，给entry，key对应的值设置 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
    }
    复制代码3.1.4. unexpungeLocked
    func (e *entry) unexpungeLocked() (wasExpunged bool) {
    return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
    }
    复制代码根据上面分析，我们发现，在新增的时候，分为四种情况：





key原先就存在于read中，获取key所对应内存地址，原子性修改
key存在，但是key所对应的值被标记为 expunged，解锁，解除标记，并更新dirty中的key，与read中进行同步，然后修改key对应的值
read中没有key，但是dirty中存在这个key，直接修改dirty中key的值
read和dirty中都没有值，先判断自从read上次同步dirty的内容后有没有再修改过dirty的内容，没有的话，先同步read和dirty的值，然后添加新的key value到dirty上面



当出现第四种情况的时候，很容易产生一个困惑：既然read.amended == false，表示数据没有修改，为什么还要将read的数据同步到dirty里面呢？
这个答案在Load 函数里面会有答案，因为，read同步dirty的数据的时候，是直接把dirty指向map的指针交给了read.m，然后将dirty的指针设置为nil，所以，同步之后，dirty就为nil
下面看看具体的实现
3.2. 读取（Load）
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
// 如果read的map中没有，且存在修改
if !ok && read.amended {
m.mu.Lock()
// Avoid reporting a spurious miss if m.dirty got promoted while we were
// blocked on m.mu. (If further loads of the same key will not miss, it’s
// not worth copying the dirty map for this key.)
// 再查找一次，有可能刚刚将dirty升级为read了
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if !ok && read.amended {
// 如果amended 还是处于修改状态，则去dirty中查找
e, ok = m.dirty[key]
// Regardless of whether the entry was present, record a miss: this key
// will take the slow path until the dirty map is promoted to the read
// map.
// 增加misses的计数，在计数达到一定规则的时候，触发升级dirty为read
m.missLocked()
}
m.mu.Unlock()
}
// read dirty中都没有找到
if !ok {
return nil, false
}
// 找到了，通过load判断具体返回内容
return e.load()
}



func (e entry) load() (value interface{}, ok bool) {
p := atomic.LoadPointer(&e.p)
// 如果p为nil或者expunged标识，则key不存在
if p == nil || p == expunged {
return nil, false
}
return *(interface{})(p), true
}
复制代码为什么找到了p，但是p对应的值为nil呢？这个答案在后面解析Delete函数的时候会被揭晓
3.2.1. missLocked
func (m *Map) missLocked() {
m.misses++
if m.misses < len(m.dirty) {
return
}
// 直接把dirty的指针给read.m，并且设置dirty为nil，这里也就是 Store 函数的最后会调用 m.dirtyLocked的原因
m.read.Store(readOnly{m: m.dirty})
m.dirty = nil
m.misses = 0
}
复制代码3.3. 删除（Delete）
这里的删除并不是简单的将key从map中删除
func (m *Map) Delete(key interface{}) {
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
// read中没有这个key，但是Map被标识修改了，那么去dirty里面看看
if !ok && read.amended {
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if !ok && read.amended {
// 调用delete删除dirty的map，delete会判断key是否存在的
delete(m.dirty, key)
}
m.mu.Unlock()
}
// 如果read中存在，则假删除
if ok {
e.delete()
}
}



func (e *entry) delete() (hadValue bool) {
for {
p := atomic.LoadPointer(&e.p)
// 已经是被删除了，不需要管了
if p == nil || p == expunged {
return false
}
// 原子性 将key的值设置为nil
if atomic.CompareAndSwapPointer(&e.p, p, nil) {
return true
}
}
}
复制代码根据上面的逻辑可以看出，删除的时候，存在以下几种情况



read中没有，且Map存在修改，则尝试删除dirty中的map中的key
read中没有，且Map不存在修改，那就是没有这个key，无需操作
read中有，尝试将key对应的值设置为nil，后面读取的时候就知道被删了，因为dirty中map的值跟read的map中的值指向的都是同一个地址空间，所以，修改了read也就是修改了dirty



3.3. 遍历（Range）
遍历的逻辑就比较简单了，Map只有两种状态，被修改过和没有修改过
修改过：将dirty的指针交给read，read就是最新的数据了，然后遍历read的map
没有修改过：遍历read的map就好了
func (m *Map) Range(f func(key, value interface{}) bool) {
read, _ := m.read.Load().(readOnly)
if read.amended {
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
if read.amended {
read = readOnly{m: m.dirty}
m.read.Store(read)
m.dirty = nil
m.misses = 0
}
m.mu.Unlock()
}



for k, e := range read.m {

	v, ok := e.load()

	if !ok {

		continue

	}

	if !f(k, v) {

		break

	}

} } 复制代码3.4. 适用场景 在官方介绍的时候，也对适用场景做了说明


The Map type is optimized for two common use cases:
(1) when the entry for a given key is only ever written once but read many times, as in caches that only grow,
(2) when multiple goroutines read, write, and overwrite entries for disjoint sets of keys.
In these two cases, use of a Map may significantly reduce lock contention compared to a Go map paired with a separate Mutex or RWMutex.



通过对源码的分析来理解一下产生这两条规则的原因：
读多写少：读多写少的环境下，都是从read的map去读取，不需要加锁，而写多读少的情况下，需要加锁，其次，存在将read数据同步到dirty的操作的可能性，大量的拷贝操作会大大的降低性能
读写不同的key：sync.Map是针对key的值的原子操作，相当于加锁加载 key上，所以，多个key的读写是可以同时并发的



在Go 1.6之前， 内置的map类型是部分goroutine安全的，并发的读没有问题，并发的写可能有问题。自go 1.6之后， 并发地读写map会报错，这在一些知名的开源库中都存在这个问题，所以go 1.9之前的解决方案是额外绑定一个锁，封装成一个新的struct或者单独使用锁都可以。



本文带你深入到sync.Map的具体实现中，看看为了增加一个功能，代码是如何变的复杂的,以及作者在实现sync.Map的一些思想。



有并发问题的map
官方的faq已经提到内建的map不是线程(goroutine)安全的。



首先，让我们看一段并发读写的代码,下列程序中一个goroutine一直读，一个goroutine一只写同一个键值，即即使读写的键不相同，而且map也没有”扩容”等操作，代码还是会报错。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package main
func main() {
m := make(map[int]int)
go func() {
for {
_ = m[1]
}
}()
go func() {
for {
m[2] = 2
}
}()
select {}
}
错误信息是: fatal error: concurrent map read and map write。



如果你查看Go的源代码: hashmap_fast.go#L118,会看到读的时候会检查hashWriting标志， 如果有这个标志，就会报并发错误。



写的时候会设置这个标志: hashmap.go#L542



1
h.flags |= hashWriting
hashmap.go#L628设置完之后会取消这个标记。



当然，代码中还有好几处并发读写的检查， 比如写的时候也会检查是不是有并发的写，删除键的时候类似写，遍历的时候并发读写问题等。



有时候，map的并发问题不是那么容易被发现, 你可以利用-race参数来检查。



Go 1.9之前的解决方案
但是，很多时候，我们会并发地使用map对象，尤其是在一定规模的项目中，map总会保存goroutine共享的数据。在Go官方blog的Go maps in action一文中，提供了一种简便的解决方案。



1
2
3
4
var counter = struct{
sync.RWMutex
m map[string]int
}{m: make(map[string]int)}
它使用嵌入struct为map增加一个读写锁。



读数据的时候很方便的加锁：



1
2
3
4
counter.RLock()
n := counter.m[“some_key”]
counter.RUnlock()
fmt.Println(“some_key:”, n)
写数据的时候:



1
2
3
counter.Lock()
counter.m[“some_key”]++
counter.Unlock()
sync.Map
可以说，上面的解决方案相当简洁，并且利用读写锁而不是Mutex可以进一步减少读写的时候因为锁带来的性能。



但是，它在一些场景下也有问题，如果熟悉Java的同学，可以对比一下java的ConcurrentHashMap的实现，在map的数据非常大的情况下，一把锁会导致大并发的客户端共争一把锁，Java的解决方案是shard, 内部使用多个锁，每个区间共享一把锁，这样减少了数据共享一把锁带来的性能影响，orcaman提供了这个思路的一个实现： concurrent-map，他也询问了Go相关的开发人员是否在Go中也实现这种方案，由于实现的复杂性，答案是Yes, we considered it.,但是除非有特别的性能提升和应用场景，否则没有进一步的开发消息。



那么，在Go 1.9中sync.Map是怎么实现的呢？它是如何解决并发提升性能的呢？



sync.Map的实现有几个优化点，这里先列出来，我们后面慢慢分析。



空间换时间。 通过冗余的两个数据结构(read、dirty),实现加锁对性能的影响。
使用只读数据(read)，避免读写冲突。
动态调整，miss次数多了之后，将dirty数据提升为read。
double-checking。
延迟删除。 删除一个键值只是打标记，只有在提升dirty的时候才清理删除的数据。
优先从read读取、更新、删除，因为对read的读取不需要锁。
下面我们介绍sync.Map的重点代码，以便理解它的实现思想。



首先，我们看一下sync.Map的数据结构：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
type Map struct {
// 当涉及到dirty数据的操作的时候，需要使用这个锁
mu Mutex
// 一个只读的数据结构，因为只读，所以不会有读写冲突。
// 所以从这个数据中读取总是安全的。
// 实际上，实际也会更新这个数据的entries,如果entry是未删除的(unexpunged), 并不需要加锁。如果entry已经被删除了，需要加锁，以便更新dirty数据。
read atomic.Value // readOnly
// dirty数据包含当前的map包含的entries,它包含最新的entries(包括read中未删除的数据,虽有冗余，但是提升dirty字段为read的时候非常快，不用一个一个的复制，而是直接将这个数据结构作为read字段的一部分),有些数据还可能没有移动到read字段中。
// 对于dirty的操作需要加锁，因为对它的操作可能会有读写竞争。
// 当dirty为空的时候， 比如初始化或者刚提升完，下一次的写操作会复制read字段中未删除的数据到这个数据中。
dirty map[interface{}]*entry
// 当从Map中读取entry的时候，如果read中不包含这个entry,会尝试从dirty中读取，这个时候会将misses加一，
// 当misses累积到 dirty的长度的时候， 就会将dirty提升为read,避免从dirty中miss太多次。因为操作dirty需要加锁。
misses int
}
它的数据结构很简单，值包含四个字段：read、mu、dirty、misses。



它使用了冗余的数据结构read、dirty。dirty中会包含read中为删除的entries，新增加的entries会加入到dirty中。



read的数据结构是：



1
2
3
4
type readOnly struct {
m map[interface{}]*entry
amended bool // 如果Map.dirty有些数据不在中的时候，这个值为true
}
amended指明Map.dirty中有readOnly.m未包含的数据，所以如果从Map.read找不到数据的话，还要进一步到Map.dirty中查找。



对Map.read的修改是通过原子操作进行的。



虽然read和dirty有冗余数据，但这些数据是通过指针指向同一个数据，所以尽管Map的value会很大，但是冗余的空间占用还是有限的。



readOnly.m和Map.dirty存储的值类型是*entry,它包含一个指针p, 指向用户存储的value值。



1
2
3
type entry struct {
p unsafe.Pointer // *interface{}
}
p有三种值：



nil: entry已被删除了，并且m.dirty为nil
expunged: entry已被删除了，并且m.dirty不为nil，而且这个entry不存在于m.dirty中
其它： entry是一个正常的值
以上是sync.Map的数据结构，下面我们重点看看Load、Store、Delete、Range这四个方法，其它辅助方法可以参考这四个方法来理解。



Load
加载方法，也就是提供一个键key,查找对应的值value,如果不存在，通过ok反映：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
// 1.首先从m.read中得到只读readOnly,从它的map中查找，不需要加锁
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
// 2. 如果没找到，并且m.dirty中有新数据，需要从m.dirty查找，这个时候需要加锁
if !ok && read.amended {
m.mu.Lock()
// 双检查，避免加锁的时候m.dirty提升为m.read,这个时候m.read可能被替换了。
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
// 如果m.read中还是不存在，并且m.dirty中有新数据
if !ok && read.amended {
// 从m.dirty查找
e, ok = m.dirty[key]
// 不管m.dirty中存不存在，都将misses计数加一
// missLocked()中满足条件后就会提升m.dirty
m.missLocked()
}
m.mu.Unlock()
}
if !ok {
return nil, false
}
return e.load()
}
这里有两个值的关注的地方。一个是首先从m.read中加载，不存在的情况下，并且m.dirty中有新数据，加锁，然后从m.dirty中加载。



二是这里使用了双检查的处理，因为在下面的两个语句中，这两行语句并不是一个原子操作。



1
2
if !ok && read.amended {
m.mu.Lock()
虽然第一句执行的时候条件满足，但是在加锁之前，m.dirty可能被提升为m.read,所以加锁后还得再检查m.read，后续的方法中都使用了这个方法。



双检查的技术Java程序员非常熟悉了，单例模式的实现之一就是利用双检查的技术。



可以看到，如果我们查询的键值正好存在于m.read中，无须加锁，直接返回，理论上性能优异。即使不存在于m.read中，经过miss几次之后，m.dirty会被提升为m.read，又会从m.read中查找。所以对于更新／增加较少，加载存在的key很多的case,性能基本和无锁的map类似。



下面看看m.dirty是如何被提升的。 missLocked方法中可能会将m.dirty提升。



1
2
3
4
5
6
7
8
9
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
}
上面的最后三行代码就是提升m.dirty的，很简单的将m.dirty作为readOnly的m字段，原子更新m.read。提升后m.dirty、m.misses重置， 并且m.read.amended为false。



Store
这个方法是更新或者新增一个entry。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
func (m Map) Store(key, value interface{}) {
// 如果m.read存在这个键，并且这个entry没有被标记删除，尝试直接存储。
// 因为m.dirty也指向这个entry,所以m.dirty也保持最新的entry。
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}
// 如果m.read不存在或者已经被标记删除
m.mu.Lock()
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
if e.unexpungeLocked() { //标记成未被删除
m.dirty[key] = e //m.dirty中不存在这个键，所以加入m.dirty
}
e.storeLocked(&value) //更新
} else if e, ok := m.dirty[key]; ok { // m.dirty存在这个键，更新
e.storeLocked(&value)
} else { //新键值
if !read.amended { //m.dirty中没有新的数据，往m.dirty中增加第一个新键
m.dirtyLocked() //从m.read中复制未删除的数据
m.read.Store(readOnly{m: read.m, amended: true})
}
m.dirty[key] = newEntry(value) //将这个entry加入到m.dirty中
}
m.mu.Unlock()
}
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 {
if !e.tryExpungeLocked() {
m.dirty[k] = e
}
}
}
func (e *entry) tryExpungeLocked() (isExpunged bool) {
p := atomic.LoadPointer(&e.p)
for p == nil {
// 将已经删除标记为nil的数据标记为expunged
if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
return true
}
p = atomic.LoadPointer(&e.p)
}
return p == expunged
}
你可以看到，以上操作都是先从操作m.read开始的，不满足条件再加锁，然后操作m.dirty。



Store可能会在某种情况下(初始化或者m.dirty刚被提升后)从m.read中复制数据，如果这个时候m.read中数据量非常大，可能会影响性能。



Delete
删除一个键值。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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()
}
}
同样，删除操作还是从m.read中开始， 如果这个entry不存在于m.read中，并且m.dirty中有新数据，则加锁尝试从m.dirty中删除。



注意，还是要双检查的。 从m.dirty中直接删除即可，就当它没存在过，但是如果是从m.read中删除，并不会直接删除，而是打标记：



1
2
3
4
5
6
7
8
9
10
11
12
13
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
}
}
}
Range
因为for … range map是内建的语言特性，所以没有办法使用for range遍历sync.Map, 但是可以使用它的Range方法，通过回调的方式遍历。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func (m *Map) Range(f func(key, value interface{}) bool) {
read, _ := m.read.Load().(readOnly)
// 如果m.dirty中有新数据，则提升m.dirty,然后在遍历
if read.amended {
//提升m.dirty
m.mu.Lock()
read, _ = m.read.Load().(readOnly) //双检查
if read.amended {
read = readOnly{m: m.dirty}
m.read.Store(read)
m.dirty = nil
m.misses = 0
}
m.mu.Unlock()
}
// 遍历, for range是安全的
for k, e := range read.m {
v, ok := e.load()
if !ok {
continue
}
if !f(k, v) {
break
}
}
}
Range方法调用前可能会做一个m.dirty的提升，不过提升m.dirty不是一个耗时的操作。



sync.Map的性能
Go 1.9源代码中提供了性能的测试： map_bench_test.go、map_reference_test.go



我也基于这些代码修改了一下，得到下面的测试数据，相比较以前的解决方案，性能多少回有些提升，如果你特别关注性能，可以考虑sync.Map。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
BenchmarkHitAll/sync.RWMutexMap-4 20000000 83.8 ns/op
BenchmarkHitAll/sync.Map-4 30000000 59.9 ns/op
BenchmarkHitAll_WithoutPrompting/sync.RWMutexMap-4 20000000 96.9 ns/op
BenchmarkHitAll_WithoutPrompting/sync.Map-4 20000000 64.1 ns/op
BenchmarkHitNone/sync.RWMutexMap-4 20000000 79.1 ns/op
BenchmarkHitNone/sync.Map-4 30000000 43.3 ns/op
BenchmarkHit_WithoutPrompting/sync.RWMutexMap-4 20000000 81.5 ns/op
BenchmarkHit_WithoutPrompting/sync.Map-4 30000000 44.0 ns/op
BenchmarkUpdate/sync.RWMutexMap-4 5000000 328 ns/op
BenchmarkUpdate/sync.Map-4 10000000 146 ns/op
BenchmarkUpdate_WithoutPrompting/sync.RWMutexMap-4 5000000 336 ns/op
BenchmarkUpdate_WithoutPrompting/sync.Map-4 5000000 324 ns/op
BenchmarkDelete/sync.RWMutexMap-4 10000000 155 ns/op
BenchmarkDelete/sync.Map-4 30000000 55.0 ns/op
BenchmarkDelete_WithoutPrompting/sync.RWMutexMap-4 10000000 173 ns/op
BenchmarkDelete_WithoutPrompting/sync.Map-4 10000000 147 ns/op
其它
sync.Map没有Len方法，并且目前没有迹象要加上 (issue#20680),所以如果想得到当前Map中有效的entries的数量，需要使用Range方法遍历一次， 比较X疼。



LoadOrStore方法如果提供的key存在，则返回已存在的值(Load)，否则保存提供的键值(Store)。



有一点没有看明白，还请大家帮忙解释一下：



当向map中插入新的之前不存在的记录时，会向dirty中写入这个记录，同时会将read中没有删除的记录拷贝到dirty中。因为后续当miss次数过多的时候，dirty会替换掉read。



但是在delete操作的时候，我发现只删除了read中的值，没有对dirty进行处理。这样如果后续进行miss切换的时候，之前删除掉的值不是就又出现了吗？



因为read和dirty指向同一个元素。 在read中标记了相当于在dirty中也标记了



https://colobu.com/2017/07/11/dive-into-sync-Map/


Category golang