map 加锁与sync.Map性能对比分析

sync.Map,读写锁的适用场景
实现方式 原理 适用场景
map+Mutex 通过Mutex互斥锁来实现多个goroutine对map的串行化访问 读写都需要通过Mutex加锁和释放锁,适用于读写比接近的场景
map+RWMutex 通过RWMutex来实现对map的读写进行读写锁分离加锁,从而实现读的并发性能提高 同Mutex相比适用于读多写少的场景
sync.Map 底层通分离读写map和原子指令来实现读的近似无锁,并通过延迟更新的方式来保证读的无锁化 读多修改少,元素增加删除频率不高的情况,在大多数情况下替代上述两种实现

https://blog.csdn.net/u010853261/article/details/103848666



golang支持map关键字,golang的map的读写是编译成runtime的函数调用。但是默认的map是非线程安全的。go 1.9 版本中支持了 sync.Map 用于线程安全的map。
关于go map的实现可以参考:Golang map实践以及实现原理



支持并发的map
golang内置的map读写操作,很多都是编译器帮我们转换成runtime的函数调用,而且整体的设计比较封闭,没有留下扩展的空间。



要支持线程安全的map,一种方式就是在go内置的map上进行封装。比较简单的就是使用sync提供的锁来实现,这种是最简单的,具体情况这里就不说了。



sync.Map
go 1.9 官方提供了sync.Map 来优化线程安全的并发读写的map。该实现也是基于内置map关键字来实现的。



这个实现类似于一个线程安全的 map[interface{}]interface{} . 这个map的优化主要适用了以下场景:



(1)给定key的键值对只写了一次,但是读了很多次,比如在只增长的缓存中;
(2)当多个goroutine读取、写入和覆盖的key值不相交时。



在这两种情况下,使用Map可能比使用单独互斥锁或RWMutex的Go Map大大减少锁争用。



对于其余情况最好还是使用RWMutex保证线程安全。



数据结构
先看一下底层的数据结构:



// 封装的线程安全的map
type Map struct {
// lock
mu Mutex



// 实际是readOnly这个结构
// 一个只读的数据结构,因为只读,所以不会有读写冲突。
// readOnly包含了map的一部分数据,用于并发安全的访问。(冗余,内存换性能)
// 访问这一部分不需要锁。
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 }


// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
m map[interface{}]*entry
// 如果Map.dirty有些数据不在m中,这个值为true
amended bool
}



// An entry is a slot in the map corresponding to a particular key.
type entry struct {
// *interface{}
p unsafe.Pointer
}
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
readOnly.amended指明Map.dirty中有readOnly.m未包含的数据,所以如果从Map.read找不到数据的话,还要进一步到Map.dirty中查找。



这里虽然有冗余的两份map数据,但是Map.dirty和readOnly.m的value都是一个指针变量 *entry,所以整体内存占用还好。



sync.Map 的kv都是 interface{} ,entry里面的p实际是一个 *interface{},也就是entry实际保存的是指向value的指针。



这里p有三个值:



nil: entry已被删除了,并且m.dirty为nil
expunged: entry已被删除了,并且m.dirty不为nil,而且这个entry不存在于m.dirty中
其它: entry是一个正常的value
sync.Map也是在golang提供的map关键字之上封装实现的。



sync.Map 整体的优化可以描述为以下几点:



空间换时间。 通过冗余的两个数据结构(read、dirty),实现加锁对性能的影响。
map只保存key和对应的value的指针,这样可以并发的读写map, 实际更新指向value的指针再通过基于CAS的无锁atomic。
使用只读数据(read),避免读写冲突
动态调整,miss次数多了之后,将dirty数据提升为read。
double-checking。
延迟删除。 删除一个键值只是打标记,只有在提升dirty的时候才清理删除的数据。
优先从read读取、更新、删除,因为对read的读取不需要锁。
Load
线程安全的加载key对应的value:



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()
// double check
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
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
}
// 原子加载 *entry 所保存的value。
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
}
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
整体pipeline如下图:



首先要强调的是,首先是从readonly里面读,读不到时候才加锁去 map.dirty 里面去读,并且加锁之后首先是进行double check(熟悉Java的都知道double check是什么)。



