hywang.me

Go 并发 map 到底该用哪个

#golang #go #map #concurrentmap #cache #in-memory-cache

Go 内置的 map 不是并发安全的 -- 多个 goroutine 同时读写会直接 panic：

fatal error: concurrent map writes

Google 一下解决方案，常见的有四种：

  • mutex：一把 sync.Mutex 保护整个 map。最简单。
  • rwmutex：sync.RWMutex，读并发、写独占。
  • syncmap：标准库自带的 sync.Map。
  • sharded map：分片锁。把 key 空间切成 256 份，每片一把 sync.Mutex。

到底哪个最快？我跑了一遍 benchmark，结果跟直觉有重大出入：比如 mutex 越多核越慢，RWMutex 只在纯读时勉强能打。

TL;DR：直接用分片锁。绝大多数场景下 sharded map 都是最优解，就算在读非常密集场景下也没有明显差距。RWMutex 是个陷阱 -- 只要写占到 10%，多核性能就跟 Mutex 差不多，别用。

下面是完整数据。

测试结果

下图是 benchmark 的结果，是在 M2 Pro 10 核（6 个性能核 + 4 个效率核）配置下，针对 1/2/4/8 个核心，分别在纯读、读 90%、读 50% 和读 10% 的情况下进行的测试。

提示：图小的话，右键在新 Tab 打开查看。

bench grid

下面是单核和 8 核下的吞吐量（Mops/s，越大越好）：

单核 Mops/s r100 r90 r50 r10
mutex 8.78 7.82 7.98 6.75
rwmutex 8.89 8.57 7.57 6.71
syncmap 3.78 3.06 1.94 1.60
sharded 7.75 7.38 6.37 5.80
8 核 Mops/s r100 r90 r50 r10
mutex 3.03 2.92 2.83 2.79
rwmutex 7.10 4.73 4.45 2.94
syncmap 25.06 19.52 13.35 10.25
sharded 35.17 26.48 24.69 22.15

从结果可以看出几件事：mutex 核越多越慢；RWMutex 只在纯读时能打；sharded 全场领先，写多时甚至是 mutex 的 8 倍。下面一个一个讲。

mutex 核越多越慢？

从 4 张图都能看到，mutex 在核数增加时性能反而下降。单核 8.78 Mops/s，8 核只剩 3.03 -- 8 倍的核换来 65% 的性能倒退。

原因很直接：所有 goroutine 都在抢同一把锁。1 个 goroutine 拿到锁，剩下 7 个都在等。核加得越多，队伍越长，抢锁的开销比 map 操作本身还大。这个是典型的负扩展（negative scaling）。

对 mutex 来说，map 操作的“并发”其实只是一个假象 -- 它只保证了并发安全，没有保证并发性能。所有 goroutine 的 map 访问都会被串行化，多核带来的只有争锁开销，不带来任何并行收益。

rwmutex 陷阱

这是全场最反直觉的发现。

大多数人下意识觉得“读多写少用 RWMutex”，因为它允许多个读操作并发进行。但数据显示，只要写操作占到 10%，RWMutex 的性能就会塌方：

  • 100% 读：8 核 7.10 Mops/s，勉强能看
  • 90% 读、10% 写：8 核 4.73 Mops/s，性能砍了 33%
  • 10% 读、90% 写：8 核 2.94 Mops/s，跟裸 Mutex 几乎一样

10% 的写就能让“读并发”的优势荡然无存。为什么？

sync.RWMutex 内部维护着一个共享的 reader 计数器（atomic.Int32），用来记录当前有多少个 reader 活跃。每次 RLock/RUnlock 都要原子地修改这个计数器 -- 多核并发下，这个计数器本身成了新的争用点。 其次还有个 cache line 效应。细节就不赘述了，也会降低 RWMutex 的性能。

而且写线程只要偶尔进来一次，就会阻塞所有读线程。 所以“读多写少”里，虽然写很少，但是就是这点写，成了压垮 RWMutex 的稻草。

受限的 sync.Map

从 Go 的官方文档中就能发现，sync.Map 只在两种情况下推荐使用：

  1. 写一次，读多次。也就是写极少、读极多的情况。
  2. map 中的 key 很分散，多个 goroutine 各自访问自己的 key（互不重叠）。

上面的 benchmark 场景两个都不满足 -- 每次操作都随机读写 100 万个 key 中的一个，读写混合。这解释了为什么 sync.Map 单核最慢（3.78 Mops/s），只有多核纯读时才能追上 -- 它的舒适区就那么大。

那么，真正需要"读多写少"高性能的场景用什么？看下面。

sharded map 全场碾压

sharded 是唯一一个核越多越快的方案（仅限当前4个方案，copy-on-write 等等的不在考虑范围）：

  • 单核 7.7 Mops/s → 8 核 35.2 Mops/s，接近 4.5 倍加速
  • 8 核纯读时是 mutex 的 12 倍
  • 就算写占 90%（r10），也有 22 Mops/s -- 比 mutex 快 8 倍

