golang sync.Map 原理以及性能分析_golang 读写都很多 适合map吗-程序员宅基地

技术标签: java  后端  

sync.Map 原理以及性能分析

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 
}

readOnly.amended指明Map.dirty中有readOnly.m未包含的数据,所以如果从Map.read找不到数据的话,还要进一步到Map.dirty中查找。

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

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

这里p有三个值:

  1. nil: entry已被删除了,并且m.dirty为nil
  2. expunged: entry已被删除了,并且m.dirty不为nil,而且这个entry不存在于m.dirty中
  3. 其它: entry是一个正常的value

sync.Map也是在golang提供的map关键字之上封装实现的。

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

  1. 空间换时间。 通过冗余的两个数据结构(read、dirty),实现加锁对性能的影响。
  2. map只保存key和对应的value的指针,这样可以并发的读写map, 实际更新指向value的指针再通过基于CAS的无锁atomic。
  3. 使用只读数据(read),避免读写冲突
  4. 动态调整,miss次数多了之后,将dirty数据提升为read。
  5. double-checking。
  6. 延迟删除。 删除一个键值只是打标记,只有在提升dirty的时候才清理删除的数据。
  7. 优先从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
}

整体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.mm.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
		}
	}
}

整体的pipeline可以用下图来解释:
在这里插入图片描述
你可以看到,以上操作都是先从操作m.read开始的,不满足条件再加锁,然后操作m.dirty。

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

  1. 从m.dirty到m.read的迁移,这个迁移过程其实是指针的的修改,所以效率高;
  2. 从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()
	}
}

整体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
		}
	}
}

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

Range方法调用前可能会做一个m.dirty的提升,不过提升m.dirty不是一个耗时的操作。

sync.Map总结

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

  1. 无锁读与读写分离;
    在这里插入图片描述
  2. 写加锁与延迟提升;
    在这里插入图片描述
  3. 指针与惰性删除,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/

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_54850604/article/details/123933055

智能推荐

为什么基于DNS的全局负载均衡(GSLB)不起作用?_gslb时不时不能解析-程序员宅基地

文章浏览阅读4.8k次,点赞2次,收藏11次。Why DNS Based Global Server Load Balancing (GSLB) Doesn’t Work作者:Pete Tenereillo3/11/04Copyright Tenereillo, Inc. 2004序言弗雷德:乔,我要去赶一班飞机,从好莱坞到洛杉矶国际机场需要多长时间? 乔:恩。。。这取决于你走哪条路。 _gslb时不时不能解析

windows下vs2015编译POCO及使用poco操作sqlite_poco在vs下指定sql-程序员宅基地

文章浏览阅读1.6k次。1.下载POCOhttps://pocoproject.org/releases/我们选择windows下的zip包下载,注意有两个版本poco-1.9.4-all.zippoco-1.9.4.zip其中不带all的是基础版本,只包含基本的poco类库,带all的是全功能版本,包含sqlite,opensll等等。2.编译Poco C++前提条件:1)Poco C++源码(官网..._poco在vs下指定sql

利用VBB仿真——实现LED+数字键盘密码验证_vbb+-程序员宅基地

文章浏览阅读919次。使用VBB仿真,实现密码验证。接线 代码贴图 操作接线:代码贴图:操作:初始密码:1234每组验证可输入4位字符,然后任意再触发任意数字键盘按键,完成一组输入验证。右LED灯亮时表示输入错误,左LED灯亮时表示输入正确。当错误输入次数满三次后闪烁报警,仅当再次正确输入后错误计数清零。..._vbb+

表白神器!程序员七夕情人节源码合集_iapp表白源码-程序员宅基地