double check 之后即使不存在于m.read中,经过miss几次之后,m.dirty会被提升为m.read,又会从m.read中查找。所以对于更新/增加较少,加载存在的key很多的case,性能基本和无锁的map类似。



missLocked方法中可能会将m.dirty提升,m,misses会记录从readOnly中获取不到 *entry 的次数,也就是miss的次数,如果达到了 len(m.dirty) 就会原子的替换m.read.m 为 m.dirty。提升后m.dirty、m.misses重置, 并且m.read.amended为false。



Store
安全的更新一个key对应的value:



// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
// 1. 如果m.read存在这个键,并且这个entry没有被标记删除(expunged),那么cas自旋更新value。
// 因为m.dirty也指向这个entry,所以m.dirty也保持最新的entry。
read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok && e.tryStore(&value) {
return
}
// 2. m.read不存在或者已经被标记删除
m.mu.Lock()
// double check
read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
if e.unexpungeLocked() {//标记成未被删除
//m.dirty中不存在这个键,所以加入m.dirty
m.dirty[key] = e
}
e.storeLocked(&value)
// m.dirty存在这个键,更新
} else if e, ok := m.dirty[key]; ok {
e.storeLocked(&value)
//新键值
} else {
//m.dirty中没有比m.readOnly更新的数据,往m.dirty中增加第一个新键
if !read.amended {
// 从m.read中复制未删除的数据
// 并标记m.read已经落后于m.dirty
m.dirtyLocked()
m.read.Store(readOnly{m: read.m, amended: true})
}
//将这个entry加入到m.dirty中
m.dirty[key] = newEntry(value)
}
m.mu.Unlock()
}



// tryStore stores a value if the entry has not been expunged.
//
// If the entry is expunged, tryStore returns false and leaves the entry
// unchanged.
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 (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
}
} } 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 54 55 56 57 58 59 60 61 62 63 64 65 整体的pipeline可以用下图来解释:


你可以看到,以上操作都是先从操作m.read开始的,不满足条件再加锁,然后操作m.dirty。



可能会发生两种数据迁移:



从m.dirty到m.read的迁移,这个迁移过程其实是指针的的修改,所以效率高;
从read map到dirty map的迁移, 这个迁移需要创建一个新的map来复制key-value,所以效率会低一些
Store可能会在某种情况下(在刚初始化和将所有元素迁移到read中后,dirty默认都是nil元素,而此时如果有新的元素增加,则需要先将read map中的所有未删除数据先迁移到dirty中)从m.read中复制数据到m.dirty,如果这个时候m.read中数据量非常大,可能会影响性能。



delete
删除一个键值对:



func (m *Map) Delete(key interface{}) {
// 1. 如果不存在于 m.read中,而且 m.dirty 和 m.read 数据不一致。
read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
if !ok && read.amended {
// 加锁,double check, 然后删除对应的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 {
e.delete()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
整体pipeline:



这里会删除 m.dirty 对应的key-value, 但是m.read中的key-value其实并没有删除,只是设置了删除的标志为expunged。这里的惰性删除避免了重新创建 entry 实体,只用更新指针和value指针。



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
}
}
}
1
2
3
4
5
6
7
8
9
10
11
Range
这里sync.Map是对map关键字的封装,肯定无法使用系统提供的 for range 操作。所以这里采用了一个回调的操作:



func (m *Map) Range(f func(key, value interface{}) bool) {
// 如果m.dirty中有新数据,则提升m.dirty,然后在遍历
read, _ := m.read.Load().(readOnly)
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
}
}
}
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
Range方法调用前可能会做一个m.dirty的提升,不过提升m.dirty不是一个耗时的操作。



sync.Map总结
sync.Map的优化策略简单总结可以理解为:



无锁读与读写分离;



写加锁与延迟提升;



指针与惰性删除,map保存的value都是指针。惰性删除,实际删除是在 Store时候去check 然后删除。
sync.Map,读写锁的适用场景
实现方式 原理 适用场景
map+Mutex 通过Mutex互斥锁来实现多个goroutine对map的串行化访问 读写都需要通过Mutex加锁和释放锁,适用于读写比接近的场景
map+RWMutex 通过RWMutex来实现对map的读写进行读写锁分离加锁,从而实现读的并发性能提高 同Mutex相比适用于读多写少的场景
sync.Map 底层通分离读写map和原子指令来实现读的近似无锁,并通过延迟更新的方式来保证读的无锁化 读多修改少,元素增加删除频率不高的情况,在大多数情况下替代上述两种实现
源码提供分析背景,实际情况还是要case by case的测试。



