[最初更新日期:2023-05-08 18:04]
Go中一般的map是非线程平安的,想要线程平安的拜访一个map,有两种形式一种是map+mutex另一种就是原生的sync.Map,这篇文章会具体的介绍sync.Map底层是如何实现的,以及一些罕用的场景。
如何保障线程平安?
sync.Map的数据结构如下:
type Map struct { mu Mutex // 锁,保障写操作及dirty晋升为read的线程平安 read atomic.Value // readOnly 只读map dirty map[any]*entry // 脏map,当外部有数据时就肯定蕴含read中的数据 misses int // read未命中次数,当达到肯定次数时会触发dirty中的护具降职到read}
如果只看这个构造咱们可能会有以下几个疑难:
- sync.Map中也用了mutex那和map+mutex的实现形式不就一样了吗?
- misses做什么用的?
- read的类型是一个
atomic.Value
而dirty是map[any]*entry
,为什么不同?
sync.Map中也用了mutex那和map+mutex的实现形式不就一样了吗?
- 在实质上都是通过map+mutex的实现形式来实现的
- sync.Map通过减少read map,升高在进行读取操作时的加锁概率,减少读取的性能。
misses做什么用的?
- misses是用于标记read中未命中次数的
- 当misses达到肯定值时会触发dirty的降职(晋升为read)
具体源码如下:
// 当执行Load操作时没能在read中命中key,则进行一次miss记录func (m *Map) missLocked() { // 1.miss计数加1 m.misses++ // 2.判断dirty是否满足降职条件 if m.misses < len(m.dirty) { // 2.1不满足间接返回 return } // 3.将dirty中的数据转存到read的m中,旧的read中的数据被摈弃 m.read.Store(readOnly{m: m.dirty}) // 4.清空dirty m.dirty = nil // 5.重置miss计数 m.misses = 0}
从代码中能够看到:
- 当misses值大于等于dirty中数据个数的时候会触发dirty的降职
- 在dirty降职时,直间接把read重置成了一个新生成的readOnly,其中m为新的dirty,amended为默认值false,保障每次触发降职都主动将amended设置为了false
- 在dirty降职时,并没有触发数据的拷贝
read的类型是一个atomic.Value
而dirty是map[any]*entry
,为什么不同?
type readOnly struct { m map[any]*entry // read map中的数据 amended bool // 标记dirty map中是否有read中没有的key,如果有,则此值为true}type entry struct { p unsafe.Pointer // *interface{} 一个指向具体数据的指针}
- read的类型底层是存储的readOnly类型,而readOnly类型只是在
map[any]*entry
的根底上减少了一个amended
标记 - 如果amended为false,则代表dirty中没有read中没有的数据,此时能够防止一次dirty操作(会加锁),从而升高无意义的加锁。
- read被申明为
atomic.Value
类型是为了满足在无锁的状况下多个Goroutine同时读取read时的数据一致性
sync.Map实用于那些场景?
sync.Map更适宜读多写少的场景,而当map须要频繁写入的时候,map+mutex的计划通过管制锁的力度能够达到比sync.Map更好的性能。
sync.Map不反对遍历操作,因为读写拆散的设计使得在遍历过程中可能存在一些未实现的批改操作,导致遍历后果不确定。
为什么sync.Map适宜读多写少的场景?
sync.Map的读取办法为Load
办法,具体的源码实现如下:
func (m *Map) Load(key any) (value any, ok bool) { // 1.将read中的数据强转为readOnly read, _ := m.read.Load().(readOnly) // 2.从read中查问key,检查数据是否存在 e, ok := read.m[key] // 3.如果read中不存在,且amended标记显示dirty中存在read中没有的key,则去dirty中查问 if !ok && read.amended { // 3.1开始操作dirty,须要加锁保障线程平安 m.mu.Lock() // 3.2 从新从read中查看一次,防止在Lock执行前dirty中的数据触发了降职到read的操作 read, _ = m.read.Load().(readOnly) e, ok = read.m[key] // 3.3 同3 if !ok && read.amended { // 3.4 从dirty中查问 e, ok = m.dirty[key] // 3.5 无论是否从dirty中查问到数据,都相当于从read中miss了,须要更新miss计数(更新计数可能会触发dirty数据的降职) m.missLocked() } // 3.5 操作实现解锁 m.mu.Unlock() } // 4.检测后果,ok为false代表没有查问到数据 // ok为true分为两种状况:1.从read中查问到了数据,read命中;2.从dirty中查问到了数据 // ok为false分为两种状况: // 1.read没有命中,但read.amended为false // 2.read没有命中,read.amended为true,但dirty中也不存在 if !ok { return nil, false } // 返回查问到的数据(这个值也并不一定是真的存在,须要依据p确定是一个失常的值还是一个nil) return e.load()}// 当从read或者dirty中获取到一个key的值的指针时,须要去加载对应指针的值func (e *entry) load() (value any, ok bool) { // 1.院子操作获取对应地址的值 p := atomic.LoadPointer(&e.p) // 2.如果值曾经不存在或者标记为被删除则返回nil,false if p == nil || p == expunged { return nil, false } // 3.返回具体的值,true return *(*any)(p), true}
每次读取数据时,优先从read中读取,且read中数据的读取不须要进行加锁操作;当read中未命中且amended标记显示dirty中存在read中没有的数据时,才进行dirty查问,并加锁。在读多写少的状况下,大多数时候数据都在read中所以能够防止加锁,以此来进步并发读的性能。
sync.Map的写操作方法为Store
办法
func (m *Map) Store(key, value any) { // 1.从read中查问数据是否曾经存在,如果存在则尝试批改 read, _ := m.read.Load().(readOnly) if e, ok := read.m[key]; ok && e.tryStore(&value) { // 1.1 read中存在数据,且更新实现,间接返回 return } //2.read中没有,筹备操作dirty,为保障线程平安加锁 m.mu.Lock() read, _ = m.read.Load().(readOnly) if e, ok := read.m[key]; ok { // 3.如果在read中查问到数据,则查看是否曾经被标记为删除, if e.unexpungeLocked() { // 3.1 如果被标记为删除须要清空标记并退出到dirty中 m.dirty[key] = e } // 3.2 更新entry的值 e.storeLocked(&value) } else if e, ok := m.dirty[key]; ok { // 4 如果存在于dirty中,则间接更新entry的值 e.storeLocked(&value) } else { // 5 如果之前这个key不存在,则将新的key-value退出到dirty中 if !read.amended { // 5.1 如果read.amended标记显示之前dirty中不存在read中没有的key,则重置dirty,并标amended为true // 5.1.1 将read中所有未被标记为删除的entry重新加入到dirty中 m.dirtyLocked() // 5.1.2 更新read.amended标记 m.read.Store(readOnly{m: read.m, amended: true}) } // 5.2 将新的key-value退出到dirty中 m.dirty[key] = newEntry(value) } m.mu.Unlock()}// 判断entry是否被标记为删除,如果是将其批改为nilfunc (e *entry) unexpungeLocked() (wasExpunged bool) { return atomic.CompareAndSwapPointer(&e.p, expunged, nil)}
写操作分为以下几种状况:
- 数据在read中
- 数据在read中但曾经被标记为删除
- 数据在dirty中
- 一个全新的数据
当数据在read中时,Store会尝试通过原子操作批改数据,如果原子操作胜利,则相当于数据更新实现;
具体的代码如下:
func (e *entry) tryStore(i *any) bool { for { // 1.获取entry具体的值 p := atomic.LoadPointer(&e.p) // 2.如果数据曾经被标记删除,则返回false if p == expunged { return false } // 3.更新以后值,并返回true if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) { return true } }}
当数据在read中曾经被标记为删除,此时须要从新将entry退出到dirty中,并更新值(这里实质上减少了一个新的entry只是服用了之前entry的地址空间)
当数据在dirty中时,则间接通过原子操作更新entry的指针;
当数据是一个新数据时,会创立一个新的entry退出到dirty中,并且如果是dirty中的第一个数据则会执行dirtyLocked
办法,将read中以后的数据(未标记删除的)退出到dirty中。
dirtyLocked的具体实现如下:
func (m *Map) dirtyLocked() { //1 dirty之前是nil的状况才能够进行重置操作 if m.dirty != nil { return } // 2 获取read中的数据 read, _ := m.read.Load().(readOnly) // 3 初始化dirty m.dirty = make(map[any]*entry, len(read.m)) // 4 遍历read for k, e := range read.m { // 4.1 将非nil且未被标记为删除的对象退出到dirty中 if !e.tryExpungeLocked() { m.dirty[k] = e } }}// 判断entry是否被标记为删除,如果entry的值为nil,则将其标记为删除func (e *entry) tryExpungeLocked() (isExpunged bool) { // 1 获取entry的值 p := atomic.LoadPointer(&e.p) for p == nil { // 2 如果以后entry的值为空,则尝试将此key标记为删除 if atomic.CompareAndSwapPointer(&e.p, nil, expunged) { return true } p = atomic.LoadPointer(&e.p) } // 3 判断p是否为被标记为删除 return p == expunged}
通过下面的剖析咱们能够发现当写操作频繁时存在以下几个问题
- dirty中存在大量数据,而read的查问会大概率无奈命中,从而导致查问须要查问read和dirty两个map且有额定的冗余操作,所以读性能被大大降低
- 频繁的无奈命中导致dirty数据的降职,尽管降职时只是进行指针切换及dirty的清空,但每次降职后的第一次写入都会导致dirty对read进行拷贝,大大降低性能。
- 每次写操作为了因为不确定数据是在read还是dirty或者新数据须要进行额定的检查和操作
- dirty中和read中在某些状况下存在数据反复,内存占用会高一些
综上,在写操作比拟频繁的时候,sync.Map的各方面性能都大大降低;而对于一些只有极少写操作的数据(比方:只在服务器启动时加载一次的表格数据),sync.Map能够进步并发操作的性能。
如何删除数据
在下面的dirtyLoacked办法中咱们看到当初始化dirty后,会遍历read中的数据,将非nil且未被标记为删除的对象退出到dirty中。由此能够看出read中的数据在删除时并不会立即删除只是将对象标记为nil或者expunged。
具体代码如下:(Delete办法实质上就是执行的LoadAndDelete)
func (m *Map) LoadAndDelete(key any) (value any, loaded bool) { read, _ := m.read.Load().(readOnly) // 1 从read中查问数据 e, ok := read.m[key] // 2 如果read中不存在,且amended标记显示dirty中存在read中没有的key,则去dirty中查问 if !ok && read.amended { // 3.1开始操作dirty,须要加锁保障线程平安 m.mu.Lock() read, _ = m.read.Load().(readOnly) // 3.2 从新从read中查看一次,防止在Lock执行前dirty中的数据触发了降职到read的操作 e, ok = read.m[key] if !ok && read.amended { // 3.3 从dirty中查问 e, ok = m.dirty[key] // 3.4 从dirty中删除 delete(m.dirty, key) // 3.5 无论是否从dirty中查问到数据,都相当于从read中miss了,须要更新miss计数(满足条件后会触发dirty降职) m.missLocked() } m.mu.Unlock() } // 4 和load一样,这里ok为true可能是在read中读取到数据或者dirty中读取到数据, // dirty中的话尽管曾经删除但须要清空entry中的指针p if ok { // 5 标记删除 return e.delete() } return nil, false}
如上述代码第5
局部所示,无论entry存在哪里,最终都须要将entry标记为删除。如果存在read中会在dirty初始化时不被退出到dirty中,当dirty再次降职时read中的数据也就被抛弃了。如果存在dirty中则间接清空了数据并标记entry被删除。
sync.Map的Range办法
sync.Map并不反对遍历,但却提供了一个Range办法,此办法并不是和range
关键字一样对map的遍历。
Range办法的具体作用:
- 遍历所有read中的元素,对其中的每个元素执行函数f
- 如果当任何一个元素作为参数执行函数f返回false,则立即中断遍历
尽管在执行初始阶段Range会将dirty的数据降职一次,但依然不能保障在执行过程中没有新的数据,所以Range只是遍历了最新的read中的数据,而非全副数据。
// 遍历sync.Mapfunc (m *Map) Range(f func(key, value any) bool) { read, _ := m.read.Load().(readOnly) // 1 如果存在未降职的数据,则先进行一次dirty数据降职 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() } // 2 遍历read中的所有entry,别离执行f函数 for k, e := range read.m { v, ok := e.load() if !ok { continue } // 3 当某个entery执行f函数返回false,则中断遍历 if !f(k, v) { break } }}
其余
问:什么时候革除被标记删除的value
答:当首次向dirty中存入数据时,会触发dirty复制read中的内容,此时再复制时只复制了非nil且未被标记删除的entry,当dirty再次降职时就笼罩掉了read中的数据,实现被标记删除的entry的删除。