Golang sync.Map原理深入分析讲解

目录
  • GO语言内置的map
  • sync.Map
  • sync.Map原理分析
    • sync.Map的结构
    • 查找
    • 新增和更新
    • 删除

GO语言内置的map

go语言内置一个map数据结构,使用起来非常方便,但是它仅支持并发的读,不支持并发的写,比如下面的代码:

在main函数中开启两个协程同时对m进行并发读和并发写,程序运行之后会报错:

package main
func main()  {
	m := make(map[int]int)
	go func()  {
		for {
			_ = m[1]
		}
	}()
	go func()  {
		for {
			m[2] = 2
		}
	}()
	select {}
}

改进

既然不可以并发的写,我们可以给map加一个读写锁,这样就不会有并发写冲突的问题了:

import "sync"
func main() {
	m := make(map[int]int)
	var lock sync.RWMutex
	go func() {
		for {
			lock.RLock()
			_ = m[1]
			lock.RUnlock()
		}
	}()
	go func() {
		for {
			lock.Lock()
			m[2] = 2
			lock.Unlock()
		}
	}()
	select {}
}

这种方式的实现非常简洁,但也存在一些问题,比如在map的数据非常大的情况下,一把锁会导致大并发的客户端共争一把锁。

sync.Map

sync.Map是官方在sync包中提供的一种并发map,使用起来非常简单,和普通map相比,只有遍历的方式有区别:

package main
import (
	"fmt"
	"sync"
)
func main() {
	var m sync.Map
	// 1. 写入
	m.Store("apple", 1)
	m.Store("banana", 2)
	// 2. 读取
	price, _ := m.Load("apple")
	fmt.Println(price.(int))
	// 3. 遍历
	m.Range(func(key, value interface{}) bool {
		fruit := key.(string)
		price := value.(int)
		fmt.Println(fruit, price)
		return true
	})
	// 4. 删除
	m.Delete("apple")
	// 5. 读取或写入
	m.LoadOrStore("peach", 3)
}

sync.Map是通过 read 和 dirty 两个字段将读写分离,读的数据存在只读字段 read 上,将最新写入的数据则存在 dirty 字段上。

读取时会先查询 read,不存在再查询 dirty,写入时则只写入 dirty。

读取 read 并不需要加锁,而读或写 dirty 都需要加锁,另外有 misses 字段来统计 read 被穿透的次数(被穿透指需要读 dirty 的情况),超过一定次数则将 dirty 数据同步到 read 上,对于删除数据则直接通过标记来延迟删除。

在map + 锁的基础上,它有着几个优化点:

  • 空间换时间。 通过冗余的两个数据结构(read、dirty),实现加锁对性能的影响。
  • 使用只读数据(read),避免读写冲突。
  • 动态调整,miss次数多了之后,将dirty数据提升为read。
  • double-checking。
  • 延迟删除。 删除一个键值只是打标记,只有在提升dirty的时候才清理删除的数据。
  • 优先从read读取、更新、删除,因为对read的读取不需要锁。

sync.Map原理分析

sync.Map的结构

sync.Map的实现在src/sync/map.go中,首先来看Map结构体:

type Map struct {
    // 当涉及到脏数据(dirty)操作时候,需要使用这个锁
    mu Mutex
    // read是一个只读数据结构,包含一个map结构,
    // 读不需要加锁,只需要通过 atomic 加载最新的指正即可
    read atomic.Value // readOnly
    // dirty 包含部分map的键值对,如果操作需要mutex获取锁
    // 最后dirty中的元素会被全部提升到read里的map去
    dirty map[interface{}]*entry
    // misses是一个计数器,用于记录read中没有的数据而在dirty中有的数据的数量。
    // 也就是说如果read不包含这个数据,会从dirty中读取,并misses+1
    // 当misses的数量等于dirty的长度,就会将dirty中的数据迁移到read中
    misses int
}

上述结构体中的read字段实际上是一个包含map的结构体,该结构体中的map是一个read map,对该map的访问不需要加锁,但是增加的元素不会被添加到这个map中,元素会被先增加到dirty中,后续才会被迁移到read只读map中。

readOnly结构体中还有一个amended字段,该字段是一个标志位,用来表示read map中的数据是否完整。假设当前要查找一个key,会先去read map中找,如果没有找到,会判断amended是否为true,如果为true,说明read map的数据不完整,需要去dirty map中找。

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
    // m包含所有只读数据,不会进行任何的数据增加和删除操作
    // 但是可以修改entry的指针因为这个不会导致map的元素移动
    m       map[interface{}]*entry
    // 标志位,如果为true则表明当前read只读map的数据不完整,dirty map中包含部分数据
    amended bool // true if the dirty map contains some key not in m.
}