参考文献
官方源码:src/sync/map.go
Go 1.9 sync.Map揭秘 https://colobu.com/2017/07/11/dive-into-sync-Map/



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



https://www.cnblogs.com/shuiyuejiangnan/p/9722791.html



如之前的文章可以看到,golang中的map是不支持并发操作的,golang推荐用户直接用读写锁对map进行保护,也有第三方类库使用分段锁。在1.19版本中,golang基于原本的map,新增了一个支持并发操作的map,叫sync map。



下面我们先介绍一下它的用法,然后在介绍原理,最后详细看看代码。



用法
基本api有这几个



Store 写入
Load 读取,返回值有两个,第一个是value,第二个是bool变量表示key是否存在
Delete 删除
LoadOrStore 存在就读,不存在就写
Range 遍历,注意遍历的快照
sync map底层使用map[interface{}]* entry来做存储,所以无论key还是value都是支持多种数据类型。
一个简单的例子:



package main



import (
“fmt”
“sync”
)



type MySyncMap struct {
sync.Map
}



func (m MySyncMap) Print(k interface{}) {
value, ok := m.Load(k)
fmt.Println(value, ok)
}



func main() {
var syncMap MySyncMap



    syncMap.Print("Key1")

syncMap.Store("Key1", "Value1")
syncMap.Print("Key1")

syncMap.Store("Key2", "Value2")

syncMap.Store("Key3", 2)
syncMap.Print("Key3")

syncMap.Store(4, 4)
syncMap.Print(4)

syncMap.Delete("Key1")
syncMap.Print("Key1") } 输出:


false
Value1 true
2 true
4 true
false
设计原理
常用方案比较
并发hashmap的方案有很多,下面简单提一下几种,然后再讨论golang实现时的考虑。
第一种是最简单的,直接在不支持并发的hashmap上,使用一个读写锁的保护,这也是golang sync map还没出来前,大家常用的方法。这种方法的缺点是写会堵塞读。

第二种是数据库常用的方法,分段锁,每一个读写锁保护一段区间,golang的第三方库也有人是这么实现的。java的ConcurrentHashMap也是这么实现的。平均情况下这样的性能还挺好的,但是极端情况下,如果某个区间有热点写,那么那个区间的读请求也会受到影响。

第三种方法是我们C++自己造轮子时经常用的,使用使用链表法解决冲突,然后链表使用CAS去解决并发下冲突,这样读写都是无锁,我觉得这种挺好的,性能非常高,不知为啥其他语言不这么实现。

然后在《An overview of sync.Map》中有提到,在cpu核数很多的情况下,因为cache contention,reflect.New、sync.RWMutex、atomic.AddUint32都会很慢,golang团队为了适应cpu核很多的情况,没有采用上面的几种常见的方案。

golang sync map的目标是实现适合读多写少的场景、并且要求稳定性很好,不能出现像分段锁那样读经常被阻塞的情况。golang sync map基于map做了一层封装,在大部分情况下,不过写入性能比较差。下面来详细说说实现。

实现思路
要读受到的影响尽量小,那么最容易想到的想法,就是读写分离。golang sync map也是受到这个想法的启发(我自认为)设计出来的。使用了两个map,一个叫read,一个叫dirty,两个map存储的都是指针,指向value数据本身,所以两个map是共享value数据的,更新value对两个map同时可见。

dirty可以进行增删查,当时都要进行加互斥锁。

read中存在的key,可以无锁的读,借助CAS进行无锁的更新、删除操作,但是不能新增key,相当于dirty的一个cache,由于value共享,所以能通过read对已存在的value进行更新。

read不能新增key,那么数据怎么来的呢?sync map中会记录miss cache的次数,当miss次数大于等于dirty元素个数时,就会把dirty变成read,原来的dirty清空。

为了方便dirty直接变成read,那么得保证read中存在的数据dirty必须有,所以在dirty是空的时候,如果要新增一个key,那么会把read中的元素复制到dirty中,然后写入新key。

