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{}
}
read map
是一个只读的 map,不能往里面添加 key,而dirty map
是一个可读写的map
,可以往里面添加 key- 首先从
read map
中查找 key,如果没有找到,再加锁从dirty map
中查找 key,然后根据查找结果进行后续的操作
实现 #
Load #
- 首先查询 read map,如果 read map 存在则直接返回
- 如果 read map 不存在,则查询 dirty map,并将 miss++
- 如果 miss 达到 len(ditryMap) 时,则将 dirty map 升级为 read map,并将 miss 置零
LoadOrStore #
- 在 read map 中查找,尝试 load 和 store,操作成功则直接返回
- read map 中不存在则加锁,并 double check,然后在 dirty map 中 load 或 store,并将 miss++
- 如果 dirty map 中不存在,则在 dirty map 中写入 key 和 val。如果 dirty map 为 nil,则先进行初始化,然后将 read map 的 amended 修改为 true