Skip to main content
  1. Docs/

Golang sync.Map

·4 mins· ·
Golang Golang
Owl Dawn
Author
Owl Dawn
A little bit about you
Table of Contents

Golang sync.Map
#

在Go 1.6 之前, 内置的map类型是部分 goroutine 安全的,并发的读没有问题,并发的写可能有问题。自 go 1.6 之后, 并发地读写 map 会报错,这在一些知名的开源库中都存在这个问题,所以go 1.9 之前的解决方案是额外绑定一个锁,封装成一个新的struct或者单独使用锁都可以。

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

以上代码会循环读写不同的键值,即使读取和写入的不是同一个键,不会有扩容操作,依然会报错 fatal error: concurrent map read and map write

golang 1.9 之前的简便解决方案,使用读写锁

var counter = struct{
    sync.RWMutex
    m map[string]int
}{m: make(map[string]int)}

// 读取数据
counter.RLock()
n := counter.m["some_key"]
counter.RUnlock()
fmt.Println("some_key:", n)

// 写数据
counter.Lock()
counter.m["some_key"]++
counter.Unlock()

在 map 的数据非常大的情况下,一把锁会导致大并发的客户端共争一把锁,Java 的解决方案是 shard, 内部使用多个锁,每个区间共享一把锁,这样减少了数据共享一把锁带来的性能影响。concurrent-map 就采用分段的方式,使用 Segment 来实现减小锁粒度,把 Map 分割成若干个 Segment,在 put 的时候需要加读写锁,get 时候只加读锁。详见 concurrnet-map

type ConcurrentMap []*ConcurrentMapShared

type ConcurrentMapShared struct {
	items        map[string]interface{}
	sync.RWMutex // 读写锁,保证进入内部 map 的线程安全
}

var SHARD_COUNT = 32

func New() ConcurrentMap {
	m := make(ConcurrentMap, SHARD_COUNT)
	for i := 0; i < SHARD_COUNT; i++ {
		m[i] = &ConcurrentMapShared{items: make(map[string]interface{})}
	}
	return m
}

无锁方案
#

在 Go 1.9 的版本中默认就实现了一种线程安全的 Map,摒弃了 Segment(分段锁)的概念,而是利用了 CAS,即 Lock - Free 方案。

注意:sync.Map 在第一次使用后,不允许再被拷贝。因为对结构体的复制不但会生成该值的副本,还会生成其中字段的副本。如此一来,本应施加于此的并发线程安全保护也就失效了。

数据结构
#

type Map struct {
    // 当涉及到 dirty 数据的操作的时候,需要使用这个锁
    mu Mutex
    // 一个只读的数据结构,因为只读,所以不会有读写冲突。
    // 所以从这个数据中读取总是安全的。
    // 实际也会更新这个数据的 entries,如果 entry 是未删除的(unexpunged), 则不需要加锁。如果 entry 已经被删除了,需要加锁,以便更新dirty数据。
    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
}

type readOnly struct { // 主要用于存储,通过原子操作存储在 Map.read 中元素
    m       map[interface{}]*entry
    // 如果数据在 dirty 中但没有在 read 中,该值为 true,作为修改标识
    // amended 指明 Map.dirty 中有 readOnly.m 未包含的数据,所以如果从 Map.read 找不到数据的话,还要进一步到 Map.dirty 中查找
    amended bool
}

type entry struct {
    // nil: 表示为被删除,调用 Delete() 可以将 read map 中的元素置为 nil
    // expunged: 也是表示被删除,但是该键只在 read 而没有在 dirty 中,这种情况出现在将 read 复制到 dirty 中,即复制的过程会先将 nil 标记为 expunged,然后不将其复制到dirty
    // 其他: 表示存着真正的数据
    p unsafe.Pointer // *interface{}
}

sync_map_1.png

  • read map 是一个只读的 map,不能往里面添加 key,而 dirty map 是一个可读写的 map,可以往里面添加 key
  • 首先从 read map 中查找 key,如果没有找到,再加锁从 dirty map 中查找 key,然后根据查找结果进行后续的操作

实现
#

Load
#

未命名文件 (1)
  1. 首先查询 read map,如果 read map 存在则直接返回
  2. 如果 read map 不存在,则查询 dirty map,并将 miss++
  3. 如果 miss 达到 len(ditryMap) 时,则将 dirty map 升级为 read map,并将 miss 置零

LoadOrStore
#

  1. 在 read map 中查找,尝试 load 和 store,操作成功则直接返回
  2. read map 中不存在则加锁,并 double check,然后在 dirty map 中 load 或 store,并将 miss++
  3. 如果 dirty map 中不存在,则在 dirty map 中写入 key 和 val。如果 dirty map 为 nil,则先进行初始化,然后将 read map 的 amended 修改为 true

参考
#

Related

Golang Channel
·5 mins
Golang Golang
containerd
·11 mins
Containerd Containerd
linux 文件系统
Linux Linux
redis
·19 mins
Redis