entry

readOnly.mMap.dirty存储的值类型是*entry,它包含一个指针p, 指向用户存储的value值,结构如下:

type entry struct {
    p unsafe.Pointer // *interface{}
}

其中p对应着三种值:

  • p == nil: 键值已经被删除,且 m.dirty == nil,这个时候dirty在等待read的同步数据。
  • p == expunged: 键值已经被删除,但 m.dirty!=nil 且 m.dirty 不存在该键值(dirty已经得到了read的数据同步,原来为nil的值已经被标记为了expunged没有被同步过来)。
  • 除以上情况,则键值对存在,存在于 m.read.m 中,如果 m.dirty!=nil 则也存在于 m.dirty

下面是sync.Map的结构示意图:

查找

查找元素会调用Load函数,该函数的执行流程:

  • 首先去read map中找值,不用加锁,找到了直接返回结果。
  • 如果没有找到就判断read.amended字段是否为true,true说明dirty中有新数据,应该去dirty中查找,开始加锁。
  • 加完锁以后又去read map中查找,因为在加锁的过程中,m.dirty可能被提升为m.read。
  • 如果二次检查没有找到key,就去m.dirty中寻找,然后将misses计数加一。
// src/sync/map.go
// 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) {
    // 首先从只读ready的map中查找,这时不需要加锁
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    // 如果没有找到,并且read.amended为true,说明dirty中有新数据,从dirty中查找,开始加锁了
    if !ok && read.amended {
        m.mu.Lock() // 加锁
       // 又在 readonly 中检查一遍,因为在加锁的时候 dirty 的数据可能已经迁移到了read中
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        // read 还没有找到,并且dirty中有数据
        if !ok && read.amended {
            e, ok = m.dirty[key] //从 dirty 中查找数据
            // 不管m.dirty中存不存在,都将misses + 1
            // missLocked() 中满足条件后就会把m.dirty中数据迁移到m.read中
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load()
}

misses计数

misses计数是有上限的,如果misses次数达到m.dirty的长度,就开始迁移数据,程序会直接将m.dirty提升为m.read,然后将m.dirty置为nil,等到下次插入新数据的时候,程序才会把read map中的值全部复制给dirty map。

// src/sync/map.go
func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {//misses次数小于 dirty的长度,就不迁移数据,直接返回
        return
    }
    m.read.Store(readOnly{m: m.dirty}) //开始迁移数据
    m.dirty = nil   //迁移完dirty就赋值为nil
    m.misses = 0  //迁移完 misses归0
}

新增和更新

新增或者更新元素会调用Store函数,该函数的前面几个步骤与Load函数是一样的:

  • 首先去read map中找值,不用加锁,找到了直接调用tryStore()函数更新值即可。
  • 如果没有找到就开始对dirty map加锁,加完锁之后再次去read map中找值,如果存在就判断该key对应的entry有没有被标记为unexpunge,如果没有被标记,就直接调用storeLocked()函数更新值即可。
  • 如果在read map中进行二次检查还是没有找到key,就去dirty map中找,找到了直接调用storeLocked()函数更新值。
  • 如果dirty map中也没有这个key,说明是新加入的key,首先要将read.amended标记为true,然后将read map中未删除的值复制到dirty中,最后向dirty map中加入这个值。
// src/sync/map.go
// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
   // 直接在read中查找值,找到了,就尝试 tryStore() 更新值
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }
    // m.read 中不存在
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        if e.unexpungeLocked() { // 未被标记成删除,前面讲到entry数据结构时,里面的p值有3种。1.nil 2.expunged,这个值含义有点复杂,可以看看前面entry数据结构 3.正常值
            m.dirty[key] = e // 加入到dirty里
        }
        e.storeLocked(&value) // 更新值
    } else if e, ok := m.dirty[key]; ok { // 存在于 dirty 中,直接更新
        e.storeLocked(&value)
    } else { // 新的值
        if !read.amended { // m.dirty 中没有新数据,增加到 m.dirty 中
            // 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中复制未删除的数据
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        m.dirty[key] = newEntry(value) //将这个entry加入到m.dirty中
    }
    m.mu.Unlock()
}