文章浏览阅读3.9k次,点赞2次,收藏12次。转眼又到了传统的情人节七夕了,今天给大家分享之前收藏的七夕表白网页源代码合集,让程序员的恋人们感受一下不一样的浪漫。表白源码一:<script> (function(){ var canvas = $('#canvas'); if (!canvas[0].getContext) { $("#error").show(); return false; } var_iapp表白源码

面向对象八大设计原则_稳定不依赖变化-程序员宅基地

文章浏览阅读191次。1 依赖倒置模式 (DIP)稳定不依赖于变化,提出了抽象类。2 开放封闭原则(OCP)对扩展开放,对更改封闭类模块应该是可扩展,不可修改的3 单一职责原则 (SRP)类里面不要放太多的成员,这代表这个类里面隐含了多个责任。4 Liskov替换原则(LSP)5接口隔离原则(ISP)接口应该小而完备 注意public、private、protected的使用。6 优先使用对象组合而不是类继承7 封装变化点使用封装来创建对象之间的分界层。8 针对接口编程,而不是针对实现编程。..._稳定不依赖变化

随便推点

计算机视觉:你必须了解的图像数据底层技术-程序员宅基地

文章浏览阅读552次。点击上方“小白学视觉”,选择加"星标"或“置顶”重磅干货,第一时间送达转自|新机器视觉引言计算机视觉(Computer Vision)自兴起以来就非常迅速且广泛应..._一张图片的底层数据

css样式引用的几种方法、优先级关系及权重计算_如何提高link样式文件的权重-程序员宅基地

文章浏览阅读1.5k次。1.引用方式1.内联式(行内样式)将标记的style属性值直接赋值为所定义的样式规则&amp;amp;lt;p style = &amp;quot;color:red;background:#000000;&amp;quot;&amp;amp;gt;这是一个段落&amp;amp;lt;/p&amp;amp;gt;2.嵌入式利用&amp;amp;lt;style&amp;amp;gt;&amp;amp;lt_如何提高link样式文件的权重

ks.cfg使用于HPC和ORACLE单机,系统版本:RHEL6.2,硬件平台:X86全系列_oraclelinux ks.cfg-程序员宅基地

文章浏览阅读2.2k次。由于AMD 6200系列和INTEL E5系列等新架构CPU的大量推广,传统的SUSE10和RHEL5在新的硬件平台上已经不能发挥出良好的性能。 经大量测试发现,在RHEL6.2 x64平台上,infiniband网络和计算软件能得到最佳性能。 由于RHEL6.2 x64在系统安装时有很多32位软件包被自动忽略,同时使用UUID方式挂载硬盘不方便克隆和修复。现发布一个新测试通过的k_oraclelinux ks.cfg

cvi文件操作笔记_cvi fopen-程序员宅基地

文章浏览阅读1.4k次。int i = 0; int x = 0; char str[20]; char val1[20],val2[20],val3[20]; case EVENT_LEFT_CLICK_UP: { sprintf(CanMeng_FileName,"%s%s","file",".txt"); http://www.docin.com/p-647400695.html printf("write file:%s\n",CanMeng_FileName); Ca._cvi fopen

Ubuntu 13.04 Linux 3D桌面完全教程,显卡驱动安装方法,compiz特效介绍,常见问题解答_linux桌面启动u3d程序 需要更新什么吗-程序员宅基地

文章浏览阅读2.3k次。[2013年4月28日更新] Ubuntu Linux 3D桌面完全教程,显卡驱动安装方法,compiz特效介绍,常见问题解答。本教程最早是一善鱼 YQ-YSY 于2008年编写并发布在Ubuntu中文论坛forum.ubuntu.org.cn配置美化区3D桌面特效版块的:——《图解Ubuntu8.10和8.04最简便的显卡驱动安装和3D桌面启用方法,compiz fusion常见问题解答_linux桌面启动u3d程序 需要更新什么吗

cloud-init实现自动扩展 磁盘分区_cloud-init 扩展-程序员宅基地

文章浏览阅读7k次。背景说明cloud-init 的一项功能是自动扩展linux的指定分区。比如linux镜像是20G,在部署instance时选择的flavor磁盘定义是40G,那么instance部署时cloud-init会自动将制定分区扩到 40G。 环境准备1) 该功能依赖growpart,所以需要在开始前,在镜像中安装包: yum install –y cloud-utils-gro..._cloud-init 扩展

推荐文章

热门文章

相关标签