然后删除操作也很有意思,使用的是延迟删除,优先看read中没有,read中有,就把read中的对应entry指针中的p置为nil,作为一个标记。在read中标记为nil的,只有在dirty提升为read时才会被实际删除。

源码
结构
// The zero Map is empty and ready for use. A Map must not be copied after first use.
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
}

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

// expunged is an arbitrary pointer that marks entries which have been deleted
// from the dirty map.
var expunged = unsafe.Pointer(new(interface{}))

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

sync map结构
mu是用来保护dirty的互斥锁
missed是记录没命中read的次数

注意对于entry.p,有两个特殊值,一个是nil,另一个是expunged。nil代表的意思是,在read中被删除了,但是dirty中还在,所以能直接更新值(如果dirty==nill的特殊情况,下次写入新值时会复制);expunged代表数据在ditry中已经被删除了,更新值的时候要先把这个entry复制到dirty。

Load 读取

// Load returns the value stored in the map for a key, or nil if no
// value is present.
// The ok result indicates whether value was found in the map.
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()
// 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.)
read, _ = m.read.Load().(readOnly)
e, ok = read.m[key]
if !ok && read.amended {
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.
m.missLocked()
}
m.mu.Unlock()
}
if !ok {
return nil, false
}
return e.load()
}

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
}

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
}
读取时,先去read读取;如果没有,就加锁,然后去dirty读取,同时调用missLocked(),再解锁。在missLocked中,会递增misses变量,如果misses>len(dirty),那么把dirty提升为read,清空原来的dirty。

在代码中,我们可以看到一个double check,检查read没有,上锁,再检查read中有没有,是因为有可能在第一次检查之后,上锁之前的间隙,dirty提升为read了,这时如果不double check,可能会导致一个存在的key却返回给调用方说不存在。 在下面的其他操作中,我们经常会看到这个double check。

Store 写入
// Store sets the value for a key.
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() {
// 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 {
e.storeLocked(&value)
} else {
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.
m.dirtyLocked()
m.read.Store(readOnly{m: read.m, amended: true})
}
m.dirty[key] = newEntry(value)
}
m.mu.Unlock()
}

// tryStore stores a value if the entry has not been expunged.
//
// If the entry is expunged, tryStore returns false and leaves the entry
// unchanged.
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
}
}
}

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 {
if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
return true
}
p = atomic.LoadPointer(&e.p)
}
return p == expunged
}

// unexpungeLocked ensures that the entry is not marked as expunged.
//
// If the entry was previously expunged, it must be added to the dirty map
// before m.mu is unlocked.
func (e *entry) unexpungeLocked() (wasExpunged bool) {
return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}
写入的时候,先看read中能否查到key,在read中存在的话,直接通过read中的entry来更新值;在read中不存在,那么就上锁,然后double check。这里需要留意,分几种情况:

double check发现read中存在,如果是expunged,那么就先尝试把expunged替换成nil,最后如果entry.p==expunged就复制到dirty中,再写入值;否则不用替换直接写入值。
dirty中存在,直接更新
dirty中不存在,如果此时dirty为空,那么需要将read复制到dirty中,最后再把新值写入到dirty中。复制的时候调用的是dirtyLocked(),在复制到dirty的时候,read中为nil的元素,会更新为expunged,并且不复制到dirty中。
我们可以看到,在更新read中的数据时,使用的是tryStore,通过CAS来解决冲突,在CAS出现冲突后,如果发现数据被置为expung,tryStore那么就不会写入数据,而是会返回false,在Store流程中,就是接着往下走,在dirty中写入。

再看下情况1的时候,为啥要那么做。double check的时候,在read中存在,那么就是说在加锁之前,有并发线程先写入了key,然后由Load触发了dirty提升为read,这时dirty可能为空,也可能不为空,但无论dirty状态如何,都是可以直接更新entry.p。如果是expunged的话,那么要先替换成nil,再复制entry到dirty中。

疑问:这里不太懂,为啥在read中直接更新就用cas去更新,跑到下面的流程,就用原子更新,可是尽管上了锁,key在read中存在,那么就会并发写,为啥可以不用cas更新??

Delete 删除
// Delete deletes the value for a key.
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
}
if atomic.CompareAndSwapPointer(&e.p, p, nil) {
return true
}
}
}
删除很简单,read中存在,就把read中的entry.p置为nil,如果只在ditry中存在,那么就直接从dirty中删掉对应的entry。