在Store函数中我们用到了两个用于更新值的函数:tryStore以及storeLockedtryStore函数是先判断p有没有被标记为expunged(软删除),如果被标记了就直接返回false,如果没有被标记,就将p指向的值进行更新然后返回true。

storeLocked函数是直接将p指向的值进行更新。

// 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
		}
	}
}
// storeLocked unconditionally stores a value to the entry.
//
// The entry must be known not to be expunged.
func (e *entry) storeLocked(i *interface{}) {
	atomic.StorePointer(&e.p, unsafe.Pointer(i))
}

将read map中的值复制到dirty map中:

m.dirtyLocked()函数用于将read map中的值复制到dirty map中:

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 {
		// 判断值是否被删除,被标记为expunged的值不会被复制到read map中
		if !e.tryExpungeLocked() {
			m.dirty[k] = e
		}
	}
}
// expunged实际上是一个指向空接口的unsafe指针
var expunged = unsafe.Pointer(new(interface{}))
func (e *entry) tryExpungeLocked() (isExpunged bool) {
	p := atomic.LoadPointer(&e.p)
	// 如果p为nil,就会被标记为expunged
	for p == nil {
		if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
			return true
		}
		p = atomic.LoadPointer(&e.p)
	}
	return p == expunged
}

下面是对sync.Map进行读写操作的示意图,正常读写且read map中有数据,程序只会访问read map,而不会去加锁:

删除

删除会调用Delete函数,该函数的步骤如下:

  • 首先去read map中找key,找到了就调用e.delete()函数删除。
  • 如果在read map中没有找到值就开始对dirty map加锁,加锁完毕之后再次去read map中查找,找到了就调用e.delete()函数删除。
  • 如果二次检查都没有找到key(说明这个key是被追加之后,还没有提升到read map中就要被删除),就去dirty map中删除这个key。
// src/sync/map.go
// Delete deletes the value for a key.
func (m *Map) Delete(key interface{}) {
    // 从 m.read 中开始查找
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended { // m.read中没有找到,并且可能存在于m.dirty中,加锁查找
        m.mu.Lock() // 加锁
        read, _ = m.read.Load().(readOnly) // 再在m.read中查找一次
        e, ok = read.m[key]
        if !ok && read.amended { //m.read中又没找到,amended标志位true,说明在m.dirty中
            delete(m.dirty, key) // 删除
        }
        m.mu.Unlock()
    }
    if ok { // 在 m.read 中就直接删除
        e.delete()
    }
}
func (e *entry) delete() (hadValue bool) {
	for {
		p := atomic.LoadPointer(&e.p)
		// 已标记为删除
		if p == nil || p == expunged {
			return false
		}
		// 原子操作,e.p标记为nil,GO的GC会将对象自动删除
		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
			return true
		}
	}
}

key究竟什么时候会被删除

我们可以发现,如果read map中存在待删除的key时,程序并不会去直接删除这个key,而是将这个key对应的p指针指向nil。

在下一次read -> dirty的同步时,指向nil的p指针会被标记为expunged,程序不会将被标记为expunged的 key 同步过去。

等到再一次dirty -> read同步的时候,read会被dirty直接覆盖,这个时候被标记为expunged的key才真正被删除了,这就是sync.Map的延迟删除。

