concurrent-map 和 sync.Map,我该选择哪个?

时间:2023-02-21 08:08:35

官方的map并不是线程安全的,如果我们在多线程中并发对一个map进行读写操作,是会引发panic的。解决方案除了使用锁来对map进行保护外,还有两种方式:

一,开源项目 concurrent-map 提供了可以用来做并发安全的map

二,Go1.9之后,标准库提供了一个sync.Map

这两种并发安全的map,我们应该怎么选择呢?

在concurrent-map我看到这么一段话:

标准库中的sync.Map是专为append-only场景设计的。因此,如果您想将Map用于一个类似内存数据库,那么使用我们的版本可能会受益。你可以在golang repo上读到更多,这里 and 这里 译注:sync.Map在读多写少性能比较好,否则并发性能很差

concurrent-map为什么会有这种表述呢?这篇文章就来庖丁解牛下。

concurrent-map

concurrent-map是Golang中一个流行的并发安全的哈希表库,它允许多个goroutine同时对哈希表进行读写操作,而不需要使用显式的锁或同步原语。

该库的核心原理是使用分片锁,将哈希表分成多个小的哈希表片段,并为每个片段分配一个独立的锁。当多个goroutine尝试同时读写同一个片段时,只有该片段上的锁会被锁住,而其他片段的锁则不受影响,从而避免了整个哈希表被锁住的情况。

当进行写操作时,只需要锁住要写入的片段的锁,以确保原子性操作。当进行读操作时,则不需要锁住片段的锁,只需要对该片段上的读取操作进行同步即可。

此外,concurrent-map库还使用了一些优化策略,如缓存哈希值和桶的地址,以减少计算和查找时间,从而提高并发读写性能。

总之,concurrent-map库的原理是基于分片锁和其他优化策略来实现高效的并发安全哈希表。

我们先看它的使用方式:

	// 创建一个新的 map.
	m := cmap.New[string]()

	// 设置变量m一个键为“foo”值为“bar”键值对
	m.Set("foo", "bar")

	// 从m中获取指定键值.
	bar, ok := m.Get("foo")

	// 删除键为“foo”的项
	m.Remove("foo")

它的New方法创建了一个ConcurrentMap结构

type ConcurrentMap[K comparable, V any] struct {
	shards   []*ConcurrentMapShared[K, V]
	sharding func(key K) uint32
}

我们看ConcurrentMap结构中的shards,是用来代表map分片之后的这些存储分片ConcurrentMapShared。

而sharing这个匿名函数代表的是分配的hash函数。

而存储分片是一个基础的,带有互斥锁的map

type ConcurrentMapShared[K comparable, V any] struct {
   items        map[K]V
   sync.RWMutex 
}

所以看到这里我们其实心里明白了个七七八八了,再看下它的New/Set/Get的流程如下:

flowchart LR cmap.New --> 创建一个ConcurrentMap --> 初始化ConcurrentMapShared cmap.Set --> 根据需要设置的key查找对应的ConcurrentMapShared --> 加锁写分片中的map cmap.Get --> 根据需要查找的key找出对应分片ConcurrentMapShared --> 加读锁读取分片中的map

是的,基本原理就是如上图所示。concurrent-map就是将一个大map拆分成若干个小map,然后用若干个小mutex 对这些小map进行保护。这样,通过降低锁的粒度提升并发程度。毕竟嘛,一个诸葛亮不如十个臭皮匠。

sync.Map

sync.Map是Golang标准库中提供的一个并发安全的哈希表,它与常规的map相比,可以在多个goroutine并发访问时,保证数据的安全性和一致性。

理解sync.Map,最关键就是理解Map结构。

type Map struct {
	mu Mutex //互斥锁,用于锁定dirty map

	//优先读map,支持原子操作,注释中有readOnly不是说read是只读,而是它的结构体。read实际上有写的操作
	read atomic.Value // readOnly

	// dirty是一个当前最新的map,允许读写
	dirty map[any]*entry

	// 主要记录read读取不到数据加锁读取read map以及dirty map的次数,当misses等于dirty的长度时,会将dirty复制到read
	misses int
}

这里的sync.Map的逻辑还是比较复杂的。我们再看它的Store函数和Load函数。

func (m *Map) Store(key, value any) 
func (m *Map) Load(key any) (value any, ok bool) 

我们先把Store的代码流程图画出来

flowchart TD Store-->判断read中是否有key{判断read中是否有key} 判断read中是否有key{判断read中是否有key}--有key-->在read中tryStore-->CompareAndSwapPointer-->原子替换read中对应指针 判断read中是否有key{判断read中是否有key}--没有key-->加锁-->判断key的位置 判断key的位置--在read中存在-->dirty中存入这对keyvalue-->read中原子替换指针-->解锁 判断key的位置--在read中不存在\n在dirty中存在-->dirty中原子替换指针-->解锁 判断key的位置--在read中不存在\n在dirty中不存在-->read中所有元素复制到dirty一份-->read中增加这个keyvalue-->dirty中增加这个keyvalue-->解锁

我们看下,这里面有几个步骤是非常有细节的。

首先,第一次判断read中是否有key的时候是没有加锁的,所以当第一次判断结束后,一旦明确read中没有key,要做后续的操作之前,先做一次加锁操作,做完加锁操作之后,又判断了一次key是否在read中。这是为什么呢?其实是由于在加锁这个操作的前后,map还是有可能有变化的,人不可能两次踏入同一个河流,map也不可能在加锁前后两次都不变,所以这里必须进行二次判断,这里可以说是非常细节了。

其次,在判断read或者dirty中已经有key的时候,Store做的操作不是复制一份value到目标结构,而是使用原子替换atomic.StorePointer 来将目标map中key对应的value指针替换为参数value。为什么呢? - 这是极致的性能优化写法,原子替换能减少一次值拷贝操作,做一次指针赋值就能替换拷贝内存操作。从这里我们也能理解为什么这个并发map会放在atomic包中,因为它的实现大量依赖atomic的原子操作。

同样,我们将Load的代码转化为流程图如下,

flowchart TD Load --> 判断read中是否有key{判断read中是否有key} 判断read中是否有key{判断read中是否有key}--有key-->直接返回对应的value 判断read中是否有key{判断read中是否有key}--没有key-->加锁-->再次判断read中是否有key{再次判断read中是否有key} 再次判断read中是否有key{再次判断read中是否有key} --有key-->直接返回对应的value 再次判断read中是否有key{再次判断read中是否有key} --没有key-->返回dirty中是否有key-->标记map的miss值加一-->如果miss值大于dirty的个数-->将dirty中的map通过指针切换到read-->dirty置空-->标记map的miss值为0

从Load中我们大致能看出sync.Map的思路。

sync.Map内部使用两个map,read和dirty。其实read的map的作用是挡在读写操作的第一个屏障。如果读写在这个read中能直接操作的话,我们就直接在read中读写,那么就可以完全避免使用锁,性能自然就提升了。

而dirty的作用就相当于是一个缓冲区,一旦要写的key在read中找不到,我们就会先写dirty中。这个好处是什么?也是不去影响读read的操作,不会出现并发读写一个数据结构的情况。

而什么时候dirty的缓存清空同步到read中呢?就是“当map的miss标记大于dirty的个数的时候”。

这里我读的时候也确实有这个疑问,为什么是“当miss标记个数大于dirty个数”。而不是当miss标记个数大于某个值呢?我是这么理解,miss是代表读操作在read中失效的数量,而dirty个数代表写操作在read中失效的数量。如果使用固定值来比对miss个数,那么这个固定值是不好定的,比如一个有10个key的map和一个有10000个key的map如果都是一样的固定值,那是明显不合适的。所以就找了这么个“浮动阈值”。

concurrent-map和sync.map的比较

我们再回到最开始的那一段话:

标准库中的sync.Map是专为append-only场景设计的。因此,如果您想将Map用于一个类似内存数据库,那么使用我们的版本可能会受益。你可以在golang repo上读到更多,这里 and 这里 译注:sync.Map在读多写少性能比较好,否则并发性能很差

通过以上的代码分析,我们看出sync.Map的这个机制,是一个想追求无锁读写的结构,它最好的运行方式是读永远都命中read,写只命中dirty,这用能不用任何锁机制就能做到map读写。而它最差的运行状态是read和dirty不断做替换和清理动作,性能就无法达到预期。而什么时候可能出现最差运行状态呢?- 大量的写操作和大量的读操作。大量读写会导致“map的miss标记大于dirty的个数”。 这个时候sync.Map中第一层屏障会失效,dirty就会频繁变动。

而current-map就相当于是一个比较中等中规中矩的方案。它的每次读写都会用到锁,只是这个锁的粒度比较小。它的最优运行方式是我们的所有并发读写都是分散在不同的hash切片中。它的最差运行方式就是我们所有的并发读写都集中在一个hash切片。但是按照实际运行逻辑,这两种极端情况都不会发生。

所以总结下来,concurrent-map 的这段话确实没有骗我们:

sync.Map在读多写少性能比较好,而concurrent-map 在key的hash度高的情况下性能比较好。

在无法确定读写比的情况下,建议使用 concurrent-map。

最后说一句:世上本没有烦恼,选择多了,便有了幸福的烦恼。

参考

https://segmentfault.com/a/1190000015242373