go src - sync.Map

这篇具有很好参考价值的文章主要介绍了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]*entry
	amended 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]
}

go src - sync.Map

expunged

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

状态机:

go src - sync.Map

 总结:

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

go src - sync.Map

 总结:

  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 := i
	for {
		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
		}
	}
}

go src - sync.Map

 总结:

  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
}

go src - sync.Map

 总结:

  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 = true
			previous = *v
		}
	} else if e, ok := m.dirty[key]; ok {
		if v := e.swapLocked(&value); v != nil {
			loaded = true
			previous = *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
		}
	}
}

go src - sync.Map

总结:

  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 := false
	if 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 := new
	for {
		if e.p.CompareAndSwap(p, &nc) {
			return true
		}
		p = e.p.Load()
		if p == nil || p == expunged || *p != old {
			return false
		}
	}
}

go src - sync.Map

 总结:

  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
}

go src - sync.Map

总结:

  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还是其他的并发原语。文章来源地址https://www.toymoban.com/news/detail-513947.html

到了这里,关于go src - sync.Map的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Go语言中sync.Map、sync.Pool和Context的用法

    目录 【sync.Map】 实现线程安全的 map 类型  使用 sync.Map 实现并发读写的map 【sync.Pool】 使用 带缓冲channel 实现对象池 使用 sync.Pool 创建临时对象池 【Context 上下文】 Context应用:实现带超时功能的远程调用 Context应用:监控指令  Context应用:取消关联任务 之前在 Go语言中ar

    2024年02月05日
    浏览(46)
  • Go并发:使用sync.Pool来性能优化

    在Go提供如何实现对象的缓存池功能?常用一种实现方式是:sync.Pool, 其旨在缓存已分配但未使用的项目以供以后重用,从而减轻垃圾收集器(GC)的压力。 sync.Pool的结构也比较简单,常用的方法有Get、Put 接着,通过一个简单的例子,来看看是如何使用的 在之前的文章中有提

    2024年02月08日
    浏览(40)
  • Go 语言 map 是并发安全的吗?

    原文链接: Go 语言 map 是并发安全的吗? Go 语言中的 map 是一个非常常用的数据结构,它允许我们快速地存储和检索键值对。然而,在并发场景下使用 map 时,还是有一些问题需要注意的。 本文将探讨 Go 语言中的 map 是否是并发安全的,并提供三种方案来解决并发问题。 先来

    2024年02月06日
    浏览(37)
  • 【Go进阶】怎么实现并发安全的map

    go语言提供的数据类型中,只有channel是并发安全的,基础map并不是并发安全的。以下三种方案实现了并发安全的map。 实现原理: 给map添加一把读写锁,读操作加读锁进行读取;添加,更新,删除,遍历,获取长度这些操作加写锁后在进行操作。 代码实现: 以下代码是并发

    2024年02月03日
    浏览(37)
  • go中数组、切片、map是否线程(并发)安全?

    博客主页:🏆 看看是李XX还是李歘歘  🏆 🌺每天不定期分享一些包括但不限于计算机基础、算法、后端开发相关的知识点,以及职场小菜鸡的生活。🌺 💗 点关注不迷路,总有一些📖知识点📖是你想要的 💗  目录 什么是线程(并发)安全? 非线程安全原因 map 解决方案

    2024年02月02日
    浏览(54)
  • Go 语言为什么不支持并发读写 map?

    大家好,我是 frank ,「 Golang 语言开发栈」公众号作者。 01 介绍 在 Go 语言项目开发中,我们经常会使用哈希表 map ,它的时间复杂度是 O(1) ,Go 语言中的 map 使用开放寻址法避免哈希碰撞。 Go 语言中的 map 并非原子操作,不支持并发读写操作。 Go 官方认为 map 在大多数情况下

    2024年02月02日
    浏览(60)
  • 使用go_concurrent_map 管理 并发更新缓存

    在后台服务中,为了提速,我在内存还做了一个告诉缓存来管理用户信息,根据更新通知,或者定时去redis中同步信息,那么在加载或者更新某个用户元素时,要防止并发, 当: 1)如果内存缓存没有; 2)去数据库或者redis加载; 3)添加到内存缓存; 这里就有个并发重复的

    2024年04月25日
    浏览(35)
  • 掌握Go并发:Go语言并发编程深度解析

    🏷️ 个人主页 :鼠鼠我捏,要死了捏的主页  🏷️ 系列专栏 :Golang全栈-专栏 🏷️ 个人学习笔记,若有缺误,欢迎评论区指正   前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站AI学习网站。 当我们开发一个W

    2024年02月20日
    浏览(69)
  • GO语言网络编程(并发编程)并发介绍,Goroutine

    进程和线程 并发和并行 协程和线程 协程:独立的栈空间,共享堆空间,调度由用户自己控制,本质上有点类似于用户级线程,这些用户级线程的调度也是自己实现的。 线程:一个线程上可以跑多个协程,协程是轻量级的线程。 goroutine 只是由官方实现的超级\\\"线程池\\\"。 每个

    2024年02月09日
    浏览(58)
  • 16 Go并发编程(三): Go并发的传统同步机制

    Go 传统同步机制 在《Go并发编程初探》中我们提到同步概念,所谓同步是相对异步而言,即串行相对于并行。 在学习Go通信机制时我们知道管道其实就是并发单元同步方式的一种,基于CSP并发模型,Go在语言原语上使管道作为核心设计,这是Go的设计哲学,也是Go所提倡的同步

    2023年04月08日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包