到此这篇关于Golang sync.Map原理深入分析讲解的文章就介绍到这了,更多相关Golang sync.Map内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • golang中sync.Map并发创建、读取问题实战记录

    背景: 我们有一个用go做的项目,其中用到了zmq4进行通信,一个简单的rpc过程,早期远端是使用一个map去做ip和具体socket的映射. 问题 大概是这样 struct SocketMap { sync.Mutex sockets map[string]*zmq4.Socket } 然后调用的时候的代码大概就是这样的: func (pushList *SocketMap) push(ip string, data []byte) { pushList.Lock() defer pushLi

  • golang中使用sync.Map的方法

    背景 go中map数据结构不是线程安全的,即多个goroutine同时操作一个map,则会报错,因此go1.9之后诞生了sync.Map sync.Map思路来自java的ConcurrentHashMap 接口 sync.map就是1.9版本带的线程安全map,主要有如下几种方法: Load(key interface{}) (value interface{}, ok bool) //通过提供一个键key,查找对应的值value,如果不存在,则返回nil.ok的结果表示是否在map中找到值

  • React Hooks核心原理深入分析讲解

    目录 Hooks 闭包 开始动手实现 将useState应用到组件中 过期闭包 模块模式 实现useEffect 支持多个Hooks Custom Hooks 重新理解Hooks规则 React Hooks已经推出一段时间,大家应该比较熟悉,或者多多少少在项目中用过.写这篇文章简单分析一下Hooks的原理,并带大家实现一个简易版的Hooks. 这篇写的比较细,相关的知识点都会解释,给大家刷新一下记忆. Hooks Hooks是React 16.8推出的新功能.以这种更简单的方式进行逻辑复用.之前

  • 一文解析 Golang sync.Once 用法及原理

    目录 前言 1. 定位 2. 对外接口 3. 实战用法 3.1 初始化 3.2 单例模式 3.3 关闭channel 4. 原理 5. 避坑 前言 在此前一篇文章中我们了解了 Golang Mutex 原理解析,今天来看一个官方给出的 Mutex 应用场景:sync.Once. 1. 定位 Once is an object that will perform exactly one action. sync.Once 是 Go 标准库提供的使函数只执行一次的实现,常应用于单例模式,例如初始化配

  • GoLang并发机制探究goroutine原理详细讲解

    目录 1. 进程与线程 2. goroutine原理 3. 并发与并行 3.1 在1个逻辑处理器上运行Go程序 3.2 goroutine的停止与重新调度 3.3 在多个逻辑处理器上运行Go程序 通常程序会被编写为一个顺序执行并完成一个独立任务的代码.如果没有特别的需求,最好总是这样写代码,因为这种类型的程序通常很容易写,也很容易维护.不过也有一些情况下,并行执行多个任务会有更大的好处.一个例子是,Web 服务需要在各自独立的套接字(socket)上同时接收多个数据请求.每个套接字请求都是独立的

  • Golang 语言map底层实现原理解析

    在开发过程中,map是必不可少的数据结构,在Golang中,使用map或多或少会遇到与其他语言不一样的体验,比如访问不存在的元素会返回其类型的空值.map的大小究竟是多少,为什么会报"cannot take the address of"错误,遍历map的随机性等等. 本文希望通过研究map的底层实现,以解答这些疑惑. 基于Golang 1.8.3 1. 数据结构及内存管理 hashmap的定义位于 src/runtime/hashmap.go 中,首先我们看下hashmap和buck

  • GoLang的sync.WaitGroup与sync.Once简单使用讲解

    目录 一.sync.WaitGroup的简单实用 Add方法 Done方法 Wait方法 二.sync.WaitGroup类型值中计数器的值可以小于0吗 三.sync.Once 用法 sync.Once类型中的uint32类型的字段 Do方法的功能特点 一.sync.WaitGroup的简单实用 在之前,我们使用通道,来主goroutine中等待其他goroutine执行完成: func coordinateWithChan() { sign := make(chan struct{}, 2)

  • Java HashMap源码深入分析讲解

    1.HashMap是数组+链表(红黑树)的数据结构. 数组用来存放HashMap的Key,链表.红黑树用来存放HashMap的value. 2.HashMap大小的确定: 1) HashMap的初始大小是16,在下面的源码分析中会看到. 2)如果创建时给定大小,HashMap会通过计算得到1.2.4.8.16.32.64....这样的二进制位作为HashMap数组的大小. //如何做到的呢?通过右移和或运算,最终n = xxx11111.n+1 = xx100000,2的n次方,即为数组大小 s

  • React中Redux核心原理深入分析

    目录 一.Redux是什么 二.Redux的核心思想 三.Redux中间件原理 四.手写一个Redux 总结 一.Redux是什么 众所周知,Redux最早运用于React框架中,是一个全局状态管理器.Redux解决了在开发过程中数据无限层层传递而引发的一系列问题,因此我们有必要来了解一下Redux到底是如何实现的? 二.Redux的核心思想 Redux主要分为几个部分:dispatch.reducer.state. 我们着重看下dispatch,该方法是Redux流程的第一步,在用户界面中通过

  • 深度解密 Go 语言中的 sync.map

    工作中,经常会碰到并发读写 map 而造成 panic 的情况,为什么在并发读写的时候,会 panic 呢?因为在并发读写的情况下,map 里的数据会被写乱,之后就是 Garbage in, garbage out,还不如直接 panic 了. 是什么 Go 语言原生 map 并不是线程安全的,对它进行并发读写操作的时候,需要加锁.而 sync.map 则是一种并发安全的 map,在 Go 1.9 引入. sync.map 是线程安全的,读取,插入,删除也都保持着常数级的时间复杂度. sync.

随机推荐