https://studygolang.com/articles/16141


golang map 读写锁与深度拷贝的坑

0X01

golang中,map(字典)无法并发读写

简单来说,新建万条线程对同一个map又读又写,会报错。

为此,最好加锁,其实性能影响并不明显。

type taskCache struct{
sync.RWMutex
data map[string] interface{}
}




0X02

golang中,map(字典)为引用拷贝。

a = 字典一

b = a

实际上是直接将指针传给了b。



于是,有一个读取,写的时候直接读map并返回

复制代码
func GetAllTasks() (result map[string]interface{}, err error) {
// 获得当前的所有任务
DEMO.RLock()
defer DEMO.RUnlock()
return DEMO.data, err
}
复制代码
而在线程中

// 接收后直接打印
fmt.Println(store.GetAllTasks())
结果居然报错,map读写冲突。



于是,我返回去一遍一遍看代码,觉得自己的读写锁写错了。

调式折腾了半天,最后发现,在接收后不用 fmt.Println 打印就不会报错。

这很不科学,然后在接收打印前后加上读锁,不报错了。



0X03

所以golang,加了读写锁的时候,要返回全部值,还不能直接返回这个字典,因为直接返回这个字典,返回了指针,操作的时候要不还要加读写锁,要不就报错。

还没有直接的取地址的值重新给另一个变量的东西,自己写个遍历,一个一个赋值吧,蛋疼,坑货,坑了一晚上

var cache = make(map[string]interface{})
for k,v := range Demo.data{
cache[k] = v
}

https://zhuanlan.zhihu.com/p/102385081?utm_source=qq

核心思想是用空间换时间,用两个map来存储数据,read和dirty,read支持原子操作,可以看作是dirty 的cache,dirty是更底层的数据存储层
4种操作:读key、增加key、更新key、删除key的基本流程
读key:先到read中读取,如果有则直接返回结果,如果没有或者是被删除(有特殊value值可以判断),则到dirty加锁中读取,如果有返回结果并更新miss数
增加key:直接增加到dirty中
更新key:先到read中看看有没有,如果有直接更新key,如果没有则到dirty中更新
删除key:先到read中看看有没有,如果有则直接更新为nil,如果没有则到dirty中直接删除

read的替换:当read多次都没有命中数据,达到阈值,表示这个cache命中率太低,这时直接将整个read用dirty替换掉,然后dirty又重新置为nil,下一次再添加一个新key的时候,会触发一次read到dirty的复制,这样二者又保持了一致。

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

总结,如果对map的读操作远远多于写操作(写操作包括新增和删除key),那么sync.Map是很合适,能够大大提升性能

syncmap是golang1.5引入的线程安全的map,以下是测试程序,结论: 不建议使用sync.map, 原因: 1. 性能不及加锁的map, 2. 对json不友好

package main_test

import (
"math/rand"
"sync"
"testing"
)

type WrapedMap struct {
lck sync.Mutex
m map[int]int
}

var normalMap WrapedMap
var syncMap sync.Map

func TestMain(m *testing.M) {
normalMap = WrapedMap{
lck: sync.Mutex{},
m: make(map[int]int, 100000),
}

m.Run()
}

func BenchmarkLockMapWrite(b *testing.B) {
b.RunParallel(func(pb *testing.PB) {
for pb.Next() {
a := rand.Intn(100) + 1
b := rand.Intn(a)
normalMap.lck.Lock()
normalMap.m[a] = b
normalMap.lck.Unlock()
}
})
}

func BenchmarkLockMapRead(b *testing.B) {
b.RunParallel(func(pb *testing.PB) {
for pb.Next() {
a := rand.Intn(100) + 1
normalMap.lck.Lock()
_, _ = normalMap.m[a]
normalMap.lck.Unlock()
}
})
}

func BenchmarkSyncMapWrite(b *testing.B) {

b.RunParallel(func(pb *testing.PB) {
for pb.Next() {
a := rand.Intn(100) + 1
b := rand.Intn(a)
syncMap.Store(a, b)
}
})
}

func BenchmarkSyncMapRead(b *testing.B) {
b.RunParallel(func(pb *testing.PB) {
for pb.Next() {
a := rand.Intn(100) + 1
syncMap.Load(a)
}
})
}


Category golang