最新要闻

广告

手机

光庭信息跌4.57% 2021上市超募11亿2022扣非降74% 时快讯

光庭信息跌4.57% 2021上市超募11亿2022扣非降74% 时快讯

搜狐汽车全球快讯 | 大众汽车最新专利曝光:仪表支持拆卸 可用手机、平板替代-环球关注

搜狐汽车全球快讯 | 大众汽车最新专利曝光:仪表支持拆卸 可用手机、平板替代-环球关注

家电

【聚看点】go src - sync.Map

来源:博客园

前言

在并发编程中,我们经常会遇到多个goroutine同时操作一个map的情况。如果在这种情况下直接使用普通的map,那么就可能会引发竞态条件,造成数据不一致或者更严重的问题。


(资料图片)

sync.Map是Go语言中内置的一种并发安全的map,但是他的实现和用法与普通的map完全不同,这篇文章将详细介绍这些区别。

一、使用方法

创建sync.Map非常简单,只需要声明即可:

var m sync.Map

使用Store方法存储键值对:

m.Store("hello", "world")

使用Load方法获取值:

value, ok := m.Load("hello")if ok {    fmt.Println(value) // 输出:world}

使用Delete方法删除键值对:

m.Delete("hello")

二、原理

sync.Map的核心实现依赖于两个主要的数据结构:一个只读的read字段,以及一个可写的dirty字段。

读操作:

当我们进行读取操作(Load)时,首先会尝试从read字段读取数据,这个过程是完全无锁的。

如果read中没有找到,那么会尝试加锁后从dirty中读取。这个设计保证了在大部分读多写少的场景下,读操作是无锁的,大大提升了性能。

写操作:

写入操作(key不存在)时,会直接在dirty中进行写入,并将readamended标记为true,表示read字段有待更新的数据。

然后再有新的读取操作到来时,如果amendedtrue并且miss数量超过dirty长度,则会从dirty中拷贝数据到read,并清除amended标记。

总结:

在这个设计中,读操作在大部分情况下是无锁的,而写操作(key不存在时)则需要获取dirty的锁,从而实现了对于读多写少场景的优化。

三、优点

sync.Map在以下两种情况下表现得特别好:

  • 键值对的数量相对稳定,读操作明显多于写操作的场景
  • 多个goroutine并发读取不重叠的键集的场景

这是因为sync.Map的设计将读取操作优化至极致,同时尽量减少在写入新键值对时的锁竞争。

四、缺点

然而,sync.Map并不是银弹,也有一些局限:

  • sync.Map没有像普通map那样的直观语法,必须使用特定的方法来操作键值对
  • 对于键值对数量快速增长、写操作频繁的场景,sync.Map的性能可能不如使用普通map加锁的方式
  • 读操作无锁情况下,可能会出现时间竞态问题

五、实现

sync.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).read atomic.Pointer[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.dirty map[any]*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.misses int}

readonly

// readOnly is an immutable struct stored atomically in the Map.read field.type readOnly struct {m       map[any]*entryamended bool // true if the dirty map contains some key not in m.}

entry

// 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.p atomic.Pointer[any]}

expunged

// expunged is an arbitrary pointer that marks entries which have been deleted// from the dirty map.var expunged = new(any)

状态机:

总结:

  1. 当key从read中删除时,会先被标记为nil,不会立马删除key
  2. 当重新初始化dirty时(将read.m克隆到dirty),如果key的值为nil,会设置为expunged,并不在dirty中创建这个key。
  3. 如果key为expunged,LoadOrStore/Swap/CompareAndDelete/CompareAndSwap都会不执行写操作并返回false。

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 any) (value any, ok bool) {read := m.loadReadOnly()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.loadReadOnly()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 (m *Map) loadReadOnly() readOnly {if p := m.read.Load(); p != nil {return *p}return readOnly{}}

总结:

  1. 如果查询的key在read中找到了,返回entry.load()
  2. 如果查询的key在read中未找到,并且read和dirty一致,返回nil, false
  3. key未找到,并且read与dirty不一致
    1. 加锁
    2. 重新查询read,类似上面1、2流程,如果未找到并且read和dirty不一致则继续
    3. 在dirty中查询
    4. misses加一
    5. 如果misses数大于dirty长度,将dirty同步到read,重置dirty和misses
    6. 释放锁
    7. 返回结果

LoadOrStore

// LoadOrStore returns the existing value for the key if present.// Otherwise, it stores and returns the given value.// The loaded result is true if the value was loaded, false if stored.func (m *Map) LoadOrStore(key, value any) (actual any, loaded bool) {// Avoid locking if it"s a clean hit.read := m.loadReadOnly()if e, ok := read.m[key]; ok {actual, loaded, ok := e.tryLoadOrStore(value)if ok {return actual, loaded}}m.mu.Lock()read = m.loadReadOnly()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 {// 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)actual, loaded = value, false}m.mu.Unlock()return actual, loaded}// tryLoadOrStore atomically loads or stores a value if the entry is not// expunged.//// If the entry is expunged, tryLoadOrStore leaves the entry unchanged and// returns with ok==false.func (e *entry) tryLoadOrStore(i any) (actual any, loaded, ok bool) {p := e.p.Load()if p == expunged {return nil, false, false}if p != nil {return *p, true, true}// Copy the interface after the first load to make this method more amenable// to escape analysis: if we hit the "load" path or the entry is expunged, we// shouldn"t bother heap-allocating.ic := ifor {if e.p.CompareAndSwap(nil, &ic) {return i, false, true}p = e.p.Load()if p == expunged {return nil, false, false}if p != nil {return *p, true, true}}}

总结:

  1. 如果key在read中找到了,并且不为expunged
    1. 如果为nil,则CAS新的值,并返回value, false
    2. 如果不为nil,则返回*p, true
  2. 如果key在read中不存在,或者为expunged
    1. 加锁
    2. 再次在read中查找,如果找到了
      1. 如果为expunged,结果为nil, false
      2. 如果为nil,则CAS新的值,结果为value, false
      3. 如果不为nil,结果为*p, true
    3. 如果在dirty中找到了,重复2的逻辑判断
    4. 在read和dirty中都没有,则创建一个新的entry
    5. 释放锁
    6. 返回结果

Delete/LoadAndDelete

// Delete deletes the value for a key.func (m *Map) Delete(key any) {m.LoadAndDelete(key)}
// LoadAndDelete deletes the value for a key, returning the previous value if any.// The loaded result reports whether the key was present.func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {read := m.loadReadOnly()e, ok := read.m[key]if !ok && read.amended {m.mu.Lock()read = m.loadReadOnly()e, ok = read.m[key]if !ok && read.amended {e, ok = m.dirty[key]delete(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 e.delete()}return nil, false}

总结:

  1. 如果要删除的key在read中存在,将它置为nil
  2. 如果要删除的key在read中未找到,并且read和dirty一致,说明key不存在,返回nil, false
  3. key未找到,并且read和dirty不一致
    1. 加锁
    2. 重新查询read,类似上面1、2流程,如果key未找到,并且read和dirty不一致继续
    3. 在dirty中查询并删除
    4. misses加一
    5. 如果misses数大于dirty长度,将dirty同步到read,重置dirty和misses
    6. 释放锁
    7. 如果key在dirty中也不存在,返回nil, false;反之,将它置为nil

Store/Swap

// Store sets the value for a key.func (m *Map) Store(key, value any) {_, _ = m.Swap(key, value)}// Swap swaps the value for a key and returns the previous value if any.// The loaded result reports whether the key was present.func (m *Map) Swap(key, value any) (previous any, loaded bool) {read := m.loadReadOnly()if e, ok := read.m[key]; ok {if v, ok := e.trySwap(&value); ok {if v == nil {return nil, false}return *v, true}}m.mu.Lock()read = m.loadReadOnly()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}if v := e.swapLocked(&value); v != nil {loaded = trueprevious = *v}} else if e, ok := m.dirty[key]; ok {if v := e.swapLocked(&value); v != nil {loaded = trueprevious = *v}} 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()return previous, loaded}// trySwap swaps a value if the entry has not been expunged.//// If the entry is expunged, trySwap returns false and leaves the entry// unchanged.func (e *entry) trySwap(i *any) (*any, bool) {for {p := e.p.Load()if p == expunged {return nil, false}if e.p.CompareAndSwap(p, i) {return p, true}}}

总结:

  1. 如果key在read中找到了,并且不为expunged,则试图CAS并返回结果
  2. key在read中未找到,或者为expunged
    1. 加锁
    2. 在read中查询
      1. 如果查到了,试图unexpunge
        1. 如果需要unexpunge,会将entry置(CAS)为nil,并在dirty中插入key
        2. 执行entry的Swap
    3. 在ditry中查询
      1. 如果查到了,执行entry的Swap
    4. 都没查到,则检查dirty是否存在,初始化dirty,并在dirty增加新的entry
    5. 释放锁
    6. 返回结果

CompareAndSwap

// CompareAndSwap swaps the old and new values for key// if the value stored in the map is equal to old.// The old value must be of a comparable type.func (m *Map) CompareAndSwap(key, old, new any) bool {read := m.loadReadOnly()if e, ok := read.m[key]; ok {return e.tryCompareAndSwap(old, new)} else if !read.amended {return false // No existing value for key.}m.mu.Lock()defer m.mu.Unlock()read = m.loadReadOnly()swapped := falseif e, ok := read.m[key]; ok {swapped = e.tryCompareAndSwap(old, new)} else if e, ok := m.dirty[key]; ok {swapped = e.tryCompareAndSwap(old, new)// We needed to lock mu in order to load the entry for key,// and the operation didn"t change the set of keys in the map// (so it would be made more efficient by promoting the dirty// map to read-only).// Count it as a miss so that we will eventually switch to the// more efficient steady state.m.missLocked()}return swapped}// tryCompareAndSwap compare the entry with the given old value and swaps// it with a new value if the entry is equal to the old value, and the entry// has not been expunged.//// If the entry is expunged, tryCompareAndSwap returns false and leaves// the entry unchanged.func (e *entry) tryCompareAndSwap(old, new any) bool {p := e.p.Load()if p == nil || p == expunged || *p != old {return false}// Copy the interface after the first load to make this method more amenable// to escape analysis: if the comparison fails from the start, we shouldn"t// bother heap-allocating an interface value to store.nc := newfor {if e.p.CompareAndSwap(p, &nc) {return true}p = e.p.Load()if p == nil || p == expunged || *p != old {return false}}}

总结:

  1. 如果key在read中找到了
    1. 如果为nil/expunged/不等于old,则返回false
    2. 试图进行entry的CAS,成功返回true,失败继续1、2流程
  2. 如果key在read中未找到,并且read与dirty没有不一致,返回false
  3. 如果key在read中未找到,并且read与dirty不一致
    1. 加锁
    2. 如果key在read中找到
      1. 如果仍然为nil/expunged/不等于old,结果为false
      2. 试图进行entry的CAS,CAS成功,则结果为true;否则继续1、2流程
    3. 如果key在dirty中找到
      1. 如果不等于old,结果为false
      2. 试图进行entry的CAS,CAS成功,则结果为true;否则继续1、2流程
      3. misses加一
      4. 如果misses数大于dirty长度,将dirty同步到read,重置dirty和misses
    4. 释放锁
    5. 返回结果

CompareAndDelete

// CompareAndDelete deletes the entry for key if its value is equal to old.// The old value must be of a comparable type.//// If there is no current value for key in the map, CompareAndDelete// returns false (even if the old value is the nil interface value).func (m *Map) CompareAndDelete(key, old any) (deleted bool) {read := m.loadReadOnly()e, ok := read.m[key]if !ok && read.amended {m.mu.Lock()read = m.loadReadOnly()e, ok = read.m[key]if !ok && read.amended {e, ok = m.dirty[key]// Don"t delete key from m.dirty: we still need to do the “compare” part// of the operation. The entry will eventually be expunged when the// dirty map is promoted to the read map.//// 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()}for ok {p := e.p.Load()if p == nil || p == expunged || *p != old {return false}if e.p.CompareAndSwap(p, nil) {return true}}return false}

总结:

  1. 如果key在read中找到了
    1. 如果为nil/expunged/不等于old,则返回false
    2. 试图进行entry的CAS,成功返回true,失败继续1、2流程
  2. 如果key在read中未找到,并且read和dirty没有不一致,返回false
  3. 如果key在read中未找到,并且read和dirty不一致
    1. 加锁
    2. 从read中查找
      1. 如果找到key
        1. 为nil/expunged/不等于old,结果为false
        2. 试图进行CAS,成功结果为true,失败继续尝试
      2. 如果没找到,并且没有不一致,结果为false
    3. 如果read和dirty有不一致
      1. 从dirty中查找
      2. 如果找到key
        1. 不等于old,结果为false
        2. 试图CAS,成功结果为true,失败继续尝试
      3. 没找到key,结果为false
    4. 释放锁
    5. 返回结果

结论

总的来说,sync.Map是Go标准库提供的一个非常有用的工具,它可以帮助我们简化并发编程,并且在一些特定的场景下能提供良好的性能。

但在使用的时候,我们需要根据具体的应用场景和需求来选择使用sync.Map还是其他的并发原语。

关键词: