深入理解 Go 的 sync.Map：从 API 到哈希字典树

# 从 API 到哈希 Trie：理解 Go 的 sync.Map 来源：https://victoriametrics.com/blog/go-sync-map-hash-trie/index.html 本文是关于 Go 并发处理系列文章的一部分： - Go sync\.Mutex：正常模式与饥饿模式 (https://victoriametrics.com/blog/go-sync-mutex/) - Go sync\.WaitGroup 与对齐问题 (https://victoriametrics.com/blog/go-sync-waitgroup/) - Go sync\.Pool 及其背后机制 (https://victoriametrics.com/blog/go-sync-pool/) - Go sync\.Cond，最容易被忽视的同步机制 (https://victoriametrics.com/blog/go-sync-cond/) - Go sync\.Map：合适的工具用在合适的地方 (https://victoriametrics.com/blog/go-sync-map/) - 从 API 到哈希 Trie 理解 Go 的 sync\.Map（本文） - Go Sync\.Once 简单...果真如此吗？ (https://victoriametrics.com/blog/go-sync-once/) - Go Singleflight 融入你的代码，而非你的数据库 (https://victoriametrics.com/blog/go-singleflight/) 自我之前关于 sync\.Map 的文章 (https://victoriametrics.com/blog/go-sync-map/) 以来，`sync\.Map` 已经发生了变化。其公共 API 保持不变，但 Go 1\.24 将其默认实现更改为实验性的哈希 Trie。 Go 1\.26 移除了实验性标志，使哈希 Trie 成为标准库中`sync\.Map`的官方实现。 我们将从头开始讨论当前的实现，因此您无需先阅读旧文章。我们将从普通 map 构建一切，直至`sync\.Map`背后的设计。如果您已经了解其设置，可以跳过这些部分。 ## 1. 从普通 Go map 开始 ## \# (https://victoriametrics.com/blog/go-sync-map-hash-trie/index.html#1-start-with-a-normal-go-map)### map 如何找到键 ### \# (https://victoriametrics.com/blog/go-sync-map-hash-trie/index.html#how-a-map-finds-a-key)在探讨`sync\.Map`之前，我们需要了解所有 map 实现共有的一部分：map 如何从其存储的所有内容中找到 1 个键。 普通的 Go map 为我们提供了最简单的起点： `` m := map[string]int{} m["cat"] = 31 m["dog"] = 28 value, ok := m["cat"] fmt.Println(value, ok) // 31 true ``` 查找很简单：在 map 存储中找到`"cat"`键并取出其值。内部实现并非线性地检查和扫描每个键。随着 map 增长（可能包含数千个其他键），这种方法会使每次查找都做更多工作。 相反，查找首先对键应用哈希函数： 将键哈希到固定宽度的整数。 将键哈希到固定宽度的整数。在 32 位架构上，哈希结果有 32 位；在 64 位架构上有 64 位。本文中我们使用 64 位示例。 例如，前 4 个哈希位可以将搜索范围缩小到`"dog"`和`"cat"`键： 哈希查找与相等性检查。 哈希查找与相等性检查。在该存储区域内部，进行相等性检查（`==`）比较实际键并确认精确匹配。 内置的`map\[K\]T`和`sync\.Map`都使用这种策略：使用哈希缩小搜索范围，然后比较实际键。它们以不同的方式组织存储，因此其查找代码并不相同。 ### 普通 map 对并发读写不安全 ### \# (https://victoriametrics.com/blog/go-sync-map-hash-trie/index.html#a-normal-map-is-not-safe-for-concurrent-read-and-write)普通 map 不同步 goroutine 之间的访问。此代码片段允许一个 goroutine 写入，同时另一个读取： `` func main() { m := map[string]int{} go func() { for { m["requests"]++ } }() go func() { for { fmt.Println(m["requests"]) } }() select {} } ``` 此代码片段存在数据竞争，可能以如下方式终止： `` fatal error: concurrent map read and map write ``` 原因是写操作可能更改 map 中查找也要读取的几个部分。它可能更新键或值，更改查找元数据和计数器，通过将条目复制到新存储中来增长 map 等。 读取者使用相同的存储和元数据来查找其键。没有同步机制，读取者可能在写入者正在更改这些部分时访问它们，因为写操作不是原子性的。 这也是为什么不能获取 map 条目地址的原因： `` p := &m["cat"] // invalid operation: cannot take address of m["cat"] ``` 没有稳定的地址可以提供。 标准的类型化解决方案是使用互斥锁保护的 map，无论是`sync\.Mutex`还是`sync\.RWMutex`： `` type Counters struct { mu sync.RWMutex m map[string]int } func (c *Counters) Load(key string) (int, bool) { c.mu.RLock() defer c.mu.RUnlock() v, ok := c.m[key] return v, ok } func (c *Counters) Store(key string, value int) { c.mu.Lock() defer c.mu.Unlock() c.m[key] = value } ``` 这通常是最好的设计。您保留具体的键和值类型，因此这里不需要类型断言。并且因为一个锁保护整个结构体，您可以一起更改多个条目，而不会让另一个 goroutine 看到半完成的状态。 相同的包装器可以作为泛型类型编写一次： `` type Map[K comparable, V any] struct { mu sync.RWMutex m map[K]V } ``` 局限性在于所有操作都通过同一个`sync\.RWMutex`协调。读锁可以与其他读锁并发运行，但写锁必须等待现有读锁，并排除所有其他操作。 外部锁定与内部锁定。 外部锁定与内部锁定。此设计使用一个锁保护整个 map，因此并发访问可能在该锁周围产生竞争。我们需要一种对锁进行分片的方法，这就是`sync\.Map`的用武之地。 ## 2. sync\.Map 提供了什么 ## \# (https://victoriametrics.com/blog/go-sync-map-hash-trie/index.html#2-what-syncmap-provides)`sync\.Map`提供了常见 map 操作的并发版本。多个 goroutine 可以调用`Load`、`Store`和`Delete`，而无需使用外部锁保护 map： `` var m sync.Map m.Store("cat", 31) value, ok := m.Load("cat") if ok { number := value.(int) fmt.Println(number) } m.Delete("cat") ``` `sync\.Map`具有有效的零值，因此我们可以立即声明和使用它，而无需初始化。但一旦使用过它，就不能复制它。另见 Go 如何使用 sync\.noCopy 检测结构体复制 (https://func25.dev/posts/go-sync-nocopy/)。 这种便利性伴随着类型信息的权衡。`sync\.Map`接受键和值为`any`类型，因此`Load`也返回一个`any`值。 我们通常需要在将其用作具体类型之前进行类型断言： `` m.Store("cat", 31) value, _ := m.Load("cat") number := value.(int) // value is any, so the type has to be restored ``` 键参数的类型为`any`，但作为键传递的值仍必须是可比较的。因此，切片在调用点可以编译，但当`sync\.Map`尝试哈希它时会 panic。 `` package main import "sync" func main() { var m sync.Map m.Store([]int{1, 2, 3}, "value") } ``` `` panic: runtime error: hash of unhashable type []int ``` 还有一个局限：`sync\.Map`不允许我们作为原子操作一起更新多个选定的键。 如果 2 个键必须一起更改，另一个 goroutine 可以在这些更改之间读取 map 并仅看到更新的一半。使用自己的互斥锁的普通`map\[K\]T`可以避免此问题，因为同一个锁可以保护两个更改。 标准库文档说大多数代码应该使用普通 map。不要每次需要带互斥锁的 map 时都使用`sync\.Map`。它推荐`sync\.Map`用于两种情况： - 一个条目只写一次，读取多次，例如只增长的缓存。 - 不同的 goroutine 主要使用不同的键。 ## 3. 在使用 sync\.Map 之前 ## \# (https://victoriametrics.com/blog/go-sync-map-hash-trie/index.html#3-before-you-reach-for-syncmap)`sync\.Map`可以从多个 goroutine 安全调用。这是容易的部分。与普通 map 相比，有几点不同，需要稍加注意。 以下是`sync\.Map`的主要方法： `` Load(key) // returns the value and whether the key was found Store(key, value) // stores the value under the key Delete(key) // removes the key and its value LoadOrStore(key, value) // returns the current value or stores the new value LoadAndDelete(key) // removes the key and returns its previous value Swap(key, value) // replaces the value and returns its previous value CompareAndSwap(key, old, new) // replaces old with new only when the current value equals old CompareAndDelete(key, old) // deletes the key only when the current value equals old Range(func(key, value any) bool) // calls the function for entries until it returns false Clear() // removes every entry ``` 您可能注意到`sync\.Map`没有`Len`方法。计算条目的唯一方法是使用`Range`遍历整个 map： `` n := 0 m.Range(func(key, value any) bool { n++ return true }) ``` 但`Range`不给我们快照。它遍历活跃结构，正如我们稍后将看到的。如果另一个 goroutine 在遍历期间存储或删除一个键，您可能看到也可能看不到该键，并且您获得的键的值可能来自遍历过程中的任何时刻。 关于使用普通`map\[K\]T`的`for range`或`sync\.Map`的`Range`方法时的键顺序，有一些有趣的细节。 每个`sync\.Map`在首次使用时选择一个随机哈希种子。该种子影响每个键的哈希，因此包含相同键的两个 map 可能在存储中放置它们的方式不同。普通的`map\[K\]T`使用相同的概念。 如果我们通过`Range`方法检查它们的顺序，可能如下所示： `` sync.Map #1: [6 3 5 1 2 4 0 7] sync.Map #2: [2 6 3 1 5 4 0 7] sync.Map #3: [6 5 1 0 2 4 7 3] ``` 这就是不同`sync\.Map`值之间顺序可能改变的原因。如果我们多次迭代同一个`sync\.Map`呢？`Range`的顺序仍然没有指定，就像普通 map 的顺序一样，但当前实现可以使其看起来稳定。 以下是`sync\.Map\.Range`与普通 map 遍历的比较： `` sync.Map [7 2 6 0 3 5 1 4] [7 2 6 0 3 5 1 4] [7 2 6 0 3 5 1 4] plain map [5 6 7 0 1 2 3 4] [3 4 5 6 7 0 1 2] [4 5 6 7 0 1 2 3] ``` 内置`map`为每次`range`循环选择随机起始偏移，因此其迭代顺序更可能改变。相比之下，`sync\.Map\.Range`总是遍历从 0 到 15 的子插槽。如果存储的结构没有改变，重复调用可以返回相同的顺序。 此行为不是`sync\.Map`契约的一部分。它是一个内部细节。插入、删除和并发更新可以更改`Range`读取哪些条目以及何时读取它们。我们永远不应编写依赖于任一 map 类型顺序的代码。 现在，每次调用本身是安全的，但`sync\.Map`不会将单独的调用转换为一个事务。如果`Clear`和`Store`同时运行，`Store`可能丢失。`Clear`通过交换一个新的空 map 来立即丢弃整个 map。 并发 Store 和 Clear。 并发 Store 和 Clear。如果`Store`先开始，它可能读取当前存储。`Clear`可以立即运行并将该存储替换为新的空存储。调用正常返回，但`Store`使用它已经读取的被丢弃的存储完成其写入。 `sync\.Map`通常比普通 map 需要更多内存。为衡量差异，我们在插入任何条目之前记录堆使用情况，然后在每个 map 中插入相同数量的`int`键和值后再次记录。 我们在每次测量之前运行 GC 以清除无关垃圾。减去初始堆大小后，我们得到每个填充的 map 大约增加的内存量： 每个 map 添加的堆内存。 每个 map 添加的堆内存。普通 map 将其`int`键和值一起存储在插槽数组中。在 100 万个条目时，这些数组使用 36\.1 MiB。`sync\.Map`为每个键值对有一个单独的对象，通过`any`存储两者，并构建包含子指针和互斥锁的 Trie 节点。这些分配使其总量达到 115\.9 MiB。 当然，两种 map 类型的确切成本也取决于键和值类型、条目数量和 Go 版本。在这些测量中，`sync\.Map`使用的内存大约是普通 map 的 3 到 5 倍。 公平地说，`sync\.Map`有两点值得考虑： 1. 它提供一次性原子操作，如`LoadOrStore`和`CompareAndSwap`。普通 map 需要我们自己在组合读写周围加锁。 2. 当共享互斥锁确实是瓶颈时，`sync\.Map`可以提供帮助，但我们应该先测量。并发安全性本身不是选择它的原因，因为互斥锁下的普通 map 也是安全的，并且通常导致更简单的代码。 ## 4. 公共类型现在非常小 ## \# (https://victoriametrics.com/blog/go-sync-map-hash-trie/index.html#4-the-public-type-is-now-very-small)我们现在已经从外部了解了全貌。本文的其余部分将打开`sync\.Map`并跟踪内部发生的情况。 公共类型是： `` package sync type Map struct { _ noCopy m isync.HashTrieMap[any, any] } ``` 第一个字段`\_ noCopy`仅存在于此，以便如果您意外复制了`sync\.Map`，`go vet`会警告您： `` var a sync.Map b := a // assignment copies lock value to b: sync.Map contains sync.noCopy ``` *另见 Go 如何使用 sync\.noCopy 检测结构体复制 (https://func25.dev/posts/go-sync-nocopy/)。* 第二个字段`m isync\.HashTrieMap\[any, any\]`是我们关心的。它持有 map 中的每个键和值，其类型是整个哈希 Trie 的所在。`isync`是`internal/sync`的别名。 `HashTrieMap`最初是为`unique`包创建的。后来，当 Go 计划将其重用于`sync\.Map`时，它被移至`internal/sync`。 现在，看看该字段背后的具体类型。它是一个泛型结构体： `` type HashTrieMap[K comparable, V any] struct { ... } ``` 因此内部类型可以持有具体的键和值类型。那么为什么`sync\.Map`将其实例化为`isync\.HashTrieMap\[any, any\]`？ 如果`sync\.Map`可以使用具体的键和值类型而不是`any`， - `Load`可以以其实际类型返回值，因此调用者不需要类型断言。 - Trie 也可以直接以这些类型存储键和值，而没有导致上述内存成本的接口装箱。 API 可能如下所示： `` var prices sync.Map[string, int] prices.Store("pizza", 9) price, ok := prices.Load("pizza") // price is an int ``` 问题在于`sync\.Map`是在 Go 拥有泛型之前添加的。Go 不能用`sync\.Map\[K, V\]`替换它，因为现有代码（如`var m sync\.Map`）将停止编译。这将违反 Go 1 兼容性承诺。 解决此问题有两种有趣的想法。 - 提议的`sync/v2` (https://github.com/golang/go/issues/71076)包将提供新的泛型 API。 - 关于默认类型参数的单独讨论 (https://github.com/golang/go/discussions/48287)考虑在未指定类型时使`sync\.Map`表示`sync\.Map\[any, any\]`。 回到`sync\.Map`。每个公共方法直接委托给内部 map： `` func (m *Map) Load(key any) (value any, ok bool) { return m.m.Load(key) } func (m *Map) Store(key, value any) { m.m.Store(key, value) } func (m *Map) Delete(key any) { m.m.Delete(key) } ``` 因此，理解当前的`sync\.Map`意味着理解`internal/sync\.HashTrieMap`。 在能够阅读该类型之前，我们需要知道什么是 Trie。 ## 5. 从 Trie 到哈希 Trie ## \# (https://victoriametrics.com/blog/go-sync-map-hash-trie/index.html#5-from-a-trie-to-a-hash-trie)Trie 将键分解为更小的部分，并为每个部分使用一个树级别。查找按顺序读取这些部分，并在每个级别选择一个子节点。在这里，每个部分是一个字符： 具有共享前缀的字符串 Trie。 具有共享前缀的字符串 Trie。要查找`"cat"`，查找读取`c`，然后是`a`，然后是`t`。要查找`"can"`，它读取`c`，然后是`a`，但由于第三个字符不匹配而失败。每个字符（或部分）决定了下一步应该检查哪个子节点，因此 Trie 可以快速定位键。 哈希 Trie 将此想法更进一步。键被哈希为整数，该整数的位被用作路径。我们无需在每个级别比较字符，而是读取哈希位来决定转向哪个子节点。 Trie 通过分片减少了键比较。在普通 map 中，每个键都可能不同，因此需要完整比较。在 Trie 中，许多键共享前缀，因此 Trie 只需要比较键的后缀。 哈希 Trie 添加了另一个优化。它不是在每个级别使用一个子节点，而是批量处理多个哈希位，以减少 Trie 的深度并增加其扇出。这减少了跟踪指针和缓存未命中的次数。 现在我们知道了组件，让我们看看`sync\.Map`内部的哈希 Trie 如何组合这些部分。