sharded map 有什么秘密么？

其实没什么秘密 -- 就一个思路：别让所有 goroutine 抢同一把锁。

一把大锁最大的问题就是它是个瓶颈。sharded 的做法很朴素 -- 把一个 map 切成 256 份小 map，每份自己一把锁。通过 hash 把 key 打散到不同的 shard 里面：

shardIndex = hash(key) & 255

一个 goroutine 操作 key “foo” 时，只锁住 “foo” 所在的那一份 shard，另外 255 份完全不受影响。8 个 goroutine 大概率落在 8 个不同的 shard 里， 各自锁自己的，互不打扰 -- 并行度直接从 1 拉到 8。

代码也不复杂，核心就这些：

const (
	numShards = 256           
	shardMask = numShards - 1
)

type shard[K comparable, V any] struct {
	mu sync.Mutex
	m  map[K]V
	_  [48]byte
}

type ShardedMap[K comparable, V any] struct {
	shards [numShards]shard[K, V]
	seed   maphash.Seed
}

func (s *ShardedMap[K, V]) at(k K) *shard[K, V] {
	return &s.shards[maphash.Comparable(s.seed, k)&shardMask]
}

func (s *ShardedMap[K, V]) Load(k K) (V, bool) {
	sh := s.at(k)
	sh.mu.Lock()
	v, ok := sh.m[k]
	sh.mu.Unlock()
	return v, ok
}

func (s *ShardedMap[K, V]) Store(k K, v V) {
	sh := s.at(k)
	sh.mu.Lock()
	sh.m[k] = v
	sh.mu.Unlock()
}

思路简单，效果很好。下面有两个细节需要说一下。

为什么用 256 个分片？

256 是一个经验值，选它有几个原因：

  • 够多，避免碰撞。8 个 goroutine 打到 256 个 shard，撞到同一个 shard 的概率不到 3%。就算撞了，也只影响那对 goroutine，其他 6 个 照跑不误。

  • 是 2 的幂。这样可以用位运算 & 255 代替取模 % 256 -- 位运算比整数除法快好几倍。代码里的 & shardMask 就是这个套路。

  • 又不算太多。每个 shard 一个 mutex + 一个 map + padding，大约 100 字节。256 个 shard 一共也就 25KB 左右 -- 能塞进 L1/L2 cache。分得太多（1024、4096）反而浪费内存。

  • 其他数字也可以，只是这个平衡点最好。orcaman/concurrent-map 用 32， Java 老版本 ConcurrentHashMap 默认 16 -- 分片数量本身不是玄学，按你的并发预期挑就可以。

padding 是干什么的？

你可能注意到 shard 末尾有一个 [48]byte 的匿名字段：

type shard[K comparable, V any] struct {
  mu sync.Mutex
  m  map[K]V
  _  [48]byte
}

这 48 字节不存任何数据，就是把 shard 撑到 64 字节——正好是 CPU 一条 cache line 的大小。

CPU 从内存读数据是按 cache line 读的，一次 64 字节。 如果两个 shard 挨在一起、共享同一条 cache line，那即使两个 goroutine 分别锁两个不同的 shard，操作也会互相触发 cache invalidation -- 一个核写完那条 cache line，另一个核就得重新从主存读一遍。加了 padding 之后，每个 shard 独占一条 cache line，两个 goroutine 锁不同 shard 时物理上不干扰，性能才能真正随核数扩展。 一个小细节，能带来 20-30% 的性能差别。

结论

跑完这一轮 benchmark，我的选型建议是：

  • 默认用 sharded map。读、写、混合都最快，代码几十行，没啥好犹豫的。
  • 不用 RWMutex 除非你能保证读操作占绝大多数。只要写占到 10%，它就跟 mutex 差不多 -- 用 mutex 都比它省心。
  • 单核或低并发用 sync.Mutex 就够，简单可靠。
  • sync.Map 只在写一次读千次、或每个 goroutine 各操作自己那份 key 时值得考虑。

注意： 本文是在随机读写的前提下进行的测试。如果是有 Hotkey 的情况下，是另外一个故事了。不过需要说的是，就算在有 Hotkey 的情况下使用 sharded map 也是没有问题的。它不会比 Mutex 的方案更好，但是也不会更差。

我把这个 sharded map 打包成了一个开箱即用的 Go 库：

https://github.com/swahpy/hykit/tree/main/cmap

支持泛型 key/value，只依赖标准库，MIT协议。除了基础的 Load/Store/Delete，还有 LoadOrStore、LoadAndDelete、Compute 三个原子的组合方法 -- 这几个方法背后还有一些有意思的坑（比如 sync.Map 上的 Compute 怎么做才真正原子），感兴趣的